From b11bf6e1604097711291265f927e79e8f2af5c54 Mon Sep 17 00:00:00 2001 From: greenboxal2 Date: Sun, 25 Nov 2012 21:20:43 +0000 Subject: Applied AStyle code formating as discussed on tid:74602. Removed /SAFESEH option from MSVC11 projects. git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/trunk@16968 54d463be-8e91-2dee-dedb-b68131a5f0ec --- src/map/path.c | 686 ++++++++++++++++++++++++++++----------------------------- 1 file changed, 340 insertions(+), 346 deletions(-) (limited to 'src/map/path.c') diff --git a/src/map/path.c b/src/map/path.c index 4505efcaa..4ccb73519 100644 --- a/src/map/path.c +++ b/src/map/path.c @@ -17,14 +17,15 @@ #define MAX_HEAP 150 -struct tmp_path { short x,y,dist,before,cost,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)) -const char walk_choices [3][3] = -{ - {1,0,7}, - {2,-1,6}, - {3,4,5}, +const char walk_choices [3][3] = { + {1,0,7}, + {2,-1,6}, + {3,4,5}, }; /*========================================== @@ -32,15 +33,15 @@ const char walk_choices [3][3] = *------------------------------------------*/ static void push_heap_path(int *heap,struct tmp_path *tp,int index) { - int i,h; + int i,h; - h = heap[0]; - heap[0]++; + h = heap[0]; + heap[0]++; - 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; + 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[h+1] = index; } /*========================================== @@ -49,19 +50,18 @@ static void push_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; + int i,h; - ARR_FIND( 0, heap[0], h, heap[h+1] == index ); - if( h == heap[0] ) - { - ShowError("update_heap_path bug\n"); - exit(EXIT_FAILURE); - } + ARR_FIND(0, heap[0], h, heap[h+1] == index); + if (h == heap[0]) { + ShowError("update_heap_path bug\n"); + exit(EXIT_FAILURE); + } - 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; + 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[h+1] = index; } /*========================================== @@ -69,31 +69,30 @@ static void update_heap_path(int *heap,struct tmp_path *tp,int index) *------------------------------------------*/ static int pop_heap_path(int *heap,struct tmp_path *tp) { - int i,h,k; - int ret,last; + int i,h,k; + int ret,last; - if( heap[0] <= 0 ) - return -1; - ret = heap[1]; - last = heap[heap[0]]; - heap[0]--; + 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; - } + 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; + 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; + 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; + heap[h+1]=last; - return ret; + return ret; } /*========================================== @@ -101,9 +100,9 @@ static int pop_heap_path(int *heap,struct tmp_path *tp) *------------------------------------------*/ static int calc_cost(struct tmp_path *p,int x1,int y1) { - int xd = abs(x1 - p->x); - int yd = abs(y1 - p->y); - return (xd + yd)*10 + p->dist; + int xd = abs(x1 - p->x); + int yd = abs(y1 - p->y); + return (xd + yd)*10 + p->dist; } /*========================================== @@ -111,38 +110,36 @@ static int calc_cost(struct tmp_path *p,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; - - 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].before = before; - tp[i].cost = cost; - 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].before = before; - tp[i].cost = cost; - tp[i].flag = 0; - push_heap_path(heap,tp,i); - - return 0; + int i; + + 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].before = before; + tp[i].cost = cost; + 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].before = before; + tp[i].cost = cost; + tp[i].flag = 0; + push_heap_path(heap,tp,i); + + return 0; } /*========================================== @@ -151,47 +148,45 @@ static int add_path(int *heap,struct tmp_path *tp,int x,int y,int dist,int befor *------------------------------------------*/ int path_blownpos(int m,int x0,int y0,int dx,int dy,int count) { - struct map_data *md; - - if( !map[m].cell ) - return -1; - md = &map[m]; - - if( count>25 ){ //Cap to prevent too much processing...? - ShowWarning("path_blownpos: count too many %d !\n",count); - count=25; - } - if( dx > 1 || dx < -1 || dy > 1 || dy < -1 ){ - ShowError("path_blownpos: illegal 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( !map_getcellp(md,x0+dx,y0+dy,CELL_CHKPASS) ) - {// attempt partial movement - int fx = ( dx != 0 && map_getcellp(md,x0+dx,y0,CELL_CHKPASS) ); - int fy = ( dy != 0 && map_getcellp(md,x0,y0+dy,CELL_CHKPASS) ); - if( fx && fy ) - { - if(rnd()&1) - dx=0; - else - dy=0; - } - if( !fx ) - dx=0; - if( !fy ) - dy=0; - } - - x0 += dx; - y0 += dy; - count--; - } - - return (x0<<16)|y0; //TODO: use 'struct point' here instead? + struct map_data *md; + + if (!map[m].cell) + return -1; + md = &map[m]; + + if (count>25) { //Cap to prevent too much processing...? + ShowWarning("path_blownpos: count too many %d !\n",count); + count=25; + } + if (dx > 1 || dx < -1 || dy > 1 || dy < -1) { + ShowError("path_blownpos: illegal 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 (!map_getcellp(md,x0+dx,y0+dy,CELL_CHKPASS)) { + // attempt partial movement + int fx = (dx != 0 && map_getcellp(md,x0+dx,y0,CELL_CHKPASS)); + int fy = (dy != 0 && map_getcellp(md,x0,y0+dy,CELL_CHKPASS)); + if (fx && fy) { + if (rnd()&1) + dx=0; + else + dy=0; + } + if (!fx) + dx=0; + if (!fy) + dy=0; + } + + x0 += dx; + y0 += dy; + count--; + } + + return (x0<<16)|y0; //TODO: use 'struct point' here instead? } /*========================================== @@ -199,69 +194,67 @@ int path_blownpos(int m,int x0,int y0,int dx,int dy,int count) *------------------------------------------*/ bool path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y1,cell_chk cell) { - int dx, dy; - int wx = 0, wy = 0; - int weight; - struct map_data *md; - struct shootpath_data s_spd; - - if( spd == NULL ) - spd = &s_spd; // use dummy output variable - - if (!map[m].cell) - return false; - md = &map[m]; - - dx = (x1 - x0); - if (dx < 0) { - swap(x0, x1); - swap(y0, y1); - dx = -dx; - } - dy = (y1 - y0); - - spd->rx = spd->ry = 0; - spd->len = 1; - spd->x[0] = x0; - spd->y[0] = y0; - - if (map_getcellp(md,x1,y1,cell)) - return false; - - if (dx > abs(dy)) { - weight = dx; - spd->ry = 1; - } else { - weight = abs(y1 - y0); - spd->rx = 1; - } - - while (x0 != x1 || y0 != y1) - { - if (map_getcellp(md,x0,y0,cell)) - return false; - wx += dx; - wy += dy; - if (wx >= weight) { - wx -= weight; - x0++; - } - if (wy >= weight) { - wy -= weight; - y0++; - } else if (wy < 0) { - wy += weight; - y0--; - } - if( spd->lenx[spd->len] = x0; - spd->y[spd->len] = y0; - spd->len++; - } - } - - return true; + int dx, dy; + int wx = 0, wy = 0; + int weight; + struct map_data *md; + struct shootpath_data s_spd; + + if (spd == NULL) + spd = &s_spd; // use dummy output variable + + if (!map[m].cell) + return false; + md = &map[m]; + + dx = (x1 - x0); + if (dx < 0) { + swap(x0, x1); + swap(y0, y1); + dx = -dx; + } + dy = (y1 - y0); + + spd->rx = spd->ry = 0; + spd->len = 1; + spd->x[0] = x0; + spd->y[0] = y0; + + if (map_getcellp(md,x1,y1,cell)) + return false; + + if (dx > abs(dy)) { + weight = dx; + spd->ry = 1; + } else { + weight = abs(y1 - y0); + spd->rx = 1; + } + + while (x0 != x1 || y0 != y1) { + if (map_getcellp(md,x0,y0,cell)) + return false; + wx += dx; + wy += dy; + if (wx >= weight) { + wx -= weight; + x0++; + } + if (wy >= weight) { + wy -= weight; + y0++; + } else if (wy < 0) { + wy += weight; + y0--; + } + if (spd->lenx[spd->len] = x0; + spd->y[spd->len] = y0; + spd->len++; + } + } + + return true; } /*========================================== @@ -272,152 +265,154 @@ bool path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int *------------------------------------------*/ bool path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int flag,cell_chk cell) { - int heap[MAX_HEAP+1]; - struct tmp_path tp[MAX_WALKPATH*MAX_WALKPATH]; - register int i,j,len,x,y,dx,dy; - int rp,xs,ys; - struct map_data *md; - struct walkpath_data s_wpd; + int heap[MAX_HEAP+1]; + struct tmp_path tp[MAX_WALKPATH*MAX_WALKPATH]; + register int i,j,len,x,y,dx,dy; + int rp,xs,ys; + struct map_data *md; + struct walkpath_data s_wpd; - if( wpd == NULL ) - wpd = &s_wpd; // use dummy output variable + if (wpd == NULL) + wpd = &s_wpd; // use dummy output variable - if( !map[m].cell ) - return false; - md = &map[m]; + if (!map[m].cell) + return false; + md = &map[m]; #ifdef CELL_NOSTACK - //Do not check starting cell as that would get you stuck. - if( x0 < 0 || x0 >= md->xs || y0 < 0 || y0 >= md->ys ) + //Do not check starting cell as that would get you stuck. + if (x0 < 0 || x0 >= md->xs || y0 < 0 || y0 >= md->ys) #else - if( x0 < 0 || x0 >= md->xs || y0 < 0 || y0 >= md->ys /*|| map_getcellp(md,x0,y0,cell)*/ ) + if (x0 < 0 || x0 >= md->xs || y0 < 0 || y0 >= md->ys /*|| map_getcellp(md,x0,y0,cell)*/) #endif - return false; - if( x1 < 0 || x1 >= md->xs || y1 < 0 || y1 >= md->ys || map_getcellp(md,x1,y1,cell) ) - return false; - - // calculate (sgn(x1-x0), sgn(y1-y0)) - dx = ((dx = x1-x0)) ? ((dx<0) ? -1 : 1) : 0; - dy = ((dy = y1-y0)) ? ((dy<0) ? -1 : 1) : 0; - - // try finding direct path to target - x = x0; - y = y0; - i = 0; - while( i < ARRAYLENGTH(wpd->path) ) - { - wpd->path[i] = walk_choices[-dy + 1][dx + 1]; - i++; - - x += dx; - y += dy; - - if( x == x1 ) dx = 0; - if( y == y1 ) dy = 0; - - if( dx == 0 && dy == 0 ) - break; // success - if( map_getcellp(md,x,y,cell) ) - break; // obstacle = failure - } - - if( x == x1 && y == y1 ) - { //easy path successful. - wpd->path_len = i; - wpd->path_pos = 0; - return true; - } - - if( flag&1 ) - return false; - - memset(tp,0,sizeof(tp)); - - i=calc_index(x0,y0); - tp[i].x=x0; - tp[i].y=y0; - tp[i].dist=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)); + return false; + if (x1 < 0 || x1 >= md->xs || y1 < 0 || y1 >= md->ys || map_getcellp(md,x1,y1,cell)) + return false; + + // calculate (sgn(x1-x0), sgn(y1-y0)) + dx = ((dx = x1-x0)) ? ((dx<0) ? -1 : 1) : 0; + dy = ((dy = y1-y0)) ? ((dy<0) ? -1 : 1) : 0; + + // try finding direct path to target + x = x0; + y = y0; + i = 0; + while (i < ARRAYLENGTH(wpd->path)) { + wpd->path[i] = walk_choices[-dy + 1][dx + 1]; + i++; + + x += dx; + y += dy; + + if (x == x1) dx = 0; + if (y == y1) dy = 0; + + if (dx == 0 && dy == 0) + break; // success + if (map_getcellp(md,x,y,cell)) + break; // obstacle = failure + } + + if (x == x1 && y == y1) { + //easy path successful. + wpd->path_len = i; + wpd->path_pos = 0; + return true; + } + + if (flag&1) + return false; + + memset(tp,0,sizeof(tp)); + + i=calc_index(x0,y0); + tp[i].x=x0; + tp[i].y=y0; + tp[i].dist=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; // Place by subtracting a pre- - ys = md->ys-1; - - for(;;) - { - int e=0,f=0,dist,cost,dc[4]={0,0,0,0}; - - if(heap[0]==0) - return false; - 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++ Incremental cost at the time - // dc[1] : x-- - // dc[2] : y-- - // dc[3] : x++ - - if(y < ys && !map_getcellp(md,x ,y+1,cell)) { - 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 ,cell)) { - f |= 2; dc[1] = (x <= x1 ? 20 : 0); - e+=add_path(heap,tp,x-1,y ,dist,rp,cost+dc[1]); // (x-1, y ) - } - if(y > 0 && !map_getcellp(md,x ,y-1,cell)) { - 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 ,cell)) { - 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,cell)) - 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,cell)) - 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,cell)) - 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,cell)) - 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 false; - } - - if( !(x==x1 && y==y1) ) // will never happen... - return false; - - 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 false; - - wpd->path_len = len; - wpd->path_pos = 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; - } - - return true; + ys = md->ys-1; + + for (;;) { + int e=0,f=0,dist,cost,dc[4]= {0,0,0,0}; + + if (heap[0]==0) + return false; + 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++ Incremental cost at the time + // dc[1] : x-- + // dc[2] : y-- + // dc[3] : x++ + + if (y < ys && !map_getcellp(md,x ,y+1,cell)) { + 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 ,cell)) { + f |= 2; + dc[1] = (x <= x1 ? 20 : 0); + e+=add_path(heap,tp,x-1,y ,dist,rp,cost+dc[1]); // (x-1, y ) + } + if (y > 0 && !map_getcellp(md,x ,y-1,cell)) { + 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 ,cell)) { + 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,cell)) + 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,cell)) + 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,cell)) + 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,cell)) + 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 false; + } + + if (!(x==x1 && y==y1)) // will never happen... + return false; + + 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 false; + + wpd->path_len = len; + wpd->path_pos = 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; + } + + return true; } @@ -425,40 +420,39 @@ bool path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int int check_distance(int dx, int dy, int distance) { #ifdef CIRCULAR_AREA - //In this case, we just do a square comparison. Add 1 tile grace for diagonal range checks. - return (dx*dx + dy*dy <= distance*distance + (dx&&dy?1:0)); + //In this case, we just do a square comparison. Add 1 tile grace for diagonal range checks. + return (dx*dx + dy*dy <= distance*distance + (dx&&dy?1:0)); #else - if (dx < 0) dx = -dx; - if (dy < 0) dy = -dy; - return ((dx> 8 ); + unsigned int min, max; + + if (dx < 0) dx = -dx; + if (dy < 0) dy = -dy; + //There appears to be something wrong with the aproximation below when either dx/dy is 0! [Skotlex] + if (dx == 0) return dy; + if (dy == 0) return dx; + + if (dx < dy) { + min = dx; + max = dy; + } else { + min = dy; + max = dx; + } + // coefficients equivalent to ( 123/128 * max ) and ( 51/128 * min ) + return (((max << 8) + (max << 3) - (max << 4) - (max << 1) + + (min << 7) - (min << 5) + (min << 3) - (min << 1)) >> 8); #else - if (dx < 0) dx = -dx; - if (dy < 0) dy = -dy; - return (dx