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