Merge branch 'master' of https://github.com/HerculesWS/Hercules

13 files changed, 797 insertions, 884 deletions

diff --git a/src/common/cbasetypes.h b/src/common/cbasetypes.h
index bfe8bf8f8..82ca9df69 100644
--- a/src/common/cbasetypes.h
+++ b/src/common/cbasetypes.h
@@ -300,6 +300,8 @@ typedef char bool;
 #endif
 #endif
 
+#define swap_ptr(a,b) if ((a) != (b)) ((a) = (void*)((intptr_t)(a) ^ (intptr_t)(b)), (b) = (void*)((intptr_t)(a) ^ (intptr_t)(b)), (a) = (void*)((intptr_t)(a) ^ (intptr_t)(b)))
+
 #ifndef max
 #define max(a,b) (((a) > (b)) ? (a) : (b))
 #endif
diff --git a/src/common/db.h b/src/common/db.h
index 5a555b2fa..aa4bfb054 100644
--- a/src/common/db.h
+++ b/src/common/db.h
@@ -1392,7 +1392,8 @@ void  linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ...  );
 /// @param __heap Binary heap
 /// @param __val Value
 /// @param __topcmp Comparator
-#define BHEAP_PUSH(__heap,__val,__topcmp) \
+/// @param __swp Swapper
+#define BHEAP_PUSH(__heap,__val,__topcmp,__swp) \
 	do{ \
 		size_t _i_ = VECTOR_LENGTH(__heap); \
 		VECTOR_PUSH(__heap,__val); /* insert at end */ \
@@ -1401,7 +1402,7 @@ void  linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ...  );
 			size_t _parent_ = (_i_-1)/2; \
 			if( __topcmp(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)) < 0 ) \
 				break; /* done */ \
-			swap(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)); \
+			__swp(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)); \
 			_i_ = _parent_; \
 		} \
 	}while(0)
@@ -1418,7 +1419,8 @@ void  linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ...  );
 ///
 /// @param __heap Binary heap
 /// @param __topcmp Comparator
-#define BHEAP_POP(__heap,__topcmp) BHEAP_POPINDEX(__heap,0,__topcmp)
+/// @param __swp Swapper
+#define BHEAP_POP(__heap,__topcmp,__swp) BHEAP_POPINDEX(__heap,0,__topcmp,__swp)
 
 
 
@@ -1433,16 +1435,19 @@ void  linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ...  );
 /// @param __heap Binary heap
 /// @param __idx Index
 /// @param __topcmp Comparator
-#define BHEAP_POPINDEX(__heap,__idx,__topcmp) \
+/// @param __swp Swapper
+#define BHEAP_POPINDEX(__heap,__idx,__topcmp,__swp) \
 	do{ \
 		size_t _i_ = __idx; \
 		VECTOR_INDEX(__heap,__idx) = VECTOR_POP(__heap); /* put last at index */ \
+		if( _i_ >= VECTOR_LENGTH(__heap)) /* removed last, nothing to do */ \
+			break; \
 		while( _i_ ) \
 		{ /* restore heap property in parents */ \
 			size_t _parent_ = (_i_-1)/2; \
 			if( __topcmp(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)) < 0 ) \
 				break; /* done */ \
-			swap(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)); \
+			__swp(VECTOR_INDEX(__heap,_parent_),VECTOR_INDEX(__heap,_i_)); \
 			_i_ = _parent_; \
 		} \
 		while( _i_ < VECTOR_LENGTH(__heap) ) \
@@ -1454,12 +1459,12 @@ void  linkdb_foreach( struct linkdb_node** head, LinkDBFunc func, ...  );
 				break; /* done */ \
 			else if( _rchild_ >= VECTOR_LENGTH(__heap) || __topcmp(VECTOR_INDEX(__heap,_lchild_),VECTOR_INDEX(__heap,_rchild_)) <= 0 ) \
 			{ /* left child */ \
-				swap(VECTOR_INDEX(__heap,_i_),VECTOR_INDEX(__heap,_lchild_)); \
+				__swp(VECTOR_INDEX(__heap,_i_),VECTOR_INDEX(__heap,_lchild_)); \
 				_i_ = _lchild_; \
 			} \
 			else \
 			{ /* right child */ \
-				swap(VECTOR_INDEX(__heap,_i_),VECTOR_INDEX(__heap,_rchild_)); \
+				__swp(VECTOR_INDEX(__heap,_i_),VECTOR_INDEX(__heap,_rchild_)); \
 				_i_ = _rchild_; \
 			} \
 		} \
