- Added map chk cells types CELL_CHKREACH and CELL_CHKNOREACH, they are the same as their PASS/NOPASS equivalents, but will ignore the cell-stacking mod when enabled.

- Updated path.c with jA's implementation, which should make long path searching more efficient.
- Also added some typedefs from jA for the common structure types (PC/MOB/NPC, etc)


git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/trunk@5366 54d463be-8e91-2dee-dedb-b68131a5f0ec

1 files changed, 115 insertions, 80 deletions

diff --git a/src/map/path.c b/src/map/path.c
index 7cab27683..03f34ead1 100644
--- a/src/map/path.c
+++ b/src/map/path.c
@@ -7,12 +7,18 @@
 

 #include "map.h"

 #include "battle.h"

-#include "nullpo.h"

+#include "../common/nullpo.h"

 #include "../common/showmsg.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;};

+struct tmp_path { short x,y,dist,before,cost,flag;};

 #define calc_index(x,y) (((x)+(y)*MAX_WALKPATH) & (MAX_WALKPATH*MAX_WALKPATH-1))

 

 /*==========================================

@@ -23,11 +29,6 @@ static void push_heap_path(int *heap,struct tmp_path *tp,int index)
 {

 	int i,h;

 

-	if( heap == NULL || tp == NULL ){

-		ShowError("push_heap_path nullpo\n");

-		return;

-	}

-

 	heap[0]++;

 

 	for(h=heap[0]-1,i=(h-1)/2;

@@ -46,9 +47,6 @@ 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;

@@ -72,9 +70,6 @@ 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];

@@ -106,8 +101,6 @@ 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;

@@ -119,21 +112,17 @@ static int calc_cost(struct tmp_path *p,int x1,int y1)
  * 必要なら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 before,int cost)

 {

 	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);

+			tp[i].cost=cost;

 			if(tp[i].flag)

 				push_heap_path(heap,tp,i);

 			else

@@ -149,9 +138,8 @@ static int add_path(int *heap,struct tmp_path *tp,int x,int y,int dist,int dir,i
 	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].cost=cost;

 	tp[i].flag=0;

 	push_heap_path(heap,tp,i);

 

@@ -166,8 +154,6 @@ static int add_path(int *heap,struct tmp_path *tp,int x,int y,int dist,int dir,i
  */

 static int can_place(struct map_data *m,int x,int y,int flag)

 {

-	nullpo_retr(0, m);

-

 	if(map_getcellp(m,x,y,CELL_CHKPASS))

 		return 1;

 	if((flag&0x10000)&&map_getcellp(m,x,y,CELL_CHKGROUND))

@@ -186,10 +172,6 @@ static int can_place(struct map_data *m,int x,int y,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(flag&0x20000) //Flag to ignore everything, for use with Taekwon's Jump skill currently. [Skotlex] 

@@ -251,11 +233,11 @@ int path_blownpos(int m,int x0,int y0,int dx,int dy,int count)
 }

 

 /*==========================================

- *  �ﾀﾋ袮�ﾍ�?ｪｬﾊｦﾒ�ｪｫｪﾉｪｦｪｫｪ�ﾚ�ｪｹ

+ *  遠距離攻撃が可能かどうかを返す

  *------------------------------------------

  */

 #define swap(x,y) { int t; t = x; x = y; y = t; }

-int path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y1)

+int path_search_long_real(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y1,int flag)

 {

 	int dx, dy;

 	int wx = 0, wy = 0;

@@ -281,7 +263,7 @@ int path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y
 		spd->y[0] = y0;

 	}

 

-	if (map_getcellp(md,x1,y1,CELL_CHKWALL))

