Pathlib code cleanup (tZork patch from the oldstuff repo)
authorterencehill <piuntn@gmail.com>
Thu, 30 Jul 2020 11:16:36 +0000 (13:16 +0200)
committerterencehill <piuntn@gmail.com>
Thu, 30 Jul 2020 11:16:36 +0000 (13:16 +0200)
qcsrc/server/pathlib/costs.qc
qcsrc/server/pathlib/expandnode.qc
qcsrc/server/pathlib/path_waypoint.qc
qcsrc/server/pathlib/pathlib.qh

index 1449e38..7dcaec8 100644 (file)
@@ -28,10 +28,10 @@ float pathlib_g_euclidean_water(entity parent,vector to, float static_cost)
 
 
 /**
-    Manhattan Menas we expect to move up,down left or right
-    No diagonal moves espected. (like moving bewteen city blocks)
+    Manhattan heuristic means we expect to move up, down left or right
+    No diagonal moves expected. (like moving between city blocks)
 **/
-float pathlib_h_manhattan(vector a,vector b)
+float pathlib_h_manhattan(vector a, vector b)
 {
     //h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))
 
@@ -43,33 +43,33 @@ float pathlib_h_manhattan(vector a,vector b)
 }
 
 /**
-    This heuristic consider both stright and disagonal moves
-    to have teh same cost.
+    This heuristic consider both straight and diagonal moves
+    to have the same cost.
 **/
-float pathlib_h_diagonal(vector a,vector b)
+float pathlib_h_diagonal(vector a, vector b)
 {
     //h(n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))
 
     float hx = fabs(a.x - b.x);
     float hy = fabs(a.y - b.y);
-    float h = pathlib_movecost * max(hx,hy);
+    float h = pathlib_movecost * max(hx, hy);
 
     return h;
 }
 
 /**
-    This heuristic only considers the stright line distance.
-    Will usualy mean a lower H then G meaning A* Will speand more
-    and run slower.
+    This heuristic only considers the straight line distance.
+    Usually means a lower H then G, resulting in A* spreading more
+    (and running slower).
 **/
-float pathlib_h_euclidean(vector a,vector b)
+float pathlib_h_euclidean(vector a, vector b)
 {
     return vlen(a - b);
 }
 
 /**
-    This heuristic consider both stright and disagonal moves,
-    But has a separate cost for diagonal moves.
+    This heuristic consider both straight and diagonal moves,
+    but has a separate cost for diagonal moves.
 **/
 float pathlib_h_diagonal2(vector a,vector b)
 {
@@ -92,10 +92,10 @@ float pathlib_h_diagonal2(vector a,vector b)
 }
 
 /**
-    This heuristic consider both stright and disagonal moves,
+    This heuristic consider both straight and diagonal moves,
     But has a separate cost for diagonal moves.
 **/
-float pathlib_h_diagonal2sdp(vector preprev,vector prev,vector point,vector end)
+float pathlib_h_diagonal2sdp(vector preprev, vector prev, vector point, vector end)
 {
     //h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
     //h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
@@ -113,13 +113,13 @@ float pathlib_h_diagonal2sdp(vector preprev,vector prev,vector point,vector end)
 
     vector d1 = normalize(preprev - point);
     vector d2 = normalize(prev    - point);
-    float m = vlen(d1-d2);
+    float m = vlen(d1 - d2);
 
     return h * m;
 }
 
 
-float pathlib_h_diagonal3(vector a,vector b)
+float pathlib_h_diagonal3(vector a, vector b)
 {
     float hx = fabs(a.x - b.x);
     float hy = fabs(a.y - b.y);
index b77736b..e3ab647 100644 (file)
@@ -2,6 +2,7 @@
 #include "pathlib.qh"
 #include "utility.qh"
 
+/*
 vector plib_points2[8];
 vector plib_points[8];
 float  plib_fvals[8];
@@ -73,13 +74,11 @@ float pathlib_expandnode_starf(entity node, vector start, vector goal)
             ++fc2;
         }
 
-        /*
-        nap = pathlib_nodeatpoint(plib_points[i]);
-        if(nap)
-        if not nap.owner == closedlist)
-        {
-        }
-        */
+        //nap = pathlib_nodeatpoint(plib_points[i]);
+        //if(nap)
+        //if not nap.owner == closedlist)
+        //{
+        //}
     }
 
     pathlib_makenode(node, start, bp, goal, pathlib_gridsize);
@@ -91,6 +90,7 @@ float pathlib_expandnode_starf(entity node, vector start, vector goal)
 
     return pathlib_open_cnt;
 }
+*/
 
 float pathlib_expandnode_star(entity node, vector start, vector goal)
 {
@@ -171,6 +171,7 @@ float pathlib_expandnode_star(entity node, vector start, vector goal)
     return pathlib_open_cnt;
 }
 
