برنامه‌نویسی هوش مصنوعی

آشنایی با الگوریتم مسیریابی *A

مقدمه

این مقاله سعی دارد تا الگوریتم *A را که از این پس برای راحتی کار، آن را الگوریتم «آ-ستاره» می نامیم، گام به گام و بر اساس مفاهیم بسیار ابتدایی شرح دهد. ضمناً سعی کرده‎‌‎‌ایم که تنها به حروف و کلمات بسنده نکنیم و از تصاویر و نمودارها نیز برای انتقال مفاهیم کمک بگیریم.

مهم نیست که شما می‎‌‎‌خواهید از کدام زبان برنامه‎‌‎‌نویسی برای پیاده‎‌‎‌سازی این الگوریتم استفاده کنید، کافی است گام به گام با ما پیش بیایید و فقط سعی کنید که الگوریتم «آ-ستاره» را کاملاً دقیق بفهمید.

گربه‎‌‎‌ی مسیریاب

تصور کنید که ما یک بازی داریم که در آن گربه‎‌‎‌ای می‎‌‎‌خواهد مسیری را برای رسیدن به یک تکه استخوان پیدا کند.

شاید از خود بپرسید که یک گربه چرا باید به دنبال یک تکه استخوان باشد؟!

خوب! گربه‎‌‎‌ی بازیِ ما بسیار زیرک است و می‎‌‎‌خواهد با جمع کردن استخوان‎‌‎‌ها و دادن آن‎‌‎‌ها به سگ‎‌‎‌ها، از چنگال آن‎‌‎‌ها در امان بماند!

فرض کنید گربه‎‌‎‌ی موجود در شکل زیر می‎‌‎‌خواهد کوتاه‎‌‎‌ترین مسیر برای رسیدن به استخوان را پیدا کند:

گربه‎‌‎‌ای در جستجوی استخوان

گربه‎‌‎‌ای در جستجوی استخوان

متأسفانه گربه نمی‎‌‎‌تواند مستقیماً از مکان فعلی خود به طرف استخوان حرکت کند، چون در مقابلش یک دیوار قرار دارد و گربه‎‌‎‌ی ما هم برخلاف ارواح نمی‏‎تواند از دیوار عبور کند!

از طرف دیگر، گربه‎‌‎‌ی ما خیلی تنبل است و دوست دارد که کوتاه‎‌‎‌ترین راه را پیدا کند.

اما چگونه می‎‌‎‌توانیم الگوریتمی بنویسیم که کوتاه‎‌‎‌ترین مسیر بین گربه و استخوان را پیدا کند؟ اینجاست که از «آ-ستاره» کمک می‎‌‎‌گیریم!

ساده کردن حوزه‎‌‎‌ی جستجو

در گام نخست باید حوزه‎‌‎‌ی جستجو را به چیزی که مدلسازی ریاضی آن آسان باشد نزدیک کنیم.

مثلاً می‎‌‎‌توانیم حوزه‎‌‎‌ی جستجو را پیکسل‎‌‎‌بندی کنیم؛ اما در شرایط فعلی این کاملاً غیرضروری است و فقط کار ما را سخت می‎‌‎‌کند پس بهتر است به چیز ساده‎‌‎‌تری فکر کنیم مثلاً تقسیم‎‌‎‌بندی صفحه به مربع‎‌‎‌های هم اندازه و تا حد ممکن بزرگ. البته می‎‌‎‌توان واحدهای مختلفی برای تقسیم‎‌‎‌بندی صفحه (مثل مثلث یا شش‎‌‎‌‏ضلعی) به کار برد اما مربع آسان‎‌‎‌ترین و بهترین گزینه‎‌‎‌ای است که می‎‌‎‌توان برای این مسئله انتخاب کرد.