+	if (map_getcellp(md,x1,y1,flag))

 		return 0;

 

 	if (dx > abs(dy)) {

@@ -295,7 +277,7 @@ int path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y
 	}

 

 	while (x0 != x1 || y0 != y1) {

-		if (map_getcellp(md,x0,y0,CELL_CHKWALL))

+		if (map_getcellp(md,x0,y0,flag))

 			return 0;

 		wx += dx;

 		wy += dy;

@@ -324,11 +306,12 @@ int path_search_long(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y
  * 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_real(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int flag,int flag2)

 {

 	int heap[MAX_HEAP+1];

 	struct tmp_path tp[MAX_WALKPATH*MAX_WALKPATH];

 	int i,rp,x,y;

+	int xs,ys;

 	struct map_data *md;

 	int dx,dy;

 

@@ -337,37 +320,40 @@ int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int
 	if(!map[m].gat)

 		return -1;

 	md=&map[m];

-

-	if(x1<0 || x1>=md->xs || y1<0 || y1>=md->ys)

-		return -1;

-

 #ifdef CELL_NOSTACK

-	if (map_getcellp(md,x1,y1,CELL_CHKNOPASS) && !map_getcellp(md,x1,y1,CELL_CHKSTACK))

-		return -1;

+	//Do not check starting cell as that would get you stuck.

+	if(x0<0 || x0>=md->xs || y0<0 || y0>=md->ys)

 #else

-	if (map_getcellp(md,x1,y1,CELL_CHKNOPASS))

-		return -1;

+	if(x0<0 || x0>=md->xs || y0<0 || y0>=md->ys || map_getcellp(md,x0,y0,flag2))

 #endif

+		return -1;

+	if(x1<0 || x1>=md->xs || y1<0 || y1>=md->ys || map_getcellp(md,x1,y1,flag2))

+		return -1;

 

 	// easy

+	// この内部では、0 <= x+dx < sx, 0 <= y+dy < sy は保証されている

 	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))

+			if(map_getcellp(md,x+dx,y   ,flag2))

+				break;

+			if(map_getcellp(md,x   ,y+dy,flag2))

+				break;

+			if(map_getcellp(md,x+dx,y+dy,flag2))

 				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))

+			if(map_getcellp(md,x+dx,y   ,flag2))

 				break;

 			x+=dx;

 			wpd->path[i++]=(dx<0) ? 2 : 6;

 		} else if(y!=y1){

-			if(!can_move(md,x,y,x   ,y+dy,flag))

+			if(map_getcellp(md,x   ,y+dy,flag2))

 				break;

 			y+=dy;

 			wpd->path[i++]=(dy>0) ? 0 : 4;

@@ -381,6 +367,7 @@ int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int
 	}

 	

 #ifdef CELL_NOSTACK

+/* Should not be needed, let's try and see.

 	//If you fail by 1 cell, consider easy path successful, too. [Skotlex]

 	if (check_distance(x-x1,y-y1,1)) {

 		wpd->path_len=i;

@@ -388,6 +375,7 @@ int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int
 		wpd->path_half=0;

 		return 0;

 	}

+*/

 #endif

 	if(flag&1)

 		return -1;

@@ -398,55 +386,102 @@ int path_search(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int
 	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));

+	xs = md->xs-1; // あらかじめ１減算しておく

+	ys = md->ys-1;

 	while(1){

-		int e=0,fromdir;

+		int e=0,f=0,dist,cost,dc[4];

 

 		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;

+		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++ の時のコスト増分

+		// dc[1] : x-- の時のコスト増分

+		// dc[2] : y-- の時のコスト増分

+		// dc[3] : x++ の時のコスト増分

+

+		if(y < ys && !map_getcellp(md,x  ,y+1,flag2)) {

+			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  ,flag2)) {

+			f |= 2; dc[1] = (x <= x1 ? 20 : 0);

+			e+=add_path(heap,tp,x-1,y  ,dist,rp,cost+dc[1]); // (x-1, y  )

 		}

-		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);

+		if(y > 0  && !map_getcellp(md,x  ,y-1,flag2)) {

+			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  ,flag2)) {

+			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,flag2))

+			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,flag2))

+			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,flag2))

+			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,flag2))

+			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 -1;

 	}

+	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--) {

+			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;

+		}

+#if 0

+		// test

+		{

+			int dirx[8]={0,-1,-1,-1,0,1,1,1};

+			int diry[8]={1,1,0,-1,-1,-1,0,1};

+			x = x0; y = y0;

+			for(i = 0; i < wpd->path_len; i++) {

+				x += dirx[ wpd->path[i] ];

+				y += diry[ wpd->path[i] ];

+				if( map_getcellp(md,x,y,flag2) ) {

+					printf("path_search_real: cannot move(%d, %d)\n", x, y);

+					return -1;

+				}

+			}

+			if( x != x1 || y != y1 ) {

+				printf("path_search_real: dest position is wrong. ok:(%d, %d) ng:(%d,%d)\n", x1, y1, x, y);

+				return -1;

+			}

+		}

+#endif

+		return 0;

+	}

 	return -1;

 }