diff --git a/src/common/timer.c b/src/common/timer.c
index 955a971c8..f019c6927 100644
--- a/src/common/timer.c
+++ b/src/common/timer.c
@@ -195,7 +195,7 @@ unsigned int timer_gettick(void) {
 /// Adds a timer to the timer_heap
 static void push_timer_heap(int tid) {
 	BHEAP_ENSURE(timer_heap, 1, 256);
-	BHEAP_PUSH(timer_heap, tid, DIFFTICK_MINTOPCMP);
+	BHEAP_PUSH(timer_heap, tid, DIFFTICK_MINTOPCMP, swap);
 }
 
 /*==========================
@@ -322,9 +322,9 @@ int timer_settick(int tid, unsigned int tick) {
 		return (int)tick;// nothing to do, already in propper position
 
 	// pop and push adjusted timer
-	BHEAP_POPINDEX(timer_heap, i, DIFFTICK_MINTOPCMP);
+	BHEAP_POPINDEX(timer_heap, i, DIFFTICK_MINTOPCMP, swap);
 	timer_data[tid].tick = tick;
-	BHEAP_PUSH(timer_heap, tid, DIFFTICK_MINTOPCMP);
+	BHEAP_PUSH(timer_heap, tid, DIFFTICK_MINTOPCMP, swap);
 	return (int)tick;
 }
 
@@ -342,7 +342,7 @@ int do_timer(unsigned int tick) {
 			break; // no more expired timers to process
 
 		// remove timer
-		BHEAP_POP(timer_heap, DIFFTICK_MINTOPCMP);
+		BHEAP_POP(timer_heap, DIFFTICK_MINTOPCMP, swap);
 		timer_data[tid].type |= TIMER_REMOVE_HEAP;
 
 		if( timer_data[tid].func ) {
diff --git a/src/map/atcommand.c b/src/map/atcommand.c
index e3cf37cf1..069856754 100644
--- a/src/map/atcommand.c
+++ b/src/map/atcommand.c
@@ -6152,10 +6152,10 @@ ACMD(cleanarea)
 	int x0 = 0, y0 = 0, x1 = 0, y1 = 0;
 	
 	if (!message || !*message || sscanf(message, "%d %d %d %d", &x0, &y0, &x1, &y1) < 1) {
-		iMap->foreachinarea(atcommand_cleanfloor_sub, sd->bl.m, sd->bl.x - (AREA_SIZE * 2), sd->bl.y - (AREA_SIZE * 2), sd->bl.x + (AREA_SIZE * 2), sd->bl.y + (AREA_SIZE * 2), BL_ITEM);
+		iMap->foreachinrange(atcommand_cleanfloor_sub, &sd->bl, AREA_SIZE * 2, BL_ITEM);
 	}
 	else if (sscanf(message, "%d %d %d %d", &x0, &y0, &x1, &y1) == 1) {
-		iMap->foreachinarea(atcommand_cleanfloor_sub, sd->bl.m, sd->bl.x - x0, sd->bl.y - x0, sd->bl.x + x0, sd->bl.y + x0, BL_ITEM);
+		iMap->foreachinrange(atcommand_cleanfloor_sub, &sd->bl, x0, BL_ITEM);
 	}
 	else if (sscanf(message, "%d %d %d %d", &x0, &y0, &x1, &y1) == 4) {
 		iMap->foreachinarea(atcommand_cleanfloor_sub, sd->bl.m, x0, y0, x1, y1, BL_ITEM);
diff --git a/src/map/map.c b/src/map/map.c
index e6a1fd73c..589f6f76d 100644
--- a/src/map/map.c
+++ b/src/map/map.c
@@ -80,7 +80,7 @@ char log_db_pw[32] = "ragnarok";
 char log_db_db[32] = "log";
 Sql* logmysql_handle;
 
-// DBMap declaartion
+// DBMap declaration
 static DBMap* id_db=NULL; // int id -> struct block_list*
 static DBMap* pc_db=NULL; // int id -> struct map_session_data*
 static DBMap* mobid_db=NULL; // int id -> struct mob_data*
@@ -447,6 +447,7 @@ int map_moveblock(struct block_list *bl, int x1, int y1, unsigned int tick)
 
 /*==========================================
 * Counts specified number of objects on given cell.
+* TODO: merge with bl_getall_area
 *------------------------------------------*/
 int map_count_oncell(int16 m, int16 x, int16 y, int type)
 {
@@ -502,546 +503,607 @@ struct skill_unit* map_find_skill_unit_oncell(struct block_list* target,int16 x,
 	return NULL;
 }
 
-/*==========================================
-* Adapted from foreachinarea for an easier invocation. [Skotlex]
-*------------------------------------------*/
-int map_foreachinrange(int (*func)(struct block_list*,va_list), struct block_list* center, int16 range, int type, ...)
+/** @name Functions for block_list search and manipulation
+ */
+
+/* @{ */
+/**
+ * Applies func to every block_list in bl_list starting with bl_list[blockcount].
+ * Sets bl_list_count back to blockcount.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param blockcount Index of first relevant entry in bl_list
+ * @param max Maximum sum of values returned by func (usually max number of func calls)
+ * @param args Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+static int bl_vforeach(int (*func)(struct block_list*, va_list), int blockcount, int max, va_list args)
 {
-	int bx, by, m;
-	int returnCount = 0;	//total sum of returned values of func() [Skotlex]
-	struct block_list *bl;
-	int blockcount = bl_list_count, i;
-	int x0, x1, y0, y1;
-	va_list ap;
+	int i;
+	int returnCount = 0;
 
-	m = center->m;
-	x0 = max(center->x - range, 0);
-	y0 = max(center->y - range, 0);
-	x1 = min(center->x + range, map[ m ].xs - 1);
-	y1 = min(center->y + range, map[ m ].ys - 1);
-
-	if ( type&~BL_MOB )
-		for ( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ ) {
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ ) {
-				for( bl = map[m].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-					if( bl->type&type
-						&& bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1
-#ifdef CIRCULAR_AREA
-						&& check_distance_bl(center, bl, range)
-#endif
-						&& bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
-				}
-			}
+	iMap->freeblock_lock();
+	for (i = blockcount; i < bl_list_count && returnCount < max; i++) {
+		if (bl_list[i]->prev) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
+			va_list argscopy;
+			va_copy(argscopy, args);
+			returnCount += func(bl_list[i], argscopy);
+			va_end(argscopy);
 		}
+	}
+	iMap->freeblock_unlock();
 
-		if( type&BL_MOB )
-			for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ ) {
-				for(bx=x0/BLOCK_SIZE;bx<=x1/BLOCK_SIZE;bx++) {
-					for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-						if( bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1
-#ifdef CIRCULAR_AREA
-							&& check_distance_bl(center, bl, range)
-#endif
-							&& bl_list_count < BL_LIST_MAX )
-							bl_list[ bl_list_count++ ] = bl;
-					}
-				}
-			}
-
-			if( bl_list_count >= BL_LIST_MAX )
-				ShowWarning("iMap->foreachinrange: block count too many!\n");
-
-			iMap->freeblock_lock();
-
-			for( i = blockcount; i < bl_list_count; i++ )
-				if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-					va_start(ap, type);
-					returnCount += func(bl_list[ i ], ap);
-					va_end(ap);
-				}
-
-				iMap->freeblock_unlock();
+	bl_list_count = blockcount;
 
-				bl_list_count = blockcount;
-				return returnCount;	//[Skotlex]
+	return returnCount;
 }
 
-/*==========================================
-* Same as foreachinrange, but there must be a shoot-able range between center and target to be counted in. [Skotlex]
-*------------------------------------------*/
-int map_foreachinshootrange(int (*func)(struct block_list*,va_list),struct block_list* center, int16 range, int type,...)
+/**
+ * Applies func to every block_list object of bl_type type on map m.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param m Map id
+ * @param type enum bl_type
+ * @param args Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+static int map_vforeachinmap(int (*func)(struct block_list*, va_list), int16 m, int type, va_list args)
 {
-	int bx, by, m;
-	int returnCount = 0;	//total sum of returned values of func() [Skotlex]
+	int i;
+	int returnCount = 0;
+	int bsize; 
+	va_list argscopy;
 	struct block_list *bl;
-	int blockcount = bl_list_count, i;
-	int x0, x1, y0, y1;
-	va_list ap;
+	int blockcount = bl_list_count;
 
-	m = center->m;
-	if ( m < 0 )
+	if (m < 0)
 		return 0;
 
-	x0 = max(center->x-range, 0);
-	y0 = max(center->y-range, 0);
-	x1 = min(center->x+range, map[m].xs-1);
-	y1 = min(center->y+range, map[m].ys-1);
-
-	if ( type&~BL_MOB )
-		for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ ) {
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ ) {
-				for( bl = map[ m ].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-					if( bl->type&type
-						&& bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1
-#ifdef CIRCULAR_AREA
-						&& check_distance_bl(center, bl, range)
-#endif
-						&& path_search_long(NULL, center->m, center->x, center->y, bl->x, bl->y, CELL_CHKWALL)
-						&& bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
+	bsize = map[m].bxs * map[m].bys;
+	for (i = 0; i < bsize; i++) {
+		if (type&~BL_MOB) {
+			for (bl = map[m].block[i]; bl != NULL; bl = bl->next) {
+				if (bl->type&type && bl_list_count < BL_LIST_MAX) {
+					bl_list[bl_list_count++] = bl;
 				}
 			}
 		}
-		if( type&BL_MOB )
-			for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ ) {
-				for( bx=x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ ) {
-					for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-						if( bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1
-#ifdef CIRCULAR_AREA
-							&& check_distance_bl(center, bl, range)
-#endif
-							&& path_search_long(NULL, center->m, center->x, center->y, bl->x, bl->y, CELL_CHKWALL)
-							&& bl_list_count < BL_LIST_MAX )
-							bl_list[ bl_list_count++ ] = bl;
-					}
+		if (type&BL_MOB) {
+			for (bl = map[m].block_mob[i]; bl != NULL; bl = bl->next) {
+				if (bl_list_count < BL_LIST_MAX) {
+					bl_list[bl_list_count++] = bl;
 				}
 			}
+		}
+	}
 
-			if( bl_list_count >= BL_LIST_MAX )
-				ShowWarning("iMap->foreachinrange: block count too many!\n");
+	if (bl_list_count >= BL_LIST_MAX)
+		ShowError("map.c:map_vforeachinmap: bl_list size (%d) exceeded\n", BL_LIST_MAX);
 
-			iMap->freeblock_lock();
+	va_copy(argscopy, args);
+	returnCount = bl_vforeach(func, blockcount, INT_MAX, argscopy);
+	va_end(argscopy);
 
-			for( i = blockcount; i < bl_list_count; i++ )
-				if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-					va_start(ap, type);
-					returnCount += func(bl_list[ i ], ap);
-					va_end(ap);
-				}
+	return returnCount;
+}
+
+/**
+ * Applies func to every block_list object of bl_type type on map m.
+ * Returns the sum of values returned by func.
+ * @see map_vforeachinmap
+ * @param func Function to be applied
+ * @param m Map id
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_foreachinmap(int (*func)(struct block_list*, va_list), int16 m, int type, ...)
+{
+	int returnCount = 0;
+	va_list ap;
 
-				iMap->freeblock_unlock();
+	va_start(ap, type);
+	returnCount = map_vforeachinmap(func, m, type, ap);
+	va_end(ap);
 
-				bl_list_count = blockcount;
-				return returnCount;	//[Skotlex]
+	return returnCount;
 }
 
-/*==========================================
-* range = map m (x0,y0)-(x1,y1)
-* Apply *func with ... arguments for the range.
-* @type = BL_PC/BL_MOB etc..
-*------------------------------------------*/
-int map_foreachinarea(int (*func)(struct block_list*,va_list), int16 m, int16 x0, int16 y0, int16 x1, int16 y1, int type, ...)
+/**
+ * Applies func to every block_list object of bl_type type on all maps
+ * of instance instance_id.
+ * Returns the sum of values returned by func.
+ * @see map_vforeachinmap.
+ * @param func Function to be applied
+ * @param m Map id
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_foreachininstance(int (*func)(struct block_list*, va_list), int16 instance_id, int type, ...)
+{
+	int i;
+	int returnCount = 0;
+
+	for (i = 0; i < instances[instance_id].num_map; i++) {
+		int m = instances[instance_id].map[i];
+		va_list ap;
+		va_start(ap, type);
+		returnCount += map_vforeachinmap(func, m, type, ap);
+		va_end(ap);
+	}
+
+	return returnCount;
+}
+
+/**
+ * Retrieves all map objects in area that are matched by the type
+ * and func. Appends them at the end of global bl_list array.
+ * @param type Matching enum bl_type
+ * @param m Map
+ * @param func Matching function
+ * @param ... Extra arguments for func
+ * @return Number of found objects
+ */
+static int bl_getall_area(int type, int m, int x0, int y0, int x1, int y1, int (*func)(struct block_list*, va_list), ...)
 {
+	va_list args;
 	int bx, by;
-	int returnCount = 0;	//total sum of returned values of func() [Skotlex]
 	struct block_list *bl;
-	int blockcount = bl_list_count, i;
-	va_list ap;
+	int found = 0;
 
-	if ( m < 0 )
+	if (m < 0)
 		return 0;
 
-	if ( x1 < x0 )
-		swap(x0, x1);
-	if ( y1 < y0 )
-		swap(y0, y1);
+	if (x1 < x0) swap(x0, x1);
+	if (y1 < y0) swap(y0, y1);
 
+	// Limit search area to map size
 	x0 = max(x0, 0);
 	y0 = max(y0, 0);
-	x1 = min(x1, map[ m ].xs - 1);
-	y1 = min(y1, map[ m ].ys - 1);
-	if ( type&~BL_MOB )
-		for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ )
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ )
-				for( bl = map[ m ].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next )
-					if( bl->type&type && bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1 && bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
-
-	if( type&BL_MOB )
-		for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ )
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ )
-				for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next )
-					if( bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1 && bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
-
-	if( bl_list_count >= BL_LIST_MAX )
-		ShowWarning("map_foreachinarea: block count too many!\n");
+	x1 = min(x1, map[m].xs - 1);
+	y1 = min(y1, map[m].ys - 1);
+
+	for (by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++) {
+		for (bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++) {
+			if (type&~BL_MOB) {
+				for (bl = map[m].block[bx + by * map[m].bxs]; bl != NULL; bl = bl->next) {
+					if (bl_list_count < BL_LIST_MAX
+						&& bl->type&type
+						&& bl->x >= x0 && bl->x <= x1
+						&& bl->y >= y0 && bl->y <= y1) {
+							if (func) {
+								va_start(args, func);
+								if (func(bl, args)) {
+									bl_list[bl_list_count++] = bl;
+									found++;
+								}
+								va_end(args);
+							}
+							else {
+								bl_list[bl_list_count++] = bl;
+								found++;
+							}
+					}
+				}
+			}
+			if (type&BL_MOB) { // TODO: fix this code duplication
+				for (bl = map[m].block_mob[bx + by * map[m].bxs]; bl != NULL; bl = bl->next) {
+					if (bl_list_count < BL_LIST_MAX
+						//&& bl->type&type // block_mob contains BL_MOBs only
+						&& bl->x >= x0 && bl->x <= x1
+						&& bl->y >= y0 && bl->y <= y1) {
+							if (func) {
+								va_start(args, func);
+								if (func(bl, args)) {
+									bl_list[bl_list_count++] = bl;
+									found++;
+								}
+								va_end(args);
+							}
+							else {
+								bl_list[bl_list_count++] = bl;
+								found++;
+							}
+					}
+				}
+			}
+		}
+	}
 
-	iMap->freeblock_lock();
+	if (bl_list_count >= BL_LIST_MAX)
+		ShowError("map.c:bl_getall_area: bl_list size (%d) exceeded\n", BL_LIST_MAX);
 
-	for( i = blockcount; i < bl_list_count; i++ )
-		if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-			va_start(ap, type);
-			returnCount += func(bl_list[ i ], ap);
-			va_end(ap);
-		}
+	return found;
+}
 
