# A*, Tile costs and heuristic; How to approach

I'm doing exercises in tile games and AI to improve my programming. I've written a highly unoptimised pathfinder that does the trick and a simple tile class.

The first problem i ran into was that the heuristic was rounded to int's which resulted in very straight paths. Resorting to a Euclidian Heuristic seemed to fixed it as opposed to use the Manhattan approach.

The 2nd problem I ran into was when i tried added tile costs. I was hoping to use the value's of the flags that i set on the tiles but the value's were too small to make the pathfinder consider them a huge obstacle so i increased their value's but that breaks the flags a certain way and no paths were found anymore.

So my questions, before posting the code, are:

1. What am I doing wrong that the Manhatten heuristic isnt working?
2. What ways can I store the tile costs? I was hoping to (ab)use the enum flags for this
3. The path finder isnt considering the chance that no path is available, how do i check this?
4. Any code optimisations are welcome as I'd love to improve my coding.

public static List<Tile> FindPath( Tile startTile, Tile endTile, Tile[,] map )
{
return FindPath( startTile, endTile, map, TileFlags.WALKABLE );
}

public static List<Tile> FindPath( Tile startTile, Tile endTile, Tile[,] map, TileFlags acceptedFlags )
{
List<Tile> open = new List<Tile>();
List<Tile> closed = new List<Tile>();

Tile tileToCheck;

do
{
tileToCheck = open;

open.Remove( tileToCheck );

for( int i = 0; i < tileToCheck.neighbors.Count; i++ )
{
Tile tile = tileToCheck.neighbors[ i ];

//has the node been processed
if( !closed.Contains( tile ) && ( tile.flags & acceptedFlags ) != 0 )
{
//Not in the open list?
if( !open.Contains( tile ) )
{
//Set G
int G = 10;
G += tileToCheck.G;

//Set Parent
tile.parentX = tileToCheck.x;
tile.parentY = tileToCheck.y;
tile.G = G;
//tile.H = Math.Abs(endTile.x - tile.x ) + Math.Abs( endTile.y - tile.y ) * 10;
//TODO omg wtf and other incredible stories
tile.H = Vector2.Distance( new Vector2( tile.x, tile.y ), new Vector2(endTile.x, endTile.y) );
tile.Cost =  tile.G + tile.H + (int)tile.flags; //Calculate H; Manhattan style

}
//Update the cost if it is
else
{
int G = 10;//cost of going to non-diagonal tiles
G += map[ tile.parentX, tile.parentY ].G;

//If this path is shorter (G cost is lower) then change
//the parent cell, G cost and F cost.
if ( G < tile.G ) //if G cost is less,
{
tile.parentX = tileToCheck.x; //change the square's parent
tile.parentY = tileToCheck.y;
tile.G = G;//change the G cost
tile.Cost =  tile.G + tile.H + (int)tile.flags; // add terrain cost
}
}
}
}

//Sort costs
open = open.OrderBy( o => o.Cost).ToList();
}
while( tileToCheck != endTile );

closed.Reverse();

List<Tile> validRoute = new List<Tile>();
Tile currentTile = closed[ 0 ];

do
{
//Look up the parent of the current cell.
currentTile = map[ currentTile.parentX, currentTile.parentY ];
currentTile.renderer.material.color = Color.green;
}
while ( currentTile != startTile );

validRoute.Reverse();

return validRoute;
}


And my Tile class:

[Flags]
public enum TileFlags: int
{
NONE = 0,
DIRT = 1,
STONE = 2,
WATER = 4,
BUILDING = 8,

//handy
WALKABLE = DIRT | STONE | NONE,
endofenum
}

public class Tile : MonoBehaviour
{
//Tile Properties
public int x, y;
public TileFlags flags = TileFlags.DIRT;
public Transform cachedTransform;

//A* properties
public int parentX, parentY;
public int G;
public float Cost;
public float H;
public List<Tile> neighbors = new List<Tile>();

void Awake()
{
cachedTransform = transform;
}
}

• Might not be optimized either but I kept tables of costs and walkability corresponding to the enum list. Instead of using power of two I simply used the enum as indices. like if(unit.walkable[currentNode.tiletype]) or gcost = 10 + unit.costs[currentNode.tiletype]. I did this because units in my game could have different walk behavior. So each unit held its own tables or a shared common table. Trough creating a common interface I'd ask the cost and walkability which allowed me to implement different rules or behaviors for each unit. – Sidar Nov 3 '13 at 23:19
• Note: "tile.H = Math.Abs(endTile.x - tile.x ) + Math.Abs( endTile.y - tile.y ) * 10;" is multiplying only the second Abs by 10, and not the first. You need parentheses if you want to multiply both by 10 (and you do) – amitp Nov 4 '13 at 7:02
• @Sidar You make a good point separating the data, thank you. – Kevin Toet Nov 4 '13 at 9:52
• @amitp Dont know how i missed that! Also I was using a link to the A* basics from your site. It's a valuable resource! Thank you so much. For the heuristic though, if i use whole ints as H i get straight corridors as it were. due to two neighbours having the same results, it would keep picking the results in the same direction – Kevin Toet Nov 4 '13 at 9:53

