The Quest for Navigation
by Kerry Enfinger · 10/13/2011 (6:21 am) · 10 comments
In my quest to find a general AI navigation path solution, I have tried several implementations of navigation mesh creation with mixed results. While some did work properly for navigation mesh generation, I did not have enough control over the parameters of the mesh creation and the loading times were long. A couple of months ago, I set out to create a navigation mesh add-on that allows extensive customization and is fast in creation and loading.
After trying several different graph creation schemes, I found that using a standard vector array for the nodes and a standard list array for the edges was the quickest method for dynamically creating and modifying the graph. I have finally completed Phase 1 of the project and have successfully implemented a fully customizable navigation mesh. It is blazingly fast compared to all other methods that I have tried and requires very little script additions. For the first time, I am able to auto-generate a navigation mesh that allows characters to walk around and over water (using structures such as bridges). I can also control the angle at which the navigation mesh edges are generated so the AI does not get stuck trying to climb hills that are too steep.
The focus of Phase 2 is to create the AI behavior functions that will allow full use of the navigation mesh including Seek, Flee, Pursue, Evade, and Wander.
I am posting this in hopes of receiving comments and suggestions on needed functionality. I will release this as a paid add-on for T3D. I am also working on making the implementation usable for all version of the Torque Game Engine, including TGE. I have not yet settled on a price point.
Now the eye candy. Please take a look and leave any positive/negative feedback. All comments are welcome.
Fully Customizable
Disallow Specific Game Objects
Extremely Fast
After trying several different graph creation schemes, I found that using a standard vector array for the nodes and a standard list array for the edges was the quickest method for dynamically creating and modifying the graph. I have finally completed Phase 1 of the project and have successfully implemented a fully customizable navigation mesh. It is blazingly fast compared to all other methods that I have tried and requires very little script additions. For the first time, I am able to auto-generate a navigation mesh that allows characters to walk around and over water (using structures such as bridges). I can also control the angle at which the navigation mesh edges are generated so the AI does not get stuck trying to climb hills that are too steep.
The focus of Phase 2 is to create the AI behavior functions that will allow full use of the navigation mesh including Seek, Flee, Pursue, Evade, and Wander.
I am posting this in hopes of receiving comments and suggestions on needed functionality. I will release this as a paid add-on for T3D. I am also working on making the implementation usable for all version of the Torque Game Engine, including TGE. I have not yet settled on a price point.
Now the eye candy. Please take a look and leave any positive/negative feedback. All comments are welcome.
Fully Customizable
Disallow Specific Game Objects
Extremely Fast
About the author
Owner of Altered Reality Software -- Bachelors Degree in Game and Simulation Programming -- Masters Degree in Database Management -- Currently working on Ph.D. in Computer Science
#2
(my own fault, lessons learned on early adopting software based on promises, fool me once i.e T3d wetness shader shame on you, fool me twice i.e Guidebot working navmesh solution shame on me)
i would love to finally see a real functioning nav mesh solution that works well stand alone or with the existing AI kit which i think many are currently utilizing in our own code bases today.
10/13/2011 (12:26 pm)
This pack would be a certain buy for me, in addition to building in your own AI behaviors i would love to see this be able to seemlessly integrate as an option into the univeral AI starter Kit. With that kind of functional flexibility I would be willing to pay over $100 for something like that. I have been looking for a nav mesh solution for some time now and after getting completely robbed on Guidebot which promised on 1.0 release to have a nav mesh system (my own fault, lessons learned on early adopting software based on promises, fool me once i.e T3d wetness shader shame on you, fool me twice i.e Guidebot working navmesh solution shame on me)
i would love to finally see a real functioning nav mesh solution that works well stand alone or with the existing AI kit which i think many are currently utilizing in our own code bases today.
#3
10/13/2011 (12:50 pm)
Looking good! On a technical note though, I don't think this can be called a 'navigation mesh'... it looks like you're generating a high-resolution waypoint grid, whereas a mesh would fill in all those triangles that are walkable. 
#4
@Kerry
Looking good.
Incidentally, what formula are using for navigation? Astar, Dijkstra, etc?
10/13/2011 (1:56 pm)
Oh Danny you hair-splitter ... I think Valve calls this a NodeGraph ... ;)@Kerry
Looking good.
Quote:160K nodes generated in 15 seconds ... yep, I'd say that's fast! :)
Extremely Fast
Incidentally, what formula are using for navigation? Astar, Dijkstra, etc?
#5
Implementing a full polygonal navigation mesh is definitely in the future plans. Complete stabilization and functionality of this method is my first priority before creation of a full-blown navigation mesh.
10/13/2011 (2:02 pm)
You are correct, Daniel. Navigation mesh is the common term used but it is actually a navigation graph. I have included a fast version of path smoothing using a one-ahead lookup method and am experimenting with parsing the entire sparse graph for a much smoother look than I've seen with any other AI pathing solutions. Implementing a full polygonal navigation mesh is definitely in the future plans. Complete stabilization and functionality of this method is my first priority before creation of a full-blown navigation mesh.
#6
I'd definitely be interested in buying the navgraph code.
10/13/2011 (8:00 pm)
A proper pathfinding solution would be a very welcome addition. There are a few resources that tackle this but each are a bit lacking in a variety of ways and none are what I'd call 'production-ready'. I'd definitely be interested in buying the navgraph code.
#7
10/13/2011 (11:12 pm)
It's a good start. Looks like the mesh could use a lot of optimization. It seems to be more dense than should be necessary...but I'm no expert. =D
#8
The density of the graph points is adjustable by using the NodeSpacing parameter.
10/14/2011 (3:44 am)
@JoeThe density of the graph points is adjustable by using the NodeSpacing parameter.
#9
10/14/2011 (12:20 pm)
I'm looking forward to seeing this evolve. We are releasing the zombie pack soon. Maybe there's an opportunity for us to do a bundle deal in the store? Best of luck!
#10
Sounds great. I'm working on adding an obstacle avoidance offset to the waypoints so that there won't be issues with AI collisions during pathing.
10/14/2011 (12:39 pm)
@EricSounds great. I'm working on adding an obstacle avoidance offset to the waypoints so that there won't be issues with AI collisions during pathing.
James Stanley
innovative imaginations