1 /*
2 ===========================================================================
3
4 Return to Castle Wolfenstein single player GPL Source Code
5 Copyright (C) 1999-2010 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Return to Castle Wolfenstein single player GPL Source Code (“RTCW SP Source Code”).
8
9 RTCW SP Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 RTCW SP Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with RTCW SP Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the RTCW SP Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the RTCW SP Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29
30 /*****************************************************************************
31 * name: be_aas_routealt.c
32 *
33 * desc: AAS
34 *
35 *
36 *****************************************************************************/
37
38 #include "../qcommon/q_shared.h"
39 #include "l_utils.h"
40 #include "l_memory.h"
41 #include "l_log.h"
42 #include "l_script.h"
43 #include "l_precomp.h"
44 #include "l_struct.h"
45 #include "aasfile.h"
46 #include "botlib.h"
47 #include "be_aas.h"
48 #include "be_aas_funcs.h"
49 #include "be_interface.h"
50 #include "be_aas_def.h"
51
52 //#define ENABLE_ALTROUTING
53
54 typedef struct midrangearea_s
55 {
56 int valid;
57 unsigned short starttime;
58 unsigned short goaltime;
59 } midrangearea_t;
60
61 midrangearea_t *midrangeareas;
62 int *clusterareas;
63 int numclusterareas;
64
65 //===========================================================================
66 //
67 // Parameter: -
68 // Returns: -
69 // Changes Globals: -
70 //===========================================================================
AAS_AltRoutingFloodCluster_r(int areanum)71 void AAS_AltRoutingFloodCluster_r( int areanum ) {
72 int i, otherareanum;
73 aas_area_t *area;
74 aas_face_t *face;
75
76 //add the current area to the areas of the current cluster
77 clusterareas[numclusterareas] = areanum;
78 numclusterareas++;
79 //remove the area from the mid range areas
80 midrangeareas[areanum].valid = qfalse;
81 //flood to other areas through the faces of this area
82 area = &( *aasworld ).areas[areanum];
83 for ( i = 0; i < area->numfaces; i++ )
84 {
85 face = &( *aasworld ).faces[abs( ( *aasworld ).faceindex[area->firstface + i] )];
86 //get the area at the other side of the face
87 if ( face->frontarea == areanum ) {
88 otherareanum = face->backarea;
89 } else { otherareanum = face->frontarea;}
90 //if there is an area at the other side of this face
91 if ( !otherareanum ) {
92 continue;
93 }
94 //if the other area is not a midrange area
95 if ( !midrangeareas[otherareanum].valid ) {
96 continue;
97 }
98 //
99 AAS_AltRoutingFloodCluster_r( otherareanum );
100 } //end for
101 } //end of the function AAS_AltRoutingFloodCluster_r
102 //===========================================================================
103 //
104 // Parameter: -
105 // Returns: -
106 // Changes Globals: -
107 //===========================================================================
AAS_AlternativeRouteGoals(vec3_t start,vec3_t goal,int travelflags,aas_altroutegoal_t * altroutegoals,int maxaltroutegoals,int color)108 int AAS_AlternativeRouteGoals( vec3_t start, vec3_t goal, int travelflags,
109 aas_altroutegoal_t *altroutegoals, int maxaltroutegoals,
110 int color ) {
111 #ifndef ENABLE_ALTROUTING
112 return 0;
113 #else
114 int i, j, startareanum, goalareanum, bestareanum;
115 int numaltroutegoals, nummidrangeareas;
116 int starttime, goaltime, goaltraveltime;
117 float dist, bestdist;
118 vec3_t mid, dir;
119 #ifdef DEBUG
120 int startmillisecs;
121
122 startmillisecs = Sys_MilliSeconds();
123 #endif
124
125 startareanum = AAS_PointAreaNum( start );
126 if ( !startareanum ) {
127 return 0;
128 }
129 goalareanum = AAS_PointAreaNum( goal );
130 if ( !goalareanum ) {
131 return 0;
132 }
133 //travel time towards the goal area
134 goaltraveltime = AAS_AreaTravelTimeToGoalArea( startareanum, start, goalareanum, travelflags );
135 //clear the midrange areas
136 memset( midrangeareas, 0, ( *aasworld ).numareas * sizeof( midrangearea_t ) );
137 numaltroutegoals = 0;
138 //
139 nummidrangeareas = 0;
140 //
141 for ( i = 1; i < ( *aasworld ).numareas; i++ )
142 {
143 //
144 if ( !( ( *aasworld ).areasettings[i].contents & AREACONTENTS_ROUTEPORTAL ) ) {
145 continue;
146 }
147 //if the area has no reachabilities
148 if ( !AAS_AreaReachability( i ) ) {
149 continue;
150 }
151 //tavel time from the area to the start area
152 starttime = AAS_AreaTravelTimeToGoalArea( startareanum, start, i, travelflags );
153 if ( !starttime ) {
154 continue;
155 }
156 //if the travel time from the start to the area is greater than the shortest goal travel time
157 if ( starttime > 1.5 * goaltraveltime ) {
158 continue;
159 }
160 //travel time from the area to the goal area
161 goaltime = AAS_AreaTravelTimeToGoalArea( i, NULL, goalareanum, travelflags );
162 if ( !goaltime ) {
163 continue;
164 }
165 //if the travel time from the area to the goal is greater than the shortest goal travel time
166 if ( goaltime > 1.5 * goaltraveltime ) {
167 continue;
168 }
169 //this is a mid range area
170 midrangeareas[i].valid = qtrue;
171 midrangeareas[i].starttime = starttime;
172 midrangeareas[i].goaltime = goaltime;
173 Log_Write( "%d midrange area %d", nummidrangeareas, i );
174 nummidrangeareas++;
175 } //end for
176 //
177 for ( i = 1; i < ( *aasworld ).numareas; i++ )
178 {
179 if ( !midrangeareas[i].valid ) {
180 continue;
181 }
182 //get the areas in one cluster
183 numclusterareas = 0;
184 AAS_AltRoutingFloodCluster_r( i );
185 //now we've got a cluster with areas through which an alternative route could go
186 //get the 'center' of the cluster
187 VectorClear( mid );
188 for ( j = 0; j < numclusterareas; j++ )
189 {
190 VectorAdd( mid, ( *aasworld ).areas[clusterareas[j]].center, mid );
191 } //end for
192 VectorScale( mid, 1.0 / numclusterareas, mid );
193 //get the area closest to the center of the cluster
194 bestdist = 999999;
195 bestareanum = 0;
196 for ( j = 0; j < numclusterareas; j++ )
197 {
198 VectorSubtract( mid, ( *aasworld ).areas[clusterareas[j]].center, dir );
199 dist = VectorLength( dir );
200 if ( dist < bestdist ) {
201 bestdist = dist;
202 bestareanum = clusterareas[j];
203 } //end if
204 } //end for
205 //now we've got an area for an alternative route
206 //FIXME: add alternative goal origin
207 VectorCopy( ( *aasworld ).areas[bestareanum].center, altroutegoals[numaltroutegoals].origin );
208 altroutegoals[numaltroutegoals].areanum = bestareanum;
209 altroutegoals[numaltroutegoals].starttraveltime = midrangeareas[bestareanum].starttime;
210 altroutegoals[numaltroutegoals].goaltraveltime = midrangeareas[bestareanum].goaltime;
211 altroutegoals[numaltroutegoals].extratraveltime =
212 ( midrangeareas[bestareanum].starttime + midrangeareas[bestareanum].goaltime ) -
213 goaltraveltime;
214 numaltroutegoals++;
215 //
216 #ifdef DEBUG
217 botimport.Print( PRT_MESSAGE, "alternative route goal area %d, numclusterareas = %d\n", bestareanum, numclusterareas );
218 if ( color ) {
219 AAS_DrawPermanentCross( ( *aasworld ).areas[bestareanum].center, 10, color );
220 } //end if
221 //AAS_ShowArea(bestarea, qtrue);
222 #endif
223 //don't return more than the maximum alternative route goals
224 if ( numaltroutegoals >= maxaltroutegoals ) {
225 break;
226 }
227 } //end for
228 botimport.Print( PRT_MESSAGE, "%d alternative route goals\n", numaltroutegoals );
229 #ifdef DEBUG
230 botimport.Print( PRT_MESSAGE, "alternative route goals in %d msec\n", Sys_MilliSeconds() - startmillisecs );
231 #endif
232 return numaltroutegoals;
233 #endif
234 } //end of the function AAS_AlternativeRouteGoals
235 //===========================================================================
236 //
237 // Parameter: -
238 // Returns: -
239 // Changes Globals: -
240 //===========================================================================
AAS_InitAlternativeRouting(void)241 void AAS_InitAlternativeRouting( void ) {
242 #ifdef ENABLE_ALTROUTING
243 if ( midrangeareas ) {
244 FreeMemory( midrangeareas );
245 }
246 midrangeareas = (midrangearea_t *) GetMemory( ( *aasworld ).numareas * sizeof( midrangearea_t ) );
247 if ( clusterareas ) {
248 FreeMemory( clusterareas );
249 }
250 clusterareas = (int *) GetMemory( aasworld.numareas * sizeof( int ) );
251 #endif
252 } //end of the function AAS_InitAlternativeRouting
253 //===========================================================================
254 //
255 // Parameter: -
256 // Returns: -
257 // Changes Globals: -
258 //===========================================================================
AAS_ShutdownAlternativeRouting(void)259 void AAS_ShutdownAlternativeRouting( void ) {
260 #ifdef ENABLE_ALTROUTING
261 if ( midrangeareas ) {
262 FreeMemory( midrangeareas );
263 }
264 midrangeareas = NULL;
265 if ( clusterareas ) {
266 FreeMemory( clusterareas );
267 }
268 clusterareas = NULL;
269 numclusterareas = 0;
270 #endif
271 }
272