जावा 2 डी गेम में पथ खोजना?

Question

अनिवार्य रूप से यह एक पॅकमैन क्लोन गेम है जिस पर मैं काम कर रहा हूं। मेरे पास एक दुश्मन वर्ग है, और इस वर्ग के 4 उदाहरण बनाए गए हैं जो सभी खेल के 4 भूत का प्रतिनिधित्व करते हैं।

सभी भूत स्क्रीन के यादृच्छिक क्षेत्रों में शुरू होते हैं और फिर उन्हें पॅकमैन चरित्र की ओर अपना रास्ता काम करना पड़ता है। चूंकि खिलाड़ी पॅकमैन को नियंत्रित करता है, इसे चारों ओर ले जाता है, उन्हें इसका पालन करना चाहिए और उसके प्रति निकटतम संभव तरीका लेना चाहिए।

कोई भूलभुलैया/बाधा नहीं है (अभी तक) इसलिए पूरा नक्शा (400x400 पिक्सेल) उनके लिए खुली जमीन है।

खिलाड़ी और प्रत्येक भूत के लिए, मैं एक्स, वाई, छवि चौड़ाई और ऊंचाई विशेषताओं को पुनर्प्राप्त कर सकता हूं। इसके अलावा, मेरे पास पहले से ही टकराव का पता लगाने वाला एल्गोरिदम है, इसलिए इसके बारे में चिंतित नहीं है, बस भूत के बारे में सोचने वाले भूत के बारे में चिंतित हैं।

Answer 1

A* का उपयोग करके, एक अच्छा पथदर्शी एल्गोरिदम के लिए, शायद एक अच्छा विचार होगा, जहां एक परिष्कृत, कुशल, और प्रभावी पथ खोज की आवश्यकता नहीं होती है, केवल वर्णों को ढूंढकर लक्ष्य की ओर बढ़ते हैं लक्ष्य की दिशा पर्याप्त होनी चाहिए।

उदाहरण के लिए, स्यूडोकोड में, चरित्र चाल बनाने के लिए निर्णय:

if (target is to the left of me): 
    move(left); 
else 
    move(right); 

if (target is above me): 
    move(up); 
else 
    move(down); 

हाँ, चरित्र सबसे कुशल आंदोलन बनाने के लिए नहीं जा रहा है, लेकिन यह करीब है और पर लक्ष्य के करीब मिल जाएगा गेम लूप का प्रत्येक पुनरावृत्ति।

यह भी मेरा अनुमान है कि 80 के दशक से एक आर्केड गेम शायद परिष्कृत पथदर्शी एल्गोरिदम का उपयोग नहीं करेगा।

Answer 2

आप looking at A* (A star)

और here is a page कि अन्य मार्ग खोजने एल्गोरिदम के लिंक हों शुरू कर सकता है।

[संपादित करें] ... मस्तिष्क बहुत धीमा है ... इस पुस्तक के बारे में भूल गया है, यह सी या सी ++ (मैं भूल जाता हूं) है, लेकिन आप अभी भी जावा के लिए अवधारणाएं प्राप्त कर सकते हैं। आपके पढ़ने के लिए यह सबसे आसान नहीं हो सकता है, लेकिन कुल मिलाकर खराब नहीं है। AI for Game Developers by David M. Bourg, Glenn Seemann।

Answer 3

यदि आपके पास सिर्फ पिक्सल का ग्रिड है - एक "बड़ा क्षेत्र" जिस पर पॅकमैन और भूत स्वतंत्र रूप से स्थानांतरित हो सकते हैं - तो सबसे छोटा रास्ता आसान है - भूत और पॅकमैन के बीच एक सीधी रेखा।

लेकिन "सबसे छोटा रास्ता" हमेशा का अर्थ है कि हम ग्राफ-सिद्धांत समस्या को हल करने का प्रयास कर रहे हैं। (मैं ग्राफ का ज्ञान मान रहा हूं, कुछ ग्राफ सिद्धांत, adj। Matrices, आदि!)

उपर्युक्त मामले में, प्रत्येक पिक्सेल को ग्राफ़ पर नोड होने पर विचार करें। प्रत्येक नोड अपने पड़ोसियों से किनारे से जुड़ा होता है, और प्रत्येक किनारे के बराबर "वजन" होता है ("उपरोक्त" पर नोड पर जाने से "नीचे" नोड पर जाने से धीमा नहीं होता है)।

तो आप इस है: ("*" = नोड "-, /, \, |" = धार)

*-*-* 
|\|/| 
*-*-* ... (etc) 
|/|\| 
*-*-* 

हैं Pacman केंद्र में है, यह किसी भी अन्य नोड के लिए स्थानांतरित कर सकते हैं बहुत आसानी से।

कुछ अधिक वास्तविकता के करीब यह हो सकता है:

*-*-* 
| | | 
*-*-* ... (etc) 
| | | 
*-*-* 

अब, pacman तिरछे स्थानांतरित नहीं कर सकते।केंद्र से नीचे-दाएं जाने के लिए एक के बजाय 2 "होप्स" की आवश्यकता होती है।

