From 634aeeb9d58b01f9de6632a014a063ef0c4cf31e Mon Sep 17 00:00:00 2001 From: Chuck Miller Date: Fri, 25 Dec 2009 05:00:31 -0500 Subject: Used the "indent" C formatting program from GNU to do some clean ups The command options used was: -nbad -bap -sc -bl -blf -bli0 -cli4 -cbi0 -di5 -nbc -bls -ip2 -nut -ts4 -bap -i4 -sob -npsl --- src/map/path.c | 645 ++++++++++++++++++++++++++++++--------------------------- 1 file changed, 343 insertions(+), 302 deletions(-) (limited to 'src/map/path.c') diff --git a/src/map/path.c b/src/map/path.c index b2e0a78..a6e7535 100644 --- a/src/map/path.c +++ b/src/map/path.c @@ -14,29 +14,33 @@ //#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; + 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) +static void push_heap_path (int *heap, struct tmp_path *tp, int index) { - int i,h; + int i, h; - if( heap == NULL || tp == NULL ){ - printf("push_heap_path nullpo\n"); - return; - } + if (heap == NULL || tp == NULL) + { + printf ("push_heap_path nullpo\n"); + return; + } - heap[0]++; + heap[0]++; - for(h=heap[0]-1,i=(h-1)/2; - h>0 && tp[index].cost 0 && tp[index].cost < tp[heap[i + 1]].cost; i = (h - 1) / 2) + heap[h + 1] = heap[i + 1], h = i; + heap[h + 1] = index; } /*========================================== @@ -44,361 +48,398 @@ static void push_heap_path(int *heap,struct tmp_path *tp,int index) * costが減ったので根の方へ移動 *------------------------------------------ */ -static void update_heap_path(int *heap,struct tmp_path *tp,int index) +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;h0 && tp[index].cost 0 && tp[index].cost < tp[heap[i + 1]].cost; i = (h - 1) / 2) + heap[h + 1] = heap[i + 1], h = i; + heap[h + 1] = index; } /*========================================== * 経路探索補助heap pop *------------------------------------------ */ -static int pop_heap_path(int *heap,struct tmp_path *tp) +static int pop_heap_path (int *heap, struct tmp_path *tp) { - int i,h,k; - int ret,last; - - nullpo_retr(-1, heap); - nullpo_retr(-1, tp); - - if(heap[0]<=0) - return -1; - ret=heap[1]; - last=heap[heap[0]]; - heap[0]--; - - for(h=0,k=2;ktp[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; + int i, h, k; + int ret, last; + + nullpo_retr (-1, heap); + nullpo_retr (-1, tp); + + if (heap[0] <= 0) + return -1; + ret = heap[1]; + last = heap[heap[0]]; + heap[0]--; + + for (h = 0, k = 2; k < heap[0]; k = k * 2 + 2) + { + if (tp[heap[k + 1]].cost > tp[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) +static int calc_cost (struct tmp_path *p, int x1, int y1) { - int xd,yd; + int xd, yd; - nullpo_retr(0, p); + 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; + 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) +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; + 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) +static int can_place (struct map_data *m, int x, int y, int flag) { - int c; + int c; - nullpo_retr(0, m); + nullpo_retr (0, m); - c=read_gatp(m,x,y); + c = read_gatp (m, x, y); - if(c==1) - return 0; - if(!(flag&0x10000) && c==5) - return 0; - return 1; + 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) +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; + 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) +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; + 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 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; + 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}, +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[]) +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); + 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