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

آشنایی با الگوریتم مسیریابی *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. سلام
    ممنون از توضیح کامل و فوق العاده که نوشتید
    من برای پروژه ام نیاز به یادگیری خیلی سریع این الگوریتم داشتم. با مطالعه مثال شما و به زبان ساده در کمترین زمان اونو یاد گرفتم.
    خیلی خیلی ممنون.
    موفق باشید

دیدگاهتان را بنویسید