← Back to branch summary

~ubuntu-branches/ubuntu/precise/openarena/precise

« back to all changes in this revision

Viewing changes to code/botlib/be_aas_routealt.c

  • Committer: Bazaar Package Importer
  • Author(s): Bruno "Fuddl" Kleinert
  • Date: 2007-01-20 12:28:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070120122809-2yza5ojt7nqiyiam
Tags: upstream-0.6.0
Import upstream version 0.6.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
code/botlib/be_aas_routealt.c
 
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
//===========================================================================
 
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
//===========================================================================
 
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
//===========================================================================
 
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
//===========================================================================
 
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