Pathfinding for large 3D worlds with complex buildings

[yop123 101]

Hi,

I am thinking about trying to implement a prototype of pathfinding that could work with large 3D worlds (a huge terrain) which contains obstacles (trees) and complexe buildings (with a lot of stairs, ladders, and can have a lot entrance doors (see the picture))

I have found a lot of informations for the plannar case but not when there is an [u]huge terrain[/u] [b]AND[/b] a lot of [u]complexe buildings[/u] (stairs and ladders at different levels)


I already did a A* on the 2D ground (and I can handle terrain obstacles) but I have no idea how to extend the pathfinding to take into account complexe buildings which have complexe connections.
Moreover, because i want to have a huge map, i do not want to store too much precomputed paths/nodes.


-So, how is problem is (well) handled in games ? And you, how do you do (or would you do) ?

-Is there one ultime strategy or do I have to perform two different pathfinding and link the solutions ? (for instance A* + navigation mesh?)

-If it is the case, have you some advises about how to make the link between the different strategies and about the choice of the algorithms ?

-Are there some solutions from robotic which could work in real time with a lot of instances ?

-How do you deals with "action required path" like "use the ladder" or "jump over the hole" or "try to climb the wall" ?


Thanks you all

[IADaveMark 3725]

2 things... remember that pathfinding happens over a graph network -- not over a plane. Therefore, you can have multiple levels of buildings that are physically above each other but are separate graph spaces connected by something (stairs, elevator, etc.). Do NOT confuse the physical space with the graph space.

Second, hierarchical A* is a lifesaver here. When you travel, you don't plan every move on the same level of detail. You think about navigating from building to building, then from floor to floor, then from room to room, and then across the room. So when leaving the house to go to work, you aren't planning to walk around the table in the middle of your office. You aren't even really thinking about moving from the stairs to the lobby, down the hall, and into your office. You are ONLY thinking about getting from your house to the office. Worry about the details later. That cuts down your search space based on the granularity needed. There are a lot of resources on hierarchical A* out there.

[jefferytitan 2523]

You have to remember that A* is a graph based path-finding algorithm. There's nothing limiting it to 2D. That means stairs, climbing, jumping, etc are fine. The key is how to set up that graph. A 2D grid-based approach sets up a different graph for A* than a navmesh does. In general I'd say that navmeshes yield better results, but they're harder to set up. Some navmesh implementations handle stairs fine - they just need to know how high a step you can climb and how steep a slope. They figure the rest out. That's one automatic connectivity criteria - what can you climb? Similarly you could allow climbing over chest-high obstacles, but just set the cost a bit higher so the character prefers to walk up stairs rather than bypass them. Special actions such as jumping... get more difficult. Walking up and down stairs can be done at any speed and is easily reversible. Jumping needs to take all sorts of physics into account. Are you running fast enough to make the jump? What about the height difference between where you are and your destination? Is there a chandelier or rock that you'd hit your head on if you jumped? That will require a lot of thinking on your part.