shortcut.cpp

CRC循环冗余编码程序实现

//////////////////////////////////////////////////////////////////////
// Amit's Path-finding (A*) code.
//
// The main items of interest in my code are:
// 
// 1. I'm using a hexagonal grid instead of a square grid.  Since A*
//    on a square grid works better with the "Manhattan" distance than with
//    straight-line distance, I wrote a "Manhattan" distance on a hexagonal
//    grid.  I also added in a penalty for paths that are not straight
//    lines.  This makes lines turn out straight in the simplest case (no
//    obstacles) without using a straight-line distance function (which can
//    make the path finder much slower).
//
//    To see the distance function, search for UnitMovement and look at
//    its 'dist' function.
//
// 2. The cost function is adjustable at run-time, allowing for a
//    sort of "slider" that varies from "Fast Path Finder" to "Good Path
//    Quality".  (My notes on A* have some ways in which you can use this.)
//
// 3. I'm using a data structure called a "heap" instead of an array
//    or linked list for my OPEN set.  Using lists or arrays, an
//    insert/delete combination takes time O(N); with heaps, an
//    insert/delete combination takes time O(log N).  When N (the number of
//    elements in OPEN) is large, this can be a big win.  However, heaps
//    by themselves are not good for one particular operation in A*.
//    The code here avoids that operation most of the time by using
//    a "Marking" array.  For more information about how this helps
//    avoid a potentially expensive operation, see my Implementation
//    Nodes in my notes on A*.
//////////////////////////////////////////////////////////////////////

#include "Path.h"

// 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.
// It also stores 'f' values for each space on the map.  These are used
// to determine whether something is in OPEN or not.  It stores 'g'
// values to determine whether costs need to be propagated down.
struct Marking
{
    HexDirection direction:4;    // !DirNone means OPEN || CLOSED
    int f:14;                    // >= 0 means OPEN
    int g:14;                    // >= 0 means OPEN || CLOSED
    Marking(): direction(DirNone), f(-1), g(-1) {}
};
static MapArray<Marking>& mark = *(new MapArray<Marking>(Marking()));

// 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 = 6;

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) {}
    ~Node() {}
};

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 );
}

// 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 class that implements A*.  I take a map, two points
// (A and B), and then output the path in the `path' vector, when
// find_path is called.
template <class Heuristic>
struct AStar
{
    PathStats stats;
    Heuristic& heuristic;
    // Remember which nodes are in the OPEN set
    Container open;
    // Remember which nodes we visited, so that we can clear the mark array
    // at the end.  This is the 'CLOSED' set plus the 'OPEN' set.
    Container visited;
    Map& map;
    HexCoord A, B;
    
    AStar( Heuristic& h, Map& m, HexCoord a, HexCoord b )
        : heuristic(h), map(m), A(a), B(b) {}
    ~AStar();

    // Main function:
    void find_path( vector<HexCoord>& path );

    // Helpers:
    void propagate_down( Node H );
    Container::iterator find_in_open( HexCoord h );
    inline bool in_open( const HexCoord& h )
    {
        return mark.data[h.m][h.n].f != -1;
    }
};

template<class Heuristic>
AStar<Heuristic>::~AStar()
{
    for( int m = 1; m <= Map::MSize; ++m )
        for( int n = 1; n <= Map::NSize; ++n )
            dirs.data[m][n] = mark.data[m][n].direction;
    
    // 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].direction = DirNone;
        mark.data[h.m][h.n].f = -1;
        mark.data[h.m][h.n].g = -1;
    }
    for( Container::iterator v = visited.begin(); v != visited.end(); ++v )
    {
        HexCoord h = (*v).h;
        mark.data[h.m][h.n].direction = DirNone;
        mark.data[h.m][h.n].g = -1;
        assert( !in_open( h ) );
    }
}

template <class Heuristic>
Container::iterator AStar<Heuristic>::find_in_open( HexCoord hn )
{
    // Only search for this node if we know it's in the OPEN set
    if( Map::valid(hn) && in_open(hn) ) 
    {
        for( Container::iterator i = open.begin(); i != open.end(); ++i )
        {
            stats.nodes_searched++;
            if( (*i).h == hn )
                return i;
        }
    }
    return open.end();
}

// This is the 'propagate down' stage of the algorithm, which I'm not
// sure I did right.
template <class Heuristic>
void AStar<Heuristic>::propagate_down( Node H )
{
    // Keep track of the nodes that we still have to consider
    Container examine;
    while( !examine.empty() )
    {
        // Remove one node from the list
        Node N = examine.back();
        examine.pop_back();

        // Examine its neighbors
        for( int dir = 0; dir < 6; ++dir )
        {
            HexDirection d = HexDirection(dir);
            HexCoord hn = Neighbor( N.h, d );
            if( in_open(hn) )
            {
                // This node is in OPEN                
                int new_g = N.gval + heuristic.kost( map, N.h, d, hn );

                // Compare this `g' to the stored `g' in the array
                if( new_g < mark.data[hn.m][hn.n].g )
                {
                    Container::iterator i = find_in_open( hn );
                    assert( i != open.end() );
                    assert( mark.data[hn.m][hn.n].g == (*i).gval );
                    
                    // Push this thing UP in the heap (only up allowed!)
                    (*i).gval = new_g;
                    push_heap( open.begin(), i+1, comp );

                    // Set its direction to the parent node
                    mark.data[hn.m][hn.n].g = new_g;
                    mark.data[hn.m][hn.n].f = new_g + (*i).hval;
                    mark.data[hn.m][hn.n].direction = ReverseDirection(d);
                        
                    // Now reset its parent 
                    examine.push_back( (*i) );
                }
                else
                {
                    // The new node is no better, so stop here
                }
            }
            else
            {
                // Either it's in closed, or it's not visited yet
            }
        }
    }
}

template <class Heuristic>
void AStar<Heuristic>::find_path( vector<HexCoord>& path )
{
    Node N;
    {
        // insert the original node
        N.h = A;
        N.gval = 0;
        N.hval = heuristic.dist(map,A,B);
        open.push_back(N);
        mark.data[A.m][A.n].f = N.gval+N.hval;
        mark.data[A.m][A.n].g = N.gval;
        stats.nodes_added++;
    }

    // * Things in OPEN are in the open container (which is a heap),
    //   and also their mark[...].f value is nonnegative.
    // * Things in CLOSED are in the visited container (which is unordered),
    //   and also their mark[...].direction value is not DirNone.

    // While there are still nodes to visit, visit them!
    while( !open.empty() )
    {
        get_first( open, N );
        mark.data[N.h.m][N.h.n].f = -1;
        visited.push_back( N );
        stats.nodes_removed++;
        
        // If we're at the goal, then exit
        if( N.h == B )
            break;

        // If we've looked too long, then exit
        if( stats.nodes_removed >= heuristic.abort_path )
        {
            // Select a good element of OPEN
            for( Container::iterator i = open.begin(); i != open.end(); ++i )
            {
                if( (*i).hval*2 + (*i).gval < N.hval*2 + N.gval )
                    N = *i;
            }
            
            B = N.h;
            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+N.h.n) % 2 == 0 )
            directions = directions1;
        else
            directions = directions2;

        // Look at your neighbors.
        for( int dci = 0; dci < 6; ++dci )
        {
            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) )