"Finding" a "Path"...Get it? Wait a minute...
Entry posted by Josh ·
4,054 views
So after about three weeks of pain and frustration, I have successfully calculated my first path using Recast navigation. This has been a new experience for me. I've implemented half a dozen low-level C++ libraries, and never had any serious trouble, but Recast Navigation is something else.
The technology underlying Recast is impressive. First they take triangle geometry, convert it to voxels, then calculate navigation, and convert it back into rough polygons. You can read about the process in more detail here:
https://sites.google.com/site/recastnavigation/MikkoMononen_RecastSlides.pdf
The results seem pretty reliable, and although the speed of regenerating a tile is slow, it can be done on a separate thread and doesn't have to be updated all that often. I have two criticisms of the library.
First, the code is a total mess. I can't complain too much since it's a free library, and I definitely appreciate Mikko putting it out there, but integrating it into the engine was a hellish process. I wouldn't even call Recast a code library so much as it is an open-source program. The amount of work it took to figure out what was going on was far beyond any library I have worked with, and it could have been wrapped up into a set of much simpler commands (which is what my end result was).
Second, I believe converting polygons to voxels and back is the technically wrong way to go about this. Constructive solid geometry is perfect for navmeshes, autogenerated or otherwise. It would be very fast to generate. It could be dynamically updated quickly. The results would also be 100% accurate virtually all the time. However, it would require all navigation geometry to be modeled with CSG, and although I would be fine with that, I know others will want to use arbitrary polygonal geometry. So that's one thing I would do different if I were making an engine for just myself. There's an example of why you need to be flexible with your goals sometimes.
Still, it's great to be able to build navigation data for any scene and make a character walk around in it without any waypoints or ray casts. Below is my very first result with Recast. There's some obvious strange results with the path, but the point is that it's working, to some extent. It's a minor miracle I am able to plot any kind of path at all. The hard part is done, and I'm sure I'll get any remaining issues ironed out pretty quickly:
Building AI features right into the engine will give us better integration than using a third-party add-on, or trying to build it on top of the engine. First example, we can use physics geometry instead of visual polygons, and make the engine automatically invalidate and update sections of a map when objects move. This will give you powerful AI features that work perfectly with the rest of the engine, so you can control characters with just a few lines of script code. When this is done, it's reasonable to expect to be able to program something like Left 4 Dead in just a couple hundred lines of script (or less, if you just feel dragging some premade scripts around and attaching them to entities).
Once the pathfinding is all tidied up, it will be a big moment, because it means at that point I will know everything I need to finish Leadwerks3D! When setting out with Leadwerks3D, the things I hadn't done before were what I was most worried about. I attacked the unknown issues first. Now that we are coming to the end of this long research and development phase, all that remains is a lot of hard work. It's all stuff I have done before, so I expect the remaining tasks to go pretty quickly. It's also pretty awesome to have a clear picture of how this massive piece of technology all works...four platforms, with rendering technology stretching from fixed-function graphics all the way to Shader Model 5 hardware tessellation...plus the easiest art pipeline ever and a script and flowgraph system that no one has ever done. The scope of this engine is just so much bigger than anything I have ever done, and it actually works! B)
17 Comments
Recommended Comments