2
\$\begingroup\$

I'm trying to implement pathfinding in a game I'm programming using this method. I'm implementing it with recursion but some of the values after the immediate circle of tiles around the player are way off. For some reason I cannot find the problem with it. This is a screen cap of the problem:

enter image description here

The pathfinding values are displayed in the center of every tile. Clipped blocks are displayed with the value of 'c' because the values were too high and were covering up the next value. The red circle is the first value that is incorrect. The code below is the recursive method.

//tileX is the coordinates of the current tile, val is the current pathfinding value, used[][] is a boolean 
//array to keep track of which tiles' values have already been assigned
public void pathFind(int tileX, int tileY, int val, boolean[][] used)
{
    //increment pathfinding value
    int curVal = val + 1;

    //set current tile to true if it hasn't been already
    used[tileX][tileY] = true;

    //booleans to know which tiles the recursive call needs to be used on
    boolean topLeftUsed = false, topUsed = false, topRightUsed = false, leftUsed = false, rightUsed = false, botomLeftUsed = false, botomUsed = false, botomRightUsed = false;

    //set value of top left tile if necessary
    if(tileX - 1 >= 0 && tileY - 1 >= 0)
    {
            //isClipped(int x, int y) returns true if the coordinates givin are in a tile that can't be walked through (IE walls)
            //occupied[][] is an array that keeps track of which tiles have an enemy in them
            //
            //if the tile is not clipped and not occupied set the pathfinding value
            if(isClipped((tileX - 1) * 50 + 25, (tileY - 1) * 50 + 25) == false && occupied[tileX - 1][tileY - 1] == false && !(used[tileX - 1][tileY - 1]))
            {
                pathFindingValues[tileX - 1][tileY - 1] = curVal;

                topLeftUsed = true;

                used[tileX - 1][tileY - 1] = true;

            }

            //if it is occupied set it to an arbitrary high number so enemies find alternate routes if the best is clogged
            if(occupied[tileX - 1][tileY - 1] == true)
                pathFindingValues[tileX - 1][tileY - 1] = 1000000000;

            //if it is clipped set it to an arbitrary higher number so enemies don't travel through walls
            if(isClipped((tileX - 1) * 50 + 25, (tileY - 1) * 50 + 25) == true)
                pathFindingValues[tileX - 1][tileY - 1] = 2000000000;
    }

    //top middle
    if(tileY - 1 >= 0 )
    {
            if(isClipped(tileX * 50 + 25, (tileY - 1) * 50 + 25) == false && occupied[tileX][tileY - 1] == false && !(used[tileX][tileY - 1]))
            {
                pathFindingValues[tileX][tileY - 1] = curVal;

                topUsed = true;

                used[tileX][tileY - 1] = true;

            }

            if(occupied[tileX][tileY - 1] == true)
                pathFindingValues[tileX][tileY - 1] = 1000000000;

            if(isClipped(tileX * 50 + 25, (tileY - 1) * 50 + 25) == true)
                pathFindingValues[tileX][tileY - 1] = 2000000000;
    }

    //top right
    if(tileX + 1 <= used.length && tileY - 1 >= 0)
    {
            if(isClipped((tileX + 1) * 50 + 25, (tileY - 1) * 50 + 25) == false && occupied[tileX + 1][tileY - 1] == false && !(used[tileX + 1][tileY - 1]))
            {
                pathFindingValues[tileX + 1][tileY - 1] = curVal;

                topRightUsed = true;

                used[tileX + 1][tileY - 1] = true;

            }

            if(occupied[tileX + 1][tileY - 1] == true)
                pathFindingValues[tileX + 1][tileY - 1] = 1000000000;

            if(isClipped((tileX + 1) * 50 + 25, (tileY - 1) * 50 + 25) == true)
                pathFindingValues[tileX + 1][tileY - 1] = 2000000000;
    }

    //left
    if(tileX - 1 >= 0)
    {
            if(isClipped((tileX - 1) * 50 + 25, (tileY) * 50 + 25) == false && occupied[tileX - 1][tileY] == false && !(used[tileX - 1][tileY]))
            {
                pathFindingValues[tileX - 1][tileY] = curVal;

                leftUsed = true;

                used[tileX - 1][tileY] = true;

            }

            if(occupied[tileX - 1][tileY] == true)
                pathFindingValues[tileX - 1][tileY] = 1000000000;

            if(isClipped((tileX - 1) * 50 + 25, (tileY) * 50 + 25) == true)
                pathFindingValues[tileX - 1][tileY] = 2000000000;
    }

    //right
    if(tileX  + 1 <= used.length)
    {
            if(isClipped((tileX + 1) * 50 + 25, (tileY) * 50 + 25) == false && occupied[tileX + 1][tileY] == false && !(used[tileX + 1][tileY]))
            {
                pathFindingValues[tileX + 1][tileY] = curVal;

                rightUsed = true;

                used[tileX + 1][tileY] = true;

            }

            if(occupied[tileX + 1][tileY] == true)
                pathFindingValues[tileX + 1][tileY] = 1000000000;

            if(isClipped((tileX + 1) * 50 + 25, (tileY) * 50 + 25) == true)
                pathFindingValues[tileX + 1][tileY] = 2000000000;
    }

    //botom left
    if(tileX  - 1 >= 0 && tileY + 1 <= used[0].length)
    {
            if(isClipped((tileX - 1) * 50 + 25, (tileY + 1) * 50 + 25) == false && occupied[tileX - 1][tileY + 1] == false && !(used[tileX - 1][tileY + 1]))
            {
                pathFindingValues[tileX - 1][tileY + 1] = curVal;

                botomLeftUsed = true;

                used[tileX - 1][tileY + 1] = true;

            }

            if(occupied[tileX - 1][tileY + 1] == true)
                pathFindingValues[tileX - 1][tileY + 1] = 1000000000;

            if(isClipped((tileX - 1) * 50 + 25, (tileY + 1) * 50 + 25) == true)
                pathFindingValues[tileX - 1][tileY + 1] = 2000000000;
    }

    //botom middle
    if(tileY + 1 <= used[0].length)
    {
            if(isClipped((tileX) * 50 + 25, (tileY + 1) * 50 + 25) == false && occupied[tileX][tileY + 1] == false && !(used[tileX][tileY + 1]))
            {
                pathFindingValues[tileX][tileY + 1] = curVal;

                botomUsed = true;

                used[tileX][tileY + 1] = true;

            }

            if(occupied[tileX][tileY + 1] == true)
                pathFindingValues[tileX][tileY + 1] = 1000000000;

            if(isClipped((tileX) * 50 + 25, (tileY + 1) * 50 + 25) == true)
                pathFindingValues[tileX][tileY + 1] = 2000000000;
    }

    //botom right
    if(tileX  + 1 <= used.length && tileY + 1 <= used[0].length)
    {
            if(isClipped((tileX + 1) * 50 + 25, (tileY + 1) * 50 + 25) == false && occupied[tileX + 1][tileY + 1] == false && !(used[tileX + 1][tileY + 1]))
            {
                pathFindingValues[tileX + 1][tileY + 1] = curVal;

                botomRightUsed = true;

                used[tileX + 1][tileY + 1] = true;

            }

            if(occupied[tileX + 1][tileY + 1] == true)
                pathFindingValues[tileX + 1][tileY + 1] = 1000000000;

            if(isClipped((tileX + 1) * 50 + 25, (tileY + 1) * 50 + 25) == true)
                pathFindingValues[tileX + 1][tileY + 1] = 2000000000;
    }


    //call the method on the tiles that need it
    if(tileX - 1 >= 0 && tileY - 1 >= 0 && topLeftUsed)     
        pathFind(tileX - 1, tileY - 1, curVal, used);

    if(tileY - 1 >= 0 && topUsed)
        pathFind(tileX , tileY - 1, curVal, used);

    if(tileX + 1 <= used.length && tileY - 1 >= 0 && topRightUsed)
        pathFind(tileX + 1, tileY - 1, curVal, used);

    if(tileX - 1 >= 0 && leftUsed)
        pathFind(tileX - 1, tileY, curVal, used);

    if(tileX  + 1 <= used.length && rightUsed)
        pathFind(tileX + 1, tileY, curVal, used);

    if(tileX  - 1 >= 0 && tileY + 1 <= used[0].length && botomLeftUsed)
        pathFind(tileX - 1, tileY + 1, curVal, used);

    if(tileY + 1 <= used[0].length && botomUsed)
        pathFind(tileX, tileY + 1, curVal, used);

    if(tileX  + 1 <= used.length && tileY + 1 <= used[0].length && botomRightUsed)
        pathFind(tileX + 1, tileY + 1, curVal, used);


}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I assume the question is "how do I fix my code?"? This might be a bit to much like a code dump question. I bet if you traced a path around your map you'd find that your algorithm is calculating the cost based on the last node it processed and not the actual distance from the starting point. Might want to look into that. \$\endgroup\$
    – House
    Commented Jun 27, 2013 at 18:28
  • \$\begingroup\$ I will +1 for a great debugging technique. It would have been very difficult to track down the problem without that visual aid. \$\endgroup\$
    – House
    Commented Jun 27, 2013 at 22:45

