gd17-02.cpp

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

// ============================================================================
//  GD17-02.cpp
//  Graph Traversal Graphical Demonstration.
// ============================================================================
#include "SDLGUI.h"
#include "Graph.h"
#include "Queue.h"
#include <stdlib.h>
#include <time.h>



// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Graph Traversal Graphical Demonstration";
const int WIDTH             = 800;
const int HEIGHT            = 600;
const int ITEMS             = 32;
const int ARIAL             = 0;
const int NODES             = 64;


// ============================================================================
//  Classes
// ============================================================================
class Coordinates
{
public:
    int data;
    int x;
    int y;
};


enum GraphState
{
    NOSTATE,
    ADDNODE,
    REMOVENODE,
    ADDARC,
    REMOVEARC,
    CLICKDEPTHFIRST,
    DEPTHFIRST,
    CLICKBREADTHFIRST,
    BREADTHFIRST
};


typedef GraphArc<Coordinates, int> Arc;
typedef GraphNode<Coordinates, int> Node;

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

// the graph
Graph<Coordinates, int> g_graph( NODES );

// the current node
GraphNode<Coordinates, int>* g_current = 0;

// used for selecting the current node;
int g_currentindex = -1;

// used for adding and removing arcs
int g_from;

// the number (in order) of the node being processed.
int g_number;

// the queue that holds the order in which nodes are processed.
LQueue<GraphNode<Coordinates, int>*> g_queue;

// the timer
int g_timer;

// Circles
SDL_Surface* g_blackcircle;
SDL_Surface* g_redcircle;
SDL_Surface* g_greycircle;

// the state of the demo
GraphState g_state = NOSTATE;


// ============================================================================
//  Algorithms
// ============================================================================
int FindOpenIndex()
{
    int i;
    for( i = 0; i < NODES; i++ )
    {
        if( g_graph.m_nodes[i] == 0 )
            return i;
    }
    return -1;
}

void NodeProcess( GraphNode<Coordinates, int>* p_node )
{
    g_queue.Enqueue( p_node );
}

// ============================================================================
//  Draw Algorithm
// ============================================================================
void DrawGraph( Graph<Coordinates, int>& p_graph )
{
    int node;
    DListIterator<Arc> itr;
    static SDL_Surface* text;
    static char number[] = "00";

    for( node = 0; node < p_graph.m_nodes.m_size; node++ )
    {
        if( p_graph.m_nodes[node] != 0 )
        {
            

            // draw the contents of the circle.
            if( p_graph.m_nodes[node]->m_data.data >= 0 )
            {
                sprintf( number, "%d", p_graph.m_nodes[node]->m_data.data );
                text = TTF_RenderText_Shaded( g_gui->GetFont(ARIAL), number, BLACK, WHITE );
                g_gui->Blit( text, (g_blackcircle->w - text->w) / 2 + 
                                   p_graph.m_nodes[node]->m_data.x - 24, 
                                   (g_blackcircle->h - text->h) / 2 + 
                                   p_graph.m_nodes[node]->m_data.y - 24 );
                SDL_FreeSurface( text );
            }

            // draw the circle
            if( g_current == p_graph.m_nodes[node] || 
              ( g_from == node && (g_state == ADDARC || g_state == REMOVEARC ) ) )
                g_gui->Blit( g_redcircle, 
                             p_graph.m_nodes[node]->m_data.x - 24, 
                             p_graph.m_nodes[node]->m_data.y - 24 );
            else
                g_gui->Blit( g_blackcircle, 
                             p_graph.m_nodes[node]->m_data.x - 24, 
                             p_graph.m_nodes[node]->m_data.y - 24 );

            // draw each arc
            itr = p_graph.m_nodes[node]->m_arcList.GetIterator();
            for( itr.Start(); itr.Valid(); itr.Forth() )
            {
                g_gui->ArrowLine( p_graph.m_nodes[node]->m_data.x,
                                  p_graph.m_nodes[node]->m_data.y,
                                  itr.Item().m_node->m_data.x, 
                                  itr.Item().m_node->m_data.y,
                                  24, 24, false, true, BLACK );
            }
        }
    }
}




// ============================================================================
//  Button Callbacks
// ============================================================================
void AddNode()
{
    if( g_graph.m_count != NODES )
        g_state = ADDNODE;
}

void RemoveNode()
{
     g_state = REMOVENODE;
}

void AddArc()
{
    g_from = -1;
    g_state = ADDARC;
}

void RemoveArc()
{
    g_from = -1;
    g_state = REMOVEARC;
}

void DepthFirst()
{
    g_state = CLICKDEPTHFIRST;

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

    // clear all the numbers in the nodes
    for( int i = 0; i < NODES; i++ )
    {
        if( g_graph.m_nodes[i] != 0 )
            g_graph.m_nodes[i]->m_data.data = -1;
    }

    g_timer = SDL_GetTicks();

    g_number = 0;
}

void BreadthFirst()
{
    g_state = CLICKBREADTHFIRST;

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

    // clear all the numbers in the nodes
    for( int i = 0; i < NODES; i++ )
    {
        if( g_graph.m_nodes[i] != 0 )
            g_graph.m_nodes[i]->m_data.data = -1;
    }

    g_timer = SDL_GetTicks();

    g_number = 0;
}


