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