shortcut.cpp

CRC循环冗余编码程序实现

                continue;

            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 )
            {
                // 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) )
                {
                    // 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
                        Container::iterator find1 = find_in_open( hn );
                        assert( find1 != open.end() );
                        
                        // Replace *find1's gval with N2.gval in the list&map
                        mark.data[hn.m][hn.n].direction = ReverseDirection(d);
                        mark.data[hn.m][hn.n].g = N2.gval;
                        mark.data[hn.m][hn.n].f = N2.gval+N2.hval;
                        (*find1).gval = N2.gval;
                        // This is allowed but it's not obvious why:
                        push_heap( open.begin(), find1+1, comp );
                        // (ask Amit if you're curious about it)

                        // This next step is not needed for most games
                        propagate_down( *find1 );
                    }
                }
            }
        }
    }

    if( N.h == B && N.gval < MAXIMUM_PATH_LENGTH )
    {
        stats.path_cost = N.gval;
        // 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].direction;
            path.push_back( h );
            h = Neighbor( h, dir );
            stats.path_length++;
        }
        path.push_back( A );
        // path now contains the hexes in which the unit must travel ..
        // backwards (like a stack)
    }
    else
    {
        // No path
    }

    stats.nodes_left = open.size();
    stats.nodes_visited = visited.size();
}

////////////////////////////////////////////////////////////////////////
// Specific instantiations of A* for different purposes

// UnitMovement is for moving units (soldiers, builders, firefighters)
struct UnitMovement
{
    HexCoord source;
    Unit* unit;
    int abort_path;
    
    inline static int dist( const HexCoord& a, const 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 = 2*a.m;
        int a2 =  2*a.n+a.m%2 - a.m;
        int a3 = -2*a.n-a.m%2 - a.m; // == -a1-a2
        int b1 = 2*b.m;
        int b2 =  2*b.n+b.m%2 - b.m;
        int b3 = -2*b.n-b.m%2 - b.m; // == -b1-b2

        // One step on the map is 10 in this function
        return 5*max(abs(a1-b1), max(abs(a2-b2), abs(a3-b3)));
    }

    inline int dist( Map& m, const HexCoord& a, const HexCoord& b )
    {
        double dx1 = a.x() - b.x();
        double dy1 = a.y() - b.y();
        double dx2 = source.x() - b.x();
        double dy2 = source.y() - b.y();
        double cross = dx1*dy2-dx2*dy1;
        if( cross < 0 ) cross = -cross;

        return dist( a, b ) + int(cross/20000);
    }
    
    inline int kost( Map& m, const HexCoord& a, 
                     HexDirection d, const HexCoord& b, int pd = -1 )
    {
        // 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.

        if( pd == -1 ) pd = path_div;
        
        // Check for neighboring moving obstacles
        int occ = m.occupied_[b];
        if( ( occ != -1 && m.units[occ] != unit ) &&
            ( !m.units[occ]->moving() || ( source == a && d != DirNone ) ) )
                return MAXIMUM_PATH_LENGTH;

        // Roads are faster (twice as fast), and cancel altitude effects
        Terrain t1 = m.terrain(a);
        Terrain t2 = m.terrain(b);
        //        int rd = int((t2==Road||t2==Bridge)&&(t1==Road||t2==Bridge));
        // It'd be better theoretically for roads to work only when both
        // hexes are roads, BUT the path finder works faster when
        // it works just when the destination is a road, because it can
        // just step onto a road and know it's going somewhere, as opposed
        // to having to step on the road AND take another step.
        int rd = int(t2==Road || t2==Bridge);
        int rdv = ( 5 - 10 * rd ) * (pd - 3) / 5;
        // Slow everyone down on gates, canals, or walls
        if( t2 == Gate || t2 == Canal )
            rdv += 50;
        if( t2 == Wall )
            rdv += 150;
        // Slow down everyone on water, unless it's on a bridge
        if( t2 != Bridge && m.water(b) > 0 )
            rdv += 30;
        // If there's no road, I take additional items into account
        if( !rd )
        {
            // One thing we can do is penalize for getting OFF a road
            if( t1==Road || t1==Bridge )
                rdv += 15;
            // I take the difference in altitude and use that as a cost,
            // rounded down, which means that small differences cost 0
            int da = (m.altitude(b)-m.altitude(a))/ALTITUDE_SCALE;
            if( da > 0 )
                rdv += da * (pd-3);
        }
        return 10 + rdv;
    }
};

