1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4
5 This file is part of Quake III Arena source code.
6
7 Quake III Arena source code is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2 of the License,
10 or (at your option) any later version.
11
12 Quake III Arena source code is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Quake III Arena source code; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 ===========================================================================
21 */
22 //
23 // cg_predict.c -- this file generates cg.predictedPlayerState by either
24 // interpolating between snapshots from the server or locally predicting
25 // ahead the client's movement.
26 // It also handles local physics interaction, like fragments bouncing off walls
27
28 #include "cg_local.h"
29
30 static pmove_t cg_pmove;
31
32 static int cg_numSolidEntities;
33 static centity_t *cg_solidEntities[MAX_ENTITIES_IN_SNAPSHOT];
34 static int cg_numTriggerEntities;
35 static centity_t *cg_triggerEntities[MAX_ENTITIES_IN_SNAPSHOT];
36
37 /*
38 ====================
39 CG_BuildSolidList
40
41 When a new cg.snap has been set, this function builds a sublist
42 of the entities that are actually solid, to make for more
43 efficient collision detection
44 ====================
45 */
CG_BuildSolidList(void)46 void CG_BuildSolidList( void ) {
47 int i;
48 centity_t *cent;
49 snapshot_t *snap;
50 entityState_t *ent;
51
52 cg_numSolidEntities = 0;
53 cg_numTriggerEntities = 0;
54
55 if ( cg.nextSnap && !cg.nextFrameTeleport && !cg.thisFrameTeleport ) {
56 snap = cg.nextSnap;
57 } else {
58 snap = cg.snap;
59 }
60
61 for ( i = 0 ; i < snap->numEntities ; i++ ) {
62 cent = &cg_entities[ snap->entities[ i ].number ];
63 ent = ¢->currentState;
64
65 if ( ent->eType == ET_ITEM || ent->eType == ET_PUSH_TRIGGER || ent->eType == ET_TELEPORT_TRIGGER ) {
66 cg_triggerEntities[cg_numTriggerEntities] = cent;
67 cg_numTriggerEntities++;
68 continue;
69 }
70
71 if ( cent->nextState.solid ) {
72 cg_solidEntities[cg_numSolidEntities] = cent;
73 cg_numSolidEntities++;
74 continue;
75 }
76 }
77 }
78
79 /*
80 ====================
81 CG_ClipMoveToEntities
82
83 ====================
84 */
CG_ClipMoveToEntities(const vec3_t start,const vec3_t mins,const vec3_t maxs,const vec3_t end,int skipNumber,int mask,trace_t * tr)85 static void CG_ClipMoveToEntities ( const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end,
86 int skipNumber, int mask, trace_t *tr ) {
87 int i, x, zd, zu;
88 trace_t trace;
89 entityState_t *ent;
90 clipHandle_t cmodel;
91 vec3_t bmins, bmaxs;
92 vec3_t origin, angles;
93 centity_t *cent;
94
95 for ( i = 0 ; i < cg_numSolidEntities ; i++ ) {
96 cent = cg_solidEntities[ i ];
97 ent = ¢->currentState;
98
99 if ( ent->number == skipNumber ) {
100 continue;
101 }
102
103 if ( ent->solid == SOLID_BMODEL ) {
104 // special value for bmodel
105 cmodel = trap_CM_InlineModel( ent->modelindex );
106 VectorCopy( cent->lerpAngles, angles );
107 BG_EvaluateTrajectory( ¢->currentState.pos, cg.physicsTime, origin );
108 } else {
109 // encoded bbox
110 x = (ent->solid & 255);
111 zd = ((ent->solid>>8) & 255);
112 zu = ((ent->solid>>16) & 255) - 32;
113
114 bmins[0] = bmins[1] = -x;
115 bmaxs[0] = bmaxs[1] = x;
116 bmins[2] = -zd;
117 bmaxs[2] = zu;
118
119 cmodel = trap_CM_TempBoxModel( bmins, bmaxs );
120 VectorCopy( vec3_origin, angles );
121 VectorCopy( cent->lerpOrigin, origin );
122 }
123
124
125 trap_CM_TransformedBoxTrace ( &trace, start, end,
126 mins, maxs, cmodel, mask, origin, angles);
127
128 if (trace.allsolid || trace.fraction < tr->fraction) {
129 trace.entityNum = ent->number;
130 *tr = trace;
131 } else if (trace.startsolid) {
132 tr->startsolid = qtrue;
133 }
134 if ( tr->allsolid ) {
135 return;
136 }
137 }
138 }
139
140 /*
141 ================
142 CG_Trace
143 ================
144 */
CG_Trace(trace_t * result,const vec3_t start,const vec3_t mins,const vec3_t maxs,const vec3_t end,int skipNumber,int mask)145 void CG_Trace( trace_t *result, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end,
146 int skipNumber, int mask ) {
147 trace_t t;
148
149 trap_CM_BoxTrace ( &t, start, end, mins, maxs, 0, mask);
150 t.entityNum = t.fraction != 1.0 ? ENTITYNUM_WORLD : ENTITYNUM_NONE;
151 // check all other solid models
152 CG_ClipMoveToEntities (start, mins, maxs, end, skipNumber, mask, &t);
153
154 *result = t;
155 }
156
157 /*
158 ================
159 CG_PointContents
160 ================
161 */
CG_PointContents(const vec3_t point,int passEntityNum)162 int CG_PointContents( const vec3_t point, int passEntityNum ) {
163 int i;
164 entityState_t *ent;
165 centity_t *cent;
166 clipHandle_t cmodel;
167 int contents;
168
169 contents = trap_CM_PointContents (point, 0);
170
171 for ( i = 0 ; i < cg_numSolidEntities ; i++ ) {
172 cent = cg_solidEntities[ i ];
173
174 ent = ¢->currentState;
175
176 if ( ent->number == passEntityNum ) {
177 continue;
178 }
179
180 if (ent->solid != SOLID_BMODEL) { // special value for bmodel
181 continue;
182 }
183
184 cmodel = trap_CM_InlineModel( ent->modelindex );
185 if ( !cmodel ) {
186 continue;
187 }
188
189 contents |= trap_CM_TransformedPointContents( point, cmodel, ent->origin, ent->angles );
190 }
191
192 return contents;
193 }
194
195
196 /*
197 ========================
198 CG_InterpolatePlayerState
199
200 Generates cg.predictedPlayerState by interpolating between
201 cg.snap->player_state and cg.nextFrame->player_state
202 ========================
203 */
CG_InterpolatePlayerState(qboolean grabAngles)204 static void CG_InterpolatePlayerState( qboolean grabAngles ) {
205 float f;
206 int i;
207 playerState_t *out;
208 snapshot_t *prev, *next;
209
210 out = &cg.predictedPlayerState;
211 prev = cg.snap;
212 next = cg.nextSnap;
213
214 *out = cg.snap->ps;
215
216 // if we are still allowing local input, short circuit the view angles
217 if ( grabAngles ) {
218 usercmd_t cmd;
219 int cmdNum;
220
221 cmdNum = trap_GetCurrentCmdNumber();
222 trap_GetUserCmd( cmdNum, &cmd );
223
224 PM_UpdateViewAngles( out, &cmd );
225 }
226
227 // if the next frame is a teleport, we can't lerp to it
228 if ( cg.nextFrameTeleport ) {
229 return;
230 }
231
232 if ( !next || next->serverTime <= prev->serverTime ) {
233 return;
234 }
235
236 f = (float)( cg.time - prev->serverTime ) / ( next->serverTime - prev->serverTime );
237
238 i = next->ps.bobCycle;
239 if ( i < prev->ps.bobCycle ) {
240 i += 256; // handle wraparound
241 }
242 out->bobCycle = prev->ps.bobCycle + f * ( i - prev->ps.bobCycle );
243
244 for ( i = 0 ; i < 3 ; i++ ) {
245 out->origin[i] = prev->ps.origin[i] + f * (next->ps.origin[i] - prev->ps.origin[i] );
246 if ( !grabAngles ) {
247 out->viewangles[i] = LerpAngle(
248 prev->ps.viewangles[i], next->ps.viewangles[i], f );
249 }
250 out->velocity[i] = prev->ps.velocity[i] +
251 f * (next->ps.velocity[i] - prev->ps.velocity[i] );
252 }
253
254 }
255
256 /*
257 ===================
258 CG_TouchItem
259 ===================
260 */
CG_TouchItem(centity_t * cent)261 static void CG_TouchItem( centity_t *cent ) {
262 gitem_t *item;
263
264 if ( !cg_predictItems.integer ) {
265 return;
266 }
267 if ( !BG_PlayerTouchesItem( &cg.predictedPlayerState, ¢->currentState, cg.time ) ) {
268 return;
269 }
270
271 // never pick an item up twice in a prediction
272 if ( cent->miscTime == cg.time ) {
273 return;
274 }
275
276 if ( !BG_CanItemBeGrabbed( cgs.gametype, ¢->currentState, &cg.predictedPlayerState ) ) {
277 return; // can't hold it
278 }
279
280 item = &bg_itemlist[ cent->currentState.modelindex ];
281
282 // Special case for flags.
283 // We don't predict touching our own flag
284 #ifdef MISSIONPACK
285 if( cgs.gametype == GT_1FCTF ) {
286 if( item->giTag != PW_NEUTRALFLAG ) {
287 return;
288 }
289 }
290 if( cgs.gametype == GT_CTF || cgs.gametype == GT_HARVESTER ) {
291 #else
292 if( cgs.gametype == GT_CTF ) {
293 #endif
294 if (cg.predictedPlayerState.persistant[PERS_TEAM] == TEAM_RED &&
295 item->giTag == PW_REDFLAG)
296 return;
297 if (cg.predictedPlayerState.persistant[PERS_TEAM] == TEAM_BLUE &&
298 item->giTag == PW_BLUEFLAG)
299 return;
300 }
301
302 // grab it
303 BG_AddPredictableEventToPlayerstate( EV_ITEM_PICKUP, cent->currentState.modelindex , &cg.predictedPlayerState);
304
305 // remove it from the frame so it won't be drawn
306 cent->currentState.eFlags |= EF_NODRAW;
307
308 // don't touch it again this prediction
309 cent->miscTime = cg.time;
310
311 // if its a weapon, give them some predicted ammo so the autoswitch will work
312 if ( item->giType == IT_WEAPON ) {
313 cg.predictedPlayerState.stats[ STAT_WEAPONS ] |= 1 << item->giTag;
314 if ( !cg.predictedPlayerState.ammo[ item->giTag ] ) {
315 cg.predictedPlayerState.ammo[ item->giTag ] = 1;
316 }
317 }
318 }
319
320
321 /*
322 =========================
323 CG_TouchTriggerPrediction
324
325 Predict push triggers and items
326 =========================
327 */
328 static void CG_TouchTriggerPrediction( void ) {
329 int i;
330 trace_t trace;
331 entityState_t *ent;
332 clipHandle_t cmodel;
333 centity_t *cent;
334 qboolean spectator;
335
336 // dead clients don't activate triggers
337 if ( cg.predictedPlayerState.stats[STAT_HEALTH] <= 0 ) {
338 return;
339 }
340
341 spectator = ( cg.predictedPlayerState.pm_type == PM_SPECTATOR );
342
343 if ( cg.predictedPlayerState.pm_type != PM_NORMAL && !spectator ) {
344 return;
345 }
346
347 for ( i = 0 ; i < cg_numTriggerEntities ; i++ ) {
348 cent = cg_triggerEntities[ i ];
349 ent = ¢->currentState;
350
351 if ( ent->eType == ET_ITEM && !spectator ) {
352 CG_TouchItem( cent );
353 continue;
354 }
355
356 if ( ent->solid != SOLID_BMODEL ) {
357 continue;
358 }
359
360 cmodel = trap_CM_InlineModel( ent->modelindex );
361 if ( !cmodel ) {
362 continue;
363 }
364
365 trap_CM_BoxTrace( &trace, cg.predictedPlayerState.origin, cg.predictedPlayerState.origin,
366 cg_pmove.mins, cg_pmove.maxs, cmodel, -1 );
367
368 if ( !trace.startsolid ) {
369 continue;
370 }
371
372 if ( ent->eType == ET_TELEPORT_TRIGGER ) {
373 cg.hyperspace = qtrue;
374 } else if ( ent->eType == ET_PUSH_TRIGGER ) {
375 BG_TouchJumpPad( &cg.predictedPlayerState, ent );
376 }
377 }
378
379 // if we didn't touch a jump pad this pmove frame
380 if ( cg.predictedPlayerState.jumppad_frame != cg.predictedPlayerState.pmove_framecount ) {
381 cg.predictedPlayerState.jumppad_frame = 0;
382 cg.predictedPlayerState.jumppad_ent = 0;
383 }
384 }
385
386
387
388 /*
389 =================
390 CG_PredictPlayerState
391
392 Generates cg.predictedPlayerState for the current cg.time
393 cg.predictedPlayerState is guaranteed to be valid after exiting.
394
395 For demo playback, this will be an interpolation between two valid
396 playerState_t.
397
398 For normal gameplay, it will be the result of predicted usercmd_t on
399 top of the most recent playerState_t received from the server.
400
401 Each new snapshot will usually have one or more new usercmd over the last,
402 but we simulate all unacknowledged commands each time, not just the new ones.
403 This means that on an internet connection, quite a few pmoves may be issued
404 each frame.
405
406 OPTIMIZE: don't re-simulate unless the newly arrived snapshot playerState_t
407 differs from the predicted one. Would require saving all intermediate
408 playerState_t during prediction.
409
410 We detect prediction errors and allow them to be decayed off over several frames
411 to ease the jerk.
412 =================
413 */
414 void CG_PredictPlayerState( void ) {
415 int cmdNum, current;
416 playerState_t oldPlayerState;
417 qboolean moved;
418 usercmd_t oldestCmd;
419 usercmd_t latestCmd;
420
421 cg.hyperspace = qfalse; // will be set if touching a trigger_teleport
422
423 // if this is the first frame we must guarantee
424 // predictedPlayerState is valid even if there is some
425 // other error condition
426 if ( !cg.validPPS ) {
427 cg.validPPS = qtrue;
428 cg.predictedPlayerState = cg.snap->ps;
429 }
430
431
432 // demo playback just copies the moves
433 if ( cg.demoPlayback || (cg.snap->ps.pm_flags & PMF_FOLLOW) ) {
434 CG_InterpolatePlayerState( qfalse );
435 return;
436 }
437
438 // non-predicting local movement will grab the latest angles
439 if ( cg_nopredict.integer || cg_synchronousClients.integer ) {
440 CG_InterpolatePlayerState( qtrue );
441 return;
442 }
443
444 // prepare for pmove
445 cg_pmove.ps = &cg.predictedPlayerState;
446 cg_pmove.trace = CG_Trace;
447 cg_pmove.pointcontents = CG_PointContents;
448 if ( cg_pmove.ps->pm_type == PM_DEAD ) {
449 cg_pmove.tracemask = MASK_PLAYERSOLID & ~CONTENTS_BODY;
450 }
451 else {
452 cg_pmove.tracemask = MASK_PLAYERSOLID;
453 }
454 if ( cg.snap->ps.persistant[PERS_TEAM] == TEAM_SPECTATOR ) {
455 cg_pmove.tracemask &= ~CONTENTS_BODY; // spectators can fly through bodies
456 }
457 cg_pmove.noFootsteps = ( cgs.dmflags & DF_NO_FOOTSTEPS ) > 0;
458
459 // save the state before the pmove so we can detect transitions
460 oldPlayerState = cg.predictedPlayerState;
461
462 current = trap_GetCurrentCmdNumber();
463
464 // if we don't have the commands right after the snapshot, we
465 // can't accurately predict a current position, so just freeze at
466 // the last good position we had
467 cmdNum = current - CMD_BACKUP + 1;
468 trap_GetUserCmd( cmdNum, &oldestCmd );
469 if ( oldestCmd.serverTime > cg.snap->ps.commandTime
470 && oldestCmd.serverTime < cg.time ) { // special check for map_restart
471 if ( cg_showmiss.integer ) {
472 CG_Printf ("exceeded PACKET_BACKUP on commands\n");
473 }
474 return;
475 }
476
477 // get the latest command so we can know which commands are from previous map_restarts
478 trap_GetUserCmd( current, &latestCmd );
479
480 // get the most recent information we have, even if
481 // the server time is beyond our current cg.time,
482 // because predicted player positions are going to
483 // be ahead of everything else anyway
484 if ( cg.nextSnap && !cg.nextFrameTeleport && !cg.thisFrameTeleport ) {
485 cg.predictedPlayerState = cg.nextSnap->ps;
486 cg.physicsTime = cg.nextSnap->serverTime;
487 } else {
488 cg.predictedPlayerState = cg.snap->ps;
489 cg.physicsTime = cg.snap->serverTime;
490 }
491
492 if ( pmove_msec.integer < 8 ) {
493 trap_Cvar_Set("pmove_msec", "8");
494 }
495 else if (pmove_msec.integer > 33) {
496 trap_Cvar_Set("pmove_msec", "33");
497 }
498
499 cg_pmove.pmove_fixed = pmove_fixed.integer;// | cg_pmove_fixed.integer;
500 cg_pmove.pmove_msec = pmove_msec.integer;
501
502 // run cmds
503 moved = qfalse;
504 for ( cmdNum = current - CMD_BACKUP + 1 ; cmdNum <= current ; cmdNum++ ) {
505 // get the command
506 trap_GetUserCmd( cmdNum, &cg_pmove.cmd );
507
508 if ( cg_pmove.pmove_fixed ) {
509 PM_UpdateViewAngles( cg_pmove.ps, &cg_pmove.cmd );
510 }
511
512 // don't do anything if the time is before the snapshot player time
513 if ( cg_pmove.cmd.serverTime <= cg.predictedPlayerState.commandTime ) {
514 continue;
515 }
516
517 // don't do anything if the command was from a previous map_restart
518 if ( cg_pmove.cmd.serverTime > latestCmd.serverTime ) {
519 continue;
520 }
521
522 // check for a prediction error from last frame
523 // on a lan, this will often be the exact value
524 // from the snapshot, but on a wan we will have
525 // to predict several commands to get to the point
526 // we want to compare
527 if ( cg.predictedPlayerState.commandTime == oldPlayerState.commandTime ) {
528 vec3_t delta;
529 float len;
530
531 if ( cg.thisFrameTeleport ) {
532 // a teleport will not cause an error decay
533 VectorClear( cg.predictedError );
534 if ( cg_showmiss.integer ) {
535 CG_Printf( "PredictionTeleport\n" );
536 }
537 cg.thisFrameTeleport = qfalse;
538 } else {
539 vec3_t adjusted;
540 CG_AdjustPositionForMover( cg.predictedPlayerState.origin,
541 cg.predictedPlayerState.groundEntityNum, cg.physicsTime, cg.oldTime, adjusted );
542
543 if ( cg_showmiss.integer ) {
544 if (!VectorCompare( oldPlayerState.origin, adjusted )) {
545 CG_Printf("prediction error\n");
546 }
547 }
548 VectorSubtract( oldPlayerState.origin, adjusted, delta );
549 len = VectorLength( delta );
550 if ( len > 0.1 ) {
551 if ( cg_showmiss.integer ) {
552 CG_Printf("Prediction miss: %f\n", len);
553 }
554 if ( cg_errorDecay.integer ) {
555 int t;
556 float f;
557
558 t = cg.time - cg.predictedErrorTime;
559 f = ( cg_errorDecay.value - t ) / cg_errorDecay.value;
560 if ( f < 0 ) {
561 f = 0;
562 }
563 if ( f > 0 && cg_showmiss.integer ) {
564 CG_Printf("Double prediction decay: %f\n", f);
565 }
566 VectorScale( cg.predictedError, f, cg.predictedError );
567 } else {
568 VectorClear( cg.predictedError );
569 }
570 VectorAdd( delta, cg.predictedError, cg.predictedError );
571 cg.predictedErrorTime = cg.oldTime;
572 }
573 }
574 }
575
576 // don't predict gauntlet firing, which is only supposed to happen
577 // when it actually inflicts damage
578 cg_pmove.gauntletHit = qfalse;
579
580 if ( cg_pmove.pmove_fixed ) {
581 cg_pmove.cmd.serverTime = ((cg_pmove.cmd.serverTime + pmove_msec.integer-1) / pmove_msec.integer) * pmove_msec.integer;
582 }
583
584 Pmove (&cg_pmove);
585
586 moved = qtrue;
587
588 // add push trigger movement effects
589 CG_TouchTriggerPrediction();
590
591 // check for predictable events that changed from previous predictions
592 //CG_CheckChangedPredictableEvents(&cg.predictedPlayerState);
593 }
594
595 if ( cg_showmiss.integer > 1 ) {
596 CG_Printf( "[%i : %i] ", cg_pmove.cmd.serverTime, cg.time );
597 }
598
599 if ( !moved ) {
600 if ( cg_showmiss.integer ) {
601 CG_Printf( "not moved\n" );
602 }
603 return;
604 }
605
606 // adjust for the movement of the groundentity
607 CG_AdjustPositionForMover( cg.predictedPlayerState.origin,
608 cg.predictedPlayerState.groundEntityNum,
609 cg.physicsTime, cg.time, cg.predictedPlayerState.origin );
610
611 if ( cg_showmiss.integer ) {
612 if (cg.predictedPlayerState.eventSequence > oldPlayerState.eventSequence + MAX_PS_EVENTS) {
613 CG_Printf("WARNING: dropped event\n");
614 }
615 }
616
617 // fire events and other transition triggered things
618 CG_TransitionPlayerState( &cg.predictedPlayerState, &oldPlayerState );
619
620 if ( cg_showmiss.integer ) {
621 if (cg.eventSequence > cg.predictedPlayerState.eventSequence) {
622 CG_Printf("WARNING: double event\n");
623 cg.eventSequence = cg.predictedPlayerState.eventSequence;
624 }
625 }
626 }
627
628
629