Path following amongst dynamic objects is a tricky topic. Gladly there are tons of good papers about it and it seems to be lively topic in the academia and actually one of those which produce good papers with realistic test cases too.
Over the past year, I have experimented with velocity obstacles. I tried several different sampling schemes, but I never quite got my implementation robust or fast enough. There's a recent paper which solves all the problems I had with the approach so far. The paper is titled:
ClearPath: Highly Parallel Collision Avoidance for Multi-Agent Simulation
http://gamma.cs.unc.edu/CA/
It is simple to implement and seems fast enough. I implemented the FVO union and new velocity selection mechanism and I like the results so far as you can see from the image above. I still need to add handling for static obstacles and then I'm ready to move on to actually create path follow example for Detour.
yesterday i implemented path finding with dynamic objects based on Recast. It is based on TileMesh, renders dynamic object into tile, when object move. First simple implementation is with rasterization both static and dynamic meshes. It's fast enough now, especially if reduce tile size and execute it 2 times per second.
ReplyDeleteThat sounds great!
ReplyDeleteWhat kind of tile sizes are you using? I think the runtime tile generation should be feasible with tile sizes from 32 to 64. Anything below 32 requires way too much over rasterization (32 usually means rasterizing 40x40 tile because of the padding, which means 50% of the rasterization is "wasted").
Are you generating the tiles in separate thread or have you time-sliced the process?
I started from tile size 32, now changed to 16, updating 2 times per second in separate thread. I selected tile size 16 to have more accurate nav mesh height, but looks like it's not enough.
ReplyDeletei dont understand ... padding?. as I understand, you clip triangles during rasterization process, how can be rasterization wasted?
I select tiles which needs update, based on bbox of moved object.
now I think, how to backup voxels of static mesh, and render only dynamic meshes.
The part of the process that adds the agent radius into the mesh needs some padding to work correctly with tiles. The padding prevents the process to shrink the tile boundaries. Maybe this picture explains it a bit better.
ReplyDeletehttp://www.edu.lahti.fi/~memon/stash/padding_explained.png
When you say more accurate height, you mean that the polygonal representation does not match the underlying geometry?
When you update a 16x16 tile how long does it take? How many triangles you pass to Recast? Looking at your screenshots there should not be that many triangles to process per tile.
It is possible to render all the static geometry to a rcHeightfield, make a duplicate and then render all the dynamic ones. That takes quite a lot of memory, though. What does the performance numbers says? Are you rasterization bound?
--When you say more accurate height, you mean --that the polygonal representation does not ---match the underlying geometry?
ReplyDeleteyes, here is i need to trace the landscape. but for another geometry, nav mesh can be used.
--When you update a 16x16 tile how long does --it take? How many triangles you pass to
--Recast?
it takes 4-5 seconds, the landscape is from 10 000 triangles, size 300x300. plus 20-30 static boxes from physics. I decided to use 32 or 64 tile size , because in case of 16x16 there are only 4-6 triangles per tile there.
-- Looking at your screenshots there should
--not be that many triangles to process per
--tile.
here is my landscape mesh http://www.haemoglobin-game.com/shareware_output.obj
--It is possible to render all the static
--geometry to a rcHeightfield, make a
--duplicate and then render all the dynamic
--ones. That takes quite a lot of memory,
--though. What does the performance numbers
--says? Are you rasterization bound?
in case of Recast Demo, it costs 50 mb with my landscape and keeping all intermediate results. if use simplified geometry, i think the numbers will be same.
I will upload video with bots and resolving dynamic paths to aiGameDev.com this week. Also I hope, I will finish complete game demo before 10 augoust.
ReplyDeletegoogle 1102
ReplyDeletegoogle 1103
google 1104
google 1105
google 1106