## What am I doing wrong that the Manhattan Heuristic isn't working?

The Manhattan distance doesn't work as a heuristic for A*, as the heuristic for A* must never overestimate the distance. But, the Manhattan distance is always larger or equal to the real distance.

The Manhattan distance would work, if you only allow 90 degree movements (left, right, up, down on the map). If you restrict your movements to 45 degree movements (straight and diagonal moves) on a chess-board map you can use the maximum of the difference in x and y coordinates like this: max((x2-x1),(y2-y1)). If you use the Euclidean Distance to calculate costs as an integer, use floor() for rounding "down" the number to the next integer value (should be equivalent to converting the float to an int).

If your map size is limited and you have a lot of RAM you could also use a lookup-table for x/y-Distances to Euclidean Distance. Or just to lookup the square roots (uses much less memory usage, but you'll still need to the multiplications):

Explanation (why overestimation isn't working): The estimation is used to sort the path-finding approaches in a way so that the first solution found, is the "shortest" path (or path with the lowest costs). This works by summing up the costs for the reaching the current position (of each approach) and the minimum rest costs, which might in fact be estimated as zero (0) but must never exceed the actual costs needed. When estimated as zero, the search is equivalent to breadth-first search. But, if the estimation would exceed the actual costs, the optimal approach is most likely put in too "late" into the priority queue and a suboptimal solution is found before it.

Explanation (why max works): If there are no obstacles you can always walk diagonal until you reached the column or row of the target tile and then move straight the rest of the way. This way you reach the target with the distance that is equal to the maximum of the distances of the x and y coordinates (between current position and target position). Note that this is only validated for tiles arrange in a chess boards fashion. If working with arrangements like octagons, this might be different!

## What ways can I store the tile costs? I was hoping to (ab)use the enum flags for this

Use a function (or lookup-table) that returns the costs for each type of tile.

int tileCosts(TileFlags flags) {
switch (flags) {
case TileFlags.DIRT: return COSTS_DIRT;
case TileFlags.STONE: return COSTS_STONE;
case TileFlags.STONE|TileFlags.DIRT: return COSTS_DIRTY_STONES;
default:
// Handle undefined flags error...
}
}


You can also use a lookup-table instead of the function. How ever, both methods allow you to set the costs for any tile type/combination independent of the flags value AND it helps to keep your code readable. If you use "flags" as costs, you'll most likely produce faulty code.

## The path finder isn't considering the chance that no path is available, how do i check this?

You can check this, by checking if your "open" list is empty. If it becomes empty, there are no more possible solutions left that are worth investigating (the shortest path to each reachable tile on the map has been calculated.

## Any code optimisations are welcome as I'd love to improve my coding.

Your performance problems are most likely not due to the Euclidean Distance calculations but because of inefficient sorting of the "open" list. The sort function needs a lot of computation time. You can heavily improve the speed if you do not use "open.Add( tile );" and "open.sort()". Because this sorts the whole list when inserting a single tile (causing N*log2(N) comparisons, if N = number of elements in the list). Instead you should "insert" the tile into the right position. This only needs to scan the list at most once (N comparisons). Instead of programming this your own you can either use the "merge" method of your list. To do that, insert your new tile into a new list and merge the list into the new list. Or, you can use a the container type "priority_queue" instead (see http://www.cplusplus.com/reference/queue/priority_queue/), which is what you are actually simulating...

As mentioned above, you should use functions for special and complex operations (e.g. getting the costs for traversing a tile). Never do something tricky without putting a source code comment next to it.

For example, this should be done in a function (or better: a method of the Tile class):

tile.Cost =  tile.G + tile.H + (int)tile.flags; //Calculate H; Manhattan style


You should also use speaking names for the properties of the tiles (what do "G", "H" mean? I have to look it up elsewhere or even have to guess what it could mean, which makes the code unreadable).

Keep your functions short! When editing a function you should see the whole function on the screen, without scrolling. They should each implement only -one- algorithm. For example A* and nothing else! Everything else, as Manhattan Distance calculations should be put into separate functions/methods.

• I had two separate functions for getting the path. When I search a path I return a boolean on whether a path was actually found and one that returns the actual path.Like: if( AStar.search(...) ) {AStar.getPath(); }. Not sure how limited this is to his needs. – Sidar Nov 4 '13 at 17:23
• @Sidar any feedback is greatly welcome. Already learned a ton from the replies. – Kevin Toet Nov 5 '13 at 10:53
• @Kevin: Note, if you use the Euklidien Distance and allow diagonal movements ... You either 1. need to divide the distance by the calculated length of the diagonal move (which is sqrt(2) or 2. you have to use sqrt(2) as the cost for the diagonal moves. Else the Euclidean Distance will again overestimate the residual distances and A* will not work correctly. But I suggest you to use the max(...) of the x/y-coordinate-difference anyway. – SDwarfs Nov 5 '13 at 14:35