|
|
|
This thread is locked; no one can reply to it.
|
| Astar |
|
Ariesnl
Member #2,902
November 2002
 |
I'm trying to grok Astar pathfinding. Any ideas why and how to improve ? 1std::vector<SCell *> CMap::FindPath(int a_nStartX, int a_nStartY,int a_nEndX, int a_nEndY)
2{
3 bool blPathFound = false;
4 std::vector<SCell *> ResultPath;
5 ClearAstar(); // clear astar values
6 SCell * pEndPath = NULL; // pointer to end of path
7 SCell * pCurrent = &(m_vInternalMap[a_nStartX][a_nStartY]); // set current pointer to start of path
8 SCell * pStartPath = pCurrent; // pointer to start of path
9 pCurrent->m_dF = 0; // F cost of start tile is 0
10 m_lstOpenList.push_back(pCurrent); // push to open list
11
12 while ( (!m_lstOpenList.empty()) && (!blPathFound)) // while open list not empty and no path is found
13 {
14 pCurrent = m_lstOpenList.front(); // get the first/next node
15 m_lstOpenList.pop_front(); // remove first node from list
16 m_lstClosedList.push_back(pCurrent); // push note to closed list
17
18 std::vector<SCell *> vSuccessors; // get the possible successors
19 vSuccessors = GetAdjectend(pCurrent->m_nX, pCurrent->m_nY);
20
21 for (size_t i=0; i < vSuccessors.size(); i++) // loop through each successor
22 {
23 SCell * pSuc = vSuccessors[i];
24 if ((pSuc->m_nX == a_nEndX) && (pSuc->m_nY == a_nEndY) && (!blPathFound)) // path found, terminate !
25 {
26 pSuc->m_pParent = pCurrent;
27 pEndPath = pSuc;
28 blPathFound = true;
29 }
30 else if (! IsInClosed(pSuc)) // ignore if in closed
31 {
32 if (IsInOpen(pSuc)) // if in open list, see what path is shortest
33 {
34 int H = abs(a_nEndX - pSuc->m_nX)+ abs(a_nEndY - pSuc->m_nY);
35 double dCurF;
36 if (i%2 == 0)
37 {
38 dCurF = pCurrent->m_dF + (pSuc->m_nTraverseCost * 1.4) + H;
39 }
40 else
41 {
42 dCurF = pCurrent->m_dF + pSuc->m_nTraverseCost + H;
43 }
44
45 if (dCurF < pSuc->m_dF) // shorter path, update F and Parent
46 {
47 pSuc->m_dF = dCurF;
48 pSuc->m_pParent = pCurrent; // set successor parent to current node
49 }
50
51 }
52 else // if not in open list, calculate F and add it to the open list
53 {
54 int H = abs(a_nEndX - pSuc->m_nX)+ abs(a_nEndY - pSuc->m_nY);
55 if (i%2 == 0)
56 {
57 pSuc->m_dF = pCurrent->m_dF + (pSuc->m_nTraverseCost * 1.4) + H;
58 }
59 else
60 {
61 pSuc->m_dF = pCurrent->m_dF + pSuc->m_nTraverseCost + H;
62 }
63
64 pSuc->m_pParent = pCurrent; // set successor parent to current node
65 m_lstOpenList.push_back(pSuc);
66 m_lstOpenList.sort(FSort);
67 }
68 }
69 }
70 }
71
72
73 if (blPathFound) // build the path
74 {
75 SCell * pCell = pEndPath;
76
77 while ((pCell != pStartPath)&&(pCell != NULL))
78 {
79 ResultPath.push_back(pCell);
80 pCell = pCell->m_pParent;
81 }
82 ResultPath.push_back(pCell);
83 }
84
85 return ResultPath;
86}
Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard) |
|
Edgar Reynaldo
Major Reynaldo
May 2007
 |
Oh for the love of m_pHungary! I don't see anywhere you ever add anything to the closed list. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
|
Ariesnl
Member #2,902
November 2002
|
Line 16 But I think I found the main problem.. seems to work now.. Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard) |
|
Elias
Member #358
May 2000
|
Ariesnl said: but can it be done more efficient ? Instead of sorting the open list every time you add something use a priority queue instead. Also for the closed list, use a set (if you are using something else currently). As always the best way to optimize is looking at a profiling output. -- |
|
|
