SDLGameEngine

- Main Page
- Related Pages
- Modules
- Data Structures
- Files

- File List
- Globals

# src/sgepathfinder.c

    00001 /*
    00002  * Copyright (c) 2007 Heiko Irrgang
    00003  *
    00004  * The license and distribution terms for this file may be
    00005  * found in the file COPYING in this distribution or at
    00006  * http://93-interactive.com/cms/products/software/sdl-game-engine/license/
    00007  */
    00008
    00009 #include <sge.h>
    00010
    00011 static void sgePathFinderInfoFree(Uint32 id, void *data) {
    00012         sgePathFinderInfoDestroy((SGEPATHFINDERINFO *)data);
    00013 }
    00014
    00015 SGEPATHFINDER *sgePathFinderNew(int width, int height) {
    00016         SGEPATHFINDER *ret;
    00017         sgeNew(ret, SGEPATHFINDER);
    00018         ret->width=width;
    00019         ret->height=height;
    00020         sgeMalloc(ret->map, unsigned char, width*height);
    00021         ret->path=sgeAutoArrayNew(&sgePathFinderInfoFree);
    00022         ret->useDiagonal=1;
    00023         return ret;
    00024 }
    00025
    00026 SGEPATHFINDER *sgePathFinderNewDiagonal(int width, int height, int diagonal) {
    00027         SGEPATHFINDER *ret=sgePathFinderNew(width, height);
    00028         sgePathFinderDiagonal(ret, diagonal);
    00029         return ret;
    00030 }
    00031
    00032 void sgePathFinderDestroy(SGEPATHFINDER *p) {
    00033         if (p->map!=NULL) {
    00034                 sgeFree(p->map);
    00035         }
    00036         sgeArrayDestroy(p->path);
    00037         sgeFree(p);
    00038 }
    00039
    00040 inline void sgePathFinderDiagonal(SGEPATHFINDER *p, int diagonal) {
    00041         p->useDiagonal=diagonal;
    00042 }
    00043
    00044 SGEPATHFINDERINFO *sgePathFinderInfoNew(int x, int y, int startWeight, int targetWeight, void *parent) {
    00045         SGEPATHFINDERINFO *ret;
    00046         sgeNew(ret, SGEPATHFINDERINFO);
    00047         ret->x=x;
    00048         ret->y=y;
    00049         ret->startWeight=startWeight;
    00050         ret->targetWeight=targetWeight;
    00051         ret->parent=parent;
    00052         return ret;
    00053 }
    00054
    00055 void sgePathFinderInfoDestroy(SGEPATHFINDERINFO *pi) {
    00056         sgeFree(pi);
    00057 }
    00058
    00059 void sgePathFinderSet(SGEPATHFINDER *p, int x, int y, int value) {
    00060         p->map[y*p->width+x]=(unsigned char) value;
    00061 }
    00062
    00063 int sgePathFinderGet(SGEPATHFINDER *p, int x, int y) {
    00064         if ( (x<0) || (x>p->width-1) ) return 1;
    00065         if ( (y<0) || (y>p->height-1) ) return 1;
    00066         return (int)p->map[y*p->width+x];
    00067 }
    00068
    00069 static int sgePathFinderIsClosed(SGEPATHFINDER *p, unsigned char *map, int x, int y) {
    00070         if ( (x<0) || (x>p->width-1) ) return 1;
    00071         if ( (y<0) || (y>p->height-1) ) return 1;
    00072         return (int)map[y*p->width+x];
    00073 }
    00074
    00075 int sgePathFinderFind(SGEPATHFINDER *p, int startx, int starty, int destx, int desty) {
    00076         int found=0;
    00077         SGEARRAY *openList;
    00078         SGEARRAY *closedList;
    00079         unsigned char *scannedMap;
    00080         SGEPATHFINDERINFO *pi=NULL;
    00081         SGEPATHFINDERINFO *opi=NULL;
    00082         int x,y;
    00083         int dist;
    00084         int newweight;
    00085         int idx;
    00086         int xstart, xend, xstep;
    00087
    00088         sgeMalloc(scannedMap, unsigned char, p->width*p->height);
    00089         openList=sgeArrayNew();
    00090         closedList=sgeArrayNew();
    00091         sgeArrayAdd(openList,sgePathFinderInfoNew(startx, starty, 0, 0, NULL));
    00092
    00093         while ( (!found) && (openList->numberOfElements) ) {
    00094                 pi=sgeArrayGet(openList, 0);
    00095                 sgeArrayRemove(openList, 0);
    00096                 if ( (pi->x==destx) && (pi->y==desty) ) {
    00097                         sgeArrayAdd(closedList, pi);
    00098                         found=1;
    00099                         continue;
    00100                 }
    00101                 for (y=pi->y-1;y<pi->y+2;y++) {
    00102                         if (p->useDiagonal==ENABLE_DIAGONAL) {
    00103                                 xstart=pi->x-1;
    00104                                 xend=pi->x+2;
    00105                                 xstep=1;
    00106                         } else {
    00107                                 if (y==pi->y) {
    00108                                         xstart=pi->x-1;
    00109                                         xend=pi->x+2;
    00110                                         xstep=2;
    00111                                 } else {
    00112                                         xstart=pi->x;
    00113                                         xend=pi->x+1;
    00114                                         xstep=1;
    00115                                 }
    00116                         }
    00117                         for (x=xstart;x<xend;x+=xstep) {
    00118                                 if (
    00119                                                 (!sgePathFinderIsClosed(p, scannedMap, x, y)) &&
    00120                                                 (!sgePathFinderGet(p, x, y)) &&
    00121                                                 ((x!=pi->x) || (y!=pi->y))
    00122                                 ) {
    00123                                         dist=sgeGetDistance(x<<7,y<<7,destx<<7,desty<<7);
    00124                                         if (openList->numberOfElements) {
    00125                                                 newweight=pi->startWeight+1+dist;
    00126
    00127                                                 opi=sgeArrayGet(openList,0);
    00128                                                 idx=1;
    00129                                                 while (
    00130                                                                 (opi->startWeight+opi->targetWeight<=newweight) &&
    00131                                                                 (idx<openList->numberOfElements)
    00132                                                 ) {
    00133                                                         opi=sgeArrayGet(openList,idx++);
    00134                                                 }
    00135                                                 if (idx==openList->numberOfElements) {
    00136                                                         sgeArrayAdd(openList,sgePathFinderInfoNew(x, y, pi->startWeight+1, dist, pi));
    00137                                                 } else {
    00138                                                         sgeArrayInsert(openList,idx-1,sgePathFinderInfoNew(x, y, pi->startWeight+1, dist, pi));
    00139                                                 }
    00140                                         } else {
    00141                                                 sgeArrayAdd(openList,sgePathFinderInfoNew(x, y, pi->startWeight+1, dist, pi));
    00142                                         }
    00143                                         scannedMap[y*p->width+x]=1;
    00144                                 }
    00145                         }
    00146                 }
    00147                 sgeArrayAdd(closedList, pi);
    00148         }
    00149
    00150         sgeFree(scannedMap);
    00151
    00152         while (openList->numberOfElements) {
    00153                 opi=sgeArrayGet(openList,0);
    00154                 sgePathFinderInfoDestroy(opi);
    00155                 sgeArrayRemove(openList,0);
    00156         }
    00157         sgeArrayDestroy(openList);
    00158
    00159         sgeArrayDestroy(p->path);
    00160         p->path=sgeAutoArrayNew(&sgePathFinderInfoFree);
    00161
    00162         if (!found) {
    00163                 while (closedList->numberOfElements) {
    00164                         opi=sgeArrayGet(closedList,0);
    00165                         sgePathFinderInfoDestroy(opi);
    00166                         sgeArrayRemove(closedList,0);
    00167                 }
    00168                 sgeArrayDestroy(closedList);
    00169                 return 0;
    00170         }
    00171
    00172         while (pi->parent!=NULL) {
    00173                 opi=(SGEPATHFINDERINFO *)pi->parent;
    00174                 sgeArrayInsert(p->path, 0, sgePathFinderInfoNew(pi->x, pi->y, 0, 0, NULL));
    00175                 pi=opi;
    00176         }
    00177         while (closedList->numberOfElements) {
    00178                 opi=sgeArrayGet(closedList,0);
    00179                 sgePathFinderInfoDestroy(opi);
    00180                 sgeArrayRemove(closedList,0);
    00181         }
    00182         sgeArrayDestroy(closedList);
    00183
    00184         return 1;
    00185 }
    00186

All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines