Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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!

share|improve this question
4  
I think my answer to a similar question might help: gamedev.stackexchange.com/a/27276/9366 starting at the second paragraph. –  John McDonald May 17 '12 at 21:28
3  
Isometric pathfinding is no different from standard grid based pathfinding. The only difference between the two is how you're displaying it. If you think of it that way, you'll have a much easier time. EDIT Oh, which is what John is basically saying with his link. –  Byte56 May 17 '12 at 21:29
add comment

1 Answer

up vote 2 down vote accepted

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.

enter image description here

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. enter image description here 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.

share|improve this answer
    
+1 Well put, and pictures to go with –  John McDonald May 18 '12 at 14:23
    
Hi! Thanks for the pics and explanation. Please tell me if I'm wrong, it seems to me that a grid "Node" or "cell" cannot be a purely conceptual entity or else the pathfinder wouldn't know how much distance to travel to reach the next node. It must have physical properties such as node size. From my understanding, A* overlays a grid of nodes on top of whatever map you already have, and checks these nodes to form the most efficient path. Wouldn't it be best if the node size was the same as the size of each tile on a given map? This is why I find it puzzling that Pathnode.cs only has GridLocation –  user1332755 May 18 '12 at 19:52
    
So in pure A*, nodes can be completely conceptual. This is because you create a "link" between nodes and the link itself knows the cost going from your start to your end. Thus there is only a path between two nodes if a link exists. –  Xphile May 24 '12 at 0:31
    
Usually when you put this onto a 2d map, you can remove the complexity of having links because you have x,y coordinates and can calculate the distance/cost between two positions. Really it doesn't matter if the distance between A1 and B1 is 1 or 160, because everything is at the same scale. Using 1 just makes everything on the back end easier. (damn, tried to add this to my above comment) –  Xphile May 24 '12 at 0:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.