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

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

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

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

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

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

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

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

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

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

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

ধাপ ২: একটি এলোমেলো শুরুর ঘর নির্বাচন করুন

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

ধাপ ৩: লুপ-ইরেজিং সহ এলোমেলোভাবে হাঁটা

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

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

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

আরও পড়ুন

যদি আপনি এই পোস্টটি উপভোগ করেন, তাহলে আপনার এই পরামর্শগুলিও পছন্দ হতে পারে:

• হান্ট অ্যান্ড কিল মেজ জেনারেটর
• এলারের অ্যালগরিদম গোলকধাঁধা জেনারেটর
• বৃক্ষ বৃদ্ধির অ্যালগরিদম গোলকধাঁধা জেনারেটর