mapdemo.cpp

基于SDL的图形化贪心算法演示,支持节点的拖放

#include "SDLGUI.h"

#include <deque>
using std::deque;
#include <stdlib.h>
#include <time.h>
#include "ShortPath.h"
#include "Object.h"

#include <afx.h>
#ifdef _DEBUG
#include "Console.h"
#endif // _DEBUG

#include "resource.h"

/*
算法5.10 生成最短路径的贪心算法
procedure SHORTEST-PATHS(v,COST,DIST,n)
//G是一个n结点有向图，它由其成本邻接矩阵COST(n,n)表示。DIST(j)被置
从结点v到结点j的最短路径长度，这里1≤j≤n。DIST(v)被置成零//
boolean S(1:n);real COST(1:n,1:n),DIST(1:n)
integer u,v,n,num,i,w
for i←1 to n do //将集合S初始化为空//
S(i) ←0;DIST(i) ←COST(v,i)  //若                          ，则DIST(i)=∞//
repeat
S(v) ←1;DIST(v) ←0  //结点v计入S//
for num←2 to n-1 do //确定由结点v出发的n-1条路//
选取结点u,它使得DIST(u)=     
S(u) ←1 //结点u计入S//
for 所有S(w)＝0的结点w do  //修改DIST(w)//
DIST(w) = min(DIST(w), DIST(u) + COST(u,w))
repeat
repeat
end SHORTEST-PATHS
*/

// ============================================================================
//  Global Constants
// ============================================================================
const char PROGRAM_NAME[]   = "Map Demo";

const int ARIAL             = 0;

// ============================================================================
//  Global Variables
// ============================================================================
const int WIDTH             = 800;
const int HEIGHT            = 600;
const int ITEMS             = 32;

SDLGUI* g_gui = new SDLGUI( WIDTH, HEIGHT, ITEMS, WHITE );

int				g_timer;

SDL_Surface*	g_blackcircle;
SDL_Surface*	g_redcircle;

#ifdef _DEBUG
CConsole		console;
#endif // _DEBUG

deque<MapNode*> g_NodeDeque;
deque<MapNode*>* MapNode::p_NodeDeque = &g_NodeDeque;


int				g_nNodeNum = 1;
MapNode*		g_pAddingNode = NULL;

int				g_AddLineProcess = 0;
MapLine*		g_pCurrentLine = NULL;

bool			bFrom = false;
bool			bTo	  = false;
bool			bGo	  = false;

MapNode*		g_pNodeFrom = NULL;
int				g_FromIndex;
MapNode*		g_pNodeTo = NULL;
int				g_ToIndex;

CShortPath*		g_pShortPath = NULL;

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


int GetNodeFrom( int x, int y )
{

	for( int i = 0; i< g_NodeDeque.size(); ++i )
	{
		MapNode* node = g_NodeDeque[i];

		if( node->PointIn( x, y ) )
		{
			return i;
		}
	}

	return NULL;
}

void ClearButton()
{
	for( int i = 3; i < g_gui->GetItemNum()+1; ++i )
	{
		g_gui->DeleteUI( i );
	}
}

void GoButton()
{
	int size =  g_NodeDeque.size();
	g_pShortPath = new CShortPath( size );

	bGo = true;

#ifdef _DEBUG
	g_pShortPath->console = &console;
#endif // _DEBUG

	for( int i = 0; i < size; ++i )
	{
		for( int j = 0; j< size; ++j )
		{	
			int num;
			if( i == j )
				num = 0;

			else{
		
				MapNode* node = g_NodeDeque[i];
				num = node->GetLengthToNode( j );
			
				g_pShortPath->SetCost( i,j, num );
			}

#ifdef _DEBUG
				console.Output( "cost[%d][%d]:%d\n ",i,j,num );
#endif // _DEBUG

		}
	}

	g_pShortPath->ProcessShortPath( g_FromIndex );
	//CreateDialog( IDD_DIALOG1 );
	//CListCtrl* pListCtrl = GetDlgItem(   )


#ifdef _DEBUG
	for( int i = 0; i< size; ++i )
	{
		for( int j = 0; j< size; ++j )
		{

			console.Output( "cost[%d][%d]:%d\n ",i,j,(g_pShortPath->cost)[i*size+j] );
		
		}
		console.Output( "path%d:",i );
		for( int k = 0; k< g_pShortPath->pathvector[i].size(); ++k )
		{
			console.Output( "_%d",g_pShortPath->pathvector[i][k] );

		}
	}
#endif // _DEBUG
	

}

