ערכתי לאחרונה בתאריך 05.04.10 בשעה 17:28 בברכה, ronen333
מה קורה אנשים?
אני מקווה שזה יהיה הפוסט האחרון שלי בנושא..
מימשתי את האלגוריתם מחדש על מנת שהוא יתאים למטריצת משחק שלי{שאותה הפכתי למטריצת Nodes. כל NODE מכיל את המיקום שלו (שורה ועמודה), g,h,f, וסוג הנשק שהוא מכיל(על מנת שאני אדע אם הוא מכשול)}.עד פה סבבה, המבנה הזה יאפשר לי יעילות BEST.
שאני מפעיל את האלגוריתם הוא נכנס ללולאה אינסופית משום מה.. רציתי שתעזרו לי בלאתר למה, ומה אני צריך להוסיף כדי לשפר וכו'...
מבני נתונים: (הוגדרו ואותחלו במחלקה עצמה)
OpenSet זה תור קדימויות (ערימה).
closeSet זה סתם רשימה.
connections זה רשימת nodes שיכיל את השכנים (כל השכנים שניתן ללכת בהם{לא מכשולים}).
HeapItem הוא struct שאוסף Object וdouble, כאשר Object יהיה האוביקט Node וdouble זה הערך עדיפות, שבאלגוריתם זה הוא f.
פעולות:
getPath מקבל Node סיום ומחזיר את מחסנית שמכילה את כל הNODES המסמלים את המסלול.
UpdatePriotity מעדכן את העדיפות של Node (העדיפות היא כמובן עפ"י f).
GetConnections מחזיר רשימה של השכנים לNODE שהם לא מכשול.
Contains בודק אם הNode מופיע ברשימה/תור קדימויות.
אממ נדמה לי שזה כמו מה שעלי להגיד על מנת שהאלגוריתם יהיה ברור, אם משהו לא ברור תשאלו אני אענה..
public Stack<Node> AstarPathSearching(Node start,Node end,Heuristic heuristic) { //Empty openSet and closeSet set openSet.Clear(); closeSet.Clear(); //Initalize start Node start.CostSoFar = 0; //g =0 start.EstimateCost = heuristic.Estimate(start);//h=Distance to end start.TotalEstimateCost = start.CostSoFar + start.EstimateCost;//f=g+h start.Father = null; //Add the start node to the openset openSet.Enqeue(new HeapItem(start, start.TotalEstimateCost)); Node currentNode; while(openSet.IsEmpty()==false) { // take out node with minimum f value currentNode = (Node)openSet.Dequeue(); //if got to goal then return the trace if (currentNode.Row == end.Row &¤tNode.Col==end.Col) return GetPath(end); closeSet.Add(world[currentNode.Row, currentNode.Col]); // this help to determine if found a "better connection" for "lowest" node. double lowset_connection_f = double.MaxValue; List<Node> connections = GetConnections(currentNode); //the lowest connection by f (TotalEstimateCost) foreach(Node connection in connections) { if (closeSet.Contains(connection)) continue; // tentative_g_score is used to check if we need to update the neightbor's state. int tentative_g_score = currentNode.CostSoFar + 1; //The problem most likely to be here: if (tentative_g_score > lowset_connection_f) break; lowset_connection_f = tentative_g_score; if(openSet.Contains(connection)) { if(connection.CostSoFar>tentative_g_score) { connection.Father = currentNode; connection.CostSoFar = tentative_g_score; connection.EstimateCost = heuristic.Estimate(connection); openSet.UpdatePriotity(connection, connection.TotalEstimateCost); } } else // not in the open list = undiscovered cell { connection.Father = currentNode; connection.CostSoFar = tentative_g_score; connection.EstimateCost = heuristic.Estimate(connection); openSet.Enqeue(new HeapItem(connection, connection.TotalEstimateCost)); } } } } return null;//path not found }
|
תודה רבה רבה מראש לעוזרים
נ.ב-בNode עשיתי העמסת אופרטורים, ככה שסימני השוואה בעצם משווים עפ"י הערך f.