# Pathfinding results in false path costs that are too high

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

}

• 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. Jun 27, 2013 at 18:28
• I will +1 for a great debugging technique. It would have been very difficult to track down the problem without that visual aid. Jun 27, 2013 at 22:45

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.

• 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. Jun 27, 2013 at 19:45
• Yes. That's Dijkstra :) Jun 27, 2013 at 19:52
• 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