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.

  18. คาสิโน บาคาร่า เว็บพนันออนไลน์ MGWIN88 ให้บริการ คาสิโนออนไลน์ มีเกมให้เลือกเล่นมากมาย สล็อต บาคาร่า รูเล็ต เกมไพ่ ยิงปลา ฝาก ถอน โอนไว ที่สุดในไทย

    คาสิโน คาสิโนออนไลน์ MGWIN88 คัดสรรค์เกมส์คาสิโนออนไลน์บนมือถือ สุดยอดเกมส์ยอดนิยมจากทั่วทุกมุมโลก มารวมไว้ในที่เดียว ที่จะทำให้ลูกค้าทุกท่านได้เพลิดเพลิน สนุกตื่นเต้น เร้าใจ ลุ้นโชค ลุ้นเงินรางวัลก้อนโตที่อาจจะทำให้ทุกท่าน รวย ในเวลาอันรวดเร็ว


  19. Thank you good website That allows us to express opinions Your information is helpful. With our organization very much And can contact us

  20. You can reinstall or install Microsoft Office Setup at

  21. CrownQQ Agen DominoQQ BandarQ dan Domino99 Online Terbesar

    Yuk Buruan ikutan bermain di website CrownQQ
    Sekarang CROWNQQ Memiliki Game terbaru Dan Ternama loh...

    10 permainan :
    => Poker
    => Bandar Poker
    => Domino99
    => BandarQ
    => AduQ
    => Sakong
    => Capsa Susun
    => Bandar 66
    => Perang Baccarat
    => Perang Dadu

    Keunggulan bermain di CrownQQ :
    => Bonus Refferal 20%
    => Bonus Turn Over 0,5%
    => Minimal Depo 20.000
    => Minimal WD 20.000
    => 100% Member Asli
    => Pelayanan DP & WD 24 jam
    => Livechat Kami 24 Jam Online
    => Bisa Dimainkan Di Hp Android
    => Di Layani Dengan 5 Bank Terbaik
    => 1 User ID 10 Permainan Menarik
    => Menyediakan deposit Via Pulsa

    Link Resmi CrownQQ:

    Info Lebih lanjut Kunjungi :
    Website : DominoQQ Online
    Daftar CrownQQ : Poker Online
    Info CrownQQ : Kontakk
    Linktree : Agen Poker Online

    WHATSAPP : +6287771354805
    Line : CS_CROWNQQ
    Facebook : CrownQQ Official
    Kemenangan CrownQQ : Agen BandarQ

  22. You can join us at BETFLIX สล็อตออนไลน์. Register for free. Win bonuses and jackpots every day, easy to play for real money, open 24 hours a day.

  23. Thanks for sharing a great article.
    You are providing wonderful information, it is very useful to us.
    Keep posting like this informative articles.
    Thank you.

    Get to know about 4movierulz

  24. Thanks for sharing a great article.
    You are providing wonderful information, it is very useful to us.
    Keep posting like this informative articles.
    Thank you.

    Get to know about 13377x

  25. Computer networks are the basis of communication in IT. They are used in a huge variety of ways and can include many different types of network. A computer network is a set of computers that are connected together so that they can share information. The earliest examples of computer networks are from the 1960s, but they have come a long way in the half-century since then.

    computer network

  26. Thanks for writing informative content very few bloggers write case study-based content.

    We see that the CRM market has grown rapidly around the world in recent years. CRM software in Australia is the fastest-growing software that helps businesses grow without showing any signs of slowing down.

  27. Thank you very much for ding the impressive work here share with us and, everyone will surely like your each and very blog. There is definitely a great deal to know about this niche information. I like all of the points you've made. assignment help services - Assignment Help in Melbourne - Assignment Help Perth

  28. Assignment help can connect you with professional academic writers by following some simple steps. So, pay a reasonable amount to access assignment writing help services without wasting your time and energy.

  29. 7StarHD, a piracy website having a huge collection of pirated movies, now can be easily downloaded and viewed by netizens without paying for it. It, thus, is coming absolutely free. It, however, is illegal. One can unlawfully make use of 7StarHD to view HD versions of movies produced by Bollywood, Hollywood, Tollywood, and more Indian regional language films by downloading them for free.

  30. Thank you dear admin, I’ve recently been searching for info approximately this niche content for a while and yours is the greatest I’ve found out so far. The reason I ask is because your many blogs posts seems different then most releases and I’m looking for something completely unique. term paper help - Accounting Assignment Help - case study help

  31. Through - how you can connect your mobile phone to Amazon Prime. Through, you can watch your favorite TV shows, series movies. You can watch prime videos anywhere on your device. Users need to create an Amazon account if they don’t have an Amazon account and enter the Amazon my TV activation code to watch Amazon prime videos on your device. |

  32. Also, Due to its smart and unique technology 2021, it remains undetectable for the Microsoft Windows updates and remains to work properly. It works smoothly on laptops as well as desktop pc with its maximum efficiency. It produces all the new unique interface that attracts the users in a great manner. This tool is very small in size but it is easily controlling these gigantic windows 10 in the best way.
    Windows 10 Activator Free Download
    Windows 10 Activator 2021
    Windows 10 Activator

  33. Nagaqq Yang Merupakan Agen Bandarq terbaik , Domino 99, Dan Bandar Poker Online Terpercaya di asia hadir untuk anda semua dengan permainan permainan menarik dan bonus menarik untuk anda semua

    Bonus yang diberikan NagaQQ :
    * Bonus rollingan 0.5%,setiap senin di bagikannya
    * Bonus Refferal 10% + 10%,seumur hidup
    * Bonus Jackpot, yang dapat anda dapatkan dengan mudah
    * Minimal Depo 15.000
    * Minimal WD 20.000
    * Deposit via Pulsa TELKOMSEL

    Memegang Gelar atau title sebagai AGEN POKER ONLINE Terbaik di masanya

    11 Games Yang di Hadirkan NagaQQ :
    * Poker Online
    * BandarQ
    * Domino99
    * Bandar Poker
    * Bandar66
    * Sakong
    * Capsa Susun
    * AduQ
    * Perang Bacarrat
    * Perang Dadu
    * BD QQ (New Game)

    Info Lebih lanjut Kunjungi :
    Website : NAGAQQ
    Facebook : NagaQQ official
    WHATSAPP : +855977509035
    Line : Cs_nagaQQ
    TELEGRAM :+855967014811

    Winner NagaQQ
    Daftar NagaQQ

  34. Webroot Secureanywhere is world’s leading antivirus software which leads to your system’s sensitive data safety from uncountable cyber threats.

  35. Mcafee Activate is a legendary anti-malware package that doubles as a virus scanner. It comes in handy with a secure firewall, a password manager, real-time VPN, auto-update function, and performance optimizer for total protection.

  36. Webroot delivers multi-vector protection for endpoints and networks and threat intelligence services to protect businesses and individuals in a connected world.

  37. is a platform designed for technical issues related to all Kindle devices. Millions of people around the world have joined Kindle that motivates the Amazon Kindle team to serve best to their readersAmazon Kindle team to serve best to their readers is the easiest way to setup Canon printer to your system. A device and internet connection are basic requirements for making connectivity Canon ij printer setup with computer system or phone.

    How to download and install hp drivers from You can download hp assistance to auto update drivers without any hadic

    Go to the Norton Utilities main window and click the how to Install norton install with product key [Antivirus]

    Go to microsoft 365 setup, then log in to your MS account. Next, type in the product key and download the application. Microsoft 365 is the most convenient method to acquire all Office software applications in a single subscription.

  38. is an online platform that is a creation of Fox Corporation and stream the latest content and videos of your interest.
    For More Information Visit Our Site:
    tubi tv
    Roadrunner email login

  39. Thanks for sharing a great article.
    You are providing wonderful information, it is very useful to us.
    Keep posting like this informative articles.
    Thank you.

    Get to know about: types of formwork

  40. webroot setup can be completed with insertion of 20-digit Webroot keycode. Webroot SecureAnywhere is one of the popular and widely accepted antivirus software in homes and offices.

    If you're having trouble logging in to, consider using one of your other Microsoft accounts, such as OneDrive, Xbox Live,, or Skype (if you've already subscribed to these products).

    If your printer is showing offline status and you want to change printer remove offline status for printer then here is a complete guide you have landed upon.

    quickbooks support number For Smooth Working As Accounting & Finance Software that will help to work smoothly.

    If your printer is showing offline status and you want to change printer remove offline status for printer then here is a complete guide you have landed upon.


  42. This is a simplest source to connect printer with devices like windows, Mac or iPhone. You can download printer driver and software of Canon Printer for your device through this link.

    Check how to install brother printing using USB connection on windows 10 computer from , the features are also available !!

    Do you want to know, how to install norton with product key? I am sure you do! Check the link to explore the complete setup guide for norton! print scan  is a official URL which helps you to install & download HP printer drivers for Windows 10. 

    Read this article carefully, if you want to install microsoft 365 on your computer, also check the features and procedure for how to use it.

  43. Nice article I was really impressed seeing this article, it was very interesting and it is very useful for me. You might want to check out 312 battery equivalent lr41 

  44. I found so many exciting matters in this particular content, I would like to request please keep posting such informative content. Check out real credit card numbers to buy stuff

  45. A hard reset will restore your device to factory default settings. You should reconfigure the device from scratch or you can load the configuration file you have backed up before the reset. With the Router powered on, press and hold the WPS/RESET button. For how to factory reset tp link router, release the button and wait for the Router to reboot to its factory default settings.

  46. This is very interesting news, i like this article
    Công ty TNHH Thương Mại Bùi Minh với kinh nghiệm gần 10 năm chuyên cung cấp thiết bị vệ sinh. Bùi Minh luôn đảm bảo mang đến khách hàng những sản phẩm chính hãng, chất lượng cao. Nhận được sự yêu thích và ủng hộ của khách hàng.
    bồn tắm massage
    Top Gạch
    American Standard
    Youtube Bùi Minh

  47. Forza88 merupakan sebuah situs terpercaya yang bisa kalian kunjungi dan mainkan beberapa permainan di forza88. Dari segi keamanan sudah dapat dipastikan kalau forza88 termasuk situs yang aman dan terpercaya. Kenyamanan member merupakan prioritas dari forza88.

    Banyak sekali pilihan permainan pada forza88 yaitu :

    - slot
    - casino
    - games
    - sport

    Banyak sekali macam - macam promo menarik yang disuguhkan oleh forza88 untuk setiap member yang sudah mendaftar di situs kami. Beragam jackpot pun sudah menanti kalian yang telah bersedia mendaftar dan bermain di agen terpercaya Forza88 ini.

  48. Hey, this is an incredible and fabulous post. The Contents of your blog are good and intriguing. Keep posting such contents. Cash Assistance For Single Moms

  49. HBO Max is a premium streaming app with unlimited access to hundreds of hours of entertainment with something for everyone in your family. So sign in HBO Max via your TV and find your next favorite from one of their chosen hubs right away. Click on code to start the service.


  50. Hbomax com/tvsignin lets you stream content on three different devices online, which means you can share it with family and friends. By contrast, Netflix lets you watch on multiple screens if you pay for the Standard (2 screens) or Premium plan (4 screens).HBO Max costs $15/month without ads or $10/month with ads. The service offers everything on HBO's cable channel, plus exclusive shows and additional movies. The ad-free plan also lets you watch new Warner Bros. films on the same day they debut in theaters. tvsignin code
    hbo max tvcode

  51. Garmin express is an application that is used to manage, set up, and register the Garmin devices. It is helpful for users in installing all the software and map updates. Whenever new updates are available, it gives you notifications at the same time. Users can save their desired maps and locations with express and can view the data on the navigation device. So, ensures quick and precise navigation.

  52. That's an outstanding piece of work!I look forward to seeing more!I am very impressed form it.
    unity crackeado

  53. Thank you for writing such a great informative article for today's modern readers. Two thumbs up for great content and interesting views.s
    anti porn crack

  54. You have done great article work. Your website is extremely useful. Kindly keep us informed about your work.
    CorelDraw Graphics Suite Crack

  55. Hi, Thank you so much for taking the time for you to share such a good information. I actually prefer to reading your post. Keep it up!
    Agisoft Photoscan Professional License Key


  56. Hi, I have to say I am impressed. I rarely come across such an informative and interesting blog,
    and let me tell you that you nailed it.cracktrue


  57. Great blog! Do you have any hints for aspiring writers? I’m hoping to start my
    own website soon but I’m a little lost on everything.
    intellij idea crack

  58. This post is a pool of information. The readers are quite impressed after reading this impressive post.
    Babylon Pro NG Crack


  59. I wanna recommend this website to you. Please visit and you will get good information, Thank you for sharing good info.
    Any Video Converter Ultimate Free Downlaod

  60. reaper license key generator Improves multi-factor display based on Windows
    USB modification settings.

  61. Great Article. Looking great work dear, I really appreciated to you on this quality work. I would like say thanks for this post. Here are some useful links for stdudents all across the globe. These tips may help me in the future. A high-standard post with all imperative information.
    isunshare clonego

  62. anymp4 registration code to convert 4K / 1080p HD videos to
    more than 500 formats at 70X faster speed, copy all DVDs / movies to traditional video and audio formats, burn DVD to ISO / Folder
    in 1: 1 ratio, full editing and compression of HD videos


  63. Great set of tips from the master himself. Excellent ideas. Thanks for Awesome tips Keep it up
    itransor-for-whatsapp-Free Download


  64. So nice I am enjoying for that post as for u latest version of this Security tool Available

  65. Wow, amazing block structure! How long
    Have you written a blog before? Working on a blog seems easy.
    The overview of your website is pretty good, not to mention what it does.
    In the content!
    PowerISO 8.1 Crack

  66. I am very impressed with your post because this post is very beneficial for and provides new knowledge to me. Thanks for sharing.
    ProShow Producer 9 Crack

  67. Thanks for sharing your knowledge to install & crack the Time Tables, but you need to update it now. because there is a 2022 version available now.

  68. This site have particular software articles which emits an impression of being a significant and significant for you individual, able software installation.This is the spot you can get helps for any software installation, usage and cracked.

  69. This site have particular software articles which emits an impression of being a significant and significant for you individual, able software installation.This is the spot you can get helps for any software installation, usage and cracked.
    tableau-desktop-professional-edition-full keygen
    officesuite-pro-free download
    drivereasy-pro-full License key

  70. So nice I am enjoying for that post as for u latest version of this Security tool. You can visit this website Click here..

  71. This comment has been removed by the author.