Jump to content
  • Advertisement
Sign in to follow this  
worldspawn

A* on a multiple tier map question

This topic is 3832 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

While trying to resolve the issue in http://www.gamedev.net/community/forums/topic.asp?topic_id=465874 I have a more complicated one in mind I figured I'd get out of the way now. I have an idea of how to do what I'm planning to do, but want some other opinions since there's probably a much easier/efficient way. Say I have an isometric map with a little maze on it, and a pathfinder in place that lets the NPC navigate it on it's own. Now, let's introduce a second floor. Say I want the little dude to navigate the maze, to the entrance of floor 2, then navigate the maze on that. I made a crude drawing to show what I mean: http://www.innerfilth.com/~mike/example1.jpg I want the blue dot to move somewhere onto the green level. I figured just have him pathfind to the entrance, move up there, then do some more pathfinding. Here's where it gets complicated though: http://www.innerfilth.com/~mike/example2.jpg Say he's starting on one of the green panels and I want him to move to the other one. Say there are multiple exists/entrances for each one. How would I handle this? I was going to have the pathfinder work backwards in this case. Say there's multiple entrances to the second floor, the pathfinder would work backwards from the goal to see which entrances total on the map can lead to it, then find a path from each of these entrances to the player, to see which is best. It gets more complicated if there's 4 floors with like 6 entrances each and they go all over the place. Before I dedicate a lot of time to it is my idea the way to go or is there a better way?

Share this post


Link to post
Share on other sites
Advertisement
A* just navigates a node graph. there's nothing that restricts it to 2D. Think of the floors as separate graphs that are linked to other floors via the stairs. i.e. the stairs connect a node on floor A to another node on floor B. Now A* will happily solve the path for you with zero modifications to your code (assuming you implemented your code nicely, of course [smile])

The only potential trick is finding which floor graph you are currently on. It sounds like you won't have this problem since you're a tile based game; your characters position is exactly equal to a node position. In 3D shooters and whatnot it can be a little more complicated but you can just find the floor to which you are closest.

-me

Share this post


Link to post
Share on other sites
Well I'm gonna do a bit of self-publicity, but you can check this :

http://www.gamedev.net/community/forums/topic.asp?topic_id=469197

It solves the problem of having multiples levels.

and for all the details on how to do it, check : http://www.gamasutra.com/features/20020405/smith_pfv.htm

Share this post


Link to post
Share on other sites
I guess my only problem is figuring out how to calculate the hueristic. Not sure how to do that since each level is it's own array.

Unless that's the problem and I shouldn't do it like that.

Share this post


Link to post
Share on other sites
The children node of a layer-switching node (a staircase) would include the higher layers, so there's no real problem there. Your heuristic would probably still be a normal distance formula, only with the Z direction appropriately scaled. If your Z size between layers is the same size of the X or Y, then this isn't an issue.

Share this post


Link to post
Share on other sites
If you scale the Z by anything more than the height (cost) of the stairs then the heuristic becomes inadmissible.

Here's some more options:

1. Just add in the z distance * cost of traversing the stair tile. The heuristic will be always admissible, but will be very inaccurate if you're nowhere near the stairs. Searches will also be slow, especially if you have to go the 'wrong way' to get to the stairs.

2. Add together two of your existing heuristics - one to get to the stairs, and the other to get back. If there's more than one set of stairs you'll probably want to pick the closest one.

3. Precompute the path to the stairs for each tile. All you need to do for this is store a 'distance from nearest stairs' value in each tile. Of course if the map can change over time the precomputed result won't be perfect, but it should still be better than the other options.

To compute that distance from nearest stairs do a breadth first search from each of the stairs on a level simultaneously, and mark the squares with distances as you go. You'll need two values in each square - one for stairs up, and one for stairs down. Any tiles the dfs didn't get to should be marked as unreachable (searches to unreachable areas will be really really slow unless you precompute that).

This will find the optimal path very quickly if the nearest stairs for both start and end are the same, and will require a bit more searching if they aren't.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!