-		iMap->freeblock_unlock();
+/**
+ * Checks if bl is within range cells from center.
+ * If CIRCULAR AREA is not used always returns 1, since
+ * preliminary range selection is already done in bl_getall_area.
+ * @return 1 if matches, 0 otherwise
+ */
+static int bl_vgetall_inrange(struct block_list *bl, va_list args)
+{
+#ifdef CIRCULAR_AREA
+	struct block_list *center = va_arg(args, struct block_list*);
+	int range = va_arg(args, int);
+	if (!check_distance_bl(center, bl, range))
+		return 0;
+#endif
+	return 1;
+}
+
+/**
+ * Applies func to every block_list object of bl_type type within range cells from center.
+ * Area is rectangular, unless CIRCULAR_AREA is defined.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param center Center of the selection area
+ * @param range Range in cells from center
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_foreachinrange(int (*func)(struct block_list*, va_list), struct block_list* center, int16 range, int type, ...)
+{
+	int returnCount = 0;
+	int blockcount = bl_list_count;
+	va_list ap;
+
+	if (range < 0) range *= -1;
 
-		bl_list_count = blockcount;
-		return returnCount;	//[Skotlex]
+	bl_getall_area(type, center->m, center->x - range, center->y - range, center->x + range, center->y + range, bl_vgetall_inrange, center, range);
+
+	va_start(ap, type);
+	returnCount = bl_vforeach(func, blockcount, INT_MAX, ap);
+	va_end(ap);
+
+	return returnCount;
 }
-/*==========================================
-* Adapted from forcountinarea for an easier invocation. [pakpil]
-*------------------------------------------*/
-int map_forcountinrange(int (*func)(struct block_list*,va_list), struct block_list* center, int16 range, int count, int type, ...)
+
+/**
+ * Applies func to some block_list objects of bl_type type within range cells from center.
+ * Limit is set by count parameter.
+ * Area is rectangular, unless CIRCULAR_AREA is defined.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param center Center of the selection area
+ * @param range Range in cells from center
+ * @param count Maximum sum of values returned by func (usually max number of func calls)
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_forcountinrange(int (*func)(struct block_list*, va_list), struct block_list* center, int16 range, int count, int type, ...)
 {
-	int bx, by, m;
-	int returnCount = 0;	//total sum of returned values of func() [Skotlex]
-	struct block_list *bl;
-	int blockcount = bl_list_count, i;
-	int x0, x1, y0, y1;
+	int returnCount = 0;
+	int blockcount = bl_list_count;
 	va_list ap;
 
-	m = center->m;
-	x0 = max(center->x - range, 0);
-	y0 = max(center->y - range, 0);
-	x1 = min(center->x + range, map[ m ].xs - 1);
-	y1 = min(center->y + range, map[ m ].ys - 1);
-
-	if ( type&~BL_MOB )
-		for ( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ ) {
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ ) {
-				for( bl = map[ m ].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-					if( bl->type&type
-						&& bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1
-#ifdef CIRCULAR_AREA
-						&& check_distance_bl(center, bl, range)
-#endif
-						&& bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
-				}
-			}
-		}
-		if( type&BL_MOB )
-			for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ ) {
-				for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ ){
-					for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-						if( bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1
+	if (range < 0) range *= -1;
+
+	bl_getall_area(type, center->m, center->x - range, center->y - range, center->x + range, center->y + range, bl_vgetall_inrange, center, range);
+
+	va_start(ap, type);
+	returnCount = bl_vforeach(func, blockcount, count, ap);
+	va_end(ap);
+
+	return returnCount;
+}
+
+/**
+ * Checks if bl is within shooting range from center.
+ * There must be a shootable path between bl and center.
+ * Does not check for range if CIRCULAR AREA is not defined, since
+ * preliminary range selection is already done in bl_getall_area.
+ * @return 1 if matches, 0 otherwise
+ */
+static int bl_vgetall_inshootrange(struct block_list *bl, va_list args)
+{
+	struct block_list *center = va_arg(args, struct block_list*);
 #ifdef CIRCULAR_AREA
-							&& check_distance_bl(center, bl, range)
+	int range = va_arg(args, int);
+	if (!check_distance_bl(center, bl, range))
+		return 0;
 #endif
-							&& bl_list_count < BL_LIST_MAX )
-							bl_list[ bl_list_count++ ] = bl;
-					}
-				}
-			}
+	if (!path_search_long(NULL, center->m, center->x, center->y, bl->x, bl->y, CELL_CHKWALL))
+		return 0;
+	return 1;
+}
 
