این مقاله ترجمه‌ای از مقاله‌ی Introduction to A* Pathfinding است که سعی دارد تا الگوریتم *A (بخوانید اِی اِستار) را گام به گام و بر اساس مفاهیم بسیار ابتدایی شرح دهد. در این راستا سعی کرده‌ایم که تنها به حروف و کلمات بسنده نکنیم و از تصاویر و نمودارها نیز برای انتقال مفاهیم کمک بگیریم.

مهم نیست که شما می‌خواهید از کدام زبان برنامه‌نویسی برای پیاده‌سازی این الگوریتم استفاده کنید، کافی است گام به گام با ما پیش بیایید و فقط سعی کنید که الگوریتم *A را کاملاً دقیق بفهمید.

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

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

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

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

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

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

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

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

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

اما چگونه می‌توانیم الگوریتمی بنویسیم که کوتاه‌ترین مسیر بین گربه و استخوان را پیدا کند؟ اینجاست که از *A کمک می‌گیریم!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

خوب، در الگوریتم *A این کار با اختصاص دادن امتیاز به هر مربع انجام می‌پذیرد که به آن امتیازدهی مسیر (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 با روش فاصله بلوکی

الگوریتم *A

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

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

  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 هستند، امّا شما می‌توانید آن‌ها را به راحتی به هر زبان دیگری ترجمه کنید:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
[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)