gd15-01.cpp

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

// ============================================================================
//  GD15-01.cpp
//  Minimax Tree Graphical Demonstration.
// ============================================================================
#include "SDLGUI.h"
#include "Queue.h"
#include "Tree.h"
#include <stdlib.h>
#include <time.h>



// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Minimax Tree Graphical Demonstration";
const int WIDTH             = 800;
const int HEIGHT            = 600;
const int ITEMS             = 32;
const int ARIAL             = 0;
const int PILES             = 3;

// ============================================================================
//  Classes
// ============================================================================
class RockState
{
public:

    // constructor, clear everything
    RockState()
    {
        int x;
        for( x = 0; x < PILES; x++ )
            m_rocks[x] = 0;
        m_minimaxValue = -1;
    }

    // the rock data
    int m_rocks[PILES];

    // the minimax value of the state
    int m_minimaxValue;
};

// this is a pair of data; a tree node and the player of the node.
// this data is meant to be enqueued into the queue.
class NodePlayerPair
{
public:
    Tree<RockState>* m_node;
    bool m_max;
};



// ============================================================================
//  Global Variables
// ============================================================================
SDLGUI* g_gui;

int g_delay = 700;
int g_timer;

// the tree of rockstates
Tree<RockState>* g_tree;

// the initial state of the game
RockState g_startingState;

// the iterators.
Tree<RockState>* g_current = 0;

// the tree iterator.
TreeIterator<RockState> g_itr;

// the queue that holds the order in which nodes are processed.
LQueue<NodePlayerPair> g_queue;

// Circles
SDL_Surface* g_blackcircle;
SDL_Surface* g_redcircle;
SDL_Surface* g_rock;

bool g_processing = false;

// ============================================================================
//  Draw Algorithms
// ============================================================================
void DrawRocks( RockState p_state, int p_x, int p_y )
{
    int x;
    int y;
    int z;

    for( x = 0; x < PILES; x++ )
    {
        // draw the boxes around each pile first.
        g_gui->Line( p_x + x * 40, p_y, p_x + x * 40 + 32, p_y, BLACK );
        g_gui->Line( p_x + x * 40, p_y + 80, p_x + x * 40 + 32, p_y + 80, BLACK );
        g_gui->Line( p_x + x * 40, p_y, p_x + x * 40, p_y + 80, BLACK );
        g_gui->Line( p_x + x * 40 + 32, p_y, p_x + x * 40 + 32, p_y + 80, BLACK );

        y = p_y + 64;
        for( z = 0; z < p_state.m_rocks[x]; z++ )
        {
            g_gui->Blit( g_rock, p_x + x * 40, y );
            y -= 16;
        }
    }
}




void DrawNode( Tree<RockState>* p_node, int p_x, int p_y )
{
    static SDL_Surface* text;
    static char number[] = "00";

    // draw the contents of the circle.
    if( p_node->m_data.m_minimaxValue != -1 )
    {
        sprintf( number, "%d", p_node->m_data.m_minimaxValue );
        text = TTF_RenderText_Shaded( g_gui->GetFont(ARIAL), number, BLACK, WHITE );

        g_gui->Blit( text, (g_blackcircle->w - text->w) / 2 + p_x, 
                           (g_blackcircle->h - text->h) / 2 + p_y );
        SDL_FreeSurface( text );
    }

    // draw the circle
    if( g_current == p_node )
        g_gui->Blit( g_redcircle, p_x, p_y );
    else
        g_gui->Blit( g_blackcircle, p_x, p_y );
}



void DrawTree( Tree<RockState>* p_tree, int p_x, int p_y, int p_width )
{
    if( p_tree != 0 )
    {
        DrawNode( p_tree, p_x + (p_width / 2) - 16, p_y);

        int w = p_tree->m_children.Size();
        int w2;
        if( w != 0 )
        {
            w = p_width / w;
            w2 = w / 2;
        }
        int x = p_x;

        // get an iterator for the children.
        DListIterator<Tree<RockState>*> itr = p_tree->m_children.GetIterator();

        for( itr.Start(); itr.Valid(); itr.Forth() )
        {
            DrawTree( itr.Item(), x, p_y + 128, w );
            g_gui->ArrowLine( p_x + (p_width / 2), p_y + 16, 
                              x + w2, p_y + 144, 16, 16, false, true, BLACK );
            x += w;
        }
    }
}


// ============================================================================
//  Tree Calculation
// ============================================================================

