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

« back to all changes in this revision

Viewing changes to code/botlib/be_aas_route.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

files added:

BUGS

COPYING.txt

ChangeLog

Makefile

NOTTODO

README

TODO

code

code/AL

code/AL/VERSION

code/AL/al.h

code/AL/alc.h

code/AL/alctypes.h

code/AL/altypes.h

code/AL/alut.h

code/SDL12

code/SDL12/include

code/SDL12/include/SDL.h

code/SDL12/include/SDL_active.h

code/SDL12/include/SDL_audio.h

code/SDL12/include/SDL_byteorder.h

code/SDL12/include/SDL_cdrom.h

code/SDL12/include/SDL_copying.h

code/SDL12/include/SDL_cpuinfo.h

code/SDL12/include/SDL_endian.h

code/SDL12/include/SDL_error.h

code/SDL12/include/SDL_events.h

code/SDL12/include/SDL_getenv.h

code/SDL12/include/SDL_joystick.h

code/SDL12/include/SDL_keyboard.h

code/SDL12/include/SDL_keysym.h

code/SDL12/include/SDL_loadso.h

code/SDL12/include/SDL_main.h

code/SDL12/include/SDL_mouse.h

code/SDL12/include/SDL_mutex.h

code/SDL12/include/SDL_name.h

code/SDL12/include/SDL_opengl.h

code/SDL12/include/SDL_quit.h

code/SDL12/include/SDL_rwops.h

code/SDL12/include/SDL_syswm.h

code/SDL12/include/SDL_thread.h

code/SDL12/include/SDL_timer.h

code/SDL12/include/SDL_types.h

code/SDL12/include/SDL_version.h

code/SDL12/include/SDL_video.h

code/SDL12/include/begin_code.h

code/SDL12/include/close_code.h

code/botlib

code/botlib/aasfile.h

code/botlib/be_aas.h

code/botlib/be_aas_bsp.h

code/botlib/be_aas_bspq3.c

code/botlib/be_aas_cluster.c

code/botlib/be_aas_cluster.h

code/botlib/be_aas_debug.c

code/botlib/be_aas_debug.h

code/botlib/be_aas_def.h

code/botlib/be_aas_entity.c

code/botlib/be_aas_entity.h

code/botlib/be_aas_file.c

code/botlib/be_aas_file.h

code/botlib/be_aas_funcs.h

code/botlib/be_aas_main.c

code/botlib/be_aas_main.h

code/botlib/be_aas_move.c

code/botlib/be_aas_move.h

code/botlib/be_aas_optimize.c

code/botlib/be_aas_optimize.h

code/botlib/be_aas_reach.c

code/botlib/be_aas_reach.h

code/botlib/be_aas_route.c

code/botlib/be_aas_route.h

code/botlib/be_aas_routealt.c

code/botlib/be_aas_routealt.h

code/botlib/be_aas_sample.c

code/botlib/be_aas_sample.h

code/botlib/be_ai_char.c

code/botlib/be_ai_char.h

code/botlib/be_ai_chat.c

code/botlib/be_ai_chat.h

code/botlib/be_ai_gen.c

code/botlib/be_ai_gen.h

code/botlib/be_ai_goal.c

code/botlib/be_ai_goal.h

code/botlib/be_ai_move.c

code/botlib/be_ai_move.h

code/botlib/be_ai_weap.c

code/botlib/be_ai_weap.h

code/botlib/be_ai_weight.c

code/botlib/be_ai_weight.h

code/botlib/be_ea.c

code/botlib/be_ea.h

code/botlib/be_interface.c

code/botlib/be_interface.h

code/botlib/botlib.h

code/botlib/l_crc.c

code/botlib/l_crc.h

code/botlib/l_libvar.c

code/botlib/l_libvar.h

code/botlib/l_log.c

code/botlib/l_log.h

code/botlib/l_memory.c

code/botlib/l_memory.h

code/botlib/l_precomp.c

code/botlib/l_precomp.h

code/botlib/l_script.c

code/botlib/l_script.h

code/botlib/l_struct.c

code/botlib/l_struct.h

code/botlib/l_utils.h

code/botlib/lcc.mak

code/botlib/linux-i386.mak

code/cgame

code/cgame/cg_consolecmds.c

code/cgame/cg_draw.c

code/cgame/cg_drawtools.c

code/cgame/cg_effects.c

code/cgame/cg_ents.c

code/cgame/cg_event.c

code/cgame/cg_info.c

code/cgame/cg_local.h

code/cgame/cg_localents.c

code/cgame/cg_main.c

code/cgame/cg_marks.c

code/cgame/cg_newdraw.c

code/cgame/cg_particles.c

code/cgame/cg_players.c

code/cgame/cg_playerstate.c

code/cgame/cg_predict.c

code/cgame/cg_public.h

code/cgame/cg_scoreboard.c

code/cgame/cg_servercmds.c

code/cgame/cg_snapshot.c

code/cgame/cg_syscalls.asm

code/cgame/cg_syscalls.c

code/cgame/cg_view.c

code/cgame/cg_weapons.c

code/cgame/cgame.bat

code/cgame/cgame.plg

code/cgame/cgame.q3asm

code/cgame/cgame.sh

code/cgame/cgame_ta.bat

code/cgame/cgame_ta.q3asm

code/cgame/cgame_ta.sh

code/client

code/client/cl_avi.c

code/client/cl_cgame.c

code/client/cl_cin.c

code/client/cl_console.c

code/client/cl_curl.c

code/client/cl_curl.h

code/client/cl_input.c

code/client/cl_keys.c

code/client/cl_main.c

code/client/cl_net_chan.c

code/client/cl_parse.c

code/client/cl_scrn.c

code/client/cl_ui.c

code/client/client.h

code/client/keycodes.h

code/client/keys.h

code/client/qal.c

code/client/qal.h

code/client/snd_adpcm.c

code/client/snd_codec.c

code/client/snd_codec.h

code/client/snd_codec_ogg.c

code/client/snd_codec_wav.c

code/client/snd_dma.c

code/client/snd_local.h

code/client/snd_main.c

code/client/snd_mem.c

code/client/snd_mix.c

code/client/snd_openal.c

code/client/snd_public.h

code/client/snd_wavelet.c

code/game

code/game/ai_chat.c

code/game/ai_chat.h

code/game/ai_cmd.c

code/game/ai_cmd.h

code/game/ai_dmnet.c

code/game/ai_dmnet.h

code/game/ai_dmq3.c

code/game/ai_dmq3.h

code/game/ai_main.c

code/game/ai_main.h

code/game/ai_team.c

code/game/ai_team.h

code/game/ai_vcmd.c

code/game/ai_vcmd.h

code/game/bg_lib.c

code/game/bg_lib.h

code/game/bg_local.h

code/game/bg_misc.c

code/game/bg_pmove.c

code/game/bg_public.h

code/game/bg_slidemove.c

code/game/chars.h

code/game/g_active.c

code/game/g_arenas.c

code/game/g_bot.c

code/game/g_client.c

code/game/g_cmds.c

code/game/g_combat.c

code/game/g_items.c

code/game/g_local.h

code/game/g_main.c

code/game/g_mem.c

code/game/g_misc.c

code/game/g_missile.c

code/game/g_mover.c

code/game/g_public.h

code/game/g_rankings.c

code/game/g_rankings.h

code/game/g_session.c

code/game/g_spawn.c

code/game/g_svcmds.c

code/game/g_syscalls.asm

code/game/g_syscalls.c

code/game/g_target.c

code/game/g_team.c

code/game/g_team.h

code/game/g_trigger.c

code/game/g_utils.c

code/game/g_weapon.c

code/game/game.bat

code/game/game.q3asm

code/game/game.sh

code/game/game_ta.bat

code/game/game_ta.q3asm

code/game/game_ta.sh

code/game/inv.h

code/game/match.h

code/game/syn.h

code/jpeg-6

code/jpeg-6/README

code/jpeg-6/jcapimin.c

code/jpeg-6/jcapistd.c

code/jpeg-6/jccoefct.c

code/jpeg-6/jccolor.c

code/jpeg-6/jcdctmgr.c

code/jpeg-6/jchuff.c

code/jpeg-6/jchuff.h

code/jpeg-6/jcinit.c

code/jpeg-6/jcmainct.c

code/jpeg-6/jcmarker.c

code/jpeg-6/jcmaster.c

code/jpeg-6/jcomapi.c

code/jpeg-6/jconfig.h

code/jpeg-6/jcparam.c

code/jpeg-6/jcphuff.c

code/jpeg-6/jcprepct.c

code/jpeg-6/jcsample.c

code/jpeg-6/jctrans.c

code/jpeg-6/jdapimin.c

code/jpeg-6/jdapistd.c

code/jpeg-6/jdatadst.c

code/jpeg-6/jdatasrc.c

code/jpeg-6/jdcoefct.c

code/jpeg-6/jdcolor.c

code/jpeg-6/jdct.h

code/jpeg-6/jddctmgr.c

code/jpeg-6/jdhuff.c

code/jpeg-6/jdhuff.h

code/jpeg-6/jdinput.c

code/jpeg-6/jdmainct.c

code/jpeg-6/jdmarker.c

code/jpeg-6/jdmaster.c

code/jpeg-6/jdmerge.c

code/jpeg-6/jdphuff.c

code/jpeg-6/jdpostct.c

code/jpeg-6/jdsample.c

code/jpeg-6/jdtrans.c

code/jpeg-6/jerror.c

code/jpeg-6/jerror.h

code/jpeg-6/jfdctflt.c

code/jpeg-6/jfdctfst.c

code/jpeg-6/jfdctint.c

code/jpeg-6/jidctflt.c

code/jpeg-6/jidctfst.c

code/jpeg-6/jidctint.c

code/jpeg-6/jidctred.c

code/jpeg-6/jinclude.h

code/jpeg-6/jload.c

code/jpeg-6/jmemansi.c

code/jpeg-6/jmemdos.c

code/jpeg-6/jmemmgr.c

code/jpeg-6/jmemname.c

code/jpeg-6/jmemnobs.c

code/jpeg-6/jmemsys.h

code/jpeg-6/jmorecfg.h

code/jpeg-6/jpegint.h

code/jpeg-6/jpeglib.h

code/jpeg-6/jpegtran.c

code/jpeg-6/jquant1.c

code/jpeg-6/jquant2.c

code/jpeg-6/jutils.c

code/jpeg-6/jversion.h

code/libcurl

code/libcurl/curl

code/libcurl/curl/curl.h

code/libcurl/curl/curlver.h

code/libcurl/curl/easy.h

code/libcurl/curl/mprintf.h

code/libcurl/curl/multi.h

code/libcurl/curl/stdcheaders.h

code/libcurl/curl/types.h

code/libs

code/libs/macosx

code/libs/macosx/libSDL-1.2.0.dylib

code/libs/macosx/libSDLmain.a

code/libs/win32

code/libs/win32/libcurl.a

code/null

code/null/mac_net.c

code/null/null_client.c

code/null/null_glimp.c

code/null/null_input.c

code/null/null_main.c

code/null/null_net.c

code/null/null_snddma.c

code/q3_ui

code/q3_ui/compile.bat

code/q3_ui/q3_ui.bat

code/q3_ui/q3_ui.q3asm

code/q3_ui/q3_ui.sh

code/q3_ui/ui.q3asm

code/q3_ui/ui_addbots.c

code/q3_ui/ui_atoms.c

code/q3_ui/ui_cdkey.c

code/q3_ui/ui_cinematics.c

code/q3_ui/ui_confirm.c

code/q3_ui/ui_connect.c

code/q3_ui/ui_controls2.c

code/q3_ui/ui_credits.c

code/q3_ui/ui_demo2.c

code/q3_ui/ui_display.c

code/q3_ui/ui_gameinfo.c

code/q3_ui/ui_ingame.c

code/q3_ui/ui_loadconfig.c

code/q3_ui/ui_local.h

code/q3_ui/ui_login.c

code/q3_ui/ui_main.c

code/q3_ui/ui_menu.c

code/q3_ui/ui_mfield.c

code/q3_ui/ui_mods.c

code/q3_ui/ui_network.c

code/q3_ui/ui_options.c

code/q3_ui/ui_playermodel.c

code/q3_ui/ui_players.c

code/q3_ui/ui_playersettings.c

code/q3_ui/ui_preferences.c

code/q3_ui/ui_qmenu.c

code/q3_ui/ui_rankings.c

code/q3_ui/ui_rankstatus.c

code/q3_ui/ui_removebots.c

code/q3_ui/ui_saveconfig.c

code/q3_ui/ui_serverinfo.c

code/q3_ui/ui_servers2.c

code/q3_ui/ui_setup.c

code/q3_ui/ui_signup.c

code/q3_ui/ui_sound.c

code/q3_ui/ui_sparena.c

code/q3_ui/ui_specifyleague.c

code/q3_ui/ui_specifyserver.c

code/q3_ui/ui_splevel.c

code/q3_ui/ui_sppostgame.c

code/q3_ui/ui_spreset.c

code/q3_ui/ui_spskill.c

code/q3_ui/ui_startserver.c

code/q3_ui/ui_team.c

code/q3_ui/ui_teamorders.c

code/q3_ui/ui_video.c

code/qcommon

code/qcommon/cm_load.c

code/qcommon/cm_local.h

code/qcommon/cm_patch.c

code/qcommon/cm_patch.h

code/qcommon/cm_polylib.c

code/qcommon/cm_polylib.h

