वीडियोगेम pathfinding के लिए A* algorithm की चतुर तकनीकें
(timmastny.com)- 8-bit top-down Zelda-शैली के गेम में monster tracking लागू करने के लिए केवल सीधी रेखा में movement पर्याप्त नहीं था, इसलिए Dijkstra और A* की तुलना करते हुए game pathfinding के trade-offs खोजे गए
- सीधी रेखा में movement दीवार से रुक जाता है, लेकिन wall-sliding जोड़ने पर character दीवार के साथ-साथ चल सकता है; इससे controls बेहतर महसूस होते हैं और monsters को terrain में फँसाने जैसा strategic element भी बनाया जा सकता है
- Dijkstra algorithm shortest path की गारंटी देता है, लेकिन starting node के आसपास बहुत व्यापक खोज करता है, इसलिए ऐसे गेम में जहाँ destination हर frame बदलता है, जरूरी अगली दिशा से ज्यादा computation कर देता है
- A* destination तक की दूरी के आधार पर search priority तय करता है, पहले destination की दिशा में देखता है, और दीवार मिलने पर आसपास के nodes की जाँच करते हुए पहले देखे गए nodes पर दोबारा नहीं जाता, इसलिए detour path खोज सकता है
- Game maps में पहले से adjacency list न बनाने वाले implicit graph, tile-level search, और iteration depth limit जैसे geometry-based heuristics से speed और implementation difficulty को संतुलित किया जा सकता है
Game context और basic requirements
- PPU466 आधारित 8-bit top-down Zelda-शैली के game में monster को player का पीछा करना था
- PPU466, PICO-8 जैसी fantasy console की तरह 8-bit graphics, प्रति tile 4 colors, fixed background, और कम संख्या में sprites जैसी constraints रखता है
- लक्ष्य था कि monster player का पीछा करे, लेकिन सिर्फ दीवार से रुककर खड़ा न हो जाए या अनचाहे तरीके से फँस न जाए
Straight-line movement और wall-sliding
- सबसे सरल तरीका है monster और player के बीच एक सीधी रेखा खींचकर उसी direction में move करना
- केवल इस तरीके से monster दीवार छूते ही रुक जाता है
- wall-sliding लागू करने पर दीवार से टकराते समय character रुकता नहीं, बल्कि दीवार के साथ-साथ move करता है
- Player movement में यह दीवारों और corners के पास controls को अधिक responsive बनाने की technique है, जो लगभग हर game में इस्तेमाल होती है
- यह Pac-Man के बाद से इस्तेमाल होती रही है, और Pac-Man Championship Edition DX+ player के wall-slide करने पर spark effect जोड़ता है
- Straight-line movement में wall-sliding जोड़ने से monster को किसी खास terrain में फँसाया जा सकता है
- कुछ games इसे strategic element के रूप में इस्तेमाल करते हैं; Runescape का safespotting इसका उदाहरण है
- इस game में यह desired behavior नहीं था, इसलिए वास्तविक pathfinding algorithm पर विचार किया गया
Dijkstra algorithm की सीमाएँ
- Dijkstra algorithm implementation में intuitive है और shortest path की guarantee देता है
- समस्या यह है कि यह जरूरत से बहुत ज्यादा काम करता है
- Starting node से graph के बाकी सभी nodes तक shortest path खोजता है
- Destination node मिलने पर रुक सकता है, लेकिन किसी specific destination direction में search को guide करने का तरीका नहीं है
- Videogame में player लगातार move करता है, इसलिए monster का destination हर frame बदलता है
- Monster को पूरी path से ज्यादा यह जानना जरूरी है कि अभी किस direction में move करना है
- Map के हर pixel या tile के लिए shortest path पहले से compute किया जा सकता है, लेकिन इससे बहुत memory लगती है
- Legacy platforms या resource-constrained platforms पर Dijkstra suitable नहीं है
A* game pathfinding के लिए क्यों सही बैठता है
- A* Search Algorithm starting node से destination तक की distance information का उपयोग करके search priority तय करता है
- पहले step में यह destination तक सीधी दिशा में जाने की कोशिश को priority देता है
- Dijkstra के विपरीत, जरूरत न हो तो opposite direction search में ज्यादा समय नहीं लगाता
- अगर wall path रोकती है, तो यह आसपास के nodes की जाँच करके wall को bypass करने की कोशिश करता है
- Dijkstra की तरह, पहले देखे गए nodes पर दोबारा नहीं जाता, इसलिए ज्यादा backtracking की जरूरत पड़ने पर भी अंततः detour path खोज सकता है
- उदाहरण में A* इस्तेमाल करने वाला monster wall के पीछे फँसता नहीं है
Implicit graph data structure
- Textbook-style graph nodes की list और adjacency matrix या adjacency list से represent होता है, लेकिन games में adjacent nodes को अधिक flexible बनाया जा सकता है
- उदाहरण के लिए, 256×240 pixel screen में हर pixel coordinate को एक node माना जा सकता है
- Adjacent pixels में ऊपर, नीचे, बाएँ, दाएँ, और 4 diagonals सहित 8 directions होते हैं
- Up/down/left/right movement weight 1 है, और diagonal movement weight √2, यानी लगभग 1.4 है
- बहुत बड़ी adjacency list पहले से बनाने के बजाय, केवल वास्तव में visit किए जाने वाले nodes के लिए उन्हें on the fly generate किया जा सकता है
- Wall पर मौजूद या किसी दूसरे sprite द्वारा occupied pixels valid monster positions नहीं हैं, इसलिए उन्हें dynamically adjacency list से बाहर रखा जाता है
- इस तरीके से map editor में non-adjacent nodes को manually exclude करने की जरूरत नहीं पड़ती
Map geometry को reflect करने वाले heuristics
- A* के कुछ elements को map की geometry structure के अनुसार सीधे adjust किया जा सकता है
-
Step size
- Pixels को nodes की तरह इस्तेमाल करने के बजाय, 2D tile-based games में tiles को nodes की तरह इस्तेमाल किया जा सकता है
- Tile-level search player तक path खोजने की iteration count को काफी घटाकर search को तेज बनाती है
- इस case में path exact per-frame movement list नहीं, बल्कि monster को जिन directions की sequence में जाना है, उसके करीब होती है
- Monster आम तौर पर प्रति frame 1 tile की speed से move नहीं करता, इसलिए tile-based path में भी असल में जरूरी जानकारी यह है कि player तक पहुँचने के लिए किस direction में जाना है
- Pixel-based path की nature भी यही है, और monster जरूरी नहीं कि प्रति frame 1 pixel या integer pixel units में move करे
-
Iteration depth
- A* में जब कोई node priority queue से निकलता है, तो वह अब तक देखी गई best path का last step होता है
- Algorithm को fixed iteration count पर रोक देने से destination तक shortest path का अब तक का best estimated path मिल सकता है
- Algorithm को पूरा चलाए बिना भी एक reasonable progress direction मिल सकती है
- Maximum iteration depth को level की geometry के अनुसार adjust करना चाहिए
- Depth बहुत कम हो तो monster फिर भी wall के पीछे फँस सकता है
- उदाहरण में fixed depth 30 tiles पर player position के अनुसार monster फँसकर आगे नहीं बढ़ पाता
- A* हर frame फिर से compute होता है, इसलिए loop बन सकता है
- Wall तक पहुँचने वाले पहले frame में यह calculate करता है कि नीचे जाना चाहिए
- अगले frame में यह calculate करता है कि ऊपर जाना चाहिए
- इस repetition से monster loop में फँस जाता है
- Player monster की search range के अंदर आ जाए तो सही path मिल सकता है
- Fixed depth
1पर यह behavior और ज्यादा extreme हो जाता है, और monster लगातार उस pixel पर लौटता रहता है जहाँ player से Euclidean distance सबसे कम होती है
Precomputation का compromise
- इसे और sophisticated बनाना हो तो map की किसी भी position से A* को path खोजने के लिए जरूरी maximum depth पहले से calculate की जा सकती है
- Dijkstra-style full-path precomputation के विपरीत, store करने की जरूरत केवल उस एक maximum value की होती है
- वह maximum depth मिलने पर A* realtime में valid path खोज सकता है
1 टिप्पणियां
Hacker News टिप्पणियाँ
production MMO में A* के साथ इस्तेमाल किए गए कुछ तरीके: 1) शहर-स्तर, इमारत के अंदर कमरों के बीच, और कमरे के भीतर जैसे hierarchical graphs रखें, तो किसी शहर की किसी इमारत के किसी कमरे के एक point से दूसरे point तक भी मिलीसेकंड के अंश में path खोजा जा सकता है
2) मौजूदा A* search का metadata graph node में ही store करने पर अलग associative array बनाए रखने की जरूरत नहीं पड़ती
3) result path को ज्यों-का-त्यों follow करने के बजाय, जब संभव हो तो अगले path node की ओर corner काटकर जाने वाले steering behavior के input की तरह इस्तेमाल करना बेहतर है. अगर path किसी दूसरे character तक जाता है, तो target character से “breadcrumbs” गिरवाएँ, ताकि जब नई position path के last node से straight-line movement में reachable न हो, तो उसे path में add कर दिया जाए
2b) इसे 16-bit bitmask में compress किया है. 2-bit के 8 chunks, यानी 8 directions, और hash table में store किए गए हैं
2c) हर bit chunk की चार states हैं: FULL_BLOCK(दीवार), HARD_BLOCK(बड़ी object जो किसी भी direction से tile से गुजरने नहीं देती), SOFT_BLOCK(छोटी object जो एक corner से गुजरना रोकती है), NO_BLOCK(खाली tile या बहुत छोटी object वाला tile)
इससे building के अंदर unit को path खोजते समय हर tile पर obstacles check करने की जरूरत नहीं रहती. अगर object बहुत बड़ी नहीं है और rotation direction के हिसाब से entrance और exit corners को block नहीं करती, तो object वाले tile से भी गुजर सकते हैं. अंत में, simulation खराब न हो—जैसे player door लगाना भूल जाए—इसके लिए agents को दीवारों से भी गुजरने दिया जाता है
https://store.steampowered.com/app/2287430/Metropolis_1998/
जब तक character ऐसे “bubble” के अंदर है, world के साथ collision checks पूरी तरह skip किए जा सकते हैं
college में मैं समझ नहीं पाता था कि RTS में A* इतना कठिन क्यों है, लेकिन जब यह explanation देखा कि units को एक-दूसरे के आर-पार जाने से रोकना हो तो हर moving चीज को बाकी सभी units से लगातार बचते हुए path दोबारा ढूँढना पड़ता है, तो Command & Conquer के लिए फिर से respect बढ़ गई
बहुत मजबूत वजह न हो तो मैं personally इससे बचूँगा
Scala में बनाए Quoridor AI को तेज करने के लिए मैंने fast pathfinding पर काफी सोचा, और जो तरीके सीखे वे ये हैं
MPAA (multi-path adaptive A*) उन situations में अच्छा है जहाँ obstacles add होते हैं और same area को कई बार फिर से search करना पड़ता है. पिछले search results डालकर pathfinding तेज की जा सकती है
JPS (Jump Point Search) theoretically आकर्षक है क्योंकि यह consider किए जाने वाले “nodes” की संख्या बहुत घटा सकता है, लेकिन jump points खोजने का overhead बढ़ गया, इसलिए actual speedup नहीं मिला. MPAA और JPS ideas को combine करने का कोई तरीका हो सकता है, लेकिन algorithms के साथ creative tinkering करते समय छोटे-छोटे conceptual details से आसानी से चोट लग जाती है. जैसे, जहाँ
>=चाहिए वहाँ>इस्तेमाल करने पर कुछ situations में सचमुच shortest path guarantee नहीं रह सकतीopen nodes store करते समय proper heap के बजाय, अगर maximum priority value relatively small integer हो तो bucket priority queue पर भी विचार किया जा सकता है. internal array को priority से index किया जाता है, इसलिए insertion और popping काफी fast हो जाते हैं
Quoridor 9x9 grid पर खेला जाता है, और player goal के कितने करीब है तथा goal तक पहुँचना possible है या नहीं, यह तय करने के लिए repeated pathfinding जरूरी है. किसी particular position से possible moves तय करने के लिए check करना होता है कि कोई move goal तक पहुँचना impossible तो नहीं बना देता. इसे कुछ महीनों में release करने की योजना है, और इसमें कम से कम 3 decision-making “engines” होंगे: mtdf (minimax variant), MCTS (कुछ tricks वाली parallel version), और catboost मिलाकर बना hybrid
इसकी अच्छी बात यह है कि इसे usual straight-line distance के बजाय heuristic function के लिए lookup table की तरह इस्तेमाल किया जा सकता है. उदाहरण के लिए, हर turn की शुरुआत में already placed walls को reflect करते हुए Floyd-Warshall algorithm से इस table को initialize किया जा सकता है. ऐसी ही problem में इस technique से A* काफी तेज हुआ था, और यह बहुत simple था. हालांकि वह MPAA या JPS के बिना pure A* था
कई साल पहले मैंने PathFinding.js के JPS implementation में jump nodes खोजने वाली recursive search को visualize करने का feature add किया था. online demo यहाँ है: https://qiao.github.io/PathFinding.js/visual/
अगर दुश्मन एक से ज्यादा हों, तो player के perspective से सिर्फ एक बार Dijkstra चलाना और हर monster से player तक का optimal path lookup करवाना ज्यादा फायदेमंद हो सकता है
monsters की संख्या बदलने पर computation cost ज्यादा predictable हो जाती है
आखिरी animation में depth बहुत कम होने की समस्या एक दिलचस्प behavior जैसी दिखती है। Monster ऐसा लगता है जैसे “तुम किस तरफ जाओगे, यह देखने के लिए इंतज़ार कर रहा हो”
क्या एक तरफ जाने का दिखावा करके फिर दिशा बदलकर उसे बेवकूफ नहीं बनाया जा सकता? अच्छी बात है कि इंसान ऐसी चीज़ों को लेकर काफ़ी उदार होते हैं, और शायद किसी भी चीज़ को intelligence वाली चीज़ की तरह model कर लेते हैं
मूल रूप से enemy को हर frame पर नहीं, बल्कि थोड़ी delay के बाद ही path update करने देना होगा। तब “inertia” की वजह से वह पुराने path का पीछा करेगा, और player उसे छल सकेगा
Game context में A* का एक दिलचस्प उपयोग यह था कि 2000s की शुरुआत के एक game के लिए computer opponent बनाने वाले programmer ने ऐसा किया था
उसने game में AI के पास मौजूद choices को abstract किया, और उस graph में सबसे नज़दीकी distance A* से ढूँढने दिया। यह world pathfinding वाले पारंपरिक उपयोग की तरह नहीं था; computer जो choices कर सकता था, उनके representation पर path खोजना और shortest path को सबसे अच्छी संभव strategy दिखाना—यह बात cool थी
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
कुछ reference material भी है (मेरा नहीं): https://github.com/agoose77/goap-resources
इंसान शायद मानते हैं कि वे खुद और दूसरे इंसान path planning, risk/reward evaluation, 6 महीने बाद के event की planning जैसी बिल्कुल अलग activities में भी मिलते-जुलते thought patterns और लगभग समान depth की सोच लगाते हैं। अगर अलग-अलग “search spaces” को common algorithm के अनुकूल graph में encode किया जा सके, तो gameplay के दौरान immersion की अवस्था में AI के thoughtful और लगभग personality वाला लगने की संभावना बनती है
University में A* सीखते समय, उसी दौरान एक public Minecraft server पर उस अजीब समस्या का सामना हुआ था
Server बहुत ज़्यादा lag कर रहा था, इसलिए trace चलाकर देखा तो पता चला कि zombies एक ऐसे village में घुसने के लिए path खोजने के loop में फँसे थे जिसे बड़े fence से पूरी तरह बंद कर दिया गया था। इसका मतलब था कि उस समय का implementation naive था और कभी give up नहीं करता था
मुझे याद है कि इसे कैसे fix किया जाए, इस पर काफ़ी detail वाला bug report था
खासकर जब कई animals सभी किसी ऐसे entrance से गुजरने की कोशिश कर रहे हों जो passable नहीं है, तो fps पर इसका बहुत साफ़ असर पड़ सकता है। बेशक, बंद दरवाज़े से गुजरने की बेहद ज़िद करने वाली cat behavior के रूप में देखें तो इसे बहुत realistic भी कहा जा सकता है। हालांकि और भी realistic तब होता जब door खोलते ही cat तुरंत अपना मन बदल लेती और गुजरने में interest खो देती!
अनजान terrain में A* इस्तेमाल करने वाले multi-agent systems के paper में आपकी रुचि हो सकती है: https://www.researchgate.net/publication/333917261_Implement...
इस post और HN thread में अच्छे tips हैं। मुझे अभी A* बहुत इस्तेमाल करने का मौका नहीं मिला, लेकिन पता है कि एक अच्छी Haskell library मौजूद है: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...