Chris Paulson asked in the comments of another post how to improve steering based local avoidance. The reply grew quite large, so I thought I'd put it here as another post instead.
All kinds of local steering behaviors have the problem of getting stuck at local minima. That is what Chris is experiencing too, and that is what my recent research is trying to solve.
When splitting the system in reactive (local) and planning (path finding on static graph) navigation, the level of detail where the split happens is important. If the high level plan is too coarse, the local planning is not able to resolve. I think that is what Chris is experiencing.
I have noticed that agents usually do not resolve from local minimas, which are twice as large as their radius. For example two barrels next to each other are still ok to avoid locally, but if they are spaced more widely, so that the agent still cannot move through them, then they may be too big an obstacle. Add another barrel or wall to make it a a but more U-shaped and you get a case which is not easily solvable using reactive local navigation.
Local and Global Navigation
My reasoning has always been that as long as the results would be unpredictable anyways, use local navigation. Moving obstacles are always avoided locally, since at least in game environment we can assume that their movement is unpredictable.
Once they come to rest and touch other objects, they should be included in the planning level navigation graph. The Recast/Detour way is to update a tile once something has changed in it. As an example see Yakov's work.
The reasoning is to try to make it as simple as possible. Modifying the navigation mesh allows the rest of the system to always use the same format of navigation data. Obstacles that change the planning graph does not need to be special cased in the code.
Alternative to rebuilding a whole tile is the just cut holes into it. Cutting holes to polygons is not exactly very easy to get right. That cookie cutter method is limited to only obstruct movement, not allow it. For those reasons (and because Recast is pretty fast ;)), my preferred solution is to build small piece of the navigation mesh every time it is necessary. In contrast to Yakov's work, I probably would not update the mesh as often as he is doing.
Obstacle Graph
If dynamic mesh updates shy you away, or you simply cannot do that. Local navigation can be enhanced to help out to avoid getting stuck at local minima. One way is to add additional representation for it, for example see [1]. Another, maybe simpler idea would be to find islands touching obstacles, calculate their boundary, and steer towards the next "shadow boundary" of the obstacle island.
This proposed method has certain similarities with [2], which Google surfaced for me when I was searching about points of visibility graphs (there were a recent discussion about then at AIGameDev.com).
As an example take a look at the picture at the top of this post. There the orange agent is trying to avoid set of barrels. Most reactive local navigation methods would probably steer the character left into the local minima between the left most barrel and the wall.
To aid this situation, it is possible to calculate a graph of all the obstacles which are touching (check using obstacle radius plus agent radius). Then sort all the links per each obstacle based on their angle.
Using this data it is possible to locate the navigating agent by finding its' spot between two links at the nearest obstacle in the graph. Then you can follow the contour of the obstacle island by always choosing the next adjacent link left or right (that is, in the sorted per obstacle list if links) depending on which direction we want to traverse the object. This traversal will lead us to follow the contour of the obstacle because the links were sorted.
During the traversal, we can find the max steering angle left and right. Steering towards this angle will lead us out of any local minima. It is also possible to calculate the winding of the traversal and check if the agent is inside or outside a set of obstacles. If the traversal code hits a wall should make the steering and in that direction invalid. If both sides are blocked, we know that the link from current navigation node/polygon to the next one is blocked.
One way to resolve from this is to then temporarily disable the link and replan. The temporary disable could last a until certain time has passed, or until any of the objects move in the island have moved. It is really important to get this feedback part right. If you get stuck in local navigation, you should never replan unless you can fix that issue in global graph!
My favorite still is to adjust the navmesh even if it is a bit more complicated to implement.
[1] Automated static and dynamic obstacle avoidance in arbitrary 3D polygonal worlds
[2] Oriented Visibility Graphs: Low-Complexity Planning in Real-Time Environments
Instead of removing the area from the navmesh where a moving character is standing still, wouldn't it be better to keep that area but give it a special flag?
ReplyDeleteThat way other characters could walk around it, but a car could just drive right over that (enemy) character (crushing it in the process) ;)
Just my 2cts.
Yeah, that is possible too. There are other "soft" obstacles too, like fire, or gas coulds or bushes, which the agent should avoid and the agent should also be able to navigate out from those areas but not in.
ReplyDeleteAlthough, I really would use different navmesh for humans and vehicles. I like the Minkowski expanded navmeshes, some like the reusable ones :)
Thanks for the blog, fame at last…
ReplyDeleteNice explanation, but....
I'm a bit confused how Yakov's recalc a tile method works.
When for example a barrel moves into a new tile he calls your stuff to recalc the tile. How does he supply the changed verts/tris? Your stuff requires the initial load of the verts/tris for the initial build. When you supply the verts/tris for the build process of the mesh, which would be all the static part of the map, how do you supply the the verts etc for the dynamic stuff later eg the verts of a barrel?
Can you pass extra verts when calculating/updating a tile?
As an addition to the library (I’m being cheeky here..) it would be nice to have a new function to cut/uncut squares in the mesh and for you to recalc/triangulate the relevant polygons. This way I could just cut squares for the bounding boxes of barrels etc.
Chris, you can call the rasterization functions (rcRasterizeTriangles()) as many times as necessary. I would store all the static geometry in some kind of BVtree (like the chunky trimesh that comes with Recast) so that you cna query only a piece of it when necessary, and then rasterize each dynamic obstacle one by one.
ReplyDeleteAs I mentioned in the post, cutting holes in the mesh is really hard to get right. For that reason, I favor (and support) regenerating a small piece of navmesh when something changes.
Simply using a flag indicating that a blocking object is there might not work in general if the blocker object is smaller then the navmesh polygon. Flagging a "very large" polygon as impassable just because of a small "bunny" on isn´t wanted...
ReplyDeleteBeside dynamic adaption of navmeshes according to movable blockers I´m also interested how to deal with experience based map knowledge.
Does it seem feasible to have a full navmesh (A)of an environment in memory while an agent calculates pathes (detour) on a "mirrowed" subset (B) of that navmesh based on the agents knowledge of the environment?
Would a simple "copy" (A->B) of certain navmesh areas which are known by the agent be enough?
Or should B created on the fly depending on "current B" + "new visible area"?
The second case might be also appropriate for "knowledge incapable" agents who only know places they actually see?!
In general a flag feature for navmesh elements sounds interesting for certain things. E.g. I´m wondering if its feasible to automatically/manually add information to edges defining if they are limited by a wall, hole etc. Obviously these information might be only added manually to a created navmesh set, though.
A link in the navmesh should be disabled only when the obstacle graph is connected on both edges. It means that the whole width of the navigation polygon is obstructed.
ReplyDeleteYour idea sounds a lot like heirarchical path finding. In case of Detour that could be handled so that each tile has small graph describing which portals connect to which neighbour tiles. Then, you could first calculate path across all tiles and then path within the tiles themselves.
I dont think full dynamic discovery based pathfinding is really good for games (that is my context). It usually is not interesting to watch AIs to fail find path. Unless your whole game is based on that :)
"Simply using a flag indicating that a blocking object is there might not work in general if the blocker object is smaller then the navmesh polygon. Flagging a "very large" polygon as impassable just because of a small "bunny" on isn´t wanted..."
ReplyDeleteWhile I completly agrre with you on that, i think some kind of fuzzy approach can do the trick. For each cell your obstacle lies in, you can tag the paths through those cells with the ratio of space occluded by the obtacle. perhaps only three steps are needed: blocked, partially blocked and free.
blocked: the agent can't go through
free : everything i OK
partially blocked: the agent need to go and see if it can pass
Anyway, nice post as allways !
I´m currently working on a simulation where agents need to oberve an unknown building. The observation itself is obviously determined by some local decisions of the agent but I want to be able to simulate some kind of memory as well for known/visible areas. So the agent e.g. still knows the way out of the building, when the decision changes to retreat...
ReplyDeleteClodéric: I don´t understand what benefit the usage of a "partial blocked flag" would have. I thought its just about "marking" an area as impassable in case its completely blocked by something or automatically calculating a way around a partial blocking object. The need for an agent to look if he can pass imho destroys the idea of pathfinding.
to Chris Paulson
ReplyDeleteI slightly changed source to support dynamic meshed. To build tile it needs static mesh and dynamic, static created during loading of level, dynamic mesh prepared during tile rebuilding.
unsigned char* Sample_TileMesh::buildTileMesh(const float* bmin, const float* bmax, int& dataSize,
// dynamic mesh
const float* verts_d, int nverts_d, const int* tris_d, int ntris_d)
{
....
//YAKOV: dynamic meshes
// make same thing for dynamic geometry
if ( verts_d )
{
m_tileTriCount += ntris_d;
unsigned char* triflags_d = new unsigned char[ntris_d];
memset(triflags_d, 0, ntris_d*sizeof(unsigned char));
rcMarkWalkableTriangles(m_cfg.walkableSlopeAngle,
verts_d, nverts_d, tris_d, ntris_d, triflags_d);
rcRasterizeTriangles(verts_d, nverts_d, tris_d, triflags_d, ntris_d, *m_solid);
delete [] triflags_d;
}
Recast is pretty fast :) it's like rap
ReplyDeletemoreover i tried to use rebuilding of tile for bots (local navigation) but failed at that time. Steering behavior looks more corret
Thanks Yakov,
ReplyDeleteSo when an object moves you redo a tile of where it left and where it entered.
You rasterize the static verts/tris and then you do the dynamic moved objects.
You then do all the other processing calls.
So in my previous example of a barrel, do you do the full detail of the barrel or do you do the simple bounding box?
To serialise the static tiles to file do I just need to write the dtTiledNavMesh to file?
PS
Been following your project and I’m very impressed. What your doing the AI with, FSMs BTs? Sorry if this is off topic.
Mirko, there's tons of literature in robotics to handle such situations. How "serious" your solution needs to be?
ReplyDeleteChris, the less geometry you pass to recast the faster it is going to be. For a barrel, I'd probably use cylinder mesh with 6-8 sections.
2 Chris Paulson
ReplyDeleteyes, i only rasterize simple shapes and take it from collision and physics. i didn't do serialization of nav mesh and rebuilding nav mesh during loading (separate thread, 4-7 sec). Also you can generate it with streaming, near tiles first.
AI in my project have done by simple FSM, maybe later i will change it. I will write detailed post in my blog ))
Looking at the data structure for tiles storing to file would not be as simple as it was for the static mesh. Static mesh was in a nice memory chunk, tiles are structures with pointers to other structure, this makes it tricky to stream to file.
ReplyDeleteI can see why you do it in realtime, however I've not opened the can of worms of threading yet.
PS
I've been using (BT) A++ from Alex C with some success. It makes it easy to add new behaviours and increase complexity without having to do lots of rework.
Mikko, I´m not worried about the local behaviour/navigation of the agent. I just want to know if there is a clean way of:
ReplyDelete1. Keep a complete navmesh of the environment.
and
2. Have a sub-navmesh for every agent representing his knowlegde about it.
or
3. Mark the complete navmesh structure with data representing the knowledge of a certain agent instead.
and
4. If there is a clean way to add meta data to the navmesh structure (e.g. data to a certain tile, polygon, edge) which can be queried at runtime.
Thanks for your attention! :-)
Mirko, if you're using recast, then I recommend using some kind of hashmap to store information per polygon, where the key is polygon reference.
ReplyDeleteI'm not sure if I completely understand you submesh problem. One way could be to use the tile mesh, and only allow the agent to use certain tiles. Or restrict the agent to only use certain polygons. How well grained control you need over how the submesh is created?
Chris, the data chunk returned by dtCreateNavMeshData() can be serialized as is, the pointers will be patched when you call addTile(). You need to remember which tile (x,y) it was, though. I want to improve how to more easily store the whole configuration.
Mikko, ok a hash map for storing the data seems to be one feasable way. Thanks.
ReplyDeleteI actually mean "sub-navmesh" for an agent which is the foundation for navigation with detour. Small example:
--
Environment: Room_A + Room-B + Room_C
Lets say they are all three connected via corridors like a triangle with the rooms as vertices.
Agent_X starts in/discovers Room_A (so he knows about that room). Then he somehow moves forward until he discovers/enters Room_B.
Now Agent_X decides that he needs to go to Room_A again which he already knows: I want to use detour to determine the way to Room_A again while ignoring the way through the undiscovered room Room_C.
--
I´m not sure if a tile based mesh fits this need because the actually "known navmesh polygons" depend on the discovery algorithm of the agent and might lead to different shaped fractions of the submesh. One idea is of course to store a list of known polygons in the agent and use this set for detour. Right?
Mirko
Mirko, ok... so something like having a flag per polygon indicating if that polygon is "seen" would be ok granularity to solve your problem?
ReplyDeleteDetour has function to query polygons within certain radius, you could use that. For the time being you need to hack Detour to add the enable flag per tile.
The area stuff is supposed to solve flagging certain areas, but it is still not finished.
Re: Streaming Tiles
ReplyDeleteAh, now I look at the code it seems obvious.
I propose storing the tiles in two files.
Header/Index file
This would contain config info and an entry per tile giving x/y and data size and data location used for indexing into main data file.
Date File
All the data stored sequentially. Using the index file I should be able to retrieve a tile at will. Question is, would this be quicker than recalculating a tile?
Chris, exactly :) Currently the state of the tiles inside the Detour is not very well exposed and not very convenient to store. I will improve this.
ReplyDeleteI think the speed depends on the size of your tile and how you store it. The best answer is that you should experiment :)
My best guess would be that in general it might be faster to load the initial batch of tiles, and then regenerate when something changes. Although Yakov has good experiences doing the initial generation on the fly too.
If you will have dynamic tile generation, then it should easy to try both.
Mikko,
ReplyDeleteI see! Thank you!
There might be some cases where using discrete polygons for discovery might be too coarse (e.g. in case of large polygons in a hall while the agent actually can only see one corner etc.). There it might be necessary to dynamically create the navmesh based on the visual ability and knowledge of the agent.
Maybe the ability to set a query mask in detour which evaluates polygon query flags would be a nice item for the roadmap. :-)
Thank you!