با این تقسیم‎‌‎‌بندی می‎‌‎‌توانیم حوزه‎‌‎‌ی جستجو را تبدیل به یک آرایه‎‌‎‌ی دو بعدی کنیم که مانند یک نقشه از حوزه‎‌‎‌ی جستجو، همه چیز را در اختیار ما می‎‌‎‌گذارد. مثلاً اگر سطح یک مربع کاشی شده‎‌‎‌ی 25 در 25 را در نظر بگیریم، حوزه‎‌‎‌ی جستجوی ما یک آرایه‎‌‎‌ی دوبعدی متشکل از 625 کاشی مربعی‎‌‎‌شکل خواهد بود. حالا اگر در همین نقشه، بخواهیم از واحد پیکسل استفاده کنیم، حوزه‎‌‎‌ی جستجوی ما تبدیل به یک آرایه‎‌‎‌ی دوبعدی متشکل از 640000 مربع خواهد شد (با این فرض که ابعاد هر کاشی 32×32 پیکسل باشد)!

بهتر است پس از تقسیم‎‌‎‌بندیِ مربعیِ حوزه‎‌‎‌ی جستجو نگاهی به آن بیندازیم که حالا به یک صفحه با (6×7 کاشی =) 42 کاشی مربعی‎‌‎‌شکل تبدیل شده است:

تقسیم‎‌‎‌بندی مربعی حوزه‎‌‎‌ی جستجو

تقسیم‎‌‎‌بندی مربعی حوزه‎‌‎‌ی جستجو

لیست‎‌‎‌های باز و بسته

حالاً که حوزه‎‌‎‌ی جستجو را به شکل ساده‎‌‎‌تری درآوردیم، زمان بحث در مورد الگوریتم آ-ستاره رسیده است.

گربه‎‌‎‌ی ما علاوه بر این که تنبل است، حافظه‎‌‎‌ی چندان خوبی هم ندارد، بنابر این ما به دو لیست نیاز داریم:

یکی برای فهرست کردن تمام مربع‎‌‎‌هایی که تصور می‎‌‎‌شود کوتاه‎‌‎‌ترین مسیر را به دست دهند؛ که آن را لیست باز (Open List) می‎‌‎‌نامیم.

دیگری برای فهرست کردن مربع‎‌‎‌هایی که دیگر لازم نیست مورد ارزیابی قرار گیرند که آن را لیست بسته (Closed List) می‎‌‎‌نامیم.

گربه با اضافه کردن موقعیت فعلی‎‌‎‌اش به لیست بسته، کارش را شروع می‎‌‎‌کند. (ما نقطه‎‌‎‌ی شروع را A می‏‎نامیم.) سپس از میان مربع‎‌‎‌های همسایه‎‌‎‌اش (Adjucent Squares) ، آن‎‌‎‌هایی را که قابل تردد هستند به لیست باز اضافه می‎‌‎‌کند.

این تصویر نمونه‎‌‎‌ای از چیزی است در بالا بیان شد، البته با این فرض که گربه در محیطی باز و بدون مانع قرار داشته باشد. (مربع‎‌‎‌های با حاشیه‎‌‎‌ی سبزرنگ همان لیستِ باز هستند):

تمام انتخاب‌های ممکن برای گربه در مکان فعلی

تمام انتخاب‌های ممکن برای گربه در مکان فعلی

حالا گربه باید مشخص کند که کدام یک از این مربع‎‌‎‌ها در کوتاه‎‌‎‌ترین مسیر قرار دارند. اما چگونه؟

خوب، در الگوریتم آ-ستاره این کار با اختصاص دادن امتیاز به هر مربع انجام می‎‌‎‌پذیرد که به آن امتیازدهی مسیر (Path Scoring) گفته می‏شود.

امتیازدهی به مسیر

ما به هر مربع یک امتیاز که حاصل جمع G+H است، اختصاص می‎‌‎‌دهیم:

G

‎هزینه‌‎‌‎‌ی حرکت از نقطه‎‌‎‌ی شروع مسیر تا مکان فعلی است. با این حساب برای مربع همسایه‎‌‎‌ی نقطه‎‌‎‌ی A ، این مقدار برابر 1 خواهد بود و هرچقدر که از نقطه‎‌‎‌ی آغازِ حرکت دورتر شویم، مقدار G افزایش خواهد یافت.

H

تخمین ما از فاصله‎‌‎‌ی مربعی که اکنون در آن قرار داریم تا نقطه‎‌‎‌ی پایان مسیر (که از این پس آن را نقطه‎ی B می‏‎نامیم) است. این عدد لزوماً مقدار واقعی نیست چون ما هنوز مسیر را نپیموده‎‌‎‌ایم تا مقداد دقیق آن را بفهمیم بلکه فقط یک حدس است.

