A*, Tile costs and heuristic; How to approach
- by Kevin Toet
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 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:
What am I doing wrong that the Manhatten heuristic isnt working?
What ways can I store the tile costs? I was hoping to (ab)use the enum flags for this
The path finder isnt considering the chance that no path is available, how do i check this?
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>();
open.Add( startTile );
Tile tileToCheck;
do
{
tileToCheck = open[0];
closed.Add( tileToCheck );
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
open.Add( tile );
}
//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 ];
validRoute.Add( currentTile );
do
{
//Look up the parent of the current cell.
currentTile = map[ currentTile.parentX, currentTile.parentY ];
currentTile.renderer.material.color = Color.green;
//Add tile to list
validRoute.Add( currentTile );
}
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;
}
}
