AStar for isometric game with overlapping walkable areas

Question

We're developing an isometric game that so far has had a single ground level (y = 0) for the avatar to walk on. Pathfinding for this can be solved with a relatively simple 2D AStar tile map.

We're now looking to add objects in the world that can elevate the avatar. There will be overlapping walkable areas, thus creating a problem of pathfinding in 3D space. These objects are distributed sparsely in the room, so I want to avoid keeping an entire 3D map of the room for a 3D AStar implementation. I've attached screenshots to illustrate.

What is the best way to accomplish this?

Answer 1

It depends. If the elevated surfaces could lead to other rooms, it could get very complicated unless the A* optimization function you are running is tailored with information specific to that room layout, it may need to search every possible path (like BFS).

How to handle this issue:

Complexity:

You need a meta graph that represents rooms; i.e to get from room A to room D I go through A => E => B => D. Each room has a few exit nodes, so instead of searching the whole map, I first search the meta graph that represents each room as a single node and then inside each room, I only need to search from the entrance to the closest relevant exit.

Sparsity:

To represent the sparse 3d matrix of surfaces, use a hash table, every elevated surface in a room will have a vector key position in the hash (x, y, z). Each surface will be able to access any other surface in (x +/- 1, y +/- 1, z +/-1). Since you separated the world into rooms or sections, the A* graph hash for each room will be reasonably sized.

Answer 2

As long as there are no overlapping walkable areas, you can keep 2D A*. You just need to add a height info to tiles and make a rule, that character can walk from tile to tile if height difference is less than X.

If there are overlapping areas you need to go kind of 3D. You can get away with several separate layers for your room, where each layer contains info about walkable areas on given height. Then to use A* you need to check not only direct neighbors of the tile, but also tiles in +/-1 layer above/below.

Answer 3

I can suggest to transform your "2d space with heigth" into a graph. Them use an A* on that graph . Example each walkable tile become a graph "node", and then add an "arc" for each "adiacent tiles" (even at different heigths)

Answer 4

I would prefer to reuse the data structure you already have. So basically a 2D grid that is the floor with a bunch of entities that are put over it.

A* actually works over a graph, so the trick is to make a decent abstract programming interface (API) for a graph. 2D or 3D grid A* is a trick by implicitly converting a grid into a graph with the shape of a lattice graph, where the nodes correspond to the cases of the grid and where the edges connect neighbouring cases of that grid.

In your modified graph,

• Like a lattice graph, each case of the floor is a node, connected to its four neighbours "by default".
• However, each entity/object is also a node, connected to neighbour entities provided they have sufficient height so a character can walk across.
• A case or entity with another entity stacked right on top of it have its connections removed (because you cannot walk onto it since you cannot go through the entity stacked right over it). A node without any connections is a pointless as no node on the graph in the computation of A*, so you can keep it alive (and possibly reconnect it later).
• ... (Depending on your game rules, you may wish to alter this interface, like adding weight on edges, ... )

Now, all you have to do is to implement A*, but not by following regular 2D or 3D neighbours to travel, but by following connections (a.k.a edges). Two nodes are neighbours if and only if they are connected. You may wish to learn how to do A* on a general graph structure.