world.c

   1 /*
   2 Copyright (C) 1996-1997 Id Software, Inc.
   3
   4 This program is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU General Public License
   6 as published by the Free Software Foundation; either version 2
   7 of the License, or (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12
  13 See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19 */
  20 // world.c -- world query functions
  21
  22 #include "quakedef.h"
  23
  24 /*
  25
  26 entities never clip against themselves, or their owner
  27
  28 line of sight checks trace->inopen and trace->inwater, but bullets don't
  29
  30 */
  31
  32 void World_Init(void)
  33 {
  34         Collision_Init();
  35 }
  36
  37 //============================================================================
  38
  39 // World_ClearLink is used for new headnodes
  40 void World_ClearLink (link_t *l)
  41 {
  42         l->entitynumber = 0;
  43         l->prev = l->next = l;
  44 }
  45
  46 void World_RemoveLink (link_t *l)
  47 {
  48         l->next->prev = l->prev;
  49         l->prev->next = l->next;
  50 }
  51
  52 void World_InsertLinkBefore (link_t *l, link_t *before, int entitynumber)
  53 {
  54         l->entitynumber = entitynumber;
  55         l->next = before;
  56         l->prev = before->prev;
  57         l->prev->next = l;
  58         l->next->prev = l;
  59 }
  60
  61 /*
  62 ===============================================================================
  63
  64 ENTITY AREA CHECKING
  65
  66 ===============================================================================
  67 */
  68
  69 void World_PrintAreaStats(world_t *world, const char *worldname)
  70 {
  71         Con_Printf("%s areagrid check stats: %d calls %d nodes (%f per call) %d entities (%f per call)\n", worldname, world->areagrid_stats_calls, world->areagrid_stats_nodechecks, (double) world->areagrid_stats_nodechecks / (double) world->areagrid_stats_calls, world->areagrid_stats_entitychecks, (double) world->areagrid_stats_entitychecks / (double) world->areagrid_stats_calls);
  72         world->areagrid_stats_calls = 0;
  73         world->areagrid_stats_nodechecks = 0;
  74         world->areagrid_stats_entitychecks = 0;
  75 }
  76
  77 /*
  78 ===============
  79 World_SetSize
  80
  81 ===============
  82 */
  83 void World_SetSize(world_t *world, const vec3_t mins, const vec3_t maxs)
  84 {
  85         int i;
  86         // the areagrid_marknumber is not allowed to be 0
  87         if (world->areagrid_marknumber < 1)
  88                 world->areagrid_marknumber = 1;
  89         // choose either the world box size, or a larger box to ensure the grid isn't too fine
  90         world->areagrid_size[0] = max(world->areagrid_maxs[0] - world->areagrid_mins[0], AREA_GRID * sv_areagrid_mingridsize.value);
  91         world->areagrid_size[1] = max(world->areagrid_maxs[1] - world->areagrid_mins[1], AREA_GRID * sv_areagrid_mingridsize.value);
  92         world->areagrid_size[2] = max(world->areagrid_maxs[2] - world->areagrid_mins[2], AREA_GRID * sv_areagrid_mingridsize.value);
  93         // figure out the corners of such a box, centered at the center of the world box
  94         world->areagrid_mins[0] = (world->areagrid_mins[0] + world->areagrid_maxs[0] - world->areagrid_size[0]) * 0.5f;
  95         world->areagrid_mins[1] = (world->areagrid_mins[1] + world->areagrid_maxs[1] - world->areagrid_size[1]) * 0.5f;
  96         world->areagrid_mins[2] = (world->areagrid_mins[2] + world->areagrid_maxs[2] - world->areagrid_size[2]) * 0.5f;
  97         world->areagrid_maxs[0] = (world->areagrid_mins[0] + world->areagrid_maxs[0] + world->areagrid_size[0]) * 0.5f;
  98         world->areagrid_maxs[1] = (world->areagrid_mins[1] + world->areagrid_maxs[1] + world->areagrid_size[1]) * 0.5f;
  99         world->areagrid_maxs[2] = (world->areagrid_mins[2] + world->areagrid_maxs[2] + world->areagrid_size[2]) * 0.5f;
 100         // now calculate the actual useful info from that
 101         VectorNegate(world->areagrid_mins, world->areagrid_bias);
 102         world->areagrid_scale[0] = AREA_GRID / world->areagrid_size[0];
 103         world->areagrid_scale[1] = AREA_GRID / world->areagrid_size[1];
 104         world->areagrid_scale[2] = AREA_GRID / world->areagrid_size[2];
 105         World_ClearLink(&world->areagrid_outside);
 106         for (i = 0;i < AREA_GRIDNODES;i++)
 107                 World_ClearLink(&world->areagrid[i]);
 108         if (developer.integer >= 10)
 109                 Con_Printf("areagrid settings: divisions %ix%ix1 : box %f %f %f : %f %f %f size %f %f %f grid %f %f %f (mingrid %f)\n", AREA_GRID, AREA_GRID, world->areagrid_mins[0], world->areagrid_mins[1], world->areagrid_mins[2], world->areagrid_maxs[0], world->areagrid_maxs[1], world->areagrid_maxs[2], world->areagrid_size[0], world->areagrid_size[1], world->areagrid_size[2], 1.0f / world->areagrid_scale[0], 1.0f / world->areagrid_scale[1], 1.0f / world->areagrid_scale[2], sv_areagrid_mingridsize.value);
 110 }
 111
 112 /*
 113 ===============
 114 World_UnlinkAll
 115
 116 ===============
 117 */
 118 void World_UnlinkAll(world_t *world)
 119 {
 120         int i;
 121         link_t *grid;
 122         // unlink all entities one by one
 123         grid = &world->areagrid_outside;
 124         while (grid->next != grid)
 125                 World_UnlinkEdict(PRVM_EDICT_NUM(grid->next->entitynumber));
 126         for (i = 0, grid = world->areagrid;i < AREA_GRIDNODES;i++, grid++)
 127                 while (grid->next != grid)
 128                         World_UnlinkEdict(PRVM_EDICT_NUM(grid->next->entitynumber));
 129 }
 130
 131 /*
 132 ===============
 133
 134 ===============
 135 */
 136 void World_UnlinkEdict(prvm_edict_t *ent)
 137 {
 138         int i;
 139         for (i = 0;i < ENTITYGRIDAREAS;i++)
 140         {
 141                 if (ent->priv.server->areagrid[i].prev)
 142                 {
 143                         World_RemoveLink (&ent->priv.server->areagrid[i]);
 144                         ent->priv.server->areagrid[i].prev = ent->priv.server->areagrid[i].next = NULL;
 145                 }
 146         }
 147 }
 148
 149 int World_EntitiesInBox(world_t *world, const vec3_t mins, const vec3_t maxs, int maxlist, prvm_edict_t **list)
 150 {
 151         int numlist;
 152         link_t *grid;
 153         link_t *l;
 154         prvm_edict_t *ent;
 155         int igrid[3], igridmins[3], igridmaxs[3];
 156
 157         // FIXME: if areagrid_marknumber wraps, all entities need their
 158         // ent->priv.server->areagridmarknumber reset
 159         world->areagrid_stats_calls++;
 160         world->areagrid_marknumber++;
 161         igridmins[0] = (int) floor((mins[0] + world->areagrid_bias[0]) * world->areagrid_scale[0]);
 162         igridmins[1] = (int) floor((mins[1] + world->areagrid_bias[1]) * world->areagrid_scale[1]);
 163         //igridmins[2] = (int) ((mins[2] + world->areagrid_bias[2]) * world->areagrid_scale[2]);
 164         igridmaxs[0] = (int) floor((maxs[0] + world->areagrid_bias[0]) * world->areagrid_scale[0]) + 1;
 165         igridmaxs[1] = (int) floor((maxs[1] + world->areagrid_bias[1]) * world->areagrid_scale[1]) + 1;
 166         //igridmaxs[2] = (int) ((maxs[2] + world->areagrid_bias[2]) * world->areagrid_scale[2]) + 1;
 167         igridmins[0] = max(0, igridmins[0]);
 168         igridmins[1] = max(0, igridmins[1]);
 169         //igridmins[2] = max(0, igridmins[2]);
 170         igridmaxs[0] = min(AREA_GRID, igridmaxs[0]);
 171         igridmaxs[1] = min(AREA_GRID, igridmaxs[1]);
 172         //igridmaxs[2] = min(AREA_GRID, igridmaxs[2]);
 173
 174         numlist = 0;
 175         // add entities not linked into areagrid because they are too big or
 176         // outside the grid bounds
 177         if (world->areagrid_outside.next != &world->areagrid_outside)
 178         {
 179                 grid = &world->areagrid_outside;
 180                 for (l = grid->next;l != grid;l = l->next)
 181                 {
 182                         ent = PRVM_EDICT_NUM(l->entitynumber);
 183                         if (ent->priv.server->areagridmarknumber != world->areagrid_marknumber)
 184                         {
 185                                 ent->priv.server->areagridmarknumber = world->areagrid_marknumber;
 186                                 if (!ent->priv.server->free && BoxesOverlap(mins, maxs, ent->priv.server->areamins, ent->priv.server->areamaxs))
 187                                 {
 188                                         if (numlist < maxlist)
 189                                                 list[numlist] = ent;
 190                                         numlist++;
 191                                 }
 192                                 world->areagrid_stats_entitychecks++;
 193                         }
 194                 }
 195         }
 196         // add grid linked entities
 197         for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
 198         {
 199                 grid = world->areagrid + igrid[1] * AREA_GRID + igridmins[0];
 200                 for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++)
 201                 {
 202                         if (grid->next != grid)
 203                         {
 204                                 for (l = grid->next;l != grid;l = l->next)
 205                                 {
 206                                         ent = PRVM_EDICT_NUM(l->entitynumber);
 207                                         if (ent->priv.server->areagridmarknumber != world->areagrid_marknumber)
 208                                         {
 209                                                 ent->priv.server->areagridmarknumber = world->areagrid_marknumber;
 210                                                 if (!ent->priv.server->free && BoxesOverlap(mins, maxs, ent->priv.server->areamins, ent->priv.server->areamaxs))
 211                                                 {
 212                                                         if (numlist < maxlist)
 213                                                                 list[numlist] = ent;
 214                                                         numlist++;
 215                                                 }
 216                                                 //Con_Printf("%d %f %f %f %f %f %f : %d : %f %f %f %f %f %f\n", BoxesOverlap(mins, maxs, ent->priv.server->areamins, ent->priv.server->areamaxs), ent->priv.server->areamins[0], ent->priv.server->areamins[1], ent->priv.server->areamins[2], ent->priv.server->areamaxs[0], ent->priv.server->areamaxs[1], ent->priv.server->areamaxs[2], PRVM_NUM_FOR_EDICT(ent), mins[0], mins[1], mins[2], maxs[0], maxs[1], maxs[2]);
 217                                         }
 218                                         world->areagrid_stats_entitychecks++;
 219                                 }
 220                         }
 221                 }
 222         }
 223         return numlist;
 224 }
 225
 226 void World_LinkEdict_AreaGrid(world_t *world, prvm_edict_t *ent)
 227 {
 228         link_t *grid;
 229         int igrid[3], igridmins[3], igridmaxs[3], gridnum, entitynumber = PRVM_NUM_FOR_EDICT(ent);
 230
 231         if (entitynumber <= 0 || entitynumber >= prog->max_edicts || PRVM_EDICT_NUM(entitynumber) != ent)
 232         {
 233                 Con_Printf ("SV_LinkEdict_AreaGrid: invalid edict %p (edicts is %p, edict compared to prog->edicts is %i)\n", ent, prog->edicts, entitynumber);
 234                 return;
 235         }
 236
 237         igridmins[0] = (int) floor((ent->priv.server->areamins[0] + world->areagrid_bias[0]) * world->areagrid_scale[0]);
 238         igridmins[1] = (int) floor((ent->priv.server->areamins[1] + world->areagrid_bias[1]) * world->areagrid_scale[1]);
 239         //igridmins[2] = (int) floor((ent->priv.server->areamins[2] + world->areagrid_bias[2]) * world->areagrid_scale[2]);
 240         igridmaxs[0] = (int) floor((ent->priv.server->areamaxs[0] + world->areagrid_bias[0]) * world->areagrid_scale[0]) + 1;
 241         igridmaxs[1] = (int) floor((ent->priv.server->areamaxs[1] + world->areagrid_bias[1]) * world->areagrid_scale[1]) + 1;
 242         //igridmaxs[2] = (int) floor((ent->priv.server->areamaxs[2] + world->areagrid_bias[2]) * world->areagrid_scale[2]) + 1;
 243         if (igridmins[0] < 0 || igridmaxs[0] > AREA_GRID || igridmins[1] < 0 || igridmaxs[1] > AREA_GRID || ((igridmaxs[0] - igridmins[0]) * (igridmaxs[1] - igridmins[1])) > ENTITYGRIDAREAS)
 244         {
 245                 // wow, something outside the grid, store it as such
 246                 World_InsertLinkBefore (&ent->priv.server->areagrid[0], &world->areagrid_outside, entitynumber);
 247                 return;
 248         }
 249
 250         gridnum = 0;
 251         for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
 252         {
 253                 grid = world->areagrid + igrid[1] * AREA_GRID + igridmins[0];
 254                 for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++, gridnum++)
 255                         World_InsertLinkBefore (&ent->priv.server->areagrid[gridnum], grid, entitynumber);
 256         }
 257 }
 258
 259 /*
 260 ===============
 261 World_LinkEdict
 262
 263 ===============
 264 */
 265 void World_LinkEdict(world_t *world, prvm_edict_t *ent, const vec3_t mins, const vec3_t maxs)
 266 {
 267         // unlink from old position first
 268         if (ent->priv.server->areagrid[0].prev)
 269                 World_UnlinkEdict(ent);
 270
 271         // don't add the world
 272         if (ent == prog->edicts)
 273                 return;
 274
 275         // don't add free entities
 276         if (ent->priv.server->free)
 277                 return;
 278
 279         VectorCopy(mins, ent->priv.server->areamins);
 280         VectorCopy(maxs, ent->priv.server->areamaxs);
 281         World_LinkEdict_AreaGrid(world, ent);
 282 }