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_routealt.c
25 *
26 * desc: AAS
27 *
28 * $Archive: /MissionPack/code/botlib/be_aas_routealt.c $
29 *
30 *****************************************************************************/
31
32 #include "../qcommon/q_shared.h"
33 #include "l_utils.h"
34 #include "l_memory.h"
35 #include "l_log.h"
36 #include "l_script.h"
37 #include "l_precomp.h"
38 #include "l_struct.h"
39 #include "aasfile.h"
40 #include "botlib.h"
41 #include "be_aas.h"
42 #include "be_aas_funcs.h"
43 #include "be_interface.h"
44 #include "be_aas_def.h"
45
46 #define ENABLE_ALTROUTING
47 //#define ALTROUTE_DEBUG
48
49 typedef struct midrangearea_s
50 {
51 int valid;
52 unsigned short starttime;
53 unsigned short goaltime;
54 } midrangearea_t;
55
56 midrangearea_t *midrangeareas;
57 int *clusterareas;
58 int numclusterareas;
59
60 //===========================================================================
61 //
62 // Parameter: -
63 // Returns: -
64 // Changes Globals: -
65 //===========================================================================
AAS_AltRoutingFloodCluster_r(int areanum)66 void AAS_AltRoutingFloodCluster_r(int areanum)
67 {
68 int i, otherareanum;
69 aas_area_t *area;
70 aas_face_t *face;
71
72 //add the current area to the areas of the current cluster
73 clusterareas[numclusterareas] = areanum;
74 numclusterareas++;
75 //remove the area from the mid range areas
76 midrangeareas[areanum].valid = qfalse;
77 //flood to other areas through the faces of this area
78 area = &aasworld.areas[areanum];
79 for (i = 0; i < area->numfaces; i++)
80 {
81 face = &aasworld.faces[abs(aasworld.faceindex[area->firstface + i])];
82 //get the area at the other side of the face
83 if (face->frontarea == areanum) otherareanum = face->backarea;
84 else otherareanum = face->frontarea;
85 //if there is an area at the other side of this face
86 if (!otherareanum) continue;
87 //if the other area is not a midrange area
88 if (!midrangeareas[otherareanum].valid) continue;
89 //
90 AAS_AltRoutingFloodCluster_r(otherareanum);
91 } //end for
92 } //end of the function AAS_AltRoutingFloodCluster_r
93 //===========================================================================
94 //
95 // Parameter: -
96 // Returns: -
97 // Changes Globals: -
98 //===========================================================================
AAS_AlternativeRouteGoals(vec3_t start,int startareanum,vec3_t goal,int goalareanum,int travelflags,aas_altroutegoal_t * altroutegoals,int maxaltroutegoals,int type)99 int AAS_AlternativeRouteGoals(vec3_t start, int startareanum, vec3_t goal, int goalareanum, int travelflags,
100 aas_altroutegoal_t *altroutegoals, int maxaltroutegoals,
101 int type)
102 {
103 #ifndef ENABLE_ALTROUTING
104 return 0;
105 #else
106 int i, j, bestareanum;
107 int numaltroutegoals, nummidrangeareas;
108 int starttime, goaltime, goaltraveltime;
109 float dist, bestdist;
110 vec3_t mid, dir;
111 #ifdef ALTROUTE_DEBUG
112 int startmillisecs;
113
114 startmillisecs = Sys_MilliSeconds();
115 #endif
116
117 if (!startareanum || !goalareanum)
118 return 0;
119 //travel time towards the goal area
120 goaltraveltime = AAS_AreaTravelTimeToGoalArea(startareanum, start, goalareanum, travelflags);
121 //clear the midrange areas
122 Com_Memset(midrangeareas, 0, aasworld.numareas * sizeof(midrangearea_t));
123 numaltroutegoals = 0;
124 //
125 nummidrangeareas = 0;
126 //
127 for (i = 1; i < aasworld.numareas; i++)
128 {
129 //
130 if (!(type & ALTROUTEGOAL_ALL))
131 {
132 if (!(type & ALTROUTEGOAL_CLUSTERPORTALS && (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)))
133 {
134 if (!(type & ALTROUTEGOAL_VIEWPORTALS && (aasworld.areasettings[i].contents & AREACONTENTS_VIEWPORTAL)))
135 {
136 continue;
137 } //end if
138 } //end if
139 } //end if
140 //if the area has no reachabilities
141 if (!AAS_AreaReachability(i)) continue;
142 //tavel time from the area to the start area
143 starttime = AAS_AreaTravelTimeToGoalArea(startareanum, start, i, travelflags);
144 if (!starttime) continue;
145 //if the travel time from the start to the area is greater than the shortest goal travel time
146 if (starttime > (float) 1.1 * goaltraveltime) continue;
147 //travel time from the area to the goal area
148 goaltime = AAS_AreaTravelTimeToGoalArea(i, NULL, goalareanum, travelflags);
149 if (!goaltime) continue;
150 //if the travel time from the area to the goal is greater than the shortest goal travel time
151 if (goaltime > (float) 0.8 * goaltraveltime) continue;
152 //this is a mid range area
153 midrangeareas[i].valid = qtrue;
154 midrangeareas[i].starttime = starttime;
155 midrangeareas[i].goaltime = goaltime;
156 Log_Write("%d midrange area %d", nummidrangeareas, i);
157 nummidrangeareas++;
158 } //end for
159 //
160 for (i = 1; i < aasworld.numareas; i++)
161 {
162 if (!midrangeareas[i].valid) continue;
163 //get the areas in one cluster
164 numclusterareas = 0;
165 AAS_AltRoutingFloodCluster_r(i);
166 //now we've got a cluster with areas through which an alternative route could go
167 //get the 'center' of the cluster
168 VectorClear(mid);
169 for (j = 0; j < numclusterareas; j++)
170 {
171 VectorAdd(mid, aasworld.areas[clusterareas[j]].center, mid);
172 } //end for
173 VectorScale(mid, 1.0 / numclusterareas, mid);
174 //get the area closest to the center of the cluster
175 bestdist = 999999;
176 bestareanum = 0;
177 for (j = 0; j < numclusterareas; j++)
178 {
179 VectorSubtract(mid, aasworld.areas[clusterareas[j]].center, dir);
180 dist = VectorLength(dir);
181 if (dist < bestdist)
182 {
183 bestdist = dist;
184 bestareanum = clusterareas[j];
185 } //end if
186 } //end for
187 //now we've got an area for an alternative route
188 //FIXME: add alternative goal origin
189 VectorCopy(aasworld.areas[bestareanum].center, altroutegoals[numaltroutegoals].origin);
190 altroutegoals[numaltroutegoals].areanum = bestareanum;
191 altroutegoals[numaltroutegoals].starttraveltime = midrangeareas[bestareanum].starttime;
192 altroutegoals[numaltroutegoals].goaltraveltime = midrangeareas[bestareanum].goaltime;
193 altroutegoals[numaltroutegoals].extratraveltime =
194 (midrangeareas[bestareanum].starttime + midrangeareas[bestareanum].goaltime) -
195 goaltraveltime;
196 numaltroutegoals++;
197 //
198 #ifdef ALTROUTE_DEBUG
199 AAS_ShowAreaPolygons(bestareanum, 1, qtrue);
200 #endif
201 //don't return more than the maximum alternative route goals
202 if (numaltroutegoals >= maxaltroutegoals) break;
203 } //end for
204 #ifdef ALTROUTE_DEBUG
205 botimport.Print(PRT_MESSAGE, "alternative route goals in %d msec\n", Sys_MilliSeconds() - startmillisecs);
206 #endif
207 return numaltroutegoals;
208 #endif
209 } //end of the function AAS_AlternativeRouteGoals
210 //===========================================================================
211 //
212 // Parameter: -
213 // Returns: -
214 // Changes Globals: -
215 //===========================================================================
AAS_InitAlternativeRouting(void)216 void AAS_InitAlternativeRouting(void)
217 {
218 #ifdef ENABLE_ALTROUTING
219 if (midrangeareas) FreeMemory(midrangeareas);
220 midrangeareas = (midrangearea_t *) GetMemory(aasworld.numareas * sizeof(midrangearea_t));
221 if (clusterareas) FreeMemory(clusterareas);
222 clusterareas = (int *) GetMemory(aasworld.numareas * sizeof(int));
223 #endif
224 } //end of the function AAS_InitAlternativeRouting
225 //===========================================================================
226 //
227 // Parameter: -
228 // Returns: -
229 // Changes Globals: -
230 //===========================================================================
AAS_ShutdownAlternativeRouting(void)231 void AAS_ShutdownAlternativeRouting(void)
232 {
233 #ifdef ENABLE_ALTROUTING
234 if (midrangeareas) FreeMemory(midrangeareas);
235 midrangeareas = NULL;
236 if (clusterareas) FreeMemory(clusterareas);
237 clusterareas = NULL;
238 numclusterareas = 0;
239 #endif
240 } //end of the function AAS_ShutdownAlternativeRouting
241