tag:blogger.com,1999:blog-1272803659321539598.post2940837002360095943..comments2024-03-28T00:38:03.399-07:00Comments on Digesting Duck: My Summer of Code 2010Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-1272803659321539598.post-14216135770398989692010-09-10T00:29:29.137-07:002010-09-10T00:29:29.137-07:00I'm not sure if the usual component architectu...I'm not sure if the usual component architecture will lend very well to the whole navigation thing. But you can structure the code quite nicely if you think it as a series of small tasks which have dependencies. If you look at the CrowdManager::update() in RecastDemo, most of the for loops are embarrassingly parallel (well, they need few tweaks to get there), but there are a couple of spots where you need to sync.<br /><br />Squad movement is interesting problem. More so if you wish them to move in formations. If it is ok to just move them as a bunch, I would structure the code so that you find path from one of the NPCs (leader) location to the new goal location and then the other agents find path to the leader, then concatenate the paths.<br /><br />This usually results one long query and many smaller ones. The paths may not be optimal ones, but the obvious kinks will be smoothed out by the runtime path optimization code (currently I use walkability raycast), and the behavior will read as a group [1]. <br /><br />Once you get close to the final destination, you find path to the individual's formation locations. You can potentially do this using findPolysAround() (Dijkstra).<br /><br />Reactive movement is indeed short pathfinds, but very special ones and that can be used to make it really fast. Take a look at my constrained movement post earlier [2].<br /><br />Maintaining elastic structure as a path representation--and updating it as you go--frees you up to create all kinds of styles of movement. Most of the AI programmers out there does not get this yet, though :) The navigation loop as a whole looks like complicated cluster of code, but the problem is not simple either! I have a feeling that I will need to spend quite a bit of time advertising and explaining the method more in detail.<br /><br />In case of formations it is also possible to adjust the path corridor as the goal location moves, which means that you do not need to replan the path if the goal moves.<br />_<br /><br />[1] http://en.wikipedia.org/wiki/Gestalt_psychology - see Prägnanz.<br />[2] http://digestingduck.blogspot.com/2010/07/constrained-movement-along-navmesh-pt-3.htmlMikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-88065899137153562232010-09-07T05:07:24.973-07:002010-09-07T05:07:24.973-07:00I know what you mean. I've been using seperate...I know what you mean. I've been using seperate components for nav following, physics, animation etc. But it feels more and more like they are one big beast rather than seperate concerns. <br /><br />One other thing I've been working on is squad control and I'm still not sure wether the squad should have individual movement or some overall movement and local steering. Seems to me that even the local steering is just a very short path plan. So all your saving is that the paths are shorter. I guess there's also the fact that you dont get too many agents pushing each other around if you use local steering + overall path follow.Phil Carlislehttps://www.blogger.com/profile/05262518177977960604noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-49237181830369422552010-08-31T03:24:13.216-07:002010-08-31T03:24:13.216-07:00Phil, that gut thing is vaguely my current plan. B...Phil, that gut thing is vaguely my current plan. But I feel that I'm entering the very muddy deep end of the who navigation deal :)<br /><br />The physics round trip is very problematic. In common canse (80% of the time) there is no problem with it. But when things go wrong, the code that tries to resolve that always ends up being a huge pile of hacks. Not to mention that syncing physics and the point on navmesh becomes nasty business.<br /><br />The road from 80% to 90% is twice as long as it was to get to that 80%. Getting from 90% to 99%, is equally challenging. End we need to aim for 99.99%.<br /><br />Ideally I would like the navmesh to be the most dominant constraint. It makes the navigation heaps more error proof (something like 80% to 99% thing). In that scenario I envision the physics being used as sensor (something hit me, I better react! or there's a moving box nearby, I might want to steer around) or to adjust the character height for better ground alignment.<br /><br />I'm sure so many people are against that because they have always used the capsule. For characters I don't really see any other good reason but legacy (and early protos) to use physics capsules.<br /><br />Animation is another beast. I have to reread Christians slides. I've yet to dive into the animation problem (and not sure if/when I want to), but even in that case the navmesh should be the final constraint, or you could allow the locomotion location to deviate from the actual navigation location (which may or may not be good idea).<br /><br />When navigation hits the fan, I think it is better to be able to detect and resolve the situation over time than to look good. So better prepare that "ouch, I hurt me toe!" locomotion animation set ;)Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-84002392011810996152010-08-31T02:59:04.238-07:002010-08-31T02:59:04.238-07:00The other part of that is that there's a great...The other part of that is that there's a great deal of interplay between physics and locomotion that concerns me. Right now I use a character controller in physx, which is basically a kinematic moving capsule that doesnt really react to physics. So I feed it a vector and it moves the capsule along the vector and gives me a resulting position (i.e. after collision). In a way, the locomotion system should really do that, so that the interface for the code basically fills in a "desired position" and the rest is handled by the locomotion code, which handles collision, avoidance, animation, etc. I guess thats the model that Christian Gyrling was talking about at GDC 2009. So at the high level you basically have a "character" and then everything below that is opaque to the AI. But at the lower level thats not a great interface because you want to batch operations up.<br /><br />I'd hesitate to say there's really no ideal here, so go with your gut and then we'll whine at you when we find something that doesnt feel right?Phil Carlislehttps://www.blogger.com/profile/05262518177977960604noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-59053069066701037662010-08-30T04:29:00.714-07:002010-08-30T04:29:00.714-07:00I think you're right Mikko, I don't much l...I think you're right Mikko, I don't much like having individual agents doing their own updates, which is what I've currently got. Right now I use physx for the collision check, but its far to slow for larger crowds. Ideally I suppose I'd feed in a list of agent positions and desired velocities and get back a list of updated positions and velocities. Thats I guess the "black box" interface. But the downside is that in order to get locomotion to feel right I really need more information (as I might actually want my agent to look towards the nearest collision, or sidestep etc).<br /><br />I think adding potential fields and such should definitely be possible in the API. But I'm happy to hack that into the API as long as the API is reasonably clear I can figure the rest out.<br /><br />I guess I'm not helping much am I :) but its a really personal thing I think. My main wish is to have ways of querying data outside of just the pathing, preferably during update, so as long as the update loop is reasonably simple to understand, I can live with the rest.Phil Carlislehttps://www.blogger.com/profile/05262518177977960604noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-86506513342500630472010-08-30T02:57:33.109-07:002010-08-30T02:57:33.109-07:00Mirko,
Does the path object also handle steering ...Mirko,<br /><br />Does the path object also handle steering and sending the velocity command to physics, or does it just contain the spatial data?<br /><br />OOP designs does not do well in practice when you have many similar things to update [1]. My plan is to divide the code so that you can call it in nice chunks to (hopefully) benefit from cache and parallelism.<br /><br />Potential maps might work at the steering level. Although, implementing 2.5D potential maps/fields may be a bit of a challenge.<br /><br />One solution for crowd path planning would be to store density per polygon and use that as extra weight during A*, a bit similarly to [2] or [3].<br /><br />Maybe the agent would regenerate path if the density of some polygons ahead along the path has changed a lot.<br /><br />The point of this method is that the agents would avoid crowded areas and fix some of the problems you saw in the current demo earlier.<br /><br />I hope ORCA will allow me to handle more agents in the future (I'm foolishly hoping for 4x more for the same budget).<br /><br /><br />[1] http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf<br />[2] http://gamma.cs.unc.edu/PLE/<br />[3] http://gamma.cs.unc.edu/DenseCrowds/Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-13033905208485530662010-08-30T02:18:32.252-07:002010-08-30T02:18:32.252-07:00Mikko,
In our application we have a manager provi...Mikko,<br /><br />In our application we have a manager providing the API based on the underlying Navmesh. This manager would deal with paging tile in a large world and every agent representation which wants to know its path will call something like "mgr.getPath(start, end)".<br />The manager provides a path object as result of the query which, depending on the implementation is updated internally, when the navmesh changes. Beside that the manager also provides information about accessibility of places, region types (based on your flags) and distance to walls.<br />We use PhysX to actually collide our agent with collision objects. Since Detour does not yet consider blocking objects this is an unsolved issue at the moment (We are glancing at your recent updates ;-) ).<br />Coming from a strong OOP field I suggest using interfaces for the different computation parts providing example implementations and allowing custom implementations if necessary. If these are called a few times per second this should not lead to performance drops at all.<br /><br />For future plans we would like to be able to support large crowds of hundreds of agents therefore we would need to be able to switch between RVO and eg. potential maps. Its not yet clear to me how this should/could fit into the general API.<br /><br />MirkoMirkohttps://www.blogger.com/profile/08991707994333357360noreply@blogger.com