maze.gno
13.10 Kb · 502 lines
1// This package demonstrate the capability of gno to build dynamic svg image
2// based on different query parameters.
3// Raycasting implementation as been heavily inspired by this project: https://github.com/AZHenley/raycasting
4
5package gnomaze
6
7import (
8 "chain/runtime"
9 "encoding/base64"
10 "hash/adler32"
11 "math"
12 "math/rand"
13 "net/url"
14 "strconv"
15 "strings"
16 "time"
17
18 "gno.land/p/moul/txlink"
19)
20
21const baseLevel = 7
22
23// Constants for cell dimensions
24const (
25 cellSize = 1.0
26 halfCell = cellSize / 2
27)
28
29type CellKind int
30
31const (
32 CellKindEmpty = iota
33 CellKindWall
34)
35
36var (
37 level int = 1
38 salt int64
39 maze [][]int
40 endPos, startPos Position
41)
42
43func init() {
44 // Generate the map
45 seed := uint64(runtime.ChainHeight())
46 rng := rand.New(rand.NewPCG(seed, uint64(time.Now().Unix())))
47 generateLevel(rng, level)
48 salt = rng.Int64()
49}
50
51// Position represents the X, Y coordinates in the maze
52type Position struct{ X, Y int }
53
54// Player represents a player with position and viewing angle
55type Player struct {
56 X, Y, Angle, FOV float64
57}
58
59// PlayerState holds the player's grid position and direction
60type PlayerState struct {
61 CellX int // Grid X position
62 CellY int // Grid Y position
63 Direction int // 0-7 (0 = east, 1 = SE, 2 = S, etc.)
64}
65
66// Angle calculates the direction angle in radians
67func (p *PlayerState) Angle() float64 {
68 return float64(p.Direction) * math.Pi / 4
69}
70
71// Position returns the player's exact position in the grid
72func (p *PlayerState) Position() (float64, float64) {
73 return float64(p.CellX) + halfCell, float64(p.CellY) + halfCell
74}
75
76// SumCode returns a hash string based on the player's position
77func (p *PlayerState) SumCode() string {
78 a := adler32.New()
79
80 var width int
81 if len(maze) > 0 {
82 width = len(maze[0])
83 }
84
85 s := strconv.Itoa(p.CellY*width+p.CellX) + "-" + strconv.Itoa(level) + "-" + strconv.FormatInt(salt, 10)
86 a.Write([]byte(s))
87 return strconv.FormatUint(uint64(a.Sum32()), 10)
88}
89
90// Move updates the player's position based on movement deltas
91func (p *PlayerState) Move(dx, dy int) {
92 newX := p.CellX + dx
93 newY := p.CellY + dy
94
95 if newY >= 0 && newY < len(maze) && newX >= 0 && newX < len(maze[0]) {
96 if maze[newY][newX] == 0 {
97 p.CellX = newX
98 p.CellY = newY
99 }
100 }
101}
102
103// Rotate changes the player's direction
104func (p *PlayerState) Rotate(clockwise bool) {
105 if clockwise {
106 p.Direction = (p.Direction + 1) % 8
107 } else {
108 p.Direction = (p.Direction + 7) % 8
109 }
110}
111
112// GenerateNextLevel validates the answer and generates a new level
113func GenerateNextLevel(cur realm, answer string) {
114 seed := uint64(runtime.ChainHeight())
115 rng := rand.New(rand.NewPCG(seed, uint64(time.Now().Unix())))
116
117 endState := PlayerState{CellX: endPos.X, CellY: endPos.Y}
118 hash := endState.SumCode()
119 if hash != answer {
120 panic("invalid answer")
121 }
122
123 // Generate new map
124 level++
125 salt = rng.Int64()
126 generateLevel(rng, level)
127}
128
129// generateLevel creates a new maze for the given level
130func generateLevel(rng *rand.Rand, level int) {
131 if level < 0 {
132 panic("invalid level")
133 }
134
135 size := level + baseLevel
136 maze, startPos, endPos = generateMap(rng, size, size)
137}
138
139// generateMap creates a random maze using a depth-first search algorithm.
140func generateMap(rng *rand.Rand, width, height int) ([][]int, Position, Position) {
141 // Initialize the maze grid filled with walls.
142 m := make([][]int, height)
143 for y := range m {
144 m[y] = make([]int, width)
145 for x := range m[y] {
146 m[y][x] = CellKindWall
147 }
148 }
149
150 // Define start position and initialize stack for DFS
151 start := Position{1, 1}
152 stack := []Position{start}
153 m[start.Y][start.X] = CellKindEmpty
154
155 // Initialize distance matrix and track farthest
156 dist := make([][]int, height)
157 for y := range dist {
158 dist[y] = make([]int, width)
159 for x := range dist[y] {
160 dist[y][x] = -1
161 }
162 }
163 dist[start.Y][start.X] = CellKindEmpty
164 maxDist := 0
165 candidates := []Position{start}
166
167 // Possible directions for movement: right, left, down, up
168 directions := []Position{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
169
170 // Generate maze paths using DFS
171 for len(stack) > 0 {
172 current := stack[len(stack)-1]
173 stack = stack[:len(stack)-1]
174
175 var dirCandidates []struct {
176 next, wall Position
177 }
178
179 // Evaluate possible candidates for maze paths
180 for _, d := range directions {
181 nx, ny := current.X+d.X*2, current.Y+d.Y*2
182 wx, wy := current.X+d.X, current.Y+d.Y
183
184 // Check if the candidate position is within bounds and still a wall
185 if nx > 0 && nx < width-1 && ny > 0 && ny < height-1 && m[ny][nx] == 1 {
186 dirCandidates = append(dirCandidates, struct{ next, wall Position }{
187 Position{nx, ny}, Position{wx, wy},
188 })
189 }
190 }
191
192 // If candidates are available, choose one and update the maze
193 if len(dirCandidates) > 0 {
194 chosen := dirCandidates[rng.IntN(len(dirCandidates))]
195 m[chosen.wall.Y][chosen.wall.X] = CellKindEmpty
196 m[chosen.next.Y][chosen.next.X] = CellKindEmpty
197
198 // Update distance for the next cell
199 currentDist := dist[current.Y][current.X]
200 nextDist := currentDist + 2
201 dist[chosen.next.Y][chosen.next.X] = nextDist
202
203 // Update maxDist and candidates
204 if nextDist > maxDist {
205 maxDist = nextDist
206 candidates = []Position{chosen.next}
207 } else if nextDist == maxDist {
208 candidates = append(candidates, chosen.next)
209 }
210
211 stack = append(stack, current, chosen.next)
212 }
213 }
214
215 // Select a random farthest position as the end
216 var end Position
217 if len(candidates) > 0 {
218 end = candidates[rng.IntN(len(candidates))]
219 } else {
220 end = Position{width - 2, height - 2} // Fallback to bottom-right
221 }
222
223 return m, start, end
224}
225
226// ftoa formats a float for SVG attribute values
227func ftoa(f float64) string {
228 return strconv.FormatFloat(f, 'f', 6, 64)
229}
230
231// castRay simulates a ray casting in the maze to find walls
232func castRay(playerX, playerY, rayAngle float64, m [][]int) (distance float64, wallHeight float64, endCellHit bool, endDistance float64) {
233 x, y := playerX, playerY
234 dx, dy := math.Cos(rayAngle), math.Sin(rayAngle)
235 steps := 0
236 endCellHit = false
237 endDistance = 0.0
238
239 for {
240 ix, iy := int(math.Floor(x)), int(math.Floor(y))
241 if ix == endPos.X && iy == endPos.Y {
242 endCellHit = true
243 endDistance = math.Sqrt(math.Pow(x-playerX, 2) + math.Pow(y-playerY, 2))
244 }
245
246 if iy < 0 || iy >= len(m) || ix < 0 || ix >= len(m[0]) || m[iy][ix] != 0 {
247 break
248 }
249
250 x += dx * 0.1
251 y += dy * 0.1
252 steps++
253 if steps > 400 {
254 break
255 }
256 }
257
258 distance = math.Sqrt(math.Pow(x-playerX, 2) + math.Pow(y-playerY, 2))
259 wallHeight = 300.0 / distance
260 return
261}
262
263// GenerateSVG creates an SVG representation of the maze scene
264func GenerateSVG(cur realm, p *PlayerState) string {
265 const (
266 svgWidth, svgHeight = 800, 600
267 offsetX, offsetY = 0.0, 500.0
268 groundLevel = 300
269 rays = 124
270 fov = math.Pi / 4
271 miniMapSize = 100.0
272 visibleCells = 7
273 dirLen = 2.0
274 )
275
276 m := maze
277 playerX, playerY := p.Position()
278 angle := p.Angle()
279
280 sliceWidth := float64(svgWidth) / float64(rays)
281 angleStep := fov / float64(rays)
282
283 var svg strings.Builder
284 svg.WriteString(`<svg width="800" height="600" xmlns="http://www.w3.org/2000/svg">`)
285 svg.WriteString(`<rect x="0" y="0" width="800" height="300" fill="rgb(20,40,20)"/>`)
286 svg.WriteString(`<rect x="0" y="300" width="800" height="300" fill="rgb(40,60,40)"/>`)
287
288 var drawBanana func()
289 for i := 0; i < rays; i++ {
290 rayAngle := angle - fov/2 + float64(i)*angleStep
291 distance, wallHeight, endHit, endDist := castRay(playerX, playerY, rayAngle, m)
292 darkness := 1.0 + distance/4.0
293 colorVal1 := int(180.0 / darkness)
294 colorVal2 := int(32.0 / darkness)
295 yPos := groundLevel - wallHeight/2
296
297 svg.WriteString(`<rect x="` + ftoa(float64(i)*sliceWidth) +
298 `" y="` + ftoa(yPos) +
299 `" width="` + ftoa(sliceWidth) +
300 `" height="` + ftoa(wallHeight) +
301 `" fill="rgb(` + strconv.Itoa(colorVal1) + `,69,` + strconv.Itoa(colorVal2) + `)"/>`)
302
303 if drawBanana != nil {
304 continue // Banana already drawn
305 }
306
307 // Only draw banana if the middle ray hit the end
308 // XXX: improve this by checking for a hit in the middle of the end cell
309 if i == rays/2 && endHit && endDist < distance {
310 iconHeight := 10.0 / endDist
311 scale := iconHeight / 100
312 x := float64(i)*sliceWidth + sliceWidth/2
313 y := groundLevel + 20 + (iconHeight*scale)/2
314
315 drawBanana = func() {
316 svg.WriteString(`<g transform="translate(` + ftoa(x) + ` ` + ftoa(y) +
317 `) scale(` + ftoa(scale) + `)">` + string(svgassets["banana"]) + `</g>`)
318 }
319 }
320 }
321
322 if drawBanana != nil {
323 drawBanana()
324 }
325
326 playerCellX, playerCellY := int(math.Floor(playerX)), int(math.Floor(playerY))
327
328 xStart := max(0, playerCellX-visibleCells/2)
329 xEnd := min(len(m[0]), playerCellX+visibleCells/2+1)
330
331 yStart := max(0, playerCellY-visibleCells/2)
332 yEnd := min(len(m), playerCellY+visibleCells/2+1)
333
334 scaleX := miniMapSize / float64(xEnd-xStart)
335 scaleY := miniMapSize / float64(yEnd-yStart)
336
337 for y := yStart; y < yEnd; y++ {
338 for x := xStart; x < xEnd; x++ {
339 color := "black"
340 if m[y][x] == 1 {
341 color = "rgb(149,0,32)"
342 }
343 svg.WriteString(`<rect x="` + ftoa(float64(x-xStart)*scaleX+offsetX) +
344 `" y="` + ftoa(float64(y-yStart)*scaleY+offsetY) +
345 `" width="` + ftoa(scaleX) +
346 `" height="` + ftoa(scaleY) +
347 `" fill="` + color + `"/>`)
348 }
349 }
350
351 px := (playerX-float64(xStart))*scaleX + offsetX
352 py := (playerY-float64(yStart))*scaleY + offsetY
353 svg.WriteString(`<circle cx="` + ftoa(px) + `" cy="` + ftoa(py) + `" r="` + ftoa(scaleX/2) + `" fill="rgb(200,200,200)"/>`)
354
355 dx := math.Cos(angle) * dirLen
356 dy := math.Sin(angle) * dirLen
357 svg.WriteString(`<line x1="` + ftoa(px) + `" y1="` + ftoa(py) +
358 `" x2="` + ftoa((playerX+dx-float64(xStart))*scaleX+offsetX) +
359 `" y2="` + ftoa((playerY+dy-float64(yStart))*scaleY+offsetY) +
360 `" stroke="rgb(200,200,200)" stroke-width="1"/>`)
361
362 svg.WriteString(`</svg>`)
363 return svg.String()
364}
365
366// renderGrid3D creates a 3D view of the grid
367func renderGrid3D(cur realm, p *PlayerState) string {
368 svg := GenerateSVG(cur, p)
369 base64SVG := base64.StdEncoding.EncodeToString([]byte(svg))
370 return "![SVG Image](data:image/svg+xml;base64," + base64SVG + ")"
371}
372
373// generateDirLink generates a link to change player direction
374func generateDirLink(path string, p *PlayerState, action string) string {
375 newState := *p // Make copy
376
377 switch action {
378 case "forward":
379 dx, dy := directionDeltas(newState.Direction)
380 newState.Move(dx, dy)
381 case "left":
382 newState.Rotate(false)
383 case "right":
384 newState.Rotate(true)
385 }
386
387 vals := make(url.Values)
388 vals.Set("x", strconv.Itoa(newState.CellX))
389 vals.Set("y", strconv.Itoa(newState.CellY))
390 vals.Set("dir", strconv.Itoa(newState.Direction))
391
392 vals.Set("sum", newState.SumCode())
393 return path + "?" + vals.Encode()
394}
395
396// isPlayerTouchingWall checks if the player's position is inside a wall
397func isPlayerTouchingWall(x, y float64) bool {
398 ix, iy := int(math.Floor(x)), int(math.Floor(y))
399 if iy < 0 || iy >= len(maze) || ix < 0 || ix >= len(maze[0]) {
400 return true
401 }
402 return maze[iy][ix] == CellKindEmpty
403}
404
405// directionDeltas provides deltas for movement based on direction
406func directionDeltas(d int) (x, y int) {
407 s := []struct{ x, y int }{
408 {1, 0}, // 0 == E
409 {1, 1}, // SE
410 {0, 1}, // S
411 {-1, 1}, // SW
412 {-1, 0}, // W
413 {-1, -1}, // NW
414 {0, -1}, // N
415 {1, -1}, // NE
416 }[d]
417 return s.x, s.y
418}
419
420// atoiDefault converts string to integer with a default fallback
421func atoiDefault(s string, def int) int {
422 if s == "" {
423 return def
424 }
425 i, _ := strconv.Atoi(s)
426 return i
427}
428
429// Render renders the game interface
430func Render(path string) string {
431 u, _ := url.Parse(path)
432 query := u.Query()
433
434 p := PlayerState{
435 CellX: atoiDefault(query.Get("x"), startPos.X),
436 CellY: atoiDefault(query.Get("y"), startPos.Y),
437 Direction: atoiDefault(query.Get("dir"), 0), // Start facing east
438 }
439
440 cpath := strings.TrimPrefix(runtime.CurrentRealm().PkgPath(), runtime.ChainDomain())
441 psum := p.SumCode()
442 reset := "[reset](" + cpath + ")"
443
444 if startPos.X != p.CellX || startPos.Y != p.CellY {
445 if sum := query.Get("sum"); psum != sum {
446 return "invalid sum : " + reset
447 }
448 }
449
450 if endPos.X == p.CellX && endPos.Y == p.CellY {
451 return strings.Join([]string{
452 "### Congrats you win level " + strconv.Itoa(level) + " !!",
453 "Code for next level is: " + psum,
454 "[Generate Next Level: " + strconv.Itoa(level+1) + "](" + txlink.Call("GenerateNextLevel", "answer", psum) + ")",
455 }, "\n\n")
456 }
457
458 // Generate commands
459 commands := strings.Join([]string{
460 "<gno-columns>",
461 "|||",
462 "[▲](" + generateDirLink(cpath, &p, "forward") + ")",
463 "|||",
464 "</gno-columns>",
465 "<gno-columns>",
466 "[◄](" + generateDirLink(cpath, &p, "left") + ")",
467 "|||",
468 "|||",
469 "[►](" + generateDirLink(cpath, &p, "right") + ")",
470 "</gno-columns>",
471 }, "\n\n")
472
473 // Generate view
474 view := strings.Join([]string{
475 "<gno-columns>",
476 renderGrid3D(cross, &p),
477 "</gno-columns>",
478 }, "\n\n")
479
480 return strings.Join([]string{
481 "## Find the banana: Level " + strconv.Itoa(level),
482 "---", view, "---", commands, "---",
483 reset,
484 "Position: (" + strconv.Itoa(p.CellX) + ", " + strconv.Itoa(p.CellY) + ") Direction: " + ftoa(float64(p.Direction)/math.Pi) + "π",
485 }, "\n\n")
486}
487
488// max returns the maximum of two integers
489func max(a, b int) int {
490 if a > b {
491 return a
492 }
493 return b
494}
495
496// min returns the minimum of two integers
497func min(a, b int) int {
498 if a < b {
499 return a
500 }
501 return b
502}
