John Ratcliff told me about a new pathfinding library named “Recast“. It’s open source and it looks pretty good. I am currently using PathEngine in Konoko Payne. That’s a powerful library but it has one big problem for me: navigation meshes have to be created by artists. Since I am the only “artist” in this project, it has always been a huge pain in the butt to open MAX and manually, painfully, create the nav meshes. I more or less did it in KP’s prototype, but never even started for the “real” level (especially since the level is “under construction”. No way I’ll spend time creating a nav mesh for a level which might change the next day).
So the biggest appeal for “Recast”, to me, is that it automatically builds nav meshes. I have no idea about the runtime performance or memory requirements yet, but for me this single feature makes it worth checking.
So, I did.
Pretty simple API, seems to work as advertised. Didn’t test it much yet but seems to work, and it’s fast.
- This picture is what I get on KP’s “Depot” level. That’s what you get out of the box, without much parameter tweaking. Pretty good.
- Only problem I see is that some cables on the ground end up creating big holes in the nav mesh, for some reason. I don’t know why yet. I don’t know if it can be easily solved by tweaking the build parameters a bit more. In any case this is a non-issue, I can simply filter those triangles out of the building process.
- Here are the build parameters I used. You can open this from KP’s console and build everything while the game is running. So far, so good. This is one big step towards releasing KP’s source code. I couldn’t do it before since PathEngine’s license prevented it, but now everything’s possible! (I just have to replace the physics engine, duh!)
(to be continued)
August 19th, 2009 at 10:59 pm
The parameter screenshot reveals that the build parameters are definitely off and that is causing cable problem. The agent params are in voxel sizes (please also note that climb & height should be derived with ch, and radius with cs). I mailed you more complete answer, and I’ll post a cleaned up version of that in my blog soon for others to enjoy too.
The memory usage should be pretty well controlled. There is no runtime allocations with Detour (unless you are using the tile navmesh, which may need to allocate larger temp buffer when you add new tile) and the memory needed by the A* can be controlled quite well too. I would expect that once you get the parameters are right the navmesh size should be one third of what your dialog says, and add hundred K for the rest.
August 20th, 2009 at 3:57 am
The parameters are not all used “as is”, from the UI to the lib. It’s like in the Recast demo, user-friendly versions are exposed in the UI but they’re transformed a bit before being used (exactly as in Recast). Anyway I will revisit this ASAP, probably this afternoon. Thanks for your great email!
August 20th, 2009 at 4:37 am
Just so we’re clear, the “params” structure comes from the UI, then it’s used like this:
const float CellSize = params.mCellSize;
const float CellHeight = params.mCellHeight;
const float WalkableSlopeAngle = params.mWalkableSlope;
const int WalkableHeight = (int)ceilf(params.mWalkableHeight / CellHeight);
const int WalkableClimb = (int)ceilf(params.mWalkableClimb / CellHeight);
const int WalkableRadius = (int)ceilf(params.mWalkableRadius / CellSize);
const int BorderSize = 0;
const int MinRegionSize = (int)rcSqr(50);
const int MergeRegionSize = (int)rcSqr(20);
const float MaxSimpError = 1.3f;
const int MaxEdgeLength = int(12.0f / CellSize);
const int NVP = 6;
September 1st, 2009 at 2:11 am
Looks good (the trend towards open-sourcing I mean). If this becomes a serious indie project, then you/we can probably interact with Wolfire and their Overgrowth thing. I’d definitely support cross-pollination here, because their engine would gain from supporting Oni-like environments.
There is a big effort right now towards completing level import for the original Oni, and this means we have to generate pathfinding information automatically, or allo an artist to provide it. So far we feel like we can do both, depending on the situation, but automatic generation is the biggest challenge, of course. We are a bit limited because on the local scale Oni resolves obstacles with grids, rather coarse (or memory-hungry) and axis-aligned - but apart from that Recast’s approach is relevant to us, and this also means that new levels developed for Oni can end up in Konoko Payne and vice-versa.