Breadth-first Pathfinding in Turing Help

[rsarvar1a]

What is it you are trying to achieve?
A friend and I are trying to write a pathfinder for a variable number of enemies that will find the best path to the player.

What is the problem you are having?
We seem to be running into errors such as having enemies moving over enemy/player-occupied squares.
Also, the player movement code forbids execution of the move proc if the destination is occupied, but it's still happening, which leads me to believe that the code below is making the wrong square occupied.


Describe what you have tried to solve this problem
We have attempted to include a property of the grid called tiletype (0 means empty, 1 means occupied) which avoids occupied spaces in the building of its path.
These get assigned for each enemy movement so that the enemies shouldn't be able to overlap.

Post any relevant code (You may choose to attach the file instead of posting the code if it is too long)

In which enemyReal is an array 1 .. 50, 1 .. 20 of enemyDec.

Turing:

type * pos : record     x : int     xlast: int     y : int     ylast : int     gnum : int     gnumlast : int     move : int     end record type * enemyDec : record   Name : string     Race : int               Character : char             Status : int         HP : int     ATK : int     DEF : int     LVL : int       Special : int             Inv : array 1 .. 10 of itemDec             Position : pos end record var enemyReal : array 1 .. 50, 1 .. 20 of enemyDec fcn Pathfinder (floori,ei,srcX,srcY,trgX,trgY,move,srcgnum,trggnum : int) : boolean % src is where you are searching from trg is your search target, though this algorithm is one source one target, it has no heuristic or move cost weighting, this algorithm also stores data much like a one source all target algorithm in the grid custom variable type that is wiped later, gnum refers to the number of the grid starting at the top left and going to the right, starting at the left on the next row upon hitting the end of a row, the reason the for loops end at 216 is because the amount of grid spaces in my program happens to be 216, the move parameter is to define how far a "unit" can move, probably useless to you         if enemyReal(floori, ei).Position.gnumlast not= enemyReal(floori, ei).Position.gnum then         grid(enemyReal(floori, ei).Position.gnumlast).tiletype := 0     end if         for i : 1 ..800 %resetting variables used for pathfinding, specifically variables used for storing if a grid space has been searched or visited before in a pathfinding equation to avoid overwriting previous path data         grid(i).pFind.searched := false         grid(i).pFind.visited := false     end for             for i : 1 .. 800 %pQ(i).active stores if that array section contains valid data, if it does not then the program has reached the end of the list of squares that it needs to search and could not find a path and will exit         pQ(i).active := false     end for                 pQ(1).gnum := srcgnum %this series of statements sets the first grid space in the queue to be the source grid defined in the function parameters     pQ(1).gX := srcX     pQ(1).gY := srcY     pQ(1).active := true         grid(pQ(1).gnum).pFind.cameFromN := srcgnum %this is probably uneeded, but sets where the algorithm searched from to be from inside itself     grid(pQ(1).gnum).pFind.cameFromX := srcX     grid(pQ(1).gnum).pFind.cameFromY := srcY         grid(srcgnum).pFind.searched := false %making sure that the source grid is marked as unchecked and unvisited even though earlier it was set as that cause i wanted to make sure :P     grid(srcgnum).pFind.visited := false         cost := 0 %this cost variable makes sure the "unit" stops when it exceeds its movement abilities, probably not needed right now     searching := 0 %this variable increments to keep searching through the grid spaces in the queue(pQ)         loop         searching += 1 %increments every search if the function has not found its target         if (pQ(searching).active = false) then %returns a result of false terminating the function when there are no more grid spaces to be searched as when a section of pQ has valid data its active value is set to true             result false         end if         if (pQ(searching).gY > 1) and (pQ(searching).gnum - 40) > 0 then %this is to make sure it doesn't search above the limits of the grid upwards and return a out of range error                 if (grid(pQ(searching).gnum - 40).pFind.searched = false) then %replace 40 with how many spaces are in a row, 20 is used here to search the gridspace directly above it                 grid(pQ(searching).gnum - 40).pFind.cameFromN := pQ(searching).gnum %stores where it searched from, knowing just that, a path can be constructed                 grid(pQ(searching).gnum - 40).pFind.cameFromX := pQ(searching).gX                 grid(pQ(searching).gnum - 40).pFind.cameFromY := pQ(searching).gY                 grid(pQ(searching).gnum - 40).pFind.searched := true                 if (grid(pQ(searching).gnum - 40).pFind.visited = false and grid(pQ(searching).gnum - 40).tiletype = 0) then %this sets the grid space to be marked as to be visited and searched from if they are not an obstacle and are not occupied by a "unit"                     for i : 1 .. 1000                         if (pQ(i).active = false) then %it finds the lowest number unoccupied array section for storing the values of the to be searched square                             hpQ := i                             pQ(hpQ).gnum := pQ(searching).gnum - 40                             pQ(hpQ).gX := pQ(searching).gX                             pQ(hpQ).gY := pQ(searching).gY - 1                             exit                         end if                     end for                         pQ(hpQ).gnum := pQ(searching).gnum - 40 %i dont know why this is here again but just keep not that pQ(hpQ).active := true is missing from the above for loop iteration                     pQ(hpQ).gX := grid(pQ(searching).gnum - 40).idX                     pQ(hpQ).gY := grid(pQ(searching).gnum - 40).idY                     pQ(hpQ).active := true                 end if             end if         end if         if (pQ(searching).gX > 1) then %the same thing except instead of searching upwards, it searches to the left             if (grid(pQ(searching).gnum - 1).pFind.searched = false) then                 grid(pQ(searching).gnum - 1).pFind.cameFromN := pQ(searching).gnum                 grid(pQ(searching).gnum - 1).pFind.cameFromX := pQ(searching).gX                 grid(pQ(searching).gnum - 1).pFind.cameFromY := pQ(searching).gY                 grid(pQ(searching).gnum - 1).pFind.searched := true                 if (grid(pQ(searching).gnum - 1).pFind.visited = false and grid(pQ(searching).gnum - 1).tiletype = 0) then                     for i : 1 .. 1000                         if (pQ(i).active = false) then                             hpQ := i                             pQ(hpQ).gnum := pQ(searching).gnum - 1                             pQ(hpQ).gX := pQ(searching).gX - 1                             pQ(hpQ).gY := pQ(searching).gY                             exit                         end if                     end for                         pQ(hpQ).gnum := pQ(searching).gnum - 1                     pQ(hpQ).gX := grid(pQ(searching).gnum - 1).idX                     pQ(hpQ).gY := grid(pQ(searching).gnum - 1).idY                     pQ(hpQ).active := true                 end if             end if         end if         if (pQ(searching).gY < 20) then %searches downwards             if (grid(pQ(searching).gnum + 40).pFind.searched = false) then                 grid(pQ(searching).gnum + 40).pFind.cameFromN := pQ(searching).gnum                 grid(pQ(searching).gnum + 40).pFind.cameFromX := pQ(searching).gX                 grid(pQ(searching).gnum + 40).pFind.cameFromY := pQ(searching).gY                 grid(pQ(searching).gnum + 40).pFind.searched := true                 if (grid(pQ(searching).gnum + 40).pFind.visited = false and grid(pQ(searching).gnum + 40).tiletype = 0) then                     for i : 1 .. 1000                         if (pQ(i).active = false) then                             hpQ := i                             pQ(hpQ).gnum := pQ(searching).gnum + 40                             pQ(hpQ).gX := pQ(searching).gX                             pQ(hpQ).gY := pQ(searching).gY + 1                             exit                         end if                     end for                         pQ(hpQ).gnum := pQ(searching).gnum + 40                     pQ(hpQ).gX := grid(pQ(searching).gnum + 40).idX                     pQ(hpQ).gY := grid(pQ(searching).gnum + 40).idY                     pQ(hpQ).active := true                 end if             end if         end if         if (pQ(searching).gX < 40) and (pQ(searching).gnum + 1) < 40 then %dont ask why it searches up left down and then right             if (grid(pQ(searching).gnum + 1).pFind.searched = false) then                 grid(pQ(searching).gnum + 1).pFind.cameFromN := pQ(searching).gnum                 grid(pQ(searching).gnum + 1).pFind.cameFromX := pQ(searching).gX                 grid(pQ(searching).gnum + 1).pFind.cameFromY := pQ(searching).gY                 grid(pQ(searching).gnum + 1).pFind.searched := true                 if (grid(pQ(searching).gnum + 1).pFind.visited = false and grid(pQ(searching).gnum + 1).tiletype = 0) then                     for i : 1 .. 1000                         if (pQ(i).active = false) then                             hpQ := i                             pQ(hpQ).gnum := pQ(searching).gnum + 1                             pQ(hpQ).gX := pQ(searching).gX                             pQ(hpQ).gY := pQ(searching).gY + 1                             exit                         end if                     end for                         pQ(hpQ).gnum := pQ(searching).gnum + 1                     pQ(hpQ).gX := grid(pQ(searching).gnum + 1).idX                     pQ(hpQ).gY := grid(pQ(searching).gnum + 1).idY                     pQ(hpQ).active := true                 end if             end if         end if                 grid(pQ(searching).gnum).pFind.visited := true %after searching everywhere around the grid space it is marked as being visited as to not be visited again, consuming unnecessary resources and slowing the function down                 if (grid(trggnum).pFind.visited = true) then %checks to see if the target has been visited yet             pathlength := 0 %this stores how long the path will be as the path is constructed from target to source and needs to be put in reverse using a decreasing for loop for my purposes as the character would look wfloori, eird going from thfloori, eir target back to where they came from, this probably doesn't matter to you though             currentGnum := trggnum %current is used as the "unit" to measure the distance between source and target             currentX := trgX             currentY := trgY             loop                 pathlength += 1 %every time current is not back to the source the path length increments to store the length of the path                 path(pathlength).gnum := currentGnum %the array path is used to store the whole path for cost computation, probably uneeded for you                 path(pathlength).gX := currentX                 path(pathlength).gY := currentY                 currentX := grid(currentGnum).pFind.cameFromX                 currentY := grid(currentGnum).pFind.cameFromY                 currentGnum := grid(currentGnum).pFind.cameFromN                 exit when path(pathlength).gnum = srcgnum %exit when the path is complete             end loop             for decreasing i : pathlength .. 1 by 1 %reverses the path to find if the path exceeds cost limits, again uneeded for you                 cost += grid(path(i).gnum).pFind.mCost                 if (cost >= move) then %returns false if cost exceeds move                     result false                 end if                 exit when i = 2 %exits when next to target, set to one for exit when on target             end for                 if enemyReal(floori, ei).Position.x not= Player.Position.x or enemyReal(floori, ei).Position.y not= Player.Position.y then                                 enemyReal(floori, ei).Position.x := path(pathlength - 1).gX                 enemyReal(floori, ei).Position.y := path(pathlength - 1).gY                 enemyReal(floori, ei).Position.gnum := path(pathlength - 1).gnum                                 if pathlength > 1 then                     grid(enemyReal(floori, ei).Position.gnumlast).tiletype := 0 % Where gnumlast is the old gnum from before the execution of this function, this is so that squares don't get forever locked up as occupied                                     grid(enemyReal(floori, ei).Position.gnum).tiletype := 1 % Assigns the new one after so that if the enemy doesnt move the tiletype becomes 0 but then goes back to 1, instead of in reverse                 end if                             end if             result true %if the path passes through the test it returns positive         end if     end loop end Pathfinder

Please specify what version of Turing you are using
4.1.1

[Nathan4102]

Turing is an eyesore to read, especially in large functions like this, so I don't think I'll find your problem, but I can offer some suggestions.

You have way too much happening in your path finding function. Functions are made to break problems down into smaller manageable ones. What happens when you cram so much stuff into one function like this, is it becomes impossible to debug.

Also, most path-finding algorithms either return the next step, or a finished path to the end goal. I'm not too sure why yours returns a boolean.

Perhaps someone can find your issue, but if not, I'd suggest breaking it down into small pieces. Test each piece separately, and you'll be able to find where your problem lies much easier.

You might have seen jokes online saying programming is 5% coding and 95% debugging, its no lie! Good debugging strategies will make your life 1000x easier.

Good luck!