1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4 Copyright (C) 2000-2006 Tim Angus
5
6 This file is part of Tremulous.
7
8 Tremulous is free software; you can redistribute it
9 and/or modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2 of the License,
11 or (at your option) any later version.
12
13 Tremulous is distributed in the hope that it will be
14 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with Tremulous; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 ===========================================================================
22 */
23
24 /*****************************************************************************
25 * name: be_aas_cluster.c
26 *
27 * desc: area clustering
28 *
29 * $Archive: /MissionPack/code/botlib/be_aas_cluster.c $
30 *
31 *****************************************************************************/
32
33 #include "../qcommon/q_shared.h"
34 #include "l_memory.h"
35 #include "l_script.h"
36 #include "l_precomp.h"
37 #include "l_struct.h"
38 #include "l_log.h"
39 #include "l_memory.h"
40 #include "l_libvar.h"
41 #include "aasfile.h"
42 #include "botlib.h"
43 #include "be_aas.h"
44 #include "be_aas_funcs.h"
45 #include "be_aas_def.h"
46
47 extern botlib_import_t botimport;
48
49 #define AAS_MAX_PORTALS 65536
50 #define AAS_MAX_PORTALINDEXSIZE 65536
51 #define AAS_MAX_CLUSTERS 65536
52 //
53 #define MAX_PORTALAREAS 1024
54
55 // do not flood through area faces, only use reachabilities
56 int nofaceflood = qtrue;
57
58 //===========================================================================
59 //
60 // Parameter: -
61 // Returns: -
62 // Changes Globals: -
63 //===========================================================================
AAS_RemoveClusterAreas(void)64 void AAS_RemoveClusterAreas(void)
65 {
66 int i;
67
68 for (i = 1; i < aasworld.numareas; i++)
69 {
70 aasworld.areasettings[i].cluster = 0;
71 } //end for
72 } //end of the function AAS_RemoveClusterAreas
73 //===========================================================================
74 //
75 // Parameter: -
76 // Returns: -
77 // Changes Globals: -
78 //===========================================================================
AAS_ClearCluster(int clusternum)79 void AAS_ClearCluster(int clusternum)
80 {
81 int i;
82
83 for (i = 1; i < aasworld.numareas; i++)
84 {
85 if (aasworld.areasettings[i].cluster == clusternum)
86 {
87 aasworld.areasettings[i].cluster = 0;
88 } //end if
89 } //end for
90 } //end of the function AAS_ClearCluster
91 //===========================================================================
92 //
93 // Parameter: -
94 // Returns: -
95 // Changes Globals: -
96 //===========================================================================
AAS_RemovePortalsClusterReference(int clusternum)97 void AAS_RemovePortalsClusterReference(int clusternum)
98 {
99 int portalnum;
100
101 for (portalnum = 1; portalnum < aasworld.numportals; portalnum++)
102 {
103 if (aasworld.portals[portalnum].frontcluster == clusternum)
104 {
105 aasworld.portals[portalnum].frontcluster = 0;
106 } //end if
107 if (aasworld.portals[portalnum].backcluster == clusternum)
108 {
109 aasworld.portals[portalnum].backcluster = 0;
110 } //end if
111 } //end for
112 } //end of the function AAS_RemovePortalsClusterReference
113 //===========================================================================
114 //
115 // Parameter: -
116 // Returns: -
117 // Changes Globals: -
118 //===========================================================================
AAS_UpdatePortal(int areanum,int clusternum)119 int AAS_UpdatePortal(int areanum, int clusternum)
120 {
121 int portalnum;
122 aas_portal_t *portal;
123 aas_cluster_t *cluster;
124
125 //find the portal of the area
126 for (portalnum = 1; portalnum < aasworld.numportals; portalnum++)
127 {
128 if (aasworld.portals[portalnum].areanum == areanum) break;
129 } //end for
130 //
131 if (portalnum == aasworld.numportals)
132 {
133 AAS_Error("no portal of area %d", areanum);
134 return qtrue;
135 } //end if
136 //
137 portal = &aasworld.portals[portalnum];
138 //if the portal is already fully updated
139 if (portal->frontcluster == clusternum) return qtrue;
140 if (portal->backcluster == clusternum) return qtrue;
141 //if the portal has no front cluster yet
142 if (!portal->frontcluster)
143 {
144 portal->frontcluster = clusternum;
145 } //end if
146 //if the portal has no back cluster yet
147 else if (!portal->backcluster)
148 {
149 portal->backcluster = clusternum;
150 } //end else if
151 else
152 {
153 //remove the cluster portal flag contents
154 aasworld.areasettings[areanum].contents &= ~AREACONTENTS_CLUSTERPORTAL;
155 Log_Write("portal area %d is seperating more than two clusters\r\n", areanum);
156 return qfalse;
157 } //end else
158 if (aasworld.portalindexsize >= AAS_MAX_PORTALINDEXSIZE)
159 {
160 AAS_Error("AAS_MAX_PORTALINDEXSIZE");
161 return qtrue;
162 } //end if
163 //set the area cluster number to the negative portal number
164 aasworld.areasettings[areanum].cluster = -portalnum;
165 //add the portal to the cluster using the portal index
166 cluster = &aasworld.clusters[clusternum];
167 aasworld.portalindex[cluster->firstportal + cluster->numportals] = portalnum;
168 aasworld.portalindexsize++;
169 cluster->numportals++;
170 return qtrue;
171 } //end of the function AAS_UpdatePortal
172 //===========================================================================
173 //
174 // Parameter: -
175 // Returns: -
176 // Changes Globals: -
177 //===========================================================================
AAS_FloodClusterAreas_r(int areanum,int clusternum)178 int AAS_FloodClusterAreas_r(int areanum, int clusternum)
179 {
180 aas_area_t *area;
181 aas_face_t *face;
182 int facenum, i;
183
184 //
185 if (areanum <= 0 || areanum >= aasworld.numareas)
186 {
187 AAS_Error("AAS_FloodClusterAreas_r: areanum out of range");
188 return qfalse;
189 } //end if
190 //if the area is already part of a cluster
191 if (aasworld.areasettings[areanum].cluster > 0)
192 {
193 if (aasworld.areasettings[areanum].cluster == clusternum) return qtrue;
194 //
195 //there's a reachability going from one cluster to another only in one direction
196 //
197 AAS_Error("cluster %d touched cluster %d at area %d\r\n",
198 clusternum, aasworld.areasettings[areanum].cluster, areanum);
199 return qfalse;
200 } //end if
201 //don't add the cluster portal areas to the clusters
202 if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL)
203 {
204 return AAS_UpdatePortal(areanum, clusternum);
205 } //end if
206 //set the area cluster number
207 aasworld.areasettings[areanum].cluster = clusternum;
208 aasworld.areasettings[areanum].clusterareanum =
209 aasworld.clusters[clusternum].numareas;
210 //the cluster has an extra area
211 aasworld.clusters[clusternum].numareas++;
212
213 area = &aasworld.areas[areanum];
214 //use area faces to flood into adjacent areas
215 if (!nofaceflood)
216 {
217 for (i = 0; i < area->numfaces; i++)
218 {
219 facenum = abs(aasworld.faceindex[area->firstface + i]);
220 face = &aasworld.faces[facenum];
221 if (face->frontarea == areanum)
222 {
223 if (face->backarea) if (!AAS_FloodClusterAreas_r(face->backarea, clusternum)) return qfalse;
224 } //end if
225 else
226 {
227 if (face->frontarea) if (!AAS_FloodClusterAreas_r(face->frontarea, clusternum)) return qfalse;
228 } //end else
229 } //end for
230 } //end if
231 //use the reachabilities to flood into other areas
232 for (i = 0; i < aasworld.areasettings[areanum].numreachableareas; i++)
233 {
234 if (!aasworld.reachability[
235 aasworld.areasettings[areanum].firstreachablearea + i].areanum)
236 {
237 continue;
238 } //end if
239 if (!AAS_FloodClusterAreas_r(aasworld.reachability[
240 aasworld.areasettings[areanum].firstreachablearea + i].areanum, clusternum)) return qfalse;
241 } //end for
242 return qtrue;
243 } //end of the function AAS_FloodClusterAreas_r
244 //===========================================================================
245 // try to flood from all areas without cluster into areas with a cluster set
246 //
247 // Parameter: -
248 // Returns: -
249 // Changes Globals: -
250 //===========================================================================
AAS_FloodClusterAreasUsingReachabilities(int clusternum)251 int AAS_FloodClusterAreasUsingReachabilities(int clusternum)
252 {
253 int i, j, areanum;
254
255 for (i = 1; i < aasworld.numareas; i++)
256 {
257 //if this area already has a cluster set
258 if (aasworld.areasettings[i].cluster)
259 continue;
260 //if this area is a cluster portal
261 if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)
262 continue;
263 //loop over the reachable areas from this area
264 for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
265 {
266 //the reachable area
267 areanum = aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].areanum;
268 //if this area is a cluster portal
269 if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL)
270 continue;
271 //if this area has a cluster set
272 if (aasworld.areasettings[areanum].cluster)
273 {
274 if (!AAS_FloodClusterAreas_r(i, clusternum))
275 return qfalse;
276 i = 0;
277 break;
278 } //end if
279 } //end for
280 } //end for
281 return qtrue;
282 } //end of the function AAS_FloodClusterAreasUsingReachabilities
283 //===========================================================================
284 //
285 // Parameter: -
286 // Returns: -
287 // Changes Globals: -
288 //===========================================================================
AAS_NumberClusterPortals(int clusternum)289 void AAS_NumberClusterPortals(int clusternum)
290 {
291 int i, portalnum;
292 aas_cluster_t *cluster;
293 aas_portal_t *portal;
294
295 cluster = &aasworld.clusters[clusternum];
296 for (i = 0; i < cluster->numportals; i++)
297 {
298 portalnum = aasworld.portalindex[cluster->firstportal + i];
299 portal = &aasworld.portals[portalnum];
300 if (portal->frontcluster == clusternum)
301 {
302 portal->clusterareanum[0] = cluster->numareas++;
303 } //end if
304 else
305 {
306 portal->clusterareanum[1] = cluster->numareas++;
307 } //end else
308 } //end for
309 } //end of the function AAS_NumberClusterPortals
310 //===========================================================================
311 //
312 // Parameter: -
313 // Returns: -
314 // Changes Globals: -
315 //===========================================================================
AAS_NumberClusterAreas(int clusternum)316 void AAS_NumberClusterAreas(int clusternum)
317 {
318 int i, portalnum;
319 aas_cluster_t *cluster;
320 aas_portal_t *portal;
321
322 aasworld.clusters[clusternum].numareas = 0;
323 aasworld.clusters[clusternum].numreachabilityareas = 0;
324 //number all areas in this cluster WITH reachabilities
325 for (i = 1; i < aasworld.numareas; i++)
326 {
327 //
328 if (aasworld.areasettings[i].cluster != clusternum) continue;
329 //
330 if (!AAS_AreaReachability(i)) continue;
331 //
332 aasworld.areasettings[i].clusterareanum = aasworld.clusters[clusternum].numareas;
333 //the cluster has an extra area
334 aasworld.clusters[clusternum].numareas++;
335 aasworld.clusters[clusternum].numreachabilityareas++;
336 } //end for
337 //number all portals in this cluster WITH reachabilities
338 cluster = &aasworld.clusters[clusternum];
339 for (i = 0; i < cluster->numportals; i++)
340 {
341 portalnum = aasworld.portalindex[cluster->firstportal + i];
342 portal = &aasworld.portals[portalnum];
343 if (!AAS_AreaReachability(portal->areanum)) continue;
344 if (portal->frontcluster == clusternum)
345 {
346 portal->clusterareanum[0] = cluster->numareas++;
347 aasworld.clusters[clusternum].numreachabilityareas++;
348 } //end if
349 else
350 {
351 portal->clusterareanum[1] = cluster->numareas++;
352 aasworld.clusters[clusternum].numreachabilityareas++;
353 } //end else
354 } //end for
355 //number all areas in this cluster WITHOUT reachabilities
356 for (i = 1; i < aasworld.numareas; i++)
357 {
358 //
359 if (aasworld.areasettings[i].cluster != clusternum) continue;
360 //
361 if (AAS_AreaReachability(i)) continue;
362 //
363 aasworld.areasettings[i].clusterareanum = aasworld.clusters[clusternum].numareas;
364 //the cluster has an extra area
365 aasworld.clusters[clusternum].numareas++;
366 } //end for
367 //number all portals in this cluster WITHOUT reachabilities
368 cluster = &aasworld.clusters[clusternum];
369 for (i = 0; i < cluster->numportals; i++)
370 {
371 portalnum = aasworld.portalindex[cluster->firstportal + i];
372 portal = &aasworld.portals[portalnum];
373 if (AAS_AreaReachability(portal->areanum)) continue;
374 if (portal->frontcluster == clusternum)
375 {
376 portal->clusterareanum[0] = cluster->numareas++;
377 } //end if
378 else
379 {
380 portal->clusterareanum[1] = cluster->numareas++;
381 } //end else
382 } //end for
383 } //end of the function AAS_NumberClusterAreas
384 //===========================================================================
385 //
386 // Parameter: -
387 // Returns: -
388 // Changes Globals: -
389 //===========================================================================
AAS_FindClusters(void)390 int AAS_FindClusters(void)
391 {
392 int i;
393 aas_cluster_t *cluster;
394
395 AAS_RemoveClusterAreas();
396 //
397 for (i = 1; i < aasworld.numareas; i++)
398 {
399 //if the area is already part of a cluster
400 if (aasworld.areasettings[i].cluster)
401 continue;
402 // if not flooding through faces only use areas that have reachabilities
403 if (nofaceflood)
404 {
405 if (!aasworld.areasettings[i].numreachableareas)
406 continue;
407 } //end if
408 //if the area is a cluster portal
409 if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)
410 continue;
411 if (aasworld.numclusters >= AAS_MAX_CLUSTERS)
412 {
413 AAS_Error("AAS_MAX_CLUSTERS");
414 return qfalse;
415 } //end if
416 cluster = &aasworld.clusters[aasworld.numclusters];
417 cluster->numareas = 0;
418 cluster->numreachabilityareas = 0;
419 cluster->firstportal = aasworld.portalindexsize;
420 cluster->numportals = 0;
421 //flood the areas in this cluster
422 if (!AAS_FloodClusterAreas_r(i, aasworld.numclusters))
423 return qfalse;
424 if (!AAS_FloodClusterAreasUsingReachabilities(aasworld.numclusters))
425 return qfalse;
426 //number the cluster areas
427 //AAS_NumberClusterPortals(aasworld.numclusters);
428 AAS_NumberClusterAreas(aasworld.numclusters);
429 //Log_Write("cluster %d has %d areas\r\n", aasworld.numclusters, cluster->numareas);
430 aasworld.numclusters++;
431 } //end for
432 return qtrue;
433 } //end of the function AAS_FindClusters
434 //===========================================================================
435 //
436 // Parameter: -
437 // Returns: -
438 // Changes Globals: -
439 //===========================================================================
AAS_CreatePortals(void)440 void AAS_CreatePortals(void)
441 {
442 int i;
443 aas_portal_t *portal;
444
445 for (i = 1; i < aasworld.numareas; i++)
446 {
447 //if the area is a cluster portal
448 if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)
449 {
450 if (aasworld.numportals >= AAS_MAX_PORTALS)
451 {
452 AAS_Error("AAS_MAX_PORTALS");
453 return;
454 } //end if
455 portal = &aasworld.portals[aasworld.numportals];
456 portal->areanum = i;
457 portal->frontcluster = 0;
458 portal->backcluster = 0;
459 aasworld.numportals++;
460 } //end if
461 } //end for
462 } //end of the function AAS_CreatePortals
463 /*
464 //===========================================================================
465 //
466 // Parameter: -
467 // Returns: -
468 // Changes Globals: -
469 //===========================================================================
470 int AAS_MapContainsTeleporters(void)
471 {
472 bsp_entity_t *entities, *ent;
473 char *classname;
474
475 entities = AAS_ParseBSPEntities();
476
477 for (ent = entities; ent; ent = ent->next)
478 {
479 classname = AAS_ValueForBSPEpairKey(ent, "classname");
480 if (classname && !strcmp(classname, "misc_teleporter"))
481 {
482 AAS_FreeBSPEntities(entities);
483 return qtrue;
484 } //end if
485 } //end for
486 return qfalse;
487 } //end of the function AAS_MapContainsTeleporters
488 //===========================================================================
489 //
490 // Parameter: -
491 // Returns: -
492 // Changes Globals: -
493 //===========================================================================
494 int AAS_NonConvexFaces(aas_face_t *face1, aas_face_t *face2, int side1, int side2)
495 {
496 int i, j, edgenum;
497 aas_plane_t *plane1, *plane2;
498 aas_edge_t *edge;
499
500
501 plane1 = &aasworld.planes[face1->planenum ^ side1];
502 plane2 = &aasworld.planes[face2->planenum ^ side2];
503
504 //check if one of the points of face1 is at the back of the plane of face2
505 for (i = 0; i < face1->numedges; i++)
506 {
507 edgenum = abs(aasworld.edgeindex[face1->firstedge + i]);
508 edge = &aasworld.edges[edgenum];
509 for (j = 0; j < 2; j++)
510 {
511 if (DotProduct(plane2->normal, aasworld.vertexes[edge->v[j]]) -
512 plane2->dist < -0.01) return qtrue;
513 } //end for
514 } //end for
515 for (i = 0; i < face2->numedges; i++)
516 {
517 edgenum = abs(aasworld.edgeindex[face2->firstedge + i]);
518 edge = &aasworld.edges[edgenum];
519 for (j = 0; j < 2; j++)
520 {
521 if (DotProduct(plane1->normal, aasworld.vertexes[edge->v[j]]) -
522 plane1->dist < -0.01) return qtrue;
523 } //end for
524 } //end for
525
526 return qfalse;
527 } //end of the function AAS_NonConvexFaces
528 //===========================================================================
529 //
530 // Parameter: -
531 // Returns: -
532 // Changes Globals: -
533 //===========================================================================
534 qboolean AAS_CanMergeAreas(int *areanums, int numareas)
535 {
536 int i, j, s, face1num, face2num, side1, side2, fn1, fn2;
537 aas_face_t *face1, *face2;
538 aas_area_t *area1, *area2;
539
540 for (i = 0; i < numareas; i++)
541 {
542 area1 = &aasworld.areas[areanums[i]];
543 for (fn1 = 0; fn1 < area1->numfaces; fn1++)
544 {
545 face1num = abs(aasworld.faceindex[area1->firstface + fn1]);
546 face1 = &aasworld.faces[face1num];
547 side1 = face1->frontarea != areanums[i];
548 //check if the face isn't a shared one with one of the other areas
549 for (s = 0; s < numareas; s++)
550 {
551 if (s == i) continue;
552 if (face1->frontarea == s || face1->backarea == s) break;
553 } //end for
554 //if the face was a shared one
555 if (s != numareas) continue;
556 //
557 for (j = 0; j < numareas; j++)
558 {
559 if (j == i) continue;
560 area2 = &aasworld.areas[areanums[j]];
561 for (fn2 = 0; fn2 < area2->numfaces; fn2++)
562 {
563 face2num = abs(aasworld.faceindex[area2->firstface + fn2]);
564 face2 = &aasworld.faces[face2num];
565 side2 = face2->frontarea != areanums[j];
566 //check if the face isn't a shared one with one of the other areas
567 for (s = 0; s < numareas; s++)
568 {
569 if (s == j) continue;
570 if (face2->frontarea == s || face2->backarea == s) break;
571 } //end for
572 //if the face was a shared one
573 if (s != numareas) continue;
574 //
575 if (AAS_NonConvexFaces(face1, face2, side1, side2)) return qfalse;
576 } //end for
577 } //end for
578 } //end for
579 } //end for
580 return qtrue;
581 } //end of the function AAS_CanMergeAreas
582 //===========================================================================
583 //
584 // Parameter: -
585 // Returns: -
586 // Changes Globals: -
587 //===========================================================================
588 qboolean AAS_NonConvexEdges(aas_edge_t *edge1, aas_edge_t *edge2, int side1, int side2, int planenum)
589 {
590 int i;
591 vec3_t edgevec1, edgevec2, normal1, normal2;
592 float dist1, dist2;
593 aas_plane_t *plane;
594
595 plane = &aasworld.planes[planenum];
596 VectorSubtract(aasworld.vertexes[edge1->v[1]], aasworld.vertexes[edge1->v[0]], edgevec1);
597 VectorSubtract(aasworld.vertexes[edge2->v[1]], aasworld.vertexes[edge2->v[0]], edgevec2);
598 if (side1) VectorInverse(edgevec1);
599 if (side2) VectorInverse(edgevec2);
600 //
601 CrossProduct(edgevec1, plane->normal, normal1);
602 dist1 = DotProduct(normal1, aasworld.vertexes[edge1->v[0]]);
603 CrossProduct(edgevec2, plane->normal, normal2);
604 dist2 = DotProduct(normal2, aasworld.vertexes[edge2->v[0]]);
605
606 for (i = 0; i < 2; i++)
607 {
608 if (DotProduct(aasworld.vertexes[edge1->v[i]], normal2) - dist2 < -0.01) return qfalse;
609 } //end for
610 for (i = 0; i < 2; i++)
611 {
612 if (DotProduct(aasworld.vertexes[edge2->v[i]], normal1) - dist1 < -0.01) return qfalse;
613 } //end for
614 return qtrue;
615 } //end of the function AAS_NonConvexEdges
616 //===========================================================================
617 //
618 // Parameter: -
619 // Returns: -
620 // Changes Globals: -
621 //===========================================================================
622 qboolean AAS_CanMergeFaces(int *facenums, int numfaces, int planenum)
623 {
624 int i, j, s, edgenum1, edgenum2, side1, side2, en1, en2, ens;
625 aas_face_t *face1, *face2, *otherface;
626 aas_edge_t *edge1, *edge2;
627
628 for (i = 0; i < numfaces; i++)
629 {
630 face1 = &aasworld.faces[facenums[i]];
631 for (en1 = 0; en1 < face1->numedges; en1++)
632 {
633 edgenum1 = aasworld.edgeindex[face1->firstedge + en1];
634 side1 = (edgenum1 < 0) ^ (face1->planenum != planenum);
635 edgenum1 = abs(edgenum1);
636 edge1 = &aasworld.edges[edgenum1];
637 //check if the edge is shared with another face
638 for (s = 0; s < numfaces; s++)
639 {
640 if (s == i) continue;
641 otherface = &aasworld.faces[facenums[s]];
642 for (ens = 0; ens < otherface->numedges; ens++)
643 {
644 if (edgenum1 == abs(aasworld.edgeindex[otherface->firstedge + ens])) break;
645 } //end for
646 if (ens != otherface->numedges) break;
647 } //end for
648 //if the edge was shared
649 if (s != numfaces) continue;
650 //
651 for (j = 0; j < numfaces; j++)
652 {
653 if (j == i) continue;
654 face2 = &aasworld.faces[facenums[j]];
655 for (en2 = 0; en2 < face2->numedges; en2++)
656 {
657 edgenum2 = aasworld.edgeindex[face2->firstedge + en2];
658 side2 = (edgenum2 < 0) ^ (face2->planenum != planenum);
659 edgenum2 = abs(edgenum2);
660 edge2 = &aasworld.edges[edgenum2];
661 //check if the edge is shared with another face
662 for (s = 0; s < numfaces; s++)
663 {
664 if (s == i) continue;
665 otherface = &aasworld.faces[facenums[s]];
666 for (ens = 0; ens < otherface->numedges; ens++)
667 {
668 if (edgenum2 == abs(aasworld.edgeindex[otherface->firstedge + ens])) break;
669 } //end for
670 if (ens != otherface->numedges) break;
671 } //end for
672 //if the edge was shared
673 if (s != numfaces) continue;
674 //
675 if (AAS_NonConvexEdges(edge1, edge2, side1, side2, planenum)) return qfalse;
676 } //end for
677 } //end for
678 } //end for
679 } //end for
680 return qtrue;
681 } //end of the function AAS_CanMergeFaces*/
682 //===========================================================================
683 //
684 // Parameter: -
685 // Returns: -
686 // Changes Globals: -
687 //===========================================================================
AAS_ConnectedAreas_r(int * areanums,int numareas,int * connectedareas,int curarea)688 void AAS_ConnectedAreas_r(int *areanums, int numareas, int *connectedareas, int curarea)
689 {
690 int i, j, otherareanum, facenum;
691 aas_area_t *area;
692 aas_face_t *face;
693
694 connectedareas[curarea] = qtrue;
695 area = &aasworld.areas[areanums[curarea]];
696 for (i = 0; i < area->numfaces; i++)
697 {
698 facenum = abs(aasworld.faceindex[area->firstface + i]);
699 face = &aasworld.faces[facenum];
700 //if the face is solid
701 if (face->faceflags & FACE_SOLID) continue;
702 //get the area at the other side of the face
703 if (face->frontarea != areanums[curarea]) otherareanum = face->frontarea;
704 else otherareanum = face->backarea;
705 //check if the face is leading to one of the other areas
706 for (j = 0; j < numareas; j++)
707 {
708 if (areanums[j] == otherareanum) break;
709 } //end for
710 //if the face isn't leading to one of the other areas
711 if (j == numareas) continue;
712 //if the other area is already connected
713 if (connectedareas[j]) continue;
714 //recursively proceed with the other area
715 AAS_ConnectedAreas_r(areanums, numareas, connectedareas, j);
716 } //end for
717 } //end of the function AAS_ConnectedAreas_r
718 //===========================================================================
719 //
720 // Parameter: -
721 // Returns: -
722 // Changes Globals: -
723 //===========================================================================
AAS_ConnectedAreas(int * areanums,int numareas)724 qboolean AAS_ConnectedAreas(int *areanums, int numareas)
725 {
726 int connectedareas[MAX_PORTALAREAS], i;
727
728 Com_Memset(connectedareas, 0, sizeof(connectedareas));
729 if (numareas < 1) return qfalse;
730 if (numareas == 1) return qtrue;
731 AAS_ConnectedAreas_r(areanums, numareas, connectedareas, 0);
732 for (i = 0; i < numareas; i++)
733 {
734 if (!connectedareas[i]) return qfalse;
735 } //end for
736 return qtrue;
737 } //end of the function AAS_ConnectedAreas
738 //===========================================================================
739 // gets adjacent areas with less presence types recursively
740 //
741 // Parameter: -
742 // Returns: -
743 // Changes Globals: -
744 //===========================================================================
AAS_GetAdjacentAreasWithLessPresenceTypes_r(int * areanums,int numareas,int curareanum)745 int AAS_GetAdjacentAreasWithLessPresenceTypes_r(int *areanums, int numareas, int curareanum)
746 {
747 int i, j, presencetype, otherpresencetype, otherareanum, facenum;
748 aas_area_t *area;
749 aas_face_t *face;
750
751 areanums[numareas++] = curareanum;
752 area = &aasworld.areas[curareanum];
753 presencetype = aasworld.areasettings[curareanum].presencetype;
754 for (i = 0; i < area->numfaces; i++)
755 {
756 facenum = abs(aasworld.faceindex[area->firstface + i]);
757 face = &aasworld.faces[facenum];
758 //if the face is solid
759 if (face->faceflags & FACE_SOLID) continue;
760 //the area at the other side of the face
761 if (face->frontarea != curareanum) otherareanum = face->frontarea;
762 else otherareanum = face->backarea;
763 //
764 otherpresencetype = aasworld.areasettings[otherareanum].presencetype;
765 //if the other area has less presence types
766 if ((presencetype & ~otherpresencetype) &&
767 !(otherpresencetype & ~presencetype))
768 {
769 //check if the other area isn't already in the list
770 for (j = 0; j < numareas; j++)
771 {
772 if (otherareanum == areanums[j]) break;
773 } //end for
774 //if the other area isn't already in the list
775 if (j == numareas)
776 {
777 if (numareas >= MAX_PORTALAREAS)
778 {
779 AAS_Error("MAX_PORTALAREAS");
780 return numareas;
781 } //end if
782 numareas = AAS_GetAdjacentAreasWithLessPresenceTypes_r(areanums, numareas, otherareanum);
783 } //end if
784 } //end if
785 } //end for
786 return numareas;
787 } //end of the function AAS_GetAdjacentAreasWithLessPresenceTypes_r
788 //===========================================================================
789 //
790 // Parameter: -
791 // Returns: -
792 // Changes Globals: -
793 //===========================================================================
AAS_CheckAreaForPossiblePortals(int areanum)794 int AAS_CheckAreaForPossiblePortals(int areanum)
795 {
796 int i, j, k, fen, ben, frontedgenum, backedgenum, facenum;
797 int areanums[MAX_PORTALAREAS], numareas, otherareanum;
798 int numareafrontfaces[MAX_PORTALAREAS], numareabackfaces[MAX_PORTALAREAS];
799 int frontfacenums[MAX_PORTALAREAS], backfacenums[MAX_PORTALAREAS];
800 int numfrontfaces, numbackfaces;
801 int frontareanums[MAX_PORTALAREAS], backareanums[MAX_PORTALAREAS];
802 int numfrontareas, numbackareas;
803 int frontplanenum, backplanenum, faceplanenum;
804 aas_area_t *area;
805 aas_face_t *frontface, *backface, *face;
806
807 //if it isn't already a portal
808 if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL) return 0;
809 //it must be a grounded area
810 if (!(aasworld.areasettings[areanum].areaflags & AREA_GROUNDED)) return 0;
811 //
812 Com_Memset(numareafrontfaces, 0, sizeof(numareafrontfaces));
813 Com_Memset(numareabackfaces, 0, sizeof(numareabackfaces));
814 numareas = numfrontfaces = numbackfaces = 0;
815 numfrontareas = numbackareas = 0;
816 frontplanenum = backplanenum = -1;
817 //add any adjacent areas with less presence types
818 numareas = AAS_GetAdjacentAreasWithLessPresenceTypes_r(areanums, 0, areanum);
819 //
820 for (i = 0; i < numareas; i++)
821 {
822 area = &aasworld.areas[areanums[i]];
823 for (j = 0; j < area->numfaces; j++)
824 {
825 facenum = abs(aasworld.faceindex[area->firstface + j]);
826 face = &aasworld.faces[facenum];
827 //if the face is solid
828 if (face->faceflags & FACE_SOLID) continue;
829 //check if the face is shared with one of the other areas
830 for (k = 0; k < numareas; k++)
831 {
832 if (k == i) continue;
833 if (face->frontarea == areanums[k] || face->backarea == areanums[k]) break;
834 } //end for
835 //if the face is shared
836 if (k != numareas) continue;
837 //the number of the area at the other side of the face
838 if (face->frontarea == areanums[i]) otherareanum = face->backarea;
839 else otherareanum = face->frontarea;
840 //if the other area already is a cluter portal
841 if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) return 0;
842 //number of the plane of the area
843 faceplanenum = face->planenum & ~1;
844 //
845 if (frontplanenum < 0 || faceplanenum == frontplanenum)
846 {
847 frontplanenum = faceplanenum;
848 frontfacenums[numfrontfaces++] = facenum;
849 for (k = 0; k < numfrontareas; k++)
850 {
851 if (frontareanums[k] == otherareanum) break;
852 } //end for
853 if (k == numfrontareas) frontareanums[numfrontareas++] = otherareanum;
854 numareafrontfaces[i]++;
855 } //end if
856 else if (backplanenum < 0 || faceplanenum == backplanenum)
857 {
858 backplanenum = faceplanenum;
859 backfacenums[numbackfaces++] = facenum;
860 for (k = 0; k < numbackareas; k++)
861 {
862 if (backareanums[k] == otherareanum) break;
863 } //end for
864 if (k == numbackareas) backareanums[numbackareas++] = otherareanum;
865 numareabackfaces[i]++;
866 } //end else
867 else
868 {
869 return 0;
870 } //end else
871 } //end for
872 } //end for
873 //every area should have at least one front face and one back face
874 for (i = 0; i < numareas; i++)
875 {
876 if (!numareafrontfaces[i] || !numareabackfaces[i]) return 0;
877 } //end for
878 //the front areas should all be connected
879 if (!AAS_ConnectedAreas(frontareanums, numfrontareas)) return 0;
880 //the back areas should all be connected
881 if (!AAS_ConnectedAreas(backareanums, numbackareas)) return 0;
882 //none of the front faces should have a shared edge with a back face
883 for (i = 0; i < numfrontfaces; i++)
884 {
885 frontface = &aasworld.faces[frontfacenums[i]];
886 for (fen = 0; fen < frontface->numedges; fen++)
887 {
888 frontedgenum = abs(aasworld.edgeindex[frontface->firstedge + fen]);
889 for (j = 0; j < numbackfaces; j++)
890 {
891 backface = &aasworld.faces[backfacenums[j]];
892 for (ben = 0; ben < backface->numedges; ben++)
893 {
894 backedgenum = abs(aasworld.edgeindex[backface->firstedge + ben]);
895 if (frontedgenum == backedgenum) break;
896 } //end for
897 if (ben != backface->numedges) break;
898 } //end for
899 if (j != numbackfaces) break;
900 } //end for
901 if (fen != frontface->numedges) break;
902 } //end for
903 if (i != numfrontfaces) return 0;
904 //set the cluster portal contents
905 for (i = 0; i < numareas; i++)
906 {
907 aasworld.areasettings[areanums[i]].contents |= AREACONTENTS_CLUSTERPORTAL;
908 //this area can be used as a route portal
909 aasworld.areasettings[areanums[i]].contents |= AREACONTENTS_ROUTEPORTAL;
910 Log_Write("possible portal: %d\r\n", areanums[i]);
911 } //end for
912 //
913 return numareas;
914 } //end of the function AAS_CheckAreaForPossiblePortals
915 //===========================================================================
916 //
917 // Parameter: -
918 // Returns: -
919 // Changes Globals: -
920 //===========================================================================
AAS_FindPossiblePortals(void)921 void AAS_FindPossiblePortals(void)
922 {
923 int i, numpossibleportals;
924
925 numpossibleportals = 0;
926 for (i = 1; i < aasworld.numareas; i++)
927 {
928 numpossibleportals += AAS_CheckAreaForPossiblePortals(i);
929 } //end for
930 botimport.Print(PRT_MESSAGE, "\r%6d possible portal areas\n", numpossibleportals);
931 } //end of the function AAS_FindPossiblePortals
932 //===========================================================================
933 //
934 // Parameter: -
935 // Returns: -
936 // Changes Globals: -
937 //===========================================================================
AAS_RemoveAllPortals(void)938 void AAS_RemoveAllPortals(void)
939 {
940 int i;
941
942 for (i = 1; i < aasworld.numareas; i++)
943 {
944 aasworld.areasettings[i].contents &= ~AREACONTENTS_CLUSTERPORTAL;
945 } //end for
946 } //end of the function AAS_RemoveAllPortals
947
948 #if 0
949 //===========================================================================
950 //
951 // Parameter: -
952 // Returns: -
953 // Changes Globals: -
954 //===========================================================================
955 void AAS_FloodCluster_r(int areanum, int clusternum)
956 {
957 int i, otherareanum;
958 aas_face_t *face;
959 aas_area_t *area;
960
961 //set cluster mark
962 aasworld.areasettings[areanum].cluster = clusternum;
963 //if the area is a portal
964 //if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL) return;
965 //
966 area = &aasworld.areas[areanum];
967 //use area faces to flood into adjacent areas
968 for (i = 0; i < area->numfaces; i++)
969 {
970 face = &aasworld.faces[abs(aasworld.faceindex[area->firstface + i])];
971 //
972 if (face->frontarea != areanum) otherareanum = face->frontarea;
973 else otherareanum = face->backarea;
974 //if there's no area at the other side
975 if (!otherareanum) continue;
976 //if the area is a portal
977 if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
978 //if the area is already marked
979 if (aasworld.areasettings[otherareanum].cluster) continue;
980 //
981 AAS_FloodCluster_r(otherareanum, clusternum);
982 } //end for
983 //use the reachabilities to flood into other areas
984 for (i = 0; i < aasworld.areasettings[areanum].numreachableareas; i++)
985 {
986 otherareanum = aasworld.reachability[
987 aasworld.areasettings[areanum].firstreachablearea + i].areanum;
988 if (!otherareanum)
989 {
990 continue;
991 AAS_Error("reachability %d has zero area\n", aasworld.areasettings[areanum].firstreachablearea + i);
992 } //end if
993 //if the area is a portal
994 if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
995 //if the area is already marked
996 if (aasworld.areasettings[otherareanum].cluster) continue;
997 //
998 AAS_FloodCluster_r(otherareanum, clusternum);
999 } //end for
1000 } //end of the function AAS_FloodCluster_r
1001 //===========================================================================
1002 //
1003 // Parameter: -
1004 // Returns: -
1005 // Changes Globals: -
1006 //===========================================================================
1007 void AAS_RemoveTeleporterPortals(void)
1008 {
1009 int i, j, areanum;
1010
1011 for (i = 1; i < aasworld.numareas; i++)
1012 {
1013 for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
1014 {
1015 areanum = aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].areanum;
1016 if (aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].traveltype == TRAVEL_TELEPORT)
1017 {
1018 aasworld.areasettings[i].contents &= ~AREACONTENTS_CLUSTERPORTAL;
1019 aasworld.areasettings[areanum].contents &= ~AREACONTENTS_CLUSTERPORTAL;
1020 break;
1021 } //end if
1022 } //end for
1023 } //end for
1024 } //end of the function AAS_RemoveTeleporterPortals
1025 //===========================================================================
1026 //
1027 // Parameter: -
1028 // Returns: -
1029 // Changes Globals: -
1030 //===========================================================================
1031 void AAS_FloodClusterReachabilities(int clusternum)
1032 {
1033 int i, j, areanum;
1034
1035 for (i = 1; i < aasworld.numareas; i++)
1036 {
1037 //if this area already has a cluster set
1038 if (aasworld.areasettings[i].cluster) continue;
1039 //if this area is a cluster portal
1040 if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL) continue;
1041 //loop over the reachable areas from this area
1042 for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
1043 {
1044 //the reachable area
1045 areanum = aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].areanum;
1046 //if this area is a cluster portal
1047 if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
1048 //if this area has a cluster set
1049 if (aasworld.areasettings[areanum].cluster == clusternum)
1050 {
1051 AAS_FloodCluster_r(i, clusternum);
1052 i = 0;
1053 break;
1054 } //end if
1055 } //end for
1056 } //end for
1057 } //end of the function AAS_FloodClusterReachabilities
1058
1059 //===========================================================================
1060 //
1061 // Parameter: -
1062 // Returns: -
1063 // Changes Globals: -
1064 //===========================================================================
1065 void AAS_RemoveNotClusterClosingPortals(void)
1066 {
1067 int i, j, k, facenum, otherareanum, nonclosingportals;
1068 aas_area_t *area;
1069 aas_face_t *face;
1070
1071 AAS_RemoveTeleporterPortals();
1072 //
1073 nonclosingportals = 0;
1074 for (i = 1; i < aasworld.numareas; i++)
1075 {
1076 if (!(aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)) continue;
1077 //find a non-portal area adjacent to the portal area and flood
1078 //the cluster from there
1079 area = &aasworld.areas[i];
1080 for (j = 0; j < area->numfaces; j++)
1081 {
1082 facenum = abs(aasworld.faceindex[area->firstface + j]);
1083 face = &aasworld.faces[facenum];
1084 //
1085 if (face->frontarea != i) otherareanum = face->frontarea;
1086 else otherareanum = face->backarea;
1087 //
1088 if (!otherareanum) continue;
1089 //
1090 if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL)
1091 {
1092 continue;
1093 } //end if
1094 //reset all cluster fields
1095 AAS_RemoveClusterAreas();
1096 //
1097 AAS_FloodCluster_r(otherareanum, 1);
1098 AAS_FloodClusterReachabilities(1);
1099 //check if all adjacent non-portal areas have a cluster set
1100 for (k = 0; k < area->numfaces; k++)
1101 {
1102 facenum = abs(aasworld.faceindex[area->firstface + k]);
1103 face = &aasworld.faces[facenum];
1104 //
1105 if (face->frontarea != i) otherareanum = face->frontarea;
1106 else otherareanum = face->backarea;
1107 //
1108 if (!otherareanum) continue;
1109 //
1110 if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL)
1111 {
1112 continue;
1113 } //end if
1114 //
1115 if (!aasworld.areasettings[otherareanum].cluster) break;
1116 } //end for
1117 //if all adjacent non-portal areas have a cluster set then the portal
1118 //didn't seal a cluster
1119 if (k >= area->numfaces)
1120 {
1121 aasworld.areasettings[i].contents &= ~AREACONTENTS_CLUSTERPORTAL;
1122 nonclosingportals++;
1123 //recheck all the other portals again
1124 i = 0;
1125 break;
1126 } //end if
1127 } //end for
1128 } //end for
1129 botimport.Print(PRT_MESSAGE, "\r%6d non closing portals removed\n", nonclosingportals);
1130 } //end of the function AAS_RemoveNotClusterClosingPortals
1131
1132 //===========================================================================
1133 //
1134 // Parameter: -
1135 // Returns: -
1136 // Changes Globals: -
1137 //===========================================================================
1138
1139 void AAS_RemoveNotClusterClosingPortals(void)
1140 {
1141 int i, j, facenum, otherareanum, nonclosingportals, numseperatedclusters;
1142 aas_area_t *area;
1143 aas_face_t *face;
1144
1145 AAS_RemoveTeleporterPortals();
1146 //
1147 nonclosingportals = 0;
1148 for (i = 1; i < aasworld.numareas; i++)
1149 {
1150 if (!(aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)) continue;
1151 //
1152 numseperatedclusters = 0;
1153 //reset all cluster fields
1154 AAS_RemoveClusterAreas();
1155 //find a non-portal area adjacent to the portal area and flood
1156 //the cluster from there
1157 area = &aasworld.areas[i];
1158 for (j = 0; j < area->numfaces; j++)
1159 {
1160 facenum = abs(aasworld.faceindex[area->firstface + j]);
1161 face = &aasworld.faces[facenum];
1162 //
1163 if (face->frontarea != i) otherareanum = face->frontarea;
1164 else otherareanum = face->backarea;
1165 //if not solid at the other side of the face
1166 if (!otherareanum) continue;
1167 //don't flood into other portals
1168 if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
1169 //if the area already has a cluster set
1170 if (aasworld.areasettings[otherareanum].cluster) continue;
1171 //another cluster is seperated by this portal
1172 numseperatedclusters++;
1173 //flood the cluster
1174 AAS_FloodCluster_r(otherareanum, numseperatedclusters);
1175 AAS_FloodClusterReachabilities(numseperatedclusters);
1176 } //end for
1177 //use the reachabilities to flood into other areas
1178 for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
1179 {
1180 otherareanum = aasworld.reachability[
1181 aasworld.areasettings[i].firstreachablearea + j].areanum;
1182 //this should never be qtrue but we check anyway
1183 if (!otherareanum) continue;
1184 //don't flood into other portals
1185 if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
1186 //if the area already has a cluster set
1187 if (aasworld.areasettings[otherareanum].cluster) continue;
1188 //another cluster is seperated by this portal
1189 numseperatedclusters++;
1190 //flood the cluster
1191 AAS_FloodCluster_r(otherareanum, numseperatedclusters);
1192 AAS_FloodClusterReachabilities(numseperatedclusters);
1193 } //end for
1194 //a portal must seperate no more and no less than 2 clusters
1195 if (numseperatedclusters != 2)
1196 {
1197 aasworld.areasettings[i].contents &= ~AREACONTENTS_CLUSTERPORTAL;
1198 nonclosingportals++;
1199 //recheck all the other portals again
1200 i = 0;
1201 } //end if
1202 } //end for
1203 botimport.Print(PRT_MESSAGE, "\r%6d non closing portals removed\n", nonclosingportals);
1204 } //end of the function AAS_RemoveNotClusterClosingPortals
1205
1206 //===========================================================================
1207 //
1208 // Parameter: -
1209 // Returns: -
1210 // Changes Globals: -
1211 //===========================================================================
1212
1213 void AAS_AddTeleporterPortals(void)
1214 {
1215 int j, area2num, facenum, otherareanum;
1216 char *target, *targetname, *classname;
1217 bsp_entity_t *entities, *ent, *dest;
1218 vec3_t origin, destorigin, mins, maxs, end;
1219 vec3_t bbmins, bbmaxs;
1220 aas_area_t *area;
1221 aas_face_t *face;
1222 aas_trace_t trace;
1223 aas_link_t *areas, *link;
1224
1225 entities = AAS_ParseBSPEntities();
1226
1227 for (ent = entities; ent; ent = ent->next)
1228 {
1229 classname = AAS_ValueForBSPEpairKey(ent, "classname");
1230 if (classname && !strcmp(classname, "misc_teleporter"))
1231 {
1232 if (!AAS_VectorForBSPEpairKey(ent, "origin", origin))
1233 {
1234 botimport.Print(PRT_ERROR, "teleporter (%s) without origin\n", target);
1235 continue;
1236 } //end if
1237 //
1238 target = AAS_ValueForBSPEpairKey(ent, "target");
1239 if (!target)
1240 {
1241 botimport.Print(PRT_ERROR, "teleporter (%s) without target\n", target);
1242 continue;
1243 } //end if
1244 for (dest = entities; dest; dest = dest->next)
1245 {
1246 classname = AAS_ValueForBSPEpairKey(dest, "classname");
1247 if (classname && !strcmp(classname, "misc_teleporter_dest"))
1248 {
1249 targetname = AAS_ValueForBSPEpairKey(dest, "targetname");
1250 if (targetname && !strcmp(targetname, target))
1251 {
1252 break;
1253 } //end if
1254 } //end if
1255 } //end for
1256 if (!dest)
1257 {
1258 botimport.Print(PRT_ERROR, "teleporter without destination (%s)\n", target);
1259 continue;
1260 } //end if
1261 if (!AAS_VectorForBSPEpairKey(dest, "origin", destorigin))
1262 {
1263 botimport.Print(PRT_ERROR, "teleporter destination (%s) without origin\n", target);
1264 continue;
1265 } //end if
1266 destorigin[2] += 24; //just for q2e1m2, the dork has put the telepads in the ground
1267 VectorCopy(destorigin, end);
1268 end[2] -= 100;
1269 trace = AAS_TraceClientBBox(destorigin, end, PRESENCE_CROUCH, -1);
1270 if (trace.startsolid)
1271 {
1272 botimport.Print(PRT_ERROR, "teleporter destination (%s) in solid\n", target);
1273 continue;
1274 } //end if
1275 VectorCopy(trace.endpos, destorigin);
1276 area2num = AAS_PointAreaNum(destorigin);
1277 //reset all cluster fields
1278 for (j = 0; j < aasworld.numareas; j++)
1279 {
1280 aasworld.areasettings[j].cluster = 0;
1281 } //end for
1282 //
1283 VectorSet(mins, -8, -8, 8);
1284 VectorSet(maxs, 8, 8, 24);
1285 //
1286 AAS_PresenceTypeBoundingBox(PRESENCE_CROUCH, bbmins, bbmaxs);
1287 //
1288 VectorAdd(origin, mins, mins);
1289 VectorAdd(origin, maxs, maxs);
1290 //add bounding box size
1291 VectorSubtract(mins, bbmaxs, mins);
1292 VectorSubtract(maxs, bbmins, maxs);
1293 //link an invalid (-1) entity
1294 areas = AAS_AASLinkEntity(mins, maxs, -1);
1295 //
1296 for (link = areas; link; link = link->next_area)
1297 {
1298 if (!AAS_AreaGrounded(link->areanum)) continue;
1299 //add the teleporter portal mark
1300 aasworld.areasettings[link->areanum].contents |= AREACONTENTS_CLUSTERPORTAL |
1301 AREACONTENTS_TELEPORTAL;
1302 } //end for
1303 //
1304 for (link = areas; link; link = link->next_area)
1305 {
1306 if (!AAS_AreaGrounded(link->areanum)) continue;
1307 //find a non-portal area adjacent to the portal area and flood
1308 //the cluster from there
1309 area = &aasworld.areas[link->areanum];
1310 for (j = 0; j < area->numfaces; j++)
1311 {
1312 facenum = abs(aasworld.faceindex[area->firstface + j]);
1313 face = &aasworld.faces[facenum];
1314 //
1315 if (face->frontarea != link->areanum) otherareanum = face->frontarea;
1316 else otherareanum = face->backarea;
1317 //
1318 if (!otherareanum) continue;
1319 //
1320 if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL)
1321 {
1322 continue;
1323 } //end if
1324 //
1325 AAS_FloodCluster_r(otherareanum, 1);
1326 } //end for
1327 } //end for
1328 //if the teleport destination IS in the same cluster
1329 if (aasworld.areasettings[area2num].cluster)
1330 {
1331 for (link = areas; link; link = link->next_area)
1332 {
1333 if (!AAS_AreaGrounded(link->areanum)) continue;
1334 //add the teleporter portal mark
1335 aasworld.areasettings[link->areanum].contents &= ~(AREACONTENTS_CLUSTERPORTAL |
1336 AREACONTENTS_TELEPORTAL);
1337 } //end for
1338 } //end if
1339 } //end if
1340 } //end for
1341 AAS_FreeBSPEntities(entities);
1342 } //end of the function AAS_AddTeleporterPortals
1343
1344 //===========================================================================
1345 //
1346 // Parameter: -
1347 // Returns: -
1348 // Changes Globals: -
1349 //===========================================================================
1350 void AAS_AddTeleporterPortals(void)
1351 {
1352 int i, j, areanum;
1353
1354 for (i = 1; i < aasworld.numareas; i++)
1355 {
1356 for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
1357 {
1358 if (aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].traveltype != TRAVEL_TELEPORT) continue;
1359 areanum = aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].areanum;
1360 aasworld.areasettings[areanum].contents |= AREACONTENTS_CLUSTERPORTAL;
1361 } //end for
1362 } //end for
1363 } //end of the function AAS_AddTeleporterPortals
1364
1365 #endif
1366
1367 //===========================================================================
1368 //
1369 // Parameter: -
1370 // Returns: -
1371 // Changes Globals: -
1372 //===========================================================================
AAS_TestPortals(void)1373 int AAS_TestPortals(void)
1374 {
1375 int i;
1376 aas_portal_t *portal;
1377
1378 for (i = 1; i < aasworld.numportals; i++)
1379 {
1380 portal = &aasworld.portals[i];
1381 if (!portal->frontcluster)
1382 {
1383 aasworld.areasettings[portal->areanum].contents &= ~AREACONTENTS_CLUSTERPORTAL;
1384 Log_Write("portal area %d has no front cluster\r\n", portal->areanum);
1385 return qfalse;
1386 } //end if
1387 if (!portal->backcluster)
1388 {
1389 aasworld.areasettings[portal->areanum].contents &= ~AREACONTENTS_CLUSTERPORTAL;
1390 Log_Write("portal area %d has no back cluster\r\n", portal->areanum);
1391 return qfalse;
1392 } //end if
1393 } //end for
1394 return qtrue;
1395 } //end of the function
1396 //===========================================================================
1397 //
1398 // Parameter: -
1399 // Returns: -
1400 // Changes Globals: -
1401 //===========================================================================
AAS_CountForcedClusterPortals(void)1402 void AAS_CountForcedClusterPortals(void)
1403 {
1404 int num, i;
1405
1406 num = 0;
1407 for (i = 1; i < aasworld.numareas; i++)
1408 {
1409 if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)
1410 {
1411 Log_Write("area %d is a forced portal area\r\n", i);
1412 num++;
1413 } //end if
1414 } //end for
1415 botimport.Print(PRT_MESSAGE, "%6d forced portal areas\n", num);
1416 } //end of the function AAS_CountForcedClusterPortals
1417 //===========================================================================
1418 //
1419 // Parameter: -
1420 // Returns: -
1421 // Changes Globals: -
1422 //===========================================================================
AAS_CreateViewPortals(void)1423 void AAS_CreateViewPortals(void)
1424 {
1425 int i;
1426
1427 for (i = 1; i < aasworld.numareas; i++)
1428 {
1429 if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)
1430 {
1431 aasworld.areasettings[i].contents |= AREACONTENTS_VIEWPORTAL;
1432 } //end if
1433 } //end for
1434 } //end of the function AAS_CreateViewPortals
1435 //===========================================================================
1436 //
1437 // Parameter: -
1438 // Returns: -
1439 // Changes Globals: -
1440 //===========================================================================
AAS_SetViewPortalsAsClusterPortals(void)1441 void AAS_SetViewPortalsAsClusterPortals(void)
1442 {
1443 int i;
1444
1445 for (i = 1; i < aasworld.numareas; i++)
1446 {
1447 if (aasworld.areasettings[i].contents & AREACONTENTS_VIEWPORTAL)
1448 {
1449 aasworld.areasettings[i].contents |= AREACONTENTS_CLUSTERPORTAL;
1450 } //end if
1451 } //end for
1452 } //end of the function AAS_SetViewPortalsAsClusterPortals
1453 //===========================================================================
1454 //
1455 // Parameter: -
1456 // Returns: -
1457 // Changes Globals: -
1458 //===========================================================================
AAS_InitClustering(void)1459 void AAS_InitClustering(void)
1460 {
1461 int i, removedPortalAreas;
1462 int n, total, numreachabilityareas;
1463
1464 if (!aasworld.loaded) return;
1465 //if there are clusters
1466 if (aasworld.numclusters >= 1)
1467 {
1468 #ifndef BSPC
1469 //if clustering isn't forced
1470 if (!((int)LibVarGetValue("forceclustering")) &&
1471 !((int)LibVarGetValue("forcereachability"))) return;
1472 #endif
1473 } //end if
1474 //set all view portals as cluster portals in case we re-calculate the reachabilities and clusters (with -reach)
1475 AAS_SetViewPortalsAsClusterPortals();
1476 //count the number of forced cluster portals
1477 AAS_CountForcedClusterPortals();
1478 //remove all area cluster marks
1479 AAS_RemoveClusterAreas();
1480 //find possible cluster portals
1481 AAS_FindPossiblePortals();
1482 //craete portals to for the bot view
1483 AAS_CreateViewPortals();
1484 //remove all portals that are not closing a cluster
1485 //AAS_RemoveNotClusterClosingPortals();
1486 //initialize portal memory
1487 if (aasworld.portals) FreeMemory(aasworld.portals);
1488 aasworld.portals = (aas_portal_t *) GetClearedMemory(AAS_MAX_PORTALS * sizeof(aas_portal_t));
1489 //initialize portal index memory
1490 if (aasworld.portalindex) FreeMemory(aasworld.portalindex);
1491 aasworld.portalindex = (aas_portalindex_t *) GetClearedMemory(AAS_MAX_PORTALINDEXSIZE * sizeof(aas_portalindex_t));
1492 //initialize cluster memory
1493 if (aasworld.clusters) FreeMemory(aasworld.clusters);
1494 aasworld.clusters = (aas_cluster_t *) GetClearedMemory(AAS_MAX_CLUSTERS * sizeof(aas_cluster_t));
1495 //
1496 removedPortalAreas = 0;
1497 botimport.Print(PRT_MESSAGE, "\r%6d removed portal areas", removedPortalAreas);
1498 while(1)
1499 {
1500 botimport.Print(PRT_MESSAGE, "\r%6d", removedPortalAreas);
1501 //initialize the number of portals and clusters
1502 aasworld.numportals = 1; //portal 0 is a dummy
1503 aasworld.portalindexsize = 0;
1504 aasworld.numclusters = 1; //cluster 0 is a dummy
1505 //create the portals from the portal areas
1506 AAS_CreatePortals();
1507 //
1508 removedPortalAreas++;
1509 //find the clusters
1510 if (!AAS_FindClusters())
1511 continue;
1512 //test the portals
1513 if (!AAS_TestPortals())
1514 continue;
1515 //
1516 break;
1517 } //end while
1518 botimport.Print(PRT_MESSAGE, "\n");
1519 //the AAS file should be saved
1520 aasworld.savefile = qtrue;
1521 //write the portal areas to the log file
1522 for (i = 1; i < aasworld.numportals; i++)
1523 {
1524 Log_Write("portal %d: area %d\r\n", i, aasworld.portals[i].areanum);
1525 } //end for
1526 // report cluster info
1527 botimport.Print(PRT_MESSAGE, "%6d portals created\n", aasworld.numportals);
1528 botimport.Print(PRT_MESSAGE, "%6d clusters created\n", aasworld.numclusters);
1529 for (i = 1; i < aasworld.numclusters; i++)
1530 {
1531 botimport.Print(PRT_MESSAGE, "cluster %d has %d reachability areas\n", i,
1532 aasworld.clusters[i].numreachabilityareas);
1533 } //end for
1534 // report AAS file efficiency
1535 numreachabilityareas = 0;
1536 total = 0;
1537 for (i = 0; i < aasworld.numclusters; i++) {
1538 n = aasworld.clusters[i].numreachabilityareas;
1539 numreachabilityareas += n;
1540 total += n * n;
1541 }
1542 total += numreachabilityareas * aasworld.numportals;
1543 //
1544 botimport.Print(PRT_MESSAGE, "%6i total reachability areas\n", numreachabilityareas);
1545 botimport.Print(PRT_MESSAGE, "%6i AAS memory/CPU usage (the lower the better)\n", total * 3);
1546 } //end of the function AAS_InitClustering
1547