شاید بپرسید که منظور از ‎هزینه‎‌‎‌ی حرکت (Movement Cost) چیست؟ خوب، در این بازی ما بسیار ساده است – صرفاً تعداد مربع‎‌‎‌هایی است که از روی آن‎‌‎‌ها عبور کرده‎‏ایم.

به هر حال باید به یاد داشته باشید که نحوه‎‌‎‌ی محاسبه‎‌‎‌ی G و H متناسب با شرایط بازی می‎‌‎‌تواند تغییر کند. مثلاً:

  • اگر شما مجاز به حرکت‎‌‎‌های قطری (اُریب) باشید، باید ‎هزینه‌‎‌‎‌ی حرکت مربوط به حرکت‎‌‎‌های قطری را اندکی بیشتر از حرکت‎‌‎‌های مستقیم (بالا، چپ، پایین و راست) در نظر بگیرید.
  • اگر در بازی شما عوارض و موانع طبیعی مختلفی وجود دارد باید ‎هزینه‌‎‌‎‌ی حرکت را برای عبور از باتلاق، دریاچه و هر مانعی که عبور از آن مشکل‎‌‎‌تر است، بیشتر در نظر بگیرید.

این‎‌‎‌ها همگی مفاهیم کلّی بودند – حالا وقت دقیق شدن در جزئیات محاسبه‎‌‎‌ی G و H است.

درباره‎‌‎‌ی G بیشتر بدانید

به یاد بیاورید که G ‎هزینه‌‎‌‎‌ی حرکت (و به طور خاص در بازی ما، تعداد مربع‎‌‎‌های پیموده شده) از نقطه‎‌‎‌ی شروع حرکت یعنی A تا موقعیت کنونی است.

برای محاسبه‎‌‎‌ی G در یک مکان خاص از مسیر، ما باید G مربوط به موقعیتِ والد (Parent) آن (یعنی آخرین مربعی که از آن گذشته‎‌‎‌ایم و به اینجا رسیده‎‌‎‌ایم) را در نظر بگیریم و یک واحد به آن اضافه کنیم. با این دستورالعمل، G مربوط به هر مربع، تعداد مربع‎‌‎‌هایی است که از نقطه‎‌‎‌ی شروع یعنی A تا موقعیت کنونی از روی آن‎‌‎‌ها عبور کرده‎‌‎‌ایم.

به عنوان مثال، نمودار زیرین دو مسیر متفاوت را به سوی دو تکه استخوان متفاوت نشان می‎‌‎‌دهد که مقادیر G مربوط به هر مربع موجود در مسیر روی خود آن مربع نوشته شده است:

مقادیر متوالی G در دو مسیر مختلف

مقادیر متوالی G در دو مسیر مختلف

درباره‎‌‎‌ی H بیشتر بدانید

به یاد بیاورید که H ‎هزینه‌‎‌‎‌ی حرکت تخمینی (یعنی تعداد مربع‎‌‎‌های باقیمانده) از موقعیت فعلی تا نقطه‎‌‎‌ی پایان مسیر یعنی B است.

هر چقدر که ‎هزینه‌‎‌‎‌ی حرکت تخمینی به اندازه‎‌‎‌ی واقعی نزدیک‎‌‎‌تر باشد، مسیر نهایی درست‎‌‎‌تر خواهد بود. اگر این مقدار تخمینی مورد استفاده قرار نگیرد، ممکن است مسیر نهایی کوتاه‎‌‎‌ترین مسیر نباشد (البته شاید نزدیک به آن باشد). این موضوع بسیار پیچیده است و از این رو در این مقاله پوشش داده نخواهد شد.

برای این که کارمان را ساده کنیم از روش فاصله‎‌‎‌ی منهتن (Manhattan distance method) که با نام‎‌‎‌های طول منهتن (Manhattan Length) یا فاصله‎‌‎‌ی بلوک شهری (City block distance) هم شناخته می‎‌‎‌شود استفاده می‎‌‎‌کنیم. در این روش بدون در نظر گرفتن موانع و عوارض طبیعی موجود در مسیر، فقط فاصله‎‌‎‌ی افقی و عمودی از نقطه‎‌‎‌ی فعلی تا رسیدن به نقطه‎‌‎‌ی نهایی یعنی B را در نظر می‏‎گیریم.

