🔒 Locked

Input on pathfinding optimizations for large graphs

Started by Krippy2k Apr 30, 2004 at 2:37 PM 2 replies 650+ views

Original Post

Apr 30, 2004 at 2:37 PM

Hi all, I am currently trying to improve my navigation system, and figure this is a good idea to get some input before I go too far. I am now working with a navigation mesh. I am automatically generating it at load time, and it seems to work fairly well for the parts I have implemented. Here is a screenshot of the Navigation Mesh I know the lines look screwed, the video card in this PC has serious Z-buffer issues. Edges are weighted according to their slope, and those that are too steep to climb are culled. Each node has a maximum of 8 edges. Edges can be one-way, a 2-way edge is comprised of 2 1-way edges. This scene has approximately 90,000 nodes, though a typical scene with detailed interiors may have upwards of 250,000 nodes. The first problem is finding a way to optimize this so that either the path can be generated on the fly, or such that they can be pre-calculated at load time without an exorbitant amount of memory usage. The nodes are laid out in grids that have a consistent x,y distance between nodes, but the z (z being UP) axis is variable. I am thinking that a hierarchical structure that breaks the graph up into reasonable sized regions, precalculates the possible paths within each region, and then at the higher level of the hierarchy, keep a list of best paths between border nodes, and use only the border nodes as the graph nodes at that level. It will still require a lot of memory, but possibly a reasonable amount. Another problem is... compile times are hideously long because I am calculating navigable space by moving a bounding box along each node path, and testing the bounding box against the environment. Therefore at a maxmimum of 8 edges per node, and 5 bounding box tests per edge, that is 8 * 5 * 90000 = 3.6 million box/world tests for the simplest level. I am thinking that at each edge I can rotate the matrix so that the edge is axis aligned, and then extend the box across the entire edge rather than doing a series of tests. That will probably save me a lot of time, but it would still leave me with over 700000 box/world tests, which is still quite a lot.. though it might be workable if I keep the compile entirely offline. I am now using A* to traverse, but I am open to any suggestions for other algorithms that might be more applicable to a hierarchical structure... or more likely, other ways to link regions. Anyway, any ideas or insight into how I can improve the efficiency of this would be most welcome, and warrant copious quantities of free virtual beer on me

In the meantime I know I read some stuff about that in AI Wisdom 2 a while back, so I'm going to go back and stick my nose in that book for a while. Thanks, Krippy [edited by - krippy2k on April 30, 2004 3:37:48 PM]

BrianL

Apr 30, 2004 at 4:51 PM

Unless you have a really good reason not to, definitely do this offline, as you can get higher quality results if you don''t have to worry about memory fragmentation, allocations, and process time.

I would suggest getting away from representing everything as a grid. Focus on minimizing the search space. A hierarchy would be one solution, though have you considered trying to collapse some of those tris with similar normals into a single poly? For instance, your flat rectangular surface could probably be collapsed from about 1200 polies to two triangles, as they all have the same normal.

Why do you need to run an hull over every connection? If the number of objects you could potentially collide with is small, find the polies around them and test them individually instead of walking everything (depending on the sparsity of the collidable objects, this may pay off well).

Krippy2k

May 2, 2004 at 10:13 AM

Hi,

Thanks Brian, and AP. I was originally using a lot of nodes with the idea of using it to help with local steering behaviors. For instance, if I had a region that included the entire flat grassy area behind the building, and I needed to travel between 2 points that were within that region, it wouldn''t be a big deal to recalculate the paths on the fly, taking into account dynamic obstacles and dangers.

However, after thinking about it, it is probably best to have the local steering seperate from the primary navigation... using more autuonomous behavior than just graph traversal.

Minifying the search graph on the terrain is easy enough. Since the nature of the terrain engine is that the only condition that would prevent movement between one node to the next is the slope of the terrain, all I have to do is compare the vertical distance between the nodes vs the horizontal distance. I can see some instances where having a finer granularity could prove beneficial, such as when an agent simply wants to keep out of sight, having more nodes would provide more options... but once again, a more autonomous behavior would probably work better in that regard instead of choking the general pathfinding.

Anyway, thanks for the tips guys, it''s coming along a lot better now.

Peace

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.