प्रगति जारी रखने के लिए:

*-*-*-* 
| | | | 
| | | | 
| | | | 
*-*-*-* 
| | | | 
*-*-*-* 

अब, शीर्ष पर एक नोड के लिए बीच में एक नोड से जाने के लिए, आप 3 हॉप्स की जरूरत है। हालांकि, नीचे की ओर बढ़ने के लिए केवल 1 हॉप लेता है।

ग्राफ में किसी भी गेम-बोर्ड सेटअप का अनुवाद करना आसान होगा। प्रत्येक "छेड़छाड़" एक नोड है। दो चौराहे के बीच का रास्ता एक किनारा है, और उस पथ की लंबाई उस किनारे का भार है।

ए * दर्ज करें। ग्राफ बनाने के द्वारा (एक आसन्न मैट्रिक्स या नोड्स की सूची का उपयोग करें), आप सबसे कम पथ खोजने के लिए ए * एल्गोरिदम का उपयोग कर सकते हैं। अन्य एल्गोरिदम में डिजस्ट्रा शामिल हैं। और बहुत सारे! लेकिन सबसे पहले आपको ग्राफ के संदर्भ में अपनी समस्या को फ्रेम करने की आवश्यकता है, और उसके बाद खिलौना नोड ए (पॅकमैन) से नोड बी (भूत) तक कैसे जाएंगे।

आशा है कि मदद करता है!

Answer 4

मुझे लगता है कि पॅकमैन द्वारा किए गए हर कदम पर सबसे कम पथ एल्गोरिदम के लिए जाना है। एक बहुत अच्छा कार्यान्वयन Dijkstra's algorithm है।

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

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

Answer 5

यह बहुत लंबा समय रहा है, लेकिन स्मृति से पीएसी-मैन में भूत ने पथदर्शी के रास्ते में बहुत कुछ नहीं किया। वे एक मानक मानक यादृच्छिक भूलभुलैया ट्रैवर्सल करेंगे जब तक कि वे आपको "देखे" न हों, जिसमें आपके प्रति गलियारे की धुरी के साथ एक अनियंत्रित पथ ढूंढना शामिल था, और तब तक वे सीधे आपकी तरफ बढ़ जाएंगे जब तक कि आप उनकी दृष्टि से गायब नहीं हो जाते, जहां वे एक यादृच्छिक पैटर्न फिर से शुरू होगा। उच्च स्तर पर पीएसी-मैन थोड़ी देर के लिए अदृश्य ट्रेल्स छोड़ देगा कि भूत "गंध" करेंगे और कभी-कभी इसका पालन करेंगे।

जब पीएसी-मैन को शक्ति मिल गई, तो एल्गोरिदम में एकमात्र अंतर यह है कि, जब उन्होंने आपको देखा, तो भूत आप की ओर बढ़ने के बजाए भाग जाएंगे।

तो, एक प्रामाणिक अनुभव के लिए, आपको शायद एक बहुत ही परिष्कृत पथदर्शी एल्गोरिदम की आवश्यकता नहीं है। यदि आप कल्पना करना चाहते हैं, तो निश्चित रूप से, आप ए * को कार्यान्वित कर सकते हैं।

Answer 6

सीधे अपने दुश्मनों की तरफ चलना एक शुरुआत है, लेकिन जब आप भूलभुलैया जोड़ते हैं तो आप थोड़ी अधिक समझदार पथदर्शी जोड़ना चाहेंगे ताकि आपके भूत झुकाव या मृत सिरों में फंस न जाए।

निम्नलिखित ट्यूटोरियल डाउनलोड करने योग्य उदाहरणों के साथ ए * के साथ शुरू करने के लिए एक महान हल्के गाइड है।> पीछा -

Path Finding on Tile based Maps

Answer 7

Pacman में भूत के सभी एक अलग पीछा एल्गोरिथ्म

• ब्लिंकी था। आमतौर पर आप के लिए सबसे छोटा रास्ता ले जाएगा, और पालन करने के लिए जाता है।
• पिंकी -> Ambushes। पीएसी-मैन के लिए एक और चौराहे रास्ता लेता है। घातक। (पिंकी और ब्लिंकी एक दिशा चुनते समय अलग-अलग पसंद करते हैं, अक्सर एक कोने में खिलाड़ी को caging)
• Inky -> Freak। यह दोस्त अजीब तरीके से काम करता है। वह बोर्ड के बारे में काफी यादृच्छिक रूप से चलता है, लेकिन कभी-कभी जब वह करीब आता है तो उसका पीछा करता है।
• क्लाइड -> इडियट। यादृच्छिक रूप से चलता है। बहुत अधिक खतरा नहीं।

भूत एक दिलचस्प पैटर्न उनकी गतिविधियों में प्रोग्राम है: कभी कभी, वे एक साथ संघर्ष और पीएसी मैन की उनकी खोज विरत और, भूलभुलैया के अपने-अपने कोनों में लौटने "बिखराव मोड" में प्रवेश करेंगे।

वहाँ पर the pacman dossier

संबंध

algo का पूरा विवरण है

Guillaume