// ============================================================================
//  Main
// ============================================================================
int main( int argc, char* argv[] )
{
    int x;
    int y;
    int i;

    Coordinates c;


    srand( time(0) );

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


    // load the bmps
    g_blackcircle = SDL_LoadBMP( "circleblack.bmp" );
    g_redcircle =   SDL_LoadBMP( "circlered.bmp" );
    g_greycircle =  SDL_LoadBMP( "circlegrey.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_greycircle, SDL_SRCCOLORKEY, 
                     SDL_MapRGB( g_greycircle->format, 255, 255, 255 ));

    // add the items to the g_gui
    g_gui->AddButton( 0, 0, "gbup.bmp", "gbdown.bmp", "Add Node", ARIAL,
                      BLACK, WHITE, AddNode );
    g_gui->AddButton( 0, 64, "gbup.bmp", "gbdown.bmp", "RemoveNode", ARIAL,
                      BLACK, WHITE, RemoveNode );
    g_gui->AddButton( 0, 128, "gbup.bmp", "gbdown.bmp", "Add Arc", ARIAL,
                      BLACK, WHITE, AddArc );
    g_gui->AddButton( 0, 192, "gbup.bmp", "gbdown.bmp", "Remove Arc", ARIAL,
                      BLACK, WHITE, RemoveArc );
    g_gui->AddButton( 0, 256, "gbup.bmp", "gbdown.bmp", "DepthFirst", ARIAL,
                      BLACK, WHITE, DepthFirst );
    g_gui->AddButton( 0, 320, "gbup.bmp", "gbdown.bmp", "BreadthFirst", ARIAL,
                      BLACK, WHITE, BreadthFirst );

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

                // determine what to do based on the state.
                switch( g_state )
                {

                // add a new node.
                case ADDNODE:
                    c.x = x;
                    c.y = y;
                    c.data = -1;
                    g_graph.AddNode( c, FindOpenIndex() );
                    g_state = NOSTATE;
                    break;

                // remove the current node.
                case REMOVENODE:
                    if( g_currentindex != -1 )
                        g_graph.RemoveNode( g_currentindex );
                    g_state = NOSTATE;
                    break;

                case ADDARC:
                    if( g_from == -1 )
                    {
                        g_from = g_currentindex;
                    }
                    else
                    {
                        g_graph.AddArc( g_from, g_currentindex, 0 );
                        g_state = NOSTATE;
                    }
                    break;

                case REMOVEARC:
                    if( g_from == -1 )
                    {
                        g_from = g_currentindex;
                    }
                    else
                    {
                        g_graph.RemoveArc( g_from, g_currentindex );
                        g_state = NOSTATE;
                    }
                    break;

                case CLICKDEPTHFIRST:
                    // clear the marks, perform the traversal.
                    g_graph.ClearMarks();
                    g_graph.DepthFirst( g_current, NodeProcess );
                    g_state = DEPTHFIRST;
                    if( g_queue.Count() != 0 )
                        g_queue.Front()->m_data.data = 0;
                    else 
                        g_state = NOSTATE;
                    g_timer = SDL_GetTicks();
                    break;

                case CLICKBREADTHFIRST:
                    // clear the marks, perform the traversal.
                    g_graph.ClearMarks();
                    g_graph.BreadthFirst( g_current, NodeProcess );
                    g_state = BREADTHFIRST;
                    if( g_queue.Count() != 0 )
                        g_queue.Front()->m_data.data = 0;
                    else 
                        g_state = NOSTATE;
                    g_timer = SDL_GetTicks();
                }


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

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


        // color the highlighted node red.
        g_currentindex = -1;
        g_current = 0;
        SDL_GetMouseState( &x, &y );
        for( i = 0; i < NODES; i++ )
        {
            if( g_graph.m_nodes[i] != 0 )
            {
                if( g_graph.m_nodes[i]->m_data.x - 24 <= x && 
                    g_graph.m_nodes[i]->m_data.x + 24 >= x && 
                    g_graph.m_nodes[i]->m_data.y - 24 <= y && 
                    g_graph.m_nodes[i]->m_data.y + 24 >= y )
                {
                    g_current = g_graph.m_nodes[i];
                    g_currentindex = i;
                    i = NODES;
                }
            }
        }

        if( g_state == DEPTHFIRST || g_state == BREADTHFIRST )
        {
            g_current = g_queue.Front();

            if( SDL_GetTicks() - g_timer >= 700 )
            {
                g_number++;
                g_queue.Dequeue();
                if( g_queue.Count() != 0 )
                {
                    g_current = g_queue.Front();
                    g_current->m_data.data = g_number;
                }
                else
                    g_state = NOSTATE;

                g_timer = SDL_GetTicks();
            }
        }

        DrawGraph( g_graph );

        if( g_state == ADDNODE )
        {
            SDL_GetMouseState( &x, &y );
            g_gui->Blit( g_greycircle, x - 24, y - 24 );
        }


        g_gui->Update();
    }

    return 0;
}