به عنوان مثال، تصویر زیر چگونگی استفاده از «فاصله‎‌‎‌ی بلوکی» را در محاسبه‎‌‎‌ی H نشان می‎‌‎‌دهد (که مقدار آن با رنگ سیاه در مربع مربوطه نوشته شده است):

تخمین مقدار H با روش فاصله بلوکی

تخمین مقدار H با روش فاصله بلوکی

الگوریتم آ-ستاره

حالا که متوجه شدید چگونه باید امتیاز هر مربع را محاسبه کنیم (که از این به بعد آن را F می‎‌‎‌نامیم و برابر با G+H است)، وقت آن است که ببینیم الگوریتم آ-ستاره چگونه کار می‎‌‎‌کند.

گربه‎‌‎‌ی ما کوتاه‎‌‎‌ترین مسیر را با تکرار کردن مراحل زیر پیدا خواهد کرد:

  1. مربعی که کم‎‌‎‌ترین امتیاز را در لیست باز دارد را در نظر می‎‌‎‌گیریم. از این پس این مربع را S می‎‌‎‌نامیم.
  2. S را از لیست باز حذف می‎‌‎‌کنیم و به لیست بسته اضافه می‎‌‎‌کنیم.
  3. به ازای هر مربعِ T که در همسایگی S قرار دارد:
  4. اگر T در لیستِ بسته است: آن را نادیده بگیر. (کاری به کارش نداشته باش.)
  5. اگر T در لیستِ باز نیست: آن را به لیست باز اضافه کن و امتیازش (F) را محاسبه کن.
  6. اگر T در لیستِ باز است: بررسی کن که با در نظر گرفتن S به عنوان موقعیت والد و محاسبه‎‌‎‌ی مجددِ G ، آیا امتیازِ F آن کاهش می‎‌‎‌یابد؟ اگر پاسخ مثبت است، امتیاز آن را به روز کن و موقعیتِ والد آن را نیز به روز کن.

اگر هنوز هم کمی سردرگم هستید، نگران نباشید چون از این پس با یک مثال و گام به گام پیش خواهیم رفت تا نحوه‎‌‎‌ی عملکرد این الگوریتم را عیناً مشاهده کنید!

مسیر گربه

بگذارید با همان مثالِ گربه‎‌‎‌ی تنبل خودمان و مسیرش به سوی تکه استخوان پیش برویم.

در نمودارهای زیر، مقادیرِ F = G + H مطابق با نکات زیر داخل هر مربع نوشته شده‎‌‎‌اند:

F (امتیاز مربع مربوطه): گوشه‎‌‎‌ی چپ و بالا

G (مسافت پیموده شده از A تا مربع مربوطه): گوشه‎‌‎‌ی چپ و پایین

H (مسافت تخمینی از مربع مربوطه تا B): گوشه‎‌‎‌ی راست و پایین

همچنین، پیکان‎‌‎‌های موجود در هر مربع، جهت حرکتی که برای رفتن به آن مربع نیاز است را نشان می‎‌‎‌دهد.

در نهایت، در هر مرحله، مربع‎‌‎‌های سرخ‎‌‎‌رنگ نشان دهنده‎‌‎‌ی موارد موجود در لیست بسته هستند و مربع‎‌‎‌های سبزرنگ نشان دهنده‎‌‎‌ی موارد موجود در لیست باز هستند.

بسیار خوب، حالا شروع می‎‌‎‌کنیم:

گام اوّل

در گام اوّل، گربه‎‌‎‌ی ما از میان مربع‎‌‎‌های مجاورِ مکان کنونی یعنی A ، مربع‎‌‎‌هایی را که مسدود نیستند شناسایی کرده و امتیازِ F آن‎‌‎‌ها را محاسبه می‎‌‎‌کند و سپس آن‎‌‎‌ها را به لیست باز اضافه می‎‌‎‌کند:

