Pathfinding results in false path costs that are too high

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/28 4:29 UTC
Read the original article Hit count: 345

Filed under:
|
|
|

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);


}

© Game Development or respective owner

Related posts about java

Related posts about 2d