* No cell stacking implemented (official version)

- Split config cell_stack_limit into custom_cell_stack_limit (previous feature) and official_cell_stack_limit (see below)
- Expanded map_count_oncell by a flag parameter, currently only one flag is supported: only count standing units (needed for official cell stack feature)
- Added a new function map_closest_freecell that will return the closest free cell using the same order that official servers use
- Monsters will now actively search for a free cell when starting to walk randomly and when unlocking target
- When any unit finishes walking (regularly) and is not on a free cell, it will now actively search for a free cell
- Step actions will be delayed until a suitable cell was found, they will even be executed when the player walked slightly out of attack range
- Monsters will now stop instantly if their target is completely non-existent
  * This is mainly for looters that had their loot taken
  * Hide and most other situations still use the configuration setting monster_chase_refresh

Mega Thanks to Playtester

9 files changed, 147 insertions, 29 deletions

diff --git a/src/map/battle.c b/src/map/battle.c
index 903414f90..66926e037 100644
--- a/src/map/battle.c
+++ b/src/map/battle.c
@@ -6639,7 +6639,8 @@ static const struct battle_data {
 	{ "bone_drop",                          &battle_config.bone_drop,                       0,      0,      2,              },
 	{ "buyer_name",                         &battle_config.buyer_name,                      1,      0,      1,              },
 	{ "skill_wall_check",                   &battle_config.skill_wall_check,                1,      0,      1,              },
-	{ "cell_stack_limit",                   &battle_config.cell_stack_limit,                1,      1,      255,            },
+	{ "official_cell_stack_limit",          &battle_config.official_cell_stack_limit,       1,      1,      255,            },

+	{ "custom_cell_stack_limit",            &battle_config.custom_cell_stack_limit,         1,      1,      255,            },

 	{ "dancing_weaponswitch_fix",           &battle_config.dancing_weaponswitch_fix,        1,      0,      1,              },
 
 // eAthena additions
@@ -7108,9 +7109,9 @@ void battle_adjust_conf(void) {
 #endif
 
 
-#ifndef CELL_NOSTACK
-	if (battle_config.cell_stack_limit != 1)
-		ShowWarning("Battle setting 'cell_stack_limit' takes no effect as this server was compiled without Cell Stack Limit support (CELL_NOSTACK).\n");
+#ifndef CELL_NOSTACK

+	if (battle_config.custom_cell_stack_limit != 1)

+		ShowWarning("Battle setting 'custom_cell_stack_limit' takes no effect as this server was compiled without Cell Stack Limit support.\n");

 #endif
 }
 
diff --git a/src/map/battle.h b/src/map/battle.h
index 7633691a8..cef54f42a 100644
--- a/src/map/battle.h
+++ b/src/map/battle.h
@@ -381,7 +381,8 @@ struct Battle_Config {
 	int allow_skill_without_day; // [Komurka]
 	int allow_es_magic_pc; // [Skotlex]
 	int skill_wall_check; // [Skotlex]
-	int cell_stack_limit; // [Skotlex]
+	int official_cell_stack_limit; // [Playtester]

+	int custom_cell_stack_limit; // [Skotlex]
 	int skill_caster_check; // [Skotlex]
 	int sc_castcancel; // [Skotlex]
 	int pc_sc_def_rate; // [Skotlex]
diff --git a/src/map/map.c b/src/map/map.c
index bb3b17822..b3efe7c57 100644
--- a/src/map/map.c
+++ b/src/map/map.c
@@ -395,9 +395,11 @@ int map_moveblock(struct block_list *bl, int x1, int y1, int64 tick) {
 
 /*==========================================
  * Counts specified number of objects on given cell.
+  * flag:

+ *		0x1 - only count standing units
  * TODO: merge with bl_getall_area
  *------------------------------------------*/
-int map_count_oncell(int16 m, int16 x, int16 y, int type) {
+int map_count_oncell(int16 m, int16 x, int16 y, int type, int flag) {
 	int bx,by;
 	struct block_list *bl;
 	int count = 0;
@@ -410,13 +412,27 @@ int map_count_oncell(int16 m, int16 x, int16 y, int type) {
 
 	if (type&~BL_MOB)
 		for( bl = map->list[m].block[bx+by*map->list[m].bxs] ; bl != NULL ; bl = bl->next )
-			if(bl->x == x && bl->y == y && bl->type&type)
-				count++;
+			if(bl->x == x && bl->y == y && bl->type&type) {

+				if(flag&1) {

+					struct unit_data *ud = unit->bl2ud(bl);

+					if(!ud || ud->walktimer == INVALID_TIMER)

+						count++;

+				} else {

+					count++;

+				}

+			}
 
 	if (type&BL_MOB)
 		for( bl = map->list[m].block_mob[bx+by*map->list[m].bxs] ; bl != NULL ; bl = bl->next )
-			if(bl->x == x && bl->y == y)
-				count++;
+			if(bl->x == x && bl->y == y) {

+				if(flag&1) {

+					struct unit_data *ud = unit->bl2ud(bl);

+					if(!ud || ud->walktimer == INVALID_TIMER)

+						count++;

+				} else {

+					count++;

+				}

+			}
 
 	return count;
 }
@@ -1379,7 +1395,7 @@ int map_searchrandfreecell(int16 m,int16 *x,int16 *y,int stack) {
 			if(map->getcell(m,j+*x,i+*y,CELL_CHKNOPASS) && !map->getcell(m,j+*x,i+*y,CELL_CHKICEWALL))
 				continue;
 			//Avoid item stacking to prevent against exploits. [Skotlex]
-			if(stack && map->count_oncell(m,j+*x,i+*y, BL_ITEM) > stack)
+			if(stack && map->count_oncell(m,j+*x,i+*y, BL_ITEM, 0) > stack)
 				continue;
 			free_cells[free_cell][0] = j+*x;
 			free_cells[free_cell++][1] = i+*y;
@@ -1472,6 +1488,85 @@ int map_search_freecell(struct block_list *src, int16 m, int16 *x,int16 *y, int1
 	return 0;
 }
 
+/*==========================================

+ * Locates the closest, walkable cell with no blocks of a certain type on it

+ * Returns true on success and sets x and y to cell found.

+ * Otherwise returns false and x and y are not changed.

+ * type: Types of block to count

+ * flag: 

+ *		0x1 - only count standing units

+ *------------------------------------------*/

+bool map_closest_freecell(int16 m, int16 *x, int16 *y, int type, int flag)

+{

+	uint8 dir = 6;

+	int16 tx = *x;

+	int16 ty = *y;

+	int costrange = 10;

+

+	if(!map->count_oncell(m, tx, ty, type, flag))

+		return true; //Current cell is free

+

+	//Algorithm only works up to costrange of 34

+	while(costrange <= 34) {

+		short dx = dirx[dir];

+		short dy = diry[dir];

+

+		//Linear search

+		if(dir%2 == 0 && costrange%MOVE_COST == 0) {

+			tx = *x+dx*(costrange/MOVE_COST);

+			ty = *y+dy*(costrange/MOVE_COST);

+			if(!map->count_oncell(m, tx, ty, type, flag) && map->getcell(m,tx,ty,CELL_CHKPASS)) {

+				*x = tx;

+				*y = ty;

+				return true;

+			}

+		} 

+		//Full diagonal search

+		else if(dir%2 == 1 && costrange%MOVE_DIAGONAL_COST == 0) {

+			tx = *x+dx*(costrange/MOVE_DIAGONAL_COST);

+			ty = *y+dy*(costrange/MOVE_DIAGONAL_COST);

+			if(!map->count_oncell(m, tx, ty, type, flag) && map->getcell(m,tx,ty,CELL_CHKPASS)) {

+				*x = tx;

+				*y = ty;

+				return true;

+			}

+		}

+		//One cell diagonal, rest linear (TODO: Find a better algorithm for this)

+		else if(dir%2 == 1 && costrange%MOVE_COST == 4) {

+			tx = *x+dx*((dir%4==3)?(costrange/MOVE_COST):1);

+			ty = *y+dy*((dir%4==1)?(costrange/MOVE_COST):1);

+			if(!map->count_oncell(m, tx, ty, type, flag) && map->getcell(m,tx,ty,CELL_CHKPASS)) {

+				*x = tx;

+				*y = ty;

+				return true;

+			}

+			tx = *x+dx*((dir%4==1)?(costrange/MOVE_COST):1);

+			ty = *y+dy*((dir%4==3)?(costrange/MOVE_COST):1);

+			if(!map->count_oncell(m, tx, ty, type, flag) && map->getcell(m,tx,ty,CELL_CHKPASS)) {

+				*x = tx;

+				*y = ty;

+				return true;

+			}

+		}

+

+		//Get next direction

+		if (dir == 5) {

+			//Diagonal search complete, repeat with higher cost range

+			if(costrange == 14) costrange += 6;

+			else if(costrange == 28 || costrange >= 38) costrange += 2;

+			else costrange += 4;

+			dir = 6;

+		} else if (dir == 4) {

+			//Linear search complete, switch to diagonal directions

+			dir = 7;

+		} else {

+			dir = (dir+2)%8;

+		}

+	}

+

+	return false;

+}
+
 /*==========================================
  * Add an item to location (m,x,y)
  * Parameters
@@ -2592,21 +2687,21 @@ int map_getcellp(struct map_data* m,int16 x,int16 y,cell_chk cellchk) {
 		// special checks
 	case CELL_CHKPASS:
 #ifdef CELL_NOSTACK
-		if (cell.cell_bl >= battle_config.cell_stack_limit) return 0;
+		if (cell.cell_bl >= battle_config.custom_cell_stack_limit) return 0;
 #endif
 	case CELL_CHKREACH:
 		return (cell.walkable);
 
 	case CELL_CHKNOPASS:
 #ifdef CELL_NOSTACK
-		if (cell.cell_bl >= battle_config.cell_stack_limit) return 1;
+		if (cell.cell_bl >= battle_config.custom_cell_stack_limit) return 1;
 #endif
 	case CELL_CHKNOREACH:
 		return (!cell.walkable);
 
 	case CELL_CHKSTACK:
 #ifdef CELL_NOSTACK
-		return (cell.cell_bl >= battle_config.cell_stack_limit);
+		return (cell.cell_bl >= battle_config.custom_cell_stack_limit);
 #else
 		return 0;
 #endif
@@ -6000,6 +6095,7 @@ void map_defaults(void) {
 	// search and creation
 	map->get_new_object_id = map_get_new_object_id;
 	map->search_freecell = map_search_freecell;
+	map->closest_freecell = map_closest_freecell;
 	//
 	map->quit = map_quit;
 	// npc
diff --git a/src/map/map.h b/src/map/map.h
index 5468016b4..1766220af 100644
--- a/src/map/map.h
+++ b/src/map/map.h
@@ -917,11 +917,12 @@ struct map_interface {
 	int (*delblock) (struct block_list* bl);
 	int (*moveblock) (struct block_list *bl, int x1, int y1, int64 tick);
 	//blocklist nb in one cell
-	int (*count_oncell) (int16 m,int16 x,int16 y,int type);
+	int (*count_oncell) (int16 m,int16 x,int16 y,int type,int flag);
 	struct skill_unit * (*find_skill_unit_oncell) (struct block_list* target,int16 x,int16 y,uint16 skill_id,struct skill_unit* out_unit, int flag);
 	// search and creation
 	int (*get_new_object_id) (void);
 	int (*search_freecell) (struct block_list *src, int16 m, int16 *x, int16 *y, int16 rx, int16 ry, int flag);
+	bool (*closest_freecell) (int16 m, int16 *x, int16 *y, int type, int flag);
 	//
 	int (*quit) (struct map_session_data *sd);
 	// npc
diff --git a/src/map/mob.c b/src/map/mob.c
index 23706d293..c05f4c4a2 100644
--- a/src/map/mob.c
+++ b/src/map/mob.c
@@ -1303,6 +1303,10 @@ int mob_unlocktarget(struct mob_data *md, int64 tick) {
 		md->ud.target_to = 0;
 		unit->set_target(&md->ud, 0);
 	}
+	if(map->count_oncell(md->bl.m, md->bl.x, md->bl.y, BL_CHAR|BL_NPC, 1) > battle_config.official_cell_stack_limit) {

+		unit->walktoxy(&md->bl, md->bl.x, md->bl.y, 8);

+	}
+
 	return 0;
 }
 /*==========================================
@@ -1330,7 +1334,7 @@ int mob_randomwalk(struct mob_data *md, int64 tick) {
 		x+=md->bl.x;
 		y+=md->bl.y;
 
-		if(((x != md->bl.x) || (y != md->bl.y)) && map->getcell(md->bl.m,x,y,CELL_CHKPASS) && unit->walktoxy(&md->bl,x,y,0)){
+		if(((x != md->bl.x) || (y != md->bl.y)) && map->getcell(md->bl.m,x,y,CELL_CHKPASS) && unit->walktoxy(&md->bl,x,y,8)){
 			break;
 		}
 	}
@@ -1429,8 +1433,9 @@ bool mob_ai_sub_hard(struct mob_data *md, int64 tick) {
 			//No valid target
 			if (mob->warpchase(md, tbl))
 				return true; //Chasing this target.
-			if(md->ud.walktimer != INVALID_TIMER && (!can_move || md->ud.walkpath.path_pos <= battle_config.mob_chase_refresh))
-				return true; //Walk at least "mob_chase_refresh" cells before dropping the target
+			if(md->ud.walktimer != INVALID_TIMER && (!can_move || md->ud.walkpath.path_pos <= battle_config.mob_chase_refresh)

+				&& (tbl || md->ud.walkpath.path_pos == 0))

+				return true; //Walk at least "mob_chase_refresh" cells before dropping the target unless target is non-existent
 			mob_unlocktarget(md, tick); //Unlock target
 			tbl = NULL;
 		}
diff --git a/src/map/path.c b/src/map/path.c
index d8096ad43..9aeb108fa 100644
--- a/src/map/path.c
+++ b/src/map/path.c
@@ -248,12 +248,8 @@ bool path_search(struct walkpath_data *wpd, int16 m, int16 x0, int16 y0, int16 x
 		return false;
 	md = &map->list[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)
-#else
 	if (x0 < 0 || x0 >= md->xs || y0 < 0 || y0 >= md->ys /*|| md->getcellp(md,x0,y0,cell)*/)
-#endif
 		return false;
 
 	// Check destination cell
diff --git a/src/map/skill.c b/src/map/skill.c
index 992b72857..a51dec868 100644
--- a/src/map/skill.c
+++ b/src/map/skill.c
@@ -6948,7 +6948,7 @@ int skill_castend_nodamage_id(struct block_list *src, struct block_list *bl, uin
 				}
 
 				clif->skill_nodamage(src,bl,TK_HIGHJUMP,skill_lv,1);
-				if(!map->count_oncell(src->m,x,y,BL_PC|BL_NPC|BL_MOB) && map->getcell(src->m,x,y,CELL_CHKREACH)) {
+				if(!map->count_oncell(src->m,x,y,BL_PC|BL_NPC|BL_MOB,0) && map->getcell(src->m,x,y,CELL_CHKREACH)) {
 					clif->slide(src,x,y);
 					unit->movepos(src, x, y, 1, 0);
 				}
@@ -10385,7 +10385,7 @@ int skill_castend_pos2(struct block_list* src, int x, int y, uint16 skill_id, ui
 		// Plant Cultivation [Celest]
 		case CR_CULTIVATION:
 			if (sd) {
-				if( map->count_oncell(src->m,x,y,BL_CHAR) > 0 ) {
+				if( map->count_oncell(src->m,x,y,BL_CHAR,0) > 0 ) {
 					clif->skill_fail(sd,skill_id,USESKILL_FAIL_LEVEL,0);
 					return 1;
 				}
@@ -11588,7 +11588,7 @@ int skill_unit_onplace_timer(struct skill_unit *src, struct block_list *bl, int6
 		ts->tick = tick+sg->interval;
 
 		if ((skill_id==CR_GRANDCROSS || skill_id==NPC_GRANDDARKNESS) && !battle_config.gx_allhit)
-			ts->tick += sg->interval*(map->count_oncell(bl->m,bl->x,bl->y,BL_CHAR)-1);
+			ts->tick += sg->interval*(map->count_oncell(bl->m,bl->x,bl->y,BL_CHAR,0)-1);
 	}
 
 	switch (sg->unit_id) {
diff --git a/src/map/unit.c b/src/map/unit.c
index 34a9dcc24..f7b484e0c 100644
--- a/src/map/unit.c
+++ b/src/map/unit.c
@@ -197,7 +197,7 @@ int unit_step_timer(int tid, int64 tick, int id, intptr_t data)
 		}
 		if(ud->stepskill_id == 0) {
 			//Execute normal attack
-			unit->attack(bl, tbl->id, ud->state.attack_continue);
+			unit->attack(bl, tbl->id, (ud->state.attack_continue) + 2);
 		} else {
 			//Execute non-ground skill
 			unit->skilluse_id(bl, tbl->id, ud->stepskill_id, ud->stepskill_lv);
@@ -439,6 +439,16 @@ int unit_walktoxy_timer(int tid, int64 tick, int id, intptr_t data) {
 		//Stopped walking. Update to_x and to_y to current location [Skotlex]
 		ud->to_x = bl->x;
 		ud->to_y = bl->y;
+
+		if(map->count_oncell(bl->m, x, y, BL_CHAR|BL_NPC, 1) > battle_config.official_cell_stack_limit) {

+			//Walked on occupied cell, call unit_walktoxy again

+			if(ud->steptimer != INVALID_TIMER) {

+				//Execute step timer on next step instead

+				timer->delete(ud->steptimer, unit_step_timer);

+				ud->steptimer = INVALID_TIMER;

+			}

+			return unit->walktoxy(bl, x, y, 8);

+		}
 	}
 	return 0;
 }
@@ -456,6 +466,7 @@ int unit_delay_walktoxy_timer(int tid, int64 tick, int id, intptr_t data) {
 //&1 -> 1/0 = easy/hard
 //&2 -> force walking
 //&4 -> Delay walking if the reason you can't walk is the canwalk delay
+//&8 -> Search for an unoccupied cell and cancel if none available
 int unit_walktoxy( struct block_list *bl, short x, short y, int flag)
 {
 	struct unit_data* ud = NULL;
@@ -468,6 +479,9 @@ int unit_walktoxy( struct block_list *bl, short x, short y, int flag)
 
 	if( ud == NULL) return 0;
 
+	if ((flag&8) && !map->closest_freecell(bl->m, &x, &y, BL_CHAR|BL_NPC, 1)) //This might change x and y

+		return 0;
+
 	if (!path->search(&wpd, bl->m, bl->x, bl->y, x, y, flag&1, CELL_CHKNOPASS)) // Count walk path cells
 		return 0;
 
@@ -654,7 +668,7 @@ bool unit_run( struct block_list *bl, struct map_session_data *sd, enum sc_type
 			break;
 
 		//if sprinting and there's a PC/Mob/NPC, block the path [Kevin]
-		if( map->count_oncell(bl->m, to_x+dir_x, to_y+dir_y, BL_PC|BL_MOB|BL_NPC) )
+		if( map->count_oncell(bl->m, to_x+dir_x, to_y+dir_y, BL_PC|BL_MOB|BL_NPC, 0) )
 			break;
 
 		to_x += dir_x;
@@ -1792,6 +1806,7 @@ int unit_unattackable(struct block_list *bl)
 	struct unit_data *ud = unit->bl2ud(bl);
 	if (ud) {
 		ud->state.attack_continue = 0;
+		ud->state.step_attack = 0;
 		unit->set_target(ud, 0);
 	}
 
@@ -1838,7 +1853,8 @@ int unit_attack(struct block_list *src,int target_id,int continuous) {
 		unit->unattackable(src);
 		return 1;
 	}
-	ud->state.attack_continue = continuous;
+	ud->state.attack_continue = (continuous&1)?1:0;

+	ud->state.step_attack = (continuous&2)?1:0;
 	unit->set_target(ud, target_id);
 
 	range = status_get_range(src);
@@ -2064,7 +2080,8 @@ int unit_attack_timer_sub(struct block_list* src, int tid, int64 tick) {
 	sstatus = status->get_status_data(src);
 	range = sstatus->rhw.range;
 
-	if( unit->is_walking(target) && (target->type == BL_PC || !map->getcell(target->m,target->x,target->y,CELL_CHKICEWALL)) )
+	if( (unit_is_walking(target) || ud->state.step_attack)

+		&& (target->type == BL_PC || !map->getcell(target->m,target->x,target->y,CELL_CHKICEWALL)) )
 		range++; // Extra range when chasing (does not apply to mobs locked in an icewall)
 
 	if(sd && !check_distance_client_bl(src,target,range)) {
diff --git a/src/map/unit.h b/src/map/unit.h
index d107992dd..881fa16f4 100644
--- a/src/map/unit.h
+++ b/src/map/unit.h
@@ -43,6 +43,7 @@ struct unit_data {
 		unsigned change_walk_target : 1 ;
 		unsigned skillcastcancel : 1 ;
 		unsigned attack_continue : 1 ;
+		unsigned step_attack : 1;
 		unsigned walk_easy : 1 ;
 		unsigned running : 1;
 		unsigned speed_changed : 1;