Note: There is both code and timing info to look at here.
Hello Steve: Here's my A* code! :) I'm using a heap for the open list instead of a list or array, as many people do, and as I mentioned before, I'm doing this with a hexagonal grid instead of a square one. About the .h files: stl.h and stack.h come from STL (C++ standard library). Notion and Figment are for my OS/2 window class library, for bitmaps and rectangles and colors and so forth. HexCoord defines HexNeighbor and the HexDirection enumeration. (Also, HexCoord is a structure with m and n fields, both int. It represents a hexagonal coordinate.) Unit doesn't do anything for this particular module. Map is used to find the terrain for any spot on the map. (The header files are all specific to my game.) Path.h just declares the one function exported by this module: Astar. - Amit
The A* Algorithm ================ #include "std.h" #include "stl.h" #include <stack.h> #include "Notion.h" #include "Figment.h" #include "HexCoord.h" #include "Unit.h" #include "Map.h" #include "Path.h" // Path_div is used to modify the heuristic. The lower the number, // the higher the heuristic value. This gives us worse paths, but // it finds them faster. This is a variable instead of a constant // so that I can adjust this dynamically, depending on how much CPU // time I have. The more CPU time there is, the better paths I should // search for. int path_div = 8; #define MAXIMUM_PATH_LENGTH 100000 // The mark array marks directions on the map. The direction points // to the spot that is the previous spot along the path. By starting // at the end, we can trace our way back to the start, and have a path. static MapArraymark(DirNone); struct Node { HexCoord h; // location on the map, in hex coordinates int gval; // g in A* represents how far we've already gone int hval; // h in A* represents an estimate of how far is left Node(): h(0,0), gval(0), hval(0) {} }; bool operator < ( const Node& a, const Node& b ) { // To compare two nodes, we compare the `f' value, which is the // sum of the g and h values. return (a.gval+a.hval) < (b.gval+b.hval); } bool operator == ( const Node& a, const Node& b ) { // Two nodes are equal if their components are equal return (a.h == b.h) && (a.gval == b.gval ) && (a.hval == b.hval ); } inline HexDirection ReverseDirection( HexDirection d ) { // With hexagons, I'm numbering the directions 0 = N, 1 = NE, // and so on (clockwise). To flip the direction, I can just // add 3, mod 6. return HexDirection( ( 3+int(d) ) % 6 ); } inline int dist( Map& m, HexCoord a, HexCoord b ) { // The **Manhattan** distance is what should be used in A*'s heuristic // distance estimate, *not* the straight-line distance. This is because // A* wants to know the estimated distance for its paths, which involve // steps along the grid. (Of course, if you assign 1.4 to the cost of // a diagonal, then you should use a distance function close to the // real distance.) // Here I compute a ``Manhattan'' distance for hexagons. Nifty, eh? int a1 = a.m*2; int a2 = a.n*2-(a.m%2)-2*(a.m/2); int a3 = -a1-a2; int b1 = b.m*2; int b2 = b.n*2-(b.m%2)-2*(b.m/2); int b3 = -b1-b2; // 2*D/path_div lets me scale the value. Scaling is nice because you // can adjust the accuracy/speed tradeoff. If you want a faster // search, you can get an approximate answer. return 2*(abs(a1-b1)+abs(a2-b2)+abs(a3-b3))/path_div; } inline int kost( Map& m, HexCoord a, HexDirection d, HexCoord b ) { // This is the cost of moving one step. To get completely accurate // paths, this must be greater than or equal to the change in the // distance function when you take a step. Terrain t = m.terrain(b); // No walking through walls! if( t == Wall || t == Tower ) return MAXIMUM_PATH_LENGTH; // I take the difference in altitude and use that as a cost int da = (m.altitude(b)-m.altitude(a)+ALTITUDE_SCALE/2)/ALTITUDE_SCALE; // Roads are faster int rd = int(t == Road); return (2-rd) + (da>0?da:0); } // greater(Node) is an STL thing to create a 'comparison' object out of // the greater-than operator, and call it comp. typedef vector(Node) Container; greater(Node) comp; // I'm using a priority queue implemented as a heap. STL has some nice // heap manipulation functions. (Look at the source to `priority_queue' // for details.) I didn't use priority_queue because later on, I need // to traverse the entire data structure to update certain elements; the // abstraction layer on priority_queue wouldn't let me do that. inline void get_first( Container& v, Node& n ) { n = v.front(); pop_heap( v.begin(), v.end(), comp ); v.pop_back(); } // Here's the algorithm. I take a map, two points (A and B), and then // output the path in the `path' vector. void AStar( Map& map, HexCoord A, HexCoord B, vector(int)& path ) { Node N; Container open; { // insert the original node N.h = A; N.gval = 0; N.hval = dist(map,A,B); open.push_back(N); } // Remember which nodes we visited, so that we can clear the mark array // at the end. Container visited; // While there are still nodes to visit, visit them! while( !open.empty() ) { get_first( open, N ); visited.push_back( N ); // If we're at the goal, then exit if( N.h == B ) break; // Every other column gets a different order of searching dirs // (Alternatively, you could pick one at random). I don't want // to be too biased by my choice of order in which I look at the // neighboring grid spots. int directions1[6] = {0,1,2,3,4,5}; int directions2[6] = {5,4,3,2,1,0}; int *directions; if( N.h.m % 2 == 0 ) directions = directions1; else directions = directions2; // Look at your neighbors. for( int dci = 0; dci < 6; dci++ ) { #if 0 { // Random permutation of directions int i = random(6-dci); swap( directions[dci+i], directions[dci] ); } #endif HexDirection d = HexDirection(directions[dci]); HexCoord hn = Neighbor( N.h, d ); // If it's off the end of the map, then don't keep scanning if( !map.valid(hn) ) continue; int k = kost(map,N.h,d,hn); Node N2; N2.h = hn; N2.gval = N.gval + k; N2.hval = dist( map, hn, B ); // If this spot (hn) hasn't been visited, its mark is DirNone if( mark.data[hn.m][hn.n] == DirNone ) { // The space is not marked mark.data[hn.m][hn.n] = ReverseDirection(d); open.push_back( N2 ); push_heap( open.begin(), open.end(), comp ); } else { // Search for hn in open Container::iterator find1 = open.end(); for( Container::iterator i = open.begin(); i != open.end(); i++ ) if( (*i).h == hn ) { find1 = i; break; } // if found, call it N3 if( find1 != open.end() ) { Node N3 = *find1; if( N3.gval > N2.gval ) { mark.data[hn.m][hn.n] = ReverseDirection(d); // Replace N3 with N2 in the open list Container::iterator last = open.end() - 1; *find1 = *last; *last = N2; push_heap( open.begin(), open.end(), comp ); } } } } } if( N.h == B && N.gval < MAXIMUM_PATH_LENGTH ) { // We have found a path, so let's copy it into `path' HexCoord h = B; while( h != A ) { HexDirection dir = mark.data[h.m][h.n]; path.push_back( int( ReverseDirection( dir ) ) ); h = Neighbor( h, dir ); } // path now contains the directions the unit must travel .. backwards // (like a stack) } else { // No path } // Erase the mark array, for all items in open or visited for( Container::iterator o = open.begin(); o != open.end(); o++ ) { HexCoord h = (*o).h; mark.data[h.m][h.n] = DirNone; } for( Container::iterator v = visited.begin(); v != visited.end(); v++ ) { HexCoord h = (*v).h; mark.data[h.m][h.n] = DirNone; } }
Timing: I have a few measurements of my A* implementation on a 486/66. They're not very good, because they're running within a multithreaded program. I guess I should separate the map from the OS/2 windowing code, so that I can run a better benchmark with no graphics or multithreading overhead. :) In the tables, Best means the heuristic is a strict underestimate. (The heuristic just returns the distance assuming that all the terrain is flat.) Approx1, Approx2, and Fast multiply the heuristic by 2, 3, and 4, respectively. The higher heuristics make A* spend less time searching, but they can lead to worse paths. I wanted to measure the effect of this. I did some measurements for A* on my small 32x24 hexagonal map. I've been trying things out to see how well A* does on varying terrain; I haven't built up a lot of obstacles yet. (I'll do that later and let you know how it goes.) Best Approx1 Approx2 Fast ---- ------- ------- ---- 5.26 4.83 3.17 0.37 These are times in seconds to compute paths for 100 objects to positions all over the map, on a 486/66. So in the best-path case, it takes 53 milliseconds to calculate the path, and in the fastest approximation, it takes 3.7 milliseconds. I also wanted to compare the quality of the path for each level of approximation. Best App1 App2 Fast ---- ---- ---- ---- A 34 82 34 82 34 82 32 91 B 27 66 27 66 27 66 28 69 C 13 33 13 33 13 34 12 42 D 24 65 24 65 24 65 23 73 A+ 34 75 34 75 34 81 21 90 B+ 27 65 27 65 27 66 28 68 C+ 13 33 13 34 13 34 12 42 D+ 24 63 24 65 24 64 23 71 A, B, C, and D are four positions on the map. The + versions are measured with some roads on the map. The first number in each column is the number of steps taken; the second number is the amount of time the soldier is walking (taking into account slower movement uphill). I told A* to try to minimize the walking time, not the steps. Since my "Fast" approximation doesn't go out of its way to look for roads, it gives noticably worse paths when roads are involved. On the other hand, if you look at the time it takes to calculate, you see it's very fast! The paths are 10 to 20% worse than those given by "Best", but it runs much much faster. This is good news! If I need to reduce CPU usage, I can switch to "Fast" (or "Faster", "Fastest", etc.) without making my paths much worse. I also looked at the number of grid spots the A* algorithm examined: Best App1 App2 Fast ---- ---- ---- ---- A 637 592 437 129 B 461 429 335 100 C 206 172 115 64 D 489 462 426 122 A+ 595 518 411 129 B+ 477 410 256 100 C+ 209 188 113 64 D+ 490 462 399 152 These numbers vary each time you search, depending on the random paths that I search. These numbers and the timings tell me that I should experiment with something between "App2" and "Fast". I might be able to get pretty good paths while still being fast. I then looked at the average number of grid spots searched per step taken. I thought this might be useful for comparing A* to the step-by-step algorithms. no roads roads -------- ----- Best 18.0 17.9 App1 16.4 15.9 App 213.0 11.7 Fast 4.6 4.9 So in the "Fast" code, it analyzes less than 5 squares for every step. Most of the numbers suggest that having roads makes it possible to search less every step; I suspect this may be due to the algorithm having a "guide" that it can follow -- the road looks better than the surrounding terrain, so it searches less of the surrounding terrain. (In the "Fast" code, however, roads are not considered very well, so they do not help a lot.)