// god bless recursion.
Tree<RockState>* CalculateTree( RockState p_state )
{
    int i;
    int rocks;

    // create a new tree node, 
    Tree<RockState>* tree = new Tree<RockState>;
    Tree<RockState>* child = 0;
    RockState state;
    TreeIterator<RockState> itr = tree;

    tree->m_data = p_state;
    

    for( i = 0; i < PILES; i++ )
    {
        for( rocks = 1; rocks <= p_state.m_rocks[i]; rocks++ )
        {
            // create a new state by subtracting rocks from
            // the current pile
            state = p_state;
            state.m_rocks[i] -= rocks;

            // calculate the game tree for the new state.
            child = CalculateTree( state );

            // add the child tree to the current tree.
            itr.AppendChild( child );
        }
    }
    return tree;
}


void MinMax( Tree<RockState>* p_tree, bool p_max )
{
    TreeIterator<RockState> itr = p_tree;

    // create a node/player pair
    NodePlayerPair p;
    p.m_node = p_tree;
    p.m_max = p_max;

    // do a postorder traversal.
    for( itr.ChildStart(); itr.ChildValid(); itr.ChildForth() )
    {
        MinMax( itr.m_childitr.Item(), !p_max );
    }

    g_queue.Enqueue( p );    
}


void CalculateMiniMaxValue( NodePlayerPair p_pair )
{
    // if the node is a leaf node, calculate its heuristic value.
    if( p_pair.m_node->m_children.m_count == 0 )
    {
        if( p_pair.m_max == true )
        {
            p_pair.m_node->m_data.m_minimaxValue = 1;
        }
        else
        {
            p_pair.m_node->m_data.m_minimaxValue = 0;
        }
        return;
    }

    // else the node is not a leaf, so you need to calculate the min or the max
    // of its children.
    int minmax;
    TreeIterator<RockState> itr = p_pair.m_node;

    if( p_pair.m_max == true )
    {
        // max's turn
        itr.ChildStart();
        minmax = itr.ChildItem().m_minimaxValue;
        itr.ChildForth();

        // loop through finding the highest child
        while( itr.ChildValid() )
        {
            if( itr.ChildItem().m_minimaxValue > minmax )
                minmax = itr.ChildItem().m_minimaxValue;
            itr.ChildForth();
        }
    }
    else
    {
        // min's turn
        itr.ChildStart();
        minmax = itr.ChildItem().m_minimaxValue;
        itr.ChildForth();

        // loop through finding the lowest child
        while( itr.ChildValid() )
        {
            if( itr.ChildItem().m_minimaxValue < minmax )
                minmax = itr.ChildItem().m_minimaxValue;
            itr.ChildForth();
        }
    }

    p_pair.m_node->m_data.m_minimaxValue = minmax;
}


// ============================================================================
//  Button Callbacks
// ============================================================================

void GameTree()
{
    if( g_tree != 0 )
        delete g_tree;

    g_tree = CalculateTree( g_startingState );
}


void Up1()
{
    if( g_processing == true )
        return;

    if( g_startingState.m_rocks[0] + 
        g_startingState.m_rocks[1] + 
        g_startingState.m_rocks[2] < 4 )
    {
        g_startingState.m_rocks[0]++;
        GameTree();
    }
}

void Up2()
{
    if( g_processing == true )
        return;

    if( g_startingState.m_rocks[0] + 
        g_startingState.m_rocks[1] + 
        g_startingState.m_rocks[2] < 4 )
    {
        g_startingState.m_rocks[1]++;
        GameTree();
    }
}

void Up3()
{
    if( g_processing == true )
        return;

    if( g_startingState.m_rocks[0] + 
        g_startingState.m_rocks[1] + 
        g_startingState.m_rocks[2] < 4 )
    {
        g_startingState.m_rocks[2]++;
        GameTree();
    }
}

void Down1()
{
    if( g_processing == true )
        return;

    if( g_startingState.m_rocks[0] > 0 )
    {
        g_startingState.m_rocks[0]--;
        GameTree();
    }
}

void Down2()
{
    if( g_processing == true )
        return;

    if( g_startingState.m_rocks[1] > 0 )
    {
        g_startingState.m_rocks[1]--;
        GameTree();
    }
}

void Down3()
{
    if( g_processing == true )
        return;

    if( g_startingState.m_rocks[2] > 0 )
    {
        g_startingState.m_rocks[2]--;
        GameTree();
    }
}



void IteratorReset()
{
    g_current = 0;

    if( g_itr.Valid() )
    {
        g_current = g_itr.m_node;
    }
}


void MiniMax()
{

    // empty the queue;
    while( g_queue.Count() != 0 )
        g_queue.Dequeue();

    // fill the queue with the new minimax data
    MinMax( g_tree, true );

    g_processing = true;
    g_timer = SDL_GetTicks();


    // set the current node pointer to point to the first node.
    g_current = g_queue.Front().m_node;

    // calculate the minimax value of the current node.
    CalculateMiniMaxValue( g_queue.Front() );
}


// ============================================================================
//  Main
// ============================================================================



