-//#define PATHLIB_RDFIELDS
-#ifdef PATHLIB_RDFIELDS
- #define path_next swampslug
- #define path_prev lasertarget
-#else
- .entity path_next;
- .entity path_prev;
-#endif
+#include "pathlib.qh"
+#include "_all.qh"
#define medium spawnshieldtime
//#define DEBUGPATHING
-
-entity openlist;
-entity closedlist;
-entity scraplist;
-
-.float pathlib_node_g;
-.float pathlib_node_h;
-.float pathlib_node_f;
-
-float pathlib_open_cnt;
-float pathlib_closed_cnt;
-float pathlib_made_cnt;
-float pathlib_merge_cnt;
-float pathlib_recycle_cnt;
-float pathlib_searched_cnt;
-
-#ifdef DEBUGPATHING
-
-#endif
-
-float pathlib_bestopen_seached;
-float pathlib_bestcash_hits;
-float pathlib_bestcash_saved;
-
-float pathlib_gridsize;
-
-float pathlib_movecost;
-float pathlib_movecost_diag;
-float pathlib_movecost_waterfactor;
-
-float pathlib_edge_check_size;
-
-float pathlib_foundgoal;
-entity goal_node;
-
-entity best_open_node;
-.float is_path_node;
-
-
#ifdef DEBUGPATHING
float edge_show(vector point,float fsize);
void mark_error(vector where,float lifetime);
}
}
-float fsnap(float val,float fsize)
-{
- return rint(val / fsize) * fsize;
-}
-
-vector vsnap(vector point,float fsize)
-{
- vector vret;
-
- vret_x = rint(point_x / fsize) * fsize;
- vret_y = rint(point_y / fsize) * fsize;
- vret_z = ceil(point_z / fsize) * fsize;
-
- return vret;
-}
-
float walknode_stepsize;
vector walknode_stepup;
vector walknode_maxdrop;
return 0;
}
-#define inwater(point) (pointcontents(point) == CONTENT_WATER)
-/*
-float inwater(vector point)
-{
- if(pointcontents(point) == CONTENT_WATER)
- return 1;
- return 0;
-}
-*/
-
#define _pcheck(p) traceline(p+z_up,p-z_down,MOVE_WORLDONLY,self); if (!floor_ok(trace_endpos)) return 1
float edge_check(vector point,float fsize)
{
pathlib_movenode_goodnode = 0;
- end_x = fsnap(end_x, pathlib_gridsize);
- end_y = fsnap(end_y, pathlib_gridsize);
+ end.x = fsnap(end.x, pathlib_gridsize);
+ end.y = fsnap(end.y, pathlib_gridsize);
traceline(end + ('0 0 0.25' * pathlib_gridsize),end - ('0 0 1' * pathlib_gridsize),MOVE_WORLDONLY,self);
end = trace_endpos;
if(pointcontents(end - '0 0 1') != CONTENT_SOLID)
return end;
- for(surface = start ; surface_z < (end_z + 32); ++surface_z)
+ for(surface = start ; surface.z < (end.z + 32); ++surface.z)
{
if(pointcontents(surface) == CONTENT_EMPTY)
break;
if(trace_fraction == 1)
pathlib_movenode_goodnode = 1;
- if(fabs(surface_z - end_z) > 32)
+ if(fabs(surface.z - end.z) > 32)
pathlib_movenode_goodnode = 0;
return end;
if(pointcontents(start) != CONTENT_WATER)
return end;
- end_x = fsnap(end_x, pathlib_gridsize);
- end_y = fsnap(end_y, pathlib_gridsize);
+ end.x = fsnap(end.x, pathlib_gridsize);
+ end.y = fsnap(end.y, pathlib_gridsize);
if(pointcontents(end) == CONTENT_EMPTY)
- return pathlib_wateroutnode( start, end);
+ return pathlib_wateroutnode( start, end, doedge);
tracebox(start, walknode_boxmin,walknode_boxmax, end, MOVE_WORLDONLY, self);
if(trace_fraction == 1)
{
pathlib_movenode_goodnode = 0;
- end_x = fsnap(end_x, pathlib_gridsize);
- end_y = fsnap(end_y, pathlib_gridsize);
+ end.x = fsnap(end.x, pathlib_gridsize);
+ end.y = fsnap(end.y, pathlib_gridsize);
tracebox(start, walknode_boxmin,walknode_boxmax, end, MOVE_WORLDONLY, self);
if(trace_fraction == 1)
s = start;
e = end;
- e_z = 0;
- s_z = 0;
+ e.z = 0;
+ s.z = 0;
direction = normalize(s - e);
distance = vlen(start - end);
point = last_point + direction * walknode_stepsize * laststep;
- point_x = fsnap(point_x, pathlib_gridsize);
- point_y = fsnap(point_y, pathlib_gridsize);
+ point.x = fsnap(point.x, pathlib_gridsize);
+ point.y = fsnap(point.y, pathlib_gridsize);
s = point + walknode_stepup;
e = point - walknode_maxdrop;
//h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))
float h;
- h = fabs(a_x - b_x);
- h += fabs(a_y - b_y);
+ h = fabs(a.x - b.x);
+ h += fabs(a.y - b.y);
h *= pathlib_gridsize;
return h;
//h(n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))
float h,x,y;
- x = fabs(a_x - b_x);
- y = fabs(a_y - b_y);
+ x = fabs(a.x - b.x);
+ y = fabs(a.y - b.y);
h = pathlib_movecost * max(x,y);
return h;
h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
*/
- x = fabs(a_x - b_x);
- y = fabs(a_y - b_y);
+ x = fabs(a.x - b.x);
+ y = fabs(a.y - b.y);
h_diag = min(x,y);
h_str = x + y;
//h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
//h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
- x = fabs(point_x - end_x);
- y = fabs(point_y - end_y);
- z = fabs(point_z - end_z);
+ x = fabs(point.x - end.x);
+ y = fabs(point.y - end.y);
+ z = fabs(point.z - end.z);
h_diag = min3(x,y,z);
h_str = x + y + z;
//h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
//h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
- x = fabs(a_x - b_x);
- y = fabs(a_y - b_y);
- z = fabs(a_z - b_z);
+ x = fabs(a.x - b.x);
+ y = fabs(a.y - b.y);
+ z = fabs(a.z - b.z);
h_diag = min3(x,y,z);
h_str = x + y + z;
return h;
}
-//#define PATHLIB_USE_NODESCRAP
-#define PATHLIB_NODEEXPIRE 0.05
+const float PATHLIB_NODEEXPIRE = 0.05;
float pathlib_scraplist_cnt;
entity newnode()
{
#endif
++pathlib_made_cnt;
n = spawn();
-#ifdef PATHLIB_NODEEXPIRE
n.think = SUB_Remove;
n.nextthink = time + PATHLIB_NODEEXPIRE;
return n;
n.path_next = world;
n.path_prev = world;
- n.is_path_node = FALSE;
+ n.is_path_node = false;
n.owner = scraplist;
#else
- //n.is_path_node = FALSE;
+ //n.is_path_node = false;
n.think = SUB_Remove;
n.nextthink = time;
#endif
entity node;
node = newnode();
- node.is_path_node = TRUE;
+ node.is_path_node = true;
node.owner = openlist;
node.path_prev = parent;
node = findradius(where,pathlib_gridsize * 0.75);
while(node)
{
- if(node.is_path_node == TRUE)
+ if(node.is_path_node == true)
{
++pathlib_merge_cnt;
if(node.owner == openlist)
if(node.owner == closedlist)
{
- dprint("Pathlib: Tried to close a closed node!\n");
+ LOG_TRACE("Pathlib: Tried to close a closed node!\n");
return;
}
if(pathlib_movenode_goodnode)
{
goal_node = node;
- pathlib_foundgoal = TRUE;
+ pathlib_foundgoal = true;
}
}
}
{
vector point;
vector where;
- float nodecnt;
+ float nodecnt = 0;
where = node.origin;
{
vector v;
- for(v_z = node.origin_z - pathlib_gridsize; v_z <= node.origin_z + pathlib_gridsize; v_z += pathlib_gridsize)
- for(v_y = node.origin_y - pathlib_gridsize; v_y <= node.origin_y + pathlib_gridsize; v_y += pathlib_gridsize)
- for(v_x = node.origin_x - pathlib_gridsize; v_x <= node.origin_x + pathlib_gridsize; v_x += pathlib_gridsize)
+ for(v.z = node.origin.z - pathlib_gridsize; v.z <= node.origin.z + pathlib_gridsize; v.z += pathlib_gridsize)
+ for(v.y = node.origin.y - pathlib_gridsize; v.y <= node.origin.y + pathlib_gridsize; v.y += pathlib_gridsize)
+ for(v.x = node.origin.x - pathlib_gridsize; v.x <= node.origin.x + pathlib_gridsize; v.x += pathlib_gridsize)
{
if(vlen(v - node.origin))
pathlib_makenode(node,start,v,goal,pathlib_movecost);
{
entity node;
- node = findfloat(world,is_path_node, TRUE);
+ node = findfloat(world,is_path_node, true);
while(node)
{
dumpnode(node);
- node = findfloat(node,is_path_node, TRUE);
+ node = findfloat(node,is_path_node, true);
}
if(openlist)
pathlib_edge_check_size = (vlen(walknode_boxmin - walknode_boxmax) * 0.5);
- walknode_boxup = '0 0 2' * self.maxs_z;
+ walknode_boxup = '0 0 2' * self.maxs.z;
walknode_stepsize = 32;
walknode_stepup = '0 0 1' * walknode_stepsize;
walknode_maxdrop = '0 0 3' * walknode_stepsize;
- from_x = fsnap(from_x,pathlib_gridsize);
- from_y = fsnap(from_y,pathlib_gridsize);
+ from.x = fsnap(from.x,pathlib_gridsize);
+ from.y = fsnap(from.y,pathlib_gridsize);
- to_x = fsnap(to_x,pathlib_gridsize);
- to_y = fsnap(to_y,pathlib_gridsize);
+ to.x = fsnap(to.x,pathlib_gridsize);
+ to.y = fsnap(to.y,pathlib_gridsize);
- dprint("AStar init. ", ftos(pathlib_scraplist_cnt), " nodes on scrap\n");
+ LOG_TRACE("AStar init. ", ftos(pathlib_scraplist_cnt), " nodes on scrap\n");
path = pathlib_mknode(from,world);
pathlib_close_node(path,to);
if(pathlib_foundgoal)
{
- dprint("AStar: Goal found on first node!\n");
+ LOG_TRACE("AStar: Goal found on first node!\n");
open = spawn();
open.owner = open;
if(pathlib_expandnode(path,from,to) <= 0)
{
- dprint("AStar path fail.\n");
+ LOG_TRACE("AStar path fail.\n");
pathlib_cleanup();
return world;
if(pathlib_foundgoal)
{
- dprint("Target found. Rebuilding and filtering path...\n");
+ LOG_TRACE("Target found. Rebuilding and filtering path...\n");
ftime = gettime(GETTIME_REALTIME);
ptime = ftime - ptime;
#ifdef DEBUGPATHING
pathlib_showpath2(start);
- dprint("Time used - pathfinding: ", ftos(ptime),"\n");
- dprint("Time used - rebuild & filter: ", ftos(ftime),"\n");
- dprint("Time used - cleanup: ", ftos(ctime),"\n");
- dprint("Time used - total: ", ftos(ptime + ftime + ctime),"\n");
- dprint("Time used - # frames: ", ftos(ceil((ptime + ftime + ctime) / sys_frametime)),"\n\n");
- dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
- dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
- dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
- dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
- dprint("Nodes - searched: ", ftos(pathlib_searched_cnt),"\n");
+ LOG_TRACE("Time used - pathfinding: ", ftos(ptime),"\n");
+ LOG_TRACE("Time used - rebuild & filter: ", ftos(ftime),"\n");
+ LOG_TRACE("Time used - cleanup: ", ftos(ctime),"\n");
+ LOG_TRACE("Time used - total: ", ftos(ptime + ftime + ctime),"\n");
+ LOG_TRACE("Time used - # frames: ", ftos(ceil((ptime + ftime + ctime) / sys_frametime)),"\n\n");
+ LOG_TRACE("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
+ LOG_TRACE("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
+ LOG_TRACE("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
+ LOG_TRACE("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
+ LOG_TRACE("Nodes - searched: ", ftos(pathlib_searched_cnt),"\n");
if(pathlib_recycle_cnt)
- dprint("Nodes - make/reuse: ", ftos(pathlib_made_cnt / pathlib_recycle_cnt),"\n");
+ LOG_TRACE("Nodes - make/reuse: ", ftos(pathlib_made_cnt / pathlib_recycle_cnt),"\n");
if(pathlib_recycle_cnt)
- dprint("Nodes - reused: ", ftos(pathlib_recycle_cnt),"\n");
+ LOG_TRACE("Nodes - reused: ", ftos(pathlib_recycle_cnt),"\n");
- dprint("Nodes bestopen searched: ", ftos(pathlib_bestopen_seached),"\n");
- dprint("Nodes bestcash - hits: ", ftos(pathlib_bestcash_hits),"\n");
- dprint("Nodes bestcash - save: ", ftos(pathlib_bestcash_saved),"\n");
- dprint("AStar done. ", ftos(pathlib_scraplist_cnt), " nodes on scrap\n\n");
+ LOG_TRACE("Nodes bestopen searched: ", ftos(pathlib_bestopen_seached),"\n");
+ LOG_TRACE("Nodes bestcash - hits: ", ftos(pathlib_bestcash_hits),"\n");
+ LOG_TRACE("Nodes bestcash - save: ", ftos(pathlib_bestcash_saved),"\n");
+ LOG_TRACE("AStar done. ", ftos(pathlib_scraplist_cnt), " nodes on scrap\n\n");
#endif
return start;
}
}
- dprint("A* Faild to find a path! Try a smaller gridsize.\n");
+ LOG_TRACE("A* Faild to find a path! Try a smaller gridsize.\n");
pathlib_cleanup();
return world;
}
-
-
-