ערכתי לאחרונה בתאריך 05.05.10 בשעה 15:19 בברכה, ronen333
אחת המטרות היותר נעלות שבונים משחקים בבינה מלאכותית היא למצוא את המסלול האופטימלי מנקודה אחת לאחרת(כמעט כל משחק שתחשבו עליו דורש את זה- במיוחד שמדובר על משחקים בזמן אמת).
בקיצור,אלגוריתם זה מאוד שימושי שבונים משחקים בבינה מלאכותית, או בכללי שרוצים למצוא את המסלול הקצר ביותר מנקודה אחת לאחרת ביעילות גבוהה.אם מדובר במחרק אווירי אז הסיפור פשוט - טסים בקו ישר ורק צריך לדאוג שלא נתנגש במטוס אחר.
תכנון מסלול על הקרקע דורש התחשבות בתנאי השטח (נשקים, סלעים, אויבים אחרים וכו') ולכן דרוש כאן אלגוריתם, ורצוי יעיל.
אלגוריתם זה מוכר בשם A Star (או A *), מה שמיוחד באלגוריתם זה שהוא מוצא את המסלול הקצר ביותר על גרף מנקודה לנקודה ביעילות גבוה מאוד של | h(x) − h * (x) | = O(logh * (x)).
הוא מתבסס על האלגוריתם דייאקסטרה (DIJKSTRA), אך יעיל יותר מימנו מהסיבה שהוא מוצא את המסלול מקודקוד מסוים לקודקוד אחר, ולא כמו דייאקסטרה מקודקוד אחד לכול הקודקודים ובנוסף A STAR מסתמך על הערכה.
כדי לפשט את העניינים בהרבה יש קודם להגדיר את העולם בצורת GRID,
לכל תא בגריד נקרא "צומת"(Node).
ובשביל למצוא את המסלול דרושים לנו 3 דברים:
1.צומת התחלה
2.צומת סיום
3.כל הצמתים בעולם.
את כל הצמתים בעולם קל ויעיל לייצג באמצעות מערך דו מימדי של צמתות.
כדי למצוא את המסלול הקצר ביותר דרושים לנו קצת "כלי עזר",
מבני נתונים שיאפשרו לאחסן ולגשת למידע באופן יעיל.
1.תור קדימויות (ערימת מנימום).
2.רשימה על מנת לשמור את הצמתים שהם מחלק מהמסלול(נקרא לרשימה זו רשימה סגורה).
3.מחסנית לשמירת המסלול הסופי.
שלושת מבני נתונים אלה יהיו מטיפוס צומת.
את האובייקט צומת נייצג באמצעות 6 שדות:
עמודה,שורה,מרחק הצומת מההתחלה (נסמן בG), מרחק אווירי לסיום (נסמן בH, מרחק משוער סופי (נסמן בF),והפניה לצומת אב.
בעת הסריקה של הצמתות בעולם שלנו נוסיף את הצמתות לרשימה הסגורה(2) שלנו שהן חלק מהמסלול הסופי.
כל צומת שאנו לא בטוחים שהיא חלק מהיעד נשים בתור הקדימויות , הרשימה הפתוחה(1).
כדי לדעת איזה צומת הכי כדאית על מנת להגיע למסלול הקצר אנו נחשב את F (המסלול המשוער הסופי) ע"י חיבור המרחק של הרחק מצומת ההתחלה עד הנוכחי (G)+ פונקציה לחישוב מרחק משוער לסיום(למה כתבתי משוער? מכיוון שאנחנו לא יודעים מה המרחק האמיתי ליעד.. קו אווירי זה לא מרחק אמיתי, מכיוון שהוא לא מתחשב בתנאי הדרך, ולכן נצטרך לחשב מרחק שהוא לא אמיתי מהצומת הנסרקת ליעד), היוריסטיקה (H).
כלומר F=G+H.
אנחנו נרצה שהצומת עם הערך (F) הכי קטן ישלף בכל פעם מן התור קדימויות, על מנת שנקבל את המסלול הקצר ביותר.
לכן חשוב שלכל צומת שלא סרקנו עדיין יהיה ערך סופי(עבור G) אינסופי, כדי שנוכל רק לשפר בכל פעם את מציאת המסלול!
בפרויקט שלי בבינה מלאכותית חישבתי את המרחק המשוער (H) ע"י 2 שיטות, האחת נקראת מרחק מנהטן והשנייה היא מרחק אוקלידי- עשיתי בחירה אקראית עבור כל אויב במציאת המסלול כדי שלא כל האויבים יעשו את אותו המסלול ויהיו "מונטונים".
כעת מה שנותר לעשות הוא לדחוף לתור קדימויות (1) את צומת ההתחלה. ואח"כ לעבור על כל השכנים של הצומת הזו ונעדכן להן את הערך F אם מצאנו אחד קטן יותר.
עכשיו מספיק עם הדיבורים, נעבור לקצת קוד (כתבתי אותו בC#)-
openSet.Clear();
closeSet.Clear();
//Initialize start node start.Father = null;
start.CostSoFar = 0;
start.EstimateCost = heuristic.Estimate(start);
//Add the start node to the openSet
openSet.Enqueue(start); Node currentNode;
while(!openSet.IsEmpty)
{
//Extract(get and remove) the min Node (by TotalEstimateCost) from openSet
currentNode = openSet.Dequeue();
//Check if CurrentNode is the goal
if (currentNode.Row == end.Row && currentNode.Col == end.Col)
return GetPath(end);
//Not goal:
//Add the currentNode to the closeSet
closeSet.Add(currentNode);
//Gets all the legal neighboors of the currentNode
neighboors = GetNeighboors(currentNode);
int newCost = currentNode.CostSoFar + 1;
foreach(Node neighboor in neighboors)
{
//if neighbor is in openSet
if (openSet.Contains(neighboor))
{
//if we have better costSoFar(grade) than we update the Node
if(neighboor.CostSoFar>newCost)
{
neighboor.CostSoFar = newCost;
neighboor.Father = currentNode;
neighboor.EstimateCost = heuristic.Estimate(neighboor);
//need to update his priority
openSet.Update(neighboor);
}
}
else
{
//if neighboor is in closeSet
if(closeSet.Contains(neighboor))
{
//if we have better CostSoFar(grade) in our track,
//than it can no longer be in our track and we test it again by adding it to openSet
if (neighboor.CostSoFar > newCost)
{
closeSet.Remove(neighboor);
neighboor.CostSoFar = newCost;
neighboor.Father = currentNode;
neighboor.EstimateCost = heuristic.Estimate(neighboor);
openSet.Enqueue(neighboor);
}
}
else //A completely new node, Add it to openSet
{
//newCost must be better than infinity, update it
neighboor.CostSoFar = newCost;
neighboor.Father = currentNode;
neighboor.EstimateCost = heuristic.Estimate(neighboor);
openSet.Enqueue(neighboor);
}
} } }
throw new PathNotFoundException("A Star Fail to found path");
|
הפעולה Estimate היא הפונקצית הערכה... (כפי שהוסבר להעיל).
הפעולה GetNeighboors נועדה להחזיר רשימה של כל השכנים של הצומת שבה אתם מבקרים.
הפעולה GetPath מחזירה את המסלול ב"רברס" מהצומת האחרונה להתחלה.
לשחזור המסלול נחזיק מחסנית של צמצות ולא רשימה של צמתות
הסיבה שנחזיר מחסנית היא בגלל שבונים את המסלול מהסוף להתחלה.
בנוסף, חשוב לי להוסיף כי כאשר נגשים למאפיין TotalEstimateCost , זה למעשה מחזיר את החיבור של EstimateCost וCostSoFar .
את הקוד המלא של הפרויקט שלי שמכיל את האלגוריתם A STAR ניתן להוריד כאן:
https://rotter.name/nor/prog/15846.shtml
לאלה שלא יודעים C#, או בכללי אנשים שרוצים את הרעיון הכללי בפסדוקוד הנה מסמך PDF שמכיל פסדוקוד עם דוגמאות על איך האלגוריתם עובד-
https://rotter.name/User_files/nor/4be15c6b33c44019.pdf
(תודה לעידן התותח שהביא לי את הקובץ הזה).
מידע נוסף ניתן כמובן למצוא בוויקיפדיה (אם כי אני לא הייתי מרוצה מהפסדוקוד שלהם):
http://en.wikipedia.org/wiki/A*_search_algorithm
אני מקווה שכיסתי את הכל, והכל ברור.. תהנו! 
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
