-
Notifications
You must be signed in to change notification settings - Fork 11
/
index.html
735 lines (680 loc) · 36 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
<!DOCTYPE html>
<html lang="en">
<head>
<title>Intersection Tests in 2D</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<link
rel="stylesheet"
media="all"
href="dpcs/public/stylesheets/normalize.css"
/>
<link rel="stylesheet" media="all" href="docs/docco.css" />
<link rel="stylesheet" media="all" href="docs/intersect.css" />
</head>
<body>
<div class="container">
<div class="page">
<div class="header">
<h1 id="intersection-tests-in-2d">Intersection Tests in 2D</h1>
<p>
This library is a collection of common 2D collision detection tests.
Hopefully this saves you from the pain of hunting them down
yourself, or trying to rip them out of physics libraries.
</p>
<p>
If you’re looking for further reading, you are hurting yourself if
you don’t buy
<a href="http://realtimecollisiondetection.net/"
>Real-Time Collision Detection</a
>. It is easily the best purchase you could make if you are learning
about collision detection. There is also an excellent
<a href="http://www.realtimerendering.com/intersections.html"
>list of different algorithms here</a
>.
</p>
<p>
The code is written in TypeScript, but it’s simple and should be
easily portable to your language of choice. If you just want to see
the code, take a look at
<a
href="https://github.com/noonat/intersect/blob/master/src/intersect.js"
>the TypeScript file</a
>. The
<a
href="https://github.com/noonat/intersect/blob/master/src/examples.js"
>animated examples</a
>
on this page are also written in TypeScript, using the library.
</p>
<ol>
<li><a href="#helpers">Helpers</a></li>
<li>
<a href="#types-of-tests">Types of Tests</a>
<ol>
<li><a href="#intersection-tests">Intersection Tests</a></li>
<li><a href="#sweep-tests">Sweep Tests</a></li>
</ol>
</li>
<li>
<a href="#axis-aligned-bounding-boxes"
>Axis-Aligned Bounding Boxes</a
>
<ol>
<li><a href="#aabb-vs-point">AABB vs Point</a></li>
<li><a href="#aabb-vs-segment">AABB vs Segment</a></li>
<li><a href="#aabb-vs-aabb">AABB vs AABB</a></li>
<li><a href="#aabb-vs-swept-aabb">AABB vs Swept AABB</a></li>
</ol>
</li>
<li>
<a href="#sweeping-an-aabb-through-multiple-objects"
>Sweeping an AABB Through Multiple Objects</a
>
</li>
</ol>
<h2 id="helpers">Helpers</h2>
<p>Let’s define a couple helpers that we’ll use through the code.</p>
<div class="highlight">
<pre><span class="hljs-keyword">export</span> <span class="hljs-keyword">const</span> EPSILON: <span class="hljs-built_in">number</span> = <span class="hljs-number">1e-8</span>;
<span class="hljs-keyword">export</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">abs</span>(<span class="hljs-params">value: <span class="hljs-built_in">number</span></span>): <span class="hljs-title">number</span> </span>{
<span class="hljs-keyword">return</span> value < <span class="hljs-number">0</span> ? -value : value;
}
<span class="hljs-keyword">export</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">clamp</span>(<span class="hljs-params">value: <span class="hljs-built_in">number</span>, min: <span class="hljs-built_in">number</span>, max: <span class="hljs-built_in">number</span></span>): <span class="hljs-title">number</span> </span>{
<span class="hljs-keyword">if</span> (value < min) {
<span class="hljs-keyword">return</span> min;
} <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (value > max) {
<span class="hljs-keyword">return</span> max;
} <span class="hljs-keyword">else</span> {
<span class="hljs-keyword">return</span> value;
}
}
<span class="hljs-keyword">export</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">sign</span>(<span class="hljs-params">value: <span class="hljs-built_in">number</span></span>): <span class="hljs-title">number</span> </span>{
<span class="hljs-keyword">return</span> value < <span class="hljs-number">0</span> ? <span class="hljs-number">-1</span> : <span class="hljs-number">1</span>;
}</pre>
</div>
</div>
<p>
We’ll also need a 2D point. We could just use a literal
<code>{x: 0, y: 0}</code> object, but you have to normalize and copy
things quite a bit when doing collision detection, so it makes things
a bit more readable to formalize it as a class.
</p>
<div class="highlight">
<pre><span class="hljs-keyword">export</span> <span class="hljs-keyword">class</span> Point {
<span class="hljs-keyword">public</span> x: <span class="hljs-built_in">number</span>;
<span class="hljs-keyword">public</span> y: <span class="hljs-built_in">number</span>;
<span class="hljs-keyword">constructor</span>(<span class="hljs-params">x: <span class="hljs-built_in">number</span> = 0, y: <span class="hljs-built_in">number</span> = 0</span>) {
<span class="hljs-keyword">this</span>.x = x;
<span class="hljs-keyword">this</span>.y = y;
}
<span class="hljs-keyword">public</span> clone(): Point {
<span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Point(<span class="hljs-keyword">this</span>.x, <span class="hljs-keyword">this</span>.y);
}
<span class="hljs-keyword">public</span> normalize(): <span class="hljs-built_in">number</span> {
<span class="hljs-keyword">let</span> length = <span class="hljs-keyword">this</span>.x * <span class="hljs-keyword">this</span>.x + <span class="hljs-keyword">this</span>.y * <span class="hljs-keyword">this</span>.y;
<span class="hljs-keyword">if</span> (length > <span class="hljs-number">0</span>) {
length = <span class="hljs-built_in">Math</span>.sqrt(length);
<span class="hljs-keyword">const</span> inverseLength = <span class="hljs-number">1.0</span> / length;
<span class="hljs-keyword">this</span>.x *= inverseLength;
<span class="hljs-keyword">this</span>.y *= inverseLength;
} <span class="hljs-keyword">else</span> {
<span class="hljs-keyword">this</span>.x = <span class="hljs-number">1</span>;
<span class="hljs-keyword">this</span>.y = <span class="hljs-number">0</span>;
}
<span class="hljs-keyword">return</span> length;
}
}</pre>
</div>
<h2 id="types-of-tests">Types of Tests</h2>
<p>
Collision and physics libraries generally assign things to two
categories: static objects at rest, and dynamic moving objects. Full
physics libraries often solve things in more complicated (and more
efficient) ways, and optimize for cases of many objects moving at once
and colliding against one another.
</p>
<p>
But, for most simple 2D games, it’s usually enough to do a collision
test between the object you’re moving now (while moving it in the
code), and the rest of the world. The world for this type of game
rarely contains so many objects that this hurts your performance, and
it makes the problem far easier to solve. It also makes it easier to
fine tune the physics system, which is often very important for
platformers.
</p>
<p>
As such, the functions in this code are all written for
<em>static vs static</em> or <em>moving vs static</em> object tests,
to keep things simple.
</p>
<h3 id="intersection-tests">Intersection Tests</h3>
<figure class="right">
<img src="./docs/svg/box-intersection-test.svg" class="small" />
<figcaption>
A intersects with B and needs to be pushed out
</figcaption>
</figure>
<p>
Intersection tests are a <em>static vs static</em> test. They check
whether two static objects are overlapping. They have a boolean result
(colliding or not), with a vector which tells you how you could move
the objects so that they’re no longer overlapping.
</p>
<p>
Intersection tests will return a Hit object when a collision occurs:
</p>
<div class="highlight">
<pre><span class="hljs-keyword">type</span> Collider = AABB;
<span class="hljs-keyword">export</span> <span class="hljs-keyword">class</span> Hit {
<span class="hljs-keyword">public</span> collider: Collider;
<span class="hljs-keyword">public</span> pos: Point;
<span class="hljs-keyword">public</span> delta: Point;
<span class="hljs-keyword">public</span> normal: Point;
<span class="hljs-keyword">public</span> time: <span class="hljs-built_in">number</span>;
<span class="hljs-keyword">constructor</span>(<span class="hljs-params">collider: Collider</span>) {
<span class="hljs-keyword">this</span>.collider = collider;
<span class="hljs-keyword">this</span>.pos = <span class="hljs-keyword">new</span> Point();
<span class="hljs-keyword">this</span>.delta = <span class="hljs-keyword">new</span> Point();
<span class="hljs-keyword">this</span>.normal = <span class="hljs-keyword">new</span> Point();
<span class="hljs-keyword">this</span>.time = <span class="hljs-number">0</span>;
}
}</pre>
</div>
<ul>
<li>
<strong>hit.pos</strong> is the point of contact between the two
objects (or an estimation of it, in some sweep tests).
</li>
<li>
<strong>hit.normal</strong> is the surface normal at the point of
contact.
</li>
<li>
<strong>hit.delta</strong> is the overlap between the two objects,
and is a vector that can be added to the colliding object’s position
to move it back to a non-colliding state.
</li>
<li>
<strong>hit.time</strong> is only defined for segment and sweep
intersections, and is a fraction from 0 to 1 indicating how far
along the line the collision occurred. (This is the \(t\) value for
the line equation \(L(t) = A + t(B - A)\))
</li>
</ul>
<h3 id="sweep-tests">Sweep Tests</h3>
<p>
Sweep tests are a <em>moving vs static</em> test. They take two
objects, sweep one along a line of movement, and determine when it
first collides with the other object along that path of movement.
</p>
<figure class="right">
<img src="./docs/svg/box-bad-intersection-test.svg" class="small" />
<figcaption>
A intersects both B and C, and is incorrectly pushed <em>into</em> a
bad state
</figcaption>
</figure>
<p>
Normal intersection tests are helpful for static objects, but they
aren’t the best choice to collide a moving object. If you are trying
to collide an object A against two objects, B and C, you can easily
get into an ambiguous situation where the collision isn’t as easy to
resolve.
</p>
<p>
Our intersection tests can only determine what the best way to resolve
a collision with an object is for that one object, independent of any
other objects you want to collide with. This means that correcting for
a collision with object B moves you into a state where are colliding
with object C, and the same thing happens with object C.
</p>
<p>
Instead, you can use a sweep test to take the path of movement into
account, and stop objects from ever moving into other objects.
</p>
<p>Sweep tests return a <code>Sweep</code> object:</p>
<div class="highlight">
<pre><span class="hljs-keyword">export</span> <span class="hljs-keyword">class</span> Sweep {
<span class="hljs-keyword">public</span> hit: Hit | <span class="hljs-literal">null</span>;
<span class="hljs-keyword">public</span> pos: Point;
<span class="hljs-keyword">public</span> time: <span class="hljs-built_in">number</span>;
<span class="hljs-keyword">constructor</span>(<span class="hljs-params"></span>) {
<span class="hljs-keyword">this</span>.hit = <span class="hljs-literal">null</span>;
<span class="hljs-keyword">this</span>.pos = <span class="hljs-keyword">new</span> Point();
<span class="hljs-keyword">this</span>.time = <span class="hljs-number">1</span>;
}
}</pre>
</div>
<ul>
<li>
<strong>sweep.hit</strong> is a Hit object if there was a collision,
or null if not.
</li>
<li>
<strong>sweep.pos</strong> is the furthest point the object reached
along the swept path before it hit something.
</li>
<li>
<strong>sweep.time</strong> is a copy of
<code>sweep.hit.time</code>, offset by epsilon, or 1 if the object
didn’t hit anything during the sweep.
</li>
</ul>
<h2 id="axis-aligned-bounding-boxes">Axis-Aligned Bounding Boxes</h2>
<p>
Axis-aligned bounding boxes (AABBs) are bounding rectangles that do
not rotate. This means that their edges are always aligned with the
main X and Y axes, which makes collision detection much simpler. These
examples specify an AABB via a center point and box’s half size for
each axis (that is, the box’s “radius” on each axis).
</p>
<div class="highlight">
<pre><span class="hljs-keyword">export</span> <span class="hljs-keyword">class</span> AABB {
<span class="hljs-keyword">public</span> pos: Point;
<span class="hljs-keyword">public</span> half: Point;
<span class="hljs-keyword">constructor</span>(<span class="hljs-params">pos: Point, half: Point</span>) {
<span class="hljs-keyword">this</span>.pos = pos;
<span class="hljs-keyword">this</span>.half = half;
}</pre>
</div>
<p>
The library has four axis-aligned bounding box (AABB) tests: AABB vs
point, AABB vs segment (raycast), AABB vs AABB, and AABB vs swept
AABB.
</p>
<h3 id="aabb-vs-point">AABB vs Point</h3>
<p>
This test is very simple, but I’ve included it for completeness. If a
point is behind all of the edges of the box, it’s colliding. The
function returns a Hit object, or null if the two do not collide.
<code>hit.pos</code> and <code>hit.delta</code> will be set to the
nearest edge of the box.
</p>
<p>
This code first finds the overlap on the X and Y axis. If the overlap
is less than zero for either, a collision is not possible. Otherwise,
we find the axis with the smallest overlap and use that to create an
intersection point on the edge of the box.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">public</span> intersectPoint(point: Point): Hit | <span class="hljs-literal">null</span> {
<span class="hljs-keyword">const</span> dx = point.x - <span class="hljs-keyword">this</span>.pos.x;
<span class="hljs-keyword">const</span> px = <span class="hljs-keyword">this</span>.half.x - abs(dx);
<span class="hljs-keyword">if</span> (px <= <span class="hljs-number">0</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>;
}
<span class="hljs-keyword">const</span> dy = point.y - <span class="hljs-keyword">this</span>.pos.y;
<span class="hljs-keyword">const</span> py = <span class="hljs-keyword">this</span>.half.y - abs(dy);
<span class="hljs-keyword">if</span> (py <= <span class="hljs-number">0</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>;
}
<span class="hljs-keyword">const</span> hit = <span class="hljs-keyword">new</span> Hit(<span class="hljs-keyword">this</span>);
<span class="hljs-keyword">if</span> (px < py) {
<span class="hljs-keyword">const</span> sx = sign(dx);
hit.delta.x = px * sx;
hit.normal.x = sx;
hit.pos.x = <span class="hljs-keyword">this</span>.pos.x + (<span class="hljs-keyword">this</span>.half.x * sx);
hit.pos.y = point.y;
} <span class="hljs-keyword">else</span> {
<span class="hljs-keyword">const</span> sy = sign(dy);
hit.delta.y = py * sy;
hit.normal.y = sy;
hit.pos.x = point.x;
hit.pos.y = <span class="hljs-keyword">this</span>.pos.y + (<span class="hljs-keyword">this</span>.half.y * sy);
}
<span class="hljs-keyword">return</span> hit;
}</pre>
</div>
<h3 id="aabb-vs-segment">AABB vs Segment</h3>
<p>
Games use segment intersection tests all the time, for everything from
line of sight to checking whether a bullet hit a monster. This is the
most complicated of the four AABB tests, and is commonly known as a
slab test. It finds the time of the line’s intersection with the near
and far edges of each axis of the AABB. If they overlap, the segment
is intersecting.
</p>
<div class="figure-row right">
<figure>
<img src="./docs/svg/box-near-far-x.svg" class="small" />
<figcaption>Near x is greater than far y</figcaption>
</figure>
<figure>
<img src="./docs/svg/box-near-far-y.svg" class="small" />
<figcaption>Near x is greater than far y</figcaption>
</figure>
</div>
<p>
What are the near and far edges? Well, in our examples to the right,
the direction of the segment is from the top left to the bottom right.
This means that the near edges of the box are the top and left edges,
and the far edges of the box are the bottom and right edges.
</p>
<p>
Note that the intersection points might not actually be on the box or
the segment. They will be at the intersection of the infinite lines of
the box’s edges and the infinite line of the segment.
</p>
<p>
This is a weird concept, so don’t feel bad if it takes a while for it
to sink in. For further reading, I recommend
<a
href="http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm"
>IRT p.65,104</a
>
and
<a
href="https://web.archive.org/web/20130420103121/http://www.cs.utah.edu/~awilliam/box/"
>WilliamsEtAl05</a
>.
</p>
<p>
The function calculates the collision times along the line for each
edge of the box. It returns a Hit object (with an extra
<code>time</code> property), or null if the two do not overlap.
<code>paddingX</code> and <code>paddingY</code> will be added to the
radius of the bounding box, if specified.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">public</span> intersectSegment(pos: Point, delta: Point, paddingX: <span class="hljs-built_in">number</span> = <span class="hljs-number">0</span>,
paddingY: <span class="hljs-built_in">number</span> = <span class="hljs-number">0</span>): Hit | <span class="hljs-literal">null</span> {</pre>
</div>
<p>
You might notice we haven’t defined a segment argument. A segment from
point \(A\) to point \(B\) can be expressed with the equation \(S(t) =
A + t(B - A)\), for \(0 <= t <= 1\). In this equation, \(t\) is
the time along the line, or percentage distance from \(A\) to \(B\).
Instead of formalizing the concept of a segment, we use this equation
and create a variable <code>pos</code> with the value of \(A\), and a
variable <code>delta</code> with the value of \(B - A\).
</p>
<p>
Next, we need to find the linear time at which point the segment
intersects with the box’s near and far edges.
</p>
<p>
We can calculate this by subtracting the position of the edge from the
segment’s start position, then dividing by the segment’s delta.
Scaling is done here using multiplication instead of division to deal
with floating point issues.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">const</span> scaleX = <span class="hljs-number">1.0</span> / delta.x;
<span class="hljs-keyword">const</span> scaleY = <span class="hljs-number">1.0</span> / delta.y;
<span class="hljs-keyword">const</span> signX = sign(scaleX);
<span class="hljs-keyword">const</span> signY = sign(scaleY);
<span class="hljs-keyword">const</span> nearTimeX = (<span class="hljs-keyword">this</span>.pos.x - signX * (<span class="hljs-keyword">this</span>.half.x + paddingX) - pos.x) * scaleX;
<span class="hljs-keyword">const</span> nearTimeY = (<span class="hljs-keyword">this</span>.pos.y - signY * (<span class="hljs-keyword">this</span>.half.y + paddingY) - pos.y) * scaleY;
<span class="hljs-keyword">const</span> farTimeX = (<span class="hljs-keyword">this</span>.pos.x + signX * (<span class="hljs-keyword">this</span>.half.x + paddingX) - pos.x) * scaleX;
<span class="hljs-keyword">const</span> farTimeY = (<span class="hljs-keyword">this</span>.pos.y + signY * (<span class="hljs-keyword">this</span>.half.y + paddingY) - pos.y) * scaleY;</pre>
</div>
<p>
Now we have to compare these times to see if a collision is possible.
</p>
<figure class="right">
<img src="./docs/svg/box-outside.svg" class="small" />
<figcaption>Near x is greater than far y</figcaption>
</figure>
<p>
<strong
>If the closest time of collision on either axis is further than the
far time on the opposite axis, we can’t be colliding.</strong
>
For instance, in the example to the right, because the segment’s
infinite line intersected the infinite line of the box’s top edge,
before it ever hit the line for the left edge, we know the
intersection occurred before the segment ever reached the box. We
don’t need to do any more checks, because we know a collision isn’t
possible.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">if</span> (nearTimeX > farTimeY || nearTimeY > farTimeX) {
<span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>;
}</pre>
</div>
<p>
Otherwise, find the greater of the near times, and the lesser of the
far times — we want the times that got closest to the slab. We
can check these two times to determine whether the collision occurred
on the segment.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">const</span> nearTime = nearTimeX > nearTimeY ? nearTimeX : nearTimeY;
<span class="hljs-keyword">const</span> farTime = farTimeX < farTimeY ? farTimeX : farTimeY;</pre>
</div>
<div class="figure-row right">
<figure>
<img src="./docs/svg/box-behind.svg" class="small" />
<figcaption>Behind the segment</figcaption>
</figure>
<figure>
<img src="./docs/svg/box-front.svg" class="small" />
<figcaption>In front of the segment</figcaption>
</figure>
</div>
<p>
If the <strong>near time is greater than or equal to 1</strong>, the
line starts in front of the nearest edge, but finishes before it
reaches it. That is, it means it further than a whole segment length
away. If the <strong>far time is less than or equal to 0</strong>, the
line starts in front of the far side of the box, and points away from
the box.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">if</span> (nearTime >= <span class="hljs-number">1</span> || farTime <= <span class="hljs-number">0</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>;
}</pre>
</div>
<p>
If we’ve gotten this far a collision of some sort is happening. If the
near time is greater than zero, the segment starts outside and is
entering the box. Otherwise, the segment starts inside the box, and is
exiting it. If we’re entering the box, we can set the hit time to the
near time, since that’s the point along the segment at which it
collided. If it’s inside, it’s colliding at the very starting of the
line, so just set the hit time to zero.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">const</span> hit = <span class="hljs-keyword">new</span> Hit(<span class="hljs-keyword">this</span>);
hit.time = clamp(nearTime, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>);
<span class="hljs-keyword">if</span> (nearTimeX > nearTimeY) {
hit.normal.x = -signX;
hit.normal.y = <span class="hljs-number">0</span>;
} <span class="hljs-keyword">else</span> {
hit.normal.x = <span class="hljs-number">0</span>;
hit.normal.y = -signY;
}
hit.delta.x = (<span class="hljs-number">1.0</span> - hit.time) * -delta.x;
hit.delta.y = (<span class="hljs-number">1.0</span> - hit.time) * -delta.y;
hit.pos.x = pos.x + delta.x * hit.time;
hit.pos.y = pos.y + delta.y * hit.time;
<span class="hljs-keyword">return</span> hit;
}</pre>
</div>
<h3 id="aabb-vs-aabb">AABB vs AABB</h3>
<p>
This test uses a
<a
href="http://www.metanetsoftware.com/technique/tutorialA.html#section1"
>separating axis test</a
>, which checks for overlaps between the two boxes on each axis. If
either axis is <em>not</em> overlapping, the boxes aren’t colliding.
</p>
<p>
The function returns a Hit object, or null if the two static boxes do
not overlap, and gives the axis of least overlap as the contact point.
That is, it sets <code>hit.delta</code> so that the colliding box will
be pushed out of the nearest edge. This can cause weird behavior for
moving boxes, so you should use <code>sweepAABB</code> instead for
moving boxes.
</p>
<p>
This code is very similar to the <code>intersectPoint</code> function
above.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">public</span> intersectAABB(box: AABB): Hit | <span class="hljs-literal">null</span> {
<span class="hljs-keyword">const</span> dx = box.pos.x - <span class="hljs-keyword">this</span>.pos.x;
<span class="hljs-keyword">const</span> px = (box.half.x + <span class="hljs-keyword">this</span>.half.x) - abs(dx);
<span class="hljs-keyword">if</span> (px <= <span class="hljs-number">0</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>;
}
<span class="hljs-keyword">const</span> dy = box.pos.y - <span class="hljs-keyword">this</span>.pos.y;
<span class="hljs-keyword">const</span> py = (box.half.y + <span class="hljs-keyword">this</span>.half.y) - abs(dy);
<span class="hljs-keyword">if</span> (py <= <span class="hljs-number">0</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>;
}
<span class="hljs-keyword">const</span> hit = <span class="hljs-keyword">new</span> Hit(<span class="hljs-keyword">this</span>);
<span class="hljs-keyword">if</span> (px < py) {
<span class="hljs-keyword">const</span> sx = sign(dx);
hit.delta.x = px * sx;
hit.normal.x = sx;
hit.pos.x = <span class="hljs-keyword">this</span>.pos.x + (<span class="hljs-keyword">this</span>.half.x * sx);
hit.pos.y = box.pos.y;
} <span class="hljs-keyword">else</span> {
<span class="hljs-keyword">const</span> sy = sign(dy);
hit.delta.y = py * sy;
hit.normal.y = sy;
hit.pos.x = box.pos.x;
hit.pos.y = <span class="hljs-keyword">this</span>.pos.y + (<span class="hljs-keyword">this</span>.half.y * sy);
}
<span class="hljs-keyword">return</span> hit;
}</pre>
</div>
<h3 id="aabb-vs-swept-aabb">AABB vs Swept AABB</h3>
<div class="figure-row right">
<figure>
<img src="./docs/svg/box-sweep-test.svg" class="small" />
<figcaption>
The sweep test prevents A from moving into B
</figcaption>
</figure>
<figure>
<img src="./docs/svg/box-sweep-padded-test.svg" class="small" />
<figcaption>
If B is padded with the size of A, this segment test is the same
as sweeping A.
</figcaption>
</figure>
</div>
<p>
Swept volume tests are awesome — they tell you whether object A
hits object B at any point along a movement path. This problem seems
hard, until someone tells you the magic word:
<a href="http://physics2d.com/content/gjk-algorithm">Minkowski</a>. If
you inflate the static box by the size of the moving box, you can just
test the movement <em>segment</em> against the padded static box. The
point at which the segment intersects the padded box tells you where
the moving box first collided with the static box.
</p>
<p>
<code>sweepAABB</code> finds the intersection of this box and another
moving box, where the <code>delta</code> argument is a point
describing the movement of the box. It returns a Sweep object.
<code>sweep.hit</code> will be a Hit object if the two collided, or
null if they did not overlap.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">public</span> sweepAABB(box: AABB, delta: Point): Sweep {
<span class="hljs-keyword">const</span> sweep = <span class="hljs-keyword">new</span> Sweep();</pre>
</div>
<p>
If the sweep isn’t actually moving anywhere, just do a static test.
It’s faster and will give us a better result for that case.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">if</span> (delta.x === <span class="hljs-number">0</span> && delta.y === <span class="hljs-number">0</span>) {
sweep.pos.x = box.pos.x;
sweep.pos.y = box.pos.y;
sweep.hit = <span class="hljs-keyword">this</span>.intersectAABB(box);
sweep.time = sweep.hit ? (sweep.hit.time = <span class="hljs-number">0</span>) : <span class="hljs-number">1</span>;
<span class="hljs-keyword">return</span> sweep;
}</pre>
</div>
<p>
Otherwise, call into <code>intersectSegment</code> instead, where the
segment is the center of the moving box, with the same delta. We pass
the moving box’s half size as padding. If we get a hit, we need to
adjust the hit pos. Since a segment vs box test was used, the hit pos
is the center of the box. This offsets it to the edge of the box, as
close to the segment of movement as possible.
</p>
<div class="highlight">
<pre> sweep.hit = <span class="hljs-keyword">this</span>.intersectSegment(box.pos, delta, box.half.x, box.half.y);
<span class="hljs-keyword">if</span> (sweep.hit) {
sweep.time = clamp(sweep.hit.time - EPSILON, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>);
sweep.pos.x = box.pos.x + delta.x * sweep.time;
sweep.pos.y = box.pos.y + delta.y * sweep.time;
<span class="hljs-keyword">const</span> direction = delta.clone();
direction.normalize();
sweep.hit.pos.x = clamp(
sweep.hit.pos.x + direction.x * box.half.x,
<span class="hljs-keyword">this</span>.pos.x - <span class="hljs-keyword">this</span>.half.x, <span class="hljs-keyword">this</span>.pos.x + <span class="hljs-keyword">this</span>.half.x);
sweep.hit.pos.y = clamp(
sweep.hit.pos.y + direction.y * box.half.y,
<span class="hljs-keyword">this</span>.pos.y - <span class="hljs-keyword">this</span>.half.y, <span class="hljs-keyword">this</span>.pos.y + <span class="hljs-keyword">this</span>.half.y);
} <span class="hljs-keyword">else</span> {
sweep.pos.x = box.pos.x + delta.x;
sweep.pos.y = box.pos.y + delta.y;
sweep.time = <span class="hljs-number">1</span>;
}
<span class="hljs-keyword">return</span> sweep;
}</pre>
</div>
<h3 id="sweeping-an-aabb-through-multiple-objects">
Sweeping an AABB Through Multiple Objects
</h3>
<p>
So, let’s say we have an AABB we want to move from one point to
another, without allowing it to collide with a list of static AABBs.
To do this, we need to call <code>sweepAABB</code> on each static
object, and keep track of the sweep that moved the least distance
— that is, the nearest collision to the start of the path.
</p>
<div class="highlight">
<pre> <span class="hljs-keyword">public</span> sweepInto(staticColliders: Collider[], delta: Point): Sweep {
<span class="hljs-keyword">let</span> nearest = <span class="hljs-keyword">new</span> Sweep();
nearest.time = <span class="hljs-number">1</span>;
nearest.pos.x = <span class="hljs-keyword">this</span>.pos.x + delta.x;
nearest.pos.y = <span class="hljs-keyword">this</span>.pos.y + delta.y;
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>, il = staticColliders.length; i < il; i++) {
<span class="hljs-keyword">const</span> sweep = staticColliders[i].sweepAABB(<span class="hljs-keyword">this</span>, delta);
<span class="hljs-keyword">if</span> (sweep.time < nearest.time) {
nearest = sweep;
}
}
<span class="hljs-keyword">return</span> nearest;
}
}</pre>
</div>
<p>
It’s a common use case to have a single object that needs to move
through a world, colliding with many other objects. Note that solving
this problem efficiently requires two steps:
</p>
<ol>
<li>
A broad phase, which does not do precise collision detection, but
which can very quickly reject large chunks of the world which are
not likely to be colliding. That is, you don’t have to try to
calculate how two objects are colliding if you know they’re in
entirely different rooms.
</li>
<li>
A narrow phase, which finds, given a set of items which are likely
to be colliding, the earliest point at which the moving object
collided with one of the items.
</li>
</ol>
<p>
The first step is out of scope for this library, but these tests are
great for solving the narrow phase. You can usually get away without a
broad phase for simple games, however, if you aren’t colliding against
a huge number of objects.
</p>
<div class="fleur">h</div>
</div>
</div>
<script src="docs/bundle.js"></script>
</body>
</html>