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