I managed to make some progress with the temporary obstacle handling. Most of the required pieces are now in place, next up is bunch of massaging to make it great.
So the stuff I have working now is a preprocess step which rasterizes the tiles, creates a minimal representation of the heightfield and then "zips" it. These data chunks are stored in tile cache. Upon request tile cache will create a piece of navmesh for you which includes all the temporary obstacles too.
I use tile size of 48x48 in the video. It takes about 2 ms to update one tile. So in worst case adding one obstacle takes 8 ms. Interestingly the conversion from the minimal representation to compact heightfield takes about 25% of the time, and generating detail mesh takes another 25% of the time.
For those in dire need for the extra nanoseconds, I think I'll provide dummy detail mesh generation process which just triangulates the polygons instead of trying to add more detail. Or maybe even support that at runtime like in the old days.
Apart from the few offenders, each Recast call takes very little time, so it is possible to timeslice the generation.
good video! Do you think that this would be fast/practical enough for HIGHLY dynamic objects? (physic controled object that move and collide for example)
ReplyDeletedo you think further optimisation is possible?
My current thinking is that stuff that moves is handled using local collision avoidance, stuff that is stationary gets baked into the navmesh. Local collision avoidance handles moving objects better, but A* will have decision problems.
ReplyDeleteI think physics objects (i.e. a barrel that move around) should be handle so that while the object is moving, it is avoided by local steering, and when the physics system freezes it, you add it as an obstacle. When it starts to move again, you remove it. It requires annoying state handling, but there is the way to go.
I have experienced this problem in games I have worked on earlier, and also my local grid path finder teest showcases the problem: http://vimeo.com/10404328
That being said, if you have large slowly moving obstacle in your level (i.e. a tank in shooter game), you may add and remove it periodically. Say, every 2 seconds or so.
I think it should be possible to reduce the time to generate one tile to about half the current time. For example shrinking the boundaries takes about 15% of the time. Bulk of it could be done in preprocess, but then the obstacle blockers needs to be expanded by the agent radius. Probably a good compromise.
Also, getting rid of the detail mesh generation should give 25% boost there. When the tile size is rather small like in the demo, the detail mesh is less important.
On top of that some speed optimizations here and there and we're done :)
I wanted to also mention that adding 1 or 20 temp objects have about the same cost. Of course it depends on the size and shape of the obstacle, but adding obstacles this way should scale better than using boolean operations on polys.
ReplyDeleteHi Mikko,
ReplyDeleteGreat progress. Also according to the previous comment, how does that fit into the dynamic obstacle avoidance strategy e.g. for agents avoiding other agents in a crowd?
Are these two avoidance methods distinct for dynamic (agents) and "more or less fixed" aobjects (like a table/chair in a room which might move but usually doesn´t)?
Ah, you are fast. You already answered my question :-)
ReplyDeleteRecast/Detour continue to impress me.
ReplyDeleteYou mention that you will have to rebuild a maximum of four tiles. That is assuming that the object added is not larger enough to hit more than four, correct? What if you're adding something enormous?
ReplyDeleteAlso, it seems like there should be a way to modify the mesh polygons directly using a process similar to the contour simplification algorithm.
namreeb, you need to rebuild all tiles that are affected by the obstacle. Enormous objects cause enormous amount of work.
ReplyDeleteI don't understand that polymesh and contour simplification idea. Can you elaborate? What would you use it for?
My understanding of what you're proposing is to postpone the final stages of the navigation mesh generation. This lets you integrate the new obstacles into the process before the mesh is finalized. This has the advantage of not duplicating any work, but it does have the disadvantage of postponing some work that could be done beforehand (specifically, generating the mesh for the geometry which you already have).
ReplyDeleteWhat I am suggesting is that it seems like there should be a way to complete the mesh generation process without the temporary obstacle(s) and, after processing them in some way, modify the mesh polygons directly. The basic idea here being to allow the user to mesh as much as possible beforehand.
You make it sound so simple ;) if you read my earlier post (linked above), i have explained why i'm not very excited to implement such method. Life is too short to spent fixing floatingpoint accuracy issue.
ReplyDelete