summaryrefslogtreecommitdiff
path: root/src/map/path.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/map/path.c')
-rw-r--r--src/map/path.c686
1 files changed, 346 insertions, 340 deletions
diff --git a/src/map/path.c b/src/map/path.c
index 4ccb73519..4505efcaa 100644
--- a/src/map/path.c
+++ b/src/map/path.c
@@ -17,15 +17,14 @@
#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},
};
/*==========================================
@@ -33,15 +32,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;
}
/*==========================================
@@ -50,18 +49,19 @@ 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,30 +69,31 @@ 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;
}
/*==========================================
@@ -100,9 +101,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;
}
/*==========================================
@@ -110,36 +111,38 @@ 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;
}
/*==========================================
@@ -148,45 +151,47 @@ 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?
}
/*==========================================
@@ -194,67 +199,69 @@ 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->len<MAX_WALKPATH) {
- spd->x[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->len<MAX_WALKPATH )
+ {
+ spd->x[spd->len] = x0;
+ spd->y[spd->len] = y0;
+ spd->len++;
+ }
+ }
+
+ return true;
}
/*==========================================
@@ -265,154 +272,152 @@ 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;
}
@@ -420,39 +425,40 @@ 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<dy?dy:dx) <= distance);
+ if (dx < 0) dx = -dx;
+ if (dy < 0) dy = -dy;
+ return ((dx<dy?dy:dx) <= distance);
#endif
}
unsigned int distance(int dx, int dy)
{
#ifdef CIRCULAR_AREA
- 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);
+ 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<dy?dy:dx);
+ if (dx < 0) dx = -dx;
+ if (dy < 0) dy = -dy;
+ return (dx<dy?dy:dx);
#endif
}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-11-10 01:27:23 +0000