g15-01.cpp

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

// ============================================================================
//  G15-01.cpp
//  Rock Pile game demo
// ============================================================================
#include "SDLGUI.h"
#include "Queue.h"
#include "Tree.h"
#include <stdlib.h>
#include <time.h>



// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Rock Pile Game Demo";
const int WIDTH             = 640;
const int HEIGHT            = 480;
const int ITEMS             = 64;
const int ARIAL             = 0;
const int PILES             = 5;
const int ROCKS             = 8;

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

    // constructor, clear everything
    RockState()
    {
        int x;

        // clear each pile
        for( x = 0; x < PILES; x++ )
            m_rocks[x] = 0;

        // make the minimax value 0
        m_minimaxValue = -1;

        // there is no next state yet.
        m_nextState = 0;
    }


    // equivalence operator, return true if all the piles match.
    bool operator== ( RockState& p_rock )
    {
        int x;
        for( x = 0; x < PILES; x++ )
        {
            // if any of the piles don't match, return false
            if( m_rocks[x] != p_rock.m_rocks[x] )
                return false;
        }
        return true;
    }

    // determines if the pile is empty.
    bool Empty()
    {
        int x;
        for( x = 0; x < PILES; x++ )
        {
            // if any of the piles aren't empty, return false
            if( m_rocks[x] != 0 )
                return false;
        }
        return true;
    }

    // the rock data
    int m_rocks[PILES];

    // the minimax value of the state
    int m_minimaxValue;

    // the next state of the game using the minimax algorithm
    Tree<RockState>* m_nextState;
};



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

int g_timer;

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

// the initial state of the game
RockState g_startingState;

// the current state of the game
Tree<RockState>* g_current = 0;

// this determines whether the game is being played or not.
bool g_playing = false;

// this determines if the hint is shown.
bool g_hint = false;

// determines whose turn it is.
bool g_yourturn = true;

// determines if the game is over.
bool g_gameOver = false;

// the rock graphic.
SDL_Surface* g_rock;



// ============================================================================
//  Functions
// ============================================================================
void GameOver()
{
    // stop the game
    g_playing = false;
    g_gameOver = true;

    // hide the buttons.
    g_gui->GetItem( 15 )->SetVisibility( false );
    g_gui->GetItem( 16 )->SetVisibility( 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 + 128, p_x + x * 40 + 32, p_y + 128, BLACK );
        g_gui->Line( p_x + x * 40, p_y, p_x + x * 40, p_y + 128, BLACK );
        g_gui->Line( p_x + x * 40 + 32, p_y, p_x + x * 40 + 32, p_y + 128, BLACK );

        y = p_y + 112;

        // draw each rock in the current pile
        for( z = 0; z < p_state.m_rocks[x]; z++ )
        {
            g_gui->Blit( g_rock, p_x + x * 40, y );
            y -= 16;
        }
    }
}




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

// god bless recursion.
// this calculates the game tree.
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;

    // set the tree nodes state to the parameter state
    tree->m_data = p_state;
    

    // loop through each pile
    for( i = 0; i < PILES; i++ )
    {
        // loop through each rock in each pile
        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;
}

// return the heuristic value of the end-game state using
// the current players turn as a value.
int Heuristic( RockState p_state, bool p_max )
{
    return p_max;
}


// calculate the minimax value of a single node.
void CalculateMiniMaxValue( Tree<RockState>* p_tree, bool p_max )
{
    // if the node is a leaf node, calculate its heuristic value.
    if( p_tree->m_children.m_count == 0 )
    {
        p_tree->m_data.m_minimaxValue = Heuristic( p_tree->m_data, p_max );
        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_tree;

    itr.ChildStart();
    minmax = itr.ChildItem().m_minimaxValue;
    p_tree->m_data.m_nextState = itr.m_childitr.m_node->m_data;
    itr.ChildForth();

    if( p_max == true )
    {
        // max's turn
        // loop through finding the highest child
        while( itr.ChildValid() )
        {
            if( itr.ChildItem().m_minimaxValue > minmax )
            {
                minmax = itr.ChildItem().m_minimaxValue;
                p_tree->m_data.m_nextState = itr.m_childitr.m_node->m_data;
            }
            itr.ChildForth();
        }
    }
    else
    {
        // min's turn
        // loop through finding the lowest child
        while( itr.ChildValid() )
        {
            if( itr.ChildItem().m_minimaxValue < minmax )
            {
                minmax = itr.ChildItem().m_minimaxValue;
                p_tree->m_data.m_nextState = itr.m_childitr.m_node->m_data;
            }
            itr.ChildForth();
        }
    }

    p_tree->m_data.m_minimaxValue = minmax;
}


// recursively calculate the entire minimax tree.
void MiniMax( Tree<RockState>* p_tree, bool p_max )
{
    TreeIterator<RockState> itr = p_tree;

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

    // process the current node.
    CalculateMiniMaxValue( p_tree, p_max );
}


// remove the rocks from the pile
void ClickRock( int p_pile, int p_rock )
{
    RockState newstate = g_current->m_data;
    TreeIterator<RockState> itr = g_current;

    // check to make sure the player didn't click too many rocks;
    // we don't want negative rocks in a pile.
    if( p_rock > newstate.m_rocks[p_pile] )
        p_rock = newstate.m_rocks[p_pile];

    // remove the rocks.
    newstate.m_rocks[p_pile] -= p_rock;

    // find the child node that matches.
    for( itr.ChildStart(); itr.ChildValid(); itr.ChildForth() )
    {
        if( itr.ChildItem() == newstate )
        {
            // found a match, return.
            g_current = itr.m_childitr.Item();
            return;
        }
    }
}


// now the computer goes!
void OpponentMove()
{
    if( g_yourturn == false )
    {
        g_current = g_current->m_data.m_nextState;
        if( g_current->m_data.Empty() )
        {
            // Computer loses!
            g_gui->GetItem( 0 )->SetVisibility( true );
            GameOver();
        }
        else
        {
            g_yourturn = true;
            g_gui->GetItem( 2 )->SetVisibility( true );
        }
        g_gui->GetItem( 3 )->SetVisibility( false );
    }

    // that was simple, wasn't it? heh.
}

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

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

    // calculate the new game tree
    g_tree = CalculateTree( g_startingState );
}