2
\$\begingroup\$

I've been thinking up a real-time strategy game that plays on a platformer type of map. The collidable portion of these maps will be made up of square tiles. I've done A* pathfinding in top down tile based games before, but I'm unsure how to lay out my tile map in such a way that allows for easy pathfinding. I've thought up some examples, but I'm not sure if it's the right way to go about it, so I thought I'd throw it out here and see if someone who knows what they're doing can give me some tips.

The first solution I thought of was to use a 2D array storing all of the tiles and empty space, similar to what I would most definitely do in a top down tile based strategy game. The 2D grid would be invisible in the background but really store whether each grid section is empty, or has a tile on it. like this:

2D array example

In this example I'm unsure as to how I would pathfind up hills, or in that specific example, determine that a wall is too high to cross. Lets say that dude can jump over 1 tile high blocks, but 2 tiles is too much. How would I effectively determine that through a pathfinding algorithm?

The other example I was thinking of was to place pathfinding nodes on top of traversible terrain, like this:

Node example

Each node might be able to give directions or commands on how to get to the next (Like the need to jump to cross a gap, or it's faster to go under rather than over, etc). Now I would want to do this logically through code, and not manually place them at design time.

This might be a better solution, but something I'm thinking of in this game is to have destructable terrain. Say an explosion happens and leaves a big hole like this:

Destructable Terrain

Suddenly those nodes I placed earlier won't work. I'd need to remake them on the fly. In this case the 2D grid sounds like the better option since I can just flip the value of that tile from full to empty.

So hopefully those 2 examples made sense, and I'd like some opinions on which might be the best option, or even if there's some other solution I didn't think about I would be glad to hear it! I'm using Unity if that helps.

I just want to get this design choice out of the way early, as it would be a pain to have to tear it apart later.

Thanks!

\$\endgroup\$
3
\$\begingroup\$

A* operates fundamentally on a graph, not a grid. When you create a grid for A* to search, what you've actually done is created something called a "lattice graph." The connections between nodes in the lattice can be anything. They don't have to just be straight lines between neighboring grid cells. In your case, you can combine the best of both worlds just by connecting up neighbors in a different way in the lattice graph. By changing your definition of "neighbor", you can alter the kinds of paths that can be produced by A*.

// Expands the valid neighbors of a cell within a grid.
List<Cell> GetNeighbors(Cell node, Grid grid)
{
    List<Cell> neighbors= new List<Cell>();

    // Get all the cells in the immediate neighborhood
    Cell top      = grid.GetCell(node.x,     node.y + 1);
    Cell left     = grid.GetCell(node.x - 1, node.y);
    Cell bottom   = grid.GetCell(node.x,     node.y - 1);
    Cell right    = grid.GetCell(node.x + 1, node.y);
    Cell topright = grid.GetCell(node.x + 1, node.y + 1);
    Cell topleft  = grid.GetCell(node.x - 1, node.y + 1);

    bool isOnGround = bottom.IsOccupied;
    bool isHeadCovered = top.IsOccupied;

    // If we're not standing on the ground, we can only fall.
    if (!isOnGround)
    {
        neighbors.add(bottom);
        return neighbors;
    }

    //Otherwise, we can try walking left or right
    if (!left.IsOccupied) neighbors.add(left);
    if (!right.IsOccupied) neighbors.add(right);

    // If our head isn't covered, we can try jumping up one, 
    // or up to the left and right.
    if (!isHeadCovered)
    {
        // Only jump up if the cell we're jumping on top of is occupied.
        if (!topleft.IsOccupied && left.IsOccupied) neighbors.add(topleft);
        if (!topright.IsOccupied&& right.IsOccupied) neighbors.add(topright);
    }

    return neighbors;
}

Then, in A*, when you expand nodes, expand only to the valid neighbors. You might also want to expand your definition of "Node" to include the action it took to get to that node (for instance, jumping, falling, or walking), so that the character can take the proper action while following the path. You can also add additional pathfinding constraints like climbing ladders or destroying things.

\$\endgroup\$
  • \$\begingroup\$ Thank you! This is exactly what I was looking for. Now say I had something that could jump more than one block high, 3 or 4 maybe. Would it be a good idea to connect nodes that far away for instance? Or could I achieve the same effect through the pathfinding algorithm itself? For example, would it make sense to include your example: Cell top = grid.GetCell(node.x, node.y + 1); Cell left = grid.GetCell(node.x - 1, node.y); .. Cell topleft = grid.GetCell(node.x - 1, node.y + 1); And then add Cell top2Left, top3Left Cell top2Right, top3Right Or would this be too inefficient? \$\endgroup\$ – Logicon211 Apr 9 '15 at 3:02
  • \$\begingroup\$ the formatting for that comment is off, and I can't edit it :/ but I think it makes sense \$\endgroup\$ – Logicon211 Apr 9 '15 at 3:08
  • \$\begingroup\$ The more nodes you have to evaluate the worse A* is going to perform, but there's nothing stopping you from adding more and more nodes as neighbors. \$\endgroup\$ – mklingen Apr 9 '15 at 15:02
  • \$\begingroup\$ Also I modified the jumping logic in my answer so that you only jump up on top of cells that are occupied. \$\endgroup\$ – mklingen Apr 9 '15 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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