-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrandom.go
More file actions
374 lines (325 loc) · 9.66 KB
/
Copy pathrandom.go
File metadata and controls
374 lines (325 loc) · 9.66 KB
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
package gaul
import (
"math"
"time"
"github.com/peterhellberg/gfx"
)
const (
defaultScale = 0.001
defaultOctaves = 1
defaultPersistence = 0.9
defaultLacunarity = 2.0
)
// Rng is a random number generator with a system PRNG and simplex noise
type Rng struct {
Simplex *gfx.SimplexNoise
seed int64
Prng LFSRLarge
octaves int
persistence float64
lacunarity float64
xscale float64
yscale float64
zscale float64
wscale float64
xoffset float64
yoffset float64
zoffset float64
woffset float64
}
// NewRng returns a PRNG with a system and Noise generator
func NewRng(i int64) Rng {
return Rng{
seed: i,
Prng: NewLFSRLargeWithSeed(uint64(i)),
Simplex: gfx.NewSimplexNoise(i),
octaves: defaultOctaves,
persistence: defaultPersistence,
lacunarity: defaultLacunarity,
xscale: defaultScale,
yscale: defaultScale,
zscale: defaultScale,
wscale: defaultScale,
xoffset: 0,
yoffset: 0,
zoffset: 0,
woffset: 0,
}
}
// Seed returns the seed the generator was created or reset with.
func (r *Rng) Seed() int64 {
return r.seed
}
// SetSeed resets the generator to the given seed. A generator reset with
// SetSeed(s) produces the same stream as a fresh NewRng(s).
func (r *Rng) SetSeed(seed int64) {
r.seed = seed
r.Prng = NewLFSRLargeWithSeed(uint64(seed))
r.Simplex = gfx.NewSimplexNoise(seed)
}
// Float64 returns a uniformly distributed value in [0, 1) from the seeded
// PRNG.
func (r *Rng) Float64() float64 {
return r.Prng.Float64()
}
// Gaussian returns a normally distributed value with the given mean and
// standard deviation, drawn from the seeded PRNG so that results are
// reproducible for a given seed.
func (r *Rng) Gaussian(mean float64, stdev float64) float64 {
// Box-Muller transform. u1 must be strictly positive for the log.
u1 := r.Prng.Float64()
for u1 <= 0 {
u1 = r.Prng.Float64()
}
u2 := r.Prng.Float64()
return mean + stdev*math.Sqrt(-2*math.Log(u1))*math.Cos(Tau*u2)
}
// The Noise scale functions scale the position values passed into the
// Noise PRNG. Typically for screen coordinates scale values in the
// range of 0.001 to 0.01 produce visually appealing Noise
// SetNoiseScaleX scales the x position in Noise calculations
func (r *Rng) SetNoiseScaleX(scale float64) {
r.xscale = scale
}
// SetNoiseScaleY scales the y position in Noise calculations
func (r *Rng) SetNoiseScaleY(scale float64) {
r.yscale = scale
}
// SetNoiseScaleZ scales the z position in Noise calculations
func (r *Rng) SetNoiseScaleZ(scale float64) {
r.zscale = scale
}
// SetNoiseScaleW scales the w position in Noise calculations
func (r *Rng) SetNoiseScaleW(scale float64) {
r.wscale = scale
}
// The Noise offset functions simple increment/decrement the
// position values before scaling
// SetNoiseOffsetX offsets the x position in Noise calculations
func (r *Rng) SetNoiseOffsetX(offset float64) {
r.xoffset = offset
}
// SetNoiseOffsetY offsets the y position in Noise calculations
func (r *Rng) SetNoiseOffsetY(offset float64) {
r.yoffset = offset
}
// SetNoiseOffsetZ offsets the z position in Noise calculations
func (r *Rng) SetNoiseOffsetZ(offset float64) {
r.zoffset = offset
}
// SetNoiseOffsetW offsets the w position in Noise calculations
func (r *Rng) SetNoiseOffsetW(offset float64) {
r.woffset = offset
}
// SetNoiseOctaves sets the number of steps when calculating fractal Noise
func (r *Rng) SetNoiseOctaves(i int) {
r.octaves = i
}
// SetNoisePersistence sets how amplitude scales with octaves
func (r *Rng) SetNoisePersistence(p float64) {
r.persistence = p
}
// SetNoiseLacunarity sets how frequency scales with octaves
func (r *Rng) SetNoiseLacunarity(l float64) {
r.lacunarity = l
}
// Noise1D 1D Noise values in the range of [-1, 1]
func (r *Rng) Noise1D(x float64) float64 {
return r.calcNoise1(x)
}
// Noise2D generates 2D Noise values in the range of [-1, 1]
func (r *Rng) Noise2D(x float64, y float64) float64 {
return r.calcNoise2(x, y)
}
// Noise3D generates 3D Noise values in the range of [0, 1]
func (r *Rng) Noise3D(x float64, y float64, z float64) float64 {
return r.calcNoise3(x, y, z)
}
// Noise4D generates 4D Noise values in the range of [-1, 1]
func (r *Rng) Noise4D(x float64, y float64, z float64, w float64) float64 {
return r.calcNoise4(x, y, z, w)
}
// ShufflePoints randomly permutes a slice of points in place using the seeded
// PRNG, so the permutation is reproducible for a given seed.
func (r *Rng) ShufflePoints(p []Point) {
// Fisher-Yates, drawing an unbiased index from the seeded generator.
for i := len(p) - 1; i > 0; i-- {
j := int(r.Prng.Uint64n(uint64(i + 1)))
p[i], p[j] = p[j], p[i]
}
}
// UniformRandomPoints generates a list of points whose coordinates
// follow a uniform random distribution within a rectangle
func (r *Rng) UniformRandomPoints(num int, rect Rect) []Point {
points := make([]Point, num)
for i := 0; i < num; i++ {
x := rect.X + r.Prng.Float64()*rect.W
y := rect.Y + r.Prng.Float64()*rect.H
points[i] = Point{X: x, Y: y}
}
return points
}
func (r *Rng) NoisyRandomPoints(num int, threshold float64, rect Rect) []Point {
points := make([]Point, 0, num)
maxtries := 10 * num
i := 0
for len(points) < num && i < maxtries {
x := rect.X + r.Prng.Float64()*rect.W
y := rect.Y + r.Prng.Float64()*rect.H
noise := r.Noise2D(x, y)
if noise >= threshold {
points = append(points, Point{X: x, Y: y})
}
i++
}
return points
}
func (r *Rng) calcNoise1(x float64) float64 {
return r.calcNoise(1, x, 0, 0, 0)
}
func (r *Rng) calcNoise2(x, y float64) float64 {
return r.calcNoise(2, x, y, 0, 0)
}
func (r *Rng) calcNoise3(x, y, z float64) float64 {
return r.calcNoise(3, x, y, z, 0)
}
func (r *Rng) calcNoise4(x, y, z, w float64) float64 {
return r.calcNoise(4, x, y, z, w)
}
func (r *Rng) calcNoise(dim int, x, y, z, w float64) float64 {
totalNoise := 0.0
totalAmp := 0.0
amp := 1.0
freq := 1.0
for i := 0; i < r.octaves; i++ {
var sample float64
switch dim {
case 1:
sample = r.Simplex.Noise2D(
(x+r.xoffset)*r.xscale*freq,
0,
)
case 2:
sample = r.Simplex.Noise2D(
(x+r.xoffset)*r.xscale*freq,
(y+r.yoffset)*r.yscale*freq,
)
case 3:
sample = r.Simplex.Noise3D(
(x+r.xoffset)*r.xscale*freq,
(y+r.yoffset)*r.yscale*freq,
(z+r.zoffset)*r.zscale*freq,
)
case 4:
sample = r.Simplex.Noise4D(
(x+r.xoffset)*r.xscale*freq,
(y+r.yoffset)*r.yscale*freq,
(z+r.zoffset)*r.zscale*freq,
(w+r.woffset)*r.wscale*freq,
)
}
// Each octave contributes at its own amplitude; without this factor
// persistence has no effect and every octave weighs the same.
totalNoise += amp * sample
totalAmp += amp
amp *= r.persistence
freq *= r.lacunarity
}
if totalAmp == 0 {
return 0
}
return totalNoise / totalAmp
}
type LFSRSmall struct {
state uint16
}
// NewLFSRSmallWithSeed returns a 16-bit LFSR seeded with the given value. A
// zero seed would lock the register at zero, so it is replaced with a
// non-zero constant.
func NewLFSRSmallWithSeed(seed uint16) LFSRSmall {
if seed == 0 {
seed = 0xACE1
}
return LFSRSmall{state: seed}
}
func NewLFSRSmall() LFSRSmall {
return LFSRSmall{state: uint16(time.Now().UnixNano())}
}
func (l *LFSRSmall) Next() uint16 {
b := ((l.state >> 0) ^ (l.state >> 2) ^ (l.state >> 3) ^ (l.state >> 5)) & 1
l.state = (l.state >> 1) | (b << 15)
return l.state
}
type LFSRMedium struct {
state uint32
}
// NewLFSRMediumWithSeed returns a 32-bit xorshift generator seeded with the
// given value. Xorshift has no escape from an all-zero state, so a zero seed
// is replaced with a fixed non-zero constant.
func NewLFSRMediumWithSeed(seed uint32) LFSRMedium {
if seed == 0 {
seed = 0x9E3779B9
}
return LFSRMedium{state: seed}
}
func NewLFSRMedium() LFSRMedium {
return LFSRMedium{state: uint32(time.Now().UnixNano())}
}
func (l *LFSRMedium) Next() uint32 {
l.state ^= l.state << 13
l.state ^= l.state >> 17
l.state ^= l.state << 5
return l.state
}
// LFSRLarge is a 64-bit Xorshift PRNG
// Benchmarks show this is faster than LFSRMedium and LFSRSmall, so you might as well use this one.
// Benchmarks also show this is 6-7x faster than the standard math/rand PRNG
type LFSRLarge struct {
state uint64
}
// NewLFSRLargeWithSeed returns a 64-bit xorshift generator seeded with the
// given value. Xorshift has no escape from an all-zero state, so a zero seed
// is replaced with a fixed non-zero constant.
func NewLFSRLargeWithSeed(seed uint64) LFSRLarge {
if seed == 0 {
seed = 0x9E3779B97F4A7C15
}
return LFSRLarge{state: seed}
}
func NewLFSRLarge() LFSRLarge {
return LFSRLarge{state: uint64(time.Now().UnixNano())}
}
func (l *LFSRLarge) Next() uint64 {
l.state ^= l.state << 13
l.state ^= l.state >> 7
l.state ^= l.state << 17
return l.state
}
// Float64 returns a uniformly distributed value in [0, 1). The top 53 bits
// are used, which is the most a float64 can represent exactly; dividing the
// full 64-bit word by 2^64-1 would instead make 1.0 attainable.
func (l *LFSRLarge) Float64() float64 {
return float64(l.Next()>>11) / (1 << 53)
}
// Uint64n returns a uniformly distributed value in [0, n). It panics if n is
// zero. A plain Next()%n would favor small results whenever n does not divide
// 2^64, so the tail of the range that causes the skew is rejected.
func (l *LFSRLarge) Uint64n(n uint64) uint64 {
if n == 0 {
panic("Uint64n: n must be positive")
}
k := (^uint64(0)%n + 1) % n // 2^64 mod n
if k == 0 {
// n divides 2^64 exactly; every value maps evenly.
return l.Next() % n
}
threshold := ^uint64(0) - k + 1 // 2^64 - k, the first biased value
v := l.Next()
for v >= threshold {
v = l.Next()
}
return v % n
}
func (l *LFSRLarge) Uint64() uint64 {
return l.Next()
}