code/qcommon/cm_public.h

code/qcommon/cm_test.c

code/qcommon/cm_trace.c

code/qcommon/cmd.c

code/qcommon/common.c

code/qcommon/cvar.c

code/qcommon/files.c

code/qcommon/huffman.c

code/qcommon/md4.c

code/qcommon/md5.c

code/qcommon/msg.c

code/qcommon/net_chan.c

code/qcommon/q_math.c

code/qcommon/q_platform.h

code/qcommon/q_shared.c

code/qcommon/q_shared.h

code/qcommon/qcommon.h

code/qcommon/qfiles.h

code/qcommon/surfaceflags.h

code/qcommon/unzip.c

code/qcommon/unzip.h

code/qcommon/vm.c

code/qcommon/vm_interpreted.c

code/qcommon/vm_local.h

code/qcommon/vm_none.c

code/qcommon/vm_ppc.c

code/qcommon/vm_ppc_new.c

code/qcommon/vm_x86.c

code/qcommon/vm_x86_64.c

code/renderer

code/renderer/qgl.h

code/renderer/qgl_linked.h

code/renderer/tr_animation.c

code/renderer/tr_backend.c

code/renderer/tr_bsp.c

code/renderer/tr_cmds.c

code/renderer/tr_curve.c

code/renderer/tr_flares.c

code/renderer/tr_font.c

code/renderer/tr_image.c

code/renderer/tr_init.c

code/renderer/tr_light.c

code/renderer/tr_local.h

code/renderer/tr_main.c

code/renderer/tr_marks.c

code/renderer/tr_mesh.c

code/renderer/tr_model.c

code/renderer/tr_noise.c

code/renderer/tr_public.h

code/renderer/tr_scene.c

code/renderer/tr_shade.c

code/renderer/tr_shade_calc.c

code/renderer/tr_shader.c

code/renderer/tr_shadows.c

code/renderer/tr_sky.c

code/renderer/tr_surface.c

code/renderer/tr_types.h

code/renderer/tr_world.c

code/server

code/server/server.h

code/server/sv_bot.c

code/server/sv_ccmds.c

code/server/sv_client.c

code/server/sv_game.c

code/server/sv_init.c

code/server/sv_main.c

code/server/sv_net_chan.c

code/server/sv_rankings.c

code/server/sv_snapshot.c

code/server/sv_world.c

code/tools

code/tools/asm

code/tools/asm/Makefile

code/tools/asm/README.Id

code/tools/asm/cmdlib.c

code/tools/asm/cmdlib.h

code/tools/asm/lib.txt

code/tools/asm/mathlib.h

code/tools/asm/notes.txt

code/tools/asm/ops.txt

code/tools/asm/opstrings.h

code/tools/asm/q3asm.c

code/tools/asm/q3asm.sln

code/tools/asm/q3asm.vcproj

code/tools/lcc

code/tools/lcc/COPYRIGHT

code/tools/lcc/LOG

code/tools/lcc/Makefile

code/tools/lcc/README

code/tools/lcc/README.id

code/tools/lcc/buildnt.bat

code/tools/lcc/cpp

code/tools/lcc/cpp/cpp.c

code/tools/lcc/cpp/cpp.h

code/tools/lcc/cpp/eval.c

code/tools/lcc/cpp/getopt.c

code/tools/lcc/cpp/hideset.c

code/tools/lcc/cpp/include.c

code/tools/lcc/cpp/lex.c

code/tools/lcc/cpp/macro.c

code/tools/lcc/cpp/nlist.c

code/tools/lcc/cpp/tokens.c

code/tools/lcc/cpp/unix.c

code/tools/lcc/doc

code/tools/lcc/doc/4.html

code/tools/lcc/doc/bprint.1

code/tools/lcc/doc/bprint.pdf

code/tools/lcc/doc/install.html

code/tools/lcc/doc/lcc.1

code/tools/lcc/doc/lcc.pdf

code/tools/lcc/etc

code/tools/lcc/etc/bytecode.c

code/tools/lcc/etc/lcc.c

code/tools/lcc/lburg

code/tools/lcc/lburg/gram.c

code/tools/lcc/lburg/gram.y

code/tools/lcc/lburg/lburg.1

code/tools/lcc/lburg/lburg.c

code/tools/lcc/lburg/lburg.h

code/tools/lcc/makefile.nt

code/tools/lcc/src

code/tools/lcc/src/alloc.c

code/tools/lcc/src/bind.c

code/tools/lcc/src/bytecode.c

code/tools/lcc/src/c.h

code/tools/lcc/src/config.h

code/tools/lcc/src/dag.c

code/tools/lcc/src/dagcheck.md

code/tools/lcc/src/decl.c

code/tools/lcc/src/enode.c

code/tools/lcc/src/error.c

code/tools/lcc/src/event.c

code/tools/lcc/src/expr.c

code/tools/lcc/src/gen.c

code/tools/lcc/src/init.c

code/tools/lcc/src/inits.c

code/tools/lcc/src/input.c

code/tools/lcc/src/lex.c

code/tools/lcc/src/list.c

code/tools/lcc/src/main.c

code/tools/lcc/src/null.c

code/tools/lcc/src/output.c

code/tools/lcc/src/prof.c

code/tools/lcc/src/profio.c

code/tools/lcc/src/simp.c

code/tools/lcc/src/stmt.c

code/tools/lcc/src/string.c

code/tools/lcc/src/sym.c

code/tools/lcc/src/symbolic.c

code/tools/lcc/src/token.h

code/tools/lcc/src/trace.c

code/tools/lcc/src/tree.c

code/tools/lcc/src/types.c

code/ui

code/ui/compile.bat

code/ui/ui.bat

code/ui/ui.q3asm

code/ui/ui_atoms.c

code/ui/ui_gameinfo.c

code/ui/ui_local.h

code/ui/ui_main.c

code/ui/ui_players.c

code/ui/ui_public.h

code/ui/ui_shared.c

code/ui/ui_shared.h

code/ui/ui_syscalls.asm

code/ui/ui_syscalls.c

code/unix

code/unix/LinuxSupport

code/unix/LinuxSupport/CHANGES-1.32.txt

code/unix/LinuxSupport/INSTALL

code/unix/LinuxSupport/index.html

code/unix/LinuxSupport/udp_wide_README.txt

code/unix/LinuxSupport/udp_wide_broadcast.patch

code/unix/MacSupport

code/unix/MacSupport/SLA-dmg.sh

code/unix/MacSupport/SLA.r

code/unix/MacSupport/ioquake3.icns

code/unix/README.Linux

code/unix/README.Q3Test

code/unix/ftola.s

code/unix/linux_glimp.c

code/unix/linux_joystick.c

code/unix/linux_local.h

code/unix/linux_qgl.c

code/unix/linux_signals.c

code/unix/linux_snd.c

code/unix/matha.s

code/unix/qasm.h

code/unix/quake3.png

code/unix/quake3.svg

code/unix/sdl_glimp.c

code/unix/sdl_snd.c

code/unix/setup

code/unix/setup/Makefile

code/unix/setup/Solaris_pkg.sh

code/unix/setup/doit

code/unix/setup/ioq3demo.sh

code/unix/setup/ioquake3.sh

code/unix/setup/pkg

code/unix/setup/pkg/ioq3ded.sh

code/unix/setup/pkg/ioquake3

code/unix/setup/pkg/ioquake3.sh

code/unix/setup/pkg/ioquake3/depend

code/unix/setup/pkg/ioquake3/pkginfo.template

code/unix/setup/pkg/ioquake3/postinstall

code/unix/setup/pkg/ioquake3/postremove

code/unix/setup/pkg/ioquake3/preinstall

code/unix/setup/pkg/ioquake3/preremove

code/unix/setup/pkg/ioquake3/prototype.template

code/unix/setup/pkg/ioquake3/space

code/unix/setup/pkg/ioquake3d

code/unix/setup/pkg/ioquake3d/depend

code/unix/setup/pkg/ioquake3d/pkginfo.template

code/unix/setup/pkg/ioquake3d/postinstall

code/unix/setup/pkg/ioquake3d/postremove

code/unix/setup/pkg/ioquake3d/preinstall

code/unix/setup/pkg/ioquake3d/preremove

code/unix/setup/pkg/ioquake3d/prototype.template

code/unix/setup/pkg/ioquake3d/space

code/unix/setup/preuninstall.sh

code/unix/setup/setup.xml

code/unix/setup/splash.xpm

code/unix/snapvectora.s

code/unix/snd_mixa.s

code/unix/unix_glw.h

code/unix/unix_main.c

code/unix/unix_net.c

code/unix/unix_shared.c

code/win32

code/win32/background.bmp

code/win32/clear.bmp

code/win32/glw_win.h

code/win32/icon2.ico

code/win32/msvc

code/win32/msvc/botlib.vcproj

code/win32/msvc/cgame.def

code/win32/msvc/cgame.vcproj

code/win32/msvc/game.def

code/win32/msvc/game.vcproj

code/win32/msvc/q3_ui.def

code/win32/msvc/q3_ui.vcproj

code/win32/msvc/quake3.sln

code/win32/msvc/quake3.vcproj

code/win32/msvc/ref_trin.def

code/win32/msvc/renderer.vcproj

code/win32/msvc/ui.def

code/win32/msvc/ui.vcproj

code/win32/qe3.ico

code/win32/resource.h

code/win32/win_gamma.c

code/win32/win_glimp.c

code/win32/win_input.c

code/win32/win_local.h

code/win32/win_main.c

code/win32/win_net.c

code/win32/win_qgl.c

code/win32/win_shared.c

code/win32/win_snd.c

code/win32/win_syscon.c

code/win32/win_wndproc.c

code/win32/winquake.rc

cross-make-mingw.sh

id-readme.txt

make-macosx-ub.sh

md4-readme.txt

ui/hud.txt

ui/hud2.txt

ui/ingame.txt

ui/menudef.h

ui/menus.txt

Show diffs side-by-side

added added

removed removed

code/botlib/be_aas_route.c

===========================================================================

This file is part of Quake III Arena source code.

Quake III Arena source code 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.

Quake III Arena source code 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 Quake III Arena source code; if not, write to the Free Software

Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA

===========================================================================

/*****************************************************************************

* name: be_aas_route.c

* desc: AAS

* $Archive: /MissionPack/code/botlib/be_aas_route.c $

*****************************************************************************/

#include "../qcommon/q_shared.h"

#include "l_utils.h"

#include "l_memory.h"

#include "l_log.h"

#include "l_crc.h"

#include "l_libvar.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 ROUTING_DEBUG

//travel time in hundreths of a second = distance * 100 / speed

#define DISTANCEFACTOR_CROUCH 1.3f //crouch speed = 100

#define DISTANCEFACTOR_SWIM 1 //should be 0.66, swim speed = 150

#define DISTANCEFACTOR_WALK 0.33f //walk speed = 300

//cache refresh time

#define CACHE_REFRESHTIME 15.0f //15 seconds refresh time

//maximum number of routing updates each frame

#define MAX_FRAMEROUTINGUPDATES 10

area routing cache:

stores the distances within one cluster to a specific goal area

this goal area is in this same cluster and could be a cluster portal

for every cluster there's a list with routing cache for every area

in that cluster (including the portals of that cluster)

area cache stores aasworld.clusters[?].numreachabilityareas travel times

portal routing cache:

stores the distances of all portals to a specific goal area

this goal area could be in any cluster and could also be a cluster portal

for every area (aasworld.numareas) the portal cache stores

aasworld.numportals travel times

#ifdef ROUTING_DEBUG

int numareacacheupdates;

int numportalcacheupdates;

#endif //ROUTING_DEBUG

int routingcachesize;

int max_routingcachesize;

//===========================================================================

// Parameter: -

// Returns: -

// Changes Globals: -

//===========================================================================

#ifdef ROUTING_DEBUG

void AAS_RoutingInfo(void)

{

botimport.Print(PRT_MESSAGE, "%d area cache updates\n", numareacacheupdates);

botimport.Print(PRT_MESSAGE, "%d portal cache updates\n", numportalcacheupdates);

botimport.Print(PRT_MESSAGE, "%d bytes routing cache\n", routingcachesize);

} //end of the function AAS_RoutingInfo

100

#endif //ROUTING_DEBUG

101

//===========================================================================

102

// returns the number of the area in the cluster

103

// assumes the given area is in the given cluster or a portal of the cluster

104

105

// Parameter: -

106

// Returns: -

107

// Changes Globals: -

108

//===========================================================================

109

ID_INLINE int AAS_ClusterAreaNum(int cluster, int areanum)

110

{

111

int side, areacluster;

112

113

areacluster = aasworld.areasettings[areanum].cluster;

114

if (areacluster > 0) return aasworld.areasettings[areanum].clusterareanum;

115

else

116

{

117

/*#ifdef ROUTING_DEBUG

118

if (aasworld.portals[-areacluster].frontcluster != cluster &&

119

aasworld.portals[-areacluster].backcluster != cluster)

120

{

121

botimport.Print(PRT_ERROR, "portal %d: does not belong to cluster %d\n"

122

, -areacluster, cluster);

123

} //end if

124

#endif //ROUTING_DEBUG*/

125

side = aasworld.portals[-areacluster].frontcluster != cluster;

126

return aasworld.portals[-areacluster].clusterareanum[side];

127

} //end else

128

} //end of the function AAS_ClusterAreaNum

129

//===========================================================================

130

131

// Parameter: -

132

// Returns: -

