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/map.c | 2 + src/map/map.h | 23 ++++++- src/map/mob.c | 12 ++-- src/map/path.c | 195 +++++++++++++++++++++++++++++++++----------------------- src/map/pc.c | 2 +- src/map/pet.c | 2 +- src/map/skill.c | 2 +- 7 files changed, 145 insertions(+), 93 deletions(-) (limited to 'src') diff --git a/src/map/map.c b/src/map/map.c index d1d557059..bf77e213d 100644 --- a/src/map/map.c +++ b/src/map/map.c @@ -2161,11 +2161,13 @@ int map_getcellp(struct map_data* m,int x,int y,cell_t cellchk) #ifdef CELL_NOSTACK if (type3 >= battle_config.cell_stack_limit) return 0; #endif + case CELL_CHKREACH: return (type!=1 && type!=5 && !(type2&(CELL_MOONLIT|CELL_ICEWALL))); case CELL_CHKNOPASS: #ifdef CELL_NOSTACK if (type3 >= battle_config.cell_stack_limit) return 1; #endif + case CELL_CHKNOREACH: return (type==1 || type==5 || type2&(CELL_MOONLIT|CELL_ICEWALL)); case CELL_CHKSTACK: #ifdef CELL_NOSTACK diff --git a/src/map/map.h b/src/map/map.h index 1d8790795..210398cba 100644 --- a/src/map/map.h +++ b/src/map/map.h @@ -1135,7 +1135,9 @@ typedef enum { CELL_CHKWATER, // 水場(セルタイプ3) CELL_CHKGROUND, // 地面障害物(セルタイプ5) CELL_CHKPASS, // 通過可能(セルタイプ1,5以外) + CELL_CHKREACH, // Same as PASS, but ignores the cell-stacking mod. CELL_CHKNOPASS, // 通過不可(セルタイプ1,5) + CELL_CHKNOREACH, // Same as NOPASS, but ignores the cell-stacking mod. CELL_GETTYPE, // セルタイプを返す CELL_GETCELLTYPE, CELL_CHKNPC=0x10, // タッチタイプのNPC(セルタイプ0x80フラグ) @@ -1286,8 +1288,13 @@ int map_setwaterheight(int m, char *mapname, int height); int map_waterheight(char *mapname); // path.cより -int path_search(struct walkpath_data*,int,int,int,int,int,int); -int path_search_long(struct shootpath_data *,int,int,int,int,int); +int path_search_real(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int flag,int flag2); +#define path_search(wpd,m,x0,y0,x1,y1,flag) path_search_real(wpd,m,x0,y0,x1,y1,flag,CELL_CHKNOPASS) +#define path_search2(wpd,m,x0,y0,x1,y1,flag) path_search_real(wpd,m,x0,y0,x1,y1,flag,CELL_CHKWALL) + +int path_search_long_real(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y1,int flag); +#define path_search_long(spd,m,x0,y0,x1,y1) path_search_long_real(spd,m,x0,y0,x1,y1,CELL_CHKWALL) + int path_blownpos(int m,int x0,int y0,int dx,int dy,int count); // distance related functions [Skotlex] @@ -1386,6 +1393,18 @@ extern MYSQL_ROW mapregsql_row; extern char mail_db[32]; #endif /* not TXT_ONLY */ +//Useful typedefs from jA [Skotlex] +typedef struct map_session_data TBL_PC; +typedef struct npc_data TBL_NPC; +typedef struct mob_data TBL_MOB; +typedef struct flooritem_data TBL_ITEM; +typedef struct chat_data TBL_CHAT; +typedef struct skill_unit TBL_SKILL; +typedef struct pet_data TBL_PET; + +#define BL_CAST(type_, bl , dest) \ + (((bl) == NULL || (bl)->type != type_) ? ((dest) = NULL, 0) : ((dest) = (T ## type_ *)(bl), 1)) + extern int lowest_gm_level; extern char main_chat_nick[16]; diff --git a/src/map/mob.c b/src/map/mob.c index 93198ddb4..48ed37475 100644 --- a/src/map/mob.c +++ b/src/map/mob.c @@ -604,11 +604,7 @@ int mob_can_reach(struct mob_data *md,struct block_list *bl,int range, int state easy = 1; break; } -#ifdef CELL_NOSTACK - //In no stack mode, do these path searches ignoring other players as it's just - //for reachability judging, not the actual path used. [Skotlex] - easy |= 0x30000; -#endif + if( md->bl.m != bl->m) // 違うャbプ return 0; @@ -622,7 +618,7 @@ int mob_can_reach(struct mob_data *md,struct block_list *bl,int range, int state wpd.path_len=0; wpd.path_pos=0; wpd.path_half=0; - if(path_search(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x,bl->y,easy)!=-1) + if(path_search_real(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x,bl->y,easy,CELL_CHKNOREACH)!=-1) return 1; // It judges whether it can adjoin or not. @@ -630,10 +626,10 @@ int mob_can_reach(struct mob_data *md,struct block_list *bl,int range, int state dy=abs(bl->y - md->bl.y); dx=(dx>0)?1:((dx<0)?-1:0); dy=(dy>0)?1:((dy<0)?-1:0); - if(path_search(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x-dx,bl->y-dy,easy)!=-1) + if(path_search_real(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x-dx,bl->y-dy,easy,CELL_CHKNOREACH)!=-1) return 1; for(i=0;i<9;i++){ - if(path_search(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x-1+i/3,bl->y-1+i%3,easy)!=-1) + if(path_search_real(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x-1+i/3,bl->y-1+i%3,easy, CELL_CHKNOREACH)!=-1) return 1; } return 0; 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; } diff --git a/src/map/pc.c b/src/map/pc.c index 6f015c0b9..d0abfac82 100644 --- a/src/map/pc.c +++ b/src/map/pc.c @@ -3552,7 +3552,7 @@ int pc_can_reach(struct map_session_data *sd,int x,int y) wpd.path_len=0; wpd.path_pos=0; wpd.path_half=0; - return (path_search(&wpd,sd->bl.m,sd->bl.x,sd->bl.y,x,y,0)!=-1)?1:0; + return (path_search_real(&wpd,sd->bl.m,sd->bl.x,sd->bl.y,x,y,0,CELL_CHKNOREACH)!=-1)?1:0; } // diff --git a/src/map/pet.c b/src/map/pet.c index ad9a4ddbc..4249ab1fa 100644 --- a/src/map/pet.c +++ b/src/map/pet.c @@ -95,7 +95,7 @@ static int pet_can_reach(struct pet_data *pd,int x,int y) wpd.path_len=0; wpd.path_pos=0; wpd.path_half=0; - return (path_search(&wpd,pd->bl.m,pd->bl.x,pd->bl.y,x,y,0)!=-1)?1:0; + return (path_search_real(&wpd,pd->bl.m,pd->bl.x,pd->bl.y,x,y,0,CELL_CHKNOREACH)!=-1)?1:0; } static int pet_calc_pos(struct pet_data *pd,int tx,int ty,int dir) diff --git a/src/map/skill.c b/src/map/skill.c index a4559e0c6..c8eda14ee 100644 --- a/src/map/skill.c +++ b/src/map/skill.c @@ -6534,7 +6534,7 @@ struct skill_unit_group *skill_unitsetting( struct block_list *src, int skillid, if (alive && battle_config.skill_wall_check) { //Check if there's a path between cell and center of casting. struct walkpath_data wpd; - if (path_search(&wpd,src->m,ux,uy,x,y,0x30001)==-1) + if (path_search2(&wpd,src->m,ux,uy,x,y,0x30001)==-1) alive = 0; } -- cgit v1.2.3-70-g09d2