商业编程-源码-A_寻路算法源代码.zip

/////////////////////////////////////////////////////////////// // A* pathfind using "manhattan distance" heuristic // // This program is a simple example of pathfind based on A* // algorithm. // I have implemented the algorithm using linked list, this is // not the best solution, because of the linear time need to access // to the listes, but this is the simplest way, and this is just // an example! ;) // For a better implementation of A* give a look at Mars source // code, when we will release it... :) // // for info about A* algorithm and "manhattan distance" heuristic // give a look at: // - http://theory.stanford.edu/~amitp/GameProgramming/ // - http://www.policyalmanac.org/games/aStarTutorial.htm // guys, thanx for your articles! // // // To play with it, just select the grey "robot", it should (I hope :)) // became blue, now you can select a destination, the program will calculate // the shortest path and move along it. // // During the "game" you could use these keys: // // - SPACEBAR -> change video mode (window/fullscreen) // - p -> pause/restart the game // - ESC -> exit // // // This software is released under GPL license, you can find a // copy of this license at http://www.gnu.org/copyleft/gpl.html // // // Last update date: // 2005-02-15 // // Author: // Davide "M3xican" Coppola - dmc@dev-labs.net // // NOTE: // // This program is part of "Mars, Land of No Mercy" SDL examples, // you can find others examples on http://mars.sourceforge.net // ///////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <string.h> #include <SDL/SDL.h> #include "define.h" #include "graphic.h" #include "grind.h" #include "pathfind.h" #include "struct.h" int main(int argc,char *argv[]) { //used surfaces SDL_Surface *screen; SDL_Surface *screen_backup; SDL_Surface *robot; SDL_Surface *bg_robot; //three SDL_Color structures SDL_Color black = {0x00,0x00,0x00,0}; SDL_Color light_grey = {0xDD,0xDD,0xDD,0}; SDL_Color grey = {0x99,0x99,0x99,0}; SDL_Color light_blue = {0x33,0x66,0x99,0}; SDL_Color red = {0xFF,0x00,0x00,0}; SDL_Color white = {0xFF,0xFF,0xFF,0}; //the system video is initialized if( SDL_Init(SDL_INIT_VIDEO) <0 ) { //SDL_GetError() returns a description of the error printf("SDL Init Error: %s\n", SDL_GetError()); return 1; } //when exit, execute SDL_Quit to restore everything atexit(SDL_Quit); //a 32 bit integer used to store screen's flags Uint32 flags = SDL_HWSURFACE|SDL_DOUBLEBUF; //SDL_SetVideoMode is used to have screen associated to the monitor if(!( screen = SDL_SetVideoMode(DIM_H, DIM_V, 0,flags) )) { printf("Screen Init Error : %s\n", SDL_GetError()); return 1; } //white background fill_square(screen, NULL, white); //screen_backup is a surface of the same dimensions of screen used to save the image when the user //changes its form (window to full screen and vice versa). screen_backup = SDL_CreateRGBSurface(flags,screen->w,screen->h,screen->format->BitsPerPixel,0,0,0,0); robot = SDL_CreateRGBSurface(flags,CELL_SIDE-ROBOT_DIST,CELL_SIDE-ROBOT_DIST, screen->format->BitsPerPixel,0,0,0,0); bg_robot = SDL_CreateRGBSurface(flags,CELL_SIDE-ROBOT_DIST,CELL_SIDE-ROBOT_DIST, screen->format->BitsPerPixel,0,0,0,0); //paint robot fill_square(robot, NULL, grey); //map rectangle SDL_Rect grind = {CELL_SIDE/2,CELL_SIDE/2,DIM_H-CELL_SIDE,DIM_V-CELL_SIDE}; //manual test map int map[NUM_ROWS][NUM_COLS]={{1,1,1,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1,1}, {1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1}, {1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1}, {0,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1}, {1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1}, {1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}; //secret MARS map :) /* int map[NUM_ROWS][NUM_COLS]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1}, {1,1,1,0,0,1,0,0,1,1,1,1,0,1,0,1,1,1,1}, {1,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1}, {1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,1,1,1}, {1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1}, {1,1,1,0,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1}, {1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1}, {1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1}, {1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}; */ //draw map on screen draw_map(screen,grind,map); //cell occupied by the robot cell_ind robot_cell; //robot is selected? bool robot_sel = false; //destination point point robot_dest; //path indexes cell_ind * robot_path; //path lenghth int len_path = 0, bk_len = 0; int ind_path = 0; bool need_checkp = false; //get a free cell to place the robot on the map get_free_cell(map,&robot_cell); //robot rect SDL_Rect robot_rect = {grind.x + (robot_cell.col * CELL_SIDE) + ROBOT_DIST/2, grind.y + (robot_cell.row * CELL_SIDE) + ROBOT_DIST/2, robot->w, robot->h}; //upper left vertex of a cell point cell_vert; //variables used to store row and column indexes of a cell cell_ind mouse_cell = {0,0}, old_cell = {0,0}, dest_cell; bool cell_sel = false; point mouse = {0,0}; //SDL_Event struct used to manage events SDL_Event event; //variable used to control the game loop bool done = false; bool paused = false; //game or main loop (as you prefer) while(!done) { //SDL_PollEvent manages user's events while(SDL_PollEvent(&event)) { //the program quits if someone press the x simbol of the window with the mouse if(event.type == SDL_QUIT) done = true; if(event.type == SDL_KEYDOWN) { //it quits also if someone press ESC if ( event.key.keysym.sym == SDLK_ESCAPE ) done = true; else if ( event.key.keysym.sym == SDLK_p ) paused = !paused ; //visualization form is changed if someone press SPACE //(from window to full screen and vice versa) if(event.key.keysym.sym == SDLK_SPACE ) { //the actual screen is saved in screen_backup SDL_BlitSurface(screen,NULL,screen_backup,NULL); //visualization form is changed flags^=SDL_FULLSCREEN; screen = SDL_SetVideoMode(DIM_H, DIM_V, 0,flags); //the original image is reBlitted SDL_BlitSurface(screen_backup,NULL,screen,NULL); } } //a point is selected when the left mouse button is pressed if(event.button.button == BUTTON_SX && event.button.type == SDL_MOUSEBUTTONDOWN) { //robot cell clicked if(mouse_cell.row == robot_cell.row && mouse_cell.col == robot_cell.col) { //robot not yet selected if(!robot_sel) { robot_sel = true; fill_square(robot, NULL, light_blue); } else //robot selected { robot_sel = false; fill_square(robot, NULL, grey); } } //free cell clicked to move else if(map[mouse_cell.row][mouse_cell.col] && robot_sel && !len_path) { cell_sel = true; dest_cell.row = mouse_cell.row; dest_cell.col = mouse_cell.col; len_path = pathfind(map,robot_cell,dest_cell,&robot_path); if(len_path) { //backup path lenght bk_len = len_path; need_checkp = true; //draw path colour_path(robot_path,len_path,screen,black,light_grey); } } } //moving with the mouse if(event.motion.type == SDL_MOUSEMOTION) { //coordinates of rectangle that