be_aas_routealt.c (8275B)
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 Foobar; 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 "../game/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 "../game/botlib.h" 41 #include "../game/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