Thursday, May 31, 2012

Detour Crowd Path Replanning

Path replanning for Detour Crowd has been a long time pet peeve of mine. I've blogged about the problems surrounding it earlier, but very little code has been submitted. I've been testing some ideas along the way, but never managed to have the few hours of solid coding to get all the pieces together.

Here's what happens in the above video:
  • At start all the agents find a short parts towards the goal. In the video they intentionally get stuck at local minima at start. Generally this improves responsiveness, but sometimes the agents move to wrong direction for a moment.
  • During movement the agents will replan their paths if they notice that the navmesh has changed in front of them. When the agents turn to purple, it means that they are replanning their paths. Similar small search is performend when the replanning occurs, but polygons along the existing path are favored. This makes changes close the agent responsive and changes further away does not make any visual change at all.
  • When the agent approaches the end of the path and the last polygon on the path is not the goal polygon, the agent will periodically replan the path. When a pathway to the goal opens, the agent will use that path.
On top of that there is the path topology optimization going on too. I think the recent changes made that pretty much irrelevant–I think it might be better to just fire a replan every now and then just for the kicks.

I think that summarizes my thinking about path following in general. Once the world is constantly changing, the system ends up replanning the whole time. You cannot replan as much as you would like to since it is hard to determine how long A* will take, so the system becomes this weird scheduler-caching-magic-fudge-latency-hiding-box. There are these dynamic planning algos, like D*, but they all require too much memory.

I hope to get to have the change to put another pass on Detour Crowd replanner to make it much simpler and more robust. Now there is too much state management spaghetti in there.

