1 /*
2 * Copyright (C) Volition, Inc. 1999. All rights reserved.
3 *
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 the
6 * source.
7 *
8 */
9
10
11
12 #include "object/objcollide.h"
13 #include "object/object.h"
14 #include "globalincs/linklist.h"
15 #include "io/timer.h"
16 #include "ship/ship.h"
17 #include "weapon/beam.h"
18 #include "weapon/weapon.h"
19 #include "object/objectdock.h"
20
21
22
23 //#define MAX_PAIRS 10000 // Bumped back to 10,000 by WMC
24 // Reduced from 10,000 to 6,000 by MK on 4/1/98.
25 // Most I saw was 3400 in sm1-06a, the asteriod mission. No other mission came close.
26 #define MIN_PAIRS 2500 // start out with this many pairs
27 #define PAIRS_BUMP 1000 // increase by this many avialable pairs when more are needed
28
29 // the next 3 variables are used for pair statistics
30 // also in weapon.cpp there is Weapons_created.
31 int Pairs_created = 0;
32 int Num_pairs = 0;
33 int Num_pairs_allocated = 0;
34 int Num_pairs_checked = 0;
35 int pairs_not_created = 0;
36
37 int Num_pairs_hwm = 0;
38
39 obj_pair *Obj_pairs = NULL;
40
41 obj_pair pair_used_list;
42 obj_pair pair_free_list;
43
44 SCP_vector<int> Collision_sort_list;
45
46 class collider_pair
47 {
48 public:
49 object *a;
50 object *b;
51 int signature_a;
52 int signature_b;
53 int next_check_time;
54 bool initialized;
55
56 // we need to define a constructor because the hash map can
57 // implicitly insert an object when we use the [] operator
collider_pair()58 collider_pair()
59 : a(NULL), b(NULL), signature_a(-1), signature_b(-1), next_check_time(-1), initialized(false)
60 {}
61 };
62
63 SCP_hash_map<uint, collider_pair> Collision_cached_pairs;
64
65 struct checkobject;
66 extern checkobject CheckObjects[MAX_OBJECTS];
67
68 extern int Cmdline_old_collision_sys;
69
obj_pairs_close()70 void obj_pairs_close()
71 {
72 if (Obj_pairs != NULL) {
73 vm_free(Obj_pairs);
74 Obj_pairs = NULL;
75 }
76
77 Num_pairs_allocated = 0;
78 }
79
obj_all_collisions_retime(int checkdly)80 void obj_all_collisions_retime(int checkdly)
81 // sets all collisions to be checked (in 25ms by default)
82 // this is for when we warp objects
83 {
84 obj_pair *parent, *tmp;
85
86 parent = &pair_used_list;
87 tmp = parent->next;
88
89
90 while (tmp != NULL)
91 {
92 tmp->next_check_time = timestamp(checkdly);
93 tmp = tmp->next;
94 }
95 }
96
97
obj_reset_pairs()98 void obj_reset_pairs()
99 {
100 int i;
101
102 // mprintf(( "Resetting object pairs...\n" ));
103
104 pair_used_list.a = pair_used_list.b = NULL;
105 pair_used_list.next = NULL;
106 pair_free_list.a = pair_free_list.b = NULL;
107
108 Num_pairs = 0;
109
110 if (Obj_pairs != NULL) {
111 vm_free(Obj_pairs);
112 Obj_pairs = NULL;
113 }
114
115 Obj_pairs = (obj_pair*) vm_malloc_q( sizeof(obj_pair) * MIN_PAIRS );
116
117 if ( Obj_pairs == NULL ) {
118 mprintf(("Unable to create space for collision pairs!!\n"));
119 return;
120 }
121
122 Num_pairs_allocated = MIN_PAIRS;
123
124 memset( Obj_pairs, 0, sizeof(obj_pair) * MIN_PAIRS );
125
126 for (i = 0; i < MIN_PAIRS; i++) {
127 Obj_pairs[i].next = &Obj_pairs[i+1];
128 }
129
130 Obj_pairs[MIN_PAIRS-1].next = NULL;
131
132 pair_free_list.next = &Obj_pairs[0];
133 }
134
135 // returns true if we should reject object pair if one is child of other.
reject_obj_pair_on_parent(object * A,object * B)136 int reject_obj_pair_on_parent(object *A, object *B)
137 {
138 if (A->type == OBJ_SHIP) {
139 if (B->type == OBJ_DEBRIS) {
140 if (B->parent_sig == A->signature) {
141 return 0;
142 }
143 }
144 }
145
146 if (B->type == OBJ_SHIP) {
147 if (A->type == OBJ_DEBRIS) {
148 if (A->parent_sig == B->signature) {
149 return 0;
150 }
151 }
152 }
153
154 if (A->parent_sig == B->signature) {
155 return 1;
156 }
157
158 if (B->parent_sig == A->signature) {
159 return 1;
160 }
161
162 return 0;
163 }
164
reject_due_collision_groups(object * A,object * B)165 int reject_due_collision_groups(object *A, object *B)
166 {
167 if (A->collision_group_id == 0 || B->collision_group_id == 0)
168 return 0;
169
170 return (A->collision_group_id & B->collision_group_id);
171 }
172
173 // Adds the pair to the pair list
obj_add_pair(object * A,object * B,int check_time,int add_to_end)174 void obj_add_pair( object *A, object *B, int check_time, int add_to_end )
175 {
176 uint ctype;
177 int (*check_collision)( obj_pair *pair );
178 int swapped = 0;
179
180 check_collision = NULL;
181
182 if ( Num_pairs_allocated == 0 ) return; // don't have anything to add the pair too
183
184 if ( A==B ) return; // Don't check collisions with yourself
185
186 if ( !(A->flags&OF_COLLIDES) ) return; // This object doesn't collide with anything
187 if ( !(B->flags&OF_COLLIDES) ) return; // This object doesn't collide with anything
188
189 // Make sure you're not checking a parent with it's kid or vicy-versy
190 // if ( A->parent_sig == B->signature && !(A->type == OBJ_SHIP && B->type == OBJ_DEBRIS) ) return;
191 // if ( B->parent_sig == A->signature && !(A->type == OBJ_DEBRIS && B->type == OBJ_SHIP) ) return;
192 if ( reject_obj_pair_on_parent(A,B) ) {
193 return;
194 }
195
196 Assert( A->type < 127 );
197 Assert( B->type < 127 );
198
199 ctype = COLLISION_OF(A->type,B->type);
200 switch( ctype ) {
201 case COLLISION_OF(OBJ_WEAPON,OBJ_SHIP):
202 swapped = 1;
203 check_collision = collide_ship_weapon;
204 break;
205 case COLLISION_OF(OBJ_SHIP, OBJ_WEAPON):
206 check_collision = collide_ship_weapon;
207 break;
208 case COLLISION_OF(OBJ_DEBRIS, OBJ_WEAPON):
209 check_collision = collide_debris_weapon;
210 break;
211 case COLLISION_OF(OBJ_WEAPON, OBJ_DEBRIS):
212 swapped = 1;
213 check_collision = collide_debris_weapon;
214 break;
215 case COLLISION_OF(OBJ_DEBRIS, OBJ_SHIP):
216 check_collision = collide_debris_ship;
217 break;
218 case COLLISION_OF(OBJ_SHIP, OBJ_DEBRIS):
219 check_collision = collide_debris_ship;
220 swapped = 1;
221 break;
222 case COLLISION_OF(OBJ_ASTEROID, OBJ_WEAPON):
223 // Only check collision's with player weapons
224 // if ( Objects[B->parent].flags & OF_PLAYER_SHIP ) {
225 check_collision = collide_asteroid_weapon;
226 // }
227 break;
228 case COLLISION_OF(OBJ_WEAPON, OBJ_ASTEROID):
229 swapped = 1;
230 // Only check collision's with player weapons
231 // if ( Objects[A->parent].flags & OF_PLAYER_SHIP ) {
232 check_collision = collide_asteroid_weapon;
233 // }
234 break;
235 case COLLISION_OF(OBJ_ASTEROID, OBJ_SHIP):
236 // Only check collisions with player ships
237 // if ( B->flags & OF_PLAYER_SHIP ) {
238 check_collision = collide_asteroid_ship;
239 // }
240 break;
241 case COLLISION_OF(OBJ_SHIP, OBJ_ASTEROID):
242 // Only check collisions with player ships
243 // if ( A->flags & OF_PLAYER_SHIP ) {
244 check_collision = collide_asteroid_ship;
245 // }
246 swapped = 1;
247 break;
248 case COLLISION_OF(OBJ_SHIP,OBJ_SHIP):
249 check_collision = collide_ship_ship;
250 break;
251
252 case COLLISION_OF(OBJ_BEAM, OBJ_SHIP):
253 if(beam_collide_early_out(A, B)){
254 return;
255 }
256 check_collision = beam_collide_ship;
257 break;
258
259 case COLLISION_OF(OBJ_BEAM, OBJ_ASTEROID):
260 if(beam_collide_early_out(A, B)){
261 return;
262 }
263 check_collision = beam_collide_asteroid;
264 break;
265
266 case COLLISION_OF(OBJ_BEAM, OBJ_DEBRIS):
267 if(beam_collide_early_out(A, B)){
268 return;
269 }
270 check_collision = beam_collide_debris;
271 break;
272
273 case COLLISION_OF(OBJ_BEAM, OBJ_WEAPON):
274 if(beam_collide_early_out(A, B)){
275 return;
276 }
277 check_collision = beam_collide_missile;
278 break;
279
280 case COLLISION_OF(OBJ_WEAPON, OBJ_WEAPON): {
281 weapon_info *awip, *bwip;
282 awip = &Weapon_info[Weapons[A->instance].weapon_info_index];
283 bwip = &Weapon_info[Weapons[B->instance].weapon_info_index];
284
285 if ((awip->weapon_hitpoints > 0) || (bwip->weapon_hitpoints > 0)) {
286 if (bwip->weapon_hitpoints == 0) {
287 check_collision = collide_weapon_weapon;
288 swapped=1;
289 } else {
290 check_collision = collide_weapon_weapon;
291 }
292 }
293 /*
294
295 if (awip->subtype != WP_LASER || bwip->subtype != WP_LASER) {
296 if (awip->subtype == WP_LASER) {
297 if ( bwip->wi_flags & WIF_BOMB ) {
298 check_collision = collide_weapon_weapon;
299 }
300 } else if (bwip->subtype == WP_LASER) {
301 if ( awip->wi_flags & WIF_BOMB ) {
302 check_collision = collide_weapon_weapon;
303 swapped=1;
304 }
305 } else {
306 if ( (awip->wi_flags&WIF_BOMB) || (bwip->wi_flags&WIF_BOMB) ) {
307 check_collision = collide_weapon_weapon;
308 }
309 }
310 }
311 */
312 /*
313 int atype, btype;
314
315 atype = Weapon_info[Weapons[A->instance].weapon_info_index].subtype;
316 btype = Weapon_info[Weapons[B->instance].weapon_info_index].subtype;
317
318 if ((atype == WP_LASER) && (btype == WP_MISSILE))
319 check_collision = collide_weapon_weapon;
320 else if ((atype == WP_MISSILE) && (btype == WP_LASER)) {
321 check_collision = collide_weapon_weapon;
322 swapped = 1;
323 } else if ((atype == WP_MISSILE) && (btype == WP_MISSILE))
324 check_collision = collide_weapon_weapon;
325 */
326
327 break;
328 }
329
330 default:
331 return;
332 }
333
334 // Swap them if needed
335 if ( swapped ) {
336 object *tmp = A;
337 A = B;
338 B = tmp;
339 }
340
341 // if there are any more obj_pair checks
342 // we should then add function int maybe_not_add_obj_pair()
343 // MWA -- 4/1/98 -- I'd do it, but I don't want to bust anything, so I'm doing my stuff here instead :-)
344 //if ( MULTIPLAYER_CLIENT && !(Netgame.debug_flags & NETD_FLAG_CLIENT_NODAMAGE)){
345 // multiplayer clients will only do ship/ship collisions, and their own ship to boot
346 // if ( check_collision != collide_ship_ship ){
347 // return;
348 // }
349
350 // if ( (A != Player_obj) && (B != Player_obj) ){
351 // return;
352 // }
353 //}
354
355 // only check debris:weapon collisions for player
356 if (check_collision == collide_debris_weapon) {
357 // weapon is B
358 if ( !(Weapon_info[Weapons[B->instance].weapon_info_index].wi_flags & WIF_TURNS) ) {
359 // check for dumbfire weapon
360 // check if debris is behind laser
361 float vdot;
362 if (Weapon_info[Weapons[B->instance].weapon_info_index].subtype == WP_LASER) {
363 vec3d velocity_rel_weapon;
364 vm_vec_sub(&velocity_rel_weapon, &B->phys_info.vel, &A->phys_info.vel);
365 vdot = -vm_vec_dot(&velocity_rel_weapon, &B->orient.vec.fvec);
366 } else {
367 vdot = vm_vec_dot( &A->phys_info.vel, &B->phys_info.vel);
368 }
369 if ( vdot <= 0.0f ) {
370 // They're heading in opposite directions...
371 // check their positions
372 vec3d weapon2other;
373 vm_vec_sub( &weapon2other, &A->pos, &B->pos );
374 float pdot = vm_vec_dot( &B->orient.vec.fvec, &weapon2other );
375 if ( pdot <= -A->radius ) {
376 // The other object is behind the weapon by more than
377 // its radius, so it will never hit...
378 return;
379 }
380 }
381
382 // check dist vs. dist moved during weapon lifetime
383 vec3d delta_v;
384 vm_vec_sub(&delta_v, &B->phys_info.vel, &A->phys_info.vel);
385 if (vm_vec_dist_squared(&A->pos, &B->pos) > (vm_vec_mag_squared(&delta_v)*Weapons[B->instance].lifeleft*Weapons[B->instance].lifeleft)) {
386 return;
387 }
388
389 // for nonplayer ships, only create collision pair if close enough
390 if ( (B->parent >= 0) && !(Objects[B->parent].flags & OF_PLAYER_SHIP) && (vm_vec_dist(&B->pos, &A->pos) < (4.0f*A->radius + 200.0f)) )
391 return;
392 }
393 }
394
395 // don't check same team laser:ship collisions on small ships if not player
396 if (check_collision == collide_ship_weapon) {
397 // weapon is B
398 if ( (B->parent >= 0)
399 && !(Objects[B->parent].flags & OF_PLAYER_SHIP)
400 && (Ships[Objects[B->parent].instance].team == Ships[A->instance].team)
401 && (Ship_info[Ships[A->instance].ship_info_index].flags & SIF_SMALL_SHIP)
402 && (Weapon_info[Weapons[B->instance].weapon_info_index].subtype == WP_LASER) ) {
403 pairs_not_created++;
404 return;
405 }
406 }
407
408 if ( !check_collision ) return;
409 Pairs_created++;
410
411 // At this point, we have determined that collisions between
412 // these two should be checked, so add the pair to the
413 // collision pair list.
414
415 if ( pair_free_list.next == NULL ) {
416 nprintf(( "collision", "Out of object pairs!! Not all collisions will work!\n" ));
417 return;
418 }
419
420 Num_pairs++;
421 /* if (Num_pairs > Num_pairs_hwm) {
422 Num_pairs_hwm = Num_pairs;
423 //nprintf(("AI", "Num_pairs high water mark = %i\n", Num_pairs_hwm));
424 }
425 */
426
427 if ( Num_pairs >= (Num_pairs_allocated - 20) ) {
428 int i;
429
430 Assert( Obj_pairs != NULL );
431
432 int old_pair_count = Num_pairs_allocated;
433 obj_pair *old_pairs_ptr = Obj_pairs;
434
435 // determine where we need to update the "previous" ptrs to
436 int prev_free_mark = (pair_free_list.next - old_pairs_ptr);
437 int prev_used_mark = (pair_used_list.next - old_pairs_ptr);
438
439 Obj_pairs = (obj_pair*) vm_realloc_q( Obj_pairs, sizeof(obj_pair) * (Num_pairs_allocated + PAIRS_BUMP) );
440
441 // allow us to fail here and only if we don't do we setup the new pairs
442
443 if (Obj_pairs == NULL) {
444 // failed, just go back to the way we were and use only the pairs we have already
445 Obj_pairs = old_pairs_ptr;
446 } else {
447 Num_pairs_allocated += PAIRS_BUMP;
448
449 Assert( Obj_pairs != NULL );
450
451 // have to reset all of the "next" ptrs for the old set and handle the new set
452 for (i = 0; i < Num_pairs_allocated; i++) {
453 if (i >= old_pair_count) {
454 memset( &Obj_pairs[i], 0, sizeof(obj_pair) );
455 Obj_pairs[i].next = &Obj_pairs[i+1];
456 } else {
457 if (Obj_pairs[i].next != NULL) {
458 // the "next" ptr will end up going backwards for used pairs so we have
459 // to allow for that with this craziness...
460 int next_mark = (Obj_pairs[i].next - old_pairs_ptr);
461 Obj_pairs[i].next = &Obj_pairs[next_mark];
462 }
463
464 // catch that last NULL from the previously allocated set
465 if ( i == (old_pair_count-1) ) {
466 Obj_pairs[i].next = &Obj_pairs[i+1];
467 }
468 }
469 }
470
471 Obj_pairs[Num_pairs_allocated-1].next = NULL;
472
473 // reset the "previous" ptrs
474 pair_free_list.next = &Obj_pairs[prev_free_mark];
475 pair_used_list.next = &Obj_pairs[prev_used_mark];
476 }
477 }
478
479 // get a new obj_pair from the free list
480 obj_pair * new_pair = pair_free_list.next;
481 pair_free_list.next = new_pair->next;
482
483 if ( add_to_end ) {
484 obj_pair *last, *tmp;
485
486 last = tmp = pair_used_list.next;
487 while( tmp != NULL ) {
488 if ( tmp->next == NULL )
489 last = tmp;
490
491 tmp = tmp->next;
492 }
493
494 if ( last == NULL )
495 last = &pair_used_list;
496
497 last->next = new_pair;
498 Assert(new_pair != NULL);
499 new_pair->next = NULL;
500 }
501 else {
502 new_pair->next = pair_used_list.next;
503 pair_used_list.next = new_pair;
504 }
505
506 A->num_pairs++;
507 B->num_pairs++;
508
509 new_pair->a = A;
510 new_pair->b = B;
511 new_pair->check_collision = check_collision;
512
513 if ( check_time == -1 ){
514 new_pair->next_check_time = timestamp(0); // 0 means instantly time out
515 } else {
516 new_pair->next_check_time = check_time;
517 }
518
519 }
520
521 MONITOR(NumPairs)
522 MONITOR(NumPairsChecked)
523
524 //#define PAIR_STATS
525
526 extern int Cmdline_dis_collisions;
obj_check_all_collisions()527 void obj_check_all_collisions()
528 {
529 obj_pair *parent, *tmp;
530
531 #ifdef PAIR_STATS
532 // debug info
533 float avg_time_to_next_check = 0.0f;
534 #endif
535
536 if (Cmdline_dis_collisions)
537 return;
538
539 if ( !(Game_detail_flags & DETAIL_FLAG_COLLISION) )
540 return;
541
542
543 parent = &pair_used_list;
544 tmp = parent->next;
545
546 Num_pairs_checked = 0;
547
548 while (tmp != NULL) {
549 int removed = 0;
550
551 if ( !timestamp_elapsed(tmp->next_check_time) )
552 goto NextPair;
553
554 if ( (tmp->a) && (tmp->b) ) {
555 Num_pairs_checked++;
556
557 if ( (*tmp->check_collision)(tmp) ) {
558 // We never need to check this pair again.
559 #if 0 //def DONT_REMOVE_PAIRS
560 // Never check it again, but keep the pair around
561 // (useful for debugging)
562 tmp->next_check_time = timestamp(-1);
563 #else
564 // Never check it again, so remove the pair
565 removed = 1;
566 tmp->a->num_pairs--;
567 Assert( tmp->a->num_pairs > -1 );
568 tmp->b->num_pairs--;
569 Assert( tmp->b->num_pairs > -1 );
570 Num_pairs--;
571 // Assert(Num_pairs >= 0);
572 parent->next = tmp->next;
573 tmp->a = tmp->b = NULL;
574 tmp->next = pair_free_list.next;
575 pair_free_list.next = tmp;
576 tmp = parent->next;
577 #endif
578 }
579 }
580
581 NextPair:
582 if ( !removed ) {
583 parent = tmp;
584 tmp = tmp->next;
585
586 #ifdef PAIR_STATS
587 // debug info
588 if (tmp) {
589 int add_time = timestamp_until( tmp->next_check_time );
590 if (add_time > 0)
591 avg_time_to_next_check += (float) add_time;
592 }
593 #endif
594 }
595 }
596
597 MONITOR_INC(NumPairs, Num_pairs);
598 MONITOR_INC(NumPairsChecked, Num_pairs_checked);
599
600 #ifdef PAIR_STATS
601 avg_time_to_next_check = avg_time_to_next_check / Num_pairs;
602 extern int Num_hull_pieces;
603 extern int Weapons_created;
604 // 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 ));
605 // 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) ));
606 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) ));
607 pairs_not_created = 0;
608 Weapons_created = 0;
609 Pairs_created = 0;
610 #endif
611
612 // What percent of the pairs did we check?
613 // FYI: (n*(n-1))/2 is the total number of checks required for comparing n objects.
614
615 // if ( org_pairs > 1 ) {
616 // Object_checked_percentage = (i2fl(n)*100.0f) / i2fl(org_pairs);
617 // } else {
618 // Object_checked_percentage = 0.0f;
619 // }
620
621 }
622
623 // See if two lines intersect by doing recursive subdivision.
624 // Bails out if larger distance traveled is less than sum of radii + 1.0f.
collide_subdivide(vec3d * p0,vec3d * p1,float prad,vec3d * q0,vec3d * q1,float qrad)625 int collide_subdivide(vec3d *p0, vec3d *p1, float prad, vec3d *q0, vec3d *q1, float qrad)
626 {
627 float a_dist, b_dist, ab_dist;
628
629 a_dist = vm_vec_dist(p0, p1);
630 b_dist = vm_vec_dist(q0, q1);
631
632 ab_dist = vm_vec_dist(p1, q1);
633
634 // See if their spheres intersect
635 if (ab_dist < a_dist + b_dist + prad + qrad) {
636 if (ab_dist < prad + qrad)
637 return 1;
638 else if (vm_vec_dist(p0, q0) < prad + qrad)
639 return 1;
640 else if (MAX(a_dist, b_dist) < prad + qrad + 1.0f)
641 return 0;
642 else {
643 int r1, r2 = 0;
644 vec3d pa, qa;
645
646 vm_vec_avg(&pa, p0, p1);
647 vm_vec_avg(&qa, q0, q1);
648 r1 = collide_subdivide(p0, &pa, prad, q0, &qa, qrad);
649 if (!r1)
650 r2 = collide_subdivide(&pa, p1, prad, &qa, q1, qrad);
651
652 return r1 | r2;
653 }
654 } else
655 return 0;
656 }
657
658
659
660 // Return true if object A is expected to collide with object B within time duration
661 // For purposes of this check, the first object moves from current location to predicted
662 // location. The second object is assumed to be where it will be at time duration, NOT
663 // where it currently is.
664 // radius_scale is used to control the precision of the check.
665 // If 0.0, then use polygon models to perform check, slow and accurate
666 // If !0.0, then use as a scale on the radius of the objects. 1.0 is Descent style
667 // collisions. Larger values can be used to be sloppy about the collisions which
668 // is useful if a moving object wants to prevent a collision.
objects_will_collide(object * A,object * B,float duration,float radius_scale)669 int objects_will_collide(object *A, object *B, float duration, float radius_scale)
670 {
671 object A_future;
672 vec3d hitpos;
673
674
675 A_future = *A;
676 vm_vec_scale_add2(&A_future.pos, &A->phys_info.vel, duration);
677
678 if (radius_scale == 0.0f) {
679 return ship_check_collision_fast(B, &A_future, &hitpos );
680 } else {
681 float size_A, size_B, dist, r;
682 vec3d nearest_point;
683
684 size_A = A->radius * radius_scale;
685 size_B = B->radius * radius_scale;
686
687 // If A is moving, check along vector.
688 if (A->phys_info.speed != 0.0f) {
689 r = find_nearest_point_on_line(&nearest_point, &A->pos, &A_future.pos, &B->pos);
690 if (r < 0) {
691 nearest_point = A->pos;
692 } else if (r > 1) {
693 nearest_point = A_future.pos;
694 }
695 dist = vm_vec_dist_quick(&B->pos, &nearest_point);
696 return (dist < size_A + size_B);
697 } else {
698 return vm_vec_dist_quick(&B->pos, &A->pos) < size_A + size_B;
699 }
700 }
701 }
702
703 // Return true if the vector from *start_pos to *end_pos is within objp->radius*radius_scale of *objp
vector_object_collision(vec3d * start_pos,vec3d * end_pos,object * objp,float radius_scale)704 int vector_object_collision(vec3d *start_pos, vec3d *end_pos, object *objp, float radius_scale)
705 {
706 float dist, r;
707 vec3d nearest_point;
708
709 r = find_nearest_point_on_line(&nearest_point, start_pos, end_pos, &objp->pos);
710 if ((r >= 0.0f) && (r <= 1.0f)) {
711 dist = vm_vec_dist_quick(&objp->pos, &nearest_point);
712
713 return (dist < objp->radius * radius_scale);
714 } else
715 return 0;
716 }
717
718 // Returns TRUE if the weapon will never hit the other object.
719 // If it can it predicts how long until these two objects need
720 // to be checked and fills the time in in current_pair.
weapon_will_never_hit(object * obj_weapon,object * other,obj_pair * current_pair)721 int weapon_will_never_hit( object *obj_weapon, object *other, obj_pair * current_pair )
722 {
723
724 Assert( obj_weapon->type == OBJ_WEAPON );
725 weapon *wp = &Weapons[obj_weapon->instance];
726 weapon_info *wip = &Weapon_info[wp->weapon_info_index];
727
728 // mprintf(( "Frame: %d, Weapon=%d, Other=%d, pair=$%08x\n", G3_frame_count, OBJ_INDEX(weapon), OBJ_INDEX(other), current_pair ));
729
730
731 // Do some checks for weapons that don't turn
732 if ( !(wip->wi_flags & WIF_TURNS) ) {
733
734 // This first check is to see if a weapon is behind an object, and they
735 // are heading in opposite directions. If so, we don't need to ever check
736 // them again. This is only valid for weapons that don't turn.
737
738 float vdot;
739 if (wip->subtype == WP_LASER) {
740 vec3d velocity_rel_weapon;
741 vm_vec_sub(&velocity_rel_weapon, &obj_weapon->phys_info.vel, &other->phys_info.vel);
742 vdot = -vm_vec_dot(&velocity_rel_weapon, &obj_weapon->orient.vec.fvec);
743 } else {
744 vdot = vm_vec_dot( &other->phys_info.vel, &obj_weapon->phys_info.vel);
745 }
746 if ( vdot <= 0.0f ) {
747 // They're heading in opposite directions...
748 // check their positions
749 vec3d weapon2other;
750 vm_vec_sub( &weapon2other, &other->pos, &obj_weapon->pos );
751 float pdot = vm_vec_dot( &obj_weapon->orient.vec.fvec, &weapon2other );
752 if ( pdot <= -other->radius ) {
753 // The other object is behind the weapon by more than
754 // its radius, so it will never hit...
755 return 1;
756 }
757 }
758
759 // FUTURE ENHANCEMENT IDEAS
760
761 // Given a laser does it hit a slow or not moving object
762 // in its life or the next n seconds? We'd actually need to check the
763 // model for this.
764
765 }
766
767
768 // This check doesn't care about orient, only looks at the maximum speed
769 // of the two objects, so it knows that in the next n seconds, they can't
770 // go further than some distance, so don't bother checking collisions for
771 // that time. This is very rough, but is so general that it works for
772 // everything and immidiately gets rid of a lot of cases.
773
774 if ( current_pair ) {
775 // Find the time it will take before these get within each others distances.
776 // tmp->next_check_time = timestamp(500);
777 //vector max_vel; //maximum foward velocity in x,y,z
778
779 float max_vel_weapon, max_vel_other;
780
781 //SUSHI: Fix bug where additive weapon velocity screws up collisions
782 //Assumes that weapons which don't home don't change speed, which is currently the case.
783 if (!(wip->wi_flags & WIF_TURNS))
784 max_vel_weapon = obj_weapon->phys_info.speed;
785 else if (wp->lssm_stage==5)
786 max_vel_weapon = wip->lssm_stage5_vel;
787 else
788 max_vel_weapon = wp->weapon_max_vel;
789
790 max_vel_other = other->phys_info.max_vel.xyz.z;
791 if (max_vel_other < 10.0f) {
792 if ( vm_vec_mag_squared( &other->phys_info.vel ) > 100 ) {
793 // bump up velocity from collision
794 max_vel_other = vm_vec_mag( &other->phys_info.vel ) + 10.0f;
795 } else {
796 max_vel_other = 10.0f; // object may move from collision
797 }
798 }
799
800 // check weapon that does not turn against sphere expanding at ship maxvel
801 // compare (weeapon) ray with expanding sphere (ship) to find earliest possible collision time
802 // look for two time solutions to Xw = Xs, where Xw = Xw0 + Vwt*t Xs = Xs + Vs*(t+dt), where Vs*dt = radius of ship
803 // Since direction of Vs is unknown, solve for (Vs*t) and find norm of both sides
804 if ( !(wip->wi_flags & WIF_TURNS) ) {
805 vec3d delta_x, laser_vel;
806 float a,b,c, delta_x_dot_vl, delta_t;
807 float root1, root2, root, earliest_time;
808
809 if (max_vel_weapon == max_vel_other) {
810 // this will give us NAN using the below formula, so check every frame
811 current_pair->next_check_time = timestamp(0);
812 return 0;
813 }
814
815 vm_vec_sub( &delta_x, &obj_weapon->pos, &other->pos );
816 laser_vel = obj_weapon->phys_info.vel;
817 // vm_vec_copy_scale( &laser_vel, &weapon->orient.vec.fvec, max_vel_weapon );
818 delta_t = (other->radius + 10.0f) / max_vel_other; // time to get from center to radius of other obj
819 delta_x_dot_vl = vm_vec_dotprod( &delta_x, &laser_vel );
820
821 a = max_vel_weapon*max_vel_weapon - max_vel_other*max_vel_other;
822 b = 2.0f * (delta_x_dot_vl - max_vel_other*max_vel_other*delta_t);
823 c = vm_vec_mag_squared( &delta_x ) - max_vel_other*max_vel_other*delta_t*delta_t;
824
825 float discriminant = b*b - 4.0f*a*c;
826 if ( discriminant < 0) {
827 // never hit
828 return 1;
829 } else {
830 root = fl_sqrt( discriminant );
831 root1 = (-b + root) / (2.0f * a) * 1000.0f; // get time in ms
832 root2 = (-b - root) / (2.0f * a) * 1000.0f; // get time in ms
833 }
834
835 // standard algorithm
836 if (max_vel_weapon > max_vel_other) {
837 // find earliest positive time
838 if ( root1 > root2 ) {
839 float temp = root1;
840 root1 = root2;
841 root2 = temp;
842 }
843
844 if (root1 > 0) {
845 earliest_time = root1;
846 } else if (root2 > 0) {
847 // root1 < 0 and root2 > 0, so we're inside sphere and next check should be next frame
848 current_pair->next_check_time = timestamp(0); // check next time
849 return 0;
850 } else {
851 // both times negative, so never collides
852 return 1;
853 }
854 }
855 // need to modify it for weapons that are slower than ships
856 else {
857 if (root2 > 0) {
858 earliest_time = root2;
859 } else {
860 current_pair->next_check_time = timestamp(0);
861 return 0;
862 }
863 }
864
865
866
867 // check if possible collision occurs after weapon expires
868 if ( earliest_time > 1000*wp->lifeleft )
869 return 1;
870
871 // Allow one worst case frametime to elapse (~5 fps)
872 earliest_time -= 200.0f;
873
874 if (earliest_time > 100) {
875 current_pair->next_check_time = timestamp( fl2i(earliest_time) );
876 return 0;
877 } else {
878 current_pair->next_check_time = timestamp(0); // check next time
879 return 0;
880 }
881
882 } else {
883
884 float dist, max_vel, time;
885
886 max_vel = max_vel_weapon + max_vel_other;
887
888 // suggest that fudge factor for other radius be changed to other_radius + const (~10)
889 dist = vm_vec_dist( &other->pos, &obj_weapon->pos ) - (other->radius + 10.0f);
890 if ( dist > 0.0f ) {
891 time = (dist*1000.0f) / max_vel;
892 int time_ms = fl2i(time);
893
894 // check if possible collision occurs after weapon expires
895 if ( time_ms > 1000*wp->lifeleft )
896 return 1;
897
898 time_ms -= 200; // Allow at least one worst case frametime to elapse (~5 fps)
899
900 if ( time_ms > 100 ) { // If it takes longer than 1/10th of a second, then delay it
901 current_pair->next_check_time = timestamp(time_ms);
902 //mprintf(( "Delaying %d ms\n", time_ms ));
903 return 0;
904 }
905 }
906 current_pair->next_check_time = timestamp(0); // check next time
907
908 }
909 }
910
911 return 0;
912 }
913
914 // Return true if vector from *curpos to *goalpos intersects with object *goalobjp
915 // Else, return false.
916 // radius is radius of object moving from curpos to goalpos.
pp_collide(vec3d * curpos,vec3d * goalpos,object * goalobjp,float radius)917 int pp_collide(vec3d *curpos, vec3d *goalpos, object *goalobjp, float radius)
918 {
919 mc_info mc;
920 mc_info_init(&mc);
921
922 Assert(goalobjp->type == OBJ_SHIP);
923
924 mc.model_instance_num = Ships[goalobjp->instance].model_instance_num;
925 mc.model_num = Ship_info[Ships[goalobjp->instance].ship_info_index].model_num; // Fill in the model to check
926 mc.orient = &goalobjp->orient; // The object's orient
927 mc.pos = &goalobjp->pos; // The object's position
928 mc.p0 = curpos; // Point 1 of ray to check
929 mc.p1 = goalpos; // Point 2 of ray to check
930 mc.flags = MC_CHECK_MODEL | MC_CHECK_SPHERELINE;
931 mc.radius = radius;
932
933 model_collide(&mc);
934
935 return mc.num_hits;
936 }
937
938 // Setup and call pp_collide for collide_predict_large_ship
939 // Returns true if objp will collide with objp2 before it reaches goal_pos.
cpls_aux(vec3d * goal_pos,object * objp2,object * objp)940 int cpls_aux(vec3d *goal_pos, object *objp2, object *objp)
941 {
942 float radius;
943
944 radius = objp->radius;
945 if (1.5f * radius < 70.0f)
946 radius *= 1.5f;
947 else
948 radius = 70.0f;
949
950 if (pp_collide(&objp->pos, goal_pos, objp2, radius))
951 return 1;
952 else
953 return 0;
954 }
955
956 // Return true if objp will collide with some large object.
957 // Don't check for an object this ship is docked to.
collide_predict_large_ship(object * objp,float distance)958 int collide_predict_large_ship(object *objp, float distance)
959 {
960 object *objp2;
961 vec3d cur_pos, goal_pos;
962 ship_info *sip;
963
964 sip = &Ship_info[Ships[objp->instance].ship_info_index];
965
966 cur_pos = objp->pos;
967
968 vm_vec_scale_add(&goal_pos, &cur_pos, &objp->orient.vec.fvec, distance);
969
970 for ( objp2 = GET_FIRST(&obj_used_list); objp2 != END_OF_LIST(&obj_used_list); objp2 = GET_NEXT(objp2) ) {
971 if ((objp != objp2) && (objp2->type == OBJ_SHIP)) {
972 if (Ship_info[Ships[objp2->instance].ship_info_index].flags & (SIF_BIG_SHIP | SIF_HUGE_SHIP)) {
973 if (dock_check_find_docked_object(objp, objp2))
974 continue;
975
976 if (cpls_aux(&goal_pos, objp2, objp))
977 return 1;
978 }
979 } else if (!(sip->flags & (SIF_BIG_SHIP | SIF_HUGE_SHIP)) && (objp2->type == OBJ_ASTEROID)) {
980 if (vm_vec_dist_quick(&objp2->pos, &objp->pos) < (distance + objp2->radius)*2.5f) {
981 vec3d pos, delvec;
982 int count;
983 float d1;
984
985 d1 = 2.5f * distance + objp2->radius;
986 count = (int) (d1/(objp2->radius + objp->radius)); // Scale up distance, else looks like there would be a collision.
987 pos = cur_pos;
988 vm_vec_normalized_dir(&delvec, &goal_pos, &cur_pos);
989 vm_vec_scale(&delvec, d1/count);
990
991 for (; count>0; count--) {
992 if (vm_vec_dist_quick(&pos, &objp2->pos) < objp->radius + objp2->radius)
993 return 1;
994 vm_vec_add2(&pos, &delvec);
995 }
996 }
997 }
998 }
999
1000 return 0;
1001 }
1002
1003 // function to iterate through all object collision pairs looking for weapons
1004 // which could be deleted since they are not going to hit anything. Passed into this
1005 // function is a 'time' parameter used as watermark for which weapons to check.
1006
1007 #define CRW_NO_OBJECT -1
1008 #define CRW_NO_PAIR 0
1009 #define CRW_IN_PAIR 1
1010 #define CRW_CAN_DELETE 2
1011
1012 #define CRW_MAX_TO_DELETE 4
1013
1014 char crw_status[MAX_WEAPONS];
1015
crw_check_weapon(int weapon_num,int collide_next_check)1016 void crw_check_weapon( int weapon_num, int collide_next_check )
1017 {
1018 float next_check_time;
1019 weapon *wp;
1020
1021 wp = &Weapons[weapon_num];
1022
1023 // if this weapons life left > time before next collision, then we cannot remove it
1024 crw_status[WEAPON_INDEX(wp)] = CRW_IN_PAIR;
1025 next_check_time = ((float)(timestamp_until(collide_next_check)) / 1000.0f);
1026 if ( wp->lifeleft < next_check_time )
1027 crw_status[WEAPON_INDEX(wp)] = CRW_CAN_DELETE;
1028 }
1029
collide_remove_weapons()1030 int collide_remove_weapons( )
1031 {
1032 obj_pair *opp;
1033 int i, num_deleted, oldest_index, j, loop_count;
1034 float oldest_time;
1035
1036 // setup remove_weapon array. assume we can remove it.
1037 for (i = 0; i < MAX_WEAPONS; i++ ) {
1038 if ( Weapons[i].objnum == -1 )
1039 crw_status[i] = CRW_NO_OBJECT;
1040 else
1041 crw_status[i] = CRW_NO_PAIR;
1042 }
1043
1044 // first pass is to see if any of the weapons don't have collision pairs.
1045
1046 if ( Cmdline_old_collision_sys ) {
1047 opp = &pair_used_list;
1048 opp = opp->next;
1049 while( opp != NULL ) {
1050 // for each collide pair, if the two objects can still collide, then set the remove_weapon
1051 // parameter for the weapon to 0. need to check both parameters
1052 if ( opp->a->type == OBJ_WEAPON )
1053 crw_check_weapon( opp->a->instance, opp->next_check_time );
1054
1055 if ( opp->b->type == OBJ_WEAPON )
1056 crw_check_weapon( opp->b->instance, opp->next_check_time );
1057
1058 opp = opp->next;
1059 }
1060 } else {
1061 SCP_hash_map<uint, collider_pair>::iterator it;
1062 collider_pair *pair_obj;
1063
1064 for ( it = Collision_cached_pairs.begin(); it != Collision_cached_pairs.end(); ++it ) {
1065 pair_obj = &it->second;
1066
1067 if ( !pair_obj->initialized ) {
1068 continue;
1069 }
1070
1071 if ( pair_obj->a->type == OBJ_WEAPON && pair_obj->signature_a == pair_obj->a->signature ) {
1072 crw_check_weapon(pair_obj->a->instance, pair_obj->next_check_time);
1073
1074 if ( crw_status[pair_obj->a->instance] == CRW_CAN_DELETE ) {
1075 pair_obj->initialized = false;
1076 }
1077 }
1078
1079 if ( pair_obj->b->type == OBJ_WEAPON && pair_obj->signature_b == pair_obj->b->signature ) {
1080 crw_check_weapon(pair_obj->b->instance, pair_obj->next_check_time);
1081
1082 if ( crw_status[pair_obj->b->instance] == CRW_CAN_DELETE ) {
1083 pair_obj->initialized = false;
1084 }
1085 }
1086 }
1087 }
1088
1089 // for each weapon which could be removed, delete the object
1090 num_deleted = 0;
1091 for ( i = 0; i < MAX_WEAPONS; i++ ) {
1092 if ( crw_status[i] == CRW_CAN_DELETE ) {
1093 Assert( Weapons[i].objnum != -1 );
1094 obj_delete( Weapons[i].objnum );
1095 num_deleted++;
1096 }
1097 }
1098
1099 if ( num_deleted )
1100 return num_deleted;
1101
1102 // if we didn't remove any weapons, try to the N oldest weapons. first checking for pairs, then
1103 // checking for oldest weapons in general. We will go through the loop a max of 2 times. first time
1104 // through, we check oldest weapons with pairs, next time through, for oldest weapons.
1105 loop_count = 0;
1106 do {
1107 for ( j = 0; j < CRW_MAX_TO_DELETE; j++ ) {
1108 oldest_time = 1000.0f;
1109 oldest_index = -1;
1110 for (i = 0; i < MAX_WEAPONS; i++ ) {
1111 if ( Weapons[i].objnum == -1 ) // shouldn't happen, but this is the safe thing to do.
1112 continue;
1113 if ( ((loop_count || crw_status[i] == CRW_NO_PAIR)) && (Weapons[i].lifeleft < oldest_time) ) {
1114 oldest_time = Weapons[i].lifeleft;
1115 oldest_index = i;
1116 }
1117 }
1118 if ( oldest_index != -1 ) {
1119 obj_delete(Weapons[oldest_index].objnum);
1120 num_deleted++;
1121 }
1122 }
1123
1124 // if we deleted some weapons, then we can break
1125 if ( num_deleted )
1126 break;
1127
1128 loop_count++;
1129 } while ( loop_count < 2);
1130
1131 return num_deleted;
1132
1133 }
1134
set_hit_struct_info(collision_info_struct * hit,mc_info * mc,int submodel_rot_hit)1135 void set_hit_struct_info(collision_info_struct *hit, mc_info *mc, int submodel_rot_hit)
1136 {
1137 hit->edge_hit = mc->edge_hit;
1138 hit->hit_pos = mc->hit_point_world;
1139 hit->hit_time = mc->hit_dist;
1140 hit->submodel_num = mc->hit_submodel;
1141
1142 hit->submodel_rot_hit = submodel_rot_hit;
1143 }
1144
1145 //Previously, this was done with
1146 //memset(&ship_ship_hit_info, -1, sizeof(collision_info_struct));
1147 //All those -1s are to replicate that logic
init_collision_info_struct(collision_info_struct * cis)1148 void init_collision_info_struct(collision_info_struct *cis)
1149 {
1150 memset(cis, -1, sizeof(collision_info_struct));
1151 cis->is_landing = false;
1152 }
1153
obj_add_collider(int obj_index)1154 void obj_add_collider(int obj_index)
1155 {
1156 object *objp = &Objects[obj_index];
1157
1158 #ifdef OBJECT_CHECK
1159 CheckObjects[obj_index].type = objp->type;
1160 CheckObjects[obj_index].signature = objp->signature;
1161 CheckObjects[obj_index].flags = objp->flags & ~(OF_NOT_IN_COLL);
1162 CheckObjects[obj_index].parent_sig = objp->parent_sig;
1163 CheckObjects[obj_index].parent_type = objp->parent_type;
1164 #endif
1165
1166 if(!(objp->flags & OF_NOT_IN_COLL)){
1167 return;
1168 }
1169
1170 Collision_sort_list.push_back(obj_index);
1171
1172 objp->flags &= ~OF_NOT_IN_COLL;
1173 }
1174
obj_remove_collider(int obj_index)1175 void obj_remove_collider(int obj_index)
1176 {
1177 #ifdef OBJECT_CHECK
1178 CheckObjects[obj_index].flags |= OF_NOT_IN_COLL;
1179 #endif
1180
1181 size_t i;
1182
1183 for ( i = 0; i < Collision_sort_list.size(); ++i ) {
1184 if ( Collision_sort_list[i] == obj_index ) {
1185 Collision_sort_list[i] = Collision_sort_list.back();
1186 Collision_sort_list.pop_back();
1187 break;
1188 }
1189 }
1190
1191 Objects[obj_index].flags |= OF_NOT_IN_COLL;
1192 }
1193
obj_reset_colliders()1194 void obj_reset_colliders()
1195 {
1196 Collision_sort_list.clear();
1197 Collision_cached_pairs.clear();
1198 }
1199
obj_collide_retime_cached_pairs(int checkdly)1200 void obj_collide_retime_cached_pairs(int checkdly)
1201 {
1202 SCP_hash_map<uint, collider_pair>::iterator it;
1203
1204 for ( it = Collision_cached_pairs.begin(); it != Collision_cached_pairs.end(); ++it ) {
1205 it->second.next_check_time = timestamp(checkdly);
1206 }
1207 }
1208
obj_sort_and_collide()1209 void obj_sort_and_collide()
1210 {
1211 if (Cmdline_dis_collisions)
1212 return;
1213
1214 if ( !(Game_detail_flags & DETAIL_FLAG_COLLISION) )
1215 return;
1216
1217 SCP_vector<int> sort_list_y;
1218 SCP_vector<int> sort_list_z;
1219
1220 sort_list_y.clear();
1221 obj_quicksort_colliders(&Collision_sort_list, 0, Collision_sort_list.size() - 1, 0);
1222 obj_find_overlap_colliders(&sort_list_y, &Collision_sort_list, 0, false);
1223
1224 sort_list_z.clear();
1225 obj_quicksort_colliders(&sort_list_y, 0, sort_list_y.size() - 1, 1);
1226 obj_find_overlap_colliders(&sort_list_z, &sort_list_y, 1, false);
1227
1228 sort_list_y.clear();
1229 obj_quicksort_colliders(&sort_list_z, 0, sort_list_z.size() - 1, 2);
1230 obj_find_overlap_colliders(&sort_list_y, &sort_list_z, 2, true);
1231 }
1232
obj_find_overlap_colliders(SCP_vector<int> * overlap_list_out,SCP_vector<int> * list,int axis,bool collide)1233 void obj_find_overlap_colliders(SCP_vector<int> *overlap_list_out, SCP_vector<int> *list, int axis, bool collide)
1234 {
1235 size_t i, j;
1236 bool overlapped;
1237 bool first_not_added = true;
1238 SCP_vector<int> overlappers;
1239
1240 float min;
1241 float max;
1242 float overlap_min;
1243 float overlap_max;
1244
1245 overlappers.clear();
1246
1247 for ( i = 0; i < (*list).size(); ++i ) {
1248 overlapped = false;
1249
1250 min = obj_get_collider_endpoint((*list)[i], axis, true);
1251 max = obj_get_collider_endpoint((*list)[i], axis, false);
1252
1253 for ( j = 0; j < overlappers.size(); ) {
1254 overlap_min = obj_get_collider_endpoint(overlappers[j], axis, true);
1255 overlap_max = obj_get_collider_endpoint(overlappers[j], axis, false);
1256 if ( min <= overlap_max ) {
1257 overlapped = true;
1258
1259 if ( overlappers.size() == 1 && first_not_added ) {
1260 first_not_added = false;
1261 overlap_list_out->push_back(overlappers[j]);
1262 }
1263
1264 if ( collide ) {
1265 obj_collide_pair(&Objects[(*list)[i]], &Objects[overlappers[j]]);
1266 }
1267 } else {
1268 overlappers[j] = overlappers.back();
1269 overlappers.pop_back();
1270 continue;
1271 }
1272
1273 ++j;
1274 }
1275
1276 if ( overlappers.size() == 0 ) {
1277 first_not_added = true;
1278 }
1279
1280 if ( overlapped ) {
1281 overlap_list_out->push_back((*list)[i]);
1282 }
1283
1284 overlappers.push_back((*list)[i]);
1285 }
1286
1287 overlapped = true;
1288 }
1289
obj_get_collider_endpoint(int obj_num,int axis,bool min)1290 float obj_get_collider_endpoint(int obj_num, int axis, bool min)
1291 {
1292 if ( Objects[obj_num].type == OBJ_BEAM ) {
1293 beam *b = &Beams[Objects[obj_num].instance];
1294
1295 // use the last start and last shot as endpoints
1296 float min_end, max_end;
1297 if ( b->last_start.a1d[axis] > b->last_shot.a1d[axis] ) {
1298 min_end = b->last_shot.a1d[axis];
1299 max_end = b->last_start.a1d[axis];
1300 } else {
1301 min_end = b->last_start.a1d[axis];
1302 max_end = b->last_shot.a1d[axis];
1303 }
1304
1305 if ( min ) {
1306 return min_end;
1307 } else {
1308 return max_end;
1309 }
1310 } else if ( Objects[obj_num].type == OBJ_WEAPON ) {
1311 float min_end, max_end;
1312
1313 if ( Objects[obj_num].pos.a1d[axis] > Objects[obj_num].last_pos.a1d[axis] ) {
1314 min_end = Objects[obj_num].last_pos.a1d[axis];
1315 max_end = Objects[obj_num].pos.a1d[axis];
1316 } else {
1317 min_end = Objects[obj_num].pos.a1d[axis];
1318 max_end = Objects[obj_num].last_pos.a1d[axis];
1319 }
1320
1321 if ( min ) {
1322 return min_end - Objects[obj_num].radius;
1323 } else {
1324 return max_end + Objects[obj_num].radius;
1325 }
1326 } else {
1327 vec3d *pos = &Objects[obj_num].pos;
1328
1329 if ( min ) {
1330 return pos->a1d[axis] - Objects[obj_num].radius;
1331 } else {
1332 return pos->a1d[axis] + Objects[obj_num].radius;
1333 }
1334 }
1335 }
1336
obj_quicksort_colliders(SCP_vector<int> * list,int left,int right,int axis)1337 void obj_quicksort_colliders(SCP_vector<int> *list, int left, int right, int axis)
1338 {
1339 Assert( axis >= 0 );
1340 Assert( axis <= 2 );
1341
1342 if ( right > left ) {
1343 int pivot_index = left + (right - left) / 2;
1344
1345 float pivot_value = obj_get_collider_endpoint((*list)[pivot_index], axis, true);
1346
1347 // swap!
1348 int temp = (*list)[pivot_index];
1349 (*list)[pivot_index] = (*list)[right];
1350 (*list)[right] = temp;
1351
1352 int store_index = left;
1353
1354 int i;
1355 for ( i = left; i < right; ++i ) {
1356 if ( obj_get_collider_endpoint((*list)[i], axis, true) <= pivot_value ) {
1357 temp = (*list)[i];
1358 (*list)[i] = (*list)[store_index];
1359 (*list)[store_index] = temp;
1360 store_index++;
1361 }
1362 }
1363
1364 temp = (*list)[right];
1365 (*list)[right] = (*list)[store_index];
1366 (*list)[store_index] = temp;
1367
1368 obj_quicksort_colliders(list, left, store_index - 1, axis);
1369 obj_quicksort_colliders(list, store_index + 1, right, axis);
1370 }
1371 }
1372
obj_collide_pair(object * A,object * B)1373 void obj_collide_pair(object *A, object *B)
1374 {
1375 uint ctype;
1376 int (*check_collision)( obj_pair *pair );
1377 int swapped = 0;
1378
1379 check_collision = NULL;
1380
1381 if ( A==B ) return; // Don't check collisions with yourself
1382
1383 if ( !(A->flags&OF_COLLIDES) ) return; // This object doesn't collide with anything
1384 if ( !(B->flags&OF_COLLIDES) ) return; // This object doesn't collide with anything
1385
1386 // Make sure you're not checking a parent with it's kid or vicy-versy
1387 // if ( A->parent_sig == B->signature && !(A->type == OBJ_SHIP && B->type == OBJ_DEBRIS) ) return;
1388 // if ( B->parent_sig == A->signature && !(A->type == OBJ_DEBRIS && B->type == OBJ_SHIP) ) return;
1389 if ( reject_obj_pair_on_parent(A,B) ) {
1390 return;
1391 }
1392
1393 Assert( A->type < 127 );
1394 Assert( B->type < 127 );
1395
1396 ctype = COLLISION_OF(A->type,B->type);
1397 switch( ctype ) {
1398 case COLLISION_OF(OBJ_WEAPON,OBJ_SHIP):
1399 swapped = 1;
1400 check_collision = collide_ship_weapon;
1401 break;
1402 case COLLISION_OF(OBJ_SHIP, OBJ_WEAPON):
1403 check_collision = collide_ship_weapon;
1404 break;
1405 case COLLISION_OF(OBJ_DEBRIS, OBJ_WEAPON):
1406 check_collision = collide_debris_weapon;
1407 break;
1408 case COLLISION_OF(OBJ_WEAPON, OBJ_DEBRIS):
1409 swapped = 1;
1410 check_collision = collide_debris_weapon;
1411 break;
1412 case COLLISION_OF(OBJ_DEBRIS, OBJ_SHIP):
1413 check_collision = collide_debris_ship;
1414 break;
1415 case COLLISION_OF(OBJ_SHIP, OBJ_DEBRIS):
1416 check_collision = collide_debris_ship;
1417 swapped = 1;
1418 break;
1419 case COLLISION_OF(OBJ_ASTEROID, OBJ_WEAPON):
1420 // Only check collision's with player weapons
1421 // if ( Objects[B->parent].flags & OF_PLAYER_SHIP ) {
1422 check_collision = collide_asteroid_weapon;
1423 // }
1424 break;
1425 case COLLISION_OF(OBJ_WEAPON, OBJ_ASTEROID):
1426 swapped = 1;
1427 // Only check collision's with player weapons
1428 // if ( Objects[A->parent].flags & OF_PLAYER_SHIP ) {
1429 check_collision = collide_asteroid_weapon;
1430 // }
1431 break;
1432 case COLLISION_OF(OBJ_ASTEROID, OBJ_SHIP):
1433 // Only check collisions with player ships
1434 // if ( B->flags & OF_PLAYER_SHIP ) {
1435 check_collision = collide_asteroid_ship;
1436 // }
1437 break;
1438 case COLLISION_OF(OBJ_SHIP, OBJ_ASTEROID):
1439 // Only check collisions with player ships
1440 // if ( A->flags & OF_PLAYER_SHIP ) {
1441 check_collision = collide_asteroid_ship;
1442 // }
1443 swapped = 1;
1444 break;
1445 case COLLISION_OF(OBJ_SHIP,OBJ_SHIP):
1446 check_collision = collide_ship_ship;
1447 break;
1448
1449 case COLLISION_OF(OBJ_SHIP, OBJ_BEAM):
1450 if(beam_collide_early_out(B, A)){
1451 return;
1452 }
1453 swapped = 1;
1454 check_collision = beam_collide_ship;
1455 break;
1456
1457 case COLLISION_OF(OBJ_BEAM, OBJ_SHIP):
1458 if(beam_collide_early_out(A, B)){
1459 return;
1460 }
1461 check_collision = beam_collide_ship;
1462 break;
1463
1464 case COLLISION_OF(OBJ_ASTEROID, OBJ_BEAM):
1465 if(beam_collide_early_out(B, A)) {
1466 return;
1467 }
1468 swapped = 1;
1469 check_collision = beam_collide_asteroid;
1470 break;
1471
1472 case COLLISION_OF(OBJ_BEAM, OBJ_ASTEROID):
1473 if(beam_collide_early_out(A, B)){
1474 return;
1475 }
1476 check_collision = beam_collide_asteroid;
1477 break;
1478 case COLLISION_OF(OBJ_DEBRIS, OBJ_BEAM):
1479 if(beam_collide_early_out(B, A)) {
1480 return;
1481 }
1482 swapped = 1;
1483 check_collision = beam_collide_debris;
1484 break;
1485 case COLLISION_OF(OBJ_BEAM, OBJ_DEBRIS):
1486 if(beam_collide_early_out(A, B)){
1487 return;
1488 }
1489 check_collision = beam_collide_debris;
1490 break;
1491 case COLLISION_OF(OBJ_WEAPON, OBJ_BEAM):
1492 if(beam_collide_early_out(B, A)) {
1493 return;
1494 }
1495 swapped = 1;
1496 check_collision = beam_collide_missile;
1497 break;
1498
1499 case COLLISION_OF(OBJ_BEAM, OBJ_WEAPON):
1500 if(beam_collide_early_out(A, B)){
1501 return;
1502 }
1503 check_collision = beam_collide_missile;
1504 break;
1505
1506 case COLLISION_OF(OBJ_WEAPON, OBJ_WEAPON): {
1507 weapon_info *awip, *bwip;
1508 awip = &Weapon_info[Weapons[A->instance].weapon_info_index];
1509 bwip = &Weapon_info[Weapons[B->instance].weapon_info_index];
1510
1511 if ((awip->weapon_hitpoints > 0) || (bwip->weapon_hitpoints > 0)) {
1512 if (bwip->weapon_hitpoints == 0) {
1513 check_collision = collide_weapon_weapon;
1514 swapped=1;
1515 } else {
1516 check_collision = collide_weapon_weapon;
1517 }
1518 }
1519
1520 break;
1521 }
1522
1523 default:
1524 return;
1525 }
1526
1527 if ( !check_collision ) return;
1528
1529 // Swap them if needed
1530 if ( swapped ) {
1531 object *tmp = A;
1532 A = B;
1533 B = tmp;
1534 }
1535
1536 collider_pair *collision_info = NULL;
1537 bool valid = false;
1538 uint key = (OBJ_INDEX(A) << 12) + OBJ_INDEX(B);
1539
1540 collision_info = &Collision_cached_pairs[key];
1541
1542 if ( collision_info->initialized ) {
1543 // make sure we're referring to the correct objects in case the original pair was deleted
1544 if ( collision_info->signature_a == collision_info->a->signature &&
1545 collision_info->signature_b == collision_info->b->signature ) {
1546 valid = true;
1547 } else {
1548 collision_info->a = A;
1549 collision_info->b = B;
1550 collision_info->signature_a = A->signature;
1551 collision_info->signature_b = B->signature;
1552 collision_info->next_check_time = timestamp(0);
1553 }
1554 } else {
1555 collision_info->a = A;
1556 collision_info->b = B;
1557 collision_info->signature_a = A->signature;
1558 collision_info->signature_b = B->signature;
1559 collision_info->initialized = true;
1560 collision_info->next_check_time = timestamp(0);
1561 }
1562
1563 if ( valid && A->type != OBJ_BEAM ) {
1564 // if this signature is valid, make the necessary checks to see if we need to collide check
1565 if ( collision_info->next_check_time == -1 ) {
1566 return;
1567 } else {
1568 if ( !timestamp_elapsed(collision_info->next_check_time) ) {
1569 return;
1570 }
1571 }
1572 } else {
1573 //if ( A->type == OBJ_BEAM ) {
1574 //if(beam_collide_early_out(A, B)){
1575 //collision_info->next_check_time = -1;
1576 //return;
1577 //}
1578 //}
1579
1580 // only check debris:weapon collisions for player
1581 if (check_collision == collide_debris_weapon) {
1582 // weapon is B
1583 if ( !(Weapon_info[Weapons[B->instance].weapon_info_index].wi_flags & WIF_TURNS) ) {
1584 // check for dumbfire weapon
1585 // check if debris is behind laser
1586 float vdot;
1587 if (Weapon_info[Weapons[B->instance].weapon_info_index].subtype == WP_LASER) {
1588 vec3d velocity_rel_weapon;
1589 vm_vec_sub(&velocity_rel_weapon, &B->phys_info.vel, &A->phys_info.vel);
1590 vdot = -vm_vec_dot(&velocity_rel_weapon, &B->orient.vec.fvec);
1591 } else {
1592 vdot = vm_vec_dot( &A->phys_info.vel, &B->phys_info.vel);
1593 }
1594 if ( vdot <= 0.0f ) {
1595 // They're heading in opposite directions...
1596 // check their positions
1597 vec3d weapon2other;
1598 vm_vec_sub( &weapon2other, &A->pos, &B->pos );
1599 float pdot = vm_vec_dot( &B->orient.vec.fvec, &weapon2other );
1600 if ( pdot <= -A->radius ) {
1601 // The other object is behind the weapon by more than
1602 // its radius, so it will never hit...
1603 collision_info->next_check_time = -1;
1604 return;
1605 }
1606 }
1607
1608 // check dist vs. dist moved during weapon lifetime
1609 vec3d delta_v;
1610 vm_vec_sub(&delta_v, &B->phys_info.vel, &A->phys_info.vel);
1611 if (vm_vec_dist_squared(&A->pos, &B->pos) > (vm_vec_mag_squared(&delta_v)*Weapons[B->instance].lifeleft*Weapons[B->instance].lifeleft)) {
1612 collision_info->next_check_time = -1;
1613 return;
1614 }
1615
1616 // for nonplayer ships, only create collision pair if close enough
1617 if ( (B->parent >= 0) && !(Objects[B->parent].flags & OF_PLAYER_SHIP) && (vm_vec_dist(&B->pos, &A->pos) < (4.0f*A->radius + 200.0f)) ) {
1618 collision_info->next_check_time = -1;
1619 return;
1620 }
1621 }
1622 }
1623
1624 // don't check same team laser:ship collisions on small ships if not player
1625 if (check_collision == collide_ship_weapon) {
1626 // weapon is B
1627 if ( (B->parent >= 0)
1628 && !(Objects[B->parent].flags & OF_PLAYER_SHIP)
1629 && (Ships[Objects[B->parent].instance].team == Ships[A->instance].team)
1630 && (Ship_info[Ships[A->instance].ship_info_index].flags & SIF_SMALL_SHIP)
1631 && (Weapon_info[Weapons[B->instance].weapon_info_index].subtype == WP_LASER) ) {
1632 collision_info->next_check_time = -1;
1633 return;
1634 }
1635 }
1636 }
1637
1638 obj_pair new_pair;
1639
1640 new_pair.a = A;
1641 new_pair.b = B;
1642 new_pair.check_collision = check_collision;
1643 new_pair.next_check_time = collision_info->next_check_time;
1644
1645 if ( check_collision(&new_pair) ) {
1646 // don't have to check ever again
1647 collision_info->next_check_time = -1;
1648 } else {
1649 collision_info->next_check_time = new_pair.next_check_time;
1650 }
1651 }
1652