1 #include "game.h"
2 
3 extern selinfo sel;
4 
5 namespace ai
6 {
7     using namespace game;
8 
9     vector<waypoint> waypoints;
10 
clipped(const vec & o)11     bool clipped(const vec &o)
12     {
13         int material = lookupmaterial(o), clipmat = material&MATF_CLIP;
14         return clipmat == MAT_CLIP || material&MAT_DEATH || (material&MATF_VOLUME) == MAT_LAVA;
15     }
16 
getweight(const vec & o)17     int getweight(const vec &o)
18     {
19         vec pos = o; pos.z += ai::JUMPMIN;
20         if(!insideworld(vec(pos.x, pos.y, min(pos.z, getworldsize() - 1e-3f)))) return -2;
21         float dist = raycube(pos, vec(0, 0, -1), 0, RAY_CLIPMAT);
22         int posmat = lookupmaterial(pos), weight = 1;
23         if(isliquid(posmat&MATF_VOLUME)) weight *= 5;
24         if(dist >= 0)
25         {
26             weight = int(dist/ai::JUMPMIN);
27             pos.z -= clamp(dist-8.0f, 0.0f, pos.z);
28             int trgmat = lookupmaterial(pos);
29             if(trgmat&MAT_DEATH || (trgmat&MATF_VOLUME) == MAT_LAVA) weight *= 10;
30             else if(isliquid(trgmat&MATF_VOLUME)) weight *= 2;
31         }
32         return weight;
33     }
34 
35     enum
36     {
37         WPCACHE_STATIC = 0,
38         WPCACHE_DYNAMIC,
39         NUMWPCACHES
40     };
41 
42     struct wpcache
43     {
44         struct node
45         {
46             float split[2];
47             uint child[2];
48 
axisai::wpcache::node49             int axis() const { return child[0]>>30; }
childindexai::wpcache::node50             int childindex(int which) const { return child[which]&0x3FFFFFFF; }
isleafai::wpcache::node51             bool isleaf(int which) const { return (child[1]&(1<<(30+which)))!=0; }
52         };
53 
54         vector<node> nodes;
55         int firstwp, lastwp;
56         vec bbmin, bbmax;
57 
wpcacheai::wpcache58         wpcache() { clear(); }
59 
clearai::wpcache60         void clear()
61         {
62             nodes.setsize(0);
63             firstwp = lastwp = -1;
64             bbmin = vec(1e16f, 1e16f, 1e16f);
65             bbmax = vec(-1e16f, -1e16f, -1e16f);
66         }
67 
buildai::wpcache68         void build(int first = 0, int last = -1)
69         {
70             if(last < 0) last = waypoints.length();
71             vector<int> indices;
72             for(int i = first; i < last; i++)
73             {
74                 waypoint &w = waypoints[i];
75                 indices.add(i);
76                 if(firstwp < 0) firstwp = i;
77                 float radius = WAYPOINTRADIUS;
78                 bbmin.min(vec(w.o).sub(radius));
79                 bbmax.max(vec(w.o).add(radius));
80             }
81             if(first < last) lastwp = max(lastwp, last-1);
82             nodes.reserve(indices.length());
83             build(indices.getbuf(), indices.length(), bbmin, bbmax);
84         }
85 
buildai::wpcache86         void build(int *indices, int numindices, const vec &vmin, const vec &vmax)
87         {
88             int axis = 2;
89             loopk(2) if(vmax[k] - vmin[k] > vmax[axis] - vmin[axis]) axis = k;
90 
91             vec leftmin(1e16f, 1e16f, 1e16f), leftmax(-1e16f, -1e16f, -1e16f), rightmin(1e16f, 1e16f, 1e16f), rightmax(-1e16f, -1e16f, -1e16f);
92             float split = 0.5f*(vmax[axis] + vmin[axis]), splitleft = -1e16f, splitright = 1e16f;
93             int left, right;
94             for(left = 0, right = numindices; left < right;)
95             {
96                 waypoint &w = waypoints[indices[left]];
97                 float radius = WAYPOINTRADIUS;
98                 if(max(split - (w.o[axis]-radius), 0.0f) > max((w.o[axis]+radius) - split, 0.0f))
99                 {
100                     ++left;
101                     splitleft = max(splitleft, w.o[axis]+radius);
102                     leftmin.min(vec(w.o).sub(radius));
103                     leftmax.max(vec(w.o).add(radius));
104                 }
105                 else
106                 {
107                     --right;
108                     swap(indices[left], indices[right]);
109                     splitright = min(splitright, w.o[axis]-radius);
110                     rightmin.min(vec(w.o).sub(radius));
111                     rightmax.max(vec(w.o).add(radius));
112                 }
113             }
114 
115             if(!left || right==numindices)
116             {
117                 leftmin = rightmin = vec(1e16f, 1e16f, 1e16f);
118                 leftmax = rightmax = vec(-1e16f, -1e16f, -1e16f);
119                 left = right = numindices/2;
120                 splitleft = -1e16f;
121                 splitright = 1e16f;
122                 loopi(numindices)
123                 {
124                     waypoint &w = waypoints[indices[i]];
125                     float radius = WAYPOINTRADIUS;
126                     if(i < left)
127                     {
128                         splitleft = max(splitleft, w.o[axis]+radius);
129                         leftmin.min(vec(w.o).sub(radius));
130                         leftmax.max(vec(w.o).add(radius));
131                     }
132                     else
133                     {
134                         splitright = min(splitright, w.o[axis]-radius);
135                         rightmin.min(vec(w.o).sub(radius));
136                         rightmax.max(vec(w.o).add(radius));
137                     }
138                 }
139             }
140 
141             int offset = nodes.length();
142             node &curnode = nodes.add();
143             curnode.split[0] = splitleft;
144             curnode.split[1] = splitright;
145 
146             if(left<=1) curnode.child[0] = (axis<<30) | (left>0 ? indices[0] : 0x3FFFFFFF);
147             else
148             {
149                 curnode.child[0] = (axis<<30) | (nodes.length()-offset);
150                 if(left) build(indices, left, leftmin, leftmax);
151             }
152 
153             if(numindices-right<=1) curnode.child[1] = (1<<31) | (left<=1 ? 1<<30 : 0) | (numindices-right>0 ? indices[right] : 0x3FFFFFFF);
154             else
155             {
156                 curnode.child[1] = (left<=1 ? 1<<30 : 0) | (nodes.length()-offset);
157                 if(numindices-right) build(&indices[right], numindices-right, rightmin, rightmax);
158             }
159         }
160     } wpcaches[NUMWPCACHES];
161 
162     static int invalidatedwpcaches = 0, clearedwpcaches = (1<<NUMWPCACHES)-1, numinvalidatewpcaches = 0, lastwpcache = 0;
163 
invalidatewpcache(int wp)164     static inline void invalidatewpcache(int wp)
165     {
166         if(++numinvalidatewpcaches >= 1000) { numinvalidatewpcaches = 0; invalidatedwpcaches = (1<<NUMWPCACHES)-1; }
167         else loopi(NUMWPCACHES) if((wp >= wpcaches[i].firstwp && wp <= wpcaches[i].lastwp) || i+1 >= NUMWPCACHES) { invalidatedwpcaches |= 1<<i; break; }
168     }
169 
clearwpcache(bool full=true)170     void clearwpcache(bool full = true)
171     {
172         loopi(NUMWPCACHES) if(full || invalidatedwpcaches&(1<<i)) { wpcaches[i].clear(); clearedwpcaches |= 1<<i; }
173         if(full || invalidatedwpcaches == (1<<NUMWPCACHES)-1)
174         {
175             numinvalidatewpcaches = 0;
176             lastwpcache = 0;
177         }
178         invalidatedwpcaches = 0;
179     }
180     ICOMMAND(clearwpcache, "", (), clearwpcache());
181 
182     avoidset wpavoid;
183 
buildwpcache()184     void buildwpcache()
185     {
186         loopi(NUMWPCACHES) if(wpcaches[i].firstwp < 0)
187             wpcaches[i].build(i > 0 ? wpcaches[i-1].lastwp+1 : 1, i+1 >= NUMWPCACHES || wpcaches[i+1].firstwp < 0 ? -1 : wpcaches[i+1].firstwp);
188         clearedwpcaches = 0;
189         lastwpcache = waypoints.length();
190 
191         wpavoid.clear();
192         loopv(waypoints) if(waypoints[i].weight < 0) wpavoid.avoidnear(NULL, waypoints[i].o.z + WAYPOINTRADIUS, waypoints[i].o, WAYPOINTRADIUS);
193     }
194 
195     struct wpcachestack
196     {
197         wpcache::node *node;
198         float tmin, tmax;
199     };
200 
201     vector<wpcache::node *> wpcachestack;
202 
closestwaypoint(const vec & pos,float mindist,bool links,gameent * d)203     int closestwaypoint(const vec &pos, float mindist, bool links, gameent *d)
204     {
205         if(waypoints.empty()) return -1;
206         if(clearedwpcaches) buildwpcache();
207 
208         #define CHECKCLOSEST(index) do { \
209             int n = (index); \
210             const waypoint &w = waypoints[n]; \
211             if(!links || w.links[0]) \
212             { \
213                 float dist = w.o.squaredist(pos); \
214                 if(dist < mindist*mindist) { closest = n; mindist = sqrtf(dist); } \
215             } \
216         } while(0)
217         int closest = -1;
218         wpcache::node *curnode;
219         loop(which, NUMWPCACHES) for(curnode = &wpcaches[which].nodes[0], wpcachestack.setsize(0);;)
220         {
221             int axis = curnode->axis();
222             float dist1 = pos[axis] - curnode->split[0], dist2 = curnode->split[1] - pos[axis];
223             if(dist1 >= mindist)
224             {
225                 if(dist2 < mindist)
226                 {
227                     if(!curnode->isleaf(1)) { curnode += curnode->childindex(1); continue; }
228                     CHECKCLOSEST(curnode->childindex(1));
229                 }
230             }
231             else if(curnode->isleaf(0))
232             {
233                 CHECKCLOSEST(curnode->childindex(0));
234                 if(dist2 < mindist)
235                 {
236                     if(!curnode->isleaf(1)) { curnode += curnode->childindex(1); continue; }
237                     CHECKCLOSEST(curnode->childindex(1));
238                 }
239             }
240             else
241             {
242                 if(dist2 < mindist)
243                 {
244                     if(!curnode->isleaf(1)) wpcachestack.add(curnode + curnode->childindex(1));
245                     else CHECKCLOSEST(curnode->childindex(1));
246                 }
247                 curnode += curnode->childindex(0);
248                 continue;
249             }
250             if(wpcachestack.empty()) break;
251             curnode = wpcachestack.pop();
252         }
253         for(int i = lastwpcache; i < waypoints.length(); i++) { CHECKCLOSEST(i); }
254         return closest;
255     }
256 
findwaypointswithin(const vec & pos,float mindist,float maxdist,vector<int> & results)257     void findwaypointswithin(const vec &pos, float mindist, float maxdist, vector<int> &results)
258     {
259         if(waypoints.empty()) return;
260         if(clearedwpcaches) buildwpcache();
261 
262         float mindist2 = mindist*mindist, maxdist2 = maxdist*maxdist;
263         #define CHECKWITHIN(index) do { \
264             int n = (index); \
265             const waypoint &w = waypoints[n]; \
266             float dist = w.o.squaredist(pos); \
267             if(dist > mindist2 && dist < maxdist2) results.add(n); \
268         } while(0)
269         wpcache::node *curnode;
270         loop(which, NUMWPCACHES) for(curnode = &wpcaches[which].nodes[0], wpcachestack.setsize(0);;)
271         {
272             int axis = curnode->axis();
273             float dist1 = pos[axis] - curnode->split[0], dist2 = curnode->split[1] - pos[axis];
274             if(dist1 >= maxdist)
275             {
276                 if(dist2 < maxdist)
277                 {
278                     if(!curnode->isleaf(1)) { curnode += curnode->childindex(1); continue; }
279                     CHECKWITHIN(curnode->childindex(1));
280                 }
281             }
282             else if(curnode->isleaf(0))
283             {
284                 CHECKWITHIN(curnode->childindex(0));
285                 if(dist2 < maxdist)
286                 {
287                     if(!curnode->isleaf(1)) { curnode += curnode->childindex(1); continue; }
288                     CHECKWITHIN(curnode->childindex(1));
289                 }
290             }
291             else
292             {
293                 if(dist2 < maxdist)
294                 {
295                     if(!curnode->isleaf(1)) wpcachestack.add(curnode + curnode->childindex(1));
296                     else CHECKWITHIN(curnode->childindex(1));
297                 }
298                 curnode += curnode->childindex(0);
299                 continue;
300             }
301             if(wpcachestack.empty()) break;
302             curnode = wpcachestack.pop();
303         }
304         for(int i = lastwpcache; i < waypoints.length(); i++) { CHECKWITHIN(i); }
305     }
306 
avoidnear(void * owner,float above,const vec & pos,float limit)307     void avoidset::avoidnear(void *owner, float above, const vec &pos, float limit)
308     {
309         if(ai::waypoints.empty()) return;
310         if(clearedwpcaches) buildwpcache();
311 
312         float limit2 = limit*limit;
313         #define CHECKNEAR(index) do { \
314             int n = (index); \
315             const waypoint &w = ai::waypoints[n]; \
316             if(w.o.squaredist(pos) < limit2) add(owner, above, n); \
317         } while(0)
318         wpcache::node *curnode;
319         loop(which, NUMWPCACHES) for(curnode = &wpcaches[which].nodes[0], wpcachestack.setsize(0);;)
320         {
321             int axis = curnode->axis();
322             float dist1 = pos[axis] - curnode->split[0], dist2 = curnode->split[1] - pos[axis];
323             if(dist1 >= limit)
324             {
325                 if(dist2 < limit)
326                 {
327                     if(!curnode->isleaf(1)) { curnode += curnode->childindex(1); continue; }
328                     CHECKNEAR(curnode->childindex(1));
329                 }
330             }
331             else if(curnode->isleaf(0))
332             {
333                 CHECKNEAR(curnode->childindex(0));
334                 if(dist2 < limit)
335                 {
336                     if(!curnode->isleaf(1)) { curnode += curnode->childindex(1); continue; }
337                     CHECKNEAR(curnode->childindex(1));
338                 }
339             }
340             else
341             {
342                 if(dist2 < limit)
343                 {
344                     if(!curnode->isleaf(1)) wpcachestack.add(curnode + curnode->childindex(1));
345                     else CHECKNEAR(curnode->childindex(1));
346                 }
347                 curnode += curnode->childindex(0);
348                 continue;
349             }
350             if(wpcachestack.empty()) break;
351             curnode = wpcachestack.pop();
352         }
353         for(int i = lastwpcache; i < waypoints.length(); i++) { CHECKNEAR(i); }
354     }
355 
remap(gameent * d,int n,vec & pos,bool retry)356     int avoidset::remap(gameent *d, int n, vec &pos, bool retry)
357     {
358         if(!obstacles.empty())
359         {
360             int cur = 0;
361             loopv(obstacles)
362             {
363                 obstacle &ob = obstacles[i];
364                 int next = cur + ob.numwaypoints;
365                 if(ob.owner != d)
366                 {
367                     for(; cur < next; cur++) if(waypoints[cur] == n)
368                     {
369                         if(ob.above < 0) return retry ? n : -1;
370                         vec above(pos.x, pos.y, ob.above);
371                         if(above.z-d->o.z >= ai::JUMPMAX)
372                             return retry ? n : -1; // too much scotty
373                         int node = closestwaypoint(above, ai::SIGHTMIN, true, d);
374                         if(ai::iswaypoint(node) && node != n)
375                         { // try to reroute above their head?
376                             if(!find(node, d))
377                             {
378                                 pos = ai::waypoints[node].o;
379                                 return node;
380                             }
381                             else return retry ? n : -1;
382                         }
383                         else
384                         {
385                             vec old = d->o;
386                             d->o = vec(above).addz(d->eyeheight);
387                             bool col = collide(d, vec(0, 0, 1));
388                             d->o = old;
389                             if(!col)
390                             {
391                                 pos = above;
392                                 return n;
393                             }
394                             else return retry ? n : -1;
395                         }
396                     }
397                 }
398                 cur = next;
399             }
400         }
401         return n;
402     }
403 
heapscore(waypoint * q)404     static inline float heapscore(waypoint *q) { return q->score(); }
405 
route(gameent * d,int node,int goal,vector<int> & route,const avoidset & obstacles,int retries)406     bool route(gameent *d, int node, int goal, vector<int> &route, const avoidset &obstacles, int retries)
407     {
408         if(waypoints.empty() || !iswaypoint(node) || !iswaypoint(goal) || goal == node || !waypoints[node].links[0])
409             return false;
410 
411         static ushort routeid = 1;
412         static vector<waypoint *> queue;
413 
414         if(!routeid)
415         {
416             loopv(waypoints) waypoints[i].route = 0;
417             routeid = 1;
418         }
419 
420         if(d)
421         {
422             if(retries <= 1 && d->ai) loopi(ai::NUMPREVNODES) if(d->ai->prevnodes[i] != node && iswaypoint(d->ai->prevnodes[i]))
423             {
424                 waypoints[d->ai->prevnodes[i]].route = routeid;
425                 waypoints[d->ai->prevnodes[i]].curscore = -1;
426                 waypoints[d->ai->prevnodes[i]].estscore = 0;
427             }
428             if(retries <= 0)
429             {
430                 loopavoid(obstacles, d,
431                 {
432                     if(iswaypoint(wp) && wp != node && wp != goal && waypoints[node].find(wp) < 0 && waypoints[goal].find(wp) < 0)
433                     {
434                         waypoints[wp].route = routeid;
435                         waypoints[wp].curscore = -1;
436                         waypoints[wp].estscore = 0;
437                     }
438                 });
439             }
440         }
441 
442         waypoints[node].route = routeid;
443         waypoints[node].curscore = waypoints[node].estscore = 0;
444         waypoints[node].prev = 0;
445         queue.setsize(0);
446         queue.add(&waypoints[node]);
447         route.setsize(0);
448 
449         int lowest = -1;
450         while(!queue.empty())
451         {
452             waypoint &m = *queue.removeheap();
453             float prevscore = m.curscore;
454             m.curscore = -1;
455             loopi(MAXWAYPOINTLINKS)
456             {
457                 int link = m.links[i];
458                 if(!link) break;
459                 if(iswaypoint(link) && (link == node || link == goal || waypoints[link].links[0]))
460                 {
461                     waypoint &n = waypoints[link];
462                     int weight = max(n.weight, 1);
463                     float curscore = prevscore + n.o.dist(m.o)*weight;
464                     if(n.route == routeid && curscore >= n.curscore) continue;
465                     n.curscore = curscore;
466                     n.prev = ushort(&m - &waypoints[0]);
467                     if(n.route != routeid)
468                     {
469                         n.estscore = n.o.dist(waypoints[goal].o)*weight;
470                         if(n.estscore <= WAYPOINTRADIUS*4 && (lowest < 0 || n.estscore <= waypoints[lowest].estscore))
471                             lowest = link;
472                         n.route = routeid;
473                         if(link == goal) goto foundgoal;
474                         queue.addheap(&n);
475                     }
476                     else loopvj(queue) if(queue[j] == &n) { queue.upheap(j); break; }
477                 }
478             }
479         }
480         foundgoal:
481 
482         routeid++;
483 
484         if(lowest >= 0) // otherwise nothing got there
485         {
486             for(waypoint *m = &waypoints[lowest]; m > &waypoints[0]; m = &waypoints[m->prev])
487                 route.add(m - &waypoints[0]); // just keep it stored backward
488         }
489 
490         return !route.empty();
491     }
492 
493     VARF(dropwaypoints, 0, 0, 1, { player1->lastnode = -1; });
494 
addwaypoint(const vec & o,int weight=-1)495     int addwaypoint(const vec &o, int weight = -1)
496     {
497         if(waypoints.length() > MAXWAYPOINTS) return -1;
498         int n = waypoints.length();
499         waypoints.add(waypoint(o, weight >= 0 ? weight : getweight(o)));
500         return n;
501     }
502 
linkwaypoint(waypoint & a,int n)503     void linkwaypoint(waypoint &a, int n)
504     {
505         loopi(MAXWAYPOINTLINKS)
506         {
507             if(a.links[i] == n) return;
508             if(!a.links[i]) { a.links[i] = n; return; }
509         }
510         a.links[rnd(MAXWAYPOINTLINKS)] = n;
511     }
512 
513     string loadedwaypoints = "";
514 
shouldnavigate()515     static inline bool shouldnavigate()
516     {
517         if(dropwaypoints) return true;
518         loopvrev(players) if(players[i]->aitype != AI_NONE) return true;
519         return false;
520     }
521 
shoulddrop(gameent * d)522     static inline bool shoulddrop(gameent *d)
523     {
524         return !d->ai && (dropwaypoints || !loadedwaypoints[0]);
525     }
526 
inferwaypoints(gameent * d,const vec & o,const vec & v,float mindist)527     void inferwaypoints(gameent *d, const vec &o, const vec &v, float mindist)
528     {
529         if(!shouldnavigate()) return;
530         if(shoulddrop(d))
531         {
532             if(waypoints.empty()) seedwaypoints();
533             int from = closestwaypoint(o, mindist, false), to = closestwaypoint(v, mindist, false);
534             if(!iswaypoint(from)) from = addwaypoint(o);
535             if(!iswaypoint(to)) to = addwaypoint(v);
536             if(d->lastnode != from && iswaypoint(d->lastnode) && iswaypoint(from))
537                 linkwaypoint(waypoints[d->lastnode], from);
538             if(iswaypoint(to))
539             {
540                 if(from != to && iswaypoint(from) && iswaypoint(to))
541                     linkwaypoint(waypoints[from], to);
542                 d->lastnode = to;
543             }
544         }
545         else d->lastnode = closestwaypoint(v, WAYPOINTRADIUS*2, false, d);
546     }
547 
navigate(gameent * d)548     void navigate(gameent *d)
549     {
550         vec v(d->feetpos());
551         if(d->state != CS_ALIVE) { d->lastnode = -1; return; }
552         bool dropping = shoulddrop(d);
553         int mat = lookupmaterial(v);
554         if((mat&MATF_CLIP) == MAT_CLIP || (mat&MATF_VOLUME) == MAT_LAVA || mat&MAT_DEATH) dropping = false;
555         float dist = dropping ? WAYPOINTRADIUS : (d->ai ? WAYPOINTRADIUS : SIGHTMIN);
556         int curnode = closestwaypoint(v, dist, false, d), prevnode = d->lastnode;
557         if(!iswaypoint(curnode) && dropping)
558         {
559             if(waypoints.empty()) seedwaypoints();
560             curnode = addwaypoint(v);
561         }
562         if(iswaypoint(curnode))
563         {
564             if(dropping && d->lastnode != curnode && iswaypoint(d->lastnode))
565             {
566                 linkwaypoint(waypoints[d->lastnode], curnode);
567                 if(!d->timeinair) linkwaypoint(waypoints[curnode], d->lastnode);
568             }
569             d->lastnode = curnode;
570             if(d->ai && iswaypoint(prevnode) && d->lastnode != prevnode) d->ai->addprevnode(prevnode);
571         }
572         else if(!iswaypoint(d->lastnode) || waypoints[d->lastnode].o.squaredist(v) > SIGHTMIN*SIGHTMIN)
573             d->lastnode = closestwaypoint(v, SIGHTMAX, false, d);
574     }
575 
navigate()576     void navigate()
577     {
578         if(shouldnavigate()) loopv(players) ai::navigate(players[i]);
579         if(invalidatedwpcaches) clearwpcache(false);
580     }
581 
clearwaypoints(bool full)582     void clearwaypoints(bool full)
583     {
584         waypoints.setsize(0);
585         clearwpcache();
586         if(full)
587         {
588             loadedwaypoints[0] = '\0';
589             dropwaypoints = 0;
590         }
591     }
592     ICOMMAND(clearwaypoints, "", (), clearwaypoints());
593 
seedwaypoints()594     void seedwaypoints()
595     {
596         if(waypoints.empty()) addwaypoint(vec(0, 0, 0));
597         loopv(entities::ents)
598         {
599             extentity &e = *entities::ents[i];
600             switch(e.type)
601             {
602                 case PLAYERSTART: case TELEPORT: case JUMPPAD: case FLAG:
603                     addwaypoint(e.o);
604                     break;
605                 default:
606                     if(validitem(e.type)) addwaypoint(e.o);
607                     break;
608             }
609         }
610     }
611 
remapwaypoints()612     void remapwaypoints()
613     {
614         vector<ushort> remap;
615         int total = 0;
616         loopv(waypoints) remap.add(waypoints[i].links[1] == 0xFFFF ? 0 : total++);
617         total = 0;
618         loopvj(waypoints)
619         {
620             if(waypoints[j].links[1] == 0xFFFF) continue;
621             waypoint &w = waypoints[total];
622             if(j != total) w = waypoints[j];
623             int k = 0;
624             loopi(MAXWAYPOINTLINKS)
625             {
626                 int link = w.links[i];
627                 if(!link) break;
628                 if((w.links[k] = remap[link])) k++;
629             }
630             if(k < MAXWAYPOINTLINKS) w.links[k] = 0;
631             total++;
632         }
633         waypoints.setsize(total);
634     }
635 
cleanwaypoints()636     bool cleanwaypoints()
637     {
638         int cleared = 0;
639         for(int i = 1; i < waypoints.length(); i++)
640         {
641             waypoint &w = waypoints[i];
642             if(clipped(w.o))
643             {
644                 w.links[0] = 0;
645                 w.links[1] = 0xFFFF;
646                 cleared++;
647             }
648         }
649         if(cleared)
650         {
651             player1->lastnode = -1;
652             loopv(players) if(players[i]) players[i]->lastnode = -1;
653             remapwaypoints();
654             clearwpcache();
655             return true;
656         }
657         return false;
658     }
659 
getwaypointfile(const char * mname,char * wptname)660     bool getwaypointfile(const char *mname, char *wptname)
661     {
662         if(!mname || !*mname) mname = getclientmap();
663         if(!*mname) return false;
664 
665         nformatstring(wptname, MAXSTRLEN, "media/map/%s.wpt", mname);
666         path(wptname);
667         return true;
668     }
669 
loadwaypoints(bool force,const char * mname)670     void loadwaypoints(bool force, const char *mname)
671     {
672         string wptname;
673         if(!getwaypointfile(mname, wptname)) return;
674         if(!force && (waypoints.length() || !strcmp(loadedwaypoints, wptname))) return;
675 
676         stream *f = opengzfile(wptname, "rb");
677         if(!f) return;
678         char magic[4];
679         if(f->read(magic, 4) < 4 || memcmp(magic, "OWPT", 4)) { delete f; return; }
680 
681         copystring(loadedwaypoints, wptname);
682 
683         waypoints.setsize(0);
684         waypoints.add(vec(0, 0, 0));
685         ushort numwp = f->getlil<ushort>();
686         loopi(numwp)
687         {
688             if(f->end()) break;
689             vec o;
690             o.x = f->getlil<float>();
691             o.y = f->getlil<float>();
692             o.z = f->getlil<float>();
693             waypoint &w = waypoints.add(waypoint(o, getweight(o)));
694             int numlinks = f->getchar(), k = 0;
695             loopi(numlinks)
696             {
697                 if((w.links[k] = f->getlil<ushort>()))
698                 {
699                     if(++k >= MAXWAYPOINTLINKS) break;
700                 }
701             }
702         }
703 
704         delete f;
705         conoutf("loaded %d waypoints from %s", numwp, wptname);
706 
707         if(!cleanwaypoints()) clearwpcache();
708     }
709     ICOMMAND(loadwaypoints, "s", (char *mname), loadwaypoints(true, mname));
710 
savewaypoints(bool force,const char * mname)711     void savewaypoints(bool force, const char *mname)
712     {
713         if((!dropwaypoints && !force) || waypoints.empty()) return;
714 
715         string wptname;
716         if(!getwaypointfile(mname, wptname)) return;
717 
718         stream *f = opengzfile(wptname, "wb");
719         if(!f) return;
720         f->write("OWPT", 4);
721         f->putlil<ushort>(waypoints.length()-1);
722         for(int i = 1; i < waypoints.length(); i++)
723         {
724             waypoint &w = waypoints[i];
725             f->putlil<float>(w.o.x);
726             f->putlil<float>(w.o.y);
727             f->putlil<float>(w.o.z);
728             int numlinks = 0;
729             loopj(MAXWAYPOINTLINKS) { if(!w.links[j]) break; numlinks++; }
730             f->putchar(numlinks);
731             loopj(numlinks) f->putlil<ushort>(w.links[j]);
732         }
733 
734         delete f;
735         conoutf("saved %d waypoints to %s", waypoints.length()-1, wptname);
736     }
737 
738     ICOMMAND(savewaypoints, "s", (char *mname), savewaypoints(true, mname));
739 
delselwaypoints()740     void delselwaypoints()
741     {
742         if(noedit(true)) return;
743         vec o = vec(sel.o).sub(0.1f), s = vec(sel.s).mul(sel.grid).add(o).add(0.1f);
744         int cleared = 0;
745         for(int i = 1; i < waypoints.length(); i++)
746         {
747             waypoint &w = waypoints[i];
748             if(w.o.x >= o.x && w.o.x <= s.x && w.o.y >= o.y && w.o.y <= s.y && w.o.z >= o.z && w.o.z <= s.z)
749             {
750                 w.links[0] = 0;
751                 w.links[1] = 0xFFFF;
752                 cleared++;
753             }
754         }
755         if(cleared)
756         {
757             player1->lastnode = -1;
758             remapwaypoints();
759             clearwpcache();
760         }
761     }
762     COMMAND(delselwaypoints, "");
763 
movewaypoints(const vec & d)764     void movewaypoints(const vec &d)
765     {
766         if(noedit(true)) return;
767         int worldsize = getworldsize();
768         if(d.x < -worldsize || d.x > worldsize || d.y < -worldsize || d.y > worldsize || d.z < -worldsize || d.z > worldsize)
769         {
770             clearwaypoints();
771             return;
772         }
773         int cleared = 0;
774         for(int i = 1; i < waypoints.length(); i++)
775         {
776             waypoint &w = waypoints[i];
777             w.o.add(d);
778             if(!insideworld(w.o)) { w.links[0] = 0; w.links[1] = 0xFFFF; cleared++; }
779         }
780         if(cleared)
781         {
782             player1->lastnode = -1;
783             remapwaypoints();
784         }
785         clearwpcache();
786     }
787     ICOMMAND(movewaypoints, "iii", (int *dx, int *dy, int *dz), movewaypoints(vec(*dx, *dy, *dz)));
788 }
789 
790