हेक्सागोनल ग्रिड पथ खोज (AS3)

यह आलेख हेक्सापाथ घटक का वर्णन है जो हेक्सागोनल ग्रिड में ए * एल्गोरिथ्म का उपयोग करके पथ खोज को लागू करता है। नेटवर्क में, मैंने एक वर्ग ग्रिड के उदाहरण और कई कार्यान्वयनों का उपयोग करके एल्गोरिदम के विवरणों की एक बड़ी संख्या को पाया, लेकिन एक हेक्सागोनल ग्रिड का एक भी उल्लेख नहीं किया। और मैंने अपना कार्यान्वयन लिखा। स्रोत फैलाओ। अचानक, किसी को इसकी आवश्यकता होगी, लेकिन खुद को लिखना बहुत आलसी होगा।

घटक विवरण

वास्तव में, यह एक वर्ग नहीं है, लेकिन कई हैं:

• NumberPoint.as - प्वाइंट क्लास का एक स्ट्राइप्ड -डाउन एनालॉग
• PathList.as - सूची का कार्यान्वयन (खुला और बंद)। यह क्या है, एल्गोरिथ्म का वर्णन देखें।
• HexaGrid.as - एक हेक्सागोनल ग्रिड के साथ काम करते हैं (सेल निर्देशांक द्वारा पड़ोसियों को ढूंढना, अपने निर्देशांक आदि द्वारा केंद्र निर्देशांक और सेल कोण खोजना)
• HexaPath.as एल्गोरिथम का कार्यान्वयन है।

किसी कारण के लिए, मैंने इस सेल को चुना:



ग्रिड खुद को सामान्य द्वि-आयामी सरणी द्वारा परिभाषित किया गया है, जिसमें कोशिकाओं के मान इस सेल के लिए "संक्रमण की लागत" हैं। यदि संक्रमण लागत HexaGrid.MAX_AVAILABLE की तुलना में अधिक या बराबर है, तो सेल की व्याख्या करने योग्य है।

एक घटक के साथ काम करना मुश्किल नहीं है। पहले आपको भरे हुए "संक्रमण लागत" के साथ दो-आयामी सरणी की आवश्यकता होती है। इस तरह के एक सरणी उदाहरण के लिए बनाया जा सकता है:

HexaGrid.init(width, height);

यह प्रत्येक सेल में 1 के मान के साथ एक सरणी बनाएगा।

कोशिकाओं को "मान" से भरना निम्नानुसार किया जाता है:

HexaGrid.grid[x][y]=value;

हम हेक्सापाथ वर्ग के लिए बनाई गई सरणी को खिलाते हैं

var res:Boolean=HexaPath.setMap(HexaGrid.grid);

फ़ंक्शन सरणी का विश्लेषण करेगा और यदि सब कुछ ठीक है, तो यह सच हो जाएगा।
अब आप पथ का अनुरोध कर सकते हैं:

var result:Object=HexaPath.createPath(source:Point, target:Point);

परिणाम चर की संरचना इस प्रकार है:
result['status']:int;
result['path']:Array;

परिणाम ['स्थिति'] = 1 यदि पथ की सफलतापूर्वक गणना की गई थी, -1 यदि कुछ हुआ।
और यह हो सकता है:

• निर्देशांक प्रारंभ या अंत सरणी से परे जाते हैं
• शुरुआत या अंत के निर्देशांक अगम्य कोशिकाओं में होते हैं।

यदि परिणाम ['स्थिति'] = 1 है , तो चर परिणाम ['पथ'] में पथ कोशिकाओं के निर्देशांक का एक उत्पन्न सरणी है। सरणी के प्रत्येक कक्ष में, ऑब्जेक्ट का एक चर, जिसके लिए सेल निर्देशांक गुण गुण में होते हैं। गंदा? अब मैं कोड पर टिप्पणी करूंगा:

var result:Object=HexaPath.createPath(new Point(0, 0), new Point(5, 5));
var path:Array= result['path'];
var first_cell:Point=path[0]['coords'];
और इसी तरह।

यह अनिवार्य रूप से सभी है। कार्यान्वयन काफी भयावह निकला।
यहां डेमो देखा जा सकता है ।
सूत्र यहाँ से झूलते हैं ।

मुझे आशा है कि कोई मेरे काम को उपयोगी पाएगा ...

युपीडी। ilyaplot ने php में इस एल्गोरिथ्म के कार्यान्वयन को फिर से लिखा। आप इसे यहाँ डाउनलोड कर सकते हैं ।