X-Git-Url: http://de.git.xonotic.org/?a=blobdiff_plain;f=qcsrc%2Fserver%2Fpathlib%2Fmain.qc;h=fc550fa636f029bd2f0b1e596c44dbd0b15a6a2e;hb=267283e6a4fd90c816ffb5d588628820499e827c;hp=cb38136cb0058b1d4e67d97bb2f4c1f02733edb3;hpb=daab9330abb8952053b47239d1322cd029b08cd1;p=xonotic%2Fxonotic-data.pk3dir.git diff --git a/qcsrc/server/pathlib/main.qc b/qcsrc/server/pathlib/main.qc index cb38136cb..fc550fa63 100644 --- a/qcsrc/server/pathlib/main.qc +++ b/qcsrc/server/pathlib/main.qc @@ -1,44 +1,43 @@ #include "main.qh" +#include +#include #include "pathlib.qh" #include "utility.qh" +#include #include "../command/common.qh" void pathlib_deletepath(entity start) { - entity e; + if(!start) + return; - e = findchainentity(owner, start); - while(e) + FOREACH_ENTITY_ENT(owner, start, { - setthink(e, SUB_Remove_self); - e.nextthink = time; - e = e.chain; - } + setthink(it, SUB_Remove); + it.nextthink = time; + }); } -//#define PATHLIB_NODEEXPIRE 0.05 -const float PATHLIB_NODEEXPIRE = 20; +const float PATHLIB_NODEEXPIRE = 20; // 0.05 void dumpnode(entity n) { + if(n.is_path_node) + IL_REMOVE(g_pathlib_nodes, n); n.is_path_node = false; - setthink(n, SUB_Remove_self); + setthink(n, SUB_Remove); n.nextthink = time; } #if DEBUGPATHING -void pathlib_showpath(entity start); -void pathlib_showpath2(entity path); -void pathlib_showsquare(vector where,float goodsquare,float _lifetime); +#include "debug.qh" #endif entity pathlib_mknode(vector where,entity parent) { - entity node; - - node = pathlib_nodeatpoint(where); + entity node = pathlib_nodeatpoint(where); if(node) { #ifdef TURRET_DEBUG @@ -49,17 +48,16 @@ entity pathlib_mknode(vector where,entity parent) node = spawn(); - setthink(node, SUB_Remove_self); + setthink(node, SUB_Remove); node.nextthink = time + PATHLIB_NODEEXPIRE; + IL_PUSH(g_pathlib_nodes, node); node.is_path_node = true; node.owner = openlist; node.path_prev = parent; - setsize(node, '0 0 0', '0 0 0'); setorigin(node, where); - node.medium = pointcontents(where); #if DEBUGPATHING pathlib_showsquare(where, 1 ,15); #endif @@ -69,17 +67,16 @@ entity pathlib_mknode(vector where,entity parent) return node; } -float pathlib_makenode_adaptive(entity parent,vector start, vector to, vector goal,float cost) +bool pathlib_makenode_adaptive(entity parent,vector start, vector to, vector goal,float cost) { - entity node; - float h,g,f,doedge = 0; - vector where; + bool dodge = false; + float f, h, g; ++pathlib_searched_cnt; if(inwater(parent.origin)) { - LOG_TRACE("FromWater\n"); + LOG_DEBUG("FromWater"); pathlib_expandnode = pathlib_expandnode_box; pathlib_movenode = pathlib_swimnode; } @@ -87,32 +84,32 @@ float pathlib_makenode_adaptive(entity parent,vector start, vector to, vector go { if(inwater(to)) { - LOG_TRACE("ToWater\n"); + LOG_DEBUG("ToWater"); pathlib_expandnode = pathlib_expandnode_box; pathlib_movenode = pathlib_walknode; } else { - LOG_TRACE("LandToLoand\n"); + LOG_DEBUG("LandToLoand"); //if(edge_check(parent.origin)) // return 0; pathlib_expandnode = pathlib_expandnode_star; pathlib_movenode = pathlib_walknode; - doedge = 1; + dodge = true; } } - node = pathlib_nodeatpoint(to); + entity node = pathlib_nodeatpoint(to); if(node) { - LOG_TRACE("NodeAtPoint\n"); + LOG_DEBUG("NodeAtPoint"); ++pathlib_merge_cnt; if(node.owner == openlist) { h = pathlib_heuristic(node.origin,goal); - g = pathlib_cost(parent,node.origin,cost); + float g = pathlib_cost(parent,node.origin,cost); f = g + h; if(node.pathlib_node_g > g) @@ -130,38 +127,38 @@ float pathlib_makenode_adaptive(entity parent,vector start, vector to, vector go best_open_node = node; } - return 1; + return true; } - where = pathlib_movenode(parent, parent.origin, to, 0); + vector where = pathlib_movenode(parent, parent.origin, to, 0); if (!pathlib_movenode_goodnode) { //pathlib_showsquare(where, 0 ,30); //pathlib_showsquare(parent.origin, 1 ,30); - LOG_TRACE("pathlib_movenode_goodnode = 0\n"); - return 0; + LOG_DEBUG("pathlib_movenode_goodnode = 0"); + return false; } //pathlib_showsquare(where, 1 ,30); if(pathlib_nodeatpoint(where)) { - LOG_TRACE("NAP WHERE :",vtos(where),"\n"); - LOG_TRACE("not NAP TO:",vtos(to),"\n"); - LOG_TRACE("NAP-NNAP:",ftos(vlen(to-where)),"\n\n"); - return 0; + LOG_DEBUG("NAP WHERE :",vtos(where)); + LOG_DEBUG("not NAP TO:",vtos(to)); + LOG_DEBUG("NAP-NNAP:",ftos(vlen(to-where))); + return false; } - if(doedge) + if(dodge) if (!tile_check(parent, where)) { - LOG_TRACE("tile_check fail\n"); + LOG_DEBUG("tile_check fail"); #if DEBUGPATHING pathlib_showsquare(where, 0 ,30); #endif - return 0; + return false; } @@ -213,14 +210,11 @@ float pathlib_makenode_adaptive(entity parent,vector start, vector to, vector go else if(best_open_node.pathlib_node_f > node.pathlib_node_f) best_open_node = node; - return 1; + return true; } entity pathlib_getbestopen() { - entity node; - entity bestnode; - if(best_open_node) { ++pathlib_bestcash_hits; @@ -229,34 +223,28 @@ entity pathlib_getbestopen() return best_open_node; } - node = findchainentity(owner,openlist); - if(!node) - return world; - - bestnode = node; - while(node) + entity bestnode = NULL; + FOREACH_ENTITY_ENT(owner, openlist, { - ++pathlib_bestopen_seached; - if(node.pathlib_node_f < bestnode.pathlib_node_f) - bestnode = node; + ++pathlib_bestopen_searched; - node = node.chain; - } + if(!bestnode || it.pathlib_node_f < bestnode.pathlib_node_f) + bestnode = it; + }); return bestnode; } void pathlib_close_node(entity node,vector goal) { - if(node.owner == closedlist) { - LOG_TRACE("Pathlib: Tried to close a closed node!\n"); + LOG_TRACE("Pathlib: Tried to close a closed node!"); return; } if(node == best_open_node) - best_open_node = world; + best_open_node = NULL; ++pathlib_closed_cnt; --pathlib_open_cnt; @@ -278,93 +266,76 @@ void pathlib_close_node(entity node,vector goal) void pathlib_cleanup() { - best_open_node = world; + best_open_node = NULL; //return; - entity node; - - node = findfloat(world,is_path_node, true); - while(node) + IL_EACH(g_pathlib_nodes, it.is_path_node, { - /* - node.owner = openlist; - node.pathlib_node_g = 0; - node.pathlib_node_h = 0; - node.pathlib_node_f = 0; - node.path_prev = world; - */ - - dumpnode(node); - node = findfloat(node,is_path_node, true); - } + dumpnode(it); + }); + + IL_CLEAR(g_pathlib_nodes); if(openlist) - remove(openlist); + delete(openlist); if(closedlist) - remove(closedlist); - - openlist = world; - closedlist = world; + delete(closedlist); + openlist = NULL; + closedlist = NULL; } -float Cosine_Interpolate(float a, float b, float x) +float Cosine_Interpolate(float a, float b, float c) { - float ft,f; + float ft = c * 3.1415927; + float f = (1 - cos(ft)) * 0.5; - ft = x * 3.1415927; - f = (1 - cos(ft)) * 0.5; - - return a*(1-f) + b*f; + return a*(1-f) + b*f; } -float buildpath_nodefilter_directional(vector n,vector c,vector p) +bool buildpath_nodefilter_directional(vector n,vector c,vector p) { - vector d1,d2; - - d2 = normalize(p - c); - d1 = normalize(c - n); + vector d2 = normalize(p - c); + vector d1 = normalize(c - n); - if(vlen(d1-d2) < 0.25) + if(vdist(d1 - d2, <, 0.25)) { //mark_error(c,30); - return 1; + return true; } //mark_info(c,30); - return 0; + return false; } -float buildpath_nodefilter_moveskip(entity this, vector n,vector c,vector p) +bool buildpath_nodefilter_moveskip(entity this, vector n,vector c,vector p) { pathlib_walknode(this, p, n, 1); if(pathlib_movenode_goodnode) - return 1; + return true; - return 0; + return false; } -float buildpath_nodefilter_none(vector n,vector c,vector p) +bool buildpath_nodefilter_none(vector n,vector c,vector p) { - return 0; + return false; } entity path_build(entity next, vector where, entity prev, entity start) { - entity path; - if(prev && next) if(buildpath_nodefilter) if(buildpath_nodefilter(next.origin,where,prev.origin)) return next; - path = spawn(); + entity path = spawn(); path.owner = start; path.path_next = next; - setorigin(path,where); + setorigin(path, where); if(!next) path.classname = "path_end"; @@ -379,12 +350,10 @@ entity path_build(entity next, vector where, entity prev, entity start) return path; } -entity pathlib_astar(vector from,vector to) -{SELFPARAM(); - entity path, start, end, open, n, ln; - float ptime, ftime, ctime; - - ptime = gettime(GETTIME_REALTIME); +entity pathlib_astar(entity this, vector from, vector to) +{ + entity open; + float ptime = gettime(GETTIME_REALTIME); pathlib_starttime = ptime; pathlib_cleanup(); @@ -432,7 +401,7 @@ entity pathlib_astar(vector from,vector to) pathlib_made_cnt = 0; pathlib_merge_cnt = 0; pathlib_searched_cnt = 0; - pathlib_bestopen_seached = 0; + pathlib_bestopen_searched = 0; pathlib_bestcash_hits = 0; pathlib_bestcash_saved = 0; @@ -442,8 +411,8 @@ entity pathlib_astar(vector from,vector to) pathlib_movecost_waterfactor = 25000000; pathlib_foundgoal = 0; - movenode_boxmax = self.maxs * 1.1; - movenode_boxmin = self.mins * 1.1; + movenode_boxmax = this.maxs * 1.1; + movenode_boxmin = this.mins * 1.1; movenode_stepsize = pathlib_gridsize * 0.25; @@ -461,22 +430,22 @@ entity pathlib_astar(vector from,vector to) from.x = fsnap(from.x, pathlib_gridsize); from.y = fsnap(from.y, pathlib_gridsize); - //from_z += 32; + //from.z += 32; to.x = fsnap(to.x, pathlib_gridsize); to.y = fsnap(to.y, pathlib_gridsize); - //to_z += 32; + //to.z += 32; - LOG_TRACE("AStar init\n"); - path = pathlib_mknode(from, world); + LOG_DEBUG("AStar init"); + entity path = pathlib_mknode(from, NULL); pathlib_close_node(path, to); if(pathlib_foundgoal) { - LOG_TRACE("AStar: Goal found on first node!\n"); + LOG_DEBUG("AStar: Goal found on first node!"); open = new(path_end); open.owner = open; - setorigin(open,path.origin); + setorigin(open, path.origin); pathlib_cleanup(); @@ -485,14 +454,14 @@ entity pathlib_astar(vector from,vector to) if(pathlib_expandnode(path, from, to) <= 0) { - LOG_TRACE("AStar path fail.\n"); + LOG_TRACE("AStar path fail."); pathlib_cleanup(); - return world; + return NULL; } best_open_node = pathlib_getbestopen(); - n = best_open_node; + entity n = best_open_node; pathlib_close_node(best_open_node, to); if(inwater(n.origin)) pathlib_expandnode_box(n, from, to); @@ -503,14 +472,14 @@ entity pathlib_astar(vector from,vector to) { if((gettime(GETTIME_REALTIME) - pathlib_starttime) > pathlib_maxtime) { - LOG_TRACE("Path took to long to compute!\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("Path took too long to compute!"); + LOG_TRACE("Nodes - created: ", ftos(pathlib_made_cnt)); + LOG_TRACE("Nodes - open: ", ftos(pathlib_open_cnt)); + LOG_TRACE("Nodes - merged: ", ftos(pathlib_merge_cnt)); + LOG_TRACE("Nodes - closed: ", ftos(pathlib_closed_cnt)); pathlib_cleanup(); - return world; + return NULL; } best_open_node = pathlib_getbestopen(); @@ -524,13 +493,13 @@ entity pathlib_astar(vector from,vector to) if(pathlib_foundgoal) { - LOG_TRACE("Target found. Rebuilding and filtering path...\n"); - ftime = gettime(GETTIME_REALTIME); + LOG_DEBUG("Target found. Rebuilding and filtering path..."); + float ftime = gettime(GETTIME_REALTIME); ptime = ftime - ptime; - start = path_build(world,path.origin,world,world); - end = path_build(world,goal_node.origin,world,start); - ln = end; + entity start = path_build(NULL,path.origin,NULL,NULL); + entity end = path_build(NULL,goal_node.origin,NULL,start); + entity ln = end; open = goal_node; for(open = goal_node; open.path_prev != path; open = open.path_prev) @@ -543,7 +512,7 @@ entity pathlib_astar(vector from,vector to) n.path_prev = start; ftime = gettime(GETTIME_REALTIME) - ftime; - ctime = gettime(GETTIME_REALTIME); + float ctime = gettime(GETTIME_REALTIME); pathlib_cleanup(); ctime = gettime(GETTIME_REALTIME) - ctime; @@ -551,28 +520,28 @@ entity pathlib_astar(vector from,vector to) #if DEBUGPATHING pathlib_showpath2(start); - 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"); - 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.\n"); + LOG_TRACE("Time used - pathfinding: ", ftos(ptime)); + LOG_TRACE("Time used - rebuild & filter: ", ftos(ftime)); + LOG_TRACE("Time used - cleanup: ", ftos(ctime)); + LOG_TRACE("Time used - total: ", ftos(ptime + ftime + ctime)); + LOG_TRACE("Time used - # frames: ", ftos(ceil((ptime + ftime + ctime) / sys_frametime))); + LOG_TRACE("Nodes - created: ", ftos(pathlib_made_cnt)); + LOG_TRACE("Nodes - open: ", ftos(pathlib_open_cnt)); + LOG_TRACE("Nodes - merged: ", ftos(pathlib_merge_cnt)); + LOG_TRACE("Nodes - closed: ", ftos(pathlib_closed_cnt)); + LOG_TRACE("Nodes - searched: ", ftos(pathlib_searched_cnt)); + LOG_TRACE("Nodes bestopen searched: ", ftos(pathlib_bestopen_searched)); + LOG_TRACE("Nodes bestcash - hits: ", ftos(pathlib_bestcash_hits)); + LOG_TRACE("Nodes bestcash - save: ", ftos(pathlib_bestcash_saved)); + LOG_TRACE("AStar done."); #endif return start; } } - LOG_TRACE("A* Faild to find a path! Try a smaller gridsize.\n"); + LOG_TRACE("A* Faild to find a path! Try a smaller gridsize."); pathlib_cleanup(); - return world; + return NULL; }