گام اول

گام اول

در شکل بالا می‏‎ببینید که مقدار H برای هر مربع نوشته شده است (دو تا از آن‎‌‎‌ها 6 هستند و یکی 4). من پیشنهاد می‎‌‎‌کنم که از همان روش شمارش مربع‎‌‎‌ها با توجه به «فاصله‎‌‎‌ی بلوکی» استفاده کنید تا متوجه شوید که چگونه H را محاسبه کرده‏ایم.

همچنین توجه داشته باشید که مقدارِ F (در گوشه‎‌‎‌ی چپ و بالا) صرفاً حاصل جمع G+H است (که در گوشه‎‌‎‌های پایینی نوشته شده‎‌‎‌اند.)

گام دوم

در گام بعدی، گربه‎‌‎‌ی ما مربعی که کم‎‌‎‌ترین مقدار F را دارد، انتخاب کرده و آن را به لیست بسته اضافه می‎‌‎‌کند، از لیست باز حذف می‎‌‎‌کند و مربع‎‌‎‌های مجاور این مربع جدید (که کم‎‌‎‌ترین F را داشته است) را شناسایی می‎‌‎‌کند.

گام دوم

گام دوم

مربعی که کمترین امتیاز را دارد همان مربعی است که مقدارِ F آن برابر 5 است. گربه تلاش می‎‌‎‌کند که تمام مربع‎‌‎‌های مجاور را به لیستِ باز اضافه کند (و امتیاز آن‎‌‎‌ها را محاسبه کند)، اما باید توجه داشته باشید که او نمی‎‌‎‌تواند مکان قبلی خودش را (که هم اکنون در لیستِ بسته قرار دارد) یا موانع موجود در مسیر مانند مربع‎‌‎‌های هاشور خورده را (که قابل تردد نیستند) به لیست باز اضافه کند.

توجه کنید که برای مربع‎‌‎‌های جدیدی که به لیست باز افزوده می‎‌‎‌شوند، مقدارِ G به اندازه‎‌‎‌ی یک واحد افزایش پیدا می‎‌‎‌کند چون این مربع‎‌‎‌ها به اندازه‏ی 2 کاشی با نقطه‎‌‎‌ی شروع فاصله دارند. برای اطمینان از مقدار H هم می‎‌‎‌توانید از شمارش «فاصله‎‌‎‌ی بلوکی» استفاده کنید.

گام سوم

دوباره مربعی که کمترین مقدار F (یعنی 5) را داراست انتخاب کرده و روند پیشین را تکرار می‎‌‎‌کنیم:

گام سوم

گام سوم

در این مرحله تنها یک کاشی می‎‌‎‌تواند به لیست باز اضافه شود، چون دوتا از کاشی‎‌‎‌های همسایه مسدود هستند و یکی هم در لیستِ بسته قرار دارد.

گام چهارم

حالا با یک وضعیت جالب مواجه شده‎‌‎‌ایم. همان‎‌‎‌گونه که در گام سوم مشاهده کردید، 4 مربع با مقدارِ F یکسان (یعنی 7) موجودند؛ الآن چه باید کرد؟!

راه حل‎‌‎‌های مختلفی برای این وضعیت وجود دارد اما ساده‎‌‎‌ترین و در عین حال سریع‎‌‎‌ترین راه این است که آخرین مربعی که به لیستِ باز اضافه شده است را برای حرکت بعدی انتخاب کنیم:

گام چهارم

گام چهارم

این بار دو کاشی قابل تردد در همسایگی وجود دارند که امتیاز آن‎‌‎‌ها را حساب می‎‌‎‌کنیم.

گام پنجم

دوباره مربعی که کمترین مقدار F (یعنی 7) را داراست و آخر از همه به لیستِ باز افزوده شده است انتخاب می‎‌‎‌کنیم:

گام پنجم

گام پنجم

در این مرحله فقط یک مربعِ قابلِ تردد به لیست باز اضافه می‎‌‎‌شود. کم کم به استخوان نزدیک می‎‌‎‌شویم!

گام ششم

دیگر خودتان روند کار را یاد گرفته‎‌‎‌اید! مطمئنم که می‎‌‎‌توانید گام بعدی را حدس بزنید:

