algorithm
ए * पाथफाइंडिंग एल्गोरिथम

परिचय

A * पाथफाइंडिंग का सरल उदाहरण: बिना किसी बाधा के एक भूलभुलैया

मान लें कि हमारे पास 4 निम्नलिखित 4 ग्रिड हैं:

मान लेते हैं कि यह एक भूलभुलैया है । हालांकि कोई दीवारें / बाधाएं नहीं हैं। हमारे पास केवल एक प्रारंभिक बिंदु (हरा वर्ग), और एक समाप्ति बिंदु (लाल वर्ग) है। यह भी मान लें कि हरे से लाल होने के लिए, हम तिरछे नहीं चल सकते। तो, हरे वर्ग से शुरू करते हुए, आइए देखें कि हम किन वर्गों को स्थानांतरित कर सकते हैं और उन्हें नीले रंग में उजागर कर सकते हैं:

चुनने के लिए कि किस वर्ग को आगे बढ़ना है, हमें 2 उत्तराधिकारियों को ध्यान में रखना होगा:

1. "जी" मान - यह नोड ग्रीन स्क्वायर से कितनी दूर है।
2. "H" मान - यह नोड लाल वर्ग से कितनी दूर है।
3. "एफ" मूल्य - यह "जी" मूल्य और "एच" मूल्य का योग है। यह अंतिम संख्या है जो हमें बताती है कि किस नोड को स्थानांतरित करना है।

इन अनुमानों की गणना करने के लिए, यह वह सूत्र है जिसका हम उपयोग करेंगे: distance = abs(from.x - to.x) + abs(from.y - to.y)

यह "मैनहट्टन दूरी" सूत्र के रूप में जाना जाता है।

चलो हरे वर्ग के बाईं ओर नीले वर्ग के लिए "जी" मान की गणना करें: abs(3 - 2) + abs(2 - 2) = 1

महान! हमें मान मिला है: 1. अब, "h" मान की गणना करने का प्रयास करें: abs(2 - 0) + abs(2 - 0) = 4

उत्तम। अब, "f" मान प्राप्त करें: 1 + 4 = 5

तो, इस नोड का अंतिम मूल्य "5" है।

अन्य सभी नीले वर्गों के लिए भी ऐसा ही करते हैं। प्रत्येक वर्ग के केंद्र में बड़ी संख्या "f" मान है, जबकि शीर्ष बाईं ओर की संख्या "g" मान है, और शीर्ष दाईं ओर की संख्या "h" मान है:

हमने सभी नीले नोड्स के लिए g, h और f मानों की गणना की है। अब हम किसे चुनें?

जिसका भी सबसे कम f मान होता है।

हालांकि, इस मामले में, हमारे पास समान मान के साथ 2 नोड हैं, 5. हम उनके बीच कैसे उठाते हैं?

बस, या तो यादृच्छिक पर एक चुनें, या एक प्राथमिकता निर्धारित करें। मैं आमतौर पर प्राथमिकता पसंद करता हूं जैसे: "राइट> अप> डाउन> लेफ्ट"

5 के f मान वाले नोड्स में से एक हमें "डाउन" दिशा में ले जाता है, और दूसरा हमें "लेफ्ट" में ले जाता है। चूंकि लेफ्ट की तुलना में डाउन उच्च प्राथमिकता पर है, इसलिए हम उस वर्ग को चुनते हैं जो हमें "डाउन" लेता है।

अब मैं उन नोड्स को चिह्नित करता हूं, जिनके लिए हमने अनुमानों की गणना की है, लेकिन नारंगी के रूप में, और उस नोड को स्थानांतरित नहीं किया, जिसे हमने नयन के रूप में चुना था:

ठीक है, अब सियान नोड के चारों ओर के नोड्स के लिए एक ही आकृति विज्ञान की गणना करें:

फिर से, हम सियान नोड से नीचे जाने वाले नोड को चुनते हैं, क्योंकि सभी विकल्पों का समान मान है:

चलो केवल पड़ोसी के लिए अनुमानों की गणना करते हैं कि सियान नोड के पास क्या है:

ठीक है, क्योंकि हम उसी पैटर्न का अनुसरण करेंगे जिसका हम अनुसरण कर रहे हैं:

एक बार और, आइए नोड के पड़ोसी के लिए अनुमानों की गणना करें:

चलो वहाँ चलते हैं:

अंत में, हम देख सकते हैं कि हमारे पास एक विजयी वर्ग है, इसलिए हम वहाँ जाते हैं, और हम कर रहे हैं।