tag:blogger.com,1999:blog-1272803659321539598.post9081488152848715600..comments2024-03-28T00:38:03.399-07:00Comments on Digesting Duck: Improving Local AvoidanceMikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-1272803659321539598.post-76343550791274317962009-12-09T15:30:50.594-08:002009-12-09T15:30:50.594-08:00Mikko,
I see! Thank you!
There might be some cas...Mikko, <br />I see! Thank you!<br /><br />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.<br /><br />Maybe the ability to set a query mask in detour which evaluates polygon query flags would be a nice item for the roadmap. :-)<br /><br />Thank you!Anonymoushttps://www.blogger.com/profile/08991707994333357360noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-20988708067975712192009-12-09T02:16:53.334-08:002009-12-09T02:16:53.334-08:00Chris, exactly :) Currently the state of the tiles...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.<br /><br />I think the speed depends on the size of your tile and how you store it. The best answer is that you should experiment :)<br /><br />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.<br /><br />If you will have dynamic tile generation, then it should easy to try both.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-35815013626600720612009-12-09T02:10:03.955-08:002009-12-09T02:10:03.955-08:00Re: Streaming Tiles
Ah, now I look at the code it...Re: Streaming Tiles<br /><br />Ah, now I look at the code it seems obvious.<br /><br />I propose storing the tiles in two files.<br /><br />Header/Index file<br /><br />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.<br /><br />Date File<br /><br />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 Paulsonhttps://www.blogger.com/profile/09216942911734497735noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-68473742117209613072009-12-09T01:49:52.685-08:002009-12-09T01:49:52.685-08:00Mirko, ok... so something like having a flag per p...Mirko, ok... so something like having a flag per polygon indicating if that polygon is "seen" would be ok granularity to solve your problem?<br /><br />Detour 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.<br /><br />The area stuff is supposed to solve flagging certain areas, but it is still not finished.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-8842623296948087852009-12-09T01:41:17.768-08:002009-12-09T01:41:17.768-08:00Mikko, ok a hash map for storing the data seems to...Mikko, ok a hash map for storing the data seems to be one feasable way. Thanks.<br /><br />I actually mean "sub-navmesh" for an agent which is the foundation for navigation with detour. Small example:<br /><br />--<br />Environment: Room_A + Room-B + Room_C<br />Lets say they are all three connected via corridors like a triangle with the rooms as vertices.<br /><br />Agent_X starts in/discovers Room_A (so he knows about that room). Then he somehow moves forward until he discovers/enters Room_B.<br /><br />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.<br />--<br /><br />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?<br /><br />MirkoAnonymoushttps://www.blogger.com/profile/08991707994333357360noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-55742929681484138442009-12-08T14:59:51.841-08:002009-12-08T14:59:51.841-08:00Mirko, if you're using recast, then I recommen...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.<br /><br />I'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?<br /><br /><br />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 Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-15232331743169487552009-12-08T14:41:40.425-08:002009-12-08T14:41:40.425-08:00Mikko, I´m not worried about the local behaviour/n...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:<br />1. Keep a complete navmesh of the environment.<br />and<br />2. Have a sub-navmesh for every agent representing his knowlegde about it.<br />or<br />3. Mark the complete navmesh structure with data representing the knowledge of a certain agent instead.<br />and<br />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.<br /><br />Thanks for your attention! :-)Anonymoushttps://www.blogger.com/profile/08991707994333357360noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-85691414951477684362009-12-08T09:47:01.056-08:002009-12-08T09:47:01.056-08:00Looking at the data structure for tiles storing to...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.<br /><br />I can see why you do it in realtime, however I've not opened the can of worms of threading yet.<br /><br />PS<br />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.Chris Paulsonhttps://www.blogger.com/profile/09216942911734497735noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-64607020892718122192009-12-08T06:24:21.197-08:002009-12-08T06:24:21.197-08:002 Chris Paulson
yes, i only rasterize simple shap...2 Chris Paulson <br />yes, 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.<br />AI in my project have done by simple FSM, maybe later i will change it. I will write detailed post in my blog ))Yakovhttps://www.blogger.com/profile/12239884265114495349noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-54400122939695312662009-12-08T05:58:57.577-08:002009-12-08T05:58:57.577-08:00Mirko, there's tons of literature in robotics ...Mirko, there's tons of literature in robotics to handle such situations. How "serious" your solution needs to be?<br /><br />Chris, 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.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-44686800555609946092009-12-08T03:58:34.232-08:002009-12-08T03:58:34.232-08:00Thanks Yakov,
So when an object moves you redo a ...Thanks Yakov,<br /><br />So when an object moves you redo a tile of where it left and where it entered.<br /><br />You rasterize the static verts/tris and then you do the dynamic moved objects. <br />You then do all the other processing calls.<br /><br />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?<br /> <br />To serialise the static tiles to file do I just need to write the dtTiledNavMesh to file?<br /> <br />PS<br /><br />Been following your project and I’m very impressed. What your doing the AI with, FSMs BTs? Sorry if this is off topic.Chris Paulsonhttps://www.blogger.com/profile/09216942911734497735noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-83946871575071010802009-12-07T22:59:44.943-08:002009-12-07T22:59:44.943-08:00Recast is pretty fast :) it's like rap
moreo...Recast is pretty fast :) it's like rap<br /><br />moreover i tried to use rebuilding of tile for bots (local navigation) but failed at that time. Steering behavior looks more corretYakovhttps://www.blogger.com/profile/12239884265114495349noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-39184939983954181162009-12-07T22:42:11.216-08:002009-12-07T22:42:11.216-08:00to Chris Paulson
I slightly changed source to su...to Chris Paulson <br /><br />I 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.<br /><br />unsigned char* Sample_TileMesh::buildTileMesh(const float* bmin, const float* bmax, int& dataSize,<br /><br />// dynamic mesh <br />const float* verts_d, int nverts_d, const int* tris_d, int ntris_d)<br />{<br />....<br /><br /><br />//YAKOV: dynamic meshes<br />// make same thing for dynamic geometry<br />if ( verts_d )<br />{<br />m_tileTriCount += ntris_d;<br /><br />unsigned char* triflags_d = new unsigned char[ntris_d];<br /><br />memset(triflags_d, 0, ntris_d*sizeof(unsigned char));<br /><br />rcMarkWalkableTriangles(m_cfg.walkableSlopeAngle,<br />verts_d, nverts_d, tris_d, ntris_d, triflags_d);<br /><br />rcRasterizeTriangles(verts_d, nverts_d, tris_d, triflags_d, ntris_d, *m_solid);<br /><br />delete [] triflags_d;<br />}Yakovhttps://www.blogger.com/profile/12239884265114495349noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-63067725684860003362009-12-07T15:11:22.564-08:002009-12-07T15:11:22.564-08:00I´m currently working on a simulation where agents...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...<br /><br />Clodé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.Anonymoushttps://www.blogger.com/profile/08991707994333357360noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-63460924172429073472009-12-07T13:39:35.077-08:002009-12-07T13:39:35.077-08:00"Simply using a flag indicating that a blocki..."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..."<br /><br />While 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. <br />blocked: the agent can't go through<br />free : everything i OK<br />partially blocked: the agent need to go and see if it can pass<br /><br />Anyway, nice post as allways !Clodérichttps://www.blogger.com/profile/14317773944696952700noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-6258543448158146802009-12-07T06:59:21.272-08:002009-12-07T06:59:21.272-08:00A link in the navmesh should be disabled only when...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.<br /><br />Your 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.<br /><br />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 :)Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-64814176310014289982009-12-07T06:54:22.106-08:002009-12-07T06:54:22.106-08:00Simply using a flag indicating that a blocking obj...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...<br /><br />Beside dynamic adaption of navmeshes according to movable blockers I´m also interested how to deal with experience based map knowledge. <br /><br />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? <br />Would a simple "copy" (A->B) of certain navmesh areas which are known by the agent be enough? <br />Or should B created on the fly depending on "current B" + "new visible area"?<br /><br />The second case might be also appropriate for "knowledge incapable" agents who only know places they actually see?!<br /><br />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.Anonymoushttps://www.blogger.com/profile/08991707994333357360noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-81985823348738888532009-12-07T03:25:18.586-08:002009-12-07T03:25:18.586-08:00Chris, you can call the rasterization functions (r...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.<br /><br />As 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.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-52868671370861688282009-12-07T02:57:13.147-08:002009-12-07T02:57:13.147-08:00Thanks for the blog, fame at last…
Nice explanatio...Thanks for the blog, fame at last…<br />Nice explanation, but....<br />I'm a bit confused how Yakov's recalc a tile method works.<br /><br />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?<br /><br />Can you pass extra verts when calculating/updating a tile?<br /><br />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 Paulsonhttps://www.blogger.com/profile/09216942911734497735noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-29209236371748270592009-12-07T02:23:30.602-08:002009-12-07T02:23:30.602-08:00Yeah, that is possible too. There are other "...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.<br /><br />Although, I really would use different navmesh for humans and vehicles. I like the Minkowski expanded navmeshes, some like the reusable ones :)Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-45360452358223198032009-12-07T02:19:27.078-08:002009-12-07T02:19:27.078-08:00Instead of removing the area from the navmesh wher...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?<br />That way other characters could walk around it, but a car could just drive right over that (enemy) character (crushing it in the process) ;)<br />Just my 2cts.Sander van Rossenhttps://www.blogger.com/profile/13955123864686957569noreply@blogger.com