133

// Changes Globals: -

134

//===========================================================================

135

void AAS_InitTravelFlagFromType(void)

136

{

137

int i;

138

139

for (i = 0; i < MAX_TRAVELTYPES; i++)

140

{

141

aasworld.travelflagfortype[i] = TFL_INVALID;

142

} //end for

143

aasworld.travelflagfortype[TRAVEL_INVALID] = TFL_INVALID;

144

aasworld.travelflagfortype[TRAVEL_WALK] = TFL_WALK;

145

aasworld.travelflagfortype[TRAVEL_CROUCH] = TFL_CROUCH;

146

aasworld.travelflagfortype[TRAVEL_BARRIERJUMP] = TFL_BARRIERJUMP;

147

aasworld.travelflagfortype[TRAVEL_JUMP] = TFL_JUMP;

148

aasworld.travelflagfortype[TRAVEL_LADDER] = TFL_LADDER;

149

aasworld.travelflagfortype[TRAVEL_WALKOFFLEDGE] = TFL_WALKOFFLEDGE;

150

aasworld.travelflagfortype[TRAVEL_SWIM] = TFL_SWIM;

151

aasworld.travelflagfortype[TRAVEL_WATERJUMP] = TFL_WATERJUMP;

152

aasworld.travelflagfortype[TRAVEL_TELEPORT] = TFL_TELEPORT;

153

aasworld.travelflagfortype[TRAVEL_ELEVATOR] = TFL_ELEVATOR;

154

aasworld.travelflagfortype[TRAVEL_ROCKETJUMP] = TFL_ROCKETJUMP;

155

aasworld.travelflagfortype[TRAVEL_BFGJUMP] = TFL_BFGJUMP;

156

aasworld.travelflagfortype[TRAVEL_GRAPPLEHOOK] = TFL_GRAPPLEHOOK;

157

aasworld.travelflagfortype[TRAVEL_DOUBLEJUMP] = TFL_DOUBLEJUMP;

158

aasworld.travelflagfortype[TRAVEL_RAMPJUMP] = TFL_RAMPJUMP;

159

aasworld.travelflagfortype[TRAVEL_STRAFEJUMP] = TFL_STRAFEJUMP;

160

aasworld.travelflagfortype[TRAVEL_JUMPPAD] = TFL_JUMPPAD;

161

aasworld.travelflagfortype[TRAVEL_FUNCBOB] = TFL_FUNCBOB;

162

} //end of the function AAS_InitTravelFlagFromType

163

//===========================================================================

164

165

// Parameter: -

166

// Returns: -

167

// Changes Globals: -

168

//===========================================================================

169

ID_INLINE int AAS_TravelFlagForType_inline(int traveltype)

170

{

171

int tfl;

172

173

tfl = 0;

174

if (tfl & TRAVELFLAG_NOTTEAM1)

175

tfl |= TFL_NOTTEAM1;

176

if (tfl & TRAVELFLAG_NOTTEAM2)

177

tfl |= TFL_NOTTEAM2;

178

traveltype &= TRAVELTYPE_MASK;

179

if (traveltype < 0 || traveltype >= MAX_TRAVELTYPES)

180

return TFL_INVALID;

181

tfl |= aasworld.travelflagfortype[traveltype];

182

return tfl;

183

} //end of the function AAS_TravelFlagForType_inline

184

//===========================================================================

185

186

// Parameter: -

187

// Returns: -

188

// Changes Globals: -

189

//===========================================================================

190

int AAS_TravelFlagForType(int traveltype)

191

{

192

return AAS_TravelFlagForType_inline(traveltype);

193

} //end of the function AAS_TravelFlagForType_inline

194

//===========================================================================

195

196

// Parameter: -

197

// Returns: -

198

// Changes Globals: -

199

//===========================================================================

200

void AAS_UnlinkCache(aas_routingcache_t *cache)

201

{

202

if (cache->time_next) cache->time_next->time_prev = cache->time_prev;

203

else aasworld.newestcache = cache->time_prev;

204

if (cache->time_prev) cache->time_prev->time_next = cache->time_next;

205

else aasworld.oldestcache = cache->time_next;

206

cache->time_next = NULL;

207

cache->time_prev = NULL;

208

} //end of the function AAS_UnlinkCache

209

//===========================================================================

210

211

// Parameter: -

212

// Returns: -

213

// Changes Globals: -

214

//===========================================================================

215

void AAS_LinkCache(aas_routingcache_t *cache)

216

{

217

if (aasworld.newestcache)

218

{

219

aasworld.newestcache->time_next = cache;

220

cache->time_prev = aasworld.newestcache;

221

} //end if

222

else

223

{

224

aasworld.oldestcache = cache;

225

cache->time_prev = NULL;

226

} //end else

227

cache->time_next = NULL;

228

aasworld.newestcache = cache;

229

} //end of the function AAS_LinkCache

230

//===========================================================================

231

232

// Parameter: -

233

// Returns: -

234

// Changes Globals: -

235

//===========================================================================

236

void AAS_FreeRoutingCache(aas_routingcache_t *cache)

237

{

238

AAS_UnlinkCache(cache);

239

routingcachesize -= cache->size;

240

FreeMemory(cache);

241

} //end of the function AAS_FreeRoutingCache

242

//===========================================================================

243

244

// Parameter: -

245

// Returns: -

246

// Changes Globals: -

247

//===========================================================================

248

void AAS_RemoveRoutingCacheInCluster( int clusternum )

249

{

250

int i;

251

aas_routingcache_t *cache, *nextcache;

252

aas_cluster_t *cluster;

253

254

if (!aasworld.clusterareacache)

255

return;

256

cluster = &aasworld.clusters[clusternum];

257

for (i = 0; i < cluster->numareas; i++)

258

{

259

for (cache = aasworld.clusterareacache[clusternum][i]; cache; cache = nextcache)

260

{

261

nextcache = cache->next;

262

AAS_FreeRoutingCache(cache);

263

} //end for

264

aasworld.clusterareacache[clusternum][i] = NULL;

265

} //end for

266

} //end of the function AAS_RemoveRoutingCacheInCluster

267

//===========================================================================

268

269

// Parameter: -

270

// Returns: -

271

// Changes Globals: -

272

//===========================================================================

273

void AAS_RemoveRoutingCacheUsingArea( int areanum )

274

{

275

int i, clusternum;

276

aas_routingcache_t *cache, *nextcache;

277

278

clusternum = aasworld.areasettings[areanum].cluster;

279

if (clusternum > 0)

280

{

281

//remove all the cache in the cluster the area is in

282

AAS_RemoveRoutingCacheInCluster( clusternum );

283

} //end if

284

else

285

{

286

// if this is a portal remove all cache in both the front and back cluster

287

AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].frontcluster );

288

AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].backcluster );

289

} //end else

290

// remove all portal cache

291

for (i = 0; i < aasworld.numareas; i++)

292

{

293

//refresh portal cache

294

for (cache = aasworld.portalcache[i]; cache; cache = nextcache)

295

{

296

nextcache = cache->next;

297

AAS_FreeRoutingCache(cache);

298

} //end for

299

aasworld.portalcache[i] = NULL;

300

} //end for

301

} //end of the function AAS_RemoveRoutingCacheUsingArea

302

//===========================================================================

303

304

// Parameter: -

305

// Returns: -

306

// Changes Globals: -

307

//===========================================================================

308

int AAS_EnableRoutingArea(int areanum, int enable)

309

{

310

int flags;

311

312

if (areanum <= 0 || areanum >= aasworld.numareas)

313

{

314

if (bot_developer)

315

{

316

botimport.Print(PRT_ERROR, "AAS_EnableRoutingArea: areanum %d out of range\n", areanum);

317

} //end if

318

return 0;

319

} //end if

320

flags = aasworld.areasettings[areanum].areaflags & AREA_DISABLED;

321

if (enable < 0)

322

return !flags;

323

324

if (enable)

325

aasworld.areasettings[areanum].areaflags &= ~AREA_DISABLED;

326

else

327

aasworld.areasettings[areanum].areaflags |= AREA_DISABLED;

328

// if the status of the area changed

329

if ( (flags & AREA_DISABLED) != (aasworld.areasettings[areanum].areaflags & AREA_DISABLED) )

330

{

331

//remove all routing cache involving this area

332

AAS_RemoveRoutingCacheUsingArea( areanum );

333

} //end if

334

return !flags;

335

} //end of the function AAS_EnableRoutingArea

336

//===========================================================================

337

338

// Parameter: -

339

// Returns: -

340

// Changes Globals: -

341

//===========================================================================

342

ID_INLINE float AAS_RoutingTime(void)

343

{

344

return AAS_Time();

345

} //end of the function AAS_RoutingTime

346

//===========================================================================

347

348

// Parameter: -

349

// Returns: -

350

// Changes Globals: -

351

//===========================================================================

352

int AAS_GetAreaContentsTravelFlags(int areanum)

353

{

354

int contents, tfl;

355

356

contents = aasworld.areasettings[areanum].contents;

357

tfl = 0;

358

if (contents & AREACONTENTS_WATER)

359

tfl |= TFL_WATER;

360

else if (contents & AREACONTENTS_SLIME)

361

tfl |= TFL_SLIME;

362

else if (contents & AREACONTENTS_LAVA)

363

tfl |= TFL_LAVA;

364

else

365

tfl |= TFL_AIR;

366

if (contents & AREACONTENTS_DONOTENTER)

367

tfl |= TFL_DONOTENTER;

368

if (contents & AREACONTENTS_NOTTEAM1)

369

tfl |= TFL_NOTTEAM1;

370

if (contents & AREACONTENTS_NOTTEAM2)

371

tfl |= TFL_NOTTEAM2;

372

if (aasworld.areasettings[areanum].areaflags & AREA_BRIDGE)

373

tfl |= TFL_BRIDGE;

374

return tfl;

375

} //end of the function AAS_GetAreaContentsTravelFlags

376

//===========================================================================

377

378

// Parameter: -

379

// Returns: -

380

// Changes Globals: -

381

//===========================================================================

382

ID_INLINE int AAS_AreaContentsTravelFlags_inline(int areanum)

383

{

384

return aasworld.areacontentstravelflags[areanum];

385

} //end of the function AAS_AreaContentsTravelFlags

386

//===========================================================================

387

388

// Parameter: -

389

// Returns: -

390

// Changes Globals: -

391

//===========================================================================

392

int AAS_AreaContentsTravelFlags(int areanum)

393

{

394

return aasworld.areacontentstravelflags[areanum];

395

} //end of the function AAS_AreaContentsTravelFlags

396

//===========================================================================

397

398

// Parameter: -

399

// Returns: -

400

// Changes Globals: -

401

//===========================================================================

402

void AAS_InitAreaContentsTravelFlags(void)

403

{

404

int i;

405

406

if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);

407

aasworld.areacontentstravelflags = (int *) GetClearedMemory(aasworld.numareas * sizeof(int));

408

409

for (i = 0; i < aasworld.numareas; i++) {

410

aasworld.areacontentstravelflags[i] = AAS_GetAreaContentsTravelFlags(i);

411

}

412

} //end of the function AAS_InitAreaContentsTravelFlags

413

//===========================================================================

414

415

// Parameter: -

416

// Returns: -

417

// Changes Globals: -

418

//===========================================================================

419

void AAS_CreateReversedReachability(void)

420

{

421

int i, n;

422

aas_reversedlink_t *revlink;

423

aas_reachability_t *reach;

424

aas_areasettings_t *settings;

425

char *ptr;

426

#ifdef DEBUG

427

int starttime;

428

429

starttime = Sys_MilliSeconds();

430

#endif

431

//free reversed links that have already been created

432

if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);

433

//allocate memory for the reversed reachability links

434

ptr = (char *) GetClearedMemory(aasworld.numareas * sizeof(aas_reversedreachability_t) +

435

aasworld.reachabilitysize * sizeof(aas_reversedlink_t));

436

437

aasworld.reversedreachability = (aas_reversedreachability_t *) ptr;

438

//pointer to the memory for the reversed links

439

ptr += aasworld.numareas * sizeof(aas_reversedreachability_t);

440

//check all reachabilities of all areas

441

for (i = 1; i < aasworld.numareas; i++)

442

{

443

//settings of the area

444

settings = &aasworld.areasettings[i];

445

446

if (settings->numreachableareas >= 128)

447

botimport.Print(PRT_WARNING, "area %d has more than 128 reachabilities\n", i);

448

//create reversed links for the reachabilities

449

for (n = 0; n < settings->numreachableareas && n < 128; n++)

450

{

451

//reachability link

452

reach = &aasworld.reachability[settings->firstreachablearea + n];

453

454

revlink = (aas_reversedlink_t *) ptr;

455

ptr += sizeof(aas_reversedlink_t);

456

457

revlink->areanum = i;

458

revlink->linknum = settings->firstreachablearea + n;

459

revlink->next = aasworld.reversedreachability[reach->areanum].first;

460

aasworld.reversedreachability[reach->areanum].first = revlink;

461

aasworld.reversedreachability[reach->areanum].numlinks++;

462

} //end for

463

} //end for

464

#ifdef DEBUG

465

botimport.Print(PRT_MESSAGE, "reversed reachability %d msec\n", Sys_MilliSeconds() - starttime);

466

#endif

467

} //end of the function AAS_CreateReversedReachability

468

//===========================================================================

469

470

// Parameter: -

471

// Returns: -

472

// Changes Globals: -

473

//===========================================================================

