got rid of AreaNode stuff, now only has AreaGrid (had to add sv_areagrid_outside...
[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_debugmove = {CVAR_NOTIFY, "sv_debugmove", "0"};
33 cvar_t sv_polygoncollisions = {CVAR_NOTIFY, "sv_polygoncollisions", "0"};
34 cvar_t sv_areagrid_mingridsize = {CVAR_NOTIFY, "sv_areagrid_mingridsize", "64"};
35
36 void SV_AreaStats_f(void);
37
38 void SV_World_Init(void)
39 {
40         Cvar_RegisterVariable(&sv_debugmove);
41         Cvar_RegisterVariable(&sv_polygoncollisions);
42         Cvar_RegisterVariable(&sv_areagrid_mingridsize);
43         Cmd_AddCommand("sv_areastats", SV_AreaStats_f);
44         Collision_Init();
45 }
46
47 typedef struct
48 {
49         // bounding box of entire move area
50         vec3_t boxmins, boxmaxs;
51
52         // size of the moving object
53         vec3_t mins, maxs;
54
55         // size when clipping against monsters
56         vec3_t mins2, maxs2;
57
58         // size when clipping against brush models
59         vec3_t hullmins, hullmaxs;
60
61         // start and end origin of move
62         vec3_t start, end;
63
64         // trace results
65         trace_t trace;
66
67         // type of move (like ignoring monsters, or similar)
68         int type;
69
70         // the edict that is moving (if any)
71         edict_t *passedict;
72 }
73 moveclip_t;
74
75 //#define EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area)))
76 #define EDICT_FROM_AREA(l) ((edict_t *)l->entity)
77
78 //============================================================================
79
80 // ClearLink is used for new headnodes
81 void ClearLink (link_t *l)
82 {
83         l->entity = NULL;
84         l->prev = l->next = l;
85 }
86
87 void RemoveLink (link_t *l)
88 {
89         l->next->prev = l->prev;
90         l->prev->next = l->next;
91 }
92
93 void InsertLinkBefore (link_t *l, link_t *before, void *ent)
94 {
95         l->entity = ent;
96         l->next = before;
97         l->prev = before->prev;
98         l->prev->next = l;
99         l->next->prev = l;
100 }
101
102 void InsertLinkAfter (link_t *l, link_t *after)
103 {
104         l->next = after->next;
105         l->prev = after;
106         l->prev->next = l;
107         l->next->prev = l;
108 }
109
110
111 /*
112 ===============================================================================
113
114 ENTITY AREA CHECKING
115
116 ===============================================================================
117 */
118
119 int sv_areagrid_stats_calls = 0;
120 int sv_areagrid_stats_nodechecks = 0;
121 int sv_areagrid_stats_entitychecks = 0;
122
123 void SV_AreaStats_f(void)
124 {
125         Con_Printf("areagrid check stats: %d calls %d nodes (%f per call) %d entities (%f per call)\n", sv_areagrid_stats_calls, sv_areagrid_stats_nodechecks, (double) sv_areagrid_stats_nodechecks / (double) sv_areagrid_stats_calls, sv_areagrid_stats_entitychecks, (double) sv_areagrid_stats_entitychecks / (double) sv_areagrid_stats_calls);
126         sv_areagrid_stats_calls = 0;
127         sv_areagrid_stats_nodechecks = 0;
128         sv_areagrid_stats_entitychecks = 0;
129 }
130
131 typedef struct areagrid_s
132 {
133         link_t trigger_edicts;
134         link_t solid_edicts;
135 }
136 areagrid_t;
137
138 #define AREA_GRID 512
139 #define AREA_GRIDNODES (AREA_GRID * AREA_GRID)
140
141 static areagrid_t sv_areagrid[AREA_GRIDNODES], sv_areagrid_outside;
142 static vec3_t sv_areagrid_bias, sv_areagrid_scale, sv_areagrid_mins, sv_areagrid_maxs, sv_areagrid_size;
143 static int sv_areagrid_marknumber = 1;
144
145 void SV_CreateAreaGrid (vec3_t mins, vec3_t maxs)
146 {
147         int i;
148         ClearLink (&sv_areagrid_outside.trigger_edicts);
149         ClearLink (&sv_areagrid_outside.solid_edicts);
150         // choose either the world box size, or a larger box to ensure the grid isn't too fine
151         sv_areagrid_size[0] = max(maxs[0] - mins[0], AREA_GRID * sv_areagrid_mingridsize.value);
152         sv_areagrid_size[1] = max(maxs[1] - mins[1], AREA_GRID * sv_areagrid_mingridsize.value);
153         sv_areagrid_size[2] = max(maxs[2] - mins[2], AREA_GRID * sv_areagrid_mingridsize.value);
154         // figure out the corners of such a box, centered at the center of the world box
155         sv_areagrid_mins[0] = (mins[0] + maxs[0] - sv_areagrid_size[0]) * 0.5f;
156         sv_areagrid_mins[1] = (mins[1] + maxs[1] - sv_areagrid_size[1]) * 0.5f;
157         sv_areagrid_mins[2] = (mins[2] + maxs[2] - sv_areagrid_size[2]) * 0.5f;
158         sv_areagrid_maxs[0] = (mins[0] + maxs[0] + sv_areagrid_size[0]) * 0.5f;
159         sv_areagrid_maxs[1] = (mins[1] + maxs[1] + sv_areagrid_size[1]) * 0.5f;
160         sv_areagrid_maxs[2] = (mins[2] + maxs[2] + sv_areagrid_size[2]) * 0.5f;
161         // now calculate the actual useful info from that
162         VectorNegate(sv_areagrid_mins, sv_areagrid_bias);
163         sv_areagrid_scale[0] = AREA_GRID / sv_areagrid_size[0];
164         sv_areagrid_scale[1] = AREA_GRID / sv_areagrid_size[1];
165         sv_areagrid_scale[2] = AREA_GRID / sv_areagrid_size[2];
166         for (i = 0;i < AREA_GRIDNODES;i++)
167         {
168                 ClearLink (&sv_areagrid[i].trigger_edicts);
169                 ClearLink (&sv_areagrid[i].solid_edicts);
170         }
171         Con_DPrintf("sv_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, sv_areagrid_mins[0], sv_areagrid_mins[1], sv_areagrid_mins[2], sv_areagrid_maxs[0], sv_areagrid_maxs[1], sv_areagrid_maxs[2], sv_areagrid_size[0], sv_areagrid_size[1], sv_areagrid_size[2], 1.0f / sv_areagrid_scale[0], 1.0f / sv_areagrid_scale[1], 1.0f / sv_areagrid_scale[2], sv_areagrid_mingridsize.value);
172 }
173
174 /*
175 ===============
176 SV_ClearWorld
177
178 ===============
179 */
180 void SV_ClearWorld (void)
181 {
182         Mod_CheckLoaded(sv.worldmodel);
183         SV_CreateAreaGrid(sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
184 }
185
186
187 /*
188 ===============
189 SV_UnlinkEdict
190
191 ===============
192 */
193 void SV_UnlinkEdict (edict_t *ent)
194 {
195         int i;
196         for (i = 0;i < ENTITYGRIDAREAS;i++)
197         {
198                 if (ent->areagrid[i].prev)
199                 {
200                         RemoveLink (&ent->areagrid[i]);
201                         ent->areagrid[i].prev = ent->areagrid[i].next = NULL;
202                 }
203         }
204 }
205
206
207 void SV_TouchAreaGrid(edict_t *ent)
208 {
209         link_t *l, *next;
210         edict_t *touch;
211         areagrid_t *grid;
212         int old_self, old_other, igrid[3], igridmins[3], igridmaxs[3];
213
214         sv_areagrid_marknumber++;
215         igridmins[0] = (int) ((ent->v->absmin[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]);
216         igridmins[1] = (int) ((ent->v->absmin[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]);
217         //igridmins[2] = (int) ((ent->v->absmin[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]);
218         igridmaxs[0] = (int) ((ent->v->absmax[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]) + 1;
219         igridmaxs[1] = (int) ((ent->v->absmax[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]) + 1;
220         //igridmaxs[2] = (int) ((ent->v->absmax[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]) + 1;
221         igridmins[0] = max(0, igridmins[0]);
222         igridmins[1] = max(0, igridmins[1]);
223         //igridmins[2] = max(0, igridmins[2]);
224         igridmaxs[0] = min(AREA_GRID, igridmaxs[0]);
225         igridmaxs[1] = min(AREA_GRID, igridmaxs[1]);
226         //igridmaxs[2] = min(AREA_GRID, igridmaxs[2]);
227
228         for (l = sv_areagrid_outside.trigger_edicts.next;l != &sv_areagrid_outside.trigger_edicts;l = next)
229         {
230                 next = l->next;
231                 touch = EDICT_FROM_AREA(l);
232                 if (ent->v->absmin[0] > touch->v->absmax[0]
233                  || ent->v->absmax[0] < touch->v->absmin[0]
234                  || ent->v->absmin[1] > touch->v->absmax[1]
235                  || ent->v->absmax[1] < touch->v->absmin[1]
236                  || ent->v->absmin[2] > touch->v->absmax[2]
237                  || ent->v->absmax[2] < touch->v->absmin[2])
238                         continue;
239                 if (touch == ent)
240                         continue;
241                 if (!touch->v->touch || touch->v->solid != SOLID_TRIGGER)
242                         continue;
243                 old_self = pr_global_struct->self;
244                 old_other = pr_global_struct->other;
245
246                 pr_global_struct->self = EDICT_TO_PROG(touch);
247                 pr_global_struct->other = EDICT_TO_PROG(ent);
248                 pr_global_struct->time = sv.time;
249                 PR_ExecuteProgram (touch->v->touch, "");
250
251                 pr_global_struct->self = old_self;
252                 pr_global_struct->other = old_other;
253         }
254
255         for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
256         {
257                 grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0];
258                 for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++)
259                 {
260                         for (l = grid->trigger_edicts.next;l != &grid->trigger_edicts;l = next)
261                         {
262                                 next = l->next;
263                                 touch = EDICT_FROM_AREA(l);
264                                 if (touch->areagridmarknumber == sv_areagrid_marknumber)
265                                         continue;
266                                 touch->areagridmarknumber = sv_areagrid_marknumber;
267                                 if (ent->v->absmin[0] > touch->v->absmax[0]
268                                  || ent->v->absmax[0] < touch->v->absmin[0]
269                                  || ent->v->absmin[1] > touch->v->absmax[1]
270                                  || ent->v->absmax[1] < touch->v->absmin[1]
271                                  || ent->v->absmin[2] > touch->v->absmax[2]
272                                  || ent->v->absmax[2] < touch->v->absmin[2])
273                                         continue;
274                                 if (touch == ent)
275                                         continue;
276                                 if (!touch->v->touch || touch->v->solid != SOLID_TRIGGER)
277                                         continue;
278                                 old_self = pr_global_struct->self;
279                                 old_other = pr_global_struct->other;
280
281                                 pr_global_struct->self = EDICT_TO_PROG(touch);
282                                 pr_global_struct->other = EDICT_TO_PROG(ent);
283                                 pr_global_struct->time = sv.time;
284                                 PR_ExecuteProgram (touch->v->touch, "");
285
286                                 pr_global_struct->self = old_self;
287                                 pr_global_struct->other = old_other;
288                         }
289                 }
290         }
291 }
292
293 void SV_LinkEdict_AreaGrid(edict_t *ent)
294 {
295         areagrid_t *grid;
296         int igrid[3], igridmins[3], igridmaxs[3], gridnum;
297
298         igridmins[0] = (int) ((ent->v->absmin[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]);
299         igridmins[1] = (int) ((ent->v->absmin[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]);
300         //igridmins[2] = (int) ((ent->v->absmin[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]);
301         igridmaxs[0] = (int) ((ent->v->absmax[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]) + 1;
302         igridmaxs[1] = (int) ((ent->v->absmax[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]) + 1;
303         //igridmaxs[2] = (int) ((ent->v->absmax[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]) + 1;
304         if (igridmins[0] < 0 || igridmaxs[0] > AREA_GRID || igridmins[1] < 0 || igridmaxs[1] > AREA_GRID || ((igridmaxs[0] - igridmins[0]) * (igridmaxs[1] - igridmins[1])) > ENTITYGRIDAREAS)
305         {
306                 // wow, something outside the grid, store it as such
307                 if (ent->v->solid == SOLID_TRIGGER)
308                         InsertLinkBefore (&ent->areagrid[0], &sv_areagrid_outside.trigger_edicts, ent);
309                 else
310                         InsertLinkBefore (&ent->areagrid[0], &sv_areagrid_outside.solid_edicts, ent);
311                 return;
312         }
313
314         gridnum = 0;
315         for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
316         {
317                 grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0];
318                 for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++, gridnum++)
319                 {
320                         if (ent->v->solid == SOLID_TRIGGER)
321                                 InsertLinkBefore (&ent->areagrid[gridnum], &grid->trigger_edicts, ent);
322                         else
323                                 InsertLinkBefore (&ent->areagrid[gridnum], &grid->solid_edicts, ent);
324                 }
325         }
326 }
327
328 /*
329 ===============
330 SV_LinkEdict
331
332 ===============
333 */
334 void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
335 {
336         model_t *model;
337
338         if (ent->areagrid[0].prev)
339                 SV_UnlinkEdict (ent);   // unlink from old position
340
341         if (ent == sv.edicts)
342                 return;         // don't add the world
343
344         if (ent->free)
345                 return;
346
347 // set the abs box
348
349         if (ent->v->solid == SOLID_BSP)
350         {
351                 if (ent->v->modelindex < 0 || ent->v->modelindex > MAX_MODELS)
352                         Host_Error("SOLID_BSP with invalid modelindex!\n");
353                 model = sv.models[(int) ent->v->modelindex];
354                 if (model != NULL)
355                 {
356                         if (model->type != mod_brush)
357                                 Host_Error("SOLID_BSP with non-BSP model\n");
358
359                         if (ent->v->angles[0] || ent->v->angles[2] || ent->v->avelocity[0] || ent->v->avelocity[2])
360                         {
361                                 VectorAdd(ent->v->origin, model->rotatedmins, ent->v->absmin);
362                                 VectorAdd(ent->v->origin, model->rotatedmaxs, ent->v->absmax);
363                         }
364                         else if (ent->v->angles[1] || ent->v->avelocity[1])
365                         {
366                                 VectorAdd(ent->v->origin, model->yawmins, ent->v->absmin);
367                                 VectorAdd(ent->v->origin, model->yawmaxs, ent->v->absmax);
368                         }
369                         else
370                         {
371                                 VectorAdd(ent->v->origin, model->normalmins, ent->v->absmin);
372                                 VectorAdd(ent->v->origin, model->normalmaxs, ent->v->absmax);
373                         }
374                 }
375                 else
376                 {
377                         // SOLID_BSP with no model is valid, mainly because some QC setup code does so temporarily
378                         VectorAdd(ent->v->origin, ent->v->mins, ent->v->absmin);
379                         VectorAdd(ent->v->origin, ent->v->maxs, ent->v->absmax);
380                 }
381         }
382         else
383         {
384                 VectorAdd(ent->v->origin, ent->v->mins, ent->v->absmin);
385                 VectorAdd(ent->v->origin, ent->v->maxs, ent->v->absmax);
386         }
387
388 //
389 // to make items easier to pick up and allow them to be grabbed off
390 // of shelves, the abs sizes are expanded
391 //
392         if ((int)ent->v->flags & FL_ITEM)
393         {
394                 ent->v->absmin[0] -= 15;
395                 ent->v->absmin[1] -= 15;
396                 ent->v->absmin[2] -= 1;
397                 ent->v->absmax[0] += 15;
398                 ent->v->absmax[1] += 15;
399                 ent->v->absmax[2] += 1;
400         }
401         else
402         {
403                 // because movement is clipped an epsilon away from an actual edge,
404                 // we must fully check even when bounding boxes don't quite touch
405                 ent->v->absmin[0] -= 1;
406                 ent->v->absmin[1] -= 1;
407                 ent->v->absmin[2] -= 1;
408                 ent->v->absmax[0] += 1;
409                 ent->v->absmax[1] += 1;
410                 ent->v->absmax[2] += 1;
411         }
412
413         if (ent->v->solid == SOLID_NOT)
414                 return;
415
416         SV_LinkEdict_AreaGrid(ent);
417
418 // if touch_triggers, touch all entities at this node and descend for more
419         if (touch_triggers)
420                 SV_TouchAreaGrid(ent);
421 }
422
423
424
425 /*
426 ===============================================================================
427
428 POINT TESTING IN HULLS
429
430 ===============================================================================
431 */
432
433 /*
434 ============
435 SV_TestEntityPosition
436
437 This could be a lot more efficient...
438 ============
439 */
440 int SV_TestEntityPosition (edict_t *ent)
441 {
442         return SV_Move (ent->v->origin, ent->v->mins, ent->v->maxs, ent->v->origin, MOVE_NORMAL, ent).startsolid;
443 }
444
445
446 /*
447 ===============================================================================
448
449 LINE TESTING IN HULLS
450
451 ===============================================================================
452 */
453
454 /*
455 ==================
456 SV_ClipMoveToEntity
457
458 Handles selection or creation of a clipping hull, and offseting (and
459 eventually rotation) of the end points
460 ==================
461 */
462 trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
463 {
464         int i;
465         trace_t trace;
466         model_t *model;
467
468         i = ent->v->modelindex;
469         if ((unsigned int) i >= MAX_MODELS)
470                 Host_Error("SV_ClipMoveToEntity: invalid modelindex\n");
471         model = sv.models[i];
472         if (i != 0 && model == NULL)
473                 Host_Error("SV_ClipMoveToEntity: invalid modelindex\n");
474
475         if ((int) ent->v->solid == SOLID_BSP)
476         {
477                 Mod_CheckLoaded(model);
478                 if (model->type != mod_brush)
479                 {
480                         Con_Printf ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model, entity dump:\n");
481                         ED_Print (ent);
482                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model\n");
483                 }
484                 if (ent->v->movetype != MOVETYPE_PUSH)
485                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP without MOVETYPE_PUSH");
486         }
487
488         if (sv_polygoncollisions.integer && (mins[0] != maxs[0] || mins[1] != maxs[1] || mins[2] != maxs[2]))
489                 Collision_PolygonClipTrace(&trace, ent, model, ent->v->origin, ent->v->angles, ent->v->mins, ent->v->maxs, start, mins, maxs, end);
490         else
491                 Collision_ClipTrace(&trace, ent, model, ent->v->origin, ent->v->angles, ent->v->mins, ent->v->maxs, start, mins, maxs, end);
492
493         return trace;
494 }
495
496 //===========================================================================
497
498 void SV_ClipToNode(moveclip_t *clip, link_t *list)
499 {
500         link_t *l, *next;
501         edict_t *touch;
502         trace_t trace;
503
504         sv_areagrid_stats_nodechecks++;
505         for (l = list->next;l != list;l = next)
506         {
507                 next = l->next;
508                 touch = EDICT_FROM_AREA(l);
509                 if (touch->areagridmarknumber == sv_areagrid_marknumber)
510                         continue;
511                 touch->areagridmarknumber = sv_areagrid_marknumber;
512                 sv_areagrid_stats_entitychecks++;
513
514                 if (clip->boxmins[0] > touch->v->absmax[0]
515                  || clip->boxmaxs[0] < touch->v->absmin[0]
516                  || clip->boxmins[1] > touch->v->absmax[1]
517                  || clip->boxmaxs[1] < touch->v->absmin[1]
518                  || clip->boxmins[2] > touch->v->absmax[2]
519                  || clip->boxmaxs[2] < touch->v->absmin[2])
520                         continue;
521
522                 if (clip->type == MOVE_NOMONSTERS && touch->v->solid != SOLID_BSP)
523                         continue;
524
525                 if (touch->v->solid == SOLID_NOT)
526                         continue;
527
528                 if (clip->passedict)
529                 {
530                         if (clip->passedict->v->size[0] && !touch->v->size[0])
531                                 continue;       // points never interact
532                         if (PROG_TO_EDICT(touch->v->owner) == clip->passedict)
533                                 continue;       // don't clip against own missiles
534                         if (PROG_TO_EDICT(clip->passedict->v->owner) == touch)
535                                 continue;       // don't clip against owner
536                         // LordHavoc: corpse code
537                         if (clip->passedict->v->solid == SOLID_CORPSE && (touch->v->solid == SOLID_SLIDEBOX || touch->v->solid == SOLID_CORPSE))
538                                 continue;
539                         if (clip->passedict->v->solid == SOLID_SLIDEBOX && touch->v->solid == SOLID_CORPSE)
540                                 continue;
541                 }
542
543                 if (touch == clip->passedict)
544                         continue;
545                 if (touch->v->solid == SOLID_TRIGGER)
546                 {
547                         ED_Print(touch);
548                         Host_Error ("Trigger in clipping list");
549                 }
550
551                 // might interact, so do an exact clip
552                 if (touch->v->solid == SOLID_BSP)
553                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->hullmins, clip->hullmaxs, clip->end);
554                 else if ((int)touch->v->flags & FL_MONSTER)
555                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
556                 else
557                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
558                 // LordHavoc: take the 'best' answers from the new trace and combine with existing data
559                 if (trace.allsolid)
560                         clip->trace.allsolid = true;
561                 if (trace.startsolid)
562                 {
563                         clip->trace.startsolid = true;
564                         if (!clip->trace.ent)
565                                 clip->trace.ent = trace.ent;
566                 }
567                 if (trace.inopen)
568                         clip->trace.inopen = true;
569                 if (trace.inwater)
570                         clip->trace.inwater = true;
571                 if (trace.fraction < clip->trace.fraction)
572                 {
573                         clip->trace.fraction = trace.fraction;
574                         VectorCopy(trace.endpos, clip->trace.endpos);
575                         clip->trace.plane = trace.plane;
576                         clip->trace.endcontents = trace.endcontents;
577                         clip->trace.ent = trace.ent;
578                 }
579                 if (clip->trace.allsolid)
580                         return;
581         }
582 }
583
584 /*
585 ====================
586 SV_ClipToAreaGrid
587
588 Mins and maxs enclose the entire area swept by the move
589 ====================
590 */
591 void SV_ClipToAreaGrid(moveclip_t *clip)
592 {
593         areagrid_t *grid;
594         int igrid[3], igridmins[3], igridmaxs[3];
595
596         if (clip->trace.allsolid)
597                 return;
598
599         sv_areagrid_stats_calls++;
600         sv_areagrid_marknumber++;
601         igridmins[0] = (int) ((clip->boxmins[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]);
602         igridmins[1] = (int) ((clip->boxmins[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]);
603         //igridmins[2] = (int) ((clip->boxmins[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]);
604         igridmaxs[0] = (int) ((clip->boxmaxs[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]) + 1;
605         igridmaxs[1] = (int) ((clip->boxmaxs[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]) + 1;
606         //igridmaxs[2] = (int) ((clip->boxmaxs[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]) + 1;
607         igridmins[0] = max(0, igridmins[0]);
608         igridmins[1] = max(0, igridmins[1]);
609         //igridmins[2] = max(0, igridmins[2]);
610         igridmaxs[0] = min(AREA_GRID, igridmaxs[0]);
611         igridmaxs[1] = min(AREA_GRID, igridmaxs[1]);
612         //igridmaxs[2] = min(AREA_GRID, igridmaxs[2]);
613
614         if (sv_areagrid_outside.solid_edicts.next != &sv_areagrid_outside.solid_edicts)
615                 SV_ClipToNode(clip, &sv_areagrid_outside.solid_edicts);
616
617         for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
618                 for (grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0], igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++)
619                         if (grid->solid_edicts.next != &grid->solid_edicts)
620                                 SV_ClipToNode(clip, &grid->solid_edicts);
621 }
622
623
624 /*
625 ==================
626 SV_MoveBounds
627 ==================
628 */
629 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
630 {
631         if (!sv_debugmove.integer)
632         {
633                 int i;
634
635                 for (i=0 ; i<3 ; i++)
636                 {
637                         if (end[i] > start[i])
638                         {
639                                 boxmins[i] = start[i] + mins[i] - 1;
640                                 boxmaxs[i] = end[i] + maxs[i] + 1;
641                         }
642                         else
643                         {
644                                 boxmins[i] = end[i] + mins[i] - 1;
645                                 boxmaxs[i] = start[i] + maxs[i] + 1;
646                         }
647                 }
648         }
649         else
650         {
651                 // debug to test against everything
652                 boxmins[0] = boxmins[1] = boxmins[2] = -999999999;
653                 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] =  999999999;
654         }
655 }
656
657 /*
658 ==================
659 SV_Move
660 ==================
661 */
662 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
663 {
664         moveclip_t      clip;
665         vec3_t          bigmins, bigmaxs;
666         int                     i;
667
668         memset ( &clip, 0, sizeof ( moveclip_t ) );
669
670         VectorCopy(start, clip.start);
671         VectorCopy(end, clip.end);
672         VectorCopy(mins, clip.mins);
673         VectorCopy(maxs, clip.maxs);
674         clip.type = type;
675         clip.passedict = passedict;
676
677         Collision_RoundUpToHullSize(sv.worldmodel, clip.mins, clip.maxs, clip.hullmins, clip.hullmaxs);
678
679         if (type == MOVE_MISSILE)
680         {
681                 // LordHavoc: modified this, was = -15, now = clip.mins[i] - 15
682                 for (i=0 ; i<3 ; i++)
683                 {
684                         clip.mins2[i] = clip.mins[i] - 15;
685                         clip.maxs2[i] = clip.maxs[i] + 15;
686                 }
687         }
688         else
689         {
690                 VectorCopy (clip.mins, clip.mins2);
691                 VectorCopy (clip.maxs, clip.maxs2);
692         }
693
694         bigmins[0] = min(clip.mins2[0], clip.hullmins[0]);
695         bigmaxs[0] = max(clip.maxs2[0], clip.hullmaxs[0]);
696         bigmins[1] = min(clip.mins2[1], clip.hullmins[1]);
697         bigmaxs[1] = max(clip.maxs2[1], clip.hullmaxs[1]);
698         bigmins[2] = min(clip.mins2[2], clip.hullmins[2]);
699         bigmaxs[2] = max(clip.maxs2[2], clip.hullmaxs[2]);
700
701         // clip to world
702         clip.trace = SV_ClipMoveToEntity (sv.edicts, start, mins, maxs, end);
703
704         // clip to entities
705         // create the bounding box of the entire move
706         SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs );
707
708         SV_ClipToAreaGrid(&clip);
709
710         return clip.trace;
711 }
712