Having trouble with pathfinding
        Posted  
        
            by 
                user2144536
            
        on Game Development
        
        See other posts from Game Development
        
            or by user2144536
        
        
        
        Published on 2013-06-27T18:22:18Z
        Indexed on 
            2013/06/27
            22:29 UTC
        
        
        Read the original article
        Hit count: 295
        
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:

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);
}
© Game Development or respective owner