course.gno
18.89 Kb · 575 lines
1// Package course is what golf and a hole agree on: a hole as data (Simple,
2// GG1), its weather, and how a stroke is launched and drops.
3package course
4
5import (
6 "math"
7 "strconv"
8
9 "gno.land/p/nym-alexiscolin000/gnogolf/physics"
10)
11
12// BoardW and BoardH are the board author.Fit gives a hole declared without W
13// and H, in board units (nothing deployed reads them: Decode holds W and H to
14// 1..MaxBoard).
15const BoardW, BoardH = 32, 16
16
17// WearW and WearH are the wear grid, stretched over any board: 128 counters.
18const WearW, WearH = 16, 8
19
20// MaxBoard is the longest side a board may have: it bounds the text board
21// and the flood a client runs.
22const MaxBoard = 96
23
24// WearIndexOn maps a position on a w x h board to its wear cell, clamped.
25func WearIndexOn(p physics.Vec2, w, h int) int {
26 x := int(p.X * WearW / float64(w))
27 y := int(p.Y * WearH / float64(h))
28 if x < 0 {
29 x = 0
30 }
31 if x >= WearW {
32 x = WearW - 1
33 }
34 if y < 0 {
35 y = 0
36 }
37 if y >= WearH {
38 y = WearH - 1
39 }
40 return y*WearW + x
41}
42
43// Pulse is pieces that come and go: present on the strokes where
44// (stroke+Phase) % Every < On, a timed wall's rule (physics.There) applied per
45// stroke. The clock is the stroke number in the player's own round (0 is the
46// first shot), never shared between players: previewing shot N and
47// committing it meet the same course.
48type Pulse struct {
49 Every, On, Phase int
50 Walls []physics.Wall
51 Posts []physics.Post
52 Zones []physics.Zone
53}
54
55// The weather kinds. Each but Clear is also the skin of its whole-board zones.
56const (
57 Clear = "" // Clear is no weather at all
58 Wind = "wind" // Wind is a Slope: a steady push, Vec per substep
59 Rain = "rain" // Rain is a Surface a little quicker than dry grass
60 Fog = "fog" // Fog is a Surface of scale 1: it only hides the far end
61 Storm = "storm" // Storm is rain and wind in gusts, and lightning to look at
62 Snow = "snow" // Snow is a Surface a little slower
63)
64
65// chance is one kind of weather in a climate, out of 100.
66type chance struct {
67 percent int
68 kind string
69}
70
71// climates is each world's chance of each kind, out of 100; a world not
72// listed has the garden's. Unexported so nothing can change it.
73var climates = map[string][]chance{
74 "garden": {{55, Clear}, {20, Wind}, {15, Rain}, {10, Fog}},
75 "island": {{50, Clear}, {25, Wind}, {15, Rain}, {10, Storm}},
76 "town": {{50, Clear}, {20, Rain}, {15, Fog}, {15, Wind}},
77 "mountain": {{40, Clear}, {25, Snow}, {20, Wind}, {15, Fog}},
78}
79
80// The weather's strengths.
81const (
82 // WindMin is the weakest wind, per substep.
83 WindMin = 0.08
84 // WindMax is the strongest wind, per substep.
85 WindMax = 0.15
86 // RainScale is how much quicker the green is in the rain: a touch, not
87 // ice (much more and every board turns to pinball).
88 RainScale = 1.025
89 // WetIce is how much quicker again the rain makes ice.
90 WetIce = 1.06
91 // SnowScale is how much slower the green is in the snow.
92 SnowScale = 0.9
93)
94
95// Forecast is one hole's weather for one period. Whole-board zones lie under
96// the hole's own; the rest (puddles, wet ice) lie over it.
97type Forecast struct {
98 Period int64
99 Kind string
100 Wind physics.Vec2
101 Zones []physics.Zone
102 // Work is what drawing it cost, in physics.MaxWork's units (about a
103 // thousand gas); golf counts it in a commit's budget.
104 Work int
105}
106
107// hash is 64-bit FNV-1a: small, deterministic, the same on every validator.
108func hash(s string) uint64 {
109 h := uint64(14695981039346656037)
110 for i := 0; i < len(s); i++ {
111 h ^= uint64(s[i])
112 h *= 1099511628211
113 }
114 return h
115}
116
117// ForecastFor is the weather of hole id (in world) for a period: a hash of
118// the two looked up in the world's climate. Nobody picks it.
119func ForecastFor(id, world string, h *Simple, period int64) Forecast {
120 seed := hash(id + "#" + strconv.FormatInt(period, 10))
121 table, ok := climates[world]
122 if !ok {
123 table = climates["garden"]
124 }
125 roll, kind := int(seed%100), Clear
126 for _, c := range table {
127 if roll < c.percent {
128 kind = c.kind
129 break
130 }
131 roll -= c.percent
132 }
133 f := Forecast{Period: period, Kind: kind, Work: forecastWork}
134 f.Wind, f.Zones = weatherFor(kind, h, seed, &f.Work)
135 return f
136}
137
138// rng is a tiny deterministic generator from a seed (Knuth's LCG).
139type rng struct{ s uint64 }
140
141func (r *rng) next() uint64 {
142 r.s = r.s*6364136223846793005 + 1442695040888963407
143 return r.s >> 11
144}
145
146func (r *rng) unit() float64 { return float64(r.next()%1000000) / 1000000 }
147
148// WeatherFor is the wind and zones of one kind of weather on a hole, drawn
149// from seed: the wind's side and strength, where the rain leaves its puddles.
150func WeatherFor(kind string, h *Simple, seed uint64) (physics.Vec2, []physics.Zone) {
151 var work int
152 return weatherFor(kind, h, seed, &work)
153}
154
155// weatherFor is WeatherFor, adding what it cost to *work (see wet).
156func weatherFor(kind string, h *Simple, seed uint64, work *int) (physics.Vec2, []physics.Zone) {
157 W, H := float64(h.W), float64(h.H)
158 all := func(k physics.ZoneKind, skin string, scale float64, vec physics.Vec2) physics.Zone {
159 // the wind is air, and never speeds the ball up
160 air := k == physics.Slope
161 return physics.Zone{Kind: k, Min: physics.V(0, 0), Max: physics.V(W, H), Scale: scale, Vec: vec, Skin: skin, Air: air, Capped: air}
162 }
163 r := &rng{s: seed}
164 blow := func() physics.Vec2 {
165 s := WindMin + r.unit()*(WindMax-WindMin)
166 if h.Shelter > 0 && s > h.Shelter {
167 s = h.Shelter
168 }
169 return physics.FromPolar(r.unit()*2*math.Pi, s)
170 }
171 switch kind {
172 case Wind:
173 v := blow()
174 return v, []physics.Zone{all(physics.Slope, Wind, 0, v)}
175 case Rain:
176 return physics.Vec2{}, wet(h, r, []physics.Zone{all(physics.Surface, Rain, RainScale, physics.Vec2{})}, work)
177 case Storm:
178 // rain, and the wind in two alternating gusts
179 *work += stormWork
180 v := blow()
181 a, s := math.Atan2(v.Y, v.X), v.Len()
182 g1, g2 := all(physics.Slope, Wind, 0, physics.FromPolar(a+gustTurn, s)), all(physics.Slope, Wind, 0, physics.FromPolar(a-gustTurn, s))
183 g1.Every, g1.On, g1.Phase = gustEvery, gustEvery/2, 0
184 g2.Every, g2.On, g2.Phase = gustEvery, gustEvery/2, gustEvery/2
185 zs := []physics.Zone{all(physics.Surface, Storm, 1, physics.Vec2{}), all(physics.Surface, Rain, RainScale, physics.Vec2{}), g1, g2}
186 return v, wet(h, r, zs, work)
187 case Fog:
188 return physics.Vec2{}, []physics.Zone{all(physics.Surface, Fog, 1, physics.Vec2{})}
189 case Snow:
190 return physics.Vec2{}, []physics.Zone{all(physics.Surface, Snow, SnowScale, physics.Vec2{})}
191 }
192 return physics.Vec2{}, nil
193}
194
195// A storm's gusts turn gustTurn radians (about 40°) off its wind, one way
196// then the other, each for half of gustEvery substeps.
197const (
198 gustTurn = 0.7
199 gustEvery = 6
200)
201
202// Where rain leaves its puddles: minPuddles plus up to morePuddles-1 more,
203// in at most puddleTries tries; each puddleR plus up to puddleGrow wide,
204// puddleAspect as deep, and puddleScale as quick as the grass, kept
205// puddleGap clear of the one before.
206const (
207 minPuddles = 2
208 morePuddles = 3
209 puddleTries = 60
210 puddleR = 1.1
211 puddleGrow = 0.7
212 puddleAspect = 0.8
213 puddleScale = 0.6
214 puddleGap = 0.5
215)
216
217// The work of a forecast, in physics.MaxWork's units, measured on GnoVM gas:
218// any forecast, a storm's gusts, a puddle try, and in it each post, zone,
219// polygon edge and fixed wall dryLand tests, and each zone wet checks for ice.
220const (
221 forecastWork = 3000 // drawing any forecast, before the rain's tries
222 stormWork = 5000 // a storm's gusts, on top
223 tryWork = 35
224 dryPostWork = 22
225 dryZoneWork = 20
226 dryEdgeWork = 16
227 dryWallWork = 100
228 iceWork = 5
229)
230
231// WorstForecastWork bounds the Work of h's forecast in any period and world:
232// a storm's, whose puddle tries all fail, each after dryLand has tested every
233// piece (a try that fails sooner costs less, and one that places a puddle
234// ends them sooner). Golf refuses a hole whose worst forecast leaves a commit
235// no room for its heaviest shot.
236func WorstForecastWork(h *Simple) int {
237 f := h.Field()
238 try := tryWork + dryPostWork*len(f.Posts)
239 for _, z := range f.Zones {
240 try += dryZoneTest(z)
241 }
242 for _, wl := range f.Walls {
243 if wl.Every <= 0 {
244 try += dryWallWork
245 }
246 }
247 return forecastWork + stormWork + iceWork*len(f.Zones) + puddleTries*try
248}
249
250// dryZoneTest is the work of dryLand's test of one zone: its polygon's edges
251// too for any zone but plain ground (Contains, at its dearest).
252func dryZoneTest(z physics.Zone) int {
253 if (z.Kind != physics.Surface && z.Kind != physics.Slope) || (z.Kind == physics.Surface && z.Skin != "") {
254 return dryZoneWork + dryEdgeWork*len(z.Poly)
255 }
256 return dryZoneWork
257}
258
259// wet adds what rain leaves on a hole: its ice quicker still, and two to four
260// puddles on the lane, clear of the kerb, the pieces, the tee and the cup.
261// What it costs goes in *work.
262func wet(h *Simple, r *rng, zs []physics.Zone, work *int) []physics.Zone {
263 f := h.Field()
264 *work += iceWork * len(f.Zones)
265 for _, z := range f.Zones {
266 if z.Kind == physics.Surface && z.Skin == "ice" {
267 z.Scale *= WetIce
268 zs = append(zs, z)
269 }
270 }
271 want, placed := minPuddles+int(r.next()%morePuddles), []physics.Zone{}
272 for try := 0; try < puddleTries && len(placed) < want; try++ {
273 c := physics.V(r.unit()*float64(h.W), r.unit()*float64(h.H))
274 rad := puddleR + r.unit()*puddleGrow
275 *work += tryWork
276 if !dryLand(h, c, rad, work) {
277 continue
278 }
279 clash := false
280 for _, p := range placed {
281 if p.Min.Add(p.Max).Scale(0.5).Sub(c).LenCmp(p.Max.X-p.Min.X+puddleGap) < 0 {
282 clash = true
283 }
284 }
285 if clash {
286 continue
287 }
288 placed = append(placed, physics.Zone{Kind: physics.Surface, Min: c.Sub(physics.V(rad, rad*puddleAspect)), Max: c.Add(physics.V(rad, rad*puddleAspect)), Scale: puddleScale, Round: true, Skin: "puddle"})
289 }
290 return append(zs, placed...)
291}
292
293// dryLand says whether a puddle of radius rad can lie at c: inside the lane's
294// outline (even-odd over the fixed walls, a ray to a far point at a slant no
295// grid wall lies along), off any zone but plain ground, dryGap from any piece
296// and dryTee from tee and cup. Cheap tests first, no square roots: on a lane
297// hole every try fails.
298func dryLand(h *Simple, c physics.Vec2, rad float64, work *int) bool {
299 f := h.Field()
300 if c.Sub(h.Start()).LenCmp(rad+dryTee) < 0 || c.Sub(h.Cup()).LenCmp(rad+dryTee) < 0 {
301 return false
302 }
303 for _, p := range f.Posts {
304 *work += dryPostWork
305 if p.C.Sub(c).LenCmp(p.R+rad+dryGap) < 0 {
306 return false
307 }
308 }
309 for _, z := range f.Zones {
310 *work += dryZoneTest(z)
311 if z.Kind != physics.Surface && z.Kind != physics.Slope && z.Contains(c) {
312 return false
313 }
314 if z.Kind == physics.Surface && z.Skin != "" && z.Contains(c) {
315 return false // not on the sand or the ice: a puddle is on the green
316 }
317 }
318 far, in := c.Add(physics.V(farX, farY)), false
319 for _, wl := range f.Walls {
320 if wl.Every > 0 {
321 continue
322 }
323 *work += dryWallWork
324 if c.Sub(wl.Seg.Closest(c)).LenCmp(rad+dryGap) < 0 {
325 return false
326 }
327 if wl.Seg.Crosses(c, far) {
328 in = !in
329 }
330 }
331 return in
332}
333
334const (
335 dryTee = 2
336 dryGap = 0.3
337 farX, farY = 1e4, 37
338)
339
340// WithWeather lays weather over a field: the sky's whole-board zones go under
341// its own (the sand stays sand in the rain), puddles and wet ice over them.
342// It may return f itself: do not mutate what it returns.
343func WithWeather(f *physics.Field, weather []physics.Zone) *physics.Field {
344 if len(weather) == 0 {
345 return f
346 }
347 under, over := []physics.Zone{}, []physics.Zone{}
348 for _, z := range weather {
349 switch z.Skin {
350 case Wind, Rain, Fog, Storm, Snow:
351 under = append(under, z)
352 default:
353 over = append(over, z)
354 }
355 }
356 g := *f
357 g.Zones = append(append(append(make([]physics.Zone, 0, len(f.Zones)+len(weather)), under...), f.Zones...), over...)
358 return &g
359}
360
361// WithZones is the field with zones put first (a puddle over the sand is the
362// puddle). It may return f itself: do not mutate what it returns.
363func WithZones(f *physics.Field, zones []physics.Zone) *physics.Field {
364 if len(zones) == 0 {
365 return f
366 }
367 g := *f
368 g.Zones = append(append(make([]physics.Zone, 0, len(f.Zones)+len(zones)), zones...), f.Zones...)
369 return &g
370}
371
372// WithExtras is the field plus one stroke's pieces, the hole's own left as
373// is. It may return f itself: do not mutate what it returns.
374func WithExtras(f *physics.Field, walls []physics.Wall, posts []physics.Post) *physics.Field {
375 if len(walls) == 0 && len(posts) == 0 {
376 return f
377 }
378 g := *f
379 g.Walls = append(append(make([]physics.Wall, 0, len(f.Walls)+len(walls)), f.Walls...), walls...)
380 g.Posts = append(append(make([]physics.Post, 0, len(f.Posts)+len(posts)), f.Posts...), posts...)
381 return &g
382}
383
384// Simple is a hole: its geometry, what Decode gives golf. Fields and methods
385// pair up (Strokes/Par, Tee/Start, Pin/Cup, Course/Field) because a field and
386// a method cannot share a name.
387type Simple struct {
388 W, H int // the board, 1 to MaxBoard a side (Decode holds data to it, author.Fit sets it)
389 Title string
390 Strokes int // par: the strokes a good round takes (0 means 3)
391 Tee, Pin physics.Vec2
392 Course *physics.Field
393 Pulses []Pulse // pieces that come and go with the stroke number
394 Substeps int
395 CupRadius float64
396 // World is the hole's world (1 to MaxWorld letters a-z, as Decode holds
397 // it); Order is its place there, 0 to MaxOrder (a course hole 1 or more).
398 World string
399 Order float64
400 // Shelter caps the wind the hole is played in (0: the world's own).
401 Shelter float64
402}
403
404// ExtraZones is the zones the hole's pulses lay down at a stroke.
405func (h *Simple) ExtraZones(stroke int) []physics.Zone {
406 var zs []physics.Zone
407 for _, p := range h.Pulses {
408 if physics.There(stroke, p.Every, p.On, p.Phase) {
409 zs = append(zs, p.Zones...)
410 }
411 }
412 return zs
413}
414
415// Varies says whether the hole has pulses: pieces that come and go.
416func (h *Simple) Varies() bool { return len(h.Pulses) > 0 }
417
418// Extras is the walls and posts the hole's pulses add at a stroke.
419func (h *Simple) Extras(stroke int) ([]physics.Wall, []physics.Post) {
420 var ws []physics.Wall
421 var ps []physics.Post
422 for _, p := range h.Pulses {
423 if physics.There(stroke, p.Every, p.On, p.Phase) {
424 ws = append(ws, p.Walls...)
425 ps = append(ps, p.Posts...)
426 }
427 }
428 return ws, ps
429}
430
431// PreviewWith plays a stroke of a round in some weather, read-only, the timed
432// pieces starting at tick. A pulse piece that came back on the ball pushes it
433// out, never across the hole's own walls. A ball left where the next stroke
434// brings a hazard back returns to where this stroke started, as under a timed
435// hazard (else that hazard would cost a stroke for nothing).
436func (h *Simple) PreviewWith(ball physics.Vec2, angle, power float64, stroke, tick int, weather []physics.Zone) (physics.Shot, bool) {
437 ws, ps := h.Extras(stroke)
438 ball = physics.UnstickIn(ball, ws, ps, h.Course.Radius, h.Course.Walls)
439 f := WithZones(WithExtras(h.Course, ws, ps), h.ExtraZones(stroke))
440 f = physics.WithTick(WithWeather(f, weather), tick)
441 shot, holed := Sink(f.Step(ball, Launch(angle, power), h.Substeps), h.Pin, h.CupRadius, h.Course.Radius)
442 if !holed && len(shot.Path) > 0 {
443 for _, z := range h.ExtraZones(stroke + 1) {
444 if z.Kind == physics.Hazard && z.Contains(shot.Rest()) {
445 shot.Path = append(shot.Path, ball)
446 shot.Air = append(shot.Air, false)
447 shot.Cause = append(shot.Cause, '-')
448 break
449 }
450 }
451 }
452 return shot, holed
453}
454
455// Par is the strokes a good round takes: Strokes, 3 unless it says 1 to 19.
456func (h *Simple) Par() int {
457 if h.Strokes > 0 && h.Strokes < 20 {
458 return h.Strokes
459 }
460 return 3
461}
462
463// Start is the tee.
464func (h *Simple) Start() physics.Vec2 { return h.Tee }
465
466// Cup is where the cup is.
467func (h *Simple) Cup() physics.Vec2 { return h.Pin }
468
469// Field is the course as the physics sees it.
470func (h *Simple) Field() *physics.Field { return h.Course }
471
472// Kick turns a stroke's power (0 to 10) into the ball's speed per substep,
473// Kick·p^(3/4), so the roll (v²/2a) grows as p^(3/2). A full stroke rolls 44
474// on the usual green, a board's length. Calibrated to keep every hole's par.
475const Kick = 0.79
476
477// Launch is the ball's starting velocity for a stroke. Every hole should use
478// it, so that the same pull means the same shot on every course.
479func Launch(angle, power float64) physics.Vec2 {
480 if !(power > 0) {
481 return physics.Vec2{}
482 }
483 return physics.FromPolar(angle, Kick*math.Sqrt(power*math.Sqrt(power)))
484}
485
486// minDrop is the least a ball falls to drop: a smaller ball drops as one of
487// 0.5, else a point ball would drop into any cup at any speed.
488const minDrop = 0.5
489
490// Capture is the fastest a ball of radius ball crossing a cup of radius cup,
491// off its centre by off, can go and still drop, in board units per substep;
492// 0 when it cannot drop at all. Holmes's criterion (Am. J. Phys. 59, 1991):
493// (2·sqrt(R² − b²) − r) · sqrt(G / 2r).
494func Capture(cup, ball, off float64) float64 {
495 c := cup*cup - off*off
496 if !(c > 0) {
497 return 0
498 }
499 if !(ball >= minDrop) {
500 ball = minDrop
501 }
502 chord := 2*math.Sqrt(c) - ball
503 if !(chord > 0) {
504 return 0
505 }
506 return chord * math.Sqrt(physics.G/(2*ball))
507}
508
509// jumpStep is how much longer than the fastest drop a step must be for the
510// one after it to be the rest of a jump, not a slow ball.
511const jumpStep = 1.5
512
513// Sink decides whether a shot ends in the cup: it stops within radius of the
514// pin, or crosses the cup no faster than Capture allows a ball of radius
515// ball. When it drops, the path is cut there and ends on the pin.
516func Sink(shot physics.Shot, pin physics.Vec2, radius, ball float64) (physics.Shot, bool) {
517 p := shot.Path
518 top := Capture(radius, ball, 0) // over the middle: the fastest drop
519 for i := 0; i+1 < len(p); i++ {
520 a, d := p[i], p[i+1].Sub(p[i])
521 if d.LenCmp(top) > 0 {
522 continue // too fast, or a tunnel jump
523 }
524 if airborne(shot, i) || airborne(shot, i+1) {
525 continue // flying over the cup is not dropping into it
526 }
527 // a short step right after a long one is not a slow ball: it is the
528 // rest of a substep after a tunnel exit or a bounce
529 if i > 0 && p[i].Sub(p[i-1]).LenCmp(top*jumpStep) > 0 {
530 continue
531 }
532 // a step whose box is more than radius from the pin cannot drop
533 if b, r := p[i+1], radius+1e-9; (pin.X < a.X-r && pin.X < b.X-r) || (pin.X > a.X+r && pin.X > b.X+r) ||
534 (pin.Y < a.Y-r && pin.Y < b.Y-r) || (pin.Y > a.Y+r && pin.Y > b.Y+r) {
535 continue
536 }
537 l := d.Len()
538 t := 0.0
539 if l > 0 {
540 t = pin.Sub(a).Dot(d) / (l * l)
541 if t < 0 {
542 t = 0
543 } else if t > 1 {
544 t = 1
545 }
546 }
547 at := a.Add(d.Scale(t))
548 // the step's nearest point to the pin is where it crosses the cup
549 if off := at.Sub(pin).Len(); off <= radius && l <= Capture(radius, ball, off) {
550 cut := make([]physics.Vec2, 0, i+3)
551 cut = append(cut, p[:i+1]...)
552 shot.Path = append(cut, at, pin)
553 if len(shot.Air) > i {
554 shot.Air = append(append(make([]bool, 0, i+3), shot.Air[:i+1]...), false, false)
555 }
556 if len(shot.Cause) > i {
557 shot.Cause = append(append(make([]byte, 0, i+3), shot.Cause[:i+1]...), '-', '-')
558 }
559 return shot, true
560 }
561 }
562 if shot.Rest().Sub(pin).LenCmp(radius) <= 0 {
563 shot.Path = append(shot.Path, pin)
564 if shot.Air != nil {
565 shot.Air = append(shot.Air, false)
566 }
567 if shot.Cause != nil {
568 shot.Cause = append(shot.Cause, '-')
569 }
570 return shot, true
571 }
572 return shot, false
573}
574
575func airborne(s physics.Shot, i int) bool { return i < len(s.Air) && s.Air[i] }