void OnFromDown()
{
	int x;
	int y;

	SDL_GetMouseState( &x, &y ); 


	g_FromIndex = GetNodeFrom( x, y );
	MapNode* node = g_NodeDeque[g_FromIndex];

	if( node ){

		if( g_pNodeFrom )
			g_pNodeFrom->UnFocus();
		
		node->Focus();
		g_pNodeFrom = node;


	}

	bFrom = false;
}

void OnToDown()
{
	int x;
	int y;

	SDL_GetMouseState( &x, &y );

	g_ToIndex = GetNodeFrom( x, y );
	MapNode* node = g_NodeDeque[g_ToIndex];

	if( node && node != g_pNodeFrom ){

		if( g_pNodeTo )
			g_pNodeTo->UnFocus();
		
		node->Focus();
		g_pNodeTo = node;
	}

	bTo = false;
}


void FromButton()
{
	bFrom = true;
}

void ToButton()
{
	bTo = true;
}



void AddNodeButton()
{
	char name[10];
	int x;
	int y;

	SDL_GetMouseState( &x, &y );

	sprintf( name, "V%d",g_nNodeNum );
	MapNode* node = new MapNode( name , x , y );
	g_pAddingNode = node;
	g_NodeDeque.push_back( node );
	g_nNodeNum++;
}



void ReleaseCurrentLine()
{
	if( g_pCurrentLine )
		g_pCurrentLine->ReleaseLine();
}


void AddLineButton()
{
	ReleaseCurrentLine();
	g_AddLineProcess = 1;
	g_pCurrentLine = new MapLine(0, NULL, NULL );
}

void OnAddLineProcess()
{
	int x,y;

	static MapNode* from;
	static MapNode* to;
	SDL_GetMouseState( &x, &y );
	if( g_AddLineProcess == 1 )
	{
		for( int i = 0; i< g_NodeDeque.size(); ++i )
		{
			MapNode* node = g_NodeDeque[i];
				
			if( node->PointIn( x, y ) )
			{
				from = node;	
				g_pCurrentLine->FocusFrom( node );

				from->Focus();
				g_AddLineProcess++;
			}
		}
		

	}

	else if( g_AddLineProcess == 2 )
	{
		if( from )
		{
			for( int i = 0; i< g_NodeDeque.size(); ++i )
			{
				MapNode* node = g_NodeDeque[i];
				to = node;
				if( node->PointIn( x, y ) && node != g_pCurrentLine->GetFromNode() )
				{
					g_pCurrentLine->FocusTo( node );
					from->AddLine( g_pCurrentLine );
					
					from->UnFocus();

					g_AddLineProcess = 0;
					g_pCurrentLine = NULL;
					from = NULL;
					to = NULL;
				}
			}
		}
		
	}
		


}


void ClearNodeAndLine()
{
	
}


void DrawMap()
{
	for( int i = 0 ; i < g_NodeDeque.size(); ++i )
	{
		g_NodeDeque[i]->Draw();
	}
	
	if( g_pAddingNode )
	{
		int x;
		int y;
		SDL_GetMouseState( &x, &y );

		g_pAddingNode->SetPos( x-24, y-24 );
		g_pAddingNode->Draw();
		
	}

	if( g_pNodeFrom )
	{
		int x,y;
		static SDL_Surface* text;
		g_pNodeFrom->Focus();
		g_pNodeFrom->GetPos( &x, &y );
		text = TTF_RenderText_Shaded( g_gui->GetFont(1), "From", RED, WHITE );
		g_gui->Blit( text, x , y );
		SDL_FreeSurface( text );
	}

	if( g_pNodeTo )
	{
		int x,y;
		static SDL_Surface* text;
		g_pNodeTo->Focus();
		g_pNodeTo->GetPos( &x, &y );
		text = TTF_RenderText_Shaded( g_gui->GetFont(1), "To", RED, WHITE );
		g_gui->Blit( text, x , y );
		SDL_FreeSurface( text );
	}

	if( bGo ){
		int x = 180; 
		int y = 380;
		static SDL_Surface* text;
		
		char str[50];

		int size = g_pShortPath->pathvector.size();
		for( int i = 0; i < size; i++ )
		{
			if( i == g_FromIndex )
				continue;

			y += 20;
			sprintf( str, "Path[%d]: V%d",i+1,g_FromIndex+1);
			for( int j = 0; j < (g_pShortPath->pathvector[i]).size(); ++j )
			{
				char temp[5];
				sprintf( temp, "->V%d", (g_pShortPath->pathvector[i])[j]+1);
				strcat( str, temp );
				text = TTF_RenderText_Shaded( g_gui->GetFont(2), str, BLACK, WHITE );
				g_gui->Blit( text, x , y );
				SDL_FreeSurface( text );
		
			}
		}
	}

	static SDL_Surface* text;
	char temp[5];
	text = TTF_RenderText_Shaded( g_gui->GetFont(3), " Developed by Shen Yuqing From CS0605  012006012519  /2008", BLACK, WHITE );
	g_gui->Blit( text, 400 ,10  );
	SDL_FreeSurface( text );

}
// ============================================================================
//  Main
// ============================================================================

