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).

56 comments:

  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.

    -stb

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  6. If you are interested, take a look:

    http://www.youtube.com/watch?v=sTb59eKp6qM

    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*.

    ReplyDelete
  7. I'm porting RecastNavigation to Delphi. Here's the reddit link: http://www.reddit.com/r/gamedev/comments/2ngpmx/porting_recastnavigation_to_delphi/

    ReplyDelete
  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."

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

    ReplyDelete
  10. Nice!!

    GRS shoes offers Mens shoes in varied designs and colors.

    http://www.grsshoes.com/

    ReplyDelete
  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
    LIVE CHAT : SENTAPOKER,COM

    AGEN POKER DAN DOMINO TERPERCAYA
    AGEN JUDI ONLINE BERKUALITAS
    AGEN POKER SANGAT AMAN TERPERCAYA
    AGEN IDN PALING DIMINATI
    BANDAR CEME TERPERCAYA TERBAIK
    SENTA POKER
    AGEN DOMINO TERAMAN DAN TERPERCAYA
    BANDAR CAPSA YANG PALING AMAN
    AGEN JUDI ONLINE PALING RAMAI
    AGEN JUDI TERLARIS DAN DIMINATI

    ReplyDelete
  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..........
    www(.)edenpoker(.)co
    GUDANG PROMO IDN POKER
    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

    ReplyDelete
  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

    ReplyDelete
  14. PERMAINAN ONLINE TERBESAR DI INDONESIA

    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
    LINE : SAHABATQQ
    FACEBOOK : SahabatQQ Reborn
    TWITTER : SahabatQQ
    YM : cs2_sahabatqq@yahoo.com
    Kami Siap Melayani anda 24 jam Nonstop

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

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  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.

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

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

    ReplyDelete

  19. Thank you good website That allows us to express opinions Your information is helpful. With our organization very much And can contact us
    ดูหนังออนไลน์

    ReplyDelete
  20. You can reinstall or install Microsoft Office Setup at office.com/setup

    ReplyDelete
  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:
    - maincrownqq.com
    - maincrownqq.net
    - maincrownqq.org

    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

    ReplyDelete
  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.

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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.

    ReplyDelete
  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

    ReplyDelete
  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.

    ReplyDelete
  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.
    7Starhd

    ReplyDelete
  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

    ReplyDelete
  31. Through www.amazon.com/mytv - how you can connect your mobile phone to Amazon Prime. Through amazon.com/mytv, 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.

    amazon.com/mytv | www.amazon.com/mytv

    ReplyDelete
  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 ACTIVATOR
    Windows 10 Activator 2021
    Windows 10 Activator

    ReplyDelete
  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
    * 6 JENIS BANK ( BCA , BNI, BRI , MANDIRI , CIMB , DANAMON )

    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

    BACA JUGA BLOGSPORT KAMI YANG LAIN:
    Winner NagaQQ
    Daftar NagaQQ
    nagaqq

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

    ReplyDelete
  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.

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

    ReplyDelete
  37. www.kindle.com/support 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

    ij.start.canon/setup 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 123.hp.com/setup? 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.




    ReplyDelete
  38. tubi.tv/activate 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

    ReplyDelete
  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

    ReplyDelete
  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 http://microsoft365.com/setup, consider using one of your other Microsoft accounts, such as OneDrive, Xbox Live, Outlook.com, 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.

    ReplyDelete