Pathfinding for large 3D worlds with complex buildings
Members - Reputation: 101
Posted 14 September 2012 - 03:46 PM
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 huge terrain AND a lot of complexe buildings (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
Moderators - Reputation: 2467
Posted 14 September 2012 - 05:20 PM
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.
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play
"Reducing the world to mathematical equations!"
Crossbones+ - Reputation: 2125
Posted 14 September 2012 - 06:09 PM