From 195dffc20af1fb32c7e4119988911b72955aeabc Mon Sep 17 00:00:00 2001 From: "(no author)" <(no author)@54d463be-8e91-2dee-dedb-b68131a5f0ec> Date: Thu, 4 Nov 2004 23:25:09 +0000 Subject: git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/athena@2 54d463be-8e91-2dee-dedb-b68131a5f0ec --- src/map/path.c | 404 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 404 insertions(+) create mode 100644 src/map/path.c (limited to 'src/map/path.c') diff --git a/src/map/path.c b/src/map/path.c new file mode 100644 index 000000000..51143c943 --- /dev/null +++ b/src/map/path.c @@ -0,0 +1,404 @@ +// $Id: path.c,v 1.1.1.1 2004/09/10 17:27:00 MagicalTux Exp $ +#include +#include +#include + +#include "map.h" +#include "battle.h" +#include "nullpo.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;}; +#define calc_index(x,y) (((x)+(y)*MAX_WALKPATH) & (MAX_WALKPATH*MAX_WALKPATH-1)) + +/*========================================== + * 経路探索補助heap push + *------------------------------------------ + */ +static void push_heap_path(int *heap,struct tmp_path *tp,int index) +{ + int i,h; + + if( heap == NULL || tp == NULL ){ + printf("push_heap_path nullpo\n"); + return; + } + + heap[0]++; + + for(h=heap[0]-1,i=(h-1)/2; + h>0 && tp[index].cost0 && tp[index].costtp[heap[k]].cost) + k--; + heap[h+1]=heap[k+1], h=k; + } + if(k==heap[0]) + heap[h+1]=heap[k], h=k-1; + + for(i=(h-1)/2; + h>0 && tp[heap[i+1]].cost>tp[last].cost; + i=(h-1)/2) + heap[h+1]=heap[i+1],h=i; + heap[h+1]=last; + + return ret; +} + +/*========================================== + * 現在の点のcost計算 + *------------------------------------------ + */ +static int calc_cost(struct tmp_path *p,int x1,int y1) +{ + int xd,yd; + + nullpo_retr(0, p); + + xd=x1-p->x; + if(xd<0) xd=-xd; + yd=y1-p->y; + if(yd<0) yd=-yd; + return (xd+yd)*10+p->dist; +} + +/*========================================== + * 必要なら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) +{ + 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); + if(tp[i].flag) + push_heap_path(heap,tp,i); + else + update_heap_path(heap,tp,i); + tp[i].flag=0; + } + return 0; + } + + if(tp[i].x || tp[i].y) + return 1; + + 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].flag=0; + push_heap_path(heap,tp,i); + + return 0; +} + + +/*========================================== + * (x,y)が移動不可能地帯かどうか + * flag 0x10000 遠距離攻撃判定 + *------------------------------------------ + */ +static int can_place(struct map_data *m,int x,int y,int flag) +{ + int c; + + nullpo_retr(0, m); + + c=read_gatp(m,x,y); + + if(c==1) + return 0; + if(!(flag&0x10000) && c==5) + return 0; + return 1; +} + +/*========================================== + * (x0,y0)から(x1,y1)へ1歩で移動可能か計算 + *------------------------------------------ + */ +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(!can_place(m,x0,y0,flag)) + return 0; + if(!can_place(m,x1,y1,flag)) + return 0; + if(x0==x1 || y0==y1) + return 1; + if(!can_place(m,x0,y1,flag) || !can_place(m,x1,y0,flag)) + return 0; + return 1; +} +/*========================================== + * (x0,y0)から(dx,dy)方向へcountセル分 + * 吹き飛ばしたあとの座標を所得 + *------------------------------------------ + */ +int path_blownpos(int m,int x0,int y0,int dx,int dy,int count) +{ + struct map_data *md; + + if(!map[m].gat) + return -1; + md=&map[m]; + + if(count>15){ // 最大10マスに制限 + if(battle_config.error_log) + printf("path_blownpos: count too many %d !\n",count); + count=15; + } + if(dx>1 || dx<-1 || dy>1 || dy<-1){ + if(battle_config.error_log) + printf("path_blownpos: illeagal dx=%d or dy=%d !\n",dx,dy); + dx=(dx>=0)?1:((dx<0)?-1:0); + dy=(dy>=0)?1:((dy<0)?-1:0); + } + + while( (count--)>0 && (dx!=0 || dy!=0) ){ + if( !can_move(md,x0,y0,x0+dx,y0+dy,0) ){ + int fx=(dx!=0 && can_move(md,x0,y0,x0+dx,y0,0)); + int fy=(dy!=0 && can_move(md,x0,y0,x0,y0+dy,0)); + if( fx && fy ){ + if(rand()&1) dx=0; + else dy=0; + } + if( !fx ) dx=0; + if( !fy ) dy=0; + } + x0+=dx; + y0+=dy; + } + return (x0<<16)|y0; +} + +/*========================================== + * 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 heap[MAX_HEAP+1]; + struct tmp_path tp[MAX_WALKPATH*MAX_WALKPATH]; + int i,rp,x,y; + struct map_data *md; + int dx,dy; + + nullpo_retr(0, wpd); + + if(!map[m].gat) + return -1; + md=&map[m]; + if(x1<0 || x1>=md->xs || y1<0 || y1>=md->ys || (i=read_gatp(md,x1,y1))==1 || i==5) + return -1; + + // easy + 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)) + 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)) + break; + x+=dx; + wpd->path[i++]=(dx<0) ? 2 : 6; + } else { // y!=y1 + if(!can_move(md,x,y,x ,y+dy,flag)) + break; + y+=dy; + wpd->path[i++]=(dy>0) ? 0 : 4; + } + if(x==x1 && y==y1){ + wpd->path_len=i; + wpd->path_pos=0; + wpd->path_half=0; + return 0; + } + } + if(flag&1) + return -1; + + memset(tp,0,sizeof(tp)); + + i=calc_index(x0,y0); + 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)); + while(1){ + int e=0,fromdir; + + 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; + } + 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); + tp[rp].flag=1; + if(e || heap[0]>=MAX_HEAP-5) + return -1; + } + return -1; +} + +#ifdef PATH_STANDALONETEST +char gat[64][64]={ + {0,0,0,0,0,0,0,0,0,0}, + {0,0,0,0,0,0,0,0,0,0}, + {0,0,0,0,0,0,0,0,0,0}, + {0,0,0,0,0,0,0,0,0,0}, + {0,0,0,0,1,0,0,0,0,0}, +}; +struct map_data map[1]; + +/*========================================== + * 経路探索ルーチン単体テスト用main関数 + *------------------------------------------ + */ +void main(int argc,char *argv[]) +{ + struct walkpath_data wpd; + + map[0].gat=gat; + map[0].xs=64; + map[0].ys=64; + + path_search(&wpd,0,3,4,5,4); + path_search(&wpd,0,5,4,3,4); + path_search(&wpd,0,6,4,3,4); + path_search(&wpd,0,7,4,3,4); + path_search(&wpd,0,4,3,4,5); + path_search(&wpd,0,4,2,4,5); + path_search(&wpd,0,4,1,4,5); + path_search(&wpd,0,4,5,4,3); + path_search(&wpd,0,4,6,4,3); + path_search(&wpd,0,4,7,4,3); + path_search(&wpd,0,7,4,3,4); + path_search(&wpd,0,8,4,3,4); + path_search(&wpd,0,9,4,3,4); + path_search(&wpd,0,10,4,3,4); + path_search(&wpd,0,11,4,3,4); + path_search(&wpd,0,12,4,3,4); + path_search(&wpd,0,13,4,3,4); + path_search(&wpd,0,14,4,3,4); + path_search(&wpd,0,15,4,3,4); + path_search(&wpd,0,16,4,3,4); + path_search(&wpd,0,17,4,3,4); + path_search(&wpd,0,18,4,3,4); +} +#endif -- cgit v1.2.3-70-g09d2