-			if( bl_list_count >= BL_LIST_MAX )
-				ShowWarning("map_forcountinrange: block count too many!\n");
+/**
+ * Applies func to every block_list object of bl_type type within shootable range from center.
+ * There must be a shootable path between bl and center.
+ * Area is rectangular, unless CIRCULAR_AREA is defined.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param center Center of the selection area
+ * @param range Range in cells from center
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_foreachinshootrange(int (*func)(struct block_list*, va_list), struct block_list* center, int16 range, int type, ...)
+{
+	int returnCount = 0;
+	int blockcount = bl_list_count;
+	va_list ap;
 
-			iMap->freeblock_lock();
+	if (range < 0) range *= -1;
 
-			for( i = blockcount; i < bl_list_count; i++ )
-				if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-					va_start(ap, type);
-					returnCount += func(bl_list[ i ], ap);
-					va_end(ap);
-					if( count && returnCount >= count )
-						break;
-				}
+	bl_getall_area(type, center->m, center->x - range, center->y - range, center->x + range, center->y + range, bl_vgetall_inshootrange, center, range);
 
-				iMap->freeblock_unlock();
+	va_start(ap, type);
+	returnCount = bl_vforeach(func, blockcount, INT_MAX, ap);
+	va_end(ap);
 
-				bl_list_count = blockcount;
-				return returnCount;	//[Skotlex]
+	return returnCount;
 }
-int map_forcountinarea(int (*func)(struct block_list*,va_list), int16 m, int16 x0, int16 y0, int16 x1, int16 y1, int count, int type, ...)
+
+/**
+ * Applies func to every block_list object of bl_type type in
+ * rectangular area (x0,y0)~(x1,y1) on map m.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param m Map id
+ * @param x0 Starting X-coordinate
+ * @param y0 Starting Y-coordinate
+ * @param x1 Ending X-coordinate
+ * @param y1 Ending Y-coordinate
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_foreachinarea(int (*func)(struct block_list*, va_list), int16 m, int16 x0, int16 y0, int16 x1, int16 y1, int type, ...)
 {
-	int bx, by;
-	int returnCount = 0;	//total sum of returned values of func() [Skotlex]
-	struct block_list *bl;
-	int blockcount = bl_list_count, i;
+	int returnCount = 0;
+	int blockcount = bl_list_count;
 	va_list ap;
 
-	if ( m < 0 )
-		return 0;
+	bl_getall_area(type, m, x0, y0, x1, y1, NULL);
 
-	if ( x1 < x0 )
-		swap(x0, x1);
-	if ( y1 < y0 )
-		swap(y0, y1);
+	va_start(ap, type);
+	returnCount = bl_vforeach(func, blockcount, INT_MAX, ap);
+	va_end(ap);
 
-	x0 = max(x0, 0);
-	y0 = max(y0, 0);
-	x1 = min(x1, map[ m ].xs - 1);
-	y1 = min(y1, map[ m ].ys - 1);
-
-	if ( type&~BL_MOB )
-		for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ )
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ )
-				for( bl = map[ m ].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next )
-					if( bl->type&type && bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1 && bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
-
-	if( type&BL_MOB )
-		for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ )
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ )
-				for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next )
-					if( bl->x >= x0 && bl->x <= x1 && bl->y >= y0 && bl->y <= y1 && bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
-
-	if( bl_list_count >= BL_LIST_MAX )
-		ShowWarning("map_foreachinarea: block count too many!\n");
+	return returnCount;
+}
 
-	iMap->freeblock_lock();
+/**
+ * Applies func to some block_list objects of bl_type type in
+ * rectangular area (x0,y0)~(x1,y1) on map m.
+ * Limit is set by @count parameter.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param m Map id
+ * @param x0 Starting X-coordinate
+ * @param y0 Starting Y-coordinate
+ * @param x1 Ending X-coordinate
+ * @param y1 Ending Y-coordinate
+ * @param count Maximum sum of values returned by func (usually max number of func calls)
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_forcountinarea(int (*func)(struct block_list*,va_list), int16 m, int16 x0, int16 y0, int16 x1, int16 y1, int count, int type, ...)
+{
+	int returnCount = 0;
+	int blockcount = bl_list_count;
+	va_list ap;
 
-	for( i = blockcount; i < bl_list_count; i++ )
-		if(bl_list[ i ]->prev) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-			va_start(ap, type);
-			returnCount += func(bl_list[ i ], ap);
-			va_end(ap);
-			if( count && returnCount >= count )
-				break;
-		}
+	bl_getall_area(type, m, x0, y0, x1, y1, NULL);
 
-		iMap->freeblock_unlock();
+	va_start(ap, type);
+	returnCount = bl_vforeach(func, blockcount, count, ap);
+	va_end(ap);
 
-		bl_list_count = blockcount;
-		return returnCount;	//[Skotlex]
+	return returnCount;
 }
 
-/*==========================================
-* For what I get
-* Move bl and do func* with va_list while moving.
-* Mouvement is set by dx dy wich are distance in x and y
-*------------------------------------------*/
-int map_foreachinmovearea(int (*func)(struct block_list*,va_list), struct block_list* center, int16 range, int16 dx, int16 dy, int type, ...)
+/**
+ * Checks if bl is inside area that was in range cells from the center
+ * before it was moved by (dx,dy) cells, but it is not in range cells
+ * from center after movement is completed.
+ * In other words, checks if bl is inside area that is no longer covered
+ * by center's range.
+ * Preliminary range selection is already done in bl_getall_area.
+ * @return 1 if matches, 0 otherwise
+ */
+static int bl_vgetall_inmovearea(struct block_list *bl, va_list args)
 {
-	int bx, by, m;
-	int returnCount = 0;  //total sum of returned values of func() [Skotlex]
-	struct block_list *bl;
-	int blockcount = bl_list_count, i;
-	int x0, x1, y0, y1;
+	int dx = va_arg(args, int);
+	int dy = va_arg(args, int);
+	struct block_list *center = va_arg(args, struct block_list*);
+	int range = va_arg(args, int);
+
+	if ((dx > 0 && bl->x < center->x - range + dx) ||
+		(dx < 0 && bl->x > center->x + range + dx) ||
+		(dy > 0 && bl->y < center->y - range + dy) ||
+		(dy < 0 && bl->y > center->y + range + dy))
+		return 1;
+	return 0;
+}
+
+/**
+ * Applies func to every block_list object of bl_type type in
+ * area that was covered by range cells from center, but is no
+ * longer after center is moved by (dx,dy) cells (i.e. area that
+ * center has lost sight of).
+ * If used after center has reached its destination and with
+ * opposed movement vector (-dx,-dy), selection corresponds
+ * to new area in center's view).
+ * Uses rectangular area.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param center Center of the selection area
+ * @param range Range in cells from center
+ * @param dx Center's movement on X-axis
+ * @param dy Center's movement on Y-axis
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_foreachinmovearea(int (*func)(struct block_list*, va_list), struct block_list* center, int16 range, int16 dx, int16 dy, int type, ...)
+{
+	int returnCount = 0;
+	int blockcount = bl_list_count;
 	va_list ap;
+	int m, x0, x1, y0, y1;
 
-	if ( !range ) return 0;
-	if ( !dx && !dy ) return 0; //No movement.
+	if (!range) return 0;
+	if (!dx && !dy) return 0; // No movement.
 
-	m = center->m;
+	if (range < 0) range *= -1;
 
+	m = center->m;
 	x0 = center->x - range;
 	x1 = center->x + range;
 	y0 = center->y - range;
 	y1 = center->y + range;
 
-	if ( x1 < x0 )
-		swap(x0, x1);
-	if ( y1 < y0 )
-		swap(y0, y1);
-
-	if( dx == 0 || dy == 0 ) {
-		//Movement along one axis only.
-		if( dx == 0 ){
-			if( dy < 0 ) //Moving south
-				y0 = y1 + dy + 1;
-			else //North
-				y1 = y0 + dy - 1;
+	if (dx == 0 || dy == 0) { // Movement along one axis only.
+		if (dx == 0) {
+			if (dy < 0) { y0 = y1 + dy + 1; } // Moving south
+			else        { y1 = y0 + dy - 1; } // North
 		} else { //dy == 0
-			if( dx < 0 ) //West
-				x0 = x1 + dx + 1;
-			else //East
-				x1 = x0 + dx - 1;
-		}
-
-		x0 = max(x0, 0);
-		y0 = max(y0, 0);
-		x1 = min(x1, map[ m ].xs - 1);
-		y1 = min(y1, map[ m ].ys - 1);
-
-		for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ ) {
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ ) {
-				if ( type&~BL_MOB ) {
-					for( bl = map[m].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-						if( bl->type&type &&
-							bl->x >= x0 && bl->x <= x1 &&
-							bl->y >= y0 && bl->y <= y1 &&
-							bl_list_count < BL_LIST_MAX )
-							bl_list[ bl_list_count++ ] = bl;
-					}
-				}
-				if ( type&BL_MOB ) {
-					for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-						if( bl->x >= x0 && bl->x <= x1 &&
-							bl->y >= y0 && bl->y <= y1 &&
-							bl_list_count < BL_LIST_MAX )
-							bl_list[ bl_list_count++ ] = bl;
-					}
-				}
-			}
-		}
-	} else { // Diagonal movement
-
-		x0 = max(x0, 0);
-		y0 = max(y0, 0);
-		x1 = min(x1, map[ m ].xs - 1);
-		y1 = min(y1, map[ m ].ys - 1);
-
-		for( by = y0 / BLOCK_SIZE; by <= y1 / BLOCK_SIZE; by++ ) {
-			for( bx = x0 / BLOCK_SIZE; bx <= x1 / BLOCK_SIZE; bx++ ) {
-				if ( type & ~BL_MOB ) {
-					for( bl = map[ m ].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-						if( bl->type&type &&
-							bl->x >= x0 && bl->x <= x1 &&
-							bl->y >= y0 && bl->y <= y1 &&
-							bl_list_count < BL_LIST_MAX )
-							if( ( dx > 0 && bl->x < x0 + dx) ||
-								( dx < 0 && bl->x > x1 + dx) ||
-								( dy > 0 && bl->y < y0 + dy) ||
-								( dy < 0 && bl->y > y1 + dy) )
-								bl_list[ bl_list_count++ ] = bl;
-					}
-				}
-				if ( type&BL_MOB ) {
-					for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-						if( bl->x >= x0 && bl->x <= x1 &&
-							bl->y >= y0 && bl->y <= y1 &&
-							bl_list_count < BL_LIST_MAX)
-							if( ( dx > 0 && bl->x < x0 + dx) ||
-								( dx < 0 && bl->x > x1 + dx) ||
-								( dy > 0 && bl->y < y0 + dy) ||
-								( dy < 0 && bl->y > y1 + dy) )
-								bl_list[ bl_list_count++ ] = bl;
-					}
-				}
-			}
+			if (dx < 0) { x0 = x1 + dx + 1; } // West
+			else        { x1 = x0 + dx - 1; } // East
 		}
-
+		bl_getall_area(type, m, x0, y0, x1, y1, NULL);
+	}
+	else { // Diagonal movement
+		bl_getall_area(type, m, x0, y0, x1, y1, bl_vgetall_inmovearea, dx, dy, center, range);
 	}
 
-	if( bl_list_count >= BL_LIST_MAX )
-		ShowWarning("map_foreachinmovearea: block count too many!\n");
-
-	iMap->freeblock_lock();	// Prohibit the release from memory
-
-	for( i = blockcount; i < bl_list_count; i++ )
-		if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-			va_start(ap, type);
-			returnCount += func(bl_list[ i ], ap);
-			va_end(ap);
-		}
-
-		iMap->freeblock_unlock();	// Allow Free
+	va_start(ap, type);
+	returnCount = bl_vforeach(func, blockcount, INT_MAX, ap);
+	va_end(ap);
 
-		bl_list_count = blockcount;
-		return returnCount;
+	return returnCount;
 }
 
-// -- moonsoul	(added map_foreachincell which is a rework of map_foreachinarea but
-//			 which only checks the exact single x/y passed to it rather than an
-//			 area radius - may be more useful in some instances)
-//
-int map_foreachincell(int (*func)(struct block_list*,va_list), int16 m, int16 x, int16 y, int type, ...)
+/**
+ * Applies func to every block_list object of bl_type type in
+ * cell (x,y) on map m.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param m Map id
+ * @param x Target cell X-coordinate
+ * @param y Target cell Y-coordinate
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_foreachincell(int (*func)(struct block_list*, va_list), int16 m, int16 x, int16 y, int type, ...)
 {
-	int bx, by;
-	int returnCount = 0;  //total sum of returned values of func() [Skotlex]
-	struct block_list *bl;
-	int blockcount = bl_list_count, i;
+	int returnCount = 0;
+	int blockcount = bl_list_count;
 	va_list ap;
 
-	if ( x < 0 || y < 0 || x >= map[ m ].xs || y >= map[ m ].ys ) return 0;
+	bl_getall_area(type, m, x, y, x, y, NULL);
 
-	by = y / BLOCK_SIZE;
-	bx = x / BLOCK_SIZE;
+	va_start(ap, type);
+	returnCount = bl_vforeach(func, blockcount, INT_MAX, ap);
+	va_end(ap);
 
-	if( type&~BL_MOB )
-		for( bl = map[ m ].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next )
-			if( bl->type&type && bl->x == x && bl->y == y && bl_list_count < BL_LIST_MAX )
-				bl_list[ bl_list_count++ ] = bl;
-	if( type&BL_MOB )
-		for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs]; bl != NULL; bl = bl->next )
-			if( bl->x == x && bl->y == y && bl_list_count < BL_LIST_MAX)
-				bl_list[ bl_list_count++ ] = bl;
+	return returnCount;
+}
 
-	if( bl_list_count >= BL_LIST_MAX )
-		ShowWarning("map_foreachincell: block count too many!\n");
+/**
+ * Helper function for map_foreachinpath()
+ * Checks if shortest distance from bl to path
+ * between (x0,y0) and (x1,y1) is shorter than range.
+ * @see map_foreachinpath
+ */
+static int bl_vgetall_inpath(struct block_list *bl, va_list args)
+{
+	int m  = va_arg(args, int);
+	int x0 = va_arg(args, int);
+	int y0 = va_arg(args, int);
+	int x1 = va_arg(args, int);
+	int y1 = va_arg(args, int);
+	int range = va_arg(args, int);
+	int len_limit = va_arg(args, int);
+	int magnitude2 = va_arg(args, int);
+
+	int xi = bl->x;
+	int yi = bl->y;
+	int xu, yu;
+
+	int k = ( xi - x0 ) * ( x1 - x0 ) + ( yi - y0 ) * ( y1 - y0 );
+
+	if ( k < 0 || k > len_limit ) //Since more skills use this, check for ending point as well.
+		return 0;
 
-	iMap->freeblock_lock();
+	if ( k > magnitude2 && !path_search_long(NULL, m, x0, y0, xi, yi, CELL_CHKWALL) )
+		return 0; //Targets beyond the initial ending point need the wall check.
 
-	for( i = blockcount; i < bl_list_count; i++ )
-		if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-			va_start(ap, type);
-			returnCount += func(bl_list[ i ], ap);
-			va_end(ap);
-		}
+	//All these shifts are to increase the precision of the intersection point and distance considering how it's
+	//int math.
+	k  = ( k << 4 ) / magnitude2; //k will be between 1~16 instead of 0~1
+	xi <<= 4;
+	yi <<= 4;
+	xu = ( x0 << 4 ) + k * ( x1 - x0 );
+	yu = ( y0 << 4 ) + k * ( y1 - y0 );
 
