removed PRVM_EDICT_NUM_UNSIGNED (PRVM_EDICT_NUM now casts to unsigned)
[divverent/darkplaces.git] / 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 cvar_t sv_areagrid_mingridsize = {CVAR_NOTIFY, "sv_areagrid_mingridsize", "64", "minimum areagrid cell size, smaller values work better for lots of small objects, higher values for large objects"};
33
34 void World_Init(void)
35 {
36         Cvar_RegisterVariable(&sv_areagrid_mingridsize);
37         Collision_Init();
38 }
39
40 //============================================================================
41
42 // World_ClearLink is used for new headnodes
43 void World_ClearLink (link_t *l)
44 {
45         l->entitynumber = 0;
46         l->prev = l->next = l;
47 }
48
49 void World_RemoveLink (link_t *l)
50 {
51         l->next->prev = l->prev;
52         l->prev->next = l->next;
53 }
54
55 void World_InsertLinkBefore (link_t *l, link_t *before, int entitynumber)
56 {
57         l->entitynumber = entitynumber;
58         l->next = before;
59         l->prev = before->prev;
60         l->prev->next = l;
61         l->next->prev = l;
62 }
63
64 /*
65 ===============================================================================
66
67 ENTITY AREA CHECKING
68
69 ===============================================================================
70 */
71
72 void World_PrintAreaStats(world_t *world, const char *worldname)
73 {
74         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);
75         world->areagrid_stats_calls = 0;
76         world->areagrid_stats_nodechecks = 0;
77         world->areagrid_stats_entitychecks = 0;
78 }
79
80 /*
81 ===============
82 World_Clear
83
84 ===============
85 */
86 void World_Clear(world_t *world)
87 {
88         int i;
89         // the areagrid_marknumber is not allowed to be 0
90         if (world->areagrid_marknumber < 1)
91                 world->areagrid_marknumber = 1;
92         // choose either the world box size, or a larger box to ensure the grid isn't too fine
93         world->areagrid_size[0] = max(world->areagrid_maxs[0] - world->areagrid_mins[0], AREA_GRID * sv_areagrid_mingridsize.value);
94         world->areagrid_size[1] = max(world->areagrid_maxs[1] - world->areagrid_mins[1], AREA_GRID * sv_areagrid_mingridsize.value);
95         world->areagrid_size[2] = max(world->areagrid_maxs[2] - world->areagrid_mins[2], AREA_GRID * sv_areagrid_mingridsize.value);
96         // figure out the corners of such a box, centered at the center of the world box
97         world->areagrid_mins[0] = (world->areagrid_mins[0] + world->areagrid_maxs[0] - world->areagrid_size[0]) * 0.5f;
98         world->areagrid_mins[1] = (world->areagrid_mins[1] + world->areagrid_maxs[1] - world->areagrid_size[1]) * 0.5f;
99         world->areagrid_mins[2] = (world->areagrid_mins[2] + world->areagrid_maxs[2] - world->areagrid_size[2]) * 0.5f;
100         world->areagrid_maxs[0] = (world->areagrid_mins[0] + world->areagrid_maxs[0] + world->areagrid_size[0]) * 0.5f;
101         world->areagrid_maxs[1] = (world->areagrid_mins[1] + world->areagrid_maxs[1] + world->areagrid_size[1]) * 0.5f;
102         world->areagrid_maxs[2] = (world->areagrid_mins[2] + world->areagrid_maxs[2] + world->areagrid_size[2]) * 0.5f;
103         // now calculate the actual useful info from that
104         VectorNegate(world->areagrid_mins, world->areagrid_bias);
105         world->areagrid_scale[0] = AREA_GRID / world->areagrid_size[0];
106         world->areagrid_scale[1] = AREA_GRID / world->areagrid_size[1];
107         world->areagrid_scale[2] = AREA_GRID / world->areagrid_size[2];
108         World_ClearLink(&world->areagrid_outside);
109         for (i = 0;i < AREA_GRIDNODES;i++)
110                 World_ClearLink(&world->areagrid[i]);
111         Con_DPrintf("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);
112 }
113
114
115 /*
116 ===============
117
118 ===============
119 */
120 void World_UnlinkEdict(prvm_edict_t *ent)
121 {
122         int i;
123         for (i = 0;i < ENTITYGRIDAREAS;i++)
124         {
125                 if (ent->priv.server->areagrid[i].prev)
126                 {
127                         World_RemoveLink (&ent->priv.server->areagrid[i]);
128                         ent->priv.server->areagrid[i].prev = ent->priv.server->areagrid[i].next = NULL;
129                 }
130         }
131 }
132
133 int World_EntitiesInBox(world_t *world, vec3_t mins, vec3_t maxs, int maxlist, prvm_edict_t **list)
134 {
135         int numlist;
136         link_t *grid;
137         link_t *l;
138         prvm_edict_t *ent;
139         int igrid[3], igridmins[3], igridmaxs[3];
140
141         // FIXME: if areagrid_marknumber wraps, all entities need their
142         // ent->priv.server->areagridmarknumber reset
143         world->areagrid_stats_calls++;
144         world->areagrid_marknumber++;
145         igridmins[0] = (int) floor((mins[0] + world->areagrid_bias[0]) * world->areagrid_scale[0]);
146         igridmins[1] = (int) floor((mins[1] + world->areagrid_bias[1]) * world->areagrid_scale[1]);
147         //igridmins[2] = (int) ((mins[2] + world->areagrid_bias[2]) * world->areagrid_scale[2]);
148         igridmaxs[0] = (int) floor((maxs[0] + world->areagrid_bias[0]) * world->areagrid_scale[0]) + 1;
149         igridmaxs[1] = (int) floor((maxs[1] + world->areagrid_bias[1]) * world->areagrid_scale[1]) + 1;
150         //igridmaxs[2] = (int) ((maxs[2] + world->areagrid_bias[2]) * world->areagrid_scale[2]) + 1;
151         igridmins[0] = max(0, igridmins[0]);
152         igridmins[1] = max(0, igridmins[1]);
153         //igridmins[2] = max(0, igridmins[2]);
154         igridmaxs[0] = min(AREA_GRID, igridmaxs[0]);
155         igridmaxs[1] = min(AREA_GRID, igridmaxs[1]);
156         //igridmaxs[2] = min(AREA_GRID, igridmaxs[2]);
157
158         numlist = 0;
159         // add entities not linked into areagrid because they are too big or
160         // outside the grid bounds
161         if (world->areagrid_outside.next != &world->areagrid_outside)
162         {
163                 grid = &world->areagrid_outside;
164                 for (l = grid->next;l != grid;l = l->next)
165                 {
166                         ent = PRVM_EDICT_NUM(l->entitynumber);
167                         if (ent->priv.server->areagridmarknumber != world->areagrid_marknumber)
168                         {
169                                 ent->priv.server->areagridmarknumber = world->areagrid_marknumber;
170                                 if (!ent->priv.server->free && BoxesOverlap(mins, maxs, ent->priv.server->areamins, ent->priv.server->areamaxs))
171                                 {
172                                         if (numlist < maxlist)
173                                                 list[numlist] = ent;
174                                         numlist++;
175                                 }
176                                 world->areagrid_stats_entitychecks++;
177                         }
178                 }
179         }
180         // add grid linked entities
181         for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
182         {
183                 grid = world->areagrid + igrid[1] * AREA_GRID + igridmins[0];
184                 for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++)
185                 {
186                         if (grid->next != grid)
187                         {
188                                 for (l = grid->next;l != grid;l = l->next)
189                                 {
190                                         ent = PRVM_EDICT_NUM(l->entitynumber);
191                                         if (ent->priv.server->areagridmarknumber != world->areagrid_marknumber)
192                                         {
193                                                 ent->priv.server->areagridmarknumber = world->areagrid_marknumber;
194                                                 if (!ent->priv.server->free && BoxesOverlap(mins, maxs, ent->priv.server->areamins, ent->priv.server->areamaxs))
195                                                 {
196                                                         if (numlist < maxlist)
197                                                                 list[numlist] = ent;
198                                                         numlist++;
199                                                 }
200                                                 //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]);
201                                         }
202                                         world->areagrid_stats_entitychecks++;
203                                 }
204                         }
205                 }
206         }
207         return numlist;
208 }
209
210 void World_LinkEdict_AreaGrid(world_t *world, prvm_edict_t *ent)
211 {
212         link_t *grid;
213         int igrid[3], igridmins[3], igridmaxs[3], gridnum, entitynumber = PRVM_NUM_FOR_EDICT(ent);
214
215         if (entitynumber <= 0 || entitynumber >= prog->max_edicts || PRVM_EDICT_NUM(entitynumber) != ent)
216         {
217                 Con_Printf ("SV_LinkEdict_AreaGrid: invalid edict %p (edicts is %p, edict compared to prog->edicts is %i)\n", ent, prog->edicts, entitynumber);
218                 return;
219         }
220
221         igridmins[0] = (int) floor((ent->priv.server->areamins[0] + sv.world.areagrid_bias[0]) * sv.world.areagrid_scale[0]);
222         igridmins[1] = (int) floor((ent->priv.server->areamins[1] + sv.world.areagrid_bias[1]) * sv.world.areagrid_scale[1]);
223         //igridmins[2] = (int) floor((ent->priv.server->areamins[2] + sv.world.areagrid_bias[2]) * sv.world.areagrid_scale[2]);
224         igridmaxs[0] = (int) floor((ent->priv.server->areamaxs[0] + sv.world.areagrid_bias[0]) * sv.world.areagrid_scale[0]) + 1;
225         igridmaxs[1] = (int) floor((ent->priv.server->areamaxs[1] + sv.world.areagrid_bias[1]) * sv.world.areagrid_scale[1]) + 1;
226         //igridmaxs[2] = (int) floor((ent->priv.server->areamaxs[2] + sv.world.areagrid_bias[2]) * sv.world.areagrid_scale[2]) + 1;
227         if (igridmins[0] < 0 || igridmaxs[0] > AREA_GRID || igridmins[1] < 0 || igridmaxs[1] > AREA_GRID || ((igridmaxs[0] - igridmins[0]) * (igridmaxs[1] - igridmins[1])) > ENTITYGRIDAREAS)
228         {
229                 // wow, something outside the grid, store it as such
230                 World_InsertLinkBefore (&ent->priv.server->areagrid[0], &sv.world.areagrid_outside, entitynumber);
231                 return;
232         }
233
234         gridnum = 0;
235         for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
236         {
237                 grid = sv.world.areagrid + igrid[1] * AREA_GRID + igridmins[0];
238                 for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++, gridnum++)
239                         World_InsertLinkBefore (&ent->priv.server->areagrid[gridnum], grid, entitynumber);
240         }
241 }
242
243 /*
244 ===============
245 World_LinkEdict
246
247 ===============
248 */
249 void World_LinkEdict(world_t *world, prvm_edict_t *ent, const vec3_t mins, const vec3_t maxs)
250 {
251         // unlink from old position first
252         if (ent->priv.server->areagrid[0].prev)
253                 World_UnlinkEdict(ent);
254
255         // don't add the world
256         if (ent == prog->edicts)
257                 return;
258
259         // don't add free entities
260         if (ent->priv.server->free)
261                 return;
262
263         VectorCopy(mins, ent->priv.server->areamins);
264         VectorCopy(maxs, ent->priv.server->areamaxs);
265         World_LinkEdict_AreaGrid(world, ent);
266 }