A* algorithm needs fixing
GrantG

I made a simple A* path finding algorithm, but it i really messed up and only finds the right path sometimes. I'll post the code since there isn't a lot.

1void AddTile(Tile *tile, bool addToOpenList = true)
2{
3 if(open && !tile->blocked)
4 {
5 if(find(openList.begin(), openList.end(), tile) == openList.end())
6 {
7 openList.push_back(tile);
8 }
9 }
10 else if(!tile->blocked)
11 {
12 if(find(closedList.begin(), closedList.end(), tile) == closedList.end())
13 {
14 closedList.push_back(tile);
15 tile->pathMark = true;
16 }
17 }
18}
19 
20void FindPath(int startX, int startY, int endX, int endY)
21{
22 bool pathFound = false;
23 int currentX = startX, currentY = startY;
24 AddTile(GetTile(startX, startY), false);
25 GetTile(endX, endY)->end = true;
26 
27 while(!pathFound)
28 {
29 //add the tiles around the current tile to check them
30 if(GetTile(currentX - 1, currentY)) AddTile(GetTile(currentX - 1, currentY));
31 if(GetTile(currentX, currentY - 1)) AddTile(GetTile(currentX, currentY - 1));
32 if(GetTile(currentX + 1, currentY)) AddTile(GetTile(currentX + 1, currentY));
33 if(GetTile(currentX, currentY + 1)) AddTile(GetTile(currentX, currentY + 1));
34 vector<Tile *>::iterator it = openList.begin();
35 int currentLow = 1000000;
36 Tile *currentTile = NULL;
37 //find the tile with the lowest F score
38 while(it != openList.end())
39 {
40 (*it)->h = 32 * (abs((*it)->x / 32 - endX) + abs((*it)->y / 32 - endY));
41 (*it)->g = closedList.size() * 32;
42 (*it)->f = (*it)->h + (*it)->g;
43 (*it)->checked = true;
44 //check if following this path would be faster
45 if((*it)->f < currentLow)
46 {
47 currentLow = (*it)->f;
48 currentTile = (*it);
49 }
50 it++;
51 }
52 //add the tile to the closed list
53 AddTile(currentTile, false);
54 currentX = currentTile->x / 32;
55 currentY = currentTile->y / 32;
56 //check if the tile we just added is the destination
57 if(currentTile->x / 32 == endX && currentTile->y / 32 == endY) pathFound = true;
58 }
59}

I realize this isn't very optimized, I just want it to work before I try speeding it up. The main problem is that it only makes paths that look like right angles, and sometimes it doesn't work at all when it meets blocked tiles.

EDIT:
Ugh, I guess I should change this so it's more like a linked list where the tiles have parents. I'm not sure how I would do the search though, would I just keep going through the whole list and adding more tiles to check which way it the shortest?

Kevin Adrian

Try the following code 

int
  tempx = (*it)->x / 32 - endX,
  tempy = (*it)->y / 32 - endY;

(*it)->h = tempx*tempx + tempy*tempy;

instead of your own to compute h. When you call
sqrt((*it)->h);
you get the distance between the current tile and the destination tile. But in this case you don't need to do that, especially if you don't want to waste runtime.

GrantG

Heh, thanks for the help, but I've already fixed it. It works perfectly now, but for some reason the search area is larger than it should be.

I suppose I'll post the updated code, the search issue isn't that much of a problem since it's still very fast, but if anyone can point out something I'm doing wrong that would be nice.

1struct Tile
2{
3 Tile *parent;
4 int x, y;
5 int h, g, f;
6 bool blocked;
7 bool onClosedList;
8 bool start, end;
9 bool pathMark;
10 bool checked;
11};
12 
13Tile *GetTile(int x, int y)
14{
15 if(x > -1 && x < 20 && y > -1 && y < 15)
16 {
17 int index = (y * 20) + x;
18 if(index > -1 && index < 300) return &tiles[index];
19 }
20 return NULL;
21}
22 
23void AddTile(Tile *parent, Tile *tile, bool open = true)
24{
25 if(open && !tile->blocked)
26 {
27 if(!tile->onClosedList)
28 {
29 if(find(openList.begin(), openList.end(), tile) != openList.end())
30 {
31 //check if the path if better using that tile
32 if(parent->g + 32 < tile->g)
33 {
34 tile->parent = parent;
35 tile->g = parent->g + 32;
36 tile->f = tile->h + tile->g;
37 }
38 }
39 else
40 {
41 tile->h = 32 * (abs(tile->x / 32 - endX) + abs(tile->y / 32 - endY));
42 tile->g = closedList.size() * 32;
43 tile->f = tile->h + tile->g;
44 tile->parent = parent;
45 tile->checked = true;
46 openList.push_back(tile);
47 }
48 }
49 }
50 else if(!tile->blocked)
51 {
52 if(find(closedList.begin(), closedList.end(), tile) == closedList.end())
53 {
54 tileAdded = true;
55 tile->onClosedList = true;
56 closedList.push_back(tile);
57 }
58 }
59}
60 
61void MarkPath(Tile *dest)
62{
63 if(dest->parent != NULL)
64 {
65 dest->pathMark = true;
66 MarkPath(dest->parent);
67 }
68}
69 
70void FindPath(int x, int y, int x2, int y2)
71{
72 if(GetTile(x2, y2)->blocked || GetTile(x, y)->blocked) return;
73 log << "Start: " << clock() << endl;
74 bool pathFound = false;
75 startX = x;
76 startY = y;
77 endX = x2;
78 endY = y2;
79 int currentX = startX, currentY = startY;
80 AddTile(NULL, GetTile(startX, startY));
81 
82 Tile *currentTile = NULL;
83 while(1)
84 {
85 //find the tile with the lowest F score
86 vector<Tile *>::iterator it = openList.begin();
87 int currentLow = 1000000;
88 tileAdded = false;
89 while(it != openList.end())
90 {
91 if(step) DrawTiles();
92 if((*it)->f < currentLow && (*it) != currentTile && !(*it)->onClosedList)
93 {
94 currentLow = (*it)->f;
95 currentTile = (*it);
96 }
97 it++;
98 }
99 //add the tile to the closed list
100 AddTile(NULL, currentTile, false);
101 //if the tile was not added, that means that a path could not be found
102 if(!tileAdded) return;
103 currentX = currentTile->x / 32;
104 currentY = currentTile->y / 32;
105 //check if the tile we just added is the destination
106 if(currentTile->x / 32 == endX && currentTile->y / 32 == endY) break;
107 //add the tiles around the current tile to check them
108 if(GetTile(currentX - 1, currentY) != NULL) AddTile(GetTile(currentX, currentY), GetTile(currentX - 1, currentY));
109 if(GetTile(currentX, currentY - 1) != NULL) AddTile(GetTile(currentX, currentY), GetTile(currentX, currentY - 1));
110 if(GetTile(currentX + 1, currentY) != NULL) AddTile(GetTile(currentX, currentY), GetTile(currentX + 1, currentY));
111 if(GetTile(currentX, currentY + 1) != NULL) AddTile(GetTile(currentX, currentY), GetTile(currentX, currentY + 1));
112 //this stuff is just here for stepping through the process
113 if(step) readkey(), clear_keybuf();
114 if(key[KEY_ENTER]) step = false;
115 }
116 MarkPath(closedList.back());
117 log << "End: " << clock() << endl;
118}

Thread #590185. Printed from Allegro.cc