2
\$\begingroup\$

I've coded up a little grid based dungeon game. Everything working quite nicely in a Tile[,]. The AI uses basic GOAP for tasks and A* for moving around. Tile reachability is done using a floodfill.

Thinking about what my next step would be, I decided to change the art style from being the typical dungeon to a more sci-fi approach and thought it'd be great to have multiple levels.

This is where I ran into a problem because A* in a 2d grid I understand. But adding extra levels makes it a wee bit harder. My initial thoughts would be to add connections to the next levels in 'stairs' or 'elevator' tiles and adding these to the neighbor list of a Tile for evaluation by A*.

But this throws my heuristic for a loop. I'm using Manhattan distance.

TL;DR: How should I improve my heuristic for multi level path finding?

\$\endgroup\$
0
\$\begingroup\$

If you go for this connections approach your heuristic will be made up of two parts. First you find the closest connection point to the target level and apply classic Manhattan distance from your current location to this stairs/elevator. Next you check the distance on the target level from the connection point to the actual target, again just Manhattan. You should probably add some costs for the elevator/stairs as well. This should give you a pretty valid estimation of the costs.

Another approach would be threedimensional geometry, so you calculate ypur Manhattan distance with also the height difference in mind: H = dh * dh + dw * dw + dl * dl. Then you add some factor for the "up"-cost and your are good to go. This is surely faster than the first approach but also not very exact if you cannnot change levels at any time. It could still be valid if your "up"-cost is high enough, but that depends on the maps.

Depending on how you implemented your algorithm this should work without much change to your actual pathfinding code, but you will have to keep track auf multiple levels and move your agent from one plane to another.

\$\endgroup\$
  • \$\begingroup\$ Hi Domnall, thanks for the response. I feel if i go the neighbor approach and just add them to the list for eval, I might as well just implement Dijkstra. As i'm not entirely sure how to properly implement the up-cost for A*. It feels to me as if Manhattan wouldnt work in this instance. Since simply going up isnt possible as the tile isnt in the neighbor list. though perhaps i can simply link between levels and use some kind of elevator system and give each level an id. \$\endgroup\$ – Kevin Toet Jul 4 '16 at 17:38
  • \$\begingroup\$ From what you say I would go with the connection points between levels. If you want real multi level navigation you can extend the neighborhood so you don't have four/eight neighbors per tile but also the ones above and below. Depending on your implementation that would not be too hard. \$\endgroup\$ – Tristan Kreuziger Jul 4 '16 at 17:55
  • 1
    \$\begingroup\$ Cheers for the brain food, Domnall. I'll let you know how i fare. \$\endgroup\$ – Kevin Toet Jul 4 '16 at 21:08
  • \$\begingroup\$ Not having much luck. Looking at HPA* meanwhile. Could you elaborate on > calculate ypur Manhattan distance with also the height difference in mind: H = dh * dh + dw * dw + dl * dl. Then you add some factor for the "up"-cost \$\endgroup\$ – Kevin Toet Jul 5 '16 at 17:47
  • 1
    \$\begingroup\$ Settled on if A and B are on the same level: manhattan_distance(A, B) else: manhattan_distance(A, lift) + number_of_levels_difference + manhattan_distance(lift, B) \$\endgroup\$ – Kevin Toet Jul 5 '16 at 23:28

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.