-		iMap->freeblock_unlock();
+//Avoid needless calculations by not getting the sqrt right away.
+#define MAGNITUDE2(x0, y0, x1, y1) ( ( ( x1 ) - ( x0 ) ) * ( ( x1 ) - ( x0 ) ) + ( ( y1 ) - ( y0 ) ) * ( ( y1 ) - ( y0 ) ) )
+
+	k  = MAGNITUDE2(xi, yi, xu, yu);
+
+	//If all dot coordinates were <<4 the square of the magnitude is <<8
+	if ( k > range )
+		return 0;
 
-		bl_list_count = blockcount;
-		return returnCount;
+	return 1;
 }
 
-/*============================================================
-* For checking a path between two points (x0, y0) and (x1, y1)
-*------------------------------------------------------------*/
-int map_foreachinpath(int (*func)(struct block_list*,va_list),int16 m,int16 x0,int16 y0,int16 x1,int16 y1,int16 range,int length, int type,...)
+/**
+ * Applies func to every block_list object of bl_type type in
+ * path on a line between (x0,y0) and (x1,y1) on map m.
+ * Path starts at (x0,y0) and is \a length cells long and \a range cells wide.
+ * Objects beyond the initial (x1,y1) ending point are checked
+ * for walls in the path.
+ * Returns the sum of values returned by func.
+ * @param func Function to be applied
+ * @param m Map id
+ * @param x Target cell X-coordinate
+ * @param y Target cell Y-coordinate
+ * @param type enum bl_type
+ * @param ... Extra arguments for func
+ * @return Sum of the values returned by func
+ */
+int map_foreachinpath(int (*func)(struct block_list*, va_list), int16 m, int16 x0, int16 y0, int16 x1, int16 y1, int16 range, int length, int type, ...)
 {
-	int returnCount = 0;  //total sum of returned values of func() [Skotlex]
-	//////////////////////////////////////////////////////////////
-	//
-	// sharp shooting 3 [Skotlex]
-	//
-	//////////////////////////////////////////////////////////////
-	// problem:
-	// Same as Sharp Shooting 1. Hits all targets within range of
-	// the line.
-	// (t1,t2 t3 and t4 get hit)
-	//
-	//     target 1
-	//      x t4
-	//     t2
-	// t3 x
-	//   x
-	//  S
-	//////////////////////////////////////////////////////////////
-	// Methodology:
-	// My trigonometrics and math are a little rusty... so the approach I am writing
-	// here is basicly do a double for to check for all targets in the square that
+	// [Skotlex]
+	// check for all targets in the square that
 	// contains the initial and final positions (area range increased to match the
 	// radius given), then for each object to test, calculate the distance to the
 	// path and include it if the range fits and the target is in the line (0<k<1,
 	// as they call it).
 	// The implementation I took as reference is found at
-	// http://astronomy.swin.edu.au/~pbourke/geometry/pointline/
-	// (they have a link to a C implementation, too)
-	// This approach is a lot like #2 commented on this function, which I have no
-	// idea why it was commented. I won't use doubles/floats, but pure int math for
+	// http://web.archive.org/web/20050720125314/http://astronomy.swin.edu.au/~pbourke/geometry/pointline/
+	// http://paulbourke.net/geometry/pointlineplane/
+	// I won't use doubles/floats, but pure int math for
 	// speed purposes. The range considered is always the same no matter how
 	// close/far the target is because that's how SharpShooting works currently in
-	// kRO.
+	// kRO
+
+	int returnCount = 0;
+	int blockcount = bl_list_count;
+	va_list ap;
 
-	//Generic map_foreach* variables.
-	int i, blockcount = bl_list_count;
-	struct block_list *bl;
-	int bx, by;
 	//method specific variables
 	int magnitude2, len_limit; //The square of the magnitude
-	int k, xi, yi, xu, yu;
+	int k;
 	int mx0 = x0, mx1 = x1, my0 = y0, my1 = y1;
-	va_list ap;
-
-	//Avoid needless calculations by not getting the sqrt right away.
-#define MAGNITUDE2(x0, y0, x1, y1) ( ( ( x1 ) - ( x0 ) ) * ( ( x1 ) - ( x0 ) ) + ( ( y1 ) - ( y0 ) ) * ( ( y1 ) - ( y0 ) ) )
-
-	if ( m < 0 )
-		return 0;
 
 	len_limit = magnitude2 = MAGNITUDE2(x0, y0, x1, y1);
-	if ( magnitude2 < 1 ) //Same begin and ending point, can't trace path.
+	if (magnitude2 < 1) //Same begin and ending point, can't trace path.
 		return 0;
 
-	if ( length ) { //Adjust final position to fit in the given area.
+	if (length) { //Adjust final position to fit in the given area.
 		//TODO: Find an alternate method which does not requires a square root calculation.
 		k = (int)sqrt((float)magnitude2);
 		mx1 = x0 + (x1 - x0) * length / k;
@@ -1049,7 +1111,7 @@ int map_foreachinpath(int (*func)(struct block_list*,va_list),int16 m,int16 x0,i
 		len_limit = MAGNITUDE2(x0, y0, mx1, my1);
 	}
 	//Expand target area to cover range.
-	if ( mx0 > mx1 ) {
+	if (mx0 > mx1) {
 		mx0 += range;
 		mx1 -= range;
 	} else {
@@ -1063,191 +1125,19 @@ int map_foreachinpath(int (*func)(struct block_list*,va_list),int16 m,int16 x0,i
 		my0 -= range;
 		my1 += range;
 	}
-
-	//The two fors assume mx0 < mx1 && my0 < my1
-	if ( mx0 > mx1 )
-		swap(mx0, mx1);
-	if ( my0 > my1 )
-		swap(my0, my1);
-
-	mx0 = max(mx0, 0);
-	my0 = max(my0, 0);
-	mx1 = min(mx1, map[ m ].xs - 1);
-	my1 = min(my1, map[ m ].ys - 1);
-
 	range *= range << 8; //Values are shifted later on for higher precision using int math.
 
-	if ( type&~BL_MOB )
-		for ( by = my0 / BLOCK_SIZE; by <= my1 / BLOCK_SIZE; by++ ) {
-			for( bx = mx0 / BLOCK_SIZE; bx <= mx1 / BLOCK_SIZE; bx++ ) {
-				for( bl = map[ m ].block[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-					if( bl->prev && bl->type&type && bl_list_count < BL_LIST_MAX ) {
-						xi = bl->x;
-						yi = bl->y;
-
-						k = ( xi - x0 ) * ( x1 - x0 ) + ( yi - y0 ) * ( y1 - y0 );
-
-						if ( k < 0 || k > len_limit ) //Since more skills use this, check for ending point as well.
-							continue;
-
-						if ( k > magnitude2 && !path_search_long(NULL, m, x0, y0, xi, yi, CELL_CHKWALL) )
-							continue; //Targets beyond the initial ending point need the wall check.
-
-						//All these shifts are to increase the precision of the intersection point and distance considering how it's
-						//int math.
-						k  = ( k << 4 ) / magnitude2; //k will be between 1~16 instead of 0~1
-						xi <<= 4;
-						yi <<= 4;
-						xu = ( x0 << 4 ) + k * ( x1 - x0 );
-						yu = ( y0 << 4 ) + k * ( y1 - y0 );
-						k  = MAGNITUDE2(xi, yi, xu, yu);
-
-						//If all dot coordinates were <<4 the square of the magnitude is <<8
-						if ( k > range )
-							continue;
-
-						bl_list[ bl_list_count++ ] = bl;
-					}
-				}
-			}
-		}
-		if( type&BL_MOB )
-			for( by = my0 / BLOCK_SIZE; by <= my1 / BLOCK_SIZE; by++ ) {
-				for( bx = mx0 / BLOCK_SIZE; bx <= mx1 / BLOCK_SIZE; bx++ ) {
-					for( bl = map[ m ].block_mob[ bx + by * map[ m ].bxs ]; bl != NULL; bl = bl->next ) {
-						if( bl->prev && bl_list_count < BL_LIST_MAX ) {
-							xi = bl->x;
-							yi = bl->y;
-							k = ( xi - x0 ) * ( x1 - x0 ) + ( yi - y0 ) * ( y1 - y0 );
-
-							if ( k < 0 || k > len_limit )
-								continue;
-
-							if ( k > magnitude2 && !path_search_long(NULL, m, x0, y0, xi, yi, CELL_CHKWALL) )
-								continue; //Targets beyond the initial ending point need the wall check.
-
-							k  = ( k << 4 ) / magnitude2; //k will be between 1~16 instead of 0~1
-							xi <<= 4;
-							yi <<= 4;
-							xu = ( x0 << 4 ) + k * ( x1 - x0 );
-							yu = ( y0 << 4 ) + k * ( y1 - y0 );
-							k  = MAGNITUDE2(xi, yi, xu, yu);
-
-							//If all dot coordinates were <<4 the square of the magnitude is <<8
-							if ( k > range )
-								continue;
-
-							bl_list[ bl_list_count++ ] = bl;
-						}
-					}
-				}
-			}
-
-			if( bl_list_count >= BL_LIST_MAX )
-				ShowWarning("map_foreachinpath: block count too many!\n");
-
-			iMap->freeblock_lock();
-
-			for( i = blockcount; i < bl_list_count; i++ )
-				if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-					va_start(ap, type);
-					returnCount += func(bl_list[ i ], ap);
-					va_end(ap);
-				}
-
-				iMap->freeblock_unlock();
+	bl_getall_area(type, m, mx0, my0, mx1, my1, bl_vgetall_inpath, m, x0, y0, x1, y1, range, len_limit, magnitude2);
 
-				bl_list_count = blockcount;
-				return returnCount;	//[Skotlex]
+	va_start(ap, type);
+	returnCount = bl_vforeach(func, blockcount, INT_MAX, ap);
+	va_end(ap);
 
-}
-
-// Copy of map_foreachincell, but applied to the whole map. [Skotlex]
-int map_foreachinmap(int (*func)(struct block_list*,va_list), int16 m, int type,...) {
-	int b, bsize;
-	int returnCount = 0;  //total sum of returned values of func() [Skotlex]
-	struct block_list *bl;
-	int blockcount = bl_list_count, i;
-	va_list ap;
-
-	bsize = map[ m ].bxs * map[ m ].bys;
-
-	if( type&~BL_MOB )
-		for( b = 0; b < bsize; b++ )
-			for( bl = map[ m ].block[ b ]; bl != NULL; bl = bl->next )
-				if( bl->type&type && bl_list_count < BL_LIST_MAX )
-					bl_list[ bl_list_count++ ] = bl;
-
-	if( type&BL_MOB )
-		for( b = 0; b < bsize; b++ )
-			for( bl = map[ m ].block_mob[ b ]; bl != NULL; bl = bl->next )
-				if( bl_list_count < BL_LIST_MAX )
-					bl_list[ bl_list_count++ ] = bl;
-
-	if( bl_list_count >= BL_LIST_MAX )
-		ShowWarning("map_foreachinmap: block count too many!\n");
-
-	iMap->freeblock_lock();
-
-	for( i = blockcount; i < bl_list_count ; i++ )
-		if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-			va_start(ap, type);
-			returnCount += func(bl_list[ i ], ap);
-			va_end(ap);
-		}
-
-		iMap->freeblock_unlock();
-
-		bl_list_count = blockcount;
-		return returnCount;
-}
-// Copy of map_foreachinmap, but applied to all maps in a instance id. [Ind/Hercules]
-int map_foreachininstance(int (*func)(struct block_list*,va_list), int16 instance_id, int type,...) {
-	int b, bsize;
-	int returnCount = 0;  //total sum of returned values of func() [Skotlex]
-	struct block_list *bl;
-	int blockcount = bl_list_count, i, j;
-	int16 m;
-	va_list ap;
-
-	for( j = 0; j < instances[instance_id].num_map; j++ ) {
-
-		m = instances[instance_id].map[j];
-
-		bsize = map[ m ].bxs * map[ m ].bys;
-
-		if( type&~BL_MOB )
-			for( b = 0; b < bsize; b++ )
-				for( bl = map[ m ].block[ b ]; bl != NULL; bl = bl->next )
-					if( bl->type&type && bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
-
-		if( type&BL_MOB )
-			for( b = 0; b < bsize; b++ )
-				for( bl = map[ m ].block_mob[ b ]; bl != NULL; bl = bl->next )
-					if( bl_list_count < BL_LIST_MAX )
-						bl_list[ bl_list_count++ ] = bl;
-
-		if( bl_list_count >= BL_LIST_MAX )
-			ShowWarning("map_foreachininstance: block count too many!\n");
-
-		iMap->freeblock_lock();
-
-		for( i = blockcount; i < bl_list_count ; i++ )
-			if( bl_list[ i ]->prev ) { //func() may delete this bl_list[] slot, checking for prev ensures it wasnt queued for deletion.
-				va_start(ap, type);
-				returnCount += func(bl_list[ i ], ap);
-				va_end(ap);
-			}
-
-			iMap->freeblock_unlock();
-
-	}
-
-	bl_list_count = blockcount;
 	return returnCount;
 }
+#undef MAGNITUDE2
 
+/** @} */
 
 /// Generates a new flooritem object id from the interval [MIN_FLOORITEM, MAX_FLOORITEM).
 /// Used for floor items, skill units and chatroom objects.
diff --git a/src/map/map.h b/src/map/map.h
index 7826e00b3..4bee9c8ea 100644
--- a/src/map/map.h
+++ b/src/map/map.h
@@ -546,8 +546,19 @@ struct map_data {
 	char name[MAP_NAME_LENGTH];
 	uint16 index; // The map index used by the mapindex* functions.
 	struct mapcell* cell; // Holds the information of each map cell (NULL if the map is not on this map-server).
-	struct block_list **block;
-	struct block_list **block_mob;
+	
+	/* 2D Orthogonal Range Search: Grid Implementation
+	   "Algorithms in Java, Parts 1-4" 3.18, Robert Sedgewick
+	   Map is divided into squares, called blocks (side length = BLOCK_SIZE).
+	   For each block there is a linked list of objects in that block (block_list).
+	   Array provides capability to access immediately the set of objects close 
+	   to a given object.
+	   The linked lists provide the flexibility to store the objects without 
+	   knowing ahead how many objects fall into each block.
+	*/
+	struct block_list **block; // Grid array of block_lists containing only non-BL_MOB objects
+	struct block_list **block_mob; // Grid array of block_lists containing only BL_MOB objects
+	
 	int16 m;
 	int16 xs,ys; // map dimensions (in cells)
 	int16 bxs,bys; // map dimensions (in blocks)
diff --git a/src/map/mob.c b/src/map/mob.c
index 601ecd110..9cd05a8a3 100644
--- a/src/map/mob.c
+++ b/src/map/mob.c
@@ -1364,7 +1364,7 @@ int mob_randomwalk(struct mob_data *md,unsigned int tick)
 	speed=iStatus->get_speed(&md->bl);
 	for(i=c=0;i<md->ud.walkpath.path_len;i++){	// The next walk start time is calculated.
 		if(md->ud.walkpath.path[i]&1)
-			c+=speed*14/10;
+			c+=speed*MOVE_DIAGONAL_COST/MOVE_COST;
 		else
 			c+=speed;
 	}
diff --git a/src/map/path.c b/src/map/path.c
index 95895cb2a..32a4189bb 100644
--- a/src/map/path.c
+++ b/src/map/path.c
@@ -2,25 +2,55 @@
 // For more information, see LICENCE in the main folder
 
 #include "../common/cbasetypes.h"
+#include "../common/db.h"
+#include "../common/malloc.h"
 #include "../common/nullpo.h"
 #include "../common/random.h"
 #include "../common/showmsg.h"
-#include "../common/malloc.h"
-#include "map.h"
-#include "battle.h"
+
 #include "path.h"
+#include "map.h"
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
+#define SET_OPEN 0
+#define SET_CLOSED 1
+
+#define DIR_NORTH 1
+#define DIR_WEST 2
+#define DIR_SOUTH 4
+#define DIR_EAST 8
+
+/// @name Structures and defines for A* pathfinding
+/// @{
+
+/// Path node
+struct path_node {
+	struct path_node *parent; ///< pointer to parent (for path reconstruction)
+	short x; ///< X-coordinate
+	short y; ///< Y-coordinate
+	short g_cost; ///< Actual cost from start to this node
+	short f_cost; ///< g_cost + heuristic(this, goal)
+	short flag; ///< SET_OPEN / SET_CLOSED
+};
+
+/// Binary heap of path nodes
+BHEAP_STRUCT_DECL(node_heap, struct path_node*);
 
-#define MAX_HEAP 150
+/// Comparator for binary heap of path nodes (minimum cost at top)
+#define NODE_MINTOPCMP(i,j) ((i)->f_cost - (j)->f_cost)
 
-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] =
+/// Estimates the cost from (x0,y0) to (x1,y1).
+/// This is inadmissible (overestimating) heuristic used by game client.
+#define heuristic(x0, y0, x1, y1)	(MOVE_COST * (abs((x1) - (x0)) + abs((y1) - (y0)))) // Manhattan distance
+/// @}
+
+// Translates dx,dy into walking direction
+static const unsigned char walk_choices [3][3] =
 {
 	{1,0,7},
 	{2,-1,6},
@@ -28,124 +58,6 @@ const char walk_choices [3][3] =
 };
 
 /*==========================================
- * heap push (helper function)
- *------------------------------------------*/
-static void push_heap_path(int *heap,struct tmp_path *tp,int index)
-{
-	int i,h;
-
-	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;
-
-	heap[h+1] = index;
-}
-
-/*==========================================
- * heap update (helper function)
- * Move toward the root because cost has decreased.
- *------------------------------------------*/
-static void update_heap_path(int *heap,struct tmp_path *tp,int index)
-{
-	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);
-	}
-
-	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 pop (helper function)
- *------------------------------------------*/
-static int pop_heap_path(int *heap,struct tmp_path *tp)
-{
-	int i,h,k;
-	int ret,last;
-
-	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;
-	}
-
-	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;
-
-	heap[h+1]=last;
-
-	return ret;
-}
-
-/*==========================================
- * calculate cost for the specified position
- *------------------------------------------*/
-static int calc_cost(struct tmp_path *p,int16 x1,int16 y1)
-{
-	int xd = abs(x1 - p->x);
-	int yd = abs(y1 - p->y);
-	return (xd + yd)*10 + p->dist;
-}
-
-/*==========================================
- * attach/adjust path if neccessary
- *------------------------------------------*/
-static int add_path(int *heap,struct tmp_path *tp,int16 x,int16 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;
-}
-
-/*==========================================
  * Find the closest reachable cell, 'count' cells away from (x0,y0) in direction (dx,dy).
  * Income after the coordinates of the blow
  *------------------------------------------*/
@@ -262,164 +174,250 @@ bool path_search_long(struct shootpath_data *spd,int16 m,int16 x0,int16 y0,int16
 	return true;
 }
 
+/// @name A* pathfinding related functions
+/// @{
+
+/// Pushes path_node to the binary node_heap.
+/// Ensures there is enough space in array to store new element.
+static void heap_push_node(struct node_heap *heap, struct path_node *node)
+{
+	BHEAP_ENSURE(*heap, 1, 256);
+	BHEAP_PUSH(*heap, node, NODE_MINTOPCMP, swap_ptr);
+}
+
+/// Updates path_node in the binary node_heap.
+static int heap_update_node(struct node_heap *heap, struct path_node *node)
+{
+	int i;
+	ARR_FIND(0, BHEAP_LENGTH(*heap), i, BHEAP_DATA(*heap)[i] == node);
+	if (i == BHEAP_LENGTH(*heap)) {
+		ShowError("heap_update_node: node not found\n");
+		return 1;
+	}
+	BHEAP_POPINDEX(*heap, i, NODE_MINTOPCMP, swap_ptr);
+	BHEAP_PUSH(*heap, node, NODE_MINTOPCMP, swap_ptr);
+	return 0;
+}
+
+/// Path_node processing in A* pathfinding.
+/// Adds new node to heap and updates/re-adds old ones if necessary.
+static int add_path(struct node_heap *heap, struct path_node *tp, int16 x, int16 y, int g_cost, struct path_node *parent, int h_cost)
+{
+	int i = calc_index(x, y);
+
+	if (tp[i].x == x && tp[i].y == y) { // We processed this node before
+		if (g_cost < tp[i].g_cost) { // New path to this node is better than old one
+			// Update costs and parent
+			tp[i].g_cost = g_cost;
+			tp[i].parent = parent; 
+			tp[i].f_cost = g_cost + h_cost;
+			if (tp[i].flag == SET_CLOSED) {
+				heap_push_node(heap, &tp[i]); // Put it in open set again
+			}
+			else if (heap_update_node(heap, &tp[i])) {
+				return 1;
+			}
+			tp[i].flag = SET_OPEN;
+		}
+		return 0;
+	}
+
+	if (tp[i].x || tp[i].y) // Index is already taken; see `tp` array FIXME for details
+		return 1;
+
+	// New node
+	tp[i].x = x;
+	tp[i].y = y;
+	tp[i].g_cost = g_cost;
+	tp[i].parent = parent;
+	tp[i].f_cost = g_cost + h_cost;
+	tp[i].flag = SET_OPEN;
+	heap_push_node(heap, &tp[i]);
+	return 0;
+}
+///@}
+
 /*==========================================
  * path search (x0,y0)->(x1,y1)
  * wpd: path info will be written here
  * flag: &1 = easy path search only
  * cell: type of obstruction to check for
  *------------------------------------------*/
-bool path_search(struct walkpath_data *wpd,int16 m,int16 x0,int16 y0,int16 x1,int16 y1,int flag,cell_chk cell)
+bool path_search(struct walkpath_data *wpd, int16 m, int16 x0, int16 y0, int16 x1, int16 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;
+	register int i, j, x, y, dx, dy;
 	struct map_data *md;
 	struct walkpath_data s_wpd;
 
-	if( wpd == NULL )
+	if (wpd == NULL)
 		wpd = &s_wpd; // use dummy output variable
 
-	if( !map[m].cell )
+	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 )
+	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)*/ )
+	if (x0 < 0 || x0 >= md->xs || y0 < 0 || y0 >= md->ys /*|| md->getcellp(md,x0,y0,cell)*/)
 #endif
 		return false;