+/*
 float pathlib_expandnode_octagon(entity node, vector start, vector goal)
 {
     vector point;
@@ -203,12 +204,10 @@ float pathlib_expandnode_octagon(entity node, vector start, vector goal)
     point = where + f + r;
     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 
-
     // Forward-left
     point = where + f - r;
     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 
-
     // Back-right
     point = where - f + r;
     pathlib_makenode(node, start, point, goal, pathlib_movecost);
@@ -219,6 +218,7 @@ float pathlib_expandnode_octagon(entity node, vector start, vector goal)
 
     return pathlib_open_cnt;
 }
+*/
 
 float pathlib_expandnode_box(entity node, vector start, vector goal)
 {
index 906ebc7..0f1c4e8 100644 (file)
@@ -76,38 +76,38 @@ float pathlib_wpp_openncb(entity wp, entity child, float cost)
 
 float pathlib_wpp_expand(entity wp)
 {
-    if(wp.wp00) pathlib_wpp_open(wp,wp.wp00,wp.wp00mincost); else return 0;
-    if(wp.wp01) pathlib_wpp_open(wp,wp.wp01,wp.wp01mincost); else return 1;
-    if(wp.wp02) pathlib_wpp_open(wp,wp.wp02,wp.wp02mincost); else return 2;
-    if(wp.wp03) pathlib_wpp_open(wp,wp.wp03,wp.wp03mincost); else return 3;
-    if(wp.wp04) pathlib_wpp_open(wp,wp.wp04,wp.wp04mincost); else return 4;
-    if(wp.wp05) pathlib_wpp_open(wp,wp.wp05,wp.wp05mincost); else return 5;
-    if(wp.wp06) pathlib_wpp_open(wp,wp.wp06,wp.wp06mincost); else return 6;
-    if(wp.wp07) pathlib_wpp_open(wp,wp.wp07,wp.wp07mincost); else return 7;
-    if(wp.wp08) pathlib_wpp_open(wp,wp.wp08,wp.wp08mincost); else return 8;
-    if(wp.wp09) pathlib_wpp_open(wp,wp.wp09,wp.wp09mincost); else return 9;
-    if(wp.wp10) pathlib_wpp_open(wp,wp.wp10,wp.wp10mincost); else return 10;
-    if(wp.wp11) pathlib_wpp_open(wp,wp.wp11,wp.wp11mincost); else return 11;
-    if(wp.wp12) pathlib_wpp_open(wp,wp.wp12,wp.wp12mincost); else return 12;
-    if(wp.wp13) pathlib_wpp_open(wp,wp.wp13,wp.wp13mincost); else return 13;
-    if(wp.wp14) pathlib_wpp_open(wp,wp.wp14,wp.wp14mincost); else return 14;
-    if(wp.wp15) pathlib_wpp_open(wp,wp.wp15,wp.wp15mincost); else return 15;
-    if(wp.wp16) pathlib_wpp_open(wp,wp.wp16,wp.wp16mincost); else return 16;
-    if(wp.wp17) pathlib_wpp_open(wp,wp.wp17,wp.wp17mincost); else return 17;
-    if(wp.wp18) pathlib_wpp_open(wp,wp.wp18,wp.wp18mincost); else return 18;
-    if(wp.wp19) pathlib_wpp_open(wp,wp.wp19,wp.wp19mincost); else return 19;
-    if(wp.wp20) pathlib_wpp_open(wp,wp.wp20,wp.wp20mincost); else return 20;
-    if(wp.wp21) pathlib_wpp_open(wp,wp.wp21,wp.wp21mincost); else return 21;
-    if(wp.wp22) pathlib_wpp_open(wp,wp.wp22,wp.wp22mincost); else return 22;
-    if(wp.wp23) pathlib_wpp_open(wp,wp.wp23,wp.wp23mincost); else return 23;
-    if(wp.wp24) pathlib_wpp_open(wp,wp.wp24,wp.wp24mincost); else return 24;
-    if(wp.wp25) pathlib_wpp_open(wp,wp.wp25,wp.wp25mincost); else return 25;
-    if(wp.wp26) pathlib_wpp_open(wp,wp.wp26,wp.wp26mincost); else return 26;
-    if(wp.wp27) pathlib_wpp_open(wp,wp.wp27,wp.wp27mincost); else return 27;
-    if(wp.wp28) pathlib_wpp_open(wp,wp.wp28,wp.wp28mincost); else return 28;
-    if(wp.wp29) pathlib_wpp_open(wp,wp.wp29,wp.wp29mincost); else return 29;
-    if(wp.wp30) pathlib_wpp_open(wp,wp.wp30,wp.wp30mincost); else return 30;
-    if(wp.wp31) pathlib_wpp_open(wp,wp.wp31,wp.wp31mincost); else return 31;
+    if(wp.wp00) pathlib_wpp_open(wp,wp.wp00, wp.wp00mincost); else return 0;
+    if(wp.wp01) pathlib_wpp_open(wp,wp.wp01, wp.wp01mincost); else return 1;
+    if(wp.wp02) pathlib_wpp_open(wp,wp.wp02, wp.wp02mincost); else return 2;
+    if(wp.wp03) pathlib_wpp_open(wp,wp.wp03, wp.wp03mincost); else return 3;
+    if(wp.wp04) pathlib_wpp_open(wp,wp.wp04, wp.wp04mincost); else return 4;
+    if(wp.wp05) pathlib_wpp_open(wp,wp.wp05, wp.wp05mincost); else return 5;
+    if(wp.wp06) pathlib_wpp_open(wp,wp.wp06, wp.wp06mincost); else return 6;
+    if(wp.wp07) pathlib_wpp_open(wp,wp.wp07, wp.wp07mincost); else return 7;
+    if(wp.wp08) pathlib_wpp_open(wp,wp.wp08, wp.wp08mincost); else return 8;
+    if(wp.wp09) pathlib_wpp_open(wp,wp.wp09, wp.wp09mincost); else return 9;
+    if(wp.wp10) pathlib_wpp_open(wp,wp.wp10, wp.wp10mincost); else return 10;
+    if(wp.wp11) pathlib_wpp_open(wp,wp.wp11, wp.wp11mincost); else return 11;
+    if(wp.wp12) pathlib_wpp_open(wp,wp.wp12, wp.wp12mincost); else return 12;
+    if(wp.wp13) pathlib_wpp_open(wp,wp.wp13, wp.wp13mincost); else return 13;
+    if(wp.wp14) pathlib_wpp_open(wp,wp.wp14, wp.wp14mincost); else return 14;
+    if(wp.wp15) pathlib_wpp_open(wp,wp.wp15, wp.wp15mincost); else return 15;
+    if(wp.wp16) pathlib_wpp_open(wp,wp.wp16, wp.wp16mincost); else return 16;
+    if(wp.wp17) pathlib_wpp_open(wp,wp.wp17, wp.wp17mincost); else return 17;
+    if(wp.wp18) pathlib_wpp_open(wp,wp.wp18, wp.wp18mincost); else return 18;
+    if(wp.wp19) pathlib_wpp_open(wp,wp.wp19, wp.wp19mincost); else return 19;
+    if(wp.wp20) pathlib_wpp_open(wp,wp.wp20, wp.wp20mincost); else return 20;
+    if(wp.wp21) pathlib_wpp_open(wp,wp.wp21, wp.wp21mincost); else return 21;
+    if(wp.wp22) pathlib_wpp_open(wp,wp.wp22, wp.wp22mincost); else return 22;
+    if(wp.wp23) pathlib_wpp_open(wp,wp.wp23, wp.wp23mincost); else return 23;
+    if(wp.wp24) pathlib_wpp_open(wp,wp.wp24, wp.wp24mincost); else return 24;
+    if(wp.wp25) pathlib_wpp_open(wp,wp.wp25, wp.wp25mincost); else return 25;
+    if(wp.wp26) pathlib_wpp_open(wp,wp.wp26, wp.wp26mincost); else return 26;
+    if(wp.wp27) pathlib_wpp_open(wp,wp.wp27, wp.wp27mincost); else return 27;
+    if(wp.wp28) pathlib_wpp_open(wp,wp.wp28, wp.wp28mincost); else return 28;
+    if(wp.wp29) pathlib_wpp_open(wp,wp.wp29, wp.wp29mincost); else return 29;
+    if(wp.wp30) pathlib_wpp_open(wp,wp.wp30, wp.wp30mincost); else return 30;
+    if(wp.wp31) pathlib_wpp_open(wp,wp.wp31, wp.wp31mincost); else return 31;
 
     return 32;
 }
@@ -146,7 +146,7 @@ entity pathlib_waypointpath(entity wp_from, entity wp_to, float callback)
        else
                pathlib_wpp_open = pathlib_wpp_openncb;
 
-       pathlib_heuristic = pathlib_h_none;
+       pathlib_heuristic = pathlib_h_none; // We run Dijkstra, A* does not make sense with variable distanced nodes.
 
     if (!openlist)
         openlist       = spawn();
index d1bafe3..da07e93 100644 (file)
@@ -80,9 +80,10 @@ vector     pathlib_flynode(entity this, vector start, vector end, float doedge);
 vector     pathlib_walknode(entity this, vector start, vector end, float doedge);
 var vector pathlib_movenode(entity this, vector start, vector end, float doedge);
 
+//float      pathlib_expandnode_starf(entity node, vector start, vector goal);
 float      pathlib_expandnode_star(entity node, vector start, vector goal);
 float      pathlib_expandnode_box(entity node, vector start, vector goal);
-float      pathlib_expandnode_octagon(entity node, vector start, vector goal);
+//float      pathlib_expandnode_octagon(entity node, vector start, vector goal);
 var float  pathlib_expandnode(entity node, vector start, vector goal);
 
 float      pathlib_g_static(entity parent, vector to, float static_cost);