Hey people !
I'm working on an accurate but not necessarily fast pathfinding algorithm for 3D environments, and thought I should ask you experienced lot if you think it could be improved somehow before I get deeper into work with it.
Clarification - The 3D environment consists of 2 types of meshes:
* Terrain - A simple 2D grid of vertices with different height
* Doodad - Any other static 3D object. These have both an enveloping bounding box and any number of custom sized and positioned boxes to represent their collision volume.
Initialization - Upon loading a doodad, a network of edges is established between bordering edges of polygons that face upward (walkable). Edges which have no neighbour or whose neighbour belong to a non-blocking wall polygon are considered "open" and stored in a special list.
Algorithm - We start out with a start and end point in 3D space
Step 1: See if the start point is inside a doodad, if not then this point belongs to the surrounding terrain piece. Repeat for the end point.
Step 2: Starting from the doodad or terrain of the start point, see if there is any connectivity (through open edges for doodads) that can link the start and end points together. Store these objects in a list, and for any doodads store the connecting open edges. If no connectivity was found, break.
Step 3: For each object along the line, use A* pathfinding to find the shortest path between open edges or the points. For terrain pieces, use a custom 2D grid where points inside doodads are avoided. For doodads, use the connectivity between walkable edges and always see if there is any other doodad blocking a potential edge-edge path. If a path is blocked, establish a temporary 2D grid (with higher resolution) on top of the polygon and A* search a path between the two edges through it.
One major thing I am unsure about is in step 3 when a doodad is blocking a polygon, if it's really a smart idea to project this 2D grid on top of it. I could see how one could start out by finding the smallest possible bounding grid for the polygon (from the Y-axis) and then sort away all the points that are not within the triangle. This does sound quite expensive, even when disregarding speed for accuracy...
Sorry for the elaborate explaination, I don't expect everyone to be interrested in this kind of stuff but I've never regretted asking you guys something :)
- Dave
Pathfinding in 3D environment
I would suggest something closer to the following:
Most of this can be computed offline or at least done very rarely, and shouldn't be a performance concern. (Storage might be an issue if you aren't careful, but it should be solvable.) Optimally, using hierarchical A* on a reduced navmesh will give you really fast runtime pathing and the opportunity to do a lot of caching at different levels of the hierarchy. Probably two distinct levels is sufficient.
- Build a navigation mesh for each doodad model, in local object space; this can be done offline in a preprocessing step and cached
- Build a navigation mesh/graph representing your terrain; this can again likely be done statically or at least updated rarely depending on how your terrain works
- When a doodad is placed onto the terrain, find all edges on the terrain navmesh that intersect the bounding box of the doodad (in world space). Transform the doodad navmesh into world space. Depending on the complexity of the doodad navmeshes, you can either replace all edges/nodes inside the bounding volume directly with the transformed doodad navmesh, or you can store a "meta-node" on the terrain navmesh and use hierarchical A* to path through doodads indirectly (may be much faster if doodad density is high and/or doodad navmesh complexity is high)
- Pathfind on the terrain/merged navmesh directly, possibly using a reduction step and doing hierarchical A* if the navmesh size is very large
Most of this can be computed offline or at least done very rarely, and shouldn't be a performance concern. (Storage might be an issue if you aren't careful, but it should be solvable.) Optimally, using hierarchical A* on a reduced navmesh will give you really fast runtime pathing and the opportunity to do a lot of caching at different levels of the hierarchy. Probably two distinct levels is sufficient.
Author
Thank you ApochPiQ for that insightful advice ! It would undeniably be faster to construct the navmesh for doodads in advance, but I anticipate that doodads may sometimes be transformed so that different polygons are walkable. Perhaps a non-transformed mesh could be constructed first, and then for instances in the scene where the dooodad has been rotated on any other axis than Y, then unique meshes are constructed on the fly. So far I have identified walkable polygons by comparing their normal against the up vector (0, 1, 0) and sorting away those where the angular difference is greater than 45 degrees.
Precompute the navmesh for each doodad with all edges traversable; then, when you do the world-space merge of the transformed navmesh into the terrain/global mesh, run the face-angle tests, and only merge in edges that pass the test. That'll allow you to retain full 6-degree-of-freedom movement for the doodads without sacrificing navigation resolution.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement