tilemap.h

游戏开发数据结构Data Structures for Game Programmers

    {
        // get the new coordinates
        int newx = p_x + DIRECTIONTABLE[p_direction][0]; 
        int newy = p_y + DIRECTIONTABLE[p_direction][1];

        // check to see if the cell is in bounds.
        if( newx < 0 || newx >= m_tiles.Width() ||
            newy < 0 || newy >= m_tiles.Height() )
            return false;

        // check to see if the path is blocked or not.
        if( m_tilemap.Get( newx, newy ).m_blocked == true )
            return false;

        // check to see if there is a person blocking the way
        if( m_tilemap.Get( newx, newy ).m_person != 0 )
            return false;

        // check to see if there in an item blocking the way
        if( m_tilemap.Get( newx, newy ).m_item != 0 )
        {
            // some items can block, others can't
            if( m_tilemap.Get( newx, newy ).m_item->CanBlock() == true )
                return false;
        }

        return true;
    }


// -------------------------------------------------------
// Name:        Move
// Description: Moves the given person in the given
//              direction
// -------------------------------------------------------
    void Move( Person* p_person, int p_direction )
    {
        // get the new coordinates
        int newx = p_person->GetX() + DIRECTIONTABLE[p_direction][0]; 
        int newy = p_person->GetY() + DIRECTIONTABLE[p_direction][1];

        // make sure the player can move
        if( CanMove( p_person, p_direction ) == true )
        {
            // move the person to the new cell
            m_tilemap.Get( newx, newy ).m_person = p_person;

            // clear the person pointer in the old cell
            m_tilemap.Get( p_person->GetX(), p_person->GetY() ).m_person = 0;

            // set the new x, y, and cell variables
            p_person->SetX( newx );
            p_person->SetY( newy );
            p_person->SetCell( GetCell( newx, newy ) );
        }
    }


// -------------------------------------------------------
// Name:        GetItem
// Description: Gets a pointer to the item in the given
//              cell
// -------------------------------------------------------
    Item* GetItem( int p_cell )
    {
        // check to see if the cell is in bounds first
        if( p_cell >= GetNumberOfCells() || p_cell < 0 )
            return 0;

        return m_tilemap.m_array[p_cell].m_item;
    }


// -------------------------------------------------------
// Name:        SetItem
// Description: Sets the item in the given cell.
// -------------------------------------------------------
    void SetItem( int p_cell, Item* p_item )
    {
        // check to see if the cell is in bounds first
        if( p_cell >= GetNumberOfCells() || p_cell < 0 )
            return;

        m_tilemap.m_array[p_cell].m_item = p_item;
    }

    
// -------------------------------------------------------
// Name:        GetPerson
// Description: Gets a pointer to the person in the given
//              cell
// -------------------------------------------------------
    Person* GetPerson( int p_cell )
    {
        // check to see if the cell is in bounds first
        if( p_cell >= GetNumberOfCells() || p_cell < 0 )
            return 0;

        return m_tilemap.m_array[p_cell].m_person;
    }


// -------------------------------------------------------
// Name:        SetPerson
// Description: sets the person in the given cell.
// -------------------------------------------------------
    void SetPerson( int p_cell, Person* p_person )
    {
        // check to see if the cell is in bounds first
        if( p_cell >= GetNumberOfCells() || p_cell < 0 )
            return;

        m_tilemap.m_array[p_cell].m_person = p_person;
    }


// -------------------------------------------------------
// Name:        GetCellNumber
// Description: Gets the number of the cell in the
//              given direction
// -------------------------------------------------------
    int GetCellNumber( int p_cell, int p_direction )
    {
        int x, y;
    
        // calculate the x and y coords of the current cell first
        y = p_cell / m_tiles.Width();
        x = p_cell - (y * m_tiles.Width());
    
        // now calculate the new coordinates
        x = x + DIRECTIONTABLE[p_direction][0];
        y = y + DIRECTIONTABLE[p_direction][1];

        // check to see if the cell is out of bounds
        if( x < 0 || x >= m_tiles.Width() ||
            y < 0 || y >= m_tiles.Height() )
        {
            return -1;
        }

        // return the cell number
        return GetCell( x, y );
    }

    
// -------------------------------------------------------
// Name:        GetNumberOfCells
// Description: Gets the number of cells in the map
// -------------------------------------------------------
    int GetNumberOfCells()
    {
        return m_tilemap.Size();
    }


// -------------------------------------------------------
// Name:        GetClosestDirection
// Description: Gets the direction that will move the
//              first person closer to the second person.
// -------------------------------------------------------
    int GetClosestDirection( Person* p_one, Person* p_two )
    {
        // calculate the path between the two persons
        AStar( p_one, p_two );

        int lx, ly, x, y;

        // now follow the path from the goal to the start
        x = p_two->GetX();
        y = p_two->GetY();

        // loop through the path while the current cell
        // isn't the goal.
        while( x != p_one->GetX() || y != p_one->GetY() )
        {
            // save the last coordinates
            lx = x;
            ly = y;

            // calculate the next coordinates
            x = m_tilemap.Get( lx, ly ).m_lastx;
            y = m_tilemap.Get( lx, ly ).m_lasty;

            if( x == -1 || y == -1 )
            {
                // the path is unreachable, so return a random
                // direction.
                // this makes the AI seem frustrated.
                return rand() % 4;
            }
        }


        // the path was reached, so calculate which direction the person
        // needs to move to get closer.
        if( ly < y )
            return 0;
        if( lx > x )
            return 1;
        if( ly > y )
            return 2;
        if( lx < x )
            return 3;

        // if execution reaches this point, you're in trouble.
        // theoretically, this should never get here. This is
        // a good place to add error-detection code.
    }