474

unsigned short int AAS_AreaTravelTime(int areanum, vec3_t start, vec3_t end)

475

{

476

int intdist;

477

float dist;

478

vec3_t dir;

479

480

VectorSubtract(start, end, dir);

481

dist = VectorLength(dir);

482

//if crouch only area

483

if (AAS_AreaCrouch(areanum)) dist *= DISTANCEFACTOR_CROUCH;

484

//if swim area

485

else if (AAS_AreaSwim(areanum)) dist *= DISTANCEFACTOR_SWIM;

486

//normal walk area

487

else dist *= DISTANCEFACTOR_WALK;

488

489

intdist = (int) dist;

490

//make sure the distance isn't zero

491

if (intdist <= 0) intdist = 1;

492

return intdist;

493

} //end of the function AAS_AreaTravelTime

494

//===========================================================================

495

496

// Parameter: -

497

// Returns: -

498

// Changes Globals: -

499

//===========================================================================

500

void AAS_CalculateAreaTravelTimes(void)

501

{

502

int i, l, n, size;

503

char *ptr;

504

vec3_t end;

505

aas_reversedreachability_t *revreach;

506

aas_reversedlink_t *revlink;

507

aas_reachability_t *reach;

508

aas_areasettings_t *settings;

509

int starttime;

510

511

starttime = Sys_MilliSeconds();

512

//if there are still area travel times, free the memory

513

if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);

514

//get the total size of all the area travel times

515

size = aasworld.numareas * sizeof(unsigned short **);

516

for (i = 0; i < aasworld.numareas; i++)

517

{

518

revreach = &aasworld.reversedreachability[i];

519

//settings of the area

520

settings = &aasworld.areasettings[i];

521

522

size += settings->numreachableareas * sizeof(unsigned short *);

523

524

size += settings->numreachableareas *

525

PAD(revreach->numlinks, sizeof(long)) * sizeof(unsigned short);

526

} //end for

527

//allocate memory for the area travel times

528

ptr = (char *) GetClearedMemory(size);

529

aasworld.areatraveltimes = (unsigned short ***) ptr;

530

ptr += aasworld.numareas * sizeof(unsigned short **);

531

//calcluate the travel times for all the areas

532

for (i = 0; i < aasworld.numareas; i++)

533

{

534

//reversed reachabilities of this area

535

revreach = &aasworld.reversedreachability[i];

536

//settings of the area

537

settings = &aasworld.areasettings[i];

538

539

aasworld.areatraveltimes[i] = (unsigned short **) ptr;

540

ptr += settings->numreachableareas * sizeof(unsigned short *);

541

542

for (l = 0; l < settings->numreachableareas; l++)

543

{

544

aasworld.areatraveltimes[i][l] = (unsigned short *) ptr;

545

ptr += PAD(revreach->numlinks, sizeof(long)) * sizeof(unsigned short);

546

//reachability link

547

reach = &aasworld.reachability[settings->firstreachablearea + l];

548

549

for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)

550

{

551

VectorCopy(aasworld.reachability[revlink->linknum].end, end);

552

553

aasworld.areatraveltimes[i][l][n] = AAS_AreaTravelTime(i, end, reach->start);

554

} //end for

555

} //end for

556

} //end for

557

#ifdef DEBUG

558

botimport.Print(PRT_MESSAGE, "area travel times %d msec\n", Sys_MilliSeconds() - starttime);

559

#endif

560

} //end of the function AAS_CalculateAreaTravelTimes

561

//===========================================================================

562

563

// Parameter: -

564

// Returns: -

565

// Changes Globals: -

566

//===========================================================================

567

int AAS_PortalMaxTravelTime(int portalnum)

568

{

569

int l, n, t, maxt;

570

aas_portal_t *portal;

571

aas_reversedreachability_t *revreach;

572

aas_reversedlink_t *revlink;

573

aas_areasettings_t *settings;

574

575

portal = &aasworld.portals[portalnum];

576

//reversed reachabilities of this portal area

577

revreach = &aasworld.reversedreachability[portal->areanum];

578

//settings of the portal area

579

settings = &aasworld.areasettings[portal->areanum];

580

581

maxt = 0;

582

for (l = 0; l < settings->numreachableareas; l++)

583

{

584

for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)

585

{

586

t = aasworld.areatraveltimes[portal->areanum][l][n];

587

if (t > maxt)

588

{

589

maxt = t;

590

} //end if

591

} //end for

592

} //end for

593

return maxt;

594

} //end of the function AAS_PortalMaxTravelTime

595

//===========================================================================

596

597

// Parameter: -

598

// Returns: -

599

// Changes Globals: -

600

//===========================================================================

601

void AAS_InitPortalMaxTravelTimes(void)

602

{

603

int i;

604

605

if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);

606

607

aasworld.portalmaxtraveltimes = (int *) GetClearedMemory(aasworld.numportals * sizeof(int));

608

609

for (i = 0; i < aasworld.numportals; i++)

610

{

611

aasworld.portalmaxtraveltimes[i] = AAS_PortalMaxTravelTime(i);

612

//botimport.Print(PRT_MESSAGE, "portal %d max tt = %d\n", i, aasworld.portalmaxtraveltimes[i]);

613

} //end for

614

} //end of the function AAS_InitPortalMaxTravelTimes

615

//===========================================================================

616

617

// Parameter: -

618

// Returns: -

619

// Changes Globals: -

620

//===========================================================================

621

622

int AAS_FreeOldestCache(void)

623

{

624

int i, j, bestcluster, bestarea, freed;

625

float besttime;

626

aas_routingcache_t *cache, *bestcache;

627

628

freed = qfalse;

629

besttime = 999999999;

630

bestcache = NULL;

631

bestcluster = 0;

632

bestarea = 0;

633

//refresh cluster cache

634

for (i = 0; i < aasworld.numclusters; i++)

635

{

636

for (j = 0; j < aasworld.clusters[i].numareas; j++)

637

{

638

for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)

639

{

640

//never remove cache leading towards a portal

641

if (aasworld.areasettings[cache->areanum].cluster < 0) continue;

642

//if this cache is older than the cache we found so far

643

if (cache->time < besttime)

644

{

645

bestcache = cache;

646

bestcluster = i;

647

bestarea = j;

648

besttime = cache->time;

649

} //end if

650

} //end for

651

} //end for

652

} //end for

653

if (bestcache)

654

{

655

cache = bestcache;

656

if (cache->prev) cache->prev->next = cache->next;

657

else aasworld.clusterareacache[bestcluster][bestarea] = cache->next;

658

if (cache->next) cache->next->prev = cache->prev;

659

AAS_FreeRoutingCache(cache);

660

freed = qtrue;

661

} //end if

662

besttime = 999999999;

663

bestcache = NULL;

664

bestarea = 0;

665

for (i = 0; i < aasworld.numareas; i++)

666

{

667

//refresh portal cache

668

for (cache = aasworld.portalcache[i]; cache; cache = cache->next)

669

{

670

if (cache->time < besttime)

671

{

672

bestcache = cache;

673

bestarea = i;

674

besttime = cache->time;

675

} //end if

676

} //end for

677

} //end for

678

if (bestcache)

679

{

680

cache = bestcache;

681

if (cache->prev) cache->prev->next = cache->next;

682

else aasworld.portalcache[bestarea] = cache->next;

683

if (cache->next) cache->next->prev = cache->prev;

684

AAS_FreeRoutingCache(cache);

685

freed = qtrue;

686

} //end if

687

return freed;

688

} //end of the function AAS_FreeOldestCache

689

690

//===========================================================================

691

692

// Parameter: -

693

// Returns: -

694

// Changes Globals: -

695

//===========================================================================

696

int AAS_FreeOldestCache(void)

697

{

698

int clusterareanum;

699

aas_routingcache_t *cache;

700

701

for (cache = aasworld.oldestcache; cache; cache = cache->time_next) {

702

// never free area cache leading towards a portal

703

if (cache->type == CACHETYPE_AREA && aasworld.areasettings[cache->areanum].cluster < 0) {

704

continue;

705

}

706

break;

707

}

708

if (cache) {

709

// unlink the cache

710

if (cache->type == CACHETYPE_AREA) {

711

//number of the area in the cluster

712

clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);

713

// unlink from cluster area cache

714

if (cache->prev) cache->prev->next = cache->next;

715

else aasworld.clusterareacache[cache->cluster][clusterareanum] = cache->next;

716

if (cache->next) cache->next->prev = cache->prev;

717

}

718

else {

719

// unlink from portal cache

720

if (cache->prev) cache->prev->next = cache->next;

721

else aasworld.portalcache[cache->areanum] = cache->next;

722

if (cache->next) cache->next->prev = cache->prev;

723

}

724

AAS_FreeRoutingCache(cache);

725

return qtrue;

726

}

727

return qfalse;

728

} //end of the function AAS_FreeOldestCache

729

//===========================================================================

730

731

// Parameter: -

732

// Returns: -

733

// Changes Globals: -

734

//===========================================================================

735

aas_routingcache_t *AAS_AllocRoutingCache(int numtraveltimes)

736

{

737

aas_routingcache_t *cache;

738

int size;

739

740

741

size = sizeof(aas_routingcache_t)

742

+ numtraveltimes * sizeof(unsigned short int)

743

+ numtraveltimes * sizeof(unsigned char);

744

745

routingcachesize += size;

746

747

cache = (aas_routingcache_t *) GetClearedMemory(size);

748

cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t)

749

+ numtraveltimes * sizeof(unsigned short int);

750

cache->size = size;

751

return cache;

752

} //end of the function AAS_AllocRoutingCache

753

//===========================================================================

754

755

// Parameter: -

756

// Returns: -

757

// Changes Globals: -

758

//===========================================================================

759

void AAS_FreeAllClusterAreaCache(void)

760

{

761

int i, j;

762

aas_routingcache_t *cache, *nextcache;

763

aas_cluster_t *cluster;

764

765

//free all cluster cache if existing

766

if (!aasworld.clusterareacache) return;

767

//free caches

768

for (i = 0; i < aasworld.numclusters; i++)

769

{

770

cluster = &aasworld.clusters[i];

771

for (j = 0; j < cluster->numareas; j++)

772

{

773

for (cache = aasworld.clusterareacache[i][j]; cache; cache = nextcache)

774

{

775

nextcache = cache->next;

776

AAS_FreeRoutingCache(cache);

777

} //end for

778

aasworld.clusterareacache[i][j] = NULL;

779

} //end for

780

} //end for

781

//free the cluster cache array

782

FreeMemory(aasworld.clusterareacache);

783

aasworld.clusterareacache = NULL;

784

} //end of the function AAS_FreeAllClusterAreaCache

785

//===========================================================================

786

787

// Parameter: -

788

// Returns: -

789

// Changes Globals: -

790

//===========================================================================

791

void AAS_InitClusterAreaCache(void)

792

{

793

int i, size;

794

char *ptr;

795

796

797

for (size = 0, i = 0; i < aasworld.numclusters; i++)

798

{

799

size += aasworld.clusters[i].numareas;

800

} //end for

801

//two dimensional array with pointers for every cluster to routing cache

802

//for every area in that cluster

803

ptr = (char *) GetClearedMemory(

804

aasworld.numclusters * sizeof(aas_routingcache_t **) +

805

size * sizeof(aas_routingcache_t *));

806

aasworld.clusterareacache = (aas_routingcache_t ***) ptr;

807

ptr += aasworld.numclusters * sizeof(aas_routingcache_t **);

808

for (i = 0; i < aasworld.numclusters; i++)

809

{

810

aasworld.clusterareacache[i] = (aas_routingcache_t **) ptr;

811

ptr += aasworld.clusters[i].numareas * sizeof(aas_routingcache_t *);

812

} //end for

813

} //end of the function AAS_InitClusterAreaCache

814

//===========================================================================

815

816

// Parameter: -

817

// Returns: -

818

// Changes Globals: -

819

//===========================================================================

820

void AAS_FreeAllPortalCache(void)

821

{

822

int i;

823

aas_routingcache_t *cache, *nextcache;

824

825

//free all portal cache if existing

826

if (!aasworld.portalcache) return;

827

//free portal caches

828

for (i = 0; i < aasworld.numareas; i++)

829

{

830

for (cache = aasworld.portalcache[i]; cache; cache = nextcache)

831

{

832

nextcache = cache->next;

833

AAS_FreeRoutingCache(cache);

834

} //end for

835

aasworld.portalcache[i] = NULL;

836

} //end for

837

FreeMemory(aasworld.portalcache);

838

aasworld.portalcache = NULL;

839

} //end of the function AAS_FreeAllPortalCache

840

//===========================================================================

841

842

// Parameter: -

843

// Returns: -

844

// Changes Globals: -

845

//===========================================================================

846

void AAS_InitPortalCache(void)

847

{

848

849

aasworld.portalcache = (aas_routingcache_t **) GetClearedMemory(

850

aasworld.numareas * sizeof(aas_routingcache_t *));

851

} //end of the function AAS_InitPortalCache

852

//===========================================================================

853

854

// Parameter: -

855

// Returns: -

856

// Changes Globals: -

857

//===========================================================================

858

void AAS_InitRoutingUpdate(void)

859

{

860

int i, maxreachabilityareas;

861

862

//free routing update fields if already existing

863

if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);

864

865

maxreachabilityareas = 0;

866

for (i = 0; i < aasworld.numclusters; i++)

867