-	if( x1 < 0 || x1 >= md->xs || y1 < 0 || y1 >= md->ys || md->getcellp(md,x1,y1,cell) )
+
+	// Check destination cell
+	if (x1 < 0 || x1 >= md->xs || y1 < 0 || y1 >= md->ys || md->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;
+	if (flag&1) {
+		// Try finding direct path to target
+		// Direct path goes diagonally first, then in straight line.
 
-	// 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++;
+		// 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;
 
-		x += dx;
-		y += dy;
+		x = x0; // Current position = starting cell
+		y = y0;
+		i = 0;
+		while( i < ARRAYLENGTH(wpd->path) )
+		{
+			wpd->path[i] = walk_choices[-dy + 1][dx + 1];
+			i++;
 
-		if( x == x1 ) dx = 0;
-		if( y == y1 ) dy = 0;
+			x += dx; // Advance current position
+			y += dy;
 
-		if( dx == 0 && dy == 0 )
-			break; // success
-		if( md->getcellp(md,x,y,cell) )
-			break; // obstacle = failure
-	}
+			if( x == x1 ) dx = 0; // destination x reached, no longer move along x-axis
+			if( y == y1 ) dy = 0; // destination y reached, no longer move along y-axis
 
-	if( x == x1 && y == y1 )
-	{ //easy path successful.
-		wpd->path_len = i;
-		wpd->path_pos = 0;
-		return true;
+			if( dx == 0 && dy == 0 )
+				break; // success
+			if( md->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;
+		}
+
+		return false; // easy path unsuccessful 
 	}
+	else { // !(flag&1)
+		// A* (A-star) pathfinding
+		// We always use A* for finding walkpaths because it is what game client uses.
+		// Easy pathfinding cuts corners of non-walkable cells, but client always walks around it.
+		
+		BHEAP_STRUCT_VAR(node_heap, open_set); // 'Open' set
+
+		// FIXME: This array is too small to ensure all paths shorter than MAX_WALKPATH
+		// can be found without node collision: calc_index(node1) = calc_index(node2).
+		// Figure out more proper size or another way to keep track of known nodes.
+		struct path_node tp[MAX_WALKPATH * MAX_WALKPATH];
+		struct path_node *current, *it;
+		int xs = md->xs - 1;
+		int ys = md->ys - 1;
+		int len = 0;
+		memset(tp, 0, sizeof(tp));
+
+		// Start node
+		i = calc_index(x0, y0);
+		tp[i].parent = NULL;
+		tp[i].x      = x0;
+		tp[i].y      = y0;
+		tp[i].g_cost = 0;
+		tp[i].f_cost = heuristic(x0, y0, x1, y1);
+		tp[i].flag   = SET_OPEN;
+
+		heap_push_node(&open_set, &tp[i]); // Put start node to 'open' set
+		for(;;)
+		{
+			int e = 0; // error flag
 
-	if( flag&1 )
-		return false;
+			// Saves allowed directions for the current cell. Diagonal directions
+			// are only allowed if both directions around it are allowed. This is
+			// to prevent cutting corner of nearby wall.
+			// For example, you can only go NW from the current cell, if you can
+			// go N *and* you can go W. Otherwise you need to walk around the
+			// (corner of the) non-walkable cell.
+			int allowed_dirs = 0;
 
-	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};
+			int g_cost;
 
-		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 && !md->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  && !md->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  && !md->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 && !md->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) && !md->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) && !md->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) && !md->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) && !md->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 (BHEAP_LENGTH(open_set) == 0) {
+				BHEAP_CLEAR(open_set);
+				return false;
+			}
 
