summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/map/map.c2
-rw-r--r--src/map/map.h23
-rw-r--r--src/map/mob.c12
-rw-r--r--src/map/path.c195
-rw-r--r--src/map/pc.c2
-rw-r--r--src/map/pet.c2
-rw-r--r--src/map/skill.c2
7 files changed, 145 insertions, 93 deletions
diff --git a/src/map/map.c b/src/map/map.c
index d1d557059..bf77e213d 100644
--- a/src/map/map.c
+++ b/src/map/map.c
@@ -2161,11 +2161,13 @@ int map_getcellp(struct map_data* m,int x,int y,cell_t cellchk)
#ifdef CELL_NOSTACK
if (type3 >= battle_config.cell_stack_limit) return 0;
#endif
+ case CELL_CHKREACH:
return (type!=1 && type!=5 && !(type2&(CELL_MOONLIT|CELL_ICEWALL)));
case CELL_CHKNOPASS:
#ifdef CELL_NOSTACK
if (type3 >= battle_config.cell_stack_limit) return 1;
#endif
+ case CELL_CHKNOREACH:
return (type==1 || type==5 || type2&(CELL_MOONLIT|CELL_ICEWALL));
case CELL_CHKSTACK:
#ifdef CELL_NOSTACK
diff --git a/src/map/map.h b/src/map/map.h
index 1d8790795..210398cba 100644
--- a/src/map/map.h
+++ b/src/map/map.h
@@ -1135,7 +1135,9 @@ typedef enum {
CELL_CHKWATER, // 水場(セルタイプ3)
CELL_CHKGROUND, // 地面障害物(セルタイプ5)
CELL_CHKPASS, // 通過可能(セルタイプ1,5以外)
+ CELL_CHKREACH, // Same as PASS, but ignores the cell-stacking mod.
CELL_CHKNOPASS, // 通過不可(セルタイプ1,5)
+ CELL_CHKNOREACH, // Same as NOPASS, but ignores the cell-stacking mod.
CELL_GETTYPE, // セルタイプを返す
CELL_GETCELLTYPE,
CELL_CHKNPC=0x10, // タッチタイプのNPC(セルタイプ0x80フラグ)
@@ -1286,8 +1288,13 @@ int map_setwaterheight(int m, char *mapname, int height);
int map_waterheight(char *mapname);
// path.cより
-int path_search(struct walkpath_data*,int,int,int,int,int,int);
-int path_search_long(struct shootpath_data *,int,int,int,int,int);
+int path_search_real(struct walkpath_data *wpd,int m,int x0,int y0,int x1,int y1,int flag,int flag2);
+#define path_search(wpd,m,x0,y0,x1,y1,flag) path_search_real(wpd,m,x0,y0,x1,y1,flag,CELL_CHKNOPASS)
+#define path_search2(wpd,m,x0,y0,x1,y1,flag) path_search_real(wpd,m,x0,y0,x1,y1,flag,CELL_CHKWALL)
+
+int path_search_long_real(struct shootpath_data *spd,int m,int x0,int y0,int x1,int y1,int flag);
+#define path_search_long(spd,m,x0,y0,x1,y1) path_search_long_real(spd,m,x0,y0,x1,y1,CELL_CHKWALL)
+
int path_blownpos(int m,int x0,int y0,int dx,int dy,int count);
// distance related functions [Skotlex]
@@ -1386,6 +1393,18 @@ extern MYSQL_ROW mapregsql_row;
extern char mail_db[32];
#endif /* not TXT_ONLY */
+//Useful typedefs from jA [Skotlex]
+typedef struct map_session_data TBL_PC;
+typedef struct npc_data TBL_NPC;
+typedef struct mob_data TBL_MOB;
+typedef struct flooritem_data TBL_ITEM;
+typedef struct chat_data TBL_CHAT;
+typedef struct skill_unit TBL_SKILL;
+typedef struct pet_data TBL_PET;
+
+#define BL_CAST(type_, bl , dest) \
+ (((bl) == NULL || (bl)->type != type_) ? ((dest) = NULL, 0) : ((dest) = (T ## type_ *)(bl), 1))
+
extern int lowest_gm_level;
extern char main_chat_nick[16];
diff --git a/src/map/mob.c b/src/map/mob.c
index 93198ddb4..48ed37475 100644
--- a/src/map/mob.c
+++ b/src/map/mob.c
@@ -604,11 +604,7 @@ int mob_can_reach(struct mob_data *md,struct block_list *bl,int range, int state
easy = 1;
break;
}
-#ifdef CELL_NOSTACK
- //In no stack mode, do these path searches ignoring other players as it's just
- //for reachability judging, not the actual path used. [Skotlex]
- easy |= 0x30000;
-#endif
+
if( md->bl.m != bl->m) // 違うャbプ
return 0;
@@ -622,7 +618,7 @@ int mob_can_reach(struct mob_data *md,struct block_list *bl,int range, int state
wpd.path_len=0;
wpd.path_pos=0;
wpd.path_half=0;
- if(path_search(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x,bl->y,easy)!=-1)
+ if(path_search_real(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x,bl->y,easy,CELL_CHKNOREACH)!=-1)
return 1;
// It judges whether it can adjoin or not.
@@ -630,10 +626,10 @@ int mob_can_reach(struct mob_data *md,struct block_list *bl,int range, int state
dy=abs(bl->y - md->bl.y);
dx=(dx>0)?1:((dx<0)?-1:0);
dy=(dy>0)?1:((dy<0)?-1:0);
- if(path_search(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x-dx,bl->y-dy,easy)!=-1)
+ if(path_search_real(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x-dx,bl->y-dy,easy,CELL_CHKNOREACH)!=-1)
return 1;
for(i=0;i<9;i++){
- if(path_search(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x-1+i/3,bl->y-1+i%3,easy)!=-1)
+ if(path_search_real(&wpd,md->bl.m,md->bl.x,md->bl.y,bl->x-1+i/3,bl->y-1+i%3,easy, CELL_CHKNOREACH)!=-1)
return 1;
}
return 0;
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; // あらかじめ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;
}
diff --git a/src/map/pc.c b/src/map/pc.c
index 6f015c0b9..d0abfac82 100644
--- a/src/map/pc.c
+++ b/src/map/pc.c
@@ -3552,7 +3552,7 @@ int pc_can_reach(struct map_session_data *sd,int x,int y)
wpd.path_len=0;
wpd.path_pos=0;
wpd.path_half=0;
- return (path_search(&wpd,sd->bl.m,sd->bl.x,sd->bl.y,x,y,0)!=-1)?1:0;
+ return (path_search_real(&wpd,sd->bl.m,sd->bl.x,sd->bl.y,x,y,0,CELL_CHKNOREACH)!=-1)?1:0;
}
//
diff --git a/src/map/pet.c b/src/map/pet.c
index ad9a4ddbc..4249ab1fa 100644
--- a/src/map/pet.c
+++ b/src/map/pet.c
@@ -95,7 +95,7 @@ static int pet_can_reach(struct pet_data *pd,int x,int y)
wpd.path_len=0;
wpd.path_pos=0;
wpd.path_half=0;
- return (path_search(&wpd,pd->bl.m,pd->bl.x,pd->bl.y,x,y,0)!=-1)?1:0;
+ return (path_search_real(&wpd,pd->bl.m,pd->bl.x,pd->bl.y,x,y,0,CELL_CHKNOREACH)!=-1)?1:0;
}
static int pet_calc_pos(struct pet_data *pd,int tx,int ty,int dir)
diff --git a/src/map/skill.c b/src/map/skill.c
index a4559e0c6..c8eda14ee 100644
--- a/src/map/skill.c
+++ b/src/map/skill.c
@@ -6534,7 +6534,7 @@ struct skill_unit_group *skill_unitsetting( struct block_list *src, int skillid,
if (alive && battle_config.skill_wall_check) {
//Check if there's a path between cell and center of casting.
struct walkpath_data wpd;
- if (path_search(&wpd,src->m,ux,uy,x,y,0x30001)==-1)
+ if (path_search2(&wpd,src->m,ux,uy,x,y,0x30001)==-1)
alive = 0;
}