{

868

if (aasworld.clusters[i].numreachabilityareas > maxreachabilityareas)

869

{

870

maxreachabilityareas = aasworld.clusters[i].numreachabilityareas;

871

} //end if

872

} //end for

873

//allocate memory for the routing update fields

874

aasworld.areaupdate = (aas_routingupdate_t *) GetClearedMemory(

875

maxreachabilityareas * sizeof(aas_routingupdate_t));

876

877

if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);

878

//allocate memory for the portal update fields

879

aasworld.portalupdate = (aas_routingupdate_t *) GetClearedMemory(

880

(aasworld.numportals+1) * sizeof(aas_routingupdate_t));

881

} //end of the function AAS_InitRoutingUpdate

882

//===========================================================================

883

884

// Parameter: -

885

// Returns: -

886

// Changes Globals: -

887

//===========================================================================

888

void AAS_CreateAllRoutingCache(void)

889

{

890

int i, j, t;

891

892

aasworld.initialized = qtrue;

893

botimport.Print(PRT_MESSAGE, "AAS_CreateAllRoutingCache\n");

894

for (i = 1; i < aasworld.numareas; i++)

895

{

896

if (!AAS_AreaReachability(i)) continue;

897

for (j = 1; j < aasworld.numareas; j++)

898

{

899

if (i == j) continue;

900

if (!AAS_AreaReachability(j)) continue;

901

t = AAS_AreaTravelTimeToGoalArea(i, aasworld.areas[i].center, j, TFL_DEFAULT);

902

//Log_Write("traveltime from %d to %d is %d", i, j, t);

903

} //end for

904

} //end for

905

aasworld.initialized = qfalse;

906

} //end of the function AAS_CreateAllRoutingCache

907

//===========================================================================

908

909

// Parameter: -

910

// Returns: -

911

// Changes Globals: -

912

//===========================================================================

913

914

//the route cache header

915

//this header is followed by numportalcache + numareacache aas_routingcache_t

916

//structures that store routing cache

917

typedef struct routecacheheader_s

918

{

919

int ident;

920

int version;

921

int numareas;

922

int numclusters;

923

int areacrc;

924

int clustercrc;

925

int numportalcache;

926

int numareacache;

927

} routecacheheader_t;

928

929

#define RCID (('C'<<24)+('R'<<16)+('E'<<8)+'M')

930

#define RCVERSION 2

931

932

//void AAS_DecompressVis(byte *in, int numareas, byte *decompressed);

933

//int AAS_CompressVis(byte *vis, int numareas, byte *dest);

934

935

void AAS_WriteRouteCache(void)

936

{

937

int i, j, numportalcache, numareacache, totalsize;

938

aas_routingcache_t *cache;

939

aas_cluster_t *cluster;

940

fileHandle_t fp;

941

char filename[MAX_QPATH];

942

routecacheheader_t routecacheheader;

943

944

numportalcache = 0;

945

for (i = 0; i < aasworld.numareas; i++)

946

{

947

for (cache = aasworld.portalcache[i]; cache; cache = cache->next)

948

{

949

numportalcache++;

950

} //end for

951

} //end for

952

numareacache = 0;

953

for (i = 0; i < aasworld.numclusters; i++)

954

{

955

cluster = &aasworld.clusters[i];

956

for (j = 0; j < cluster->numareas; j++)

957

{

958

for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)

959

{

960

numareacache++;

961

} //end for

962

} //end for

963

} //end for

964

// open the file for writing

965

Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);

966

botimport.FS_FOpenFile( filename, &fp, FS_WRITE );

967

if (!fp)

968

{

969

AAS_Error("Unable to open file: %s\n", filename);

970

return;

971

} //end if

972

//create the header

973

routecacheheader.ident = RCID;

974

routecacheheader.version = RCVERSION;

975

routecacheheader.numareas = aasworld.numareas;

976

routecacheheader.numclusters = aasworld.numclusters;

977

routecacheheader.areacrc = CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas );

978

routecacheheader.clustercrc = CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters );

979

routecacheheader.numportalcache = numportalcache;

980

routecacheheader.numareacache = numareacache;

981

//write the header

982

botimport.FS_Write(&routecacheheader, sizeof(routecacheheader_t), fp);

983

984

totalsize = 0;

985

//write all the cache

986

for (i = 0; i < aasworld.numareas; i++)

987

{

988

for (cache = aasworld.portalcache[i]; cache; cache = cache->next)

989

{

990

botimport.FS_Write(cache, cache->size, fp);

991

totalsize += cache->size;

992

} //end for

993

} //end for

994

for (i = 0; i < aasworld.numclusters; i++)

995

{

996

cluster = &aasworld.clusters[i];

997

for (j = 0; j < cluster->numareas; j++)

998

{

999

for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)

1000

{

1001

botimport.FS_Write(cache, cache->size, fp);

1002

totalsize += cache->size;

1003

} //end for

1004

} //end for

1005

} //end for

1006

// write the visareas

1007

1008

for (i = 0; i < aasworld.numareas; i++)

1009

{

1010

if (!aasworld.areavisibility[i]) {

1011

size = 0;

1012

botimport.FS_Write(&size, sizeof(int), fp);

1013

continue;

1014

}

1015

AAS_DecompressVis( aasworld.areavisibility[i], aasworld.numareas, aasworld.decompressedvis );

1016

size = AAS_CompressVis( aasworld.decompressedvis, aasworld.numareas, aasworld.decompressedvis );

1017

botimport.FS_Write(&size, sizeof(int), fp);

1018

botimport.FS_Write(aasworld.decompressedvis, size, fp);

1019

}

1020

1021

1022

botimport.FS_FCloseFile(fp);

1023

botimport.Print(PRT_MESSAGE, "\nroute cache written to %s\n", filename);

1024

botimport.Print(PRT_MESSAGE, "written %d bytes of routing cache\n", totalsize);

1025

} //end of the function AAS_WriteRouteCache

1026

//===========================================================================

1027

1028

// Parameter: -

1029

// Returns: -

1030

// Changes Globals: -

1031

//===========================================================================

1032

aas_routingcache_t *AAS_ReadCache(fileHandle_t fp)

1033

{

1034

int size;

1035

aas_routingcache_t *cache;

1036

1037

botimport.FS_Read(&size, sizeof(size), fp);

1038

cache = (aas_routingcache_t *) GetMemory(size);

1039

cache->size = size;

1040

botimport.FS_Read((unsigned char *)cache + sizeof(size), size - sizeof(size), fp);

1041

cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t) - sizeof(unsigned short) +

1042

(size - sizeof(aas_routingcache_t) + sizeof(unsigned short)) / 3 * 2;

1043

return cache;

1044

} //end of the function AAS_ReadCache

1045

//===========================================================================

1046

1047

// Parameter: -

1048

// Returns: -

1049

// Changes Globals: -

1050

//===========================================================================

1051

int AAS_ReadRouteCache(void)

1052

{

1053

int i, clusterareanum;//, size;

1054

fileHandle_t fp;

1055

char filename[MAX_QPATH];

1056

routecacheheader_t routecacheheader;

1057

aas_routingcache_t *cache;

1058

1059

Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);

1060

botimport.FS_FOpenFile( filename, &fp, FS_READ );

1061

if (!fp)

1062

{

1063

return qfalse;

1064

} //end if

1065

botimport.FS_Read(&routecacheheader, sizeof(routecacheheader_t), fp );

1066

if (routecacheheader.ident != RCID)

1067

{

1068

AAS_Error("%s is not a route cache dump\n");

1069

return qfalse;

1070

} //end if

1071

if (routecacheheader.version != RCVERSION)

1072

{

1073

AAS_Error("route cache dump has wrong version %d, should be %d", routecacheheader.version, RCVERSION);

1074

return qfalse;

1075

} //end if

1076

if (routecacheheader.numareas != aasworld.numareas)

1077

{

1078

//AAS_Error("route cache dump has wrong number of areas\n");

1079

return qfalse;

1080

} //end if

1081

if (routecacheheader.numclusters != aasworld.numclusters)

1082

{

1083

//AAS_Error("route cache dump has wrong number of clusters\n");

1084

return qfalse;

1085

} //end if

1086

if (routecacheheader.areacrc !=

1087

CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas ))

1088

{

1089

//AAS_Error("route cache dump area CRC incorrect\n");

1090

return qfalse;

1091

} //end if

1092

if (routecacheheader.clustercrc !=

1093

CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters ))

1094

{

1095

//AAS_Error("route cache dump cluster CRC incorrect\n");

1096

return qfalse;

1097

} //end if

1098

//read all the portal cache

1099

for (i = 0; i < routecacheheader.numportalcache; i++)

1100

{

1101

cache = AAS_ReadCache(fp);

1102

cache->next = aasworld.portalcache[cache->areanum];

1103

cache->prev = NULL;

1104

if (aasworld.portalcache[cache->areanum])

1105

aasworld.portalcache[cache->areanum]->prev = cache;

1106

aasworld.portalcache[cache->areanum] = cache;

1107

} //end for

1108

//read all the cluster area cache

1109

for (i = 0; i < routecacheheader.numareacache; i++)

1110

{

1111

cache = AAS_ReadCache(fp);

1112

clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);

1113

cache->next = aasworld.clusterareacache[cache->cluster][clusterareanum];

1114

cache->prev = NULL;

1115

if (aasworld.clusterareacache[cache->cluster][clusterareanum])

1116

aasworld.clusterareacache[cache->cluster][clusterareanum]->prev = cache;

1117

aasworld.clusterareacache[cache->cluster][clusterareanum] = cache;

1118

} //end for

1119

// read the visareas

1120

1121

aasworld.areavisibility = (byte **) GetClearedMemory(aasworld.numareas * sizeof(byte *));

1122

aasworld.decompressedvis = (byte *) GetClearedMemory(aasworld.numareas * sizeof(byte));

1123

for (i = 0; i < aasworld.numareas; i++)

1124

{

1125

botimport.FS_Read(&size, sizeof(size), fp );

1126

if (size) {

1127

aasworld.areavisibility[i] = (byte *) GetMemory(size);

1128

botimport.FS_Read(aasworld.areavisibility[i], size, fp );

1129

}

1130

}

1131

1132

1133

botimport.FS_FCloseFile(fp);

1134

return qtrue;

1135

} //end of the function AAS_ReadRouteCache

1136

//===========================================================================

1137

1138

// Parameter: -

1139

// Returns: -

1140

// Changes Globals: -

1141

//===========================================================================

1142

#define MAX_REACHABILITYPASSAREAS 32

1143

1144

void AAS_InitReachabilityAreas(void)

1145

{

1146

int i, j, numareas, areas[MAX_REACHABILITYPASSAREAS];

1147

int numreachareas;

1148

aas_reachability_t *reach;

1149

vec3_t start, end;

1150

1151

if (aasworld.reachabilityareas)

1152

FreeMemory(aasworld.reachabilityareas);

1153

if (aasworld.reachabilityareaindex)

1154

FreeMemory(aasworld.reachabilityareaindex);

1155

1156

aasworld.reachabilityareas = (aas_reachabilityareas_t *)

1157

GetClearedMemory(aasworld.reachabilitysize * sizeof(aas_reachabilityareas_t));

1158

aasworld.reachabilityareaindex = (int *)

1159

GetClearedMemory(aasworld.reachabilitysize * MAX_REACHABILITYPASSAREAS * sizeof(int));

1160

numreachareas = 0;

1161

for (i = 0; i < aasworld.reachabilitysize; i++)

1162

{

1163

reach = &aasworld.reachability[i];

1164

numareas = 0;

1165

switch(reach->traveltype & TRAVELTYPE_MASK)

1166

{

1167

//trace areas from start to end

1168

case TRAVEL_BARRIERJUMP:

1169

case TRAVEL_WATERJUMP:

1170

VectorCopy(reach->start, end);

1171

end[2] = reach->end[2];

1172

numareas = AAS_TraceAreas(reach->start, end, areas, NULL, MAX_REACHABILITYPASSAREAS);

1173

break;

1174

case TRAVEL_WALKOFFLEDGE:

1175

VectorCopy(reach->end, start);

1176

start[2] = reach->start[2];

1177

numareas = AAS_TraceAreas(start, reach->end, areas, NULL, MAX_REACHABILITYPASSAREAS);

1178

break;

1179

case TRAVEL_GRAPPLEHOOK:

1180

numareas = AAS_TraceAreas(reach->start, reach->end, areas, NULL, MAX_REACHABILITYPASSAREAS);

1181

break;

1182

1183

//trace arch

1184

case TRAVEL_JUMP: break;

1185

case TRAVEL_ROCKETJUMP: break;

1186

case TRAVEL_BFGJUMP: break;

1187

case TRAVEL_JUMPPAD: break;

1188

1189

//trace from reach->start to entity center, along entity movement

1190

//and from entity center to reach->end

1191

case TRAVEL_ELEVATOR: break;

1192

case TRAVEL_FUNCBOB: break;

1193

1194

//no areas in between

1195

case TRAVEL_WALK: break;

1196

case TRAVEL_CROUCH: break;

1197

case TRAVEL_LADDER: break;

1198

case TRAVEL_SWIM: break;

1199

case TRAVEL_TELEPORT: break;

1200

default: break;

1201

} //end switch

1202

aasworld.reachabilityareas[i].firstarea = numreachareas;

1203

aasworld.reachabilityareas[i].numareas = numareas;

1204

for (j = 0; j < numareas; j++)

1205

{

1206

aasworld.reachabilityareaindex[numreachareas++] = areas[j];

1207

} //end for

1208

} //end for

1209

} //end of the function AAS_InitReachabilityAreas

