From 4d1e84d0d9af4fcad025e039544a37a76c91aa1a Mon Sep 17 00:00:00 2001 From: skotlex Date: Wed, 22 Feb 2006 15:27:04 +0000 Subject: - Added map chk cells types CELL_CHKREACH and CELL_CHKNOREACH, they are the same as their PASS/NOPASS equivalents, but will ignore the cell-stacking mod when enabled. - Updated path.c with jA's implementation, which should make long path searching more efficient. - Also added some typedefs from jA for the common structure types (PC/MOB/NPC, etc) git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/trunk@5366 54d463be-8e91-2dee-dedb-b68131a5f0ec --- src/map/path.c | 195 ++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 115 insertions(+), 80 deletions(-) (limited to 'src/map/path.c') diff --git a/src/map/path.c b/src/map/path.c index 7cab27683..03f34ead1 100644 --- a/src/map/path.c +++ b/src/map/path.c @@ -7,12 +7,18 @@ #include "map.h" #include "battle.h" -#include "nullpo.h" +#include "../common/nullpo.h" #include "../common/showmsg.h" +#ifdef MEMWATCH +#include "memwatch.h" +#endif + +//#define PATH_STANDALONETEST + #define MAX_HEAP 150 -struct tmp_path { short x,y,dist,before,cost; char dir,flag;}; +struct tmp_path { short x,y,dist,before,cost,flag;}; #define calc_index(x,y) (((x)+(y)*MAX_WALKPATH) & (MAX_WALKPATH*MAX_WALKPATH-1)) /*========================================== @@ -23,11 +29,6 @@ static void push_heap_path(int *heap,struct tmp_path *tp,int index) { int i,h; - if( heap == NULL || tp == NULL ){ - ShowError("push_heap_path nullpo\n"); - return; - } - heap[0]++; for(h=heap[0]-1,i=(h-1)/2; @@ -46,9 +47,6 @@ static void update_heap_path(int *heap,struct tmp_path *tp,int index) { int i,h; - nullpo_retv(heap); - nullpo_retv(tp); - for(h=0;hx; if(xd<0) xd=-xd; yd=y1-p->y; @@ -119,21 +112,17 @@ static int calc_cost(struct tmp_path *p,int x1,int y1) * 必要ならpathを追加/修正する *------------------------------------------ */ -static int add_path(int *heap,struct tmp_path *tp,int x,int y,int dist,int dir,int before,int x1,int y1) +static int add_path(int *heap,struct tmp_path *tp,int x,int y,int dist,int before,int cost) { int i; - nullpo_retr(0, heap); - nullpo_retr(0, tp); - i=calc_index(x,y); if(tp[i].x==x && tp[i].y==y){ if(tp[i].dist>dist){ tp[i].dist=dist; - tp[i].dir=dir; tp[i].before=before; - tp[i].cost=calc_cost(&tp[i],x1,y1); + tp[i].cost=cost; if(tp[i].flag) push_heap_path(heap,tp,i); else @@ -149,9 +138,8 @@ static int add_path(int *heap,struct tmp_path *tp,int x,int y,int dist,int dir,i tp[i].x=x; tp[i].y=y; tp[i].dist=dist; - tp[i].dir=dir; tp[i].before=before; - tp[i].cost=calc_cost(&tp[i],x1,y1); + tp[i].cost=cost; tp[i].flag=0; push_heap_path(heap,tp,i); @@ -166,8 +154,6 @@ static int add_path(int *heap,struct tmp_path *tp,int x,int y,int dist,int dir,i */ static int can_place(struct map_data *m,int x,int y,int flag) { - nullpo_retr(0, m); - if(map_getcellp(m,x,y,CELL_CHKPASS)) return 1; if((flag&0x10000)&&map_getcellp(m,x,y,CELL_CHKGROUND)) @@ -186,10 +172,6 @@ static int can_place(struct map_data *m,int x,int y,int flag) */ static int can_move(struct map_data *m,int x0,int y0,int x1,int y1,int flag) { - nullpo_retr(0, m); - - if(x0-x1<-1 || x0-x1>1 || y0-y1<-1 || y0-y1>1) - return 0; if(x1<0 || y1<0 || x1>=m->xs || y1>=m->ys) return 0; if(flag&0x20000) //Flag to ignore everything, for use with Taekwon's Jump skill currently. [Skotlex] @@ -251,11 +233,11 @@ int path_blownpos(int m,int x0,int y0,int dx,int dy,int count) } /*========================================== - * ﾀﾋ袮ﾍ?ｪｬﾊｦﾒｪｫｪﾉｪｦｪｫｪﾚｪｹ + * 遠距離攻撃が可能かどうかを返す *------------------------------------------ */ #define swap(x,y) { int t; t = x; x = y; y = t; } -int path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y1) +int path_search_long_real(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y1,int flag) { int dx, dy; int wx = 0, wy = 0; @@ -281,7 +263,7 @@ int path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y spd->y[0] = y0; } - if (map_getcellp(md,x1,y1,CELL_CHKWALL)) + if (map_getcellp(md,x1,y1,flag)) return 0; if (dx > abs(dy)) { @@ -295,7 +277,7 @@ int path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y } while (x0 != x1 || y0 != y1) { - if (map_getcellp(md,x0,y0,CELL_CHKWALL)) + if (map_getcellp(md,x0,y0,flag)) return 0; wx += dx; wy += dy; @@ -324,11 +306,12 @@ int path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y * path探索 (x0,y0)->(x1,y1) *------------------------------------------ */ -int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int flag) +int path_search_real(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int flag,int flag2) { int heap[MAX_HEAP+1]; struct tmp_path tp[MAX_WALKPATH*MAX_WALKPATH]; int i,rp,x,y; + int xs,ys; struct map_data *md; int dx,dy; @@ -337,37 +320,40 @@ int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int if(!map[m].gat) return -1; md=&map[m]; - - if(x1<0 || x1>=md->xs || y1<0 || y1>=md->ys) - return -1; - #ifdef CELL_NOSTACK - if (map_getcellp(md,x1,y1,CELL_CHKNOPASS) && !map_getcellp(md,x1,y1,CELL_CHKSTACK)) - return -1; + //Do not check starting cell as that would get you stuck. + if(x0<0 || x0>=md->xs || y0<0 || y0>=md->ys) #else - if (map_getcellp(md,x1,y1,CELL_CHKNOPASS)) - return -1; + if(x0<0 || x0>=md->xs || y0<0 || y0>=md->ys || map_getcellp(md,x0,y0,flag2)) #endif + return -1; + if(x1<0 || x1>=md->xs || y1<0 || y1>=md->ys || map_getcellp(md,x1,y1,flag2)) + return -1; // easy + // この内部では、0 <= x+dx < sx, 0 <= y+dy < sy は保証されている dx = (x1-x0<0) ? -1 : 1; dy = (y1-y0<0) ? -1 : 1; for(x=x0,y=y0,i=0;x!=x1 || y!=y1;){ if(i>=sizeof(wpd->path)) return -1; if(x!=x1 && y!=y1){ - if(!can_move(md,x,y,x+dx,y+dy,flag)) + if(map_getcellp(md,x+dx,y ,flag2)) + break; + if(map_getcellp(md,x ,y+dy,flag2)) + break; + if(map_getcellp(md,x+dx,y+dy,flag2)) break; x+=dx; y+=dy; wpd->path[i++]=(dx<0) ? ((dy>0)? 1 : 3) : ((dy<0)? 5 : 7); } else if(x!=x1){ - if(!can_move(md,x,y,x+dx,y ,flag)) + if(map_getcellp(md,x+dx,y ,flag2)) break; x+=dx; wpd->path[i++]=(dx<0) ? 2 : 6; } else if(y!=y1){ - if(!can_move(md,x,y,x ,y+dy,flag)) + if(map_getcellp(md,x ,y+dy,flag2)) break; y+=dy; wpd->path[i++]=(dy>0) ? 0 : 4; @@ -381,6 +367,7 @@ int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int } #ifdef CELL_NOSTACK +/* Should not be needed, let's try and see. //If you fail by 1 cell, consider easy path successful, too. [Skotlex] if (check_distance(x-x1,y-y1,1)) { wpd->path_len=i; @@ -388,6 +375,7 @@ int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int wpd->path_half=0; return 0; } +*/ #endif if(flag&1) return -1; @@ -398,55 +386,102 @@ int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int tp[i].x=x0; tp[i].y=y0; tp[i].dist=0; - tp[i].dir=0; tp[i].before=0; tp[i].cost=calc_cost(&tp[i],x1,y1); tp[i].flag=0; heap[0]=0; push_heap_path(heap,tp,calc_index(x0,y0)); + xs = md->xs-1; // あらかじめ１減算しておく + ys = md->ys-1; while(1){ - int e=0,fromdir; + int e=0,f=0,dist,cost,dc[4]; if(heap[0]==0) return -1; - rp=pop_heap_path(heap,tp); - x=tp[rp].x; - y=tp[rp].y; - if(x==x1 && y==y1){ - int len,j; - - for(len=0,i=rp;len<100 && i!=calc_index(x0,y0);i=tp[i].before,len++); - if(len==100 || len>=sizeof(wpd->path)) - return -1; - wpd->path_len=len; - wpd->path_pos=0; - wpd->path_half=0; - for(i=rp,j=len-1;j>=0;i=tp[i].before,j--) - wpd->path[j]=tp[i].dir; - - return 0; + rp = pop_heap_path(heap,tp); + x = tp[rp].x; + y = tp[rp].y; + dist = tp[rp].dist + 10; + cost = tp[rp].cost; + if(x==x1 && y==y1) break; + + // dc[0] : y++ の時のコスト増分 + // dc[1] : x-- の時のコスト増分 + // dc[2] : y-- の時のコスト増分 + // dc[3] : x++ の時のコスト増分 + + if(y < ys && !map_getcellp(md,x ,y+1,flag2)) { + f |= 1; dc[0] = (y >= y1 ? 20 : 0); + e+=add_path(heap,tp,x ,y+1,dist,rp,cost+dc[0]); // (x, y+1) + } + if(x > 0 && !map_getcellp(md,x-1,y ,flag2)) { + f |= 2; dc[1] = (x <= x1 ? 20 : 0); + e+=add_path(heap,tp,x-1,y ,dist,rp,cost+dc[1]); // (x-1, y ) } - fromdir=tp[rp].dir; - if(can_move(md,x,y,x+1,y-1,flag)) - e+=add_path(heap,tp,x+1,y-1,tp[rp].dist+14,5,rp,x1,y1); - if(can_move(md,x,y,x+1,y ,flag)) - e+=add_path(heap,tp,x+1,y ,tp[rp].dist+10,6,rp,x1,y1); - if(can_move(md,x,y,x+1,y+1,flag)) - e+=add_path(heap,tp,x+1,y+1,tp[rp].dist+14,7,rp,x1,y1); - if(can_move(md,x,y,x ,y+1,flag)) - e+=add_path(heap,tp,x ,y+1,tp[rp].dist+10,0,rp,x1,y1); - if(can_move(md,x,y,x-1,y+1,flag)) - e+=add_path(heap,tp,x-1,y+1,tp[rp].dist+14,1,rp,x1,y1); - if(can_move(md,x,y,x-1,y ,flag)) - e+=add_path(heap,tp,x-1,y ,tp[rp].dist+10,2,rp,x1,y1); - if(can_move(md,x,y,x-1,y-1,flag)) - e+=add_path(heap,tp,x-1,y-1,tp[rp].dist+14,3,rp,x1,y1); - if(can_move(md,x,y,x ,y-1,flag)) - e+=add_path(heap,tp,x ,y-1,tp[rp].dist+10,4,rp,x1,y1); + if(y > 0 && !map_getcellp(md,x ,y-1,flag2)) { + f |= 4; dc[2] = (y <= y1 ? 20 : 0); + e+=add_path(heap,tp,x ,y-1,dist,rp,cost+dc[2]); // (x , y-1) + } + if(x < xs && !map_getcellp(md,x+1,y ,flag2)) { + f |= 8; dc[3] = (x >= x1 ? 20 : 0); + e+=add_path(heap,tp,x+1,y ,dist,rp,cost+dc[3]); // (x+1, y ) + } + if( (f & (2+1)) == (2+1) && !map_getcellp(md,x-1,y+1,flag2)) + e+=add_path(heap,tp,x-1,y+1,dist+4,rp,cost+dc[1]+dc[0]-6); // (x-1, y+1) + if( (f & (2+4)) == (2+4) && !map_getcellp(md,x-1,y-1,flag2)) + e+=add_path(heap,tp,x-1,y-1,dist+4,rp,cost+dc[1]+dc[2]-6); // (x-1, y-1) + if( (f & (8+4)) == (8+4) && !map_getcellp(md,x+1,y-1,flag2)) + e+=add_path(heap,tp,x+1,y-1,dist+4,rp,cost+dc[3]+dc[2]-6); // (x+1, y-1) + if( (f & (8+1)) == (8+1) && !map_getcellp(md,x+1,y+1,flag2)) + e+=add_path(heap,tp,x+1,y+1,dist+4,rp,cost+dc[3]+dc[0]-6); // (x+1, y+1) tp[rp].flag=1; if(e || heap[0]>=MAX_HEAP-5) return -1; } + if(x==x1 && y==y1) { + int len,j; + + for(len=0,i=rp;len<100 && i!=calc_index(x0,y0);i=tp[i].before,len++); + if(len==100 || len>=sizeof(wpd->path)) + return -1; + wpd->path_len=len; + wpd->path_pos=0; + wpd->path_half=0; + for(i=rp,j=len-1;j>=0;i=tp[i].before,j--) { + int dx = tp[i].x - tp[tp[i].before].x; + int dy = tp[i].y - tp[tp[i].before].y; + int dir; + if( dx == 0 ) { + dir = (dy > 0 ? 0 : 4); + } else if( dx > 0 ) { + dir = (dy == 0 ? 6 : (dy < 0 ? 5 : 7) ); + } else { + dir = (dy == 0 ? 2 : (dy > 0 ? 1 : 3) ); + } + wpd->path[j] = dir; + } +#if 0 + // test + { + int dirx[8]={0,-1,-1,-1,0,1,1,1}; + int diry[8]={1,1,0,-1,-1,-1,0,1}; + x = x0; y = y0; + for(i = 0; i < wpd->path_len; i++) { + x += dirx[ wpd->path[i] ]; + y += diry[ wpd->path[i] ]; + if( map_getcellp(md,x,y,flag2) ) { + printf("path_search_real: cannot move(%d, %d)\n", x, y); + return -1; + } + } + if( x != x1 || y != y1 ) { + printf("path_search_real: dest position is wrong. ok:(%d, %d) ng:(%d,%d)\n", x1, y1, x, y); + return -1; + } + } +#endif + return 0; + } return -1; } -- cgit v1.2.3-70-g09d2