summaryrefslogtreecommitdiff
path: root/src/map/path.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/map/path.c')
-rw-r--r--src/map/path.c95
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;
}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-10-24 16:13:07 +0000