1210

//===========================================================================

1211

1212

// Parameter: -

1213

// Returns: -

1214

// Changes Globals: -

1215

//===========================================================================

1216

void AAS_InitRouting(void)

1217

{

1218

AAS_InitTravelFlagFromType();

1219

1220

AAS_InitAreaContentsTravelFlags();

1221

//initialize the routing update fields

1222

AAS_InitRoutingUpdate();

1223

//create reversed reachability links used by the routing update algorithm

1224

AAS_CreateReversedReachability();

1225

//initialize the cluster cache

1226

AAS_InitClusterAreaCache();

1227

//initialize portal cache

1228

AAS_InitPortalCache();

1229

//initialize the area travel times

1230

AAS_CalculateAreaTravelTimes();

1231

//calculate the maximum travel times through portals

1232

AAS_InitPortalMaxTravelTimes();

1233

//get the areas reachabilities go through

1234

AAS_InitReachabilityAreas();

1235

1236

#ifdef ROUTING_DEBUG

1237

numareacacheupdates = 0;

1238

numportalcacheupdates = 0;

1239

#endif //ROUTING_DEBUG

1240

1241

routingcachesize = 0;

1242

max_routingcachesize = 1024 * (int) LibVarValue("max_routingcache", "4096");

1243

// read any routing cache if available

1244

AAS_ReadRouteCache();

1245

} //end of the function AAS_InitRouting

1246

//===========================================================================

1247

1248

// Parameter: -

1249

// Returns: -

1250

// Changes Globals: -

1251

//===========================================================================

1252

void AAS_FreeRoutingCaches(void)

1253

{

1254

// free all the existing cluster area cache

1255

AAS_FreeAllClusterAreaCache();

1256

// free all the existing portal cache

1257

AAS_FreeAllPortalCache();

1258

// free cached travel times within areas

1259

if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);

1260

aasworld.areatraveltimes = NULL;

1261

// free cached maximum travel time through cluster portals

1262

if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);

1263

aasworld.portalmaxtraveltimes = NULL;

1264

// free reversed reachability links

1265

if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);

1266

aasworld.reversedreachability = NULL;

1267

// free routing algorithm memory

1268

if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);

1269

aasworld.areaupdate = NULL;

1270

if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);

1271

aasworld.portalupdate = NULL;

1272

// free lists with areas the reachabilities go through

1273

if (aasworld.reachabilityareas) FreeMemory(aasworld.reachabilityareas);

1274

aasworld.reachabilityareas = NULL;

1275

// free the reachability area index

1276

if (aasworld.reachabilityareaindex) FreeMemory(aasworld.reachabilityareaindex);

1277

aasworld.reachabilityareaindex = NULL;

1278

// free area contents travel flags look up table

1279

if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);

1280

aasworld.areacontentstravelflags = NULL;

1281

} //end of the function AAS_FreeRoutingCaches

1282

//===========================================================================

1283

// update the given routing cache

1284

1285

// Parameter: areacache : routing cache to update

1286

// Returns: -

1287

// Changes Globals: -

1288

//===========================================================================

1289

void AAS_UpdateAreaRoutingCache(aas_routingcache_t *areacache)

1290

{

1291

int i, nextareanum, cluster, badtravelflags, clusterareanum, linknum;

1292

int numreachabilityareas;

1293

unsigned short int t, startareatraveltimes[128]; //NOTE: not more than 128 reachabilities per area allowed

1294

aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;

1295

aas_reachability_t *reach;

1296

aas_reversedreachability_t *revreach;

1297

aas_reversedlink_t *revlink;

1298

1299

#ifdef ROUTING_DEBUG

1300

numareacacheupdates++;

1301

#endif //ROUTING_DEBUG

1302

//number of reachability areas within this cluster

1303

numreachabilityareas = aasworld.clusters[areacache->cluster].numreachabilityareas;

1304

1305

aasworld.frameroutingupdates++;

1306

//clear the routing update fields

1307

// Com_Memset(aasworld.areaupdate, 0, aasworld.numareas * sizeof(aas_routingupdate_t));

1308

1309

badtravelflags = ~areacache->travelflags;

1310

1311

clusterareanum = AAS_ClusterAreaNum(areacache->cluster, areacache->areanum);

1312

if (clusterareanum >= numreachabilityareas) return;

1313

1314

Com_Memset(startareatraveltimes, 0, sizeof(startareatraveltimes));

1315

1316

curupdate = &aasworld.areaupdate[clusterareanum];

1317

curupdate->areanum = areacache->areanum;

1318

//VectorCopy(areacache->origin, curupdate->start);

1319

curupdate->areatraveltimes = startareatraveltimes;

1320

curupdate->tmptraveltime = areacache->starttraveltime;

1321

1322

areacache->traveltimes[clusterareanum] = areacache->starttraveltime;

1323

//put the area to start with in the current read list

1324

curupdate->next = NULL;

1325

curupdate->prev = NULL;

1326

updateliststart = curupdate;

1327

updatelistend = curupdate;

1328

//while there are updates in the current list

1329

while (updateliststart)

1330

{

1331

curupdate = updateliststart;

1332

1333

if (curupdate->next) curupdate->next->prev = NULL;

1334

else updatelistend = NULL;

1335

updateliststart = curupdate->next;

1336

1337

curupdate->inlist = qfalse;

1338

//check all reversed reachability links

1339

revreach = &aasworld.reversedreachability[curupdate->areanum];

1340

1341

for (i = 0, revlink = revreach->first; revlink; revlink = revlink->next, i++)

1342

{

1343

linknum = revlink->linknum;

1344

reach = &aasworld.reachability[linknum];

1345

//if there is used an undesired travel type

1346

if (AAS_TravelFlagForType_inline(reach->traveltype) & badtravelflags) continue;

1347

//if not allowed to enter the next area

1348

if (aasworld.areasettings[reach->areanum].areaflags & AREA_DISABLED) continue;

1349

//if the next area has a not allowed travel flag

1350

if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & badtravelflags) continue;

1351

//number of the area the reversed reachability leads to

1352

nextareanum = revlink->areanum;

1353

//get the cluster number of the area

1354

cluster = aasworld.areasettings[nextareanum].cluster;

1355

//don't leave the cluster

1356

if (cluster > 0 && cluster != areacache->cluster) continue;

1357

//get the number of the area in the cluster

1358

clusterareanum = AAS_ClusterAreaNum(areacache->cluster, nextareanum);

1359

if (clusterareanum >= numreachabilityareas) continue;

1360

//time already travelled plus the traveltime through

1361

//the current area plus the travel time from the reachability

1362

t = curupdate->tmptraveltime +

1363

//AAS_AreaTravelTime(curupdate->areanum, curupdate->start, reach->end) +

1364

curupdate->areatraveltimes[i] +

1365

reach->traveltime;

1366

1367

if (!areacache->traveltimes[clusterareanum] ||

1368

areacache->traveltimes[clusterareanum] > t)

1369

{

1370

areacache->traveltimes[clusterareanum] = t;

1371

areacache->reachabilities[clusterareanum] = linknum - aasworld.areasettings[nextareanum].firstreachablearea;

1372

nextupdate = &aasworld.areaupdate[clusterareanum];

1373

nextupdate->areanum = nextareanum;

1374

nextupdate->tmptraveltime = t;

1375

//VectorCopy(reach->start, nextupdate->start);

1376

nextupdate->areatraveltimes = aasworld.areatraveltimes[nextareanum][linknum -

1377

aasworld.areasettings[nextareanum].firstreachablearea];

1378

if (!nextupdate->inlist)

1379

{

1380

// we add the update to the end of the list

1381

// we could also use a B+ tree to have a real sorted list

1382

// on travel time which makes for faster routing updates

1383

nextupdate->next = NULL;

1384

nextupdate->prev = updatelistend;

1385

if (updatelistend) updatelistend->next = nextupdate;

1386

else updateliststart = nextupdate;

1387

updatelistend = nextupdate;

1388

nextupdate->inlist = qtrue;

1389

} //end if

1390

} //end if

1391

} //end for

1392

} //end while

1393

} //end of the function AAS_UpdateAreaRoutingCache

1394

//===========================================================================

1395

1396

// Parameter: -

1397

// Returns: -

1398

// Changes Globals: -

1399

//===========================================================================

1400

aas_routingcache_t *AAS_GetAreaRoutingCache(int clusternum, int areanum, int travelflags)

1401

{

1402

int clusterareanum;

1403

aas_routingcache_t *cache, *clustercache;

1404

1405

//number of the area in the cluster

1406

clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);

1407

//pointer to the cache for the area in the cluster

1408

clustercache = aasworld.clusterareacache[clusternum][clusterareanum];

1409

//find the cache without undesired travel flags

1410

for (cache = clustercache; cache; cache = cache->next)

1411

{

1412

//if there aren't used any undesired travel types for the cache

1413

if (cache->travelflags == travelflags) break;

1414

} //end for

1415

//if there was no cache

1416

if (!cache)

1417

{

1418

cache = AAS_AllocRoutingCache(aasworld.clusters[clusternum].numreachabilityareas);

1419

cache->cluster = clusternum;

1420

cache->areanum = areanum;

1421

VectorCopy(aasworld.areas[areanum].center, cache->origin);

1422

cache->starttraveltime = 1;

1423

cache->travelflags = travelflags;

1424

cache->prev = NULL;

1425

cache->next = clustercache;

1426

if (clustercache) clustercache->prev = cache;

1427

aasworld.clusterareacache[clusternum][clusterareanum] = cache;

1428

AAS_UpdateAreaRoutingCache(cache);

1429

} //end if

1430

else

1431

{

1432

AAS_UnlinkCache(cache);

1433

} //end else

1434

//the cache has been accessed

1435

cache->time = AAS_RoutingTime();

1436

cache->type = CACHETYPE_AREA;

1437

AAS_LinkCache(cache);

1438

return cache;

1439

} //end of the function AAS_GetAreaRoutingCache

1440

//===========================================================================

1441

1442

// Parameter: -

1443

// Returns: -

1444

// Changes Globals: -

1445

//===========================================================================

1446

void AAS_UpdatePortalRoutingCache(aas_routingcache_t *portalcache)

1447

{

1448

int i, portalnum, clusterareanum, clusternum;

1449

unsigned short int t;

1450

aas_portal_t *portal;

1451

aas_cluster_t *cluster;

1452

aas_routingcache_t *cache;

1453

aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;

1454

1455

#ifdef ROUTING_DEBUG

1456

numportalcacheupdates++;

1457

#endif //ROUTING_DEBUG

1458

//clear the routing update fields

1459

// Com_Memset(aasworld.portalupdate, 0, (aasworld.numportals+1) * sizeof(aas_routingupdate_t));

1460

1461

curupdate = &aasworld.portalupdate[aasworld.numportals];

1462

curupdate->cluster = portalcache->cluster;

1463

curupdate->areanum = portalcache->areanum;

1464

curupdate->tmptraveltime = portalcache->starttraveltime;

1465

//if the start area is a cluster portal, store the travel time for that portal

1466

clusternum = aasworld.areasettings[portalcache->areanum].cluster;

1467

if (clusternum < 0)

1468

{

1469

portalcache->traveltimes[-clusternum] = portalcache->starttraveltime;

1470

} //end if

1471

//put the area to start with in the current read list

1472

curupdate->next = NULL;

1473

curupdate->prev = NULL;

1474

updateliststart = curupdate;

1475

updatelistend = curupdate;

1476

//while there are updates in the current list

1477

while (updateliststart)

1478

{

1479

curupdate = updateliststart;

1480

//remove the current update from the list

1481

if (curupdate->next) curupdate->next->prev = NULL;

1482

else updatelistend = NULL;

1483

updateliststart = curupdate->next;

1484

//current update is removed from the list

1485

curupdate->inlist = qfalse;

1486

1487

cluster = &aasworld.clusters[curupdate->cluster];

1488

1489

cache = AAS_GetAreaRoutingCache(curupdate->cluster,

1490

curupdate->areanum, portalcache->travelflags);

1491

//take all portals of the cluster

1492

for (i = 0; i < cluster->numportals; i++)

1493

{

1494

portalnum = aasworld.portalindex[cluster->firstportal + i];

1495

portal = &aasworld.portals[portalnum];

1496

//if this is the portal of the current update continue

1497

if (portal->areanum == curupdate->areanum) continue;

1498

1499

clusterareanum = AAS_ClusterAreaNum(curupdate->cluster, portal->areanum);

1500

if (clusterareanum >= cluster->numreachabilityareas) continue;

1501

1502

t = cache->traveltimes[clusterareanum];

1503

if (!t) continue;

1504

t += curupdate->tmptraveltime;

1505

1506

if (!portalcache->traveltimes[portalnum] ||

1507

portalcache->traveltimes[portalnum] > t)

1508

{

1509

portalcache->traveltimes[portalnum] = t;

1510

nextupdate = &aasworld.portalupdate[portalnum];

1511

if (portal->frontcluster == curupdate->cluster)

1512

{

1513

nextupdate->cluster = portal->backcluster;

1514

} //end if

1515

else

1516

{

1517

nextupdate->cluster = portal->frontcluster;

1518

} //end else

1519

nextupdate->areanum = portal->areanum;

1520

//add travel time through the actual portal area for the next update

1521

nextupdate->tmptraveltime = t + aasworld.portalmaxtraveltimes[portalnum];

1522

if (!nextupdate->inlist)

1523

{

1524

// we add the update to the end of the list

1525

// we could also use a B+ tree to have a real sorted list

1526

// on travel time which makes for faster routing updates

1527

nextupdate->next = NULL;

1528

nextupdate->prev = updatelistend;

1529

if (updatelistend) updatelistend->next = nextupdate;

1530

else updateliststart = nextupdate;

1531

updatelistend = nextupdate;

1532

nextupdate->inlist = qtrue;

1533

} //end if

1534

} //end if

1535

} //end for

1536

} //end while

1537

} //end of the function AAS_UpdatePortalRoutingCache