-	if( !(x==x1 && y==y1) ) // will never happen...
-		return false;
+			current = BHEAP_PEEK(open_set); // Look for the lowest f_cost node in the 'open' set
+			BHEAP_POP(open_set, NODE_MINTOPCMP, swap_ptr); // Remove it from 'open' set
 
-	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;
+			x      = current->x;
+			y      = current->y;
+			g_cost = current->g_cost;
+
+			current->flag = SET_CLOSED; // Add current node to 'closed' set
 
-	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;
-		uint8 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) );
+			if (x == x1 && y == y1) {
+				BHEAP_CLEAR(open_set);
+				break;
+			}
+
+			if (y < ys && !md->getcellp(md, x, y+1, cell)) allowed_dirs |= DIR_NORTH;
+			if (y >  0 && !md->getcellp(md, x, y-1, cell)) allowed_dirs |= DIR_SOUTH;
+			if (x < xs && !md->getcellp(md, x+1, y, cell)) allowed_dirs |= DIR_EAST;
+			if (x >  0 && !md->getcellp(md, x-1, y, cell)) allowed_dirs |= DIR_WEST;
+
+#define chk_dir(d) ((allowed_dirs & (d)) == (d))
+			// Process neighbors of current node
+			// TODO: Processing order affects chosen path if there is more than one path with same cost.
+			// In few cases path found by server will be different than path found by game client.
+			if (chk_dir(DIR_SOUTH))
+				e += add_path(&open_set, tp, x, y-1, g_cost + MOVE_COST, current, heuristic(x, y-1, x1, y1)); // (x, y-1) 4
+			if (chk_dir(DIR_SOUTH|DIR_WEST) && !md->getcellp(md, x-1, y-1, cell))
+				e += add_path(&open_set, tp, x-1, y-1, g_cost + MOVE_DIAGONAL_COST, current, heuristic(x-1, y-1, x1, y1)); // (x-1, y-1) 3
+			if (chk_dir(DIR_WEST))
+				e += add_path(&open_set, tp, x-1, y, g_cost + MOVE_COST, current, heuristic(x-1, y, x1, y1)); // (x-1, y) 2
+			if (chk_dir(DIR_NORTH|DIR_WEST) && !md->getcellp(md, x-1, y+1, cell))
+				e += add_path(&open_set, tp, x-1, y+1, g_cost + MOVE_DIAGONAL_COST, current, heuristic(x-1, y+1, x1, y1)); // (x-1, y+1) 1
+			if (chk_dir(DIR_NORTH))
+				e += add_path(&open_set, tp, x, y+1, g_cost + MOVE_COST, current, heuristic(x, y+1, x1, y1)); // (x, y+1) 0
+			if (chk_dir(DIR_NORTH|DIR_EAST) && !md->getcellp(md, x+1, y+1, cell))
+				e += add_path(&open_set, tp, x+1, y+1, g_cost + MOVE_DIAGONAL_COST, current, heuristic(x+1, y+1, x1, y1)); // (x+1, y+1) 7
+			if (chk_dir(DIR_EAST))
+				e += add_path(&open_set, tp, x+1, y, g_cost + MOVE_COST, current, heuristic(x+1, y, x1, y1)); // (x+1, y) 6
+			if (chk_dir(DIR_SOUTH|DIR_EAST) && !md->getcellp(md, x+1, y-1, cell))
+				e += add_path(&open_set, tp, x+1, y-1, g_cost + MOVE_DIAGONAL_COST, current, heuristic(x+1, y-1, x1, y1)); // (x+1, y-1) 5
+#undef chk_dir
+			if (e) {
+				BHEAP_CLEAR(open_set);
+				return false;
+			}
 		}
