walls.gno
9.47 Kb · 347 lines
1package physics
2
3import "math"
4
5// offset is what Step needs of a wall: its two offset lines (where the
6// ball's centre meets it), their normals, the wall's start, normal and
7// length, its bounce and timing, and its broad-phase box.
8type offset struct {
9 plus, minus Segment
10 pn, mn Vec2 // plus.Normal(), minus.Normal()
11 a, n Vec2
12 length, bounce float64
13 every, on, phase int
14 lo, hi Vec2
15}
16
17// unstickGap is how far clear of a piece UnstickIn sets a ball down.
18const unstickGap = 0.02
19
20// boxPad grows every broad-phase box: more than the half skin of Step's near
21// test, and far more than rounding.
22const boxPad = 1e-6
23
24// lines works out a wall's offset lines for a ball of radius r: the segment
25// pushed r to each side and lengthened by r at each end. Same bits as Normal
26// and that push, with 3 square roots instead of 8.
27func lines(s Segment, r float64, o *offset) {
28 d := s.B.Sub(s.A)
29 l := d.Len()
30 o.a, o.length = s.A, l
31 if l == 0 {
32 o.plus, o.minus, o.n, o.pn, o.mn = s, s, Vec2{}, Vec2{}, Vec2{}
33 } else {
34 n := Vec2{-d.Y / l, d.X / l}
35 toward := func(p Vec2) Segment {
36 m := n
37 if p.Sub(s.A).Dot(m) < 0 {
38 m = m.Scale(-1)
39 }
40 e, off := d.Scale(r/l), m.Scale(r)
41 return Segment{A: s.A.Sub(e).Add(off), B: s.B.Add(e).Add(off)}
42 }
43 o.n = n
44 o.plus, o.minus = toward(s.A.Add(n)), toward(s.A.Sub(n))
45 o.pn, o.mn = o.plus.Normal(), o.minus.Normal()
46 }
47 o.lo, o.hi = o.plus.A, o.plus.A
48 for _, p := range []Vec2{o.plus.B, o.minus.A, o.minus.B} {
49 if p.X < o.lo.X {
50 o.lo.X = p.X
51 } else if p.X > o.hi.X {
52 o.hi.X = p.X
53 }
54 if p.Y < o.lo.Y {
55 o.lo.Y = p.Y
56 } else if p.Y > o.hi.Y {
57 o.hi.Y = p.Y
58 }
59 }
60 o.lo, o.hi = o.lo.Sub(Vec2{boxPad, boxPad}), o.hi.Add(Vec2{boxPad, boxPad})
61}
62
63// stride is the floats per wall in Field.prep: the wall's ends (to know the
64// entry is still that wall's), then plus, minus, pn, mn, n, length, lo, hi.
65const stride = 23
66
67// Prepare works out the field's wall offsets once, for every shot to reuse.
68// Call it once the walls are where they stay: Step works out again any wall
69// that no longer matches its entry.
70func Prepare(f *Field) {
71 p := make([]float64, 1, 1+stride*len(f.Walls))
72 p[0] = f.Radius
73 var o offset
74 for j := range f.Walls {
75 s := f.Walls[j].Seg
76 lines(s, f.Radius, &o)
77 p = appendPrep(p, s, &o)
78 }
79 f.prep = p
80}
81
82func appendPrep(p []float64, s Segment, o *offset) []float64 {
83 return append(p, s.A.X, s.A.Y, s.B.X, s.B.Y,
84 o.plus.A.X, o.plus.A.Y, o.plus.B.X, o.plus.B.Y,
85 o.minus.A.X, o.minus.A.Y, o.minus.B.X, o.minus.B.Y,
86 o.pn.X, o.pn.Y, o.mn.X, o.mn.Y, o.n.X, o.n.Y, o.length,
87 o.lo.X, o.lo.Y, o.hi.X, o.hi.Y)
88}
89
90// Lengths is the three square roots Prepare takes for a wall and a ball of
91// radius r: the wall's length, then its plus and minus offset lines'.
92func Lengths(s Segment, r float64) (l, lp, lm float64) {
93 var o offset
94 lines(s, r, &o)
95 return o.length, o.plus.B.Sub(o.plus.A).Len(), o.minus.B.Sub(o.minus.A).Len()
96}
97
98// PrepareWith is Prepare with each wall's Lengths given, three per wall in
99// wall order: the same prep, bit for bit, when they are the walls' own. It
100// does not check them; whoever stored them must have. With the wrong count
101// it is Prepare.
102func PrepareWith(f *Field, lens []float64) {
103 if len(lens) != 3*len(f.Walls) {
104 Prepare(f)
105 return
106 }
107 p := make([]float64, 1, 1+stride*len(f.Walls))
108 p[0] = f.Radius
109 var o offset
110 for j := range f.Walls {
111 s := f.Walls[j].Seg
112 linesWith(s, f.Radius, &o, lens[3*j], lens[3*j+1], lens[3*j+2])
113 p = appendPrep(p, s, &o)
114 }
115 f.prep = p
116}
117
118// Prepared is a copy of the field's prep, to compare bit for bit.
119func Prepared(f *Field) []float64 {
120 out := make([]float64, len(f.prep))
121 copy(out, f.prep)
122 return out
123}
124
125// linesWith is lines with its square roots given (Lengths): the same
126// operations in the same order, so the same bits, written out by hand to
127// save lines' calls. Keep the two in step.
128func linesWith(s Segment, r float64, o *offset, l, lp, lm float64) {
129 dx, dy := s.B.X-s.A.X, s.B.Y-s.A.Y
130 o.a, o.length = s.A, l
131 if l == 0 {
132 o.plus, o.minus, o.n, o.pn, o.mn = s, s, Vec2{}, Vec2{}, Vec2{}
133 } else {
134 nx, ny := -dy/l, dx/l
135 q := r / l
136 ex, ey := dx*q, dy*q
137 o.n = Vec2{nx, ny}
138 o.plus = towardWith(s, nx, ny, ex, ey, r, s.A.X+nx, s.A.Y+ny)
139 o.minus = towardWith(s, nx, ny, ex, ey, r, s.A.X-nx, s.A.Y-ny)
140 o.pn = normalWith(o.plus, lp)
141 o.mn = normalWith(o.minus, lm)
142 }
143 lo, hi := o.plus.A, o.plus.A
144 if p := o.plus.B; p.X < lo.X {
145 lo.X = p.X
146 } else if p.X > hi.X {
147 hi.X = p.X
148 }
149 if p := o.plus.B; p.Y < lo.Y {
150 lo.Y = p.Y
151 } else if p.Y > hi.Y {
152 hi.Y = p.Y
153 }
154 if p := o.minus.A; p.X < lo.X {
155 lo.X = p.X
156 } else if p.X > hi.X {
157 hi.X = p.X
158 }
159 if p := o.minus.A; p.Y < lo.Y {
160 lo.Y = p.Y
161 } else if p.Y > hi.Y {
162 hi.Y = p.Y
163 }
164 if p := o.minus.B; p.X < lo.X {
165 lo.X = p.X
166 } else if p.X > hi.X {
167 hi.X = p.X
168 }
169 if p := o.minus.B; p.Y < lo.Y {
170 lo.Y = p.Y
171 } else if p.Y > hi.Y {
172 hi.Y = p.Y
173 }
174 o.lo, o.hi = Vec2{lo.X - boxPad, lo.Y - boxPad}, Vec2{hi.X + boxPad, hi.Y + boxPad}
175}
176
177// towardWith is lines' toward: the offset line on (px, py)'s side.
178func towardWith(s Segment, nx, ny, ex, ey, r, px, py float64) Segment {
179 mx, my := nx, ny
180 if (px-s.A.X)*mx+(py-s.A.Y)*my < 0 {
181 mx, my = mx*-1, my*-1
182 }
183 ox, oy := mx*r, my*r
184 return Segment{A: Vec2{(s.A.X - ex) + ox, (s.A.Y - ey) + oy}, B: Vec2{(s.B.X + ex) + ox, (s.B.Y + ey) + oy}}
185}
186
187// normalWith is Segment.Normal with the length given.
188func normalWith(s Segment, l float64) Vec2 {
189 if l == 0 {
190 return Vec2{}
191 }
192 return Vec2{-(s.B.Y - s.A.Y) / l, (s.B.X - s.A.X) / l}
193}
194
195// offsets is every wall's offset for this shot: from the prep where it still
196// matches the wall, worked out otherwise.
197func (f *Field) offsets() []offset {
198 offs := make([]offset, len(f.Walls))
199 p := f.prep
200 if len(p) == 0 || p[0] != f.Radius {
201 p = nil
202 }
203 for j := range f.Walls {
204 w := &f.Walls[j]
205 o := &offs[j]
206 if k := 1 + j*stride; k+stride <= len(p) && p[k] == w.Seg.A.X && p[k+1] == w.Seg.A.Y && p[k+2] == w.Seg.B.X && p[k+3] == w.Seg.B.Y {
207 o.plus = Segment{Vec2{p[k+4], p[k+5]}, Vec2{p[k+6], p[k+7]}}
208 o.minus = Segment{Vec2{p[k+8], p[k+9]}, Vec2{p[k+10], p[k+11]}}
209 o.pn, o.mn, o.n = Vec2{p[k+12], p[k+13]}, Vec2{p[k+14], p[k+15]}, Vec2{p[k+16], p[k+17]}
210 o.a, o.length = w.Seg.A, p[k+18]
211 o.lo, o.hi = Vec2{p[k+19], p[k+20]}, Vec2{p[k+21], p[k+22]}
212 } else {
213 lines(w.Seg, f.Radius, o)
214 }
215 o.bounce = bounceOf(w.Bounce, f.Bounce, w.Skin)
216 o.every, o.on, o.phase = w.Every, w.On, w.Phase
217 }
218 return offs
219}
220
221// timedBars is where each timed bar starts in f.Walls: four timed walls in a
222// row, one timing, closing on themselves (build.Timed(build.Bar(…))).
223func (f *Field) timedBars() []int {
224 var out []int
225 ws := f.Walls
226 for j := 0; j+3 < len(ws); j++ {
227 a := &ws[j]
228 if a.Every <= 0 {
229 continue
230 }
231 closed := true
232 for k := 0; k < 4; k++ {
233 w, next := &ws[j+k], &ws[j+(k+1)%4]
234 if w.Every != a.Every || w.On != a.On || w.Phase != a.Phase || w.Seg.B != next.Seg.A {
235 closed = false
236 break
237 }
238 }
239 if closed {
240 out = append(out, j)
241 j += 3
242 }
243 }
244 return out
245}
246
247// UnstickIn moves a ball of radius r out of pieces that appeared on top of
248// it. walls are read in bars of four (build.Bar): a ball inside one leaves
249// through the nearest side it can; one closer than r to a bar or a post is
250// pushed off it. No push crosses an untimed wall of stays: out of a bar the
251// ball tries the next side, else it stays; any other such push is not made.
252func UnstickIn(ball Vec2, walls []Wall, posts []Post, r float64, stays []Wall) Vec2 {
253 for i := 0; i+3 < len(walls); i += 4 {
254 q := walls[i : i+4]
255 c := q[0].Seg.A.Add(q[1].Seg.A).Add(q[2].Seg.A).Add(q[3].Seg.A).Scale(0.25)
256 inside := true
257 for _, w := range q {
258 if side(w.Seg, ball) != side(w.Seg, c) {
259 inside = false
260 }
261 }
262 if inside {
263 // nearest side first, along its outward normal
264 var tried [4]bool
265 for range q {
266 k, best, bestD := -1, Vec2{}, math.Inf(1)
267 for j, w := range q {
268 if p := w.Seg.Closest(ball); !tried[j] {
269 if d := p.Sub(ball).Len(); d < bestD {
270 k, best, bestD = j, p, d
271 }
272 }
273 }
274 if k < 0 {
275 break // a NaN ball: no side is nearest
276 }
277 tried[k] = true
278 n := q[k].Seg.Normal()
279 if n.Dot(best.Sub(c)) < 0 {
280 n = n.Scale(-1)
281 }
282 if to := best.Add(n.Scale(r + unstickGap)); !crossesAny(stays, ball, to) {
283 ball = to
284 break
285 }
286 }
287 continue
288 }
289 best, bestD := Vec2{}, math.Inf(1)
290 for _, w := range q {
291 p := w.Seg.Closest(ball)
292 if d := p.Sub(ball).Len(); d < bestD {
293 best, bestD = p, d
294 }
295 }
296 if bestD < r {
297 out := ball.Sub(best)
298 if l := out.Len(); l > 0 {
299 if to := best.Add(out.Scale((r + unstickGap) / l)); !crossesAny(stays, ball, to) {
300 ball = to
301 }
302 }
303 }
304 }
305 for _, p := range posts {
306 d := ball.Sub(p.C)
307 if l := d.Len(); l < p.R+r {
308 if l == 0 {
309 d, l = Vec2{X: 1}, 1
310 }
311 if to := p.C.Add(d.Scale((p.R + r + unstickGap) / l)); !crossesAny(stays, ball, to) {
312 ball = to
313 }
314 }
315 }
316 return ball
317}
318
319// crossesAny reports whether the move a->b crosses one of the untimed walls.
320func crossesAny(walls []Wall, a, b Vec2) bool {
321 for j := range walls {
322 if walls[j].Every <= 0 && walls[j].Seg.Crosses(a, b) {
323 return true
324 }
325 }
326 return false
327}
328
329func side(s Segment, p Vec2) bool {
330 return s.B.Sub(s.A).X*(p.Y-s.A.Y)-s.B.Sub(s.A).Y*(p.X-s.A.X) > 0
331}
332
333// Closest is the point of the segment nearest p.
334func (s Segment) Closest(p Vec2) Vec2 {
335 d := s.B.Sub(s.A)
336 l := d.Dot(d)
337 if l == 0 {
338 return s.A
339 }
340 t := p.Sub(s.A).Dot(d) / l
341 if t < 0 {
342 t = 0
343 } else if t > 1 {
344 t = 1
345 }
346 return s.A.Add(d.Scale(t))
347}