// Some useful functions are exported to be used without the pathfinder

int hex_distance( HexCoord a, HexCoord b )
{
    return UnitMovement::dist( a, b );
}

int movement_cost( Map& m, HexCoord a, HexCoord b, Unit* unit )
{
    UnitMovement um;
    um.unit = unit;
    return um.kost( m, a, DirNone, b, 8 );
}

// BuildingMovement is for drawing straight lines (!)
struct BuildingMovement
{
    HexCoord source;
    int abort_path;
    
    inline int dist( Map& m, const HexCoord& a, const HexCoord& b )
    {
        double dx1 = a.x() - b.x();
        double dy1 = a.y() - b.y();
        double dd1 = dx1*dx1+dy1*dy1;
        // The cross product will be high if two vectors are not colinear
        // so we can calculate the cross product of [current->goal] and
        // [source->goal] to see if we're staying along the [source->goal]
        // vector.  This will help keep us in a straight line.
        double dx2 = source.x() - b.x();
        double dy2 = source.y() - b.y();
        double cross = dx1*dy2-dx2*dy1;
        if( cross < 0 ) cross = -cross;
        return int( dd1 + cross );
    }

    inline int kost( Map& m, const HexCoord& a, 
                     HexDirection d, const HexCoord& b )
    {
        return 0;
    }
};

// Flat Canal movement tries to find a path for a canal that is not too steep
struct FlatCanalPath: public UnitMovement
{
    int kost( Map& m, const HexCoord& a, 
                     HexDirection d, const HexCoord& b )
    {
        // Try to minimize the slope
        int a0 = m.altitude(a);
        int bda = 0;
        for( int dir = 0; dir < 6; ++dir )
        {            
            int da = a0-m.altitude( Neighbor(a,HexDirection(dir)) );
            if( da > bda ) bda = da;
        }
        return 1 + 100*bda*bda;
    }
};

//////////////////////////////////////////////////////////////////////
// These functions call AStar with the proper heuristic object

PathStats FindUnitPath( Map& map, HexCoord A, HexCoord B, 
                        vector<HexCoord>& path, Unit* unit, int cutoff )
{
    UnitMovement um;    
    um.source = A;
    um.unit = unit;
    um.abort_path = cutoff * hex_distance(A,B) / 10;

    AStar<UnitMovement> finder( um, map, A, B );

    // If the goal node is unreachable, don't even try
    if( um.kost( map, A, DirNone, B ) == MAXIMUM_PATH_LENGTH )
    {
        // Check to see if a neighbor is reachable.  This is specific
        // to SimBlob and not something for A* -- I want to find a path
        // to a neighbor if the original goal was unreachable (perhaps it
        // is occupied or unpassable).
        int cost = MAXIMUM_PATH_LENGTH;
        HexCoord Bnew = B;
        for( int d = 0; d < 6; ++d )
        {
            HexCoord hn = Neighbor( B, HexDirection(d) );
            int c = um.kost( map, A, DirNone, hn );
            if( c < cost )
            {
                // This one is closer, hopefully
                Bnew = B;
                cost = c;
            }
        }
        // New goal
        B = Bnew;

        if( cost == MAXIMUM_PATH_LENGTH )
        {
            // No neighbor was good
            return finder.stats;
        }
    }

    finder.find_path( path );
    return finder.stats;
}

PathStats FindBuildPath( Map& map, HexCoord A, HexCoord B,
                         vector<HexCoord>& path )
{
    BuildingMovement bm;
    bm.source = A;

    AStar<BuildingMovement> finder( bm, map, A, B );
    finder.find_path( path );
    return finder.stats;
}

PathStats FindCanalPath( Map& map, HexCoord A, HexCoord B,
                         vector<HexCoord>& path )
{
    FlatCanalPath fcp;
    fcp.source = A;

    AStar<FlatCanalPath> finder( fcp, map, A, B );
    finder.find_path( path );
    return finder.stats;
}