1 Answer 1

Reset to default
3
\$\begingroup\$

I believe that problem in your code is with "used". You are not trying to find shortest path or cheapest. You are searching for first path you can find.

You implemented DFS algorithm (depth-first-search). Everytime you grab tile to the top left and update it's state and it's neighbors. Then you take tile to the top left from this tile and again. And it goes to the end of map. Then it goes to the top as much as it can. Then it will explore tiles in some other ways. It's definitely not growing in all direction at the same time.

Anyway: Solution may be to implement BFS (breadth-first-search) - you will put your tiles to some queue instead of processing them immediately. You shouldn't update value in neighbors, but instead just put that neighbor to the end of the queue. When you push it from queue, you will update it's value.

The best (and maybe - for you - simplest) way is to implement something like Dijkstra's algorithm - don't use "used" variable, instead try to update value everytime - if it's higher or equal than stored value, then stop. If it's lower, update value in tile and proceed to neighbors (again - compare value). But Dijkstra is probably also more suitable with BFS-based search, not DFS.

\$\endgroup\$
4
  • \$\begingroup\$ Another thing you can do is upon entering a tile that has been visited previously, check if the number on that tile is lower than your current move distance, you can throw out the current move as there is already a shorter path to the node. \$\endgroup\$
    – UnderscoreZero
    Commented Jun 27, 2013 at 19:45
  • \$\begingroup\$ Yes. That's Dijkstra :) \$\endgroup\$
    – zacharmarz
    Commented Jun 27, 2013 at 19:52
  • \$\begingroup\$ If you want to do a depth first search you need to use iterative deepening to get the shortest path. en.wikipedia.org/wiki/IDA%2A \$\endgroup\$
    – Adam
    Commented Jun 27, 2013 at 23:15
  • \$\begingroup\$ Thanks! I just added a check to see if curVal is less than the value being checked and it works! \$\endgroup\$
    – user2144536
    Commented Jun 30, 2013 at 18:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .