2 * Copyright (C) Volition, Inc. 1999. All rights reserved.
4 * All source code herein is the property of Volition, Inc. You may not sell
5 * or otherwise commercially exploit the source or things you created based on
10 * $Logfile: /Freespace2/code/Object/ObjCollide.cpp $
15 * Helper routines for all the collision detection functions
16 * Also keeps track of all the object pairs.
19 * Revision 1.5 2003/05/25 02:30:43 taylor
22 * Revision 1.4 2002/06/17 06:33:10 relnev
23 * ryan's struct patch for gcc 2.95
25 * Revision 1.3 2002/06/09 04:41:24 relnev
26 * added copyright header
28 * Revision 1.2 2002/05/07 03:16:48 theoddone33
29 * The Great Newline Fix
31 * Revision 1.1.1.1 2002/05/03 03:28:10 root
35 * 18 7/15/99 9:20a Andsager
36 * FS2_DEMO initial checkin
38 * 17 6/14/99 3:21p Andsager
39 * Allow collisions between ship and its debris. Fix up collision pairs
40 * when large ship is warping out.
42 * 16 5/08/99 8:25p Dave
43 * Upped object pairs. First run of nebula lightning.
45 * 15 4/23/99 12:01p Johnson
48 * 14 4/21/99 6:15p Dave
49 * Did some serious housecleaning in the beam code. Made it ready to go
50 * for anti-fighter "pulse" weapons. Fixed collision pair creation. Added
51 * a handy macro for recalculating collision pairs for a given object.
53 * 13 4/20/99 3:41p Andsager
54 * Modify objects_will_collide to use endpoints
56 * 12 3/10/99 6:50p Dave
57 * Changed the way we buffer packets for all clients. Optimized turret
58 * fired packets. Did some weapon firing optimizations.
60 * 11 3/05/99 3:32p Dan
61 * Make out of collision pars message npirntf with "collision"
63 * 10 1/21/99 2:06p Dave
64 * Final checkin for multiplayer testing.
66 * 9 1/21/99 10:44a Dave
67 * More beam weapon stuff. Put in warmdown time.
69 * 8 1/15/99 5:01p Dave
70 * Fix for object collision problem.
72 * 7 1/12/99 5:45p Dave
73 * Moved weapon pipeline in multiplayer to almost exclusively client side.
74 * Very good results. Bandwidth goes down, playability goes up for crappy
75 * connections. Fixed object update problem for ship subsystems.
77 * 6 1/12/99 12:53a Dave
78 * More work on beam weapons - made collision detection very efficient -
79 * collide against all object types properly - made 3 movement types
80 * smooth. Put in test code to check for possible non-darkening pixels on
83 * 5 11/19/98 11:08p Andsager
84 * Check in of physics and collision detection of rotating submodels
86 * 4 11/05/98 5:55p Dave
87 * Big pass at reducing #includes
89 * 3 10/26/98 9:42a Dave
90 * Early flak gun support.
92 * 2 10/07/98 10:53a Dave
95 * 1 10/07/98 10:50a Dave
97 * 38 7/29/98 3:24p Allender
98 * don't call collision code when either of the object pairs is NULL.
100 * 37 4/08/98 8:38a Mike
101 * Make ships avoid player when attacking or guarding a faraway object.
103 * 36 4/02/98 11:40a Lawrance
104 * check for #ifdef DEMO instead of #ifdef DEMO_RELEASE
106 * 35 4/01/98 1:48p Allender
107 * major changes to ship collision in multiplayer. Clients now do own
108 * ship/ship collisions (with their own ship only) Modifed the hull
109 * update packet to be sent quicker when object is target of player.
111 * 34 4/01/98 10:57a Mike
112 * Reduce array sizes to save memory.
114 * 33 3/31/98 5:18p John
115 * Removed demo/save/restore. Made NDEBUG defined compile. Removed a
116 * bunch of debug stuff out of player file. Made model code be able to
117 * unload models and malloc out only however many models are needed.
120 * 32 3/06/98 12:45a Lawrance
121 * Rmove a bogus assert in the object pair save/restore
123 * 31 3/05/98 3:12p Mike
124 * Fix bugs in asteroid collisions. Throw asteroids at Galataea (needs to
125 * be made general). Add skill level support for asteroid throwing.
127 * 30 3/05/98 12:12a Mike
128 * Make an asteroid in the way prevent player warpout.
130 * 29 2/27/98 4:48p John
131 * Made objects keep track of number of pairs they have associated with
132 * them. Then, I can early out of the obj_remove_all which was 2.5% of
133 * frametime at beginning of sm2-2 which then is 0% after this.
135 * 28 2/26/98 10:07p Hoffoss
136 * Rewrote state saving and restoring to fix bugs and simplify the code.
138 * 27 2/23/98 9:00a Andsager
139 * improved back face culling of object:laser pairs to check relative
140 * velocity dot laser forward < 0 vs. v_other dot v_laser < 0
142 * 26 2/19/98 4:34p Lawrance
143 * Allow weapon-asteroid collisions
145 * 25 2/19/98 10:52a Sandeep
146 * AL: Have asteroids collide with all ships
148 * 24 2/12/98 11:45a Andsager
149 * Try to cull debris:weapon collisions before they collisoin pair is
150 * created. Look at movement in lifetime and whether debris is behind
153 * 23 2/07/98 3:54p John
154 * Added FVI to show_game_resources
156 * 22 2/06/98 7:29p John
157 * Made only players ships and player ship weapons do collisions with
160 * 21 2/05/98 11:49p Andsager
161 * Don't check laser:ship collisions on same team for small ships if laser
164 * 20 2/05/98 9:21p John
165 * Some new Direct3D code. Added code to monitor a ton of stuff in the
168 * 19 2/05/98 12:51a Mike
169 * Early asteroid stuff.
171 * 18 2/03/98 9:40a Andsager
172 * Modify collision object pair creation code so that pairs between debris
173 * and weapons (other than player) are not created.
175 * 17 1/28/98 11:06a Andsager
176 * Remove some collision pairs. Add debug code for displaying collision
179 * 16 1/24/98 11:16a Andsager
182 * 15 1/24/98 11:09a Andsager
183 * Fixed bug that was removing collision pairs when weapon within the
186 * 14 1/23/98 5:07p Andsager
187 * Added tests for object pairs. (1) for weapons that do not turn, find
188 * the soonest hit time. (2) Check if soonest hit time if after end of
191 * 13 1/22/98 6:43p John
192 * Took out debug code.
194 * 12 1/22/98 6:42p John
195 * Move game_flush out of debug console into freespace. Made object
196 * pair code throw out some weapons that turn. Added stats for how many
197 * object pair are actually checked.
199 * 11 1/17/98 10:06p Lawrance
200 * For missiles, only collide if WIF_BOMB flag set.
202 * 10 1/14/98 5:21p Allender
203 * system to delete object when buffer is nearly full. System in place to
204 * delete weapons when nearly out of weapons slots
206 * 9 1/13/98 8:09p John
207 * Removed the old collision system that checked all pairs. Added code
208 * to disable collisions and particles.
210 * 8 1/13/98 3:11p Allender
211 * new code to remove old weapons when no more weapon slots available.
212 * Currently not called anywhere pending further testing
214 * 7 1/10/98 3:22p Allender
215 * temporary check in to get new code
217 * 6 1/10/98 1:14p John
218 * Added explanation to debug console commands
220 * 5 1/09/98 9:29a Mike
221 * Enable docked ships to warp out. Make damage done to a ship not
222 * proportional to its own mass.
224 * 4 1/08/98 12:12a Mike
225 * Make ships turn before warping out, if necessary, to avoid a collision.
226 * Warn player if his warpout will collide. Abort if in stage1.
228 * 3 12/21/97 4:33p John
229 * Made debug console functions a class that registers itself
230 * automatically, so you don't need to add the function to
231 * debugfunctions.cpp.
233 * 2 12/16/97 5:23p Allender
234 * don't deal with object collision paris on multiplayer clients
236 * 1 9/17/97 2:14p John
242 #include "objcollide.h"
243 #include "linklist.h"
244 #include "systemvars.h"
249 #if defined(FS2_DEMO) || defined(FS1_DEMO)
250 #define MAX_PAIRS 3000
252 #define MAX_PAIRS 8000 // Reduced from 10,000 to 6,000 by MK on 4/1/98.
253 // Most I saw was 3400 in sm1-06a, the asteriod mission. No other mission came close.
256 // the next 3 variables are used for pair statistics
257 // also in weapon.cpp there is Weapons_created.
258 int Pairs_created = 0;
260 int Num_pairs_checked = 0;
261 int pairs_not_created = 0;
263 int Num_pairs_hwm = 0;
265 obj_pair Obj_pairs[MAX_PAIRS];
267 obj_pair pair_used_list;
268 obj_pair pair_free_list;
270 void obj_reset_pairs()
274 // mprintf(( "Resetting object pairs...\n" ));
276 pair_used_list.a = pair_used_list.b = NULL;
277 pair_used_list.next = NULL;
278 pair_free_list.a = pair_free_list.b = NULL;
279 pair_free_list.next = &Obj_pairs[0];
282 for (i=0; i<MAX_PAIRS; i++ ) {
283 Obj_pairs[i].a = Obj_pairs[i].b = NULL;
284 Obj_pairs[i].next = &Obj_pairs[i+1];
286 Obj_pairs[MAX_PAIRS-1].next = NULL;
289 // returns true if we should reject object pair if one is child of other.
290 int reject_obj_pair_on_parent(object *A, object *B)
292 if (A->type == OBJ_SHIP) {
293 if (B->type == OBJ_DEBRIS) {
294 if (B->parent_sig == A->signature) {
300 if (B->type == OBJ_SHIP) {
301 if (A->type == OBJ_DEBRIS) {
302 if (A->parent_sig == B->signature) {
308 if (A->parent_sig == B->signature) {
312 if (B->parent_sig == A->signature) {
320 // Adds the pair to the pair list
321 void obj_add_pair( object *A, object *B, int check_time, int add_to_end )
324 int (*check_collision)( obj_pair *pair );
327 check_collision = NULL;
329 if ( A==B ) return; // Don't check collisions with yourself
331 if ( !(A->flags&OF_COLLIDES) ) return; // This object doesn't collide with anything
332 if ( !(B->flags&OF_COLLIDES) ) return; // This object doesn't collide with anything
334 // Make sure you're not checking a parent with it's kid or vicy-versy
335 // if ( A->parent_sig == B->signature && !(A->type == OBJ_SHIP && B->type == OBJ_DEBRIS) ) return;
336 // if ( B->parent_sig == A->signature && !(A->type == OBJ_DEBRIS && B->type == OBJ_SHIP) ) return;
337 if ( reject_obj_pair_on_parent(A,B) ) {
341 SDL_assert( A->type < 127 );
342 SDL_assert( B->type < 127 );
344 ctype = COLLISION_OF(A->type,B->type);
346 case COLLISION_OF(OBJ_WEAPON,OBJ_SHIP):
348 check_collision = collide_ship_weapon;
350 case COLLISION_OF(OBJ_SHIP, OBJ_WEAPON):
351 check_collision = collide_ship_weapon;
353 case COLLISION_OF(OBJ_DEBRIS, OBJ_WEAPON):
354 check_collision = collide_debris_weapon;
356 case COLLISION_OF(OBJ_WEAPON, OBJ_DEBRIS):
358 check_collision = collide_debris_weapon;
360 case COLLISION_OF(OBJ_DEBRIS, OBJ_SHIP):
361 check_collision = collide_debris_ship;
363 case COLLISION_OF(OBJ_SHIP, OBJ_DEBRIS):
364 check_collision = collide_debris_ship;
367 case COLLISION_OF(OBJ_ASTEROID, OBJ_WEAPON):
368 // Only check collision's with player weapons
369 // if ( Objects[B->parent].flags & OF_PLAYER_SHIP ) {
370 check_collision = collide_asteroid_weapon;
373 case COLLISION_OF(OBJ_WEAPON, OBJ_ASTEROID):
375 // Only check collision's with player weapons
376 // if ( Objects[A->parent].flags & OF_PLAYER_SHIP ) {
377 check_collision = collide_asteroid_weapon;
380 case COLLISION_OF(OBJ_ASTEROID, OBJ_SHIP):
381 // Only check collisions with player ships
382 // if ( B->flags & OF_PLAYER_SHIP ) {
383 check_collision = collide_asteroid_ship;
386 case COLLISION_OF(OBJ_SHIP, OBJ_ASTEROID):
387 // Only check collisions with player ships
388 // if ( A->flags & OF_PLAYER_SHIP ) {
389 check_collision = collide_asteroid_ship;
393 case COLLISION_OF(OBJ_SHIP,OBJ_SHIP):
394 check_collision = collide_ship_ship;
397 case COLLISION_OF(OBJ_BEAM, OBJ_SHIP):
398 if(beam_collide_early_out(A, B)){
401 check_collision = beam_collide_ship;
404 case COLLISION_OF(OBJ_BEAM, OBJ_ASTEROID):
405 if(beam_collide_early_out(A, B)){
408 check_collision = beam_collide_asteroid;
411 case COLLISION_OF(OBJ_BEAM, OBJ_DEBRIS):
412 if(beam_collide_early_out(A, B)){
415 check_collision = beam_collide_debris;
418 case COLLISION_OF(OBJ_BEAM, OBJ_WEAPON):
419 if(beam_collide_early_out(A, B)){
422 check_collision = beam_collide_missile;
425 case COLLISION_OF(OBJ_WEAPON, OBJ_WEAPON): {
426 weapon_info *awip, *bwip;
427 awip = &Weapon_info[Weapons[A->instance].weapon_info_index];
428 bwip = &Weapon_info[Weapons[B->instance].weapon_info_index];
430 if (awip->subtype != WP_LASER || bwip->subtype != WP_LASER) {
431 if (awip->subtype == WP_LASER) {
432 if ( bwip->wi_flags & WIF_BOMB ) {
433 check_collision = collide_weapon_weapon;
435 } else if (bwip->subtype == WP_LASER) {
436 if ( awip->wi_flags & WIF_BOMB ) {
437 check_collision = collide_weapon_weapon;
441 if ( (awip->wi_flags&WIF_BOMB) || (bwip->wi_flags&WIF_BOMB) ) {
442 check_collision = collide_weapon_weapon;
449 atype = Weapon_info[Weapons[A->instance].weapon_info_index].subtype;
450 btype = Weapon_info[Weapons[B->instance].weapon_info_index].subtype;
452 if ((atype == WP_LASER) && (btype == WP_MISSILE))
453 check_collision = collide_weapon_weapon;
454 else if ((atype == WP_MISSILE) && (btype == WP_LASER)) {
455 check_collision = collide_weapon_weapon;
457 } else if ((atype == WP_MISSILE) && (btype == WP_MISSILE))
458 check_collision = collide_weapon_weapon;
468 // Swap them if needed
475 // if there are any more obj_pair checks
476 // we should then add function int maybe_not_add_obj_pair()
477 // MWA -- 4/1/98 -- I'd do it, but I don't want to bust anything, so I'm doing my stuff here instead :-)
478 //if ( MULTIPLAYER_CLIENT && !(Netgame.debug_flags & NETD_FLAG_CLIENT_NODAMAGE)){
479 // multiplayer clients will only do ship/ship collisions, and their own ship to boot
480 // if ( check_collision != collide_ship_ship ){
484 // if ( (A != Player_obj) && (B != Player_obj) ){
489 // only check debris:weapon collisions for player
490 if (check_collision == collide_debris_weapon) {
492 if ( !(Weapon_info[Weapons[B->instance].weapon_info_index].wi_flags & WIF_TURNS) ) {
493 // check for dumbfire weapon
494 // check if debris is behind laser
496 if (Weapon_info[Weapons[B->instance].weapon_info_index].subtype == WP_LASER) {
497 vector velocity_rel_weapon;
498 vm_vec_sub(&velocity_rel_weapon, &B->phys_info.vel, &A->phys_info.vel);
499 vdot = -vm_vec_dot(&velocity_rel_weapon, &B->orient.v.fvec);
501 vdot = vm_vec_dot( &A->phys_info.vel, &B->phys_info.vel);
503 if ( vdot <= 0.0f ) {
504 // They're heading in opposite directions...
505 // check their positions
507 vm_vec_sub( &weapon2other, &A->pos, &B->pos );
508 float pdot = vm_vec_dot( &B->orient.v.fvec, &weapon2other );
509 if ( pdot <= -A->radius ) {
510 // The other object is behind the weapon by more than
511 // its radius, so it will never hit...
516 // check dist vs. dist moved during weapon lifetime
518 vm_vec_sub(&delta_v, &B->phys_info.vel, &A->phys_info.vel);
519 if (vm_vec_dist_squared(&A->pos, &B->pos) > (vm_vec_mag_squared(&delta_v)*Weapons[B->instance].lifeleft*Weapons[B->instance].lifeleft)) {
523 // for nonplayer ships, only create collision pair if close enough
524 if ( !(Objects[B->parent].flags & OF_PLAYER_SHIP) && (vm_vec_dist(&B->pos, &A->pos) < (4.0f*A->radius + 200.0f)) )
529 // don't check same team laser:ship collisions on small ships if not player
530 if (check_collision == collide_ship_weapon) {
532 if ( !(Objects[B->parent].flags & OF_PLAYER_SHIP)
533 && (Ships[Objects[B->parent].instance].team == Ships[A->instance].team)
534 && (Ship_info[Ships[A->instance].ship_info_index].flags & SIF_SMALL_SHIP)
535 && (Weapon_info[Weapons[B->instance].weapon_info_index].subtype == WP_LASER) ) {
541 if ( !check_collision ) return;
544 // At this point, we have determined that collisions between
545 // these two should be checked, so add the pair to the
546 // collision pair list.
548 if ( pair_free_list.next == NULL ) {
549 nprintf(( "collision", "Out of object pairs!! Not all collisions will work!\n" ));
553 // get a new obj_pair from the free list
554 obj_pair * new_pair = pair_free_list.next;
555 pair_free_list.next = new_pair->next;
558 obj_pair *last, *tmp;
560 last = tmp = pair_used_list.next;
561 while( tmp != NULL ) {
562 if ( tmp->next == NULL )
569 last = &pair_used_list;
571 last->next = new_pair;
572 SDL_assert(new_pair != NULL);
573 new_pair->next = NULL;
576 new_pair->next = pair_used_list.next;
577 pair_used_list.next = new_pair;
581 /* if (Num_pairs > Num_pairs_hwm) {
582 Num_pairs_hwm = Num_pairs;
583 //nprintf(("AI", "Num_pairs high water mark = %i\n", Num_pairs_hwm));
592 new_pair->check_collision = check_collision;
594 if ( check_time == -1 ){
595 new_pair->next_check_time = timestamp(0); // 0 means instantly time out
597 new_pair->next_check_time = check_time;
603 MONITOR(NumPairsChecked);
605 void obj_check_all_collisions()
607 if ( !(Game_detail_flags & DETAIL_FLAG_COLLISION) ) return;
609 obj_pair *parent, *tmp;
611 float avg_time_to_next_check = 0.0f;
613 parent = &pair_used_list;
616 Num_pairs_checked = 0;
618 while( tmp != NULL ) {
621 if ( (tmp->a != NULL) && (tmp->b != NULL) && timestamp_elapsed(tmp->next_check_time) ) {
624 if ((*tmp->check_collision)(tmp)) {
625 // We never need to check this pair again.
626 #if 0 //def DONT_REMOVE_PAIRS
627 // Never check it again, but keep the pair around
628 // (useful for debugging)
629 tmp->next_check_time = timestamp(-1);
631 // Never check it again, so remove the pair
634 SDL_assert( tmp->a->num_pairs > -1 );
636 SDL_assert( tmp->b->num_pairs > -1 );
638 // SDL_assert(Num_pairs >= 0);
639 parent->next = tmp->next;
640 tmp->a = tmp->b = NULL;
641 tmp->next = pair_free_list.next;
642 pair_free_list.next = tmp;
653 int add_time = timestamp_until( tmp->next_check_time );
655 avg_time_to_next_check += (float) add_time;
660 MONITOR_INC(NumPairs,Num_pairs);
661 MONITOR_INC(NumPairsChecked,Num_pairs_checked);
663 // #define PAIR_STATS
665 avg_time_to_next_check = avg_time_to_next_check / Num_pairs;
666 extern int Num_hull_pieces;
667 extern int Weapons_created;
668 // mprintf(( "[pairs checked: %d, start_pairs: %d, num obj: %d, avg next time: %f]\n", n, org_pairs, num_objects, avg_time_to_next_check ));
669 // mprintf(( "[Num_hull_pieces: %3d, Num_weapons_created: %3d, pairs_not_created: %3d, pairs_created: %3d, percent new saved: %9.5f]\n", Num_hull_pieces, Weapons_created, pairs_not_created, Pairs_created, 100.0f*(float)pairs_not_created/(float)(pairs_not_created + Pairs_created) ));
670 mprintf(( "[pairs_created: %3d, pairs_not_created: %3d, percent saved %6.3f]\n", Pairs_created, pairs_not_created, 100.0f*pairs_not_created/(Pairs_created+pairs_not_created) ));
671 pairs_not_created = 0;
676 // What percent of the pairs did we check?
677 // FYI: (n*(n-1))/2 is the total number of checks required for comparing n objects.
679 // if ( org_pairs > 1 ) {
680 // Object_checked_percentage = (i2fl(n)*100.0f) / i2fl(org_pairs);
682 // Object_checked_percentage = 0.0f;
687 // See if two lines intersect by doing recursive subdivision.
688 // Bails out if larger distance traveled is less than sum of radii + 1.0f.
689 int collide_subdivide(vector *p0, vector *p1, float prad, vector *q0, vector *q1, float qrad)
691 float a_dist, b_dist, ab_dist;
693 a_dist = vm_vec_dist(p0, p1);
694 b_dist = vm_vec_dist(q0, q1);
696 ab_dist = vm_vec_dist(p1, q1);
698 // See if their spheres intersect
699 if (ab_dist < a_dist + b_dist + prad + qrad) {
700 if (ab_dist < prad + qrad)
702 else if (vm_vec_dist(p0, q0) < prad + qrad)
704 else if (SDL_max(a_dist, b_dist) < prad + qrad + 1.0f)
710 vm_vec_avg(&pa, p0, p1);
711 vm_vec_avg(&qa, q0, q1);
712 r1 = collide_subdivide(p0, &pa, prad, q0, &qa, qrad);
714 r2 = collide_subdivide(&pa, p1, prad, &qa, q1, qrad);
724 // Return true if object A is expected to collide with object B within time duration
725 // For purposes of this check, the first object moves from current location to predicted
726 // location. The second object is assumed to be where it will be at time duration, NOT
727 // where it currently is.
728 // radius_scale is used to control the precision of the check.
729 // If 0.0, then use polygon models to perform check, slow and accurate
730 // If !0.0, then use as a scale on the radius of the objects. 1.0 is Descent style
731 // collisions. Larger values can be used to be sloppy about the collisions which
732 // is useful if a moving object wants to prevent a collision.
733 int objects_will_collide(object *A, object *B, float duration, float radius_scale)
740 vm_vec_scale_add2(&A_future.pos, &A->phys_info.vel, duration);
742 if (radius_scale == 0.0f) {
743 return ship_check_collision_fast(B, &A_future, &hitpos );
745 float size_A, size_B, dist, r;
746 vector nearest_point;
748 size_A = A->radius * radius_scale;
749 size_B = B->radius * radius_scale;
751 // If A is moving, check along vector.
752 if (A->phys_info.speed != 0.0f) {
753 r = find_nearest_point_on_line(&nearest_point, &A->pos, &A_future.pos, &B->pos);
755 nearest_point = A->pos;
757 nearest_point = A_future.pos;
759 dist = vm_vec_dist_quick(&B->pos, &nearest_point);
760 return (dist < size_A + size_B);
762 return vm_vec_dist_quick(&B->pos, &A->pos) < size_A + size_B;
767 // Return true if the vector from *start_pos to *end_pos is within objp->radius*radius_scale of *objp
768 int vector_object_collision(vector *start_pos, vector *end_pos, object *objp, float radius_scale)
771 vector nearest_point;
773 r = find_nearest_point_on_line(&nearest_point, start_pos, end_pos, &objp->pos);
774 if ((r >= 0.0f) && (r <= 1.0f)) {
775 dist = vm_vec_dist_quick(&objp->pos, &nearest_point);
777 return (dist < objp->radius * radius_scale);
782 // Returns TRUE if the weapon will never hit the other object.
783 // If it can it predicts how long until these two objects need
784 // to be checked and fills the time in in current_pair.
785 int weapon_will_never_hit( object *weapon, object *other, obj_pair * current_pair )
788 SDL_assert( weapon->type == OBJ_WEAPON );
790 // mprintf(( "Frame: %d, Weapon=%d, Other=%d, pair=$%08x\n", G3_frame_count, OBJ_INDEX(weapon), OBJ_INDEX(other), current_pair ));
793 // Do some checks for weapons that don't turn
794 if ( !(Weapon_info[Weapons[weapon->instance].weapon_info_index].wi_flags & WIF_TURNS) ) {
796 // This first check is to see if a weapon is behind an object, and they
797 // are heading in opposite directions. If so, we don't need to ever check
798 // them again. This is only valid for weapons that don't turn.
801 if (Weapon_info[Weapons[weapon->instance].weapon_info_index].subtype == WP_LASER) {
802 vector velocity_rel_weapon;
803 vm_vec_sub(&velocity_rel_weapon, &weapon->phys_info.vel, &other->phys_info.vel);
804 vdot = -vm_vec_dot(&velocity_rel_weapon, &weapon->orient.v.fvec);
806 vdot = vm_vec_dot( &other->phys_info.vel, &weapon->phys_info.vel);
808 if ( vdot <= 0.0f ) {
809 // They're heading in opposite directions...
810 // check their positions
812 vm_vec_sub( &weapon2other, &other->pos, &weapon->pos );
813 float pdot = vm_vec_dot( &weapon->orient.v.fvec, &weapon2other );
814 if ( pdot <= -other->radius ) {
815 // The other object is behind the weapon by more than
816 // its radius, so it will never hit...
821 // FUTURE ENHANCEMENT IDEAS
823 // Given a laser does it hit a slow or not moving object
824 // in its life or the next n seconds? We'd actually need to check the
830 // This check doesn't care about orient, only looks at the maximum speed
831 // of the two objects, so it knows that in the next n seconds, they can't
832 // go further than some distance, so don't bother checking collisions for
833 // that time. This is very rough, but is so general that it works for
834 // everything and immidiately gets rid of a lot of cases.
836 if ( current_pair ) {
837 // Find the time it will take before these get within each others distances.
838 // tmp->next_check_time = timestamp(500);
839 //vector max_vel; //maximum foward velocity in x,y,z
841 float max_vel_weapon, max_vel_other;
842 max_vel_weapon = weapon->phys_info.max_vel.xyz.z;
843 max_vel_other = other->phys_info.max_vel.xyz.z;
844 if (max_vel_other < 10.0f) {
845 if ( vm_vec_mag_squared( &other->phys_info.vel ) > 100 ) {
846 // bump up velocity from collision
847 max_vel_other = vm_vec_mag( &other->phys_info.vel ) + 10.0f;
849 max_vel_other = 10.0f; // object may move from collision
853 // check weapon that does not turn against sphere expanding at ship maxvel
854 // compare (weeapon) ray with expanding sphere (ship) to find earliest possible collision time
855 // look for two time solutions to Xw = Xs, where Xw = Xw0 + Vwt*t Xs = Xs + Vs*(t+dt), where Vs*dt = radius of ship
856 // Since direction of Vs is unknown, solve for (Vs*t) and find norm of both sides
857 if ( !(Weapon_info[Weapons[weapon->instance].weapon_info_index].wi_flags & WIF_TURNS) ) {
858 vector delta_x, laser_vel;
859 float a,b,c, delta_x_dot_vl, delta_t;
860 float root1, root2, root, earliest_time;
862 vm_vec_sub( &delta_x, &weapon->pos, &other->pos );
863 vm_vec_copy_scale( &laser_vel, &weapon->orient.v.fvec, max_vel_weapon );
864 delta_t = (other->radius + 10.0f) / max_vel_other; // time to get from center to radius of other obj
865 delta_x_dot_vl = vm_vec_dotprod( &delta_x, &laser_vel );
867 a = max_vel_weapon*max_vel_weapon - max_vel_other*max_vel_other;
868 b = 2.0f * (delta_x_dot_vl - max_vel_other*max_vel_other*delta_t);
869 c = vm_vec_mag_squared( &delta_x ) - max_vel_other*max_vel_other*delta_t*delta_t;
871 float discriminant = b*b - 4.0f*a*c;
872 if ( discriminant < 0) {
876 root = fl_sqrt( discriminant );
877 root1 = (-b + root) / (2.0f * a) * 1000.0f; // get time in ms
878 root2 = (-b - root) / (2.0f * a) * 1000.0f; // get time in ms
881 // find earliest positive time
882 if ( root1 > root2 ) {
889 earliest_time = root1;
890 } else if (root2 > 0) {
891 // root1 < 0 and root2 > 0, so we're inside sphere and next check should be next frame
892 current_pair->next_check_time = timestamp(0); // check next time
895 // both times negative, so never collides
901 // check if possible collision occurs after weapon expires
902 if ( earliest_time > 1000*Weapons[weapon->instance].lifeleft )
905 // Allow one worst case frametime to elapse (~5 fps)
906 earliest_time -= 200.0f;
908 if (earliest_time > 100) {
909 current_pair->next_check_time = timestamp( fl2i(earliest_time) );
912 current_pair->next_check_time = timestamp(0); // check next time
918 float dist, max_vel, time;
920 max_vel = max_vel_weapon + max_vel_other;
922 // suggest that fudge factor for other radius be changed to other_radius + const (~10)
923 dist = vm_vec_dist( &other->pos, &weapon->pos ) - (other->radius + 10.0f);
925 time = (dist*1000.0f) / max_vel;
926 int time_ms = fl2i(time);
928 // check if possible collision occurs after weapon expires
929 if ( time_ms > 1000*Weapons[weapon->instance].lifeleft )
932 time_ms -= 200; // Allow at least one worst case frametime to elapse (~5 fps)
934 if ( time_ms > 100 ) { // If it takes longer than 1/10th of a second, then delay it
935 current_pair->next_check_time = timestamp(time_ms);
936 //mprintf(( "Delaying %d ms\n", time_ms ));
940 current_pair->next_check_time = timestamp(0); // check next time
948 // Return true if vector from *curpos to *goalpos intersects with object *goalobjp
949 // Else, return false.
950 // radius is radius of object moving from curpos to goalpos.
951 int pp_collide(vector *curpos, vector *goalpos, object *goalobjp, float radius)
955 SDL_assert(goalobjp->type == OBJ_SHIP);
957 ship_model_start(goalobjp);
959 mc.model_num = Ships[goalobjp->instance].modelnum; // Fill in the model to check
960 mc.orient = &goalobjp->orient; // The object's orient
961 mc.pos = &goalobjp->pos; // The object's position
962 mc.p0 = curpos; // Point 1 of ray to check
963 mc.p1 = goalpos; // Point 2 of ray to check
964 mc.flags = MC_CHECK_MODEL | MC_CHECK_SPHERELINE;
969 ship_model_stop(goalobjp);
974 // Setup and call pp_collide for collide_predict_large_ship
975 // Returns true if objp will collide with objp2 before it reaches goal_pos.
976 int cpls_aux(vector *goal_pos, object *objp2, object *objp)
980 radius = objp->radius;
981 if (1.5f * radius < 70.0f)
986 if (pp_collide(&objp->pos, goal_pos, objp2, radius))
992 // Return true if objp will collide with some large object.
993 // Don't check for an object this ship is docked to.
994 int collide_predict_large_ship(object *objp, float distance)
997 vector cur_pos, goal_pos;
1001 sip = &Ship_info[Ships[objp->instance].ship_info_index];
1004 if (objp->type == OBJ_SHIP) {
1005 ai_info *aip = &Ai_info[Ships[objp->instance].ai_index];
1006 if (aip->dock_objnum != -1)
1007 dock_objp = &Objects[aip->dock_objnum];
1010 cur_pos = objp->pos;
1012 vm_vec_scale_add(&goal_pos, &cur_pos, &objp->orient.v.fvec, distance);
1014 for ( objp2 = GET_FIRST(&obj_used_list); objp2 != END_OF_LIST(&obj_used_list); objp2 = GET_NEXT(objp2) ) {
1015 if ((objp != objp2) && (objp2->type == OBJ_SHIP)) {
1016 if (Ship_info[Ships[objp2->instance].ship_info_index].flags & (SIF_BIG_SHIP | SIF_HUGE_SHIP)) {
1017 if (objp2 == dock_objp)
1020 if (cpls_aux(&goal_pos, objp2, objp))
1023 } else if (!(sip->flags & (SIF_BIG_SHIP | SIF_HUGE_SHIP)) && (objp2->type == OBJ_ASTEROID)) {
1024 if (vm_vec_dist_quick(&objp2->pos, &objp->pos) < (distance + objp2->radius)*2.5f) {
1029 d1 = 2.5f * distance + objp2->radius;
1030 count = (int) (d1/(objp2->radius + objp->radius)); // Scale up distance, else looks like there would be a collision.
1032 vm_vec_normalized_dir(&delvec, &goal_pos, &cur_pos);
1033 vm_vec_scale(&delvec, d1/count);
1035 for (; count>0; count--) {
1036 if (vm_vec_dist_quick(&pos, &objp2->pos) < objp->radius + objp2->radius)
1038 vm_vec_add2(&pos, &delvec);
1047 // function to iterate through all object collision pairs looking for weapons
1048 // which could be deleted since they are not going to hit anything. Passed into this
1049 // function is a 'time' parameter used as watermark for which weapons to check.
1051 #define CRW_NO_OBJECT -1
1052 #define CRW_NO_PAIR 0
1053 #define CRW_IN_PAIR 1
1054 #define CRW_CAN_DELETE 2
1056 #define CRW_MAX_TO_DELETE 4
1058 char crw_status[MAX_WEAPONS];
1060 void crw_check_weapon( int weapon_num, int collide_next_check )
1062 float next_check_time;
1065 wp = &Weapons[weapon_num];
1067 // if this weapons life left > time before next collision, then we cannot remove it
1068 crw_status[WEAPON_INDEX(wp)] = CRW_IN_PAIR;
1069 next_check_time = ((float)(timestamp_until(collide_next_check)) / 1000.0f);
1070 if ( wp->lifeleft < next_check_time )
1071 crw_status[WEAPON_INDEX(wp)] = CRW_CAN_DELETE;
1074 int collide_remove_weapons( )
1077 int i, num_deleted, oldest_index, j, loop_count;
1080 // setup remove_weapon array. assume we can remove it.
1081 for (i = 0; i < MAX_WEAPONS; i++ ) {
1082 if ( Weapons[i].objnum == -1 )
1083 crw_status[i] = CRW_NO_OBJECT;
1085 crw_status[i] = CRW_NO_PAIR;
1088 // first pass is to see if any of the weapons don't have collision pairs.
1090 opp = &pair_used_list;
1092 while( opp != NULL ) {
1093 // for each collide pair, if the two objects can still collide, then set the remove_weapon
1094 // parameter for the weapon to 0. need to check both parameters
1095 if ( opp->a->type == OBJ_WEAPON )
1096 crw_check_weapon( opp->a->instance, opp->next_check_time );
1098 if ( opp->b->type == OBJ_WEAPON )
1099 crw_check_weapon( opp->b->instance, opp->next_check_time );
1104 // for each weapon which could be removed, delete the object
1106 for ( i = 0; i < MAX_WEAPONS; i++ ) {
1107 if ( crw_status[i] == CRW_CAN_DELETE ) {
1108 SDL_assert( Weapons[i].objnum != -1 );
1109 obj_delete( Weapons[i].objnum );
1117 // if we didn't remove any weapons, try to the N oldest weapons. first checking for pairs, then
1118 // checking for oldest weapons in general. We will go through the loop a max of 2 times. first time
1119 // through, we check oldest weapons with pairs, next time through, for oldest weapons.
1122 for ( j = 0; j < CRW_MAX_TO_DELETE; j++ ) {
1123 oldest_time = 1000.0f;
1125 for (i = 0; i < MAX_WEAPONS; i++ ) {
1126 if ( Weapons[i].objnum == -1 ) // shouldn't happen, but this is the safe thing to do.
1128 if ( ((loop_count || crw_status[i] == CRW_NO_PAIR)) && (Weapons[i].lifeleft < oldest_time) ) {
1129 oldest_time = Weapons[i].lifeleft;
1133 if ( oldest_index != -1 ) {
1134 obj_delete(Weapons[oldest_index].objnum);
1139 // if we deleted some weapons, then we can break
1144 } while ( loop_count < 2);
1150 void set_hit_struct_info(collision_info_struct *hit, mc_info *mc, int submodel_rot_hit)
1152 hit->edge_hit = mc->edge_hit;
1153 hit->hit_pos = mc->hit_point_world;
1154 hit->hit_time = mc->hit_dist;
1155 hit->submodel_num = mc->hit_submodel;
1157 hit->submodel_rot_hit = submodel_rot_hit;