From c0c254f14d0d65a8b7ec50720ed8d98b5a04919a Mon Sep 17 00:00:00 2001 From: Piotr Hałaczkiewicz Date: Mon, 22 Jul 2013 22:50:45 +0200 Subject: Binary heap fix & improvement. Fixed a bug when removing last element of binary heap (its parent would be removed instead if it had the same value). Binary heap now allows custom swapper function/macro. Added `swap_ptr` macro to swap two pointers in place (`swap` is not suitable for pointers). This allows to store pointers in binary heap. --- src/common/cbasetypes.h | 2 ++ src/common/db.h | 19 ++++++++++++------- src/common/timer.c | 8 ++++---- 3 files changed, 18 insertions(+), 11 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 ) { -- cgit v1.2.3-70-g09d2 From 86f70d9f4ff1715dccbc101b78728c366623fe7b Mon Sep 17 00:00:00 2001 From: Piotr Hałaczkiewicz Date: Wed, 17 Jul 2013 21:13:21 +0200 Subject: Refactored map_foreach* functions. Removed a lot of duplicated code. Added some documentation & comments. --- src/map/atcommand.c | 4 +- src/map/map.c | 1120 +++++++++++++++++++++++---------------------------- src/map/map.h | 15 +- 3 files changed, 520 insertions(+), 619 deletions(-) diff --git a/src/map/atcommand.c b/src/map/atcommand.c index 29bd43d16..a0a6623cf 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 db3bcf001..fe0b93609 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 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) -- cgit v1.2.3-70-g09d2 From 78028c8b652a4edf761b6f250c2fca4b6c576dee Mon Sep 17 00:00:00 2001 From: Piotr Hałaczkiewicz Date: Tue, 23 Jul 2013 09:56:54 +0200 Subject: Pathfinding code cleanup. Now uses binary heap defined in `db.h`. Walk requests now use A* (hard) pathfinding only to match game client behavior. Added defines for movement cost. Added some documentation & comments. --- src/map/mob.c | 2 +- src/map/path.c | 486 ++++++++++++++++++++++++++++----------------------------- src/map/path.h | 3 + src/map/pet.c | 2 +- src/map/unit.c | 12 +- 5 files changed, 254 insertions(+), 251 deletions(-) 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;iud.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,149 +2,61 @@ // 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 #include #include +#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}, {3,4,5}, }; -/*========================================== - * 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 2697e8128..3e7019806 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;iud.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/unit.c b/src/map/unit.c index 4a8a87920..7c65594ca 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 && -- cgit v1.2.3-70-g09d2 From 078bbbada6272b56ecf22a98ee63345a8e35822e Mon Sep 17 00:00:00 2001 From: Haru Date: Wed, 24 Jul 2013 00:03:51 +0200 Subject: Fixed SA_DISPELL failing outside PvP against party - Follow-up to a4802eae - Fixes bugreport #7572 http://hercules.ws/board/tracker/issue-7572-dispell-2 - SA_DISPELL would fail outside PvP if caster and target are in the same party AND in the same guild at the same time. - Special thanks for kyeme (bugreport), Xgear (review.) Signed-off-by: Haru --- src/map/skill.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/src/map/skill.c b/src/map/skill.c index 28c5245bb..1cdec9322 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; } -- cgit v1.2.3-70-g09d2 From e9e8914ebfa70c1c212d0a7d7173b6da9e0e5b60 Mon Sep 17 00:00:00 2001 From: Piotr Hałaczkiewicz Date: Thu, 25 Jul 2013 22:29:07 +0200 Subject: Fixed typo in `SC__STRIPACCESSARY`. Fixed `SC__STRIPACCESSARY` checking for equip index instead of equip position. Fixes #72 --- src/map/status.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/map/status.c b/src/map/status.c index 58e844529..c0378afbc 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 -- cgit v1.2.3-70-g09d2