Pathfinding results in false path costs that are too high
- by user2144536
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);
}
