# AStar for isometric game with overlapping walkable areas

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?

• If the characters can never walk underneath these objects, then you can still use a 2D A* implementation. Just elevate the character by the height of your object. Add a field in each tile, y, and modify your algorithm to only produce a positive result when the y-difference between two tiles is <= 1. – user39686 Feb 2 '15 at 19:01
• Thanks for the response. There will be overlapping areas, so the y-offset approach wont work. I've made the edit to the original question. – Jimmy Xu Feb 2 '15 at 19:03

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.

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.

• There will be overlaping walkable areas – Jimmy Xu Feb 2 '15 at 19:01
• Thanks for the response, Krom. This is an idea I've been exploring, but my worry is that the inclusion of Y-layers will dramatically decrease performance and increase memory profile. Can you suggest a reference for me to check out that implements this in an efficient manner? – Jimmy Xu Feb 2 '15 at 19:08
• @JimmyXu: We are talking about small rooms, with 32x32 tiles and 8 layers at most, right? Performance and memory hit is going to be minimal. – Kromster Feb 2 '15 at 19:09
• @JimmyXu: There are a multitude of ways to tune the performance of A-star. I have implemented A-star with Landmarks and Triangle-inequality on a 750 hexes x 450 hexes terrain hex grid (so also 3D though not overlapping, with > 325,000 nodes) that calculates paths in less than 100ms on (one CPU of) an Intel i7. The cost of this performance is 3 seconds at start-up on 6 of 8 processors to pre-calculate Landmark distances. Check my profile for a link to an old version of the code. – Pieter Geerkens Feb 3 '15 at 3:20
• You can also prepocess the map to a connectivity graph and use that, you can even do it at runtime on such a small map. – user29244 Feb 4 '15 at 5:10

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)

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.