7
\$\begingroup\$

I'm interested in path finding between multiple maps - could be indoor/outdoor maps, different levels in a building etc but the main restraint is that there are one (or more) ingress/egress points between the different maps. I've looked and couldn't find any good solutions, yet I'm aware of several games which use similar systems.

I've found this paper - Hierarchical Shortest Path Finding Applied to Route-Planning for Wheelchair Users which seems to address a similar issue, but it is purely theoretical.

Anyone done similar with some experience they could share, or some tips?

\$\endgroup\$
3
  • \$\begingroup\$ I'm not going to give an answer, since I haven't ever had to implement such a case which makes this statement speculative, but I doubt there is a solution besides the obvious one that you have to load your nodes even of maps which are not loaded yet (which shouldn't be any trouble since waypoint or navigation mesh data is maybe a couple kilobytes even for large maps). Without the nodes, there's no information that your algorithms can use. Other than that, it should be pretty straight forward - load all graphs and connect them on the crossing points (doors etc.). edit: oh and +1 \$\endgroup\$
    – TravisG
    Aug 12, 2011 at 10:45
  • \$\begingroup\$ Agreed on that - I don't think that loading the nodes is the issue - it's more being a bit more intelligent about how the different maps hang together. Like you say, maybe it's a simple case of using a standard algorithm (A*?), loading all the maps in question and then artificially connecting the maps. If there were 2+ multiple levels then maybe I should be using two sets of path finding, as I prob won't need the whole path - only the path out of the current map? \$\endgroup\$
    – Martyn
    Aug 12, 2011 at 10:52
  • \$\begingroup\$ Exactly. It's probably fastest if you represent a "map" (the building or whatever that your A* needs to run into) as one big node until your AI actually stands in front of it, find the shortest path towards that big node, then once you're there load the entire graph of that sub-map and calculate the more precise path. Calculating it all at once in the beginning is wasteful imo, since a lot can happen between that calculation and your AI moving there. \$\endgroup\$
    – TravisG
    Aug 12, 2011 at 11:57

2 Answers 2

5
\$\begingroup\$

I did something similiar several years ago for a mockup demo of cyberpunk-themed "Jagged Alliance" clone which was supposed to have large maps filled with skyscrapers. It was a stupid idea, apparently maps for tactical combat should be tidy and easily understandable :)

In order to have a quicker pathfinding one global map was divided into several discrete square-shaped areas. Once we have a criteria for areas, it's time to find possible "entrances" between each pair of adjacent areas. "Entrance" is a transition point which shows that this agent can enter this area at this point.

In your example with building of several floors, each floor would be an area with borders defined by floor, ceiling and outer walls; and varius holes in wall or floor, or ladders would be entrances, there could be a lot of them. So entrances basically link path nodes from one area to path nodes in the other area.

Once you identified entrances, you'll need to find all possible ways to traverse each area resulting in a "map of area entrances to adjacent area entrances" with edges between entrances showing length of this path through area.

If everything went right, your agent standing on the 1-st floor will be able to find its way to that special box on the 4-th floor quickly. Maybe something similiar could be used in your problem of multiple maps, so hope it helps.

\$\endgroup\$
1
\$\begingroup\$

I believe you are looking for Hierarchical Path-Finding A-star such as described here:

HPA-*

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .