क्यूब सतह

Question

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

मैं इसे ए * का उपयोग करने के लिए प्राप्त करने की कोशिश कर रहा हूं लेकिन मुझे एक अच्छा ह्युरिस्टिक नहीं मिल रहा है। आंदोलन के 4 दिशाओं के साथ एक फ्लैट ग्रिड पर, मैं मैनहट्टन दूरी का उपयोग करूंगा। मैंने 3 डी मैनहट्टन दूरी abs(dx) + abs(dy) + abs(dz) का उपयोग करने की कोशिश की है जो अच्छे कारण के लिए काम नहीं करता है: सांप के लिए, गेम दुनिया वास्तव में 6 grids (corresponding to the faces of the cube) असामान्य लपेट-आसपास गुणों के साथ है।

कोड में, प्रत्येक वर्ग को grid[15][15] 2D सरणी में संग्रहीत किया जाता है। प्रत्येक चेहरे को स्टोर करने के लिए 6 ऐसे सरणी हैं। तो प्रत्येक वर्ग में 212 सरणी में ऑफ़सेट का वर्णन करने के लिए (arrayX, arrayY, d) ट्रिपल है और कौन सी सरणी निर्दिष्ट करें। इसके अलावा, प्रत्येक वर्ग में (x, y, z) ट्रिपल स्थानिक स्थिति का वर्णन करता है।

https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105

यहाँ एक * के लिए पुस्तकालय कोड है::

यहाँ खेल कोड के क्षेत्र है जहां pathfinding होता है

https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60

क्या इस के लिए एक उपयुक्त, संक्षिप्त अनुमानी है गेम की दुनिया?

Answer 1

यह हल करने का एक तरीका है, जैसे ही आप एक खाद्य पदार्थ को पकड़ते हैं, साँप की ओर बढ़ने के बजाय, सांप उस पक्ष की ओर बढ़ता है जिसमें अगली खाद्य वस्तु होती है और फिर, जब वह उस तरफ होती है , खाद्य पदार्थ प्राप्त करने के लिए एक बुनियादी 2 डी ग्रिड ए * एल्गोरिदम का उपयोग करें। दूसरे शब्दों में:

जब भी साँप एक खाद्य पदार्थ या घन का एक नया पक्ष को चाल पकड़ लेता है, निम्न करें:

• तो खाद्य वस्तु वर्तमान घन तरफ है, करने के लिए एक रास्ता खोजने के यह 2 डी मैनहट्टन दूरी हेरिस्टिक
• के साथ ए * एल्गोरिदम का उपयोग कर रहा है यदि खाद्य पदार्थ घन के आसन्न किनारे पर है, तो वर्तमान पक्ष के किनारे घन के किनारे पर एक पथ ढूंढें और उसी पथदर्शी एल्गोरिदम का उपयोग करके लक्ष्य पक्ष ।
• यदि खाद्य वस्तु घन के विपरीत तरफ है, तो उसी पथदर्शी एल्गोरिदम के साथ वर्तमान पक्ष का पथ पाएं।

यह कम से कम समग्र पथ की गारंटी नहीं है, लेकिन आमतौर पर कम से कम पथ के पास होना चाहिए, और यह तेजी से होना चाहिए, क्योंकि यह विभाजन कई चरणों में ऊपर pathfinding और प्रत्येक चरण के लिए एक अधिक कुशल एल्गोरिथ्म का उपयोग करता।