int main( int argc, char* argv[] )
{
    int x;
    int y;

    srand( time(0) );

    g_startingState.m_rocks[0] = 0;
    g_startingState.m_rocks[1] = 0;
    g_startingState.m_rocks[2] = 0;

    //initialize systems
    SDL_Init( SDL_INIT_VIDEO | SDL_INIT_TIMER );
    TTF_Init();
    g_gui = new SDLGUI( WIDTH, HEIGHT, ITEMS, WHITE );
    SDL_WM_SetCaption( PROGRAM_NAME, 0); 
    g_gui->SetFont( "arial.ttf", ARIAL, 20, TTF_STYLE_NORMAL );


    // load the bmps
    g_blackcircle = SDL_LoadBMP( "scircleblack.bmp" );
    g_redcircle =   SDL_LoadBMP( "scirclered.bmp" );
    g_rock        = SDL_LoadBMP( "rock.bmp" );

    // set the color keys of the BMPs
    SDL_SetColorKey( g_blackcircle, SDL_SRCCOLORKEY, 
                     SDL_MapRGB( g_blackcircle->format, 255, 255, 255 ));
    SDL_SetColorKey( g_redcircle, SDL_SRCCOLORKEY, 
                     SDL_MapRGB( g_redcircle->format, 255, 255, 255 ));
    SDL_SetColorKey( g_rock, SDL_SRCCOLORKEY, 
                     SDL_MapRGB( g_rock->format, 255, 255, 255 ));


    // add the items to the g_gui

    g_gui->AddLabel( 0, 0, "Game:", ARIAL, BLACK, WHITE );

    g_gui->AddButton( 72, 0, "upbuttonup.bmp", "upbuttondown.bmp", " ", ARIAL,
                      BLACK, WHITE, Up1 );
    g_gui->AddButton( 112, 0, "upbuttonup.bmp", "upbuttondown.bmp", " ", ARIAL,
                      BLACK, WHITE, Up2 );
    g_gui->AddButton( 152, 0, "upbuttonup.bmp", "upbuttondown.bmp", " ", ARIAL,
                      BLACK, WHITE, Up3 );

    g_gui->AddButton( 72, 96, "downbuttonup.bmp", "downbuttondown.bmp", " ", ARIAL,
                      BLACK, WHITE, Down1 );
    g_gui->AddButton( 112, 96, "downbuttonup.bmp", "downbuttondown.bmp", " ", ARIAL,
                      BLACK, WHITE, Down2 );
    g_gui->AddButton( 152, 96, "downbuttonup.bmp", "downbuttondown.bmp", " ", ARIAL,
                      BLACK, WHITE, Down3 );

    g_gui->AddButton( 672, 0, "gbup.bmp", "gbdown.bmp", "Minimax", ARIAL,
                      BLACK, WHITE, MiniMax );
    
    // set our at exit function
    atexit( SDL_Quit ) ;

    // declare event variable
    SDL_Event event;

    g_gui->Draw();
    g_gui->Update();

    // loop until we get a quit message.
    while( 1 )
    {
        //look for an event
        if( SDL_PollEvent( &event ) )
        {
            //an event was found
            if( event.type == SDL_QUIT ) 
                break;

            // mouse button was pressed
            if( event.type == SDL_MOUSEBUTTONDOWN ) 
            {
                // get the mouse g_state.
                SDL_GetMouseState( &x, &y );

                // tell the GUI that a button has been pressed
                g_gui->MouseDown( x, y );

            }

            // mouse button was released
            if( event.type == SDL_MOUSEBUTTONUP ) 
            {
                // get the mouse state.
                SDL_GetMouseState( &x, &y );

                // tell the GUI that a button has been released
                g_gui->MouseUp( x, y );
            }

            if( event.type == SDL_KEYDOWN )
            {
                // a key was pressed.
                if( event.key.keysym.sym == SDLK_ESCAPE )
                {
                    // if ESC was pressed, quit the program.
                    SDL_Event quit;
                    quit.type = SDL_QUIT;
                    SDL_PushEvent( &quit );
                }

                // tell the GUI that a key was pressed.
                g_gui->KeyDown( event.key.keysym.sym, 
                                event.key.keysym.mod,
                                event.key.keysym.unicode );
            }
        }


        if( g_processing == true && SDL_GetTicks() - g_timer > g_delay )
        {
            g_queue.Dequeue();

            if( g_queue.Count() != 0 )
            {
                g_current = g_queue.Front().m_node;
                CalculateMiniMaxValue( g_queue.Front() );
                g_timer = SDL_GetTicks();
            }
            else
            {
                g_current = 0;
                g_processing = false;
            }
        }


        // draw the g_gui at the end of each loop.
        g_gui->Draw();

        DrawRocks( g_startingState, 64, 16 );

        if( g_tree != 0 )
        {
            DrawTree( g_tree, 0, 0, WIDTH );
        }

        g_gui->Update();
    }

    return 0;
}