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