// =======================================================
//  Pathfinding Functions
// =======================================================

// -------------------------------------------------------
// Name:        ClearCells
// Description: Clears all the pathfinding information
//              for each cell
// -------------------------------------------------------
    void ClearCells()
    {
        int x;
        int y;

        for( x = 0; x < m_tilemap.Width(); x++ )
        {
            for( y = 0; y < m_tilemap.Height(); y++ )
            {
                m_tilemap.Get( x, y ).m_marked = false;
                m_tilemap.Get( x, y ).m_distance = 0.0f;
                m_tilemap.Get( x, y ).m_lastx = -1;
                m_tilemap.Get( x, y ).m_lasty= -1;
            }
        }
    }

// -------------------------------------------------------
// Name:        Heuristic
// Description: Computes the Heuristic for the cell
// -------------------------------------------------------
    float Heuristic( int x, int y, int gx, int gy, int dir )
    {
        x = x + DIRECTIONTABLE[dir][0];
        y = y + DIRECTIONTABLE[dir][1];

        return Distance( x, y, gx, gy );
    }



// -------------------------------------------------------
// Name:        AStar
// Description: calculates the path from one cell to
//              another using the A* pathfinder
// -------------------------------------------------------
    void AStar( Person* p_one, Person* p_two )
    {
        Coordinate c;
        int x, y;
        int ax, ay;
        int dir;
        float distance;

        static Heap<Coordinate> queue( 1024, CompareCoordinates );

        // clear the queue
        queue.m_count = 0;

        // clear the cells first.
        ClearCells();
    
        // enqueue the starting cell in the queue
        c.x = p_one->GetX();
        c.y = p_one->GetY();
        queue.Enqueue( c );

        // start the main loop
        while( queue.m_count != 0 )
        {
            // pull the first cell off the queue and process it.
            x = queue.Item().x;
            y = queue.Item().y;
            queue.Dequeue();

            // make sure the node isn't already marked. If it is, do
            // nothing.
            if( m_tilemap.Get( x, y ).m_marked == false )
            {
                // mark the cell as it is pulled off the queue.
                m_tilemap.Get( x, y ).m_marked = true;

                // quit out if the goal has been reached.
                if( x == p_two->GetX() && y == p_two->GetY() )
                    break;

                // loop through each direction.
                for( dir = 0; dir < 4; dir++ )
                {
                    // retrieve the coordinates of the current adjacent cell
                    ax = x + DIRECTIONTABLE[dir][0];
                    ay = y + DIRECTIONTABLE[dir][1];

                    // check to see if the adjacent cell passable, 
                    // and not marked.
                    // note that the CanMove function will return false
                    // when ax and ay are the goal coordinates, since there
                    // is a person on that cell. Therefore, you need to make
                    // a special exception to allow that cell to be processed.
                    if( ( CanMove( x, y, dir ) &&
                          m_tilemap.Get( ax, ay ).m_marked == false ) ||
                          ( ax == p_two->GetX() && ay == p_two->GetY() ) )
                    {
                        // calculate the distance to get into this cell.
                        distance = m_tilemap.Get( x, y ).m_distance + 1;

                        // check if the node has already been calculated before
                        if( m_tilemap.Get( ax, ay ).m_lastx != -1 )
                        {
                            // the node has already been calculated, see if the
                            // new distance is shorter. If so, update the links.
                            if( distance < m_tilemap.Get( ax, ay ).m_distance )
                            {
                                // the new distance is shorter, update the links
                                m_tilemap.Get( ax, ay ).m_lastx = x;
                                m_tilemap.Get( ax, ay ).m_lasty = y;
                                m_tilemap.Get( ax, ay ).m_distance = distance;

                                // add the cell to the queue.
                                c.x = ax;
                                c.y = ay;
                                c.heuristic = distance + 
                                              Heuristic( x, y, p_two->GetX(), 
                                                         p_two->GetY(), dir );
                                queue.Enqueue( c );
                            }
                        }
                        else
                        {
                            // set the links and the distance
                            m_tilemap.Get( ax, ay ).m_lastx = x;
                            m_tilemap.Get( ax, ay ).m_lasty = y;
                            m_tilemap.Get( ax, ay ).m_distance = distance;

                            // add the cell to the queue.
                            c.x = ax;
                            c.y = ay;
                            c.heuristic = distance + 
                                          Heuristic( x, y, p_two->GetX(), 
                                                     p_two->GetY(), dir );
                            queue.Enqueue( c );
                        }
                    }
                }
            }
        }
    }
};







#endif