Pathfinding in a 3D grip
I have made a 3D grid map for bots in a Quake III
with for each link the 3D position and if the bot can go to
this link (if it is not in a wall).
But now I try to find a good pathfinding and I want to know
if a AStar with little modification is a good idea or if an other
algorithm exist for its special case !
Thanks for your help
Pathfinding is merely the connecting of two nodes on a graph of interconnected nodes. If you have your front hall connected to some stairs connected to an upstairs hall, then, despite the fact the rooms are in 3D, you can define the floor planes of the rooms in 2D and pathfind without even a conceptual change in your implementation of A*. This works even if the upstairs hall is directly above the downstairs hall as you only worry about the connectivity (the rooms can be connected by a portal between the two planes that define the rooms).
This seems to fall apart if you are dealing with two areas that are only connected by carrying out a jump on behalf of the bot. The key here is to set up the connectivity by telling the bot explicitly that they can jump between two seemingly disconnected areas either by tagging the areas in some editor or automatically pre-processing the world to see which areas can be connected by a given action (including jumping with anti-grav boots or rocket jumping). By knowing the physcial limitations of the game you can have a section of area A that can be used to traverse to a section of area B under certain circumstances (via one of the actions mentioned previously). Then, when the path has been built, you have, as part of the path, the method the agent needs to take to traverse between each room (walk, jump,rocket jump etc.).
Mike
This seems to fall apart if you are dealing with two areas that are only connected by carrying out a jump on behalf of the bot. The key here is to set up the connectivity by telling the bot explicitly that they can jump between two seemingly disconnected areas either by tagging the areas in some editor or automatically pre-processing the world to see which areas can be connected by a given action (including jumping with anti-grav boots or rocket jumping). By knowing the physcial limitations of the game you can have a section of area A that can be used to traverse to a section of area B under certain circumstances (via one of the actions mentioned previously). Then, when the path has been built, you have, as part of the path, the method the agent needs to take to traverse between each room (walk, jump,rocket jump etc.).
Mike
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement