Add an intrusive list for bot waypoints
authorMario <mario@smbclan.net>
Thu, 28 Jul 2016 06:49:07 +0000 (16:49 +1000)
committerTimePath <andrew.hardaker1995@gmail.com>
Thu, 28 Jul 2016 10:39:56 +0000 (20:39 +1000)
.gitlab-ci.yml
qcsrc/server/bot/bot.qc
qcsrc/server/bot/havocbot/havocbot.qc
qcsrc/server/bot/navigation.qc
qcsrc/server/bot/navigation.qh
qcsrc/server/bot/waypoints.qc
qcsrc/server/cl_impulse.qc
qcsrc/server/defs.qh
qcsrc/server/pathlib/path_waypoint.qc

index 3785a36..ce9e150 100644 (file)
@@ -24,7 +24,7 @@ test_sv_game:
     - wget -O data/maps/g-23.waypoints.cache https://gitlab.com/xonotic/xonotic-maps.pk3dir/raw/master/maps/g-23.waypoints.cache
     - wget -O data/maps/g-23.waypoints.hardwired https://gitlab.com/xonotic/xonotic-maps.pk3dir/raw/master/maps/g-23.waypoints.hardwired
     - make
-    - EXPECT=7de811bad4617961bc8f4e53d9c428e4
+    - EXPECT=d17f62e08ff11b8b25116fa4a64f7e86
     - HASH=$(${ENGINE} -noconfig -nohome +exec serverbench.cfg
       | tee /dev/stderr
       | grep '^:'
index 8eb0b7f..df0f36a 100644 (file)
@@ -670,7 +670,7 @@ void bot_serverframe()
                else
                {
                        // TODO: Make this check cleaner
-                       FOREACH_ENTITY_CLASS("waypoint", time - it.nextthink > 10,
+                       IL_EACH(g_waypoints, time - it.nextthink > 10,
                        {
                                waypoint_save_links();
                                break;
index aca4b97..b22ded2 100644 (file)
@@ -46,7 +46,7 @@ void havocbot_ai(entity this)
                {
                        // Look for the closest waypoint out of water
                        entity newgoal = NULL;
-                       FOREACH_ENTITY_CLASS("waypoint", vdist(it.origin - this.origin, <=, 10000),
+                       IL_EACH(g_waypoints, vdist(it.origin - this.origin, <=, 10000),
                        {
                                if(it.origin.z < this.origin.z)
                                        continue;
@@ -486,7 +486,7 @@ void havocbot_movetogoal(entity this)
                        if(fabs(this.velocity.z)<50)
                        {
                                entity newgoal = NULL;
-                               FOREACH_ENTITY_CLASS("waypoint", vdist(it.origin - this.origin, <=, 1000),
+                               IL_EACH(g_waypoints, vdist(it.origin - this.origin, <=, 1000),
                                {
                                        traceline(this.origin + this.view_ofs, ((it.absmin + it.absmax) * 0.5), true, this);
 
index 21e5342..c9418e2 100644 (file)
@@ -373,25 +373,17 @@ float navigation_waypoint_will_link(vector v, vector org, entity ent, float walk
 // find the spawnfunc_waypoint near a dynamic goal such as a dropped weapon
 entity navigation_findnearestwaypoint_withdist_except(entity ent, float walkfromwp, float bestdist, entity except)
 {
-       entity waylist, w, best;
-       vector v, org, pm1, pm2;
-
-       pm1 = ent.origin + ent.mins;
-       pm2 = ent.origin + ent.maxs;
-       waylist = findchain(classname, "waypoint");
+       vector pm1 = ent.origin + ent.mins;
+       vector pm2 = ent.origin + ent.maxs;
 
        // do two scans, because box test is cheaper
-       w = waylist;
-       while (w)
+       IL_EACH(g_waypoints, it != ent && it != except,
        {
-               // if object is touching spawnfunc_waypoint
-               if(w != ent && w != except)
-                       if (boxesoverlap(pm1, pm2, w.absmin, w.absmax))
-                               return w;
-               w = w.chain;
-       }
+               if(boxesoverlap(pm1, pm2, it.absmin, it.absmax))
+                       return it;
+       });
 
-       org = ent.origin + 0.5 * (ent.mins + ent.maxs);
+       vector org = ent.origin + 0.5 * (ent.mins + ent.maxs);
        org.z = ent.origin.z + ent.mins.z - STAT(PL_MIN, NULL).z; // player height
        // TODO possibly make other code have the same support for bboxes
        if(ent.tag_entity)
@@ -399,34 +391,28 @@ entity navigation_findnearestwaypoint_withdist_except(entity ent, float walkfrom
        if (navigation_testtracewalk)
                te_plasmaburn(org);
 
-       best = NULL;
+       entity best = NULL;
+       vector v;
 
        // box check failed, try walk
-       w = waylist;
-       while (w)
+       IL_EACH(g_waypoints, it != ent,
        {
-               // if object can walk from spawnfunc_waypoint
-               if(w != ent)
+               if(it.wpisbox)
                {
-                       if (w.wpisbox)
-                       {
-                               vector wm1, wm2;
-                               wm1 = w.origin + w.mins;
-                               wm2 = w.origin + w.maxs;
-                               v.x = bound(wm1_x, org.x, wm2_x);
-                               v.y = bound(wm1_y, org.y, wm2_y);
-                               v.z = bound(wm1_z, org.z, wm2_z);
-                       }
-                       else
-                               v = w.origin;
-                       if(navigation_waypoint_will_link(v, org, ent, walkfromwp, bestdist))
-                       {
-                               bestdist = vlen(v - org);
-                               best = w;
-                       }
+                       vector wm1 = it.origin + it.mins;
+                       vector wm2 = it.origin + it.maxs;
+                       v.x = bound(wm1_x, org.x, wm2_x);
+                       v.y = bound(wm1_y, org.y, wm2_y);
+                       v.z = bound(wm1_z, org.z, wm2_z);
                }
-               w = w.chain;
-       }
+               else
+                       v = it.origin;
+               if(navigation_waypoint_will_link(v, org, ent, walkfromwp, bestdist))
+               {
+                       bestdist = vlen(v - org);
+                       best = it;
+               }
+       });
        return best;
 }
 entity navigation_findnearestwaypoint(entity ent, float walkfromwp)
@@ -442,46 +428,39 @@ entity navigation_findnearestwaypoint(entity ent, float walkfromwp)
 }
 
 // finds the waypoints near the bot initiating a navigation query
-float navigation_markroutes_nearestwaypoints(entity this, entity waylist, float maxdist)
+float navigation_markroutes_nearestwaypoints(entity this, float maxdist)
 {
-       entity head;
-       vector v, m1, m2, diff;
-       float c;
+       vector v, m1, m2;
 //     navigation_testtracewalk = true;
-       c = 0;
-       head = waylist;
-       while (head)
+       int c = 0;
+       IL_EACH(g_waypoints, !it.wpconsidered,
        {
-               if (!head.wpconsidered)
+               if (it.wpisbox)
                {
-                       if (head.wpisbox)
+                       m1 = it.origin + it.mins;
+                       m2 = it.origin + it.maxs;
+                       v = this.origin;
+                       v.x = bound(m1_x, v.x, m2_x);
+                       v.y = bound(m1_y, v.y, m2_y);
+                       v.z = bound(m1_z, v.z, m2_z);
+               }
+               else
+                       v = it.origin;
+               vector diff = v - this.origin;
+               diff.z = max(0, diff.z);
+               if(vdist(diff, <, maxdist))
+               {
+                       it.wpconsidered = true;
+                       if (tracewalk(this, this.origin, this.mins, this.maxs, v, bot_navigation_movemode))
                        {
-                               m1 = head.origin + head.mins;
-                               m2 = head.origin + head.maxs;
-                               v = this.origin;
-                               v.x = bound(m1_x, v.x, m2_x);
-                               v.y = bound(m1_y, v.y, m2_y);
-                               v.z = bound(m1_z, v.z, m2_z);
-                       }
-                       else
-                               v = head.origin;
-                       diff = v - this.origin;
-                       diff.z = max(0, diff.z);
-                       if(vdist(diff, <, maxdist))
-                       {
-                               head.wpconsidered = true;
-                               if (tracewalk(this, this.origin, this.mins, this.maxs, v, bot_navigation_movemode))
-                               {
-                                       head.wpnearestpoint = v;
-                                       head.wpcost = vlen(v - this.origin) + head.dmg;
-                                       head.wpfire = 1;
-                                       head.enemy = NULL;
-                                       c = c + 1;
-                               }
+                               it.wpnearestpoint = v;
+                               it.wpcost = vlen(v - this.origin) + it.dmg;
+                               it.wpfire = 1;
+                               it.enemy = NULL;
+                               c = c + 1;
                        }
                }
-               head = head.chain;
-       }
+       });
        //navigation_testtracewalk = false;
        return c;
 }
@@ -515,19 +494,17 @@ void navigation_markroutes_checkwaypoint(entity w, entity wp, float cost2, vecto
 // queries the entire spawnfunc_waypoint network for pathes leading away from the bot
 void navigation_markroutes(entity this, entity fixed_source_waypoint)
 {
-       entity w, wp, waylist;
-       float searching, cost, cost2;
+       float cost, cost2;
        vector p;
-       w = waylist = findchain(classname, "waypoint");
-       while (w)
+
+       IL_EACH(g_waypoints, true,
        {
-               w.wpconsidered = false;
-               w.wpnearestpoint = '0 0 0';
-               w.wpcost = 10000000;
-               w.wpfire = 0;
-               w.enemy = NULL;
-               w = w.chain;
-       }
+               it.wpconsidered = false;
+               it.wpnearestpoint = '0 0 0';
+               it.wpcost = 10000000;
+               it.wpfire = 0;
+               it.enemy = NULL;
+       });
 
        if(fixed_source_waypoint)
        {
@@ -541,7 +518,7 @@ void navigation_markroutes(entity this, entity fixed_source_waypoint)
        {
                // try a short range search for the nearest waypoints, and expand the search repeatedly if none are found
                // as this search is expensive we will use lower values if the bot is on the air
-               float i, increment, maxdistance;
+               float increment, maxdistance;
                if(IS_ONGROUND(this))
                {
                        increment = 750;
@@ -553,77 +530,70 @@ void navigation_markroutes(entity this, entity fixed_source_waypoint)
                        maxdistance = 1500;
                }
 
-               for(i=increment;!navigation_markroutes_nearestwaypoints(this, waylist, i)&&i<maxdistance;i+=increment);
+               for(int j = increment; !navigation_markroutes_nearestwaypoints(this, j) && j < maxdistance; j += increment);
        }
 
-       searching = true;
+       bool searching = true;
        while (searching)
        {
                searching = false;
-               w = waylist;
-               while (w)
+               IL_EACH(g_waypoints, it.wpfire,
                {
-                       if (w.wpfire)
-                       {
-                               searching = true;
-                               w.wpfire = 0;
-                               cost = w.wpcost;
-                               p = w.wpnearestpoint;
-                               wp = w.wp00;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp00mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp01;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp01mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp02;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp02mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp03;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp03mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp04;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp04mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp05;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp05mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp06;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp06mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp07;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp07mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp08;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp08mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp09;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp09mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp10;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp10mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp11;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp11mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp12;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp12mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp13;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp13mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp14;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp14mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp15;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp15mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp16;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp16mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp17;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp17mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp18;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp18mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp19;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp19mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp20;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp20mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp21;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp21mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp22;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp22mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp23;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp23mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp24;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp24mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp25;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp25mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp26;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp26mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp27;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp27mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp28;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp28mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp29;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp29mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp30;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp30mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               wp = w.wp31;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp31mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
-                       }
-                       w = w.chain;
-               }
+                       searching = true;
+                       it.wpfire = 0;
+                       cost = it.wpcost;
+                       p = it.wpnearestpoint;
+                       entity wp;
+                       wp = it.wp00;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp00mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp01;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp01mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp02;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp02mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp03;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp03mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp04;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp04mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp05;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp05mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp06;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp06mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp07;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp07mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp08;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp08mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp09;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp09mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp10;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp10mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp11;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp11mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp12;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp12mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp13;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp13mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp14;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp14mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp15;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp15mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp16;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp16mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp17;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp17mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp18;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp18mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp19;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp19mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp20;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp20mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp21;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp21mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp22;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp22mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp23;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp23mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp24;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp24mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp25;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp25mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp26;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp26mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp27;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp27mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp28;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp28mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp29;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp29mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp30;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp30mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       wp = it.wp31;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp31mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
+                       }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
+               });
        }
 }
 
 // queries the entire spawnfunc_waypoint network for pathes leading to the bot
 void navigation_markroutes_inverted(entity fixed_source_waypoint)
 {
-       entity w, wp, waylist;
-       float searching, cost, cost2;
+       float cost, cost2;
        vector p;
-       w = waylist = findchain(classname, "waypoint"); // TODO
-       while (w)
+       IL_EACH(g_waypoints, true,
        {
-               w.wpconsidered = false;
-               w.wpnearestpoint = '0 0 0';
-               w.wpcost = 10000000;
-               w.wpfire = 0;
-               w.enemy = NULL;
-               w = w.chain;
-       }
+               it.wpconsidered = false;
+               it.wpnearestpoint = '0 0 0';
+               it.wpcost = 10000000;
+               it.wpfire = 0;
+               it.enemy = NULL;
+       });
 
        if(fixed_source_waypoint)
        {
@@ -638,36 +608,32 @@ void navigation_markroutes_inverted(entity fixed_source_waypoint)
                error("need to start with a waypoint\n");
        }
 
-       searching = true;
+       bool searching = true;
        while (searching)
        {
                searching = false;
-               w = waylist;
-               while (w)
+               IL_EACH(g_waypoints, it.wpfire,
                {
-                       if (w.wpfire)
+                       searching = true;
+                       it.wpfire = 0;
+                       cost = it.wpcost; // cost to walk from it to home
+                       p = it.wpnearestpoint;
+                       entity wp = it;
+                       IL_EACH(g_waypoints, true,
                        {
-                               searching = true;
-                               w.wpfire = 0;
-                               cost = w.wpcost; // cost to walk from w to home
-                               p = w.wpnearestpoint;
-                               for(wp = waylist; wp; wp = wp.chain)
-                               {
-                                       if(w != wp.wp00) if(w != wp.wp01) if(w != wp.wp02) if(w != wp.wp03)
-                                       if(w != wp.wp04) if(w != wp.wp05) if(w != wp.wp06) if(w != wp.wp07)
-                                       if(w != wp.wp08) if(w != wp.wp09) if(w != wp.wp10) if(w != wp.wp11)
-                                       if(w != wp.wp12) if(w != wp.wp13) if(w != wp.wp14) if(w != wp.wp15)
-                                       if(w != wp.wp16) if(w != wp.wp17) if(w != wp.wp18) if(w != wp.wp19)
-                                       if(w != wp.wp20) if(w != wp.wp21) if(w != wp.wp22) if(w != wp.wp23)
-                                       if(w != wp.wp24) if(w != wp.wp25) if(w != wp.wp26) if(w != wp.wp27)
-                                       if(w != wp.wp28) if(w != wp.wp29) if(w != wp.wp30) if(w != wp.wp31)
-                                               continue;
-                                       cost2 = cost + wp.dmg;
-                                       navigation_markroutes_checkwaypoint(w, wp, cost2, p);
-                               }
-                       }
-                       w = w.chain;
-               }
+                               if(wp != it.wp00) if(wp != it.wp01) if(wp != it.wp02) if(wp != it.wp03)
+                               if(wp != it.wp04) if(wp != it.wp05) if(wp != it.wp06) if(wp != it.wp07)
+                               if(wp != it.wp08) if(wp != it.wp09) if(wp != it.wp10) if(wp != it.wp11)
+                               if(wp != it.wp12) if(wp != it.wp13) if(wp != it.wp14) if(wp != it.wp15)
+                               if(wp != it.wp16) if(wp != it.wp17) if(wp != it.wp18) if(wp != it.wp19)
+                               if(wp != it.wp20) if(wp != it.wp21) if(wp != it.wp22) if(wp != it.wp23)
+                               if(wp != it.wp24) if(wp != it.wp25) if(wp != it.wp26) if(wp != it.wp27)
+                               if(wp != it.wp28) if(wp != it.wp29) if(wp != it.wp30) if(wp != it.wp31)
+                                       continue;
+                               cost2 = cost + it.dmg;
+                               navigation_markroutes_checkwaypoint(wp, it, cost2, p);
+                       });
+               });
        }
 }
 
@@ -1027,7 +993,7 @@ void botframe_updatedangerousobjects(float maxupdate)
        vector m1, m2, v, o;
        float c, d, danger;
        c = 0;
-       FOREACH_ENTITY_CLASS("waypoint", true,
+       IL_EACH(g_waypoints, true,
        {
                danger = 0;
                m1 = it.mins;
@@ -1112,27 +1078,18 @@ void navigation_unstuck(entity this)
                // build a new queue
                LOG_DEBUG(strcat(this.netname, " stuck, scanning reachable waypoints within ", ftos(search_radius)," qu\n"));
 
-               entity head, first;
-
-               first = NULL;
-               head = findradius(this.origin, search_radius);
+               entity first = NULL;
 
-               while(head)
+               FOREACH_ENTITY_RADIUS(this.origin, search_radius, it.classname == "waypoint" && !(it.wpflags & WAYPOINTFLAG_GENERATED),
                {
-                       if(head.classname=="waypoint")
-               //      if(!(head.wpflags & WAYPOINTFLAG_GENERATED))
-                       {
-                               if(bot_waypoint_queue_goal)
-                                       bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = head;
-                               else
-                                       first = head;
-
-                               bot_waypoint_queue_goal = head;
-                               bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = NULL;
-                       }
+                       if(bot_waypoint_queue_goal)
+                               bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = it;
+                       else
+                               first = it;
 
-                       head = head.chain;
-               }
+                       bot_waypoint_queue_goal = it;
+                       bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = NULL;
+               });
 
                if (first)
                        bot_waypoint_queue_goal = first;
index cf79306..ad01776 100644 (file)
@@ -56,7 +56,7 @@ void debuggoalstack(entity this);
 
 float tracewalk(entity e, vector start, vector m1, vector m2, vector end, float movemode);
 
-float navigation_markroutes_nearestwaypoints(entity this, entity waylist, float maxdist);
+float navigation_markroutes_nearestwaypoints(entity this, float maxdist);
 float navigation_routetogoal(entity this, entity e, vector startposition);
 
 void navigation_clearroute(entity this);
index 1a9b478..586f2a8 100644 (file)
@@ -19,13 +19,14 @@ entity waypoint_spawn(vector m1, vector m2, float f)
 {
        if(!(f & WAYPOINTFLAG_PERSONAL))
        {
-               FOREACH_ENTITY_CLASS("waypoint", boxesoverlap(m1, m2, it.absmin, it.absmax),
+               IL_EACH(g_waypoints, boxesoverlap(m1, m2, it.absmin, it.absmax),
                {
                        return it;
                });
        }
 
        entity w = new(waypoint);
+       IL_PUSH(g_waypoints, w);
        w.dphitcontentsmask = DPCONTENTS_SOLID | DPCONTENTS_BODY | DPCONTENTS_PLAYERCLIP | DPCONTENTS_BOTCLIP;
        w.wpflags = f;
        w.solid = SOLID_TRIGGER;
@@ -170,7 +171,7 @@ void waypoint_think(entity this)
        //dprint("waypoint_think wpisbox = ", ftos(this.wpisbox), "\n");
        sm1 = this.origin + this.mins;
        sm2 = this.origin + this.maxs;
-       FOREACH_ENTITY_CLASS("waypoint", true,
+       IL_EACH(g_waypoints, true,
        {
                if (boxesoverlap(this.absmin, this.absmax, it.absmin, it.absmax))
                {
@@ -292,6 +293,8 @@ void waypoint_schedulerelink(entity wp)
 // spawnfunc_waypoint map entity
 spawnfunc(waypoint)
 {
+       IL_PUSH(g_waypoints, this);
+
        setorigin(this, this.origin);
        // schedule a relink after other waypoints have had a chance to spawn
        waypoint_clearlinks(this);
@@ -341,7 +344,7 @@ void waypoint_remove(entity e)
 // empties the map of waypoints
 void waypoint_removeall()
 {
-       FOREACH_ENTITY_CLASS("waypoint", true,
+       IL_EACH(g_waypoints, true,
        {
                remove(it);
        });
@@ -352,7 +355,7 @@ void waypoint_removeall()
 void waypoint_schedulerelinkall()
 {
        relink_total = relink_walkculled = relink_pvsculled = relink_lengthculled = 0;
-       FOREACH_ENTITY_CLASS("waypoint", true,
+       IL_EACH(g_waypoints, true,
        {
                waypoint_schedulerelink(it);
        });
@@ -587,7 +590,7 @@ void waypoint_save_links()
        }
 
        int c = 0;
-       FOREACH_ENTITY_CLASS("waypoint", true,
+       IL_EACH(g_waypoints, true,
        {
                for(int j = 0; j < 32; ++j)
                {
@@ -621,7 +624,7 @@ void waypoint_saveall()
        }
 
        int c = 0;
-       FOREACH_ENTITY_CLASS("waypoint", true,
+       IL_EACH(g_waypoints, true,
        {
                if(it.wpflags & WAYPOINTFLAG_GENERATED)
                        continue;
@@ -701,7 +704,7 @@ void waypoint_spawnforitem_force(entity e, vector org)
        org = waypoint_fixorigin(org);
 
        // don't spawn an item spawnfunc_waypoint if it already exists
-       FOREACH_ENTITY_CLASS("waypoint", true,
+       IL_EACH(g_waypoints, true,
        {
                if(it.wpisbox)
                {
@@ -781,19 +784,20 @@ entity waypoint_spawnpersonal(entity this, vector position)
 
 void botframe_showwaypointlinks()
 {
-       entity head, w;
        if (time < botframe_waypointeditorlightningtime)
                return;
        botframe_waypointeditorlightningtime = time + 0.5;
-       FOREACH_CLIENT(IS_PLAYER(it) && !it.isbot, LAMBDA(
+       FOREACH_CLIENT(IS_PLAYER(it) && !it.isbot,
+       {
                if(IS_ONGROUND(it) || it.waterlevel > WATERLEVEL_NONE)
                {
                        //navigation_testtracewalk = true;
-                       head = navigation_findnearestwaypoint(it, false);
+                       entity head = navigation_findnearestwaypoint(it, false);
                //      print("currently selected WP is ", etos(head), "\n");
                        //navigation_testtracewalk = false;
                        if (head)
                        {
+                               entity w;
                                w = head     ;if (w) te_lightning2(NULL, w.origin, it.origin);
                                w = head.wp00;if (w) te_lightning2(NULL, w.origin, head.origin);
                                w = head.wp01;if (w) te_lightning2(NULL, w.origin, head.origin);
@@ -829,7 +833,7 @@ void botframe_showwaypointlinks()
                                w = head.wp31;if (w) te_lightning2(NULL, w.origin, head.origin);
                        }
                }
-       ));
+       });
 }
 
 float botframe_autowaypoints_fixdown(vector v)
@@ -842,17 +846,11 @@ float botframe_autowaypoints_fixdown(vector v)
 
 float botframe_autowaypoints_createwp(vector v, entity p, .entity fld, float f)
 {
-       entity w;
-
-       w = find(NULL, classname, "waypoint");
-       while (w)
+       IL_EACH(g_waypoints, boxesoverlap(v - '32 32 32', v + '32 32 32', it.absmin, it.absmax),
        {
                // if a matching spawnfunc_waypoint already exists, don't add a duplicate
-               if (boxesoverlap(v - '32 32 32', v + '32 32 32', w.absmin, w.absmax))
-               //if (boxesoverlap(v - '4 4 4', v + '4 4 4', w.absmin, w.absmax))
-                       return 0;
-               w = find(w, classname, "waypoint");
-       }
+               return 0;
+       });
 
        waypoint_schedulerelink(p.(fld) = waypoint_spawn(v, v, f));
        return 1;
@@ -895,25 +893,18 @@ float botframe_autowaypoints_fix_from(entity p, float walkfromwp, entity wp, .en
                        maxdist = 2100;
                }
 
-               float bestdist;
-               bestdist = maxdist;
-               w = find(NULL, classname, "waypoint");
-               while (w)
+               float bestdist = maxdist;
+               IL_EACH(g_waypoints, it != wp && !(it.wpflags & WAYPOINTFLAG_NORELINK),
                {
-                       if(w != wp && !(w.wpflags & WAYPOINTFLAG_NORELINK))
+                       float d = vlen(wp.origin - it.origin) + vlen(it.origin - porg);
+                       if(d < bestdist)
+                       if(navigation_waypoint_will_link(wp.origin, it.origin, p, walkfromwp, 1050))
+                       if(navigation_waypoint_will_link(it.origin, porg, p, walkfromwp, 1050))
                        {
-                               float d;
-                               d = vlen(wp.origin - w.origin) + vlen(w.origin - porg);
-                               if(d < bestdist)
-                                       if(navigation_waypoint_will_link(wp.origin, w.origin, p, walkfromwp, 1050))
-                                               if(navigation_waypoint_will_link(w.origin, porg, p, walkfromwp, 1050))
-                                               {
-                                                       bestdist = d;
-                                                       p.(fld) = w;
-                                               }
+                               bestdist = d;
+                               p.(fld) = it;
                        }
-                       w = find(w, classname, "waypoint");
-               }
+               });
                if(bestdist < maxdist)
                {
                        LOG_INFO("update chain to new nearest WP ", etos(p.(fld)), "\n");
@@ -1019,84 +1010,80 @@ void botframe_autowaypoints_fix(entity p, float walkfromwp, .entity fld)
 
 void botframe_deleteuselesswaypoints()
 {
-       entity w, w1, w2;
-       float i, j, k;
-       for (w = NULL; (w = findfloat(w, bot_pickup, true)); )
+       FOREACH_ENTITY_FLOAT(bot_pickup, true,
        {
                // NOTE: this protects waypoints if they're the ONLY nearest
                // waypoint. That's the intention.
-               navigation_findnearestwaypoint(w, false);  // Walk TO item.
-               navigation_findnearestwaypoint(w, true);  // Walk FROM item.
-       }
-       for (w = NULL; (w = find(w, classname, "waypoint")); )
+               navigation_findnearestwaypoint(it, false);  // Walk TO item.
+               navigation_findnearestwaypoint(it, true);  // Walk FROM item.
+       });
+       IL_EACH(g_waypoints, true,
        {
-               w.wpflags |= WAYPOINTFLAG_DEAD_END;
-               w.wpflags &= ~WAYPOINTFLAG_USEFUL;
+               it.wpflags |= WAYPOINTFLAG_DEAD_END;
+               it.wpflags &= ~WAYPOINTFLAG_USEFUL;
                // WP is useful if:
-               if (w.wpflags & WAYPOINTFLAG_ITEM)
-                       w.wpflags |= WAYPOINTFLAG_USEFUL;
-               if (w.wpflags & WAYPOINTFLAG_TELEPORT)
-                       w.wpflags |= WAYPOINTFLAG_USEFUL;
-               if (w.wpflags & WAYPOINTFLAG_PROTECTED)
-                       w.wpflags |= WAYPOINTFLAG_USEFUL;
+               if (it.wpflags & WAYPOINTFLAG_ITEM)
+                       it.wpflags |= WAYPOINTFLAG_USEFUL;
+               if (it.wpflags & WAYPOINTFLAG_TELEPORT)
+                       it.wpflags |= WAYPOINTFLAG_USEFUL;
+               if (it.wpflags & WAYPOINTFLAG_PROTECTED)
+                       it.wpflags |= WAYPOINTFLAG_USEFUL;
                // b) WP is closest WP for an item/spawnpoint/other entity
                //    This has been done above by protecting these WPs.
-       }
+       });
        // c) There are w1, w, w2 so that w1 -> w, w -> w2 and not w1 -> w2.
-       for (w1 = NULL; (w1 = find(w1, classname, "waypoint")); )
+       IL_EACH(g_waypoints, !(it.wpflags & WAYPOINTFLAG_PERSONAL),
        {
-               if (w1.wpflags & WAYPOINTFLAG_PERSONAL)
-                       continue;
-               for (i = 0; i < 32; ++i)
+               for (int m = 0; m < 32; ++m)
                {
-                       w = waypoint_get_link(w1, i);
+                       entity w = waypoint_get_link(it, m);
                        if (!w)
                                break;
                        if (w.wpflags & WAYPOINTFLAG_PERSONAL)
                                continue;
                        if (w.wpflags & WAYPOINTFLAG_USEFUL)
                                continue;
-                       for (j = 0; j < 32; ++j)
+                       for (int j = 0; j < 32; ++j)
                        {
-                               w2 = waypoint_get_link(w, j);
+                               entity w2 = waypoint_get_link(w, j);
                                if (!w2)
                                        break;
-                               if (w1 == w2)
+                               if (it == w2)
                                        continue;
                                if (w2.wpflags & WAYPOINTFLAG_PERSONAL)
                                        continue;
-                               // If we got here, w1 != w2 exist with w1 -> w
+                               // If we got here, it != w2 exist with it -> w
                                // and w -> w2. That means the waypoint is not
                                // a dead end.
                                w.wpflags &= ~WAYPOINTFLAG_DEAD_END;
-                               for (k = 0; k < 32; ++k)
+                               for (int k = 0; k < 32; ++k)
                                {
-                                       if (waypoint_get_link(w1, k) == w2)
+                                       if (waypoint_get_link(it, k) == w2)
                                                continue;
                                        // IF WE GET HERE, w is proven useful
-                                       // to get from w1 to w2!
+                                       // to get from it to w2!
                                        w.wpflags |= WAYPOINTFLAG_USEFUL;
                                        goto next;
                                }
                        }
 LABEL(next)
                }
-       }
+       });
        // d) The waypoint is a dead end. Dead end waypoints must be kept as
        //     they are needed to complete routes while autowaypointing.
 
-       for (w = NULL; (w = find(w, classname, "waypoint")); )
+       IL_EACH(g_waypoints, !(it.wpflags & (WAYPOINTFLAG_USEFUL | WAYPOINTFLAG_DEAD_END)),
        {
-               if (!(w.wpflags & (WAYPOINTFLAG_USEFUL | WAYPOINTFLAG_DEAD_END)))
-               {
-                       LOG_INFOF("Removed a waypoint at %v. Try again for more!\n", w.origin);
-                       te_explosion(w.origin);
-                       waypoint_remove(w);
-                       break;
-               }
-       }
-       for (w = NULL; (w = find(w, classname, "waypoint")); )
-               w.wpflags &= ~(WAYPOINTFLAG_USEFUL | WAYPOINTFLAG_DEAD_END); // temp flag
+               LOG_INFOF("Removed a waypoint at %v. Try again for more!\n", it.origin);
+               te_explosion(it.origin);
+               waypoint_remove(it);
+               break;
+       });
+
+       IL_EACH(g_waypoints, true,
+       {
+               it.wpflags &= ~(WAYPOINTFLAG_USEFUL | WAYPOINTFLAG_DEAD_END); // temp flag
+       });
 }
 
 void botframe_autowaypoints()
index f3fedf5..5e276c4 100644 (file)
@@ -512,7 +512,7 @@ IMPULSE(navwaypoint_save)
 IMPULSE(navwaypoint_unreachable)
 {
        if (!autocvar_g_waypointeditor) return;
-       FOREACH_ENTITY_CLASS("waypoint", true,
+       IL_EACH(g_waypoints, true,
        {
                it.colormod = '0.5 0.5 0.5';
                it.effects &= ~(EF_NODEPTHTEST | EF_RED | EF_BLUE);
@@ -524,7 +524,7 @@ IMPULSE(navwaypoint_unreachable)
 
        j = 0;
        m = 0;
-       FOREACH_ENTITY_CLASS("waypoint", it.wpcost >= 10000000,
+       IL_EACH(g_waypoints, it.wpcost >= 10000000,
        {
                LOG_INFO("unreachable: ", etos(it), " ", vtos(it.origin), "\n");
                it.colormod_z = 8;
@@ -536,7 +536,7 @@ IMPULSE(navwaypoint_unreachable)
        navigation_markroutes_inverted(e2);
 
        j = 0;
-       FOREACH_ENTITY_CLASS("waypoint", it.wpcost >= 10000000,
+       IL_EACH(g_waypoints, it.wpcost >= 10000000,
        {
                LOG_INFO("cannot reach me: ", etos(it), " ", vtos(it.origin), "\n");
                it.colormod_x = 8;
index 30c9bb4..a1c180c 100644 (file)
@@ -446,3 +446,6 @@ const int MIF_GUIDED_CONFUSABLE = MIF_GUIDED_HEAT | MIF_GUIDED_AI;
 
 IntrusiveList g_monsters;
 STATIC_INIT(g_monsters) { g_monsters = IL_NEW(); }
+
+IntrusiveList g_waypoints;
+STATIC_INIT(g_waypoints) { g_waypoints = IL_NEW(); }
index 01a6e2c..a2aaf55 100644 (file)
@@ -162,8 +162,7 @@ entity pathlib_waypointpath(entity wp_from, entity wp_to, float callback)
     LOG_TRACE("pathlib_waypointpath init\n");
 
     // Initialize waypoint grid
-    // FIXME! presisted chain for better preformance
-    FOREACH_ENTITY_CLASS("waypoint", true,
+    IL_EACH(g_waypoints, true,
     {
         it.pathlib_list = NULL;
         it.pathlib_node_g = 0;