diff options
author | Dennis Friis <peavey@placid.dk> | 2008-11-03 07:00:17 +0000 |
---|---|---|
committer | Dennis Friis <peavey@placid.dk> | 2008-11-03 07:00:17 +0000 |
commit | a7f3726a0a7f16bccb664871fe35e8d2f2572f00 (patch) | |
tree | 52d1d2d53186ea4a8bbeb0c879f7494a9771fde7 /misc/src/map/path.c | |
parent | d569cd100a2f60ec99104a83c1e54306f94dd06f (diff) | |
download | tmwa-a7f3726a0a7f16bccb664871fe35e8d2f2572f00.tar.gz tmwa-a7f3726a0a7f16bccb664871fe35e8d2f2572f00.tar.bz2 tmwa-a7f3726a0a7f16bccb664871fe35e8d2f2572f00.tar.xz tmwa-a7f3726a0a7f16bccb664871fe35e8d2f2572f00.zip |
Do a bit of cleanup I never got around to do, before moving from my repo to sf.net
Diffstat (limited to 'misc/src/map/path.c')
-rw-r--r-- | misc/src/map/path.c | 404 |
1 files changed, 0 insertions, 404 deletions
diff --git a/misc/src/map/path.c b/misc/src/map/path.c deleted file mode 100644 index b2e0a78..0000000 --- a/misc/src/map/path.c +++ /dev/null @@ -1,404 +0,0 @@ -// $Id: path.c,v 1.1.1.1 2004/09/10 17:27:00 MagicalTux Exp $ -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -#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].cost<tp[heap[i+1]].cost; - i=(h-1)/2) - heap[h+1]=heap[i+1],h=i; - heap[h+1]=index; -} - -/*========================================== - * 経路探索補助heap update - * costが減ったので根の方へ移動 - *------------------------------------------ - */ -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;h<heap[0];h++) - if(heap[h+1]==index) - break; - if(h==heap[0]){ - fprintf(stderr,"update_heap_path bug\n"); - exit(1); - } - for(i=(h-1)/2; - h>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) -{ - 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) -{ - 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 |