سلام؛
به نظر من شما سه حالت پیش رو دارین.
حالت اول اینه که بلدید با رفتار
Path Finding کار کنید.
حالت دوم اینه که شما بلد نیستید با این رفتار کار کنید. در هر صورت باید خودتون متوسل به ریاضیات و مبحث گراف ها بشین.
حالت سوم اینه که از
این رفتار که مختص تایل مپ ها هست استفاده کنین و مثالی هم که میتونه شما رو کمک کنه
این هست که در تاپیکی که معرفی کردم موجوده.
قبل از هر چیز باید بدونید الگوریتمی که در رفتار
Path Finding استفاده شده
A* Search (جستجوی A*) نام داره. این الگوریتم قادره مسیر از مبدأ تا مقصد رو با وجود موانع شناسایی کنه اما چون فهمش نیاز به دونستن مباحثی مثل هیستوریک و وزن گراف و ... داره و ممکنه پیچیده به نظر بیاد از گفتن این روش صرف نظر میکنم و یک روش ساده تر رو که مبتنی بر
تایل (Tile) هست رو بررسی می کنیم. دقت کن که پروسه ای که در ادامه شرح میدم مشابه همون پروسه ای هست که در رفتاری که معرفی کردم اتفاق میفته اما رفتاری که معرفی کردم یکم پیشرفته تر و بهینه تر عمل میکنه. البته ادامه مطلب فقط صرف آشنایی هست.
فرض کنیم نقشه ای مشابه شکل زیر داریم: (X بیانگر دیوار و مسیر مسدود (مانع)، S نقطه شروع (مبدأ)، _ مسیرهای باز و O هم نقطه مقصد)
کد:
1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X
قبل از هر چیز باید یک لیست شامل مختصات های هر یک از المان های موجود در نقشه تهیه کنیم. اولین مقداری که باید در این لیست باید بگنجونیم نقطه نهایی هست یعنی
(3,8,0). به زبان ساده تر انگار داریم اینجا یک مجموعه شامل مختصات های المان های موجود تشکیل میدیم. به هر یک از اعضای مجموعه یک شمارنده اختصاص میدیم. بعد بر روی تک تک اعضای مجموعه پردازش انجام میدیم و برای هر یک از اعضا به شکل زیر عمل می کنیم:
- * 1- یک لیست از چهار المان مجاور عضو مورد پردازش تشکیل میدیم. لیست حاوی چهار المان مجاور عضو (3,8,0) { (۲٬۸٬۱),(۳٬۷٬۱),(۴٬۸٬۱),(۳٬۹٬۱) } خواهد شد.
- * 2- بعد عناصر موجود در این لیست جدید بررسی میشود که اگر آن عنصر دیوار بود یا در لیست اصلی مختصاتی (مجموعه اولیه که تشکیل دادیم) مشابه با شمارندهٔ کمتر وجود داشت حذف میشود.
با اتمام مراحل 1 و 2 اصطلاحاً یک دور (راند) را به اتمام رسانده ایم. پس از اتمام یک راند لیست تشکیل شده در مرحله انتجاب چهار المان مجاور را به انتهای لیست اصلی (مجموعه اولیه) اضافه می کنیم (البته با توجه به مرحله شماره 2). در نهایت هم به سراغ دیگر اعضای مجموعه اصلی جهت پردازش میریم.
پس هر راند (دور) اعضای مجموعه اصلی به شکل زیر خواهند شد:
ما از نقطه نهایی شروع به پردازش کردیم و به نقطه اولیه (1,3,7) رسیدیم. با رسیدن به نقطه اولیه یعنی بالاخره کار تموم شده. اینکه در کدوم راند به نقطه نهایی برسیم بستگی به این داره که چقدر خوش شانس باشیم. الگویی که ما رو به مقصد میرسونه طبق محاسباتی که در راند سوم انجام دادیم به شکل
(1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> (1,8,2) -> (2,8,1) -> (3,8,0) خواهد بود.
المان هایی که با علامت
نشان داده شده اند میتونن هم ما رو از مبدأ به مقصد و هم از مقصد به مبدأ منتقل کنند.
کد:
1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X X _ X _ _ _ X 4
X X X X _ X 5
X X X X _ X 6
X X X X _ X 7
X O X _ X 8
X X X X X X X X X X
موفق باشین.