diff options
Diffstat (limited to 'src/map/path.c')
-rw-r--r-- | src/map/path.c | 95 |
1 files changed, 62 insertions, 33 deletions
diff --git a/src/map/path.c b/src/map/path.c index 5a9ddf9c7..9aeb108fa 100644 --- a/src/map/path.c +++ b/src/map/path.c @@ -10,6 +10,7 @@ #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <math.h> #include "map.h" #include "../common/cbasetypes.h" @@ -128,9 +129,6 @@ bool path_search_long(struct shootpath_data *spd,int16 m,int16 x0,int16 y0,int16 spd->x[0] = x0; spd->y[0] = y0; - if (md->getcellp(md,x1,y1,cell)) - return false; - if (dx > abs(dy)) { weight = dx; spd->ry = 1; @@ -141,8 +139,6 @@ bool path_search_long(struct shootpath_data *spd,int16 m,int16 x0,int16 y0,int16 while (x0 != x1 || y0 != y1) { - if (md->getcellp(md,x0,y0,cell)) - return false; wx += dx; wy += dy; if (wx >= weight) { @@ -162,6 +158,8 @@ bool path_search_long(struct shootpath_data *spd,int16 m,int16 x0,int16 y0,int16 spd->y[spd->len] = y0; spd->len++; } + if (md->getcellp(md,x0,y0,cell)) + return false; } return true; @@ -176,7 +174,7 @@ static void heap_push_node(struct node_heap *heap, struct path_node *node) { #ifndef __clang_analyzer__ // TODO: Figure out why clang's static analyzer doesn't like this BHEAP_ENSURE(*heap, 1, 256); - BHEAP_PUSH(*heap, node, NODE_MINTOPCMP, swap_ptr); + BHEAP_PUSH2(*heap, node, NODE_MINTOPCMP, swap_ptr); #endif // __clang_analyzer__ } @@ -189,8 +187,7 @@ static int heap_update_node(struct node_heap *heap, struct path_node *node) 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); + BHEAP_UPDATE(*heap, i, NODE_MINTOPCMP, swap_ptr); return 0; } @@ -251,12 +248,8 @@ bool path_search(struct walkpath_data *wpd, int16 m, int16 x0, int16 y0, int16 x return false; md = &map->list[m]; -#ifdef CELL_NOSTACK //Do not check starting cell as that would get you stuck. - if (x0 < 0 || x0 >= md->xs || y0 < 0 || y0 >= md->ys) -#else if (x0 < 0 || x0 >= md->xs || y0 < 0 || y0 >= md->ys /*|| md->getcellp(md,x0,y0,cell)*/) -#endif return false; // Check destination cell @@ -304,7 +297,7 @@ bool path_search(struct walkpath_data *wpd, int16 m, int16 x0, int16 y0, int16 x // 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 @@ -327,8 +320,8 @@ bool path_search(struct walkpath_data *wpd, int16 m, int16 x0, int16 y0, int16 x tp[i].flag = SET_OPEN; heap_push_node(&open_set, &tp[i]); // Put start node to 'open' set - for(;;) - { + + for(;;) { int e = 0; // error flag // Saves allowed directions for the current cell. Diagonal directions @@ -347,7 +340,7 @@ bool path_search(struct walkpath_data *wpd, int16 m, int16 x0, int16 y0, int16 x } 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 + BHEAP_POP2(open_set, NODE_MINTOPCMP, swap_ptr); // Remove it from 'open' set x = current->x; y = current->y; @@ -367,24 +360,22 @@ bool path_search(struct walkpath_data *wpd, int16 m, int16 x0, int16 y0, int16 x #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 + 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_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_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_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_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_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_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 #undef chk_dir if (e) { BHEAP_CLEAR(open_set); @@ -413,7 +404,7 @@ bool path_search(struct walkpath_data *wpd, int16 m, int16 x0, int16 y0, int16 x //Distance functions, taken from http://www.flipcode.com/articles/article_fastdistance.shtml -int check_distance(int dx, int dy, int distance) +bool check_distance(int dx, int dy, int distance) { #ifdef CIRCULAR_AREA //In this case, we just do a square comparison. Add 1 tile grace for diagonal range checks. @@ -453,6 +444,42 @@ unsigned int distance(int dx, int dy) return (dx<dy?dy:dx); #endif } + +/** + * The client uses a circular distance instead of the square one. The circular distance + * is only used by units sending their attack commands via the client (not monsters). + * @param dx: Horizontal distance + * @param dy: Vertical distance + * @param distance: Distance to check against + * @return Within distance(1); Not within distance(0); + */ +bool check_distance_client(int dx, int dy, int distance) +{ + if(distance < 0) distance = 0; + + return (path->distance_client(dx,dy) <= distance); +} + +/** + * The client uses a circular distance instead of the square one. The circular distance + * is only used by units sending their attack commands via the client (not monsters). + * @param dx: Horizontal distance + * @param dy: Vertical distance + * @return Circular distance + */ +int distance_client(int dx, int dy) +{ + double temp_dist = sqrt((double)(dx*dx + dy*dy)); + + //Bonus factor used by client + //This affects even horizontal/vertical lines so they are one cell longer than expected + temp_dist -= 0.0625; + + if(temp_dist < 0) temp_dist = 0; + + return ((int)temp_dist); +} + void path_defaults(void) { path = &path_s; @@ -461,4 +488,6 @@ void path_defaults(void) { path->search = path_search; path->check_distance = check_distance; path->distance = distance; + path->check_distance_client = check_distance_client; + path->distance_client = distance_client; } |