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