-		wpd->path[j] = dir;
-	}
 
-	return true;
+		for (it = current; it->parent != NULL; it = it->parent, len++);
+		if (len > sizeof(wpd->path)) {
+			return false;
+		}
+
+		// Recreate path
+		wpd->path_len = len;
+		wpd->path_pos = 0;
+		for (it = current, j = len-1; j >= 0; it = it->parent, j--) {
+			dx = it->x - it->parent->x;
+			dy = it->y - it->parent->y;
+			wpd->path[j] = walk_choices[-dy + 1][dx + 1];
+		}
+		return true;
+	} // A* end
+
+	return false;
 }
 
 
-//Distance functions, taken from http://www.flpcode.com/articles/article_fastdistance.shtml
+//Distance functions, taken from http://www.flipcode.com/articles/article_fastdistance.shtml
 int check_distance(int dx, int dy, int distance)
 {
 #ifdef CIRCULAR_AREA
@@ -439,7 +437,7 @@ unsigned int distance(int dx, int dy)
 
 	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]
+	//There appears to be something wrong with the approximation below when either dx/dy is 0! [Skotlex]
 	if ( dx == 0 ) return dy;
 	if ( dy == 0 ) return dx;
 
diff --git a/src/map/path.h b/src/map/path.h
index b1ca71955..5bc551dc9 100644
--- a/src/map/path.h
+++ b/src/map/path.h
@@ -6,6 +6,9 @@
 
 #include "map.h" // enum cell_chk
 
+#define MOVE_COST 10
+#define MOVE_DIAGONAL_COST 14
+
 #define MAX_WALKPATH 32
 
 struct walkpath_data {
diff --git a/src/map/pet.c b/src/map/pet.c
index 62a884316..c83027f2a 100644
--- a/src/map/pet.c
+++ b/src/map/pet.c
@@ -817,7 +817,7 @@ static int pet_randomwalk(struct pet_data *pd,unsigned int tick)
 		}
 		for(i=c=0;i<pd->ud.walkpath.path_len;i++){
 			if(pd->ud.walkpath.path[i]&1)
-				c+=pd->status.speed*14/10;
+				c+=pd->status.speed*MOVE_DIAGONAL_COST/MOVE_COST;
 			else
 				c+=pd->status.speed;
 		}
diff --git a/src/map/skill.c b/src/map/skill.c
index 835d5cca9..9ef768382 100644
--- a/src/map/skill.c
+++ b/src/map/skill.c
@@ -6634,7 +6634,9 @@ int skill_castend_nodamage_id (struct block_list *src, struct block_list *bl, ui
 				if(iStatus->isimmune(bl) || !tsc || !tsc->count)
 					break;
 				
-				if( sd && dstsd && !map_flag_vs(sd->bl.m) && sd->status.guild_id == dstsd->status.guild_id ) {
+				if( sd && dstsd && !map_flag_vs(sd->bl.m)
+						&& (sd->status.party_id == 0 || sd->status.party_id != dstsd->status.party_id) ) {
+					// Outside PvP it should only affect party members
 					clif->skill_fail(sd,skill_id,USESKILL_FAIL_LEVEL,0);
 					break;
 				}
diff --git a/src/map/status.c b/src/map/status.c
index 7d5676b98..2f1950c47 100644
--- a/src/map/status.c
+++ b/src/map/status.c
@@ -6865,11 +6865,11 @@ int status_change_start(struct block_list* bl,enum sc_type type,int rate,int val
 	case SC__STRIPACCESSARY:
 		if( sd ) {
 			int i = -1;
-			if( !(sd->bonus.unstripable_equip&EQI_ACC_L) ) {
+			if( !(sd->bonus.unstripable_equip&EQP_ACC_L) ) {
 				i = sd->equip_index[EQI_ACC_L];
 				if( i >= 0 && sd->inventory_data[i] && sd->inventory_data[i]->type == IT_ARMOR )
 					pc->unequipitem(sd,i,3); //L-Accessory
-			} if( !(sd->bonus.unstripable_equip&EQI_ACC_R) ) {
+			} if( !(sd->bonus.unstripable_equip&EQP_ACC_R) ) {
 				i = sd->equip_index[EQI_ACC_R];
 				if( i >= 0 && sd->inventory_data[i] && sd->inventory_data[i]->type == IT_ARMOR )
 					pc->unequipitem(sd,i,3); //R-Accessory
diff --git a/src/map/unit.c b/src/map/unit.c
index 36f3eab45..b1ed24666 100644
--- a/src/map/unit.c
+++ b/src/map/unit.c
@@ -107,9 +107,9 @@ int unit_walktoxy_sub(struct block_list *bl)
 		   ud->walkpath.path_len--;
 			dir = ud->walkpath.path[ud->walkpath.path_len];
 			if(dir&1)
-				i-=14;
+				i -= MOVE_DIAGONAL_COST;
 			else
-				i-=10;
+				i -= MOVE_COST;
 			ud->to_x -= dirx[dir];
 			ud->to_y -= diry[dir];
 		}
@@ -126,7 +126,7 @@ int unit_walktoxy_sub(struct block_list *bl)
 	if(ud->walkpath.path_pos>=ud->walkpath.path_len)
 		i = -1;
 	else if(ud->walkpath.path[ud->walkpath.path_pos]&1)
-		i = iStatus->get_speed(bl)*14/10;
+		i = iStatus->get_speed(bl)*MOVE_DIAGONAL_COST/MOVE_COST;
 	else
 		i = iStatus->get_speed(bl);
 	if( i > 0)
@@ -346,14 +346,16 @@ int unit_walktoxy( struct block_list *bl, short x, short y, int flag)
 
 	if( ud == NULL) return 0;
 
-	path_search(&wpd, bl->m, bl->x, bl->y, x, y, flag&1, CELL_CHKNOPASS); // Count walk path cells
+	if (!path_search(&wpd, bl->m, bl->x, bl->y, x, y, flag&1, CELL_CHKNOPASS)) // Count walk path cells
+		return 0;
+
 #ifdef OFFICIAL_WALKPATH
 	if( !path_search_long(NULL, bl->m, bl->x, bl->y, x, y, CELL_CHKNOPASS) // Check if there is an obstacle between
 		&& (wpd.path_len > (battle_config.max_walk_path/17)*14) // Official number of walkable cells is 14 if and only if there is an obstacle between. [malufett]
 		&& (bl->type != BL_NPC) ) // If type is a NPC, please disregard.
 		return 0;
 #endif
-	if( (battle_config.max_walk_path < wpd.path_len) && (bl->type != BL_NPC) )
+	if ((wpd.path_len > battle_config.max_walk_path) && (bl->type != BL_NPC))
 		return 0;
 
 	if (flag&4 && DIFF_TICK(ud->canmove_tick, iTimer->gettick()) > 0 &&