گام ششم

گام ششم

تقریباً رسیده‎‌‎‌ایم، امّا این بار مشاهده می‎‌‎‌کنید که دو مسیر وجود دارد که هر دو طول یکسانی دارند و کوتاه‎‌‎‌ترین مسیر هستند.  می‎‌‎‌توانیم یکی از آن‎‌‎‌ها را انتخاب کنیم تا به استخوان برسیم:

دو مسیر متفاوت با طول یکسان

دو مسیر متفاوت با طول یکسان

در مثال ما 2 مسیر مختلف به عنوان کوتاه‎‌‎‌ترین مسیر وجود دارند:

6 – 5 – 4 – 3 – 2 – 1

7 – 5 – 4 – 3 – 2 – 1

فرقی نمی‎‌‎‌کند که کدام‎‌‎‌یک از آن‎‌‎‌ها را انتخاب کنیم، این موضوع باید در پیاده‌سازی الگوریتم هنگام کدنویسی در نظر گرفته شود.

گام هفتم

بگذارید مسیر را از طریق یکی از این دو مربع ادامه دهیم:

گام هفتم

گام هفتم

حالا استخوان در لیستِ باز است!

گام هشتم

در وضعیتی که استخوان (نقطه‎‌‎‌ی مقصد) در لیست باز قرار گیرد، الگوریتم آن را به لیستِ بسته اضافه می‎‌‎‌کند:

گام هشتم

گام هشتم

سپس تنها کاری که الگوریتم باید انجام دهد این است به عقب برگردد و مسیر نهایی را شناسایی کند.

مسیر نهایی

مسیر نهایی

یک گربه‎‌‎‌ی معمولی

در مثال فوق، ما می‎‌‎‌بینیم که وقتی گربه به دنبال کوتاه‎‌‎‌ترین مسیر می‎‌‎‌گشت، غالباً بهترین مربع را انتخاب می‎‌‎‌کرد (آن مربعی که در راستای کوتاه‎‌‎‌ترین مسیرِ آینده‎‌‎‌اش قرار داشت) – گویا گربه‎‌‎‌ی ما می‏‎توانست آینده را پیش‏بینی کند.

اما چه می‎‌‎‌شد اگر گربه‎‌‎‌ی ما نمی‎‌‎‌توانست آینده را ببیند و همواره اوّلین مربعی را که به لیست اضافه می‎‌‎‌شد انتخاب می‎‌‎‌کرد؟

شکل زیر نشان می‎‌‎‌دهد که اگر چنین فرایندی را طی می‎‌‎‌کردیم باید چه مربع‎‌‎‌هایی را مورد بررسی قرار می‎‌‎‌دادیم. شما مشاهده می‎‌‎‌کنید که در این حالت گربه‎‌‎‌ی ما مربع‎‌‎‌های بیشتری را امتحان می‎‌‎‌کند، امّا باز هم کوتاه‎‌‎‌ترین مسیر را پیدا می‎‌‎‌کند (نه دقیقاً همان مسیری که قبلاً پیدا کرده بود امّا مسیر دیگری با طول یکسان پیدا می‎‌‎‌کند):

پیدا کردن مسیر بدون انتخاب بهترین مربع‌ها

پیدا کردن مسیر بدون انتخاب بهترین مربع‌ها

مربع‎‌‎‌های سرخ‎‌‎‌رنگ در نمودار فوق لزوماً کوتاه‎‌‎‌ترین مسیر را نشان نمی‎‌‎‌دهند، آن‎‌‎‌ها فقط مربع‎‌‎‌هایی را نشان می‎‌‎‌دهند که در مراحل مختلف به عنوانِ مربعِ S در نظر گرفته شده‎‌‎‌اند.

من توصیه می‎‌‎‌کنم که به نمودار بالایی نگاه کنید و سعی کنید که همگام با آن پیش بروید. این بار در هر چندراهی، «بدترین» مسیر را برای رفتن انتخاب کنید. خواهید دید که باز هم با پیمودن کوتاه‎‌‎‌ترین مسیر به انتها می‎‌‎‌رسید!