int main( int argc, char* argv[] )
{
    int x;
    int y;
 
#ifdef _DEBUG
	console.Create( "debulg console" );
#endif // _DEBUG

    srand( time(0) );

    SDL_Init( SDL_INIT_VIDEO | SDL_INIT_TIMER );
    SDL_WM_SetCaption( PROGRAM_NAME, 0); 
	SDL_EnableUNICODE( 1 ); 
	TTF_Init();
    g_gui->SetFont( "arial.ttf", ARIAL, 20, TTF_STYLE_NORMAL );
	g_gui->SetFont( "arial.ttf", 1, 10, TTF_STYLE_NORMAL);
	g_gui->SetFont( "arial.ttf", 2, 15, TTF_STYLE_NORMAL);
	g_gui->SetFont( "arial.ttf", 3, 12, TTF_STYLE_NORMAL);

    // load the bmps
    g_blackcircle = SDL_LoadBMP( "circleblack.bmp" );
    g_redcircle =   SDL_LoadBMP( "circlered.bmp" );

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


	int start_x = 20;
	int start_y = 50;

	int distance = 80;

    // add the items to the g_gui

	g_gui->AddButton( start_x, start_y, "gbup.bmp", "gbdown.bmp", "Add Node", ARIAL,
		BLACK, WHITE, AddNodeButton );

	g_gui->AddButton( start_x, start_y + distance, "gbup.bmp", "gbdown.bmp", "Add Line", ARIAL,
		BLACK, WHITE, AddLineButton );

	g_gui->AddButton( start_x, start_y + distance*2, "gbup.bmp", "gbdown.bmp", "Go", ARIAL,
		BLACK, WHITE, GoButton );

	g_gui->AddButton( start_x, start_y + distance*3, "gbup.bmp", "gbdown.bmp", "From", ARIAL,
		BLACK, WHITE, FromButton );

	//g_gui->AddButton( start_x, start_y + distance*4, "gbup.bmp", "gbdown.bmp", "Clear", ARIAL,
	//	BLACK, WHITE, NULL );
	//
	//g_gui->AddTextBox( 100,200, 100, 30,str , 20, ARIAL, BLACK, WHITE,BLACK, true, 0 );

    atexit( SDL_Quit ) ;

    SDL_Event event;

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

    g_timer = SDL_GetTicks();

    while( 1 )
    {
       
        if( SDL_PollEvent( &event ) )
        {
            
            if( event.type == SDL_QUIT ) 
                break;

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

				if( g_pAddingNode )
				{
					g_pAddingNode = NULL;				
				}
             
                g_gui->MouseDown( x, y );

				
				OnAddLineProcess();

				if( bFrom )
					OnFromDown();

				if( bTo )
					OnToDown();


            }

        
            if( event.type == SDL_MOUSEBUTTONUP ) 
            {
                SDL_GetMouseState( &x, &y );

                g_gui->MouseUp( x, y );

            }

            if( event.type == SDL_KEYDOWN )
            {
              
                if( event.key.keysym.sym == SDLK_ESCAPE )
                {
                  
                    SDL_Event quit;
                    quit.type = SDL_QUIT;
                    SDL_PushEvent( &quit );
                }

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

		DrawMap();

        g_gui->Update();
		
    }

    return 0;
}