-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathindex.html
944 lines (831 loc) · 43.7 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
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<link rel="stylesheet" type="text/css" media="screen" href="style.css" />
<title>Circular Obstacle Pathfinding</title>
<meta name="description" content="Pathfinding around a set of circular obstacles" />
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css" integrity="sha384-wITovz90syo1dJWVh32uuETPVEtGigN07tkttEqPv+uR2SE/mbQcG7ATL28aI9H0" crossorigin="anonymous">
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.js" integrity="sha384-/y1Nn9+QQAipbNQWU65krzJralCnuOasHncUFXGkdwntGeSvQicrYkiUBwsgUqc1" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/contrib/auto-render.min.js" integrity="sha384-dq1/gEHSxPZQ7DdrM82ID4YVol9BYyU7GbWlIwnwyPzotpoc57wDw/guX8EaYGPx" crossorigin="anonymous"></script>
</head>
<body>
<header>
<a id="forkme_banner" href="https://github.com/redblobgames/circular-obstacle-pathfinding">View on GitHub</a>
<div>
<h1>Circular Obstacle Pathfinding</h1>
<h3>Pathfinding around a set of circular obstacles</h3>
</div>
</header>
<section>
<div>
<address>Mar 2017</address>
<h2 id="navigating-a-forest">Navigating a forest</h2>
<p>
The A* pathfinding algorithm is a powerful method for
quickly generating optimal paths. Typically, people
demonstrate A* navigating grid-based maps, but A* isn’t just
a grid algorithm! It can work on any graph. We can use A* to
find a path through this world of round obstacles.
</p>
<svg id="diagram-intro" viewBox="0 0 600 300">
<a-draggable v-for="(A, index) in circles"
:key="index" :model="A" :constraint="no_touching_circle(index)">
<circle :r="Math.max(A.r, 10)" />
</a-draggable>
<circle v-for="A in circles"
:cx="A.x" :cy="A.y" :r="A.r"
style="fill: none; stroke: black; stroke-width: 2px" />
<path :d="d(true, true)" stroke="hsl(0,50%,50%)" stroke-width="2" fill="none" />
<circle v-for="A in path"
:cx="A.x" :cy="A.y" :r="3" fill="hsl(0,100%,50%)" stroke="hsl(0,50%,25%)" />
</svg>
<p>
How does the same algorithm solve both problems? Let’s start
with a review of how A* works.
</p>
<h2 id="a-algorithm">A* algorithm</h2>
<p>
The A* algorithm finds the <em>optimal path</em> from the start point
to the end point, avoiding obstacles along the way. It does this by
gradually expanding a set of <em>partial paths</em>. Each partial path
is a series of steps from the start point to some intermediate point
on the way to the goal. As A* progresses, the partial paths get
closer and closer to the goal point. The algorithm terminates once it
finds a complete path that it can prove to be better than any of the
remaining possibilities.
</p>
<p>
At each step in the algorithm, A* evaluates the set of
partial paths and generates some new paths by expanding the
most promising path in the set. To do this, A* keeps the
partial paths in a priority queue, sorted by <em>estimated
length</em>—the actual measured length of the path so
far, plus a guess of the remaining distance to the
goal. This guess must be an <em>underestimate</em>; that is,
the guess can be less than the actual distance, but not
greater. In most pathfinding problems, a good underestimate
is the geometric straight-line distance from the end of the
partial path to the goal. The actual best path to the goal
from the end of the partial path might be longer than this
straight line distance, but it can’t be shorter.
</p>
<p>
When A* begins, the priority queue contains just one partial
path: the start point. The algorithm works by repeatedly
removing the most promising path from the priority queue,
that is, the path with the smallest estimated length. If
this path ends at the goal point, the algorithm is done—the
priority queue ensures that no other path could possibly be
better. Otherwise, starting from the end of the partial path
it removed from the queue, A* generates some new paths by
taking single steps in all possible directions. It places
these new paths back into the priority queue and begins the
process again.
</p>
<h2 id="graph">Graph</h2>
<p>
A* works on a <em>graph</em>: a collection of <em>nodes</em> connected
by <em>edges</em>. In a grid-based world, each node represents
an individual grid location, while each edge represents a
connection to a neighboring location to the north, south,
east or west.
</p>
<p>
Before A* can run on the forest of round obstacles, we need
to convert it into a graph. All the paths through the forest
consist of alternating line segments
<svg class="plain" width="5em" height="1em" viewBox="0 0 100 20">
<path class="surfing-edge" d="M 10,12 L 90,12" />
<circle class="graph-node" cx="10" cy="12" r="4" />
<circle class="graph-node" cx="90" cy="12" r="4" />
</svg>
and arc sections
<svg class="plain" width="5em" height="1em" viewBox="0 0 100 20">
<path class="hugging-edge" d="M 10,20 A 50,50 0 0 1 90,20" />
<circle class="graph-node" cx="10" cy="20" r="4" />
<circle class="graph-node" cx="90" cy="20" r="4" />
</svg>.
These are edges in the path graph. The endpoints of these
edges become nodes
<svg class="plain" width="1em" height="1em" viewBox="0 0 20 20">
<circle class="graph-node" cx="10" cy="10" r="8" />
</svg>.
A path through the graph is a series of nodes connected by edges:
</p>
<svg id="diagram-path-edges" viewBox="0 0 600 180">
<a-draggable v-for="(A, index) in circles"
:key="index" :model="A" :constraint="no_touching_circle(index)">
<circle :r="Math.max(A.r, 10)" />
</a-draggable>
<circle v-for="A in circles"
:cx="A.x" :cy="A.y" :r="A.r"
style="fill: none; stroke: black; stroke-opacity: 0.5; stroke-width: 0.5px" />
<path class="surfing-edge" :d="d(true, false)" style="stroke-width: 3px" />
<path class="hugging-edge" :d="d(false, true)" style="stroke-width: 5px" />
<circle v-for="A in path" class="graph-node" :cx="A.x" :cy="A.y" :r="3" />
</svg>
<p>
Both segments and arcs act as edges in the graph. We’ll call the
segments <em>surfing edges</em>, because the path uses them to surf between
obstacles. The arcs we’ll call <em>hugging edges</em>, as their purpose in
the path is to hug the sides of the obstacles.
</p>
<p>
Next we’ll explore a simple way to turn the obstacle forest into a
graph: generate all of the possible surfing and hugging edges.
</p>
<svg id="diagram-surfing-edges" viewBox="0 0 600 300">
<a-draggable v-for="(A, index) in circles"
:key="index" :model="A" :constraint="no_touching_circle(index)">
<circle :r="Math.max(A.r, 5)" />
</a-draggable>
<circle v-for="A in circles"
:cx="A.x" :cy="A.y" :r="A.r"
fill="none" stroke="black" class="hugging-edge" />
<line v-for="edge in surfing_edges" class="surfing-edge"
:x1="edge[0].x" :y1="edge[0].y"
:x2="edge[1].x" :y2="edge[1].y" />
<circle v-for="node in nodes" class="graph-node"
:cx="node.x" :cy="node.y" r="5" />
</svg>
<p>
This is called a <em>tangent visibility graph</em>.
</p>
<h3 id="generating-surfing-edges">Generating surfing edges</h3>
<p>
The surfing edges between a pair of circles are the line segments
which just barely kiss both circles; these segments are known as
<em>bitangents</em>, and there are four of them for each
pair of circles. The bitangents which cross between the
circles are the
<em>internal bitangents</em>, while the ones which go along the outside are
the <em>external bitangents</em>.
</p>
<h4 id="internal-bitangents">Internal bitangents</h4>
<p>
Historically, internal bitangents were important for calculating the
length of a belt which crosses over two different sized pulleys, and
so the problem of constructing internal bitangents is known as the <em>belt
problem</em>. To find the internal bitangents, calculate the angle \(\theta\)
in the diagram below.
</p>
<svg id="diagram-belt-problem" viewBox="0 0 600 300">
<defs>
<clipPath id="belt-problem-clip">
<circle :cx="B.x" :cy="B.y" :r="B.r" />
</clipPath>
</defs>
<a-draggable :model="A"><circle :r="A.r" /></a-draggable>
<a-draggable :model="B"><circle :r="B.r" /></a-draggable>
<circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black" />
<circle :cx="B.x" :cy="B.y" :r="B.r" fill="none" stroke="black" />
<circle :cx="A.x" :cy="A.y" :r="A.r" fill="hsl(0,20%,85%)" clip-path="url(#belt-problem-clip)" />
<line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" />
<a-label :at="A" :opposite="B" label="A" />
<a-label :at="B" :opposite="A" label="B" />
<template v-if="non_overlapping">
<line class="dashed" :x1="A.x" :y1="A.y" :x2="C.x" :y2="C.y" />
<line class="dashed" :x1="A.x" :y1="A.y" :x2="D.x" :y2="D.y" />
<line class="dashed" :x1="B.x" :y1="B.y" :x2="E.x" :y2="E.y" />
<line class="dashed" :x1="B.x" :y1="B.y" :x2="F.x" :y2="F.y" />
<line class="surfing-edge" :x1="C.x" :y1="C.y" :x2="F.x" :y2="F.y" />
<line class="surfing-edge" :x1="D.x" :y1="D.y" :x2="E.x" :y2="E.y" />
<circle class="graph-node" :cx="C.x" :cy="C.y" r="5" />
<circle class="graph-node" :cx="D.x" :cy="D.y" r="5" />
<circle class="graph-node" :cx="E.x" :cy="E.y" r="5" />
<circle class="graph-node" :cx="F.x" :cy="F.y" r="5" />
<a-label :at="C" :opposite="A" label="C" />
<a-label :at="D" :opposite="A" label="D" />
<a-label :at="E" :opposite="B" label="E" />
<a-label :at="F" :opposite="B" label="F" />
<a-label :at="theta_AC" :opposite="A" label="θ" />
<a-label :at="theta_AD" :opposite="A" label="θ" />
<a-label :at="theta_BE" :opposite="B" label="θ" />
<a-label :at="theta_BF" :opposite="B" label="θ" />
</template>
<template v-else="">
<text class="plain" x="300" y="15">Overlapping circles have no bitangents</text>
</template>
</svg>
<p>
It turns out that, given circles centered on points \(A\)
and \(B\) with radii \(r_A\) and \(r_B\), and centers
separated by distance \(d\): \[\theta =
\arccos{{r_A+r_B}\over{d}}\] Once \(\theta\) is known, it's
easy to find points \(C\), \(D\), \(E\) and \(F\).
</p>
<h4 id="external-bitangents">External bitangents</h4>
<p>
Constructing external bitangents—the <em>pulley problem</em>—uses a
similar technique.
</p>
<svg id="diagram-pulley-problem" viewBox="0 0 600 300">
<defs>
<clipPath id="pulley-problem-clip">
<circle :cx="B.x" :cy="B.y" :r="B.r" />
</clipPath>
</defs>
<a-draggable :model="A"><circle :r="A.r" /></a-draggable>
<a-draggable :model="B"><circle :r="B.r" /></a-draggable>
<circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black" />
<circle :cx="B.x" :cy="B.y" :r="B.r" fill="none" stroke="black" />
<circle :cx="A.x" :cy="A.y" :r="A.r" :fill="containing?'hsl(0,20%,85%)':'hsl(240,25%,85%)'" clip-path="url(#pulley-problem-clip)" />
<line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" />
<a-label :at="A" :opposite="B" label="A" />
<a-label :at="B" :opposite="A" label="B" />
<template v-if="!containing">
<line class="dashed" :x1="A.x" :y1="A.y" :x2="C.x" :y2="C.y" />
<line class="dashed" :x1="A.x" :y1="A.y" :x2="D.x" :y2="D.y" />
<line class="dashed" :x1="B.x" :y1="B.y" :x2="E.x" :y2="E.y" />
<line class="dashed" :x1="B.x" :y1="B.y" :x2="F.x" :y2="F.y" />
<line class="surfing-edge" :x1="C.x" :y1="C.y" :x2="F.x" :y2="F.y" />
<line class="surfing-edge" :x1="D.x" :y1="D.y" :x2="E.x" :y2="E.y" />
<circle class="graph-node" :cx="C.x" :cy="C.y" r="5" />
<circle class="graph-node" :cx="D.x" :cy="D.y" r="5" />
<circle class="graph-node" :cx="E.x" :cy="E.y" r="5" />
<circle class="graph-node" :cx="F.x" :cy="F.y" r="5" />
<a-label :at="C" :opposite="A" label="C" />
<a-label :at="D" :opposite="A" label="D" />
<a-label :at="E" :opposite="B" label="E" />
<a-label :at="F" :opposite="B" label="F" />
<a-label :at="theta_AC" :opposite="A" label="θ" />
<a-label :at="theta_AD" :opposite="A" label="θ" />
<a-label :at="theta_BE" :opposite="B" label="θ" />
<a-label :at="theta_BF" :opposite="B" label="θ" />
</template>
<template v-else="">
<text class="plain" x="300" y="15">Smaller circle entirely contained in larger one</text>
</template>
</svg>
<p>
For external bitangents we can find \(\theta\) like this:
\[\theta = \arccos{{\lvert r_A - r_B \rvert} \over d}\]
It doesn’t matter whether circle A or B is bigger, but as shown in
the diagram, \(\theta\) appears on the side of A toward B,
but on the side of B away from A.
</p>
<h4 id="surfing-line-of-sight">Line of sight</h4>
<p>
Taken together, the internal and external bitangents between two
circles constitute surfing edges between the circles. But what if a
third circle blocks one or more of the surfing edges?
</p>
</div>
<div id="diagram-surfing-line-of-sight">
<svg viewBox="0 0 600 200">
<defs>
<clipPath id="surfing-line-of-sight-clip">
<circle :cx="C.x" :cy="C.y" :r="C.r" />
</clipPath>
</defs>
<line class="surfing-edge" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" />
<a-draggable :model="C"><circle :r="C.r" /></a-draggable>
<circle class="graph-node" :cx="A.x" :cy="A.y" r="5" />
<circle class="graph-node" :cx="B.x" :cy="B.y" r="5" />
<line class="surfing-edge invalid-edge"
:x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y"
clip-path="url(#surfing-line-of-sight-clip)" />
<a-label :at="A" :opposite="B" label="A" />
<a-label :at="B" :opposite="A" label="B" />
<circle :cx="C.x" :cy="C.y" :r="C.r" fill="none" stroke="black" />
<circle class="point" :cx="C.x" :cy="C.y" r="3" />
<a-label :at="C" :opposite="E" label="C" />
<text class="plain" x="300" y="25">
<template v-if="intersects">Circle blocks line of sight</template>
<template v-else>A and B visible from each other</template>
</text>
</svg>
<p>
If a surfing edge is blocked by another circle, we need to throw the
edge out. To detect this case, we use a simple <em>point-line-distance</em>
calculation. If the distance from the surfing edge to the obstacle’s
center is less than the obstacle’s radius, then the obstacle blocks
the surfing edge, and we should throw the edge away.
</p>
<p>
To calculate the distance from point \(C\) to line segment
\(\overline{AB}\), use the
<a href="http://paulbourke.net/geometry/pointlineplane/">following
method</a>:
</p>
<p>
First, compute \(u\), the fraction of the distance along
segment \(\overline{AB}\) at which a perpendicular ascender
hits point \(C\):
</p>
<p>
\[ u = {(C - A) \cdot (B-A) \over (B-A)\cdot(B-A)} \]
</p>
<p>
Then compute the position \(E\) on \(\overline{AB}\):
</p>
<p>
\[ E = A + \mathrm{clamp}(u, 0, 1) * (B - A) \]
</p>
<svg viewBox="0 0 600 300">
<line class="surfing-edge" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" />
<a-draggable :model="C"><circle :r="C.r" /></a-draggable>
<line class="surfing-edge invalid-edge" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" clip-path="url(#surfing-line-of-sight-clip)" />
<circle class="graph-node" :cx="A.x" :cy="A.y" r="5" />
<circle class="graph-node" :cx="B.x" :cy="B.y" r="5" />
<g :transform="`translate(0,${dashed_line_offset})`">
<!-- horizontal ruler showing 'u' -->
<line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" />
<a-tick :at="A" :opposite="B" />
<a-tick :at="B" :opposite="A" />
<circle class="point" :cx="A.x" :cy="A.y" :r="3" />
<circle class="point" :cx="B.x" :cy="B.y" :r="3" />
<circle class="point" :cx="C.x" :cy="A.y" :r="3" />
<text :x="A.x" :y="A.y" dx="-10" dy="5">0</text>
<text :x="B.x" :y="B.y" dx="10" dy="5">1</text>
<text :x="C.x" :y="A.y" :dy="5 + dashed_line_offset/5">u={{Math.round(100*(C.x-A.x)/(B.x-A.x))/100}}</text>
</g>
<g>
<!-- ruler showing 'd' -->
<a-tick :at="C" :opposite="E" />
<a-tick :at="E" :opposite="C" />
<text :x="(C.x+E.x)/2" :y="(C.y+E.y)/2" dx="15" dy="5">d</text>
</g>
<g>
<!-- ruler showing 'r' -->
<line class="dashed" :x1="C.x" :y1="C.y" :x2="F.x" :y2="F.y" />
<text :x="0.2*C.x+0.8*F.x" :y="0.2*C.y+0.8*F.y" dx="-5" dy="10">r</text>
</g>
<circle class="point" :cx="C.x" :cy="C.y" r="3" />
<circle class="point" :cx="E.x" :cy="E.y" r="3" />
<a-label :at="A" :opposite="B" label="A" />
<a-label :at="B" :opposite="A" label="B" />
<a-label :at="C" :opposite="E" label="C" />
<a-label :at="E" :opposite="C" label="E" dx="-10" />
<line class="dashed" :x1="C.x" :y1="C.y" :x2="E.x" :y2="E.y" />
<line class="dashed" :x1="C.x" :y1="C.y" :x2="C.x" :y2="A.y + dashed_line_offset" />
<circle :cx="C.x" :cy="C.y" :r="C.r" fill="none" stroke="black" />
</svg>
<p>
The distance \(d\) from \(C\) to segment \(\overline{AB}\)
is the distance from \(C\) to \(E\):
\[d = \|E - C\|\]
Since <span v-if="d < r">\(d < r\), the circle blocks the line of sight
from \(A\) to \(B\), and the edge should be thrown out.</span>
<span v-else>\(d \ge r\), there is line of sight from \(A\) to
\(B\), and the edge should be kept.</span> Try moving
the circle to see the case where <span v-if="d < r">\(d \ge r\)</span>
<span v-else>\(d < r\)</span>.
</p>
</div>
<div>
<h3 id="generating-hugging-edges">Generating hugging edges</h3>
<p>
The graph nodes connect a surfing edge to a hugging edge. We
generated the surfing edges in the previous sections. To
generate the hugging edges we start at the endpoint of a
surfing edge, traverse around the circle, and terminate at
the endpoint of a different surfing edge.
</p>
<svg id="diagram-hugging-edge" viewBox="0 0 600 300">
<a-draggable :model="A"><circle r="10" /></a-draggable>
<a-draggable :model="E"><circle r="10" /></a-draggable>
<template v-if="valid">
<line class="surfing-edge" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" />
<line class="surfing-edge" :x1="D.x" :y1="D.y" :x2="E.x" :y2="E.y" />
</template>
<a-draggable :model="C"><circle :r="C.r" /></a-draggable>
<template v-if="valid">
<line class="dashed" :x1="C.x" :y1="C.y" :x2="B.x" :y2="B.y" />
<line class="dashed" :x1="C.x" :y1="C.y" :x2="D.x" :y2="D.y" />
<a-label :at="C" :opposite="mid_BD" label="C" />
<a-label :at="B" :opposite="C" label="B" />
<a-label :at="D" :opposite="C" label="D" />
</template>
<circle class="graph-node" :cx="A.x" :cy="A.y" r="5" />
<circle class="graph-node" :cx="E.x" :cy="E.y" r="5" />
<circle :cx="C.x" :cy="C.y" :r="C.r" fill="none" stroke="black" />
<template v-if="valid">
<path class="hugging-edge" :d="arc_path" />
<circle class="graph-node" :cx="B.x" :cy="B.y" r="5" />
<circle class="graph-node" :cx="D.x" :cy="D.y" r="5" />
</template>
</svg>
<p>
To find the set of hugging edges for a circle, first find
all the surfing edges that touch the circle. Then, create
hugging edges between all the surfing edge endpoints on the
circle.
</p>
<h2 id="putting-it-all-together">Putting it all together</h2>
<p>
Given the generation of surfing edges, hugging edges and
nodes, and the culling of blocked surfing edges, we can
produce a graph and run pathfinding using the A* algorithm.
</p>
<svg id="diagram-final" viewBox="0 0 600 300">
<a-draggable v-for="(A, index) in circles"
:key="index" :model="A" :constraint="no_touching_circle(index)">
<circle :r="Math.max(A.r, 10)" />
</a-draggable>
<circle v-for="A in circles"
:cx="A.x" :cy="A.y" :r="A.r"
class="hugging-edge"
style="stroke-width: 1px" />
<line v-for="edge in surfing_edges" class="surfing-edge"
:x1="edge[0].x" :y1="edge[0].y"
:x2="edge[1].x" :y2="edge[1].y"
style="stroke: hsl(260,10%,80%);stroke-width: 1px" />
<circle v-for="node in nodes" class="graph-node"
:cx="node.x" :cy="node.y" :r="node.circle.r == 0? 7 : 2" />
<path class="surfing-edge" :d="d(true, false)" stroke-width="2" />
<path class="hugging-edge" :d="d(false, true)" stroke-width="2" />
<circle v-for="A in path"
:cx="A.x" :cy="A.y" :r="3" fill="hsl(0,100%,50%)" stroke="hsl(0,50%,25%)" />
</svg>
</div>
</section>
<section>
<div>
<h2 id="enhancements">Enhancements</h2>
<p>
The graph generation procedure we've discussed works well
enough for explaining the algorithm, but there are many ways in which
it can be improved. These enhancements make the algorithm use less CPU
and memory, and allow it to handle more cases. Let's take a look at a
few.
</p>
<h3>Obstacles that touch</h3>
<p>
Perhaps you picked up on it—none of the circular obstacles in
the examples given so far have overlapped or even touched. Allowing
circles to touch makes the pathfinding problem a little, but not much,
harder.
</p>
<h4>Bitangents</h4>
<p>
Recall that bitangents can be found using this formula for internal bitangents:
\[\theta = \arccos{{r_A+r_B}\over{d}}\]
and this one for external bitangents:
\[\theta = \arccos{{\lvert r_A - r_B \rvert} \over d}\]
</p>
<p>
When two circles touch or overlap, there are no internal
bitangents between them. In this case \({r_A+r_B}\over d\)
is greater than one. Since arccosine is undefined for inputs
outside its domain of \([-1, 1]\), it's important to check
for circle overlap before performing the arccosine.
</p>
<p>
Likewise, if one circle completely encloses the other, then
there are no external bitangents between the circles. In
this case \({r_A - r_B} \over d\) is outside the range
\([-1, 1]\), and it has no arccosine.
</p>
<svg id="diagram-bitangents-overlap" viewBox="0 0 600 300">
<defs>
<clipPath id="overlap-clip">
<circle :cx="B.x" :cy="B.y" :r="B.r" />
</clipPath>
</defs>
<a-draggable :model="A"><circle :r="A.r" /></a-draggable>
<a-draggable :model="B"><circle :r="B.r" /></a-draggable>
<circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black" />
<circle :cx="B.x" :cy="B.y" :r="B.r" fill="none" stroke="black" />
<circle :cx="A.x" :cy="A.y" :r="A.r" :fill="containing?'hsl(0,20%,85%)':'hsl(240,25%,85%)'" clip-path="url(#overlap-clip)" />
<line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" />
<a-label :at="A" :opposite="B" label="A" />
<a-label :at="B" :opposite="A" label="B" />
<template v-if="!containing">
<line class="surfing-edge"
:x1="external.C.x" :y1="external.C.y"
:x2="external.F.x" :y2="external.F.y" />
<line class="surfing-edge"
:x1="external.D.x" :y1="external.D.y"
:x2="external.E.x" :y2="external.E.y" />
<template v-if="!overlapping">
<line class="surfing-edge"
:x1="internal.C.x" :y1="internal.C.y"
:x2="internal.F.x" :y2="internal.F.y" />
<line class="surfing-edge"
:x1="internal.D.x" :y1="internal.D.y"
:x2="internal.E.x" :y2="internal.E.y" />
<text class="plain" x="300" y="15">Circles don't overlap: both external and internal bitangents</text>
</template>
<template v-else>
<text class="plain" x="300" y="15">Circles overlap: external bitangents only</text>
</template>
</template>
<template v-else>
<text class="plain" x="300" y="15">Small circle contained by large one: no bitangents</text>
</template>
</svg>
<h4 id="surfing-line-of-sight-2">Surfing edge line of sight</h4>
<p>
When obstacles are allowed to touch or overlap, new cases
arise in calculating surfing edge line of sight.
Recall <a href="#surfing-line-of-sight">the calculation of \(u\)</a>,
the fraction of distance along the surfing edge at which a
perpendicular ascender to the point touches the edge. When
circles are not allowed to touch, a value of \(u\) outside
\([0,1]\) means that the circle cannot touch the edge
because to do so it would have to touch one of the endpoints
of the edge. This is impossible, because the endpoints of
the edge are already tangent to (and thus touching) other
circles.
</p>
<p>
However, if circles are allowed to overlap, then values of
\(u\) outside \([0,1]\) might block line of sight along the
edge. This corresponds to cases where the circle is off the
end of the surfing edge, but covering or touching an
endpoint. To catch these cases mathematically, we <em>clamp</em> \(u\) to the range \([0,1]\):
\[E = A + clamp(u, 0, 1) * (B - A)\]
</p>
<h4 id="hugging-line-of-sight">Hugging edge line of sight</h4>
<p>
When obstacles are allowed to touch or overlap, hugging
edges can be blocked by obstacles just as surfing edges
can. Consider the hugging edge in the diagram below. If
another obstacle touches the hugging edge, it’s blocked and
should be thrown out.
</p>
<svg id="diagram-hugging-overlap" viewBox="0 0 600 300">
<circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black" />
<a-draggable :model="B">
<circle :r="B.r" fill-opacity="0.01" stroke="black" />
</a-draggable>
<path
:d="`M ${A.x-A.r},${A.y} A ${A.r},${A.r} 0 0 1 ${A.x+A.r},${A.y}`"
class="hugging-edge"
:class="{'invalid-edge': AD_angle < 0 || AE_angle < 0}"
></path>
<circle class="point" :cx="A.x" :cy="A.y" r="3" />
<circle class="point" :cx="B.x" :cy="B.y" r="3" />
<circle v-if="valid" class="point" :cx="D.x" :cy="D.y" r="3" />
<circle v-if="valid" class="point" :cx="E.x" :cy="E.y" r="3" />
<text class="plain" x="300" y="275">
<template v-if="AD_angle < 0 || AE_angle < 0">Hugging edge blocked</template>
<template v-else>Hugging edge valid</template>
</text>
</svg>
<p>
To determine whether a hugging edge is blocked by another
obstacle, use the
<a href="http://paulbourke.net/geometry/circlesphere/">following method
</a> to determine the points at which the two circles
intersect. Given circles centered on points \(A\) and \(B\)
with radii \(r_A\) and \(r_B\), where \(d\) is the distance
between \(A\) and \(B\), there are a few cases to check for
first. If the circles are not touching (that is, \(d > r_A + r_B\)),
if one circle is inside the other (\(d < |r_A - r_B|\)), or
the circles are coincident (\(d = 0\) and \(r_A = r_B\)),
then the circles cannot interfere with each others' hugging
edges.
</p>
<p>
If none of these cases hold, then the circles intersect at two
points—if the circles are tangent to each other, these two
points are coincident. Consider the <em>radical line</em> which
connects the intersection points; it's perpendicular to the line
connecting \(A\) and \(B\) at some point \(C\). We can calculate the
distance \(a\) from \(A\) to \(C\) as follows:
\[a = {r_A^2 - r_B^2 + d^2 \over 2d } \]
Having found \(a\), we can find the angle \(\theta\):
\[\theta = \arccos {a \over r_A} \]
If \(\theta\) is zero, the circles are
tangent at \(C\). Otherwise, there are two intersection
points, corresponding to positive and negative \(\theta\).
</p>
<svg id="diagram-circle-overlap" viewBox="0 0 600 300">
<a-draggable :model="A"><circle :r="A.r" /></a-draggable>
<a-draggable :model="B"><circle :r="B.r" /></a-draggable>
<line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y" />
<line v-if="valid" class="dashed" :x1="D.x" :y1="D.y" :x2="E.x" :y2="E.y" />
<line v-if="valid" class="dashed" :x1="A.x" :y1="A.y" :x2="D.x" :y2="D.y" />
<line v-if="valid" class="dashed" :x1="A.x" :y1="A.y" :x2="E.x" :y2="E.y" />
<circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black" />
<circle :cx="B.x" :cy="B.y" :r="B.r" fill="none" stroke="black" />
<circle class="point" :cx="A.x" :cy="A.y" r="3" />
<circle class="point" :cx="B.x" :cy="B.y" r="3" />
<circle v-if="valid" class="point" :cx="C.x" :cy="C.y" r="3" />
<circle v-if="valid" class="point" :cx="D.x" :cy="D.y" r="3" />
<circle v-if="valid" class="point" :cx="E.x" :cy="E.y" r="3" />
<a-label :at="A" :opposite="B" label="A" />
<a-label :at="B" :opposite="A" label="B" />
<a-label v-if="valid" :at="C" :opposite="opposite_C" label="C" />
<a-label v-if="valid" :at="theta_AC" :opposite="A" label="θ" />
<a-label v-if="valid" :at="theta_AD" :opposite="A" label="θ" />
<a-label v-if="valid" :at="D" :opposite="C" label="D" />
<a-label v-if="valid" :at="E" :opposite="C" label="E" />
<text class="plain" x="300" y="275">
<template v-if="containing">Larger circle contains smaller one</template>
<template v-if="!overlapping">Circles don't overlap</template>
</text>
</svg>
<p>
Next, determine whether either of the intersection points fall between
the start and end points of the hugging edge. If this is the case,
then the obstacle blocks the hugging edge, and we should discard the
edge. Note that we don’t have to worry about the case where the
hugging edge is entirely contained within an obstacle, as the line of
sight culling for surfing edges will have already thrown the edge out.
</p>
<p>
After making the changes for bitangent calculation and line of sight
for surfing and hugging edges, everything else just works.
</p>
<h3>Variable actor radius via Minkowski expansion</h3>
<p>
When navigating a round object through a world of round obstacles, we
can make a few observations that simplify the problem. First, we can
make things easier by noticing that moving a circle of radius <em>r</em>
through a forest of round obstacles is identical to moving a point
through that same forest with one change: each obstacle has its radius
increased by <em>r</em>. This is an extremely simple application of
<em>Minkowski addition</em>. If it has a radius larger than
zero, we’ll just increase the size of the obstacles before
we start.
</p>
<h3 id="delayed-edge-generation">Delayed edge generation</h3>
<p>
In general, the graph for a forest of \(n\) obstacles contains
\(O(n^2)\) surfing edges, but since each of these must be checked for
line of sight against \(n\) obstacles, the total time to generate the
graph is \(O(n^3)\). Additionally, pairs of surfing edges can induce
hugging edges, and each of these must be checked against every
obstacle for line of sight. However, because the A* algorithm is so
efficient, it normally looks at only a fraction of this large graph to
produce an optimal path.
</p>
<p>
We can save time by generating small portions of the graph on the fly
as we proceed through the A* algorithm, rather than doing all of the
work up front. If A* finds a path quickly, we'll generate only a small
part of the graph. We do this by moving edge generation to the
<code>neighbors()</code> function.
</p>
<p>
There are several cases. At the beginning of the algorithm, we need the
neighbors of the start point. These are surfing edges from the start point
to the left and right edges of each obstacle.
</p>
<p>
The next case is when A* has just arrived at point \(p\) on on the
edge of obstacle \(C\) along a surfing edge: <code>neighbors()</code>
needs to return the hugging edges leading from \(p\). To do
this determine which surfing edges leave the obstacle by
computing the bitangents between \(C\) and every other
obstacle, throwing away any that do not have line of sight.
Then find all the hugging edges that connect \(p\) to these
surfing edges, discarding those that are blocked by other
obstacles. Return all of these hugging edges, saving the
surfing edges for return in a subsequent <code>neighbors()</code>
call.
</p>
<p>
The last case is when A* has traversed a hugging edge along obstacle
\(C\) and needs to leave the \(C\) via a surfing edge. Because the
previous step calculated and saved all the surfing edges, the correct
set of edges can just be looked up and returned.
</p>
<h3>Cull cusped hugging edges</h3>
<p>
Hugging edges connect surfing edges which touch the same circle, but
it turns out that many of these hugging edges are not eligible to be
used in any optimal path. We can speed up the algorithm by eliminating
them.
</p>
<p>
An optimal path through the forest of obstacles always
consists of alternating surfing and hugging edges. Suppose
we're entering at node \(A\) and are trying to decide how to
exit:
</p>
<svg id="diagram-rotation-1" viewBox="0 0 600 300">
<defs>
<marker id="arrowhead-start" viewBox="0 0 10 10" refX="-3" refY="5" markerUnits="strokeWidth" markerWidth="5" markerHeight="4" orient="auto">
<path d="M 10 0 L 0 5 L 10 10 z" />
</marker>
<marker id="arrowhead-end" viewBox="0 0 10 10" refX="7" refY="5" markerUnits="strokeWidth" markerWidth="5" markerHeight="4" orient="auto">
<path d="M 0 0 L 10 5 L 0 10 z" />
</marker>
</defs>
<circle class="hugging-edge" :cx="circle.x" :cy="circle.y" :r="circle.r"
style="fill:hsla(240,0%,100%,0.5)" />
<template v-for="edge in edges">
<a-draggable :model="edge"><circle r="10" /></a-draggable>
<line class="surfing-edge"
:x1="center(edge).x" :y1="center(edge).y"
:x2="edge.x" :y2="edge.y"
:marker-start="edge.marker == 'start' && 'url(#arrowhead-start)'"
:marker-end="edge.marker == 'end' && 'url(#arrowhead-end)'"
/>
<circle class="graph-node" :cx="center(edge).x" :cy="center(edge).y" r="5" />
<a-label :at="center(edge)" :opposite="circle" :label="edge.label" />
</template>
</svg>
<p>
Entering through \(A\) means we're going <em>clockwise</em>\(\circlearrowright\).
We must exit through a node that keeps us going clockwise\(\circlearrowright\),
so we can only exit through node \(B\) or \(D\). Exiting through \(C\) creates
a <em>cusp</em>\(\curlywedge\) in the path, which will never
be optimal. We want to filter out these cusped edges.
</p>
<p>
First note that A* already treats each undirected
edge \(P \longleftrightarrow Q\) as two directed edges, \(P
\longrightarrow Q\) and \(Q \longrightarrow P\). We can take
advantage of this by annotating the edges and nodes with directions.
</p>
<ol>
<li>
The nodes \(P\) become nodes with a direction, either
clockwise \(P\circlearrowright\) or counterclockwise
\(P\circlearrowleft\).
</li>
<li>
The undirected surfing edges \(P \longleftrightarrow Q\)
become directed edges \(P,p \longrightarrow
Q,\hat{q}\) and \(Q,q \longrightarrow P,\hat{p}\), where
\(p\) and \(q\) are directions, and \(\hat{x}\) means the
opposite direction of \(x\).
</li>
<li>
The undirected hugging edges \(P \longleftrightarrow Q\)
become directed edges \(P\circlearrowright \longrightarrow
Q\circlearrowright\) and \(P\circlearrowleft
\longrightarrow Q\circlearrowleft\). This is where the
filtering happens: we <em>don't</em> include
\(P\circlearrowright \longrightarrow Q\circlearrowleft\) and
\(P\circlearrowleft \longrightarrow Q\circlearrowright\),
because changing direction introduces cusps\(\curlywedge\).
</li>
</ol>
<p>
In our diagram, node \(A\) would become two nodes,
\(A\circlearrowright\) and \(A\circlearrowleft\), and have
an incoming surfing edge \(\longrightarrow
A\circlearrowright\) and an outgoing surfing edge
\(A\circlearrowleft \longrightarrow\). If the path entered
through \(A\circlearrowright\) then it must exit through a
\(\circlearrowright\) node, which would be either the
\(B\circlearrowright \longrightarrow\) surfing edge (via the
\(A\circlearrowright \longrightarrow B\circlearrowright\)
hugging edge) or the \(D\circlearrowright \longrightarrow\)
surfing edge (via the \(A\circlearrowright \longrightarrow
D\circlearrowright\) hugging edge). It can't leave through
\(C\circlearrowleft \longrightarrow\) because it changes
rotation direction, and we have filtered out the
\(A\circlearrowright \longrightarrow C\circlearrowleft\)
hugging edge.
</p>
<p>
By filtering these cusped hugging edges out of the graph, we
make the algorithm more efficient.
</p>
<h3 id="crossing-edge-culling">Crossing edge culling</h3>
<p>
Cull partial paths whose final surfing edge crosses the penultimate
surfing edge.
</p>
<h3 id="polygonal-obstacles">Polygonal obstacles</h3>
<p>
See <a href="https://dl.acm.org/citation.cfm?id=516343">Game Programming Gems 2</a>, Chapter 3.10, Optimizing Points-of-Visibility Pathfinding by Thomas Young. It covers the node culling but for polygons instead of circles.
</p>
<h2 id="references">References</h2>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Belt_problem">Belt problem</a></li>
<li><a href="https://en.wikipedia.org/wiki/Belt_problem#Pulley_problem">Pulley problem</a></li>
<li><a href="http://paulbourke.net/geometry/pointlineplane/">Point line distance</a></li>
<li><a href="http://paulbourke.net/geometry/circlesphere/">Intersection of two circles</a></li>
</ul>
</div>
</section>
<footer>
<div>
<p class="copyright">Copyright 2017 by <a href="https://github.com/redblobgames">redblobgames</a> and <a href="https://github.com/shillingsburg">shillingsburg</a>. Implemented with <a href="https://khan.github.io/KaTeX/">KaTeX</a> and <a href="https://vuejs.org/">Vue.js</a>.
</p>
</div>
<svg class="plain" width="0" height="0">
<defs>
<filter id="drop-shadow" x="-100%" y="-100%" width="300%" height="300%">
<feGaussianBlur in="SourceAlpha" stdDeviation="2" />
<feOffset dx="0" dy="1" result="offsetblur" />
<feFlood flood-color="#000000" />
<feComposite in2="offsetblur" operator="in" />
<feMerge>
<feMergeNode />
<feMergeNode in="SourceGraphic" />
</feMerge>
</filter>
</defs>
</svg>
<script>
renderMathInElement(document.body);
</script>
<script src="https://unpkg.com/vue@^2.5.0/dist/vue.min.js"></script>
<script src="lib.js"></script>
<script src="components.js"></script>
<script src="belt-problem.js"></script>
<script src="graph-diagrams.js"></script>
</footer>
</body>
</html>