A* pathfinding for an isometric map

Question

I am making an isometric tower defense game in XNA and trying to implement the A* pathfinding algorithms for my enemy AI. I am quite new to programming, especially AI and pathfinding, so please excuse my lack of knowledge.

I am using an a* tutorial from an XNA game programming book but it is made for standard square tile maps. I am trying to adapt this into my isometric tile engine and running into a few problems. Firstly, here are the major differences between the two maps:

Book:

• Tiles are 32x32.
• directions are up, down, left, right.
• obstacles are wall tiles

My Map:

• tiles are 64 x 64
• 4 directions: NE, NW, SE, SW
• impassable tiles

From these differences, I can figure out that I have to make changes to the grid setup, cost calculation and tile types.

I have made adjustments for the latter two, but I am having problems setting up the grid/gridnodes which is the most important part. Or perhaps, I simply don't understand the code well enough.

Here is the code for the Pathnode:

class PathNode
{

    public PathNode ParentNode;
    public PathNode EndNode;
    private Vector2 gridLocation;
    public float TotalCost;
    public float DirectCost;
    public Vector2 GridLocation
    {
        get { return gridLocation; }
        set
        {
            gridLocation = new Vector2(
               (float)MathHelper.Clamp(value.X, 0f, (float)50),
               (float)MathHelper.Clamp(value.Y, 0f, (float)50));
        }
    }

    public int GridX
    {
        get { return (int)gridLocation.X; }
    }

    public int GridY
    {
        get { return (int)gridLocation.Y; }
    }

    public PathNode(
        PathNode parentNode,
        PathNode endNode,
        Vector2 gridLocation,
        float cost)
    {
        ParentNode = parentNode;
        GridLocation = gridLocation;
        EndNode = endNode;
        DirectCost = cost;
        if (!(endNode == null))
        {
            TotalCost = DirectCost + LinearCost();
        }
    }

    public float LinearCost()
    {
        return (
            Vector2.Distance(
            EndNode.GridLocation,
            this.GridLocation));
    }



    public bool IsEqualToNode(PathNode node)
    {
        return (GridLocation == node.GridLocation);
    }


}

What should I change in this class to adapt this pathnode.cs to an isometric map? It is probably the gridLocation property but I am stumped as to what should be in there.

Any other tips on isometric pathfinding would be greatly appreciated!

Answer 1

Can't give you code, but I'll try to help you with this problem by explaining it in a different way so that you can apply what you know to solve it.

1) Grid size shouldn't matter. The data structure in which you store objects should be agnostic about such things. Take the chess board example above. I could double or halve the size of the board, but as long as I know the coordinates, it doesn't matter for any internal mechanics, only for rendering.

2) Isometric verus normal grid also doesn't matter. Either way you have the same exact grid, it is only roated. As you can see, I took the same board and converted it to an isometric view. My pieces would still be in the same exact spot and could still use the same exact logic.

3) Impassible tiles are actually easier than walls between grids. Your program knows how to move and it already knows positions of objects in terms of grid cells. You just need to mark the object in that grid on if you can move through it or not.

I usually do this by creating data structures, one for static objects and one for objects that change. The static objects are filled with objects that tell the game how to render the map. It also says if you can move through that tile or not. Thus to see if you can move there, you get all of the objects in that grid space and check them all for the flag. If all allow you to pass, then you can move through it.