Improvements to Amit’s A* Code

Petr Sulla sent me mail with some improvements to my A* code^[1]. I was going to merge his changes into my code, but then realized that I don’t actually use the code anymore (because I’m not working on games at the moment), and I shouldn’t write the code without adequately testing it. So instead I’m posting his notes here. He writes:

In my case it is pretty expensive to calculate the cost and the heuristics (especially the cost). I just doubled the code and calculate the two when they are really needed. This speeded up things from 13 ms to 9 ms (on a 400 MHz PII, 120x120 map, in Delphi) (only the main loop measured)

// remove from here
//            int k = heuristic.kost(map, N.h, d, hn);
//            Node N2;
//            N2.h = hn;
//            N2.gval = N.gval + k;
//            N2.hval = heuristic.dist( map, hn, B );
            // If this spot (hn) hasn't been visited, its mark is DirNone
            if( mark.data[hn.m][hn.n].direction == DirNone )
            {
                // insert here
                int k = heuristic.kost(map, N.h, d, hn);
                Node N2;
                N2.h = hn;
                N2.gval = N.gval + k;
                N2.hval = heuristic.dist( map, hn, B );

                // The space is not marked
                mark.data[hn.m][hn.n].direction = ReverseDirection(d);
                mark.data[hn.m][hn.n].f = N2.gval+N2.hval;
                mark.data[hn.m][hn.n].g = N2.gval;
                open.push_back( N2 );
                push_heap( open.begin(), open.end(), comp );
                stats.nodes_added++;
            }
            else
            {                
                // We know it's in OPEN or CLOSED...
                if( in_open(hn) )
                {
                    // and also here
                    int k = heuristic.kost(map, N.h, d, hn);
                    Node N2;
                    N2.h = hn;
                    N2.gval = N.gval + k;
                    N2.hval = heuristic.dist( map, hn, B );

                    // It's in OPEN, so figure out whether g is better
                    if( N2.gval < mark.data[hn.m][hn.n].g )
                    {
                        // Search for hn in open

it’s pretty bad going through the whole priority queue all the time in find_in_open - the algorithm spends there close to 1/4 of time. I implemented the PQ myself, so I added a variable index_in_PQ to the marking array and I update it when reorganizing the heap-based PQ. So my find_in_open is just one access to the marking array, although the reorganizing got a bit slower. Speed improvement from 21 ms to 17 ms (which is now the average time for 1 path on my PII/400 on a 120x120 hexes map)

Endnotes