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 #include "be_aas_cluster.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