1538

//===========================================================================

1539

1540

// Parameter: -

1541

// Returns: -

1542

// Changes Globals: -

1543

//===========================================================================

1544

aas_routingcache_t *AAS_GetPortalRoutingCache(int clusternum, int areanum, int travelflags)

1545

{

1546

aas_routingcache_t *cache;

1547

1548

//find the cached portal routing if existing

1549

for (cache = aasworld.portalcache[areanum]; cache; cache = cache->next)

1550

{

1551

if (cache->travelflags == travelflags) break;

1552

} //end for

1553

//if the portal routing isn't cached

1554

if (!cache)

1555

{

1556

cache = AAS_AllocRoutingCache(aasworld.numportals);

1557

cache->cluster = clusternum;

1558

cache->areanum = areanum;

1559

VectorCopy(aasworld.areas[areanum].center, cache->origin);

1560

cache->starttraveltime = 1;

1561

cache->travelflags = travelflags;

1562

//add the cache to the cache list

1563

cache->prev = NULL;

1564

cache->next = aasworld.portalcache[areanum];

1565

if (aasworld.portalcache[areanum]) aasworld.portalcache[areanum]->prev = cache;

1566

aasworld.portalcache[areanum] = cache;

1567

//update the cache

1568

AAS_UpdatePortalRoutingCache(cache);

1569

} //end if

1570

else

1571

{

1572

AAS_UnlinkCache(cache);

1573

} //end else

1574

//the cache has been accessed

1575

cache->time = AAS_RoutingTime();

1576

cache->type = CACHETYPE_PORTAL;

1577

AAS_LinkCache(cache);

1578

return cache;

1579

} //end of the function AAS_GetPortalRoutingCache

1580

//===========================================================================

1581

1582

// Parameter: -

1583

// Returns: -

1584

// Changes Globals: -

1585

//===========================================================================

1586

int AAS_AreaRouteToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags, int *traveltime, int *reachnum)

1587

{

1588

int clusternum, goalclusternum, portalnum, i, clusterareanum, bestreachnum;

1589

unsigned short int t, besttime;

1590

aas_portal_t *portal;

1591

aas_cluster_t *cluster;

1592

aas_routingcache_t *areacache, *portalcache;

1593

aas_reachability_t *reach;

1594

1595

if (!aasworld.initialized) return qfalse;

1596

1597

if (areanum == goalareanum)

1598

{

1599

*traveltime = 1;

1600

*reachnum = 0;

1601

return qtrue;

1602

}

1603

1604

if (areanum <= 0 || areanum >= aasworld.numareas)

1605

{

1606

if (bot_developer)

1607

{

1608

botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: areanum %d out of range\n", areanum);

1609

} //end if

1610

return qfalse;

1611

} //end if

1612

if (goalareanum <= 0 || goalareanum >= aasworld.numareas)

1613

{

1614

if (bot_developer)

1615

{

1616

botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: goalareanum %d out of range\n", goalareanum);

1617

} //end if

1618

return qfalse;

1619

} //end if

1620

// make sure the routing cache doesn't grow to large

1621

while(AvailableMemory() < 1 * 1024 * 1024) {

1622

if (!AAS_FreeOldestCache()) break;

1623

}

1624

1625

if (AAS_AreaDoNotEnter(areanum) || AAS_AreaDoNotEnter(goalareanum))

1626

{

1627

travelflags |= TFL_DONOTENTER;

1628

} //end if

1629

//NOTE: the number of routing updates is limited per frame

1630

1631

if (aasworld.frameroutingupdates > MAX_FRAMEROUTINGUPDATES)

1632

{

1633

#ifdef DEBUG

1634

//Log_Write("WARNING: AAS_AreaTravelTimeToGoalArea: frame routing updates overflowed");

1635

#endif

1636

return 0;

1637

} //end if

1638

1639

1640

clusternum = aasworld.areasettings[areanum].cluster;

1641

goalclusternum = aasworld.areasettings[goalareanum].cluster;

1642

//check if the area is a portal of the goal area cluster

1643

if (clusternum < 0 && goalclusternum > 0)

1644

{

1645

portal = &aasworld.portals[-clusternum];

1646

if (portal->frontcluster == goalclusternum ||

1647

portal->backcluster == goalclusternum)

1648

{

1649

clusternum = goalclusternum;

1650

} //end if

1651

} //end if

1652

//check if the goalarea is a portal of the area cluster

1653

else if (clusternum > 0 && goalclusternum < 0)

1654

{

1655

portal = &aasworld.portals[-goalclusternum];

1656

if (portal->frontcluster == clusternum ||

1657

portal->backcluster == clusternum)

1658

{

1659

goalclusternum = clusternum;

1660

} //end if

1661

} //end if

1662

//if both areas are in the same cluster

1663

//NOTE: there might be a shorter route via another cluster!!! but we don't care

1664

if (clusternum > 0 && goalclusternum > 0 && clusternum == goalclusternum)

1665

{

1666

1667

areacache = AAS_GetAreaRoutingCache(clusternum, goalareanum, travelflags);

1668

//the number of the area in the cluster

1669

clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);

1670

//the cluster the area is in

1671

cluster = &aasworld.clusters[clusternum];

1672

//if the area is NOT a reachability area

1673

if (clusterareanum >= cluster->numreachabilityareas) return 0;

1674

//if it is possible to travel to the goal area through this cluster

1675

if (areacache->traveltimes[clusterareanum] != 0)

1676

{

1677

*reachnum = aasworld.areasettings[areanum].firstreachablearea +

1678

areacache->reachabilities[clusterareanum];

1679

if (!origin) {

1680

*traveltime = areacache->traveltimes[clusterareanum];

1681

return qtrue;

1682

}

1683

reach = &aasworld.reachability[*reachnum];

1684

*traveltime = areacache->traveltimes[clusterareanum] +

1685

AAS_AreaTravelTime(areanum, origin, reach->start);

1686

1687

return qtrue;

1688

} //end if

1689

} //end if

1690

1691

clusternum = aasworld.areasettings[areanum].cluster;

1692

goalclusternum = aasworld.areasettings[goalareanum].cluster;

1693

//if the goal area is a portal

1694

if (goalclusternum < 0)

1695

{

1696

//just assume the goal area is part of the front cluster

1697

portal = &aasworld.portals[-goalclusternum];

1698

goalclusternum = portal->frontcluster;

1699

} //end if

1700

//get the portal routing cache

1701

portalcache = AAS_GetPortalRoutingCache(goalclusternum, goalareanum, travelflags);

1702

//if the area is a cluster portal, read directly from the portal cache

1703

if (clusternum < 0)

1704

{

1705

*traveltime = portalcache->traveltimes[-clusternum];

1706

*reachnum = aasworld.areasettings[areanum].firstreachablearea +

1707

portalcache->reachabilities[-clusternum];

1708

return qtrue;

1709

} //end if

1710

1711

besttime = 0;

1712

bestreachnum = -1;

1713

//the cluster the area is in

1714

cluster = &aasworld.clusters[clusternum];

1715

//find the portal of the area cluster leading towards the goal area

1716

for (i = 0; i < cluster->numportals; i++)

1717

{

1718

portalnum = aasworld.portalindex[cluster->firstportal + i];

1719

//if the goal area isn't reachable from the portal

1720

if (!portalcache->traveltimes[portalnum]) continue;

1721

1722

portal = &aasworld.portals[portalnum];

1723

//get the cache of the portal area

1724

areacache = AAS_GetAreaRoutingCache(clusternum, portal->areanum, travelflags);

1725

//current area inside the current cluster

1726

clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);

1727

//if the area is NOT a reachability area

1728

if (clusterareanum >= cluster->numreachabilityareas) continue;

1729

//if the portal is NOT reachable from this area

1730

if (!areacache->traveltimes[clusterareanum]) continue;

1731

//total travel time is the travel time the portal area is from

1732

//the goal area plus the travel time towards the portal area

1733

t = portalcache->traveltimes[portalnum] + areacache->traveltimes[clusterareanum];

1734

//FIXME: add the exact travel time through the actual portal area

1735

//NOTE: for now we just add the largest travel time through the portal area

1736

// because we can't directly calculate the exact travel time

1737

// to be more specific we don't know which reachability was used to travel

1738

// into the portal area

1739

t += aasworld.portalmaxtraveltimes[portalnum];

1740

1741

if (origin)

1742

{

1743

*reachnum = aasworld.areasettings[areanum].firstreachablearea +

1744

areacache->reachabilities[clusterareanum];

1745

reach = aasworld.reachability + *reachnum;

1746

t += AAS_AreaTravelTime(areanum, origin, reach->start);

1747

} //end if

1748

//if the time is better than the one already found

1749

if (!besttime || t < besttime)

1750

{

1751

bestreachnum = *reachnum;

1752

besttime = t;

1753

} //end if

1754

} //end for

1755

if (bestreachnum < 0) {

1756

return qfalse;

1757

}

1758

*reachnum = bestreachnum;

1759

*traveltime = besttime;

1760

return qtrue;

1761

} //end of the function AAS_AreaRouteToGoalArea

1762

//===========================================================================

1763

1764

// Parameter: -

1765

// Returns: -

1766

// Changes Globals: -

1767

//===========================================================================

1768

int AAS_AreaTravelTimeToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags)

1769

{

1770

int traveltime, reachnum;

1771

1772

if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))

1773

{

1774

return traveltime;

1775

}

1776

return 0;

1777

} //end of the function AAS_AreaTravelTimeToGoalArea

1778

//===========================================================================

1779

1780

// Parameter: -

1781

// Returns: -

1782

// Changes Globals: -

1783

//===========================================================================

1784

int AAS_AreaReachabilityToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags)

1785

{

1786

int traveltime, reachnum;

1787

1788

if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))

1789

{

1790

return reachnum;

1791

}

1792

return 0;

1793

} //end of the function AAS_AreaReachabilityToGoalArea

1794

//===========================================================================

1795

// predict the route and stop on one of the stop events

1796

1797

// Parameter: -

1798

// Returns: -

1799

// Changes Globals: -

1800

//===========================================================================

1801

int AAS_PredictRoute(struct aas_predictroute_s *route, int areanum, vec3_t origin,

1802

int goalareanum, int travelflags, int maxareas, int maxtime,

1803

int stopevent, int stopcontents, int stoptfl, int stopareanum)

1804

{

1805

int curareanum, reachnum, i, j, testareanum;

1806

vec3_t curorigin;

1807

aas_reachability_t *reach;

1808

aas_reachabilityareas_t *reachareas;

1809

1810

//init output

1811

route->stopevent = RSE_NONE;

1812

route->endarea = goalareanum;

1813

route->endcontents = 0;

1814

route->endtravelflags = 0;

1815

VectorCopy(origin, route->endpos);

1816

route->time = 0;

1817

1818

curareanum = areanum;

1819

VectorCopy(origin, curorigin);

1820

1821

for (i = 0; curareanum != goalareanum && (!maxareas || i < maxareas) && i < aasworld.numareas; i++)

1822

{

1823

reachnum = AAS_AreaReachabilityToGoalArea(curareanum, curorigin, goalareanum, travelflags);

1824

if (!reachnum)

1825

{

1826

route->stopevent = RSE_NOROUTE;

1827

return qfalse;

1828

} //end if

1829

reach = &aasworld.reachability[reachnum];

1830

1831

if (stopevent & RSE_USETRAVELTYPE)

1832

{

1833

if (AAS_TravelFlagForType_inline(reach->traveltype) & stoptfl)

1834

{

1835

route->stopevent = RSE_USETRAVELTYPE;

1836

route->endarea = curareanum;

1837

route->endcontents = aasworld.areasettings[curareanum].contents;

1838

route->endtravelflags = AAS_TravelFlagForType_inline(reach->traveltype);

1839

VectorCopy(reach->start, route->endpos);

1840

return qtrue;

1841

} //end if

1842

if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & stoptfl)

1843

{

1844

route->stopevent = RSE_USETRAVELTYPE;

1845

route->endarea = reach->areanum;

1846

route->endcontents = aasworld.areasettings[reach->areanum].contents;

1847

route->endtravelflags = AAS_AreaContentsTravelFlags_inline(reach->areanum);

1848

VectorCopy(reach->end, route->endpos);

1849

route->time += AAS_AreaTravelTime(areanum, origin, reach->start);

1850

route->time += reach->traveltime;

1851

return qtrue;

1852

} //end if

1853

} //end if

1854

reachareas = &aasworld.reachabilityareas[reachnum];

1855

for (j = 0; j < reachareas->numareas + 1; j++)

1856

{

1857

if (j >= reachareas->numareas)

1858

testareanum = reach->areanum;

1859

else

1860

testareanum = aasworld.reachabilityareaindex[reachareas->firstarea + j];

1861

if (stopevent & RSE_ENTERCONTENTS)

1862

{

1863

if (aasworld.areasettings[testareanum].contents & stopcontents)

1864

{

1865

route->stopevent = RSE_ENTERCONTENTS;

1866

route->endarea = testareanum;

1867

route->endcontents = aasworld.areasettings[testareanum].contents;

1868

VectorCopy(reach->end, route->endpos);

1869

route->time += AAS_AreaTravelTime(areanum, origin, reach->start);

1870

route->time += reach->traveltime;

1871

return qtrue;

1872

} //end if

1873

} //end if

1874

if (stopevent & RSE_ENTERAREA)

1875

{

1876

if (testareanum == stopareanum)

1877

{

1878

route->stopevent = RSE_ENTERAREA;

1879

route->endarea = testareanum;

1880

route->endcontents = aasworld.areasettings[testareanum].contents;

1881

VectorCopy(reach->start, route->endpos);

1882

return qtrue;

1883

} //end if

1884

} //end if

1885

} //end for

1886

1887

route->time += AAS_AreaTravelTime(areanum, origin, reach->start);

1888

route->time += reach->traveltime;

1889

route->endarea = reach->areanum;

1890

route->endcontents = aasworld.areasettings[reach->areanum].contents;

1891

route->endtravelflags = AAS_TravelFlagForType_inline(reach->traveltype);

1892

VectorCopy(reach->end, route->endpos);

1893

1894

curareanum = reach->areanum;

1895

VectorCopy(reach->end, curorigin);

1896

1897

if (maxtime && route->time > maxtime)

1898

break;

1899

} //end while

