From 1d4173cf0f1224350ea7eaf95f4d874c1271ab27 Mon Sep 17 00:00:00 2001 From: Mario Date: Thu, 28 Jul 2016 16:49:07 +1000 Subject: [PATCH] Add an intrusive list for bot waypoints --- .gitlab-ci.yml | 2 +- qcsrc/server/bot/bot.qc | 2 +- qcsrc/server/bot/havocbot/havocbot.qc | 4 +- qcsrc/server/bot/navigation.qc | 325 +++++++++++--------------- qcsrc/server/bot/navigation.qh | 2 +- qcsrc/server/bot/waypoints.qc | 139 +++++------ qcsrc/server/cl_impulse.qc | 6 +- qcsrc/server/defs.qh | 3 + qcsrc/server/pathlib/path_waypoint.qc | 3 +- 9 files changed, 216 insertions(+), 270 deletions(-) diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index 3785a3618d..ce9e150565 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -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 '^:' diff --git a/qcsrc/server/bot/bot.qc b/qcsrc/server/bot/bot.qc index 8eb0b7f1aa..df0f36ab1a 100644 --- a/qcsrc/server/bot/bot.qc +++ b/qcsrc/server/bot/bot.qc @@ -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; diff --git a/qcsrc/server/bot/havocbot/havocbot.qc b/qcsrc/server/bot/havocbot/havocbot.qc index aca4b9756a..b22ded20fb 100644 --- a/qcsrc/server/bot/havocbot/havocbot.qc +++ b/qcsrc/server/bot/havocbot/havocbot.qc @@ -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); diff --git a/qcsrc/server/bot/navigation.qc b/qcsrc/server/bot/navigation.qc index 21e5342c03..c9418e2e31 100644 --- a/qcsrc/server/bot/navigation.qc +++ b/qcsrc/server/bot/navigation.qc @@ -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 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; diff --git a/qcsrc/server/bot/navigation.qh b/qcsrc/server/bot/navigation.qh index cf793068bf..ad01776652 100644 --- a/qcsrc/server/bot/navigation.qh +++ b/qcsrc/server/bot/navigation.qh @@ -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); diff --git a/qcsrc/server/bot/waypoints.qc b/qcsrc/server/bot/waypoints.qc index 1a9b4784f6..586f2a8c04 100644 --- a/qcsrc/server/bot/waypoints.qc +++ b/qcsrc/server/bot/waypoints.qc @@ -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() diff --git a/qcsrc/server/cl_impulse.qc b/qcsrc/server/cl_impulse.qc index f3fedf5f10..5e276c4a3a 100644 --- a/qcsrc/server/cl_impulse.qc +++ b/qcsrc/server/cl_impulse.qc @@ -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; diff --git a/qcsrc/server/defs.qh b/qcsrc/server/defs.qh index 30c9bb4494..a1c180cef8 100644 --- a/qcsrc/server/defs.qh +++ b/qcsrc/server/defs.qh @@ -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(); } diff --git a/qcsrc/server/pathlib/path_waypoint.qc b/qcsrc/server/pathlib/path_waypoint.qc index 01a6e2c747..a2aaf55635 100644 --- a/qcsrc/server/pathlib/path_waypoint.qc +++ b/qcsrc/server/pathlib/path_waypoint.qc @@ -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; -- 2.39.2