The changes are available in SVN, please not that I removed the adjust move target function as it was complicating the logic too much. If you are using it, please let me know and I'll try to figure out similar functionality. I also added velocity control for agents (for player characters and such).


  1. Might be worth seeing if the initial short path is obviously blocked (raycastishly) so it won't look *too* stupid.

    Under what conditions do agents reach the end of the path but it's not the goal polygon? I couldn't tell if the agents had found some alternate route around or if they were just gathering under the goal as the nearest place they could find.

    Assuming the latter, and you're not computing incomplete paths, then I assume this will suffer from agents never noticing that a better path opened up somewhere behind/sideways to them? So some kind of hierarchical pathing with incomplete paths and then replanning at the end of the incomplete step might be better (although I guess it's an open question how realistic it is for agents to discover better paths when their current path is valid).

    A crazy idea I thought of while watching the video: for groups of agents with the same destination, you could actually try to do something where each one replans less often, but then if they notice a same-goal-agent going the opposite direction, they replan sooner, although more realistically this would happen not just with opposite direction--movement.


  2. Hi,

    My intuition says that the raycastish metric won't be very good. But on a second though maybe the open node that has best score could be better than just best score. I think heuristics like these will always fail in one way or the other. For example that movement you see in the video would be totally cool for "investigate" behavior but looks stupid if the intent is to reach the goal in a rush.

    If the path finder cannot reach the end polygon, then it will pick the polygon that has highest score. That's the reason the guys find path under the platform. Also, once the agents reach the end of incomplete path, they will replan every few seconds (that's why it looks like christmas under the platform), if new opening is found, they will continue to follow it.

    My idea is to provide callback function in the API so that the caller can decide how many times and how often impartial paths are replanned, and whether it is ok to just stop at the end of an incomplete path. This is where the path following gets really game and behavior specific. There is no correct solution, as sometimes the right answer is to wait 15 minutes.

    I find it always funny that one of the most important actions of path planning and moving is staying still :)

    Group path planning definitely should use one "ghost agent" which does the full path planning and other agents would just do small searches to keep up with the ghost.

  3. Excellent work, Mikko; it's looking really nice! I'll give it a try later.

    I'd just better pipe up and ask whether you removed adjusting move targets just for crowds or for corridors in general. I'm using it for individual agents currently, for a chase behaviour.

  4. Does the localized planning more or less correspond to the agent's field of view? That could help solve the problem that an agent appears to be omniscient about whether a path is blocked in the distance or not.

  5. I am a big fan of regularly scheduled path re-planning. I agree with your comments about it. To me, this sort of approach means accepting that the world is dynamic, and you know it's going to change, so why not continually re-plan. I think re-planning solves a lot of problems with a minimal amount of code. There are certainly other solutions to solving some of these problems, but I tend to like the re-planning model better, for whatever reason.

    When I created SimplePath for Unity, I included a re-plan interval that you can specify, to determine how frequently paths are re-planned (ex: every 0.5 seconds)

    I think it is also useful for correcting certain bugs that occur due to the dynamic nature of the game environment. For example, physics are sometimes battling against the navigation system. If the agent gets pushed off the nav mesh because of physics, he needs to discover that he is out of bounds, and plan his way back in bounds. With frequent re-planning, you don't have to worry about sending specific events for situations like this, because the agent should detect that he is out of bounds during his next planning phase, and plan a proper path back in bounds.

  6. If you are interested, take a look:

    I know SimplePath is not nearly as developed as your software, but i do think that handling dynamic situations was one of its strengths. Of course, that is easier to do when you are on a grid :]

    If you take a look at the yellow paths in the dynamic portion of the video, I think there are a few things of note. You can clearly tell that the agent is replanning, because he is avoiding the obstacles, and because the yellow line will sometimes jitter a little bit, back and forth between two or so squares. Initially I thought that this would have been a problem. But the visual result of the agent looks fine; the line jitters sometimes as a result of this replanning, but the agent does not. I didn't write any sort of special case weighing for preferring some recently cached path over another, it's pretty much just straight forward A*.

  7. I'm porting RecastNavigation to Delphi. Here's the reddit link:

  8. "Excellent Article.
    Enzyme is dedicated to providing exceptional enzyme-focused supplements at the most therapeutic levels available in the natural foods industry and beyond.

    Using cutting-edge formulations, in 1998 Enzymedica introduced Thera-blend™ to the industry. Thera-blend is a proven technology for blending multiple strains of enzymes, shown to be far superior in potency over competing brands.

    From the beginning, we understood how everything begins with digestion. All food is composed of protein, fat, carbohydrates and fiber. The key to turning food into energy is enzymes. Once food is broken down, the body can rebuild and heal, build or create energy and remove toxins and Digestive Enzymes."

  9. E Brochure iBrouchure with numerous exceptional capacity to make your undertaking intriguing. It tells the story and interactive.

  10. Nice!!

    GRS shoes offers Mens shoes in varied designs and colors.

  11. Jadilah jutawan mendadak sekarang juga hanya bermain di sentapoker,com. Hanya deposit 15ribu kamu sudah bisa mendapatkan bonus 10ribu dan berkesempatan memenangkan hadiah ratusan juta hingga milliaran Rupiah! Jangan sampai ketinggalan dengan bonus yang akan datang nantinya hanya di sentapoker,com

    WHATSAPP : +6285921063064
    BBM : SENTA88


  12. selamat pagi bossku , E D E N POKER lagi bonus nihhh
    sebesar 10Ribu lho dan juga kami berikan lagi bonus next depo 5% LHOO setiap melakukan deposit , ayukk buruan jangan sampai ketinggalan..........
    Agen Bandar Poker Terpercaya
    Bandar Poker IDN
    Poker IDN Terbaik
    Agen Judi Uang Asli
    Agen Judi Terbaik Di Indonesia
    Agen Judi Deposit Murah
    Info Poker IDN Terbaik

  13. Your blog has always been a good source for me to get quality tips on blogging. Thanks once again. Try to check this too
    Types of Insectst


    Website paling ternama dan paling terpercaya di Asia ^^
    Sistem pelayanan 24 Jam Non-Stop bersama dengan CS Berpengalaman respon tercepat :)
    Memiliki 9 Jenis game yang sangat digemari oleh seluruh peminat poker / domino

    - Adu Q
    - Bandar Q
    - Bandar Sakong
    - Bandar Poker
    - Poker
    - Domino 99
    - Capsa Susun
    - Bandar66 / Adu Balak
    - Perang Baccarat ( GAME TERBARU )

    Permainan Judi online yang menggunakan uang asli dan mendapatkan uang asli ^^
    * Minimal Deposit : 20.000
    * Minimal Withdraw : 20.000
    * Deposit dan Withdraw 24 jam Non stop ( Kecuali Bank offline / gangguan )
    * Bonus REFFERAL 15 % Seumur hidup tanpa syarat
    * Bonus ROLLINGAN 0.3 % Dibagikan 5 hari 1 kali
    * Proses Deposit & Withdraw PALING CEPAT
    * Sistem keamanan Terbaru & Terjamin
    * Poker Online Terpercaya
    * Live chat yang Responsive
    * Support lebih banyak bank LOKAL Yaitu : Bca, Bri, Bni, Mandiri, Danamon, Cimb niaga , Permata Bank dan Ocbc Nisp
    * Tersedia deposit via pulsa telkomsel dan XL serta OVO juga

    Contact Us

    Website SahabatQQ
    WA 1 : +85515769793
    WA 2 : +855972076840
    FACEBOOK : SahabatQQ Reborn
    TWITTER : SahabatQQ
    YM :
    Kami Siap Melayani anda 24 jam Nonstop

    Daftar SahabatQQ
    #sahabatQQ #winsahabatQQ #winsahabat #rajakartu99 #windaftar

  15. Mobile gaming and development is definitely a huge market which can be used for potential revenue. There are so many success stories for games such as Clash of Clans, Candy Crush, Angry Birds. These games have managed to inspire a million others to take some initiative in the world of iOS and Android game development. About 62% of mobile users install a particular game just a week after they buy their device.

  16. Hi,

    Freelance IT Specialist IT specialists participate in the design, operation and maintenance of IT systems used by companies of all types, as well as by public sector institutions. They take care of everything from hardware and software to networks and web resources. Sometimes, they work with consultants and suppliers to implement new systems and integrate IT processes for customers.

  17. We are tournament management service.You've probably been about your journey to become a wealthy gambler through massive football betting and no job or company is isc888 คาสิโนออนไลน์ easy and doesn't pay off. High and high, many of you may have seen the law in a different country. Instead, in Thailand still unable to make the law, we have to wait.