1900

if (curareanum != goalareanum)

1901

return qfalse;

1902

return qtrue;

1903

} //end of the function AAS_PredictRoute

1904

//===========================================================================

1905

1906

// Parameter: -

1907

// Returns: -

1908

// Changes Globals: -

1909

//===========================================================================

1910

int AAS_BridgeWalkable(int areanum)

1911

{

1912

return qfalse;

1913

} //end of the function AAS_BridgeWalkable

1914

//===========================================================================

1915

1916

// Parameter: -

1917

// Returns: -

1918

// Changes Globals: -

1919

//===========================================================================

1920

void AAS_ReachabilityFromNum(int num, struct aas_reachability_s *reach)

1921

{

1922

if (!aasworld.initialized)

1923

{

1924

Com_Memset(reach, 0, sizeof(aas_reachability_t));

1925

return;

1926

} //end if

1927

if (num < 0 || num >= aasworld.reachabilitysize)

1928

{

1929

Com_Memset(reach, 0, sizeof(aas_reachability_t));

1930

return;

1931

} //end if

1932

Com_Memcpy(reach, &aasworld.reachability[num], sizeof(aas_reachability_t));;

1933

} //end of the function AAS_ReachabilityFromNum

1934

//===========================================================================

1935

1936

// Parameter: -

1937

// Returns: -

1938

// Changes Globals: -

1939

//===========================================================================

1940

int AAS_NextAreaReachability(int areanum, int reachnum)

1941

{

1942

aas_areasettings_t *settings;

1943

1944

if (!aasworld.initialized) return 0;

1945

1946

if (areanum <= 0 || areanum >= aasworld.numareas)

1947

{

1948

botimport.Print(PRT_ERROR, "AAS_NextAreaReachability: areanum %d out of range\n", areanum);

1949

return 0;

1950

} //end if

1951

1952

settings = &aasworld.areasettings[areanum];

1953

if (!reachnum)

1954

{

1955

return settings->firstreachablearea;

1956

} //end if

1957

if (reachnum < settings->firstreachablearea)

1958

{

1959

botimport.Print(PRT_FATAL, "AAS_NextAreaReachability: reachnum < settings->firstreachableara");

1960

return 0;

1961

} //end if

1962

reachnum++;

1963

if (reachnum >= settings->firstreachablearea + settings->numreachableareas)

1964

{

1965

return 0;

1966

} //end if

1967

return reachnum;

1968

} //end of the function AAS_NextAreaReachability

1969

//===========================================================================

1970

1971

// Parameter: -

1972

// Returns: -

1973

// Changes Globals: -

1974

//===========================================================================

1975

int AAS_NextModelReachability(int num, int modelnum)

1976

{

1977

int i;

1978

1979

if (num <= 0) num = 1;

1980

else if (num >= aasworld.reachabilitysize) return 0;

1981

else num++;

1982

1983

for (i = num; i < aasworld.reachabilitysize; i++)

1984

{

1985

if ((aasworld.reachability[i].traveltype & TRAVELTYPE_MASK) == TRAVEL_ELEVATOR)

1986

{

1987

if (aasworld.reachability[i].facenum == modelnum) return i;

1988

} //end if

1989

else if ((aasworld.reachability[i].traveltype & TRAVELTYPE_MASK) == TRAVEL_FUNCBOB)

1990

{

1991

if ((aasworld.reachability[i].facenum & 0x0000FFFF) == modelnum) return i;

1992

} //end if

1993

} //end for

1994

return 0;

1995

} //end of the function AAS_NextModelReachability

1996

//===========================================================================

1997

1998

// Parameter: -

1999

// Returns: -

2000

// Changes Globals: -

2001

//===========================================================================

2002

int AAS_RandomGoalArea(int areanum, int travelflags, int *goalareanum, vec3_t goalorigin)

2003

{

2004

int i, n, t;

2005

vec3_t start, end;

2006

aas_trace_t trace;

2007

2008

//if the area has no reachabilities

2009

if (!AAS_AreaReachability(areanum)) return qfalse;

2010

2011

n = aasworld.numareas * random();

2012

for (i = 0; i < aasworld.numareas; i++)

2013

{

2014

if (n <= 0) n = 1;

2015

if (n >= aasworld.numareas) n = 1;

2016

if (AAS_AreaReachability(n))

2017

{

2018

t = AAS_AreaTravelTimeToGoalArea(areanum, aasworld.areas[areanum].center, n, travelflags);

2019

//if the goal is reachable

2020

if (t > 0)

2021

{

2022

if (AAS_AreaSwim(n))

2023

{

2024

*goalareanum = n;

2025

VectorCopy(aasworld.areas[n].center, goalorigin);

2026

//botimport.Print(PRT_MESSAGE, "found random goal area %d\n", *goalareanum);

2027

return qtrue;

2028

} //end if

2029

VectorCopy(aasworld.areas[n].center, start);

2030

if (!AAS_PointAreaNum(start))

2031

Log_Write("area %d center %f %f %f in solid?", n, start[0], start[1], start[2]);

2032

VectorCopy(start, end);

2033

end[2] -= 300;

2034

trace = AAS_TraceClientBBox(start, end, PRESENCE_CROUCH, -1);

2035

if (!trace.startsolid && trace.fraction < 1 && AAS_PointAreaNum(trace.endpos) == n)

2036

{

2037

if (AAS_AreaGroundFaceArea(n) > 300)

2038

{

2039

*goalareanum = n;

2040

VectorCopy(trace.endpos, goalorigin);

2041

//botimport.Print(PRT_MESSAGE, "found random goal area %d\n", *goalareanum);

2042

return qtrue;

2043

} //end if

2044

} //end if

2045

} //end if

2046

} //end if

2047

n++;

2048

} //end for

2049

return qfalse;

2050

} //end of the function AAS_RandomGoalArea

2051

//===========================================================================

2052

2053

// Parameter: -

2054

// Returns: -

2055

// Changes Globals: -

2056

//===========================================================================

2057

int AAS_AreaVisible(int srcarea, int destarea)

2058

{

2059

return qfalse;

2060

} //end of the function AAS_AreaVisible

2061

//===========================================================================

2062

2063

// Parameter: -

2064

// Returns: -

2065

// Changes Globals: -

2066

//===========================================================================

2067

float DistancePointToLine(vec3_t v1, vec3_t v2, vec3_t point)

2068

{

2069

vec3_t vec, p2;

2070

2071

AAS_ProjectPointOntoVector(point, v1, v2, p2);

2072

VectorSubtract(point, p2, vec);

2073

return VectorLength(vec);

2074

} //end of the function DistancePointToLine

2075

//===========================================================================

2076

2077

// Parameter: -

2078

// Returns: -

2079

// Changes Globals: -

2080

//===========================================================================

2081

int AAS_NearestHideArea(int srcnum, vec3_t origin, int areanum, int enemynum, vec3_t enemyorigin, int enemyareanum, int travelflags)

2082

{

2083

int i, j, nextareanum, badtravelflags, numreach, bestarea;

2084

unsigned short int t, besttraveltime;

2085

static unsigned short int *hidetraveltimes;

2086

aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;

2087

aas_reachability_t *reach;

2088

float dist1, dist2;

2089

vec3_t v1, v2, p;

2090

qboolean startVisible;

2091

2092

2093

if (!hidetraveltimes)

2094

{

2095

hidetraveltimes = (unsigned short int *) GetClearedMemory(aasworld.numareas * sizeof(unsigned short int));

2096

} //end if

2097

else

2098

{

2099

Com_Memset(hidetraveltimes, 0, aasworld.numareas * sizeof(unsigned short int));

2100

} //end else

2101

besttraveltime = 0;

2102

bestarea = 0;

2103

//assume visible

2104

startVisible = qtrue;

2105

2106

badtravelflags = ~travelflags;

2107

2108

curupdate = &aasworld.areaupdate[areanum];

2109

curupdate->areanum = areanum;

2110

VectorCopy(origin, curupdate->start);

2111

curupdate->areatraveltimes = aasworld.areatraveltimes[areanum][0];

2112

curupdate->tmptraveltime = 0;

2113

//put the area to start with in the current read list

2114

curupdate->next = NULL;

2115

curupdate->prev = NULL;

2116

updateliststart = curupdate;

2117

updatelistend = curupdate;

2118

//while there are updates in the list

2119

while (updateliststart)

2120

{

2121

curupdate = updateliststart;

2122

2123

if (curupdate->next) curupdate->next->prev = NULL;

2124

else updatelistend = NULL;

2125

updateliststart = curupdate->next;

2126

2127

curupdate->inlist = qfalse;

2128

//check all reversed reachability links

2129

numreach = aasworld.areasettings[curupdate->areanum].numreachableareas;

2130

reach = &aasworld.reachability[aasworld.areasettings[curupdate->areanum].firstreachablearea];

2131

2132

for (i = 0; i < numreach; i++, reach++)

2133

{

2134

//if an undesired travel type is used

2135

if (AAS_TravelFlagForType_inline(reach->traveltype) & badtravelflags) continue;

2136

2137

if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & badtravelflags) continue;

2138

//number of the area the reachability leads to

2139

nextareanum = reach->areanum;

2140

// if this moves us into the enemies area, skip it

2141

if (nextareanum == enemyareanum) continue;

2142

//time already travelled plus the traveltime through

2143

//the current area plus the travel time from the reachability

2144

t = curupdate->tmptraveltime +

2145

AAS_AreaTravelTime(curupdate->areanum, curupdate->start, reach->start) +

2146

reach->traveltime;

2147

2148

//avoid going near the enemy

2149

AAS_ProjectPointOntoVector(enemyorigin, curupdate->start, reach->end, p);

2150

for (j = 0; j < 3; j++)

2151

if ((p[j] > curupdate->start[j] && p[j] > reach->end[j]) ||

2152

(p[j] < curupdate->start[j] && p[j] < reach->end[j]))

2153

break;

2154

if (j < 3)

2155

{

2156

VectorSubtract(enemyorigin, reach->end, v2);

2157

} //end if

2158

else

2159

{

2160

VectorSubtract(enemyorigin, p, v2);

2161

} //end else

2162

dist2 = VectorLength(v2);

2163

//never go through the enemy

2164

if (dist2 < 40) continue;

2165

2166

VectorSubtract(enemyorigin, curupdate->start, v1);

2167

dist1 = VectorLength(v1);

2168

2169

if (dist2 < dist1)

2170

{

2171

t += (dist1 - dist2) * 10;

2172

}

2173

// if we weren't visible when starting, make sure we don't move into their view

2174

if (!startVisible && AAS_AreaVisible(enemyareanum, nextareanum)) {

2175

continue;

2176

}

2177

2178

if (besttraveltime && t >= besttraveltime) continue;

2179

2180

if (!hidetraveltimes[nextareanum] ||

2181

hidetraveltimes[nextareanum] > t)

2182

{

2183

//if the nextarea is not visible from the enemy area

2184

if (!AAS_AreaVisible(enemyareanum, nextareanum))

2185

{

2186

besttraveltime = t;

2187

bestarea = nextareanum;

2188

} //end if

2189

hidetraveltimes[nextareanum] = t;

2190

nextupdate = &aasworld.areaupdate[nextareanum];

2191

nextupdate->areanum = nextareanum;

2192

nextupdate->tmptraveltime = t;

2193

//remember where we entered this area

2194

VectorCopy(reach->end, nextupdate->start);

2195

//if this update is not in the list yet

2196

if (!nextupdate->inlist)

2197

{

2198

//add the new update to the end of the list

2199

nextupdate->next = NULL;

2200

nextupdate->prev = updatelistend;

2201

if (updatelistend) updatelistend->next = nextupdate;

2202

else updateliststart = nextupdate;

2203

updatelistend = nextupdate;

2204

nextupdate->inlist = qtrue;

2205

} //end if

2206

} //end if

2207

} //end for

2208

} //end while

2209

return bestarea;

2210

} //end of the function AAS_NearestHideArea

Older »