شما می‎‌‎‌بینید که اگر مربعِ «اشتباه» را دنبال کنید، مشکلی پیش نمی‎‌‎‌آید و شما با کوتاه‎‌‎‌ترین مسیر به انتها می‎‌‎‌رسید هرچند که باید روند الگوریتم را بیشتر تکرار کنید.

در هنگام اجرای الگوریتم، مربع‎‌‎‌ها را با توجه به الگوریتم زیر به لیستِ باز اضافه می‎‌‎‌کنیم:

مربع‎‌‎‌های همسایه به این ترتیب در نظر گرفته می‎‌‎‌شوند:

بالا / چپ / پایین / راست (البته شما می‌توانید ترتیب دیگری انتخاب کنید!)

یک مربع پس از تمام مربع‎‌‎‌هایی که امتیاز یکسانی با آن دارند به لیستِ باز افزوده می‎‌‎‌شود (بنابر این اوّلین مربعی که اضافه می‎‌‎‌شود اولّین مربعی است که گربه انتخاب می‎‌‎‌کند).

این یک نمودار برای عقب‎‌‎‌گرد و بازخوانی مسیر است:

بازخوانی مسیر

بازخوانی مسیر

کوتاه‎‌‎‌ترین مسیر با شروع از نقطه‎‌‎‌ی مقصد و عقب رفتن از یک مربع والد به مربع والد دیگر ساخته می‎‌‎‌شود (مثلاً: در مربعِ مقصد می‎‌‎‌بینیم که پیکانِ داخلِ آن به سمت راست است پس مربعِ والد آن در سمت چپ قرار دارد).

برای نتیجه‎‌‎‌گیری می‎‌‎‌توانیم فرایندی را که گربه طی می‎‌‎‌کند در قالب کد زیر خلاصه کنیم. کدهای زیر به زبان Objective-C هستند، امّا شما می‎‌‎‌توانید آن‎‌‎‌ها را به راحتی به هر زبان دیگری ترجمه کنید:

[openList add:originalSquare]; // start by adding the original position to the open list

do {
       currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score
       [closedList add:currentSquare]; // add the current square to the closed list
       [openList remove:currentSquare]; // remove it to the open list

       if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path
              // PATH FOUND
              break; // break the loop
       }

       adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares

       foreach (aSquare in adjacentSquares) {
              if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it
                     continue; // Go to the next adjacent square
              }

              if (![openList contains:aSquare]) { // if its not in the open list
                     // compute its score, set the parent
                     [openList add:aSquare]; // and add it to the open list
              } else { // if its already in the open list
                     // test if using the current G score make the aSquare F score lower, if yes update the parent because it means its a better path
              }
       }
} while(![openList isEmpty]); // Continue until there is no more available square in the open list (which means there is no path)

مرجع: raywenderlich.com

دیدگاه‌های شما (۷ دیدگاه)
  1. سلام
    ممنون از توضیح کامل و فوق العاده که نوشتید
    من برای پروژه ام نیاز به یادگیری خیلی سریع این الگوریتم داشتم. با مطالعه مثال شما و به زبان ساده در کمترین زمان اونو یاد گرفتم.
    خیلی خیلی ممنون.
    موفق باشید

  2. سلام
    این مطلب رو مدت ها قبل خونده بودم ( اگر اشتباه نکنم روی ساب دامین mp.tabin.ir بود ) به نظرم یکی از مقالاتِ خوبِ فارسی در مورد این الگوریتم هست.

  3. توضیحات این سایت واقعا به درک مفهومی الگوریتم
    *aکمک میکنه

  4. سلام و تشکر فراوان از توضیحات مفیدتون

  5. سلام، ممنون از مقاله بسیار خوبتون بسیار عالی و کاربردی،وجود این مقاله ها برای افرادی تو زبان ضعیفن خیلی خوبه مثل من.
    من با GML این رو پیاده سازی کردم البته فقط یه چالش میمونه که اونم عرض کاراکتر از عرض مسیر باز بیشتر باشه که اونم خدارو شکر حل شد 🙂

  6. با سلام مهندس عزیزم چقدر جالب و روان. لطفا مثالهای متنوعی تری هم بزارین. با سپاس

پاسخی بگذارید