উইলসনের অ্যালগরিদম গোলকধাঁধা জেনারেটর

উইলসনের অ্যালগরিদম একটি লুপ-মুছে ফেলা এলোমেলো হাঁটার পদ্ধতি যা গোলকধাঁধা তৈরির জন্য অভিন্ন স্প্যানিং গাছ তৈরি করে। এর অর্থ হ'ল প্রদত্ত আকারের সমস্ত সম্ভাব্য গোলকধাঁধা সমানভাবে উত্পন্ন হওয়ার সম্ভাবনা রয়েছে, এটি একটি নিরপেক্ষ গোলকধাঁধা প্রজন্মের কৌশল তৈরি করে। উইলসনের অ্যালগরিদমকে অ্যালডাস-ব্রোডার অ্যালগরিদমের একটি উন্নত সংস্করণ হিসাবে বিবেচনা করা যেতে পারে, কারণ এটি অভিন্ন বৈশিষ্ট্যগুলির সাথে গোলকধাঁধা তৈরি করে, তবে এটি অনেক দ্রুত চলে, তাই আমি এখানে অ্যালডাস-ব্রোডার অ্যালগরিদম প্রয়োগ করতে বিরক্ত করি নি।

একটি নিখুঁত গোলকধাঁধা হল এমন একটি গোলকধাঁধা যেখানে গোলকধাঁধার যেকোনো বিন্দু থেকে অন্য যেকোনো বিন্দুতে ঠিক একটি পথ থাকে। এর মানে হল আপনি বৃত্তাকারে ঘুরে বেড়াতে পারবেন না, তবে আপনি প্রায়শই অচল প্রান্তের মুখোমুখি হবেন, যা আপনাকে ঘুরে ফিরে যেতে বাধ্য করবে।

এখানে তৈরি করা গোলকধাঁধা মানচিত্রগুলিতে কোনও শুরু এবং শেষ অবস্থান ছাড়াই একটি ডিফল্ট সংস্করণ রয়েছে, তাই আপনি নিজেই সেগুলি সিদ্ধান্ত নিতে পারেন: গোলকধাঁধার যেকোনো বিন্দু থেকে অন্য যেকোনো বিন্দুতে একটি সমাধান থাকবে। আপনি যদি অনুপ্রেরণা চান, তাহলে আপনি একটি প্রস্তাবিত শুরু এবং শেষ অবস্থান সক্ষম করতে পারেন - এবং এমনকি উভয়ের মধ্যে সমাধানও দেখতে পারেন।

উইলসনের অ্যালগরিদম সম্পর্কে

লুপ-মুছে ফেলা এলোমেলো প্রাচীর ব্যবহার করে অভিন্ন স্প্যানিং গাছ তৈরির জন্য উইলসনের অ্যালগরিদমটি ডেভিড ব্রুস উইলসন তৈরি করেছিলেন।

উইলসন মূলত ১৯৯৬ সালে সম্ভাব্যতা তত্ত্বে এলোমেলো বিস্তৃত গাছ এবং মার্কভ চেইন নিয়ে গবেষণা করার সময় এই অ্যালগরিদমটি চালু করেছিলেন। যদিও তার কাজ প্রাথমিকভাবে গণিত এবং পরিসংখ্যান পদার্থবিজ্ঞানে ছিল, পুরোপুরি অভিন্ন গোলকধাঁধা উত্পাদন করার দক্ষতার কারণে অ্যালগরিদমটি গোলকধাঁধা প্রজন্মের জন্য ব্যাপকভাবে গৃহীত হয়েছে।

উইলসনের অ্যালগরিদম কীভাবে গোলকধাঁধা প্রজন্মের জন্য কাজ করে

উইলসনের অ্যালগরিদম নিশ্চিত করে যে চূড়ান্ত গোলকধাঁধাটি এলোমেলো পদচারণা ব্যবহার করে অপরিদর্শিত কোষগুলি থেকে পুনরাবৃত্তিমূলকভাবে খোদাই করে কোনও লুপ ছাড়াই সম্পূর্ণরূপে সংযুক্ত রয়েছে।

ধাপ 1: আরম্ভ করুন

• দেয়াল দিয়ে ভরা গ্রিড দিয়ে শুরু করুন।
• সমস্ত সম্ভাব্য প্যাসেজ কক্ষের একটি তালিকা সংজ্ঞায়িত করুন।

পদক্ষেপ 2: একটি এলোমেলো প্রারম্ভিক ঘর চয়ন করুন

• যে কোনও এলোমেলো ঘর চয়ন করুন ও এটিকে পরিদর্শন হিসাবে চিহ্নিত করুন। এটি প্রজন্মের সময় গোলকধাঁধা প্রারম্ভিক পয়েন্ট হিসাবে কাজ করে।

পদক্ষেপ 3: লুপ-মোছার সাথে এলোমেলো হাঁটা

• একটি অপরিদর্শিত ঘর চয়ন করুন এবং একটি এলোমেলো হাঁটা শুরু করুন (এলোমেলো দিকগুলিতে চলমান)।
• যদি হাঁটা ইতিমধ্যে পরিদর্শন করা কক্ষে পৌঁছে যায় তবে পথের কোনও লুপ মুছুন।
• একবার হাঁটা পরিদর্শন করা অঞ্চলের সাথে সংযুক্ত হয়ে গেলে, পথের সমস্ত কক্ষকে পরিদর্শন হিসাবে চিহ্নিত করুন।

পদক্ষেপ 4: সমস্ত ঘর পরিদর্শন না হওয়া পর্যন্ত পুনরাবৃত্তি করুন:

• প্রতিটি ঘর গোলকধাঁধার অংশ না হওয়া পর্যন্ত অপরিদর্শিত কক্ষগুলি নির্বাচন করা এবং এলোমেলো পদচারণা করা চালিয়ে যান।