maze.gno
12.79 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 "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 cross(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 crossing()
119
120 seed := uint64(std.ChainHeight())
121 rng := rand.New(rand.NewPCG(seed, uint64(time.Now().Unix())))
122
123 endState := PlayerState{CellX: endPos.X, CellY: endPos.Y}
124 hash := endState.SumCode()
125 if hash != answer {
126 panic("invalid answer")
127 }
128
129 // Generate new map
130 level++
131 salt = rng.Int64()
132 generateLevel(rng, level)
133}
134
135// generateLevel creates a new maze for the given level
136func generateLevel(rng *rand.Rand, level int) {
137 if level < 0 {
138 panic("invalid level")
139 }
140
141 size := level + baseLevel
142 maze, startPos, endPos = generateMap(rng, size, size)
143}
144
145// generateMap creates a random maze using a depth-first search algorithm.
146func generateMap(rng *rand.Rand, width, height int) ([][]int, Position, Position) {
147 // Initialize the maze grid filled with walls.
148 m := make([][]int, height)
149 for y := range m {
150 m[y] = make([]int, width)
151 for x := range m[y] {
152 m[y][x] = CellKindWall
153 }
154 }
155
156 // Define start position and initialize stack for DFS
157 start := Position{1, 1}
158 stack := []Position{start}
159 m[start.Y][start.X] = CellKindEmpty
160
161 // Initialize distance matrix and track farthest
162 dist := make([][]int, height)
163 for y := range dist {
164 dist[y] = make([]int, width)
165 for x := range dist[y] {
166 dist[y][x] = -1
167 }
168 }
169 dist[start.Y][start.X] = CellKindEmpty
170 maxDist := 0
171 candidates := []Position{start}
172
173 // Possible directions for movement: right, left, down, up
174 directions := []Position{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
175
176 // Generate maze paths using DFS
177 for len(stack) > 0 {
178 current := stack[len(stack)-1]
179 stack = stack[:len(stack)-1]
180
181 var dirCandidates []struct {
182 next, wall Position
183 }
184
185 // Evaluate possible candidates for maze paths
186 for _, d := range directions {
187 nx, ny := current.X+d.X*2, current.Y+d.Y*2
188 wx, wy := current.X+d.X, current.Y+d.Y
189
190 // Check if the candidate position is within bounds and still a wall
191 if nx > 0 && nx < width-1 && ny > 0 && ny < height-1 && m[ny][nx] == 1 {
192 dirCandidates = append(dirCandidates, struct{ next, wall Position }{
193 Position{nx, ny}, Position{wx, wy},
194 })
195 }
196 }
197
198 // If candidates are available, choose one and update the maze
199 if len(dirCandidates) > 0 {
200 chosen := dirCandidates[rng.IntN(len(dirCandidates))]
201 m[chosen.wall.Y][chosen.wall.X] = CellKindEmpty
202 m[chosen.next.Y][chosen.next.X] = CellKindEmpty
203
204 // Update distance for the next cell
205 currentDist := dist[current.Y][current.X]
206 nextDist := currentDist + 2
207 dist[chosen.next.Y][chosen.next.X] = nextDist
208
209 // Update maxDist and candidates
210 if nextDist > maxDist {
211 maxDist = nextDist
212 candidates = []Position{chosen.next}
213 } else if nextDist == maxDist {
214 candidates = append(candidates, chosen.next)
215 }
216
217 stack = append(stack, current, chosen.next)
218 }
219 }
220
221 // Select a random farthest position as the end
222 var end Position
223 if len(candidates) > 0 {
224 end = candidates[rng.IntN(len(candidates))]
225 } else {
226 end = Position{width - 2, height - 2} // Fallback to bottom-right
227 }
228
229 return m, start, end
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 crossing()
267
268 const (
269 svgWidth, svgHeight = 800, 600
270 offsetX, offsetY = 0.0, 500.0
271 groundLevel = 300
272 rays = 124
273 fov = math.Pi / 4
274 miniMapSize = 100.0
275 visibleCells = 7
276 dirLen = 2.0
277 )
278
279 m := maze
280 playerX, playerY := p.Position()
281 angle := p.Angle()
282
283 sliceWidth := float64(svgWidth) / float64(rays)
284 angleStep := fov / float64(rays)
285
286 var svg strings.Builder
287 svg.WriteString(`<svg width="800" height="600" xmlns="http://www.w3.org/2000/svg">`)
288 svg.WriteString(`<rect x="0" y="0" width="800" height="300" fill="rgb(20,40,20)"/>`)
289 svg.WriteString(`<rect x="0" y="300" width="800" height="300" fill="rgb(40,60,40)"/>`)
290
291 var drawBanana func()
292 for i := 0; i < rays; i++ {
293 rayAngle := angle - fov/2 + float64(i)*angleStep
294 distance, wallHeight, endHit, endDist := castRay(playerX, playerY, rayAngle, m)
295 darkness := 1.0 + distance/4.0
296 colorVal1 := int(180.0 / darkness)
297 colorVal2 := int(32.0 / darkness)
298 yPos := groundLevel - wallHeight/2
299
300 ufmt.Fprintf(&svg,
301 `<rect x="%f" y="%f" width="%f" height="%f" fill="rgb(%d,69,%d)"/>`,
302 float64(i)*sliceWidth, yPos, sliceWidth, wallHeight, colorVal1, 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 ufmt.Fprintf(&svg,
318 `<g transform="translate(%f %f) scale(%f)">%s</g>`,
319 x, y, scale, string(svgassets["banana"]),
320 )
321 }
322 }
323 }
324
325 if drawBanana != nil {
326 drawBanana()
327 }
328
329 playerCellX, playerCellY := int(math.Floor(playerX)), int(math.Floor(playerY))
330
331 xStart := max(0, playerCellX-visibleCells/2)
332 xEnd := min(len(m[0]), playerCellX+visibleCells/2+1)
333
334 yStart := max(0, playerCellY-visibleCells/2)
335 yEnd := min(len(m), playerCellY+visibleCells/2+1)
336
337 scaleX := miniMapSize / float64(xEnd-xStart)
338 scaleY := miniMapSize / float64(yEnd-yStart)
339
340 for y := yStart; y < yEnd; y++ {
341 for x := xStart; x < xEnd; x++ {
342 color := "black"
343 if m[y][x] == 1 {
344 color = "rgb(149,0,32)"
345 }
346 ufmt.Fprintf(&svg,
347 `<rect x="%f" y="%f" width="%f" height="%f" fill="%s"/>`,
348 float64(x-xStart)*scaleX+offsetX, float64(y-yStart)*scaleY+offsetY, scaleX, scaleY, color)
349 }
350 }
351
352 px := (playerX-float64(xStart))*scaleX + offsetX
353 py := (playerY-float64(yStart))*scaleY + offsetY
354 ufmt.Fprintf(&svg, `<circle cx="%f" cy="%f" r="%f" fill="rgb(200,200,200)"/>`, px, py, scaleX/2)
355
356 dx := math.Cos(angle) * dirLen
357 dy := math.Sin(angle) * dirLen
358 ufmt.Fprintf(&svg,
359 `<line x1="%f" y1="%f" x2="%f" y2="%f" stroke="rgb(200,200,200)" stroke-width="1"/>`,
360 px, py, (playerX+dx-float64(xStart))*scaleX+offsetX, (playerY+dy-float64(yStart))*scaleY+offsetY)
361
362 svg.WriteString(`</svg>`)
363 return svg.String()
364}
365
366// renderGrid3D creates a 3D view of the grid
367func renderGrid3D(p *PlayerState) string {
368 svg := GenerateSVG(p)
369 base64SVG := base64.StdEncoding.EncodeToString([]byte(svg))
370 return ufmt.Sprintf("", 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(std.CurrentRealm().PkgPath(), std.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 ufmt.Sprintf("### Congrats you win level %d !!", level),
453 ufmt.Sprintf("Code for next level is: %s", psum),
454 ufmt.Sprintf("[Generate Next Level: %d](%s)", 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 ufmt.Sprintf("[▲](%s)", generateDirLink(cpath, &p, "forward")),
463 "|||",
464 "</gno-columns>",
465 "<gno-columns>",
466 ufmt.Sprintf("[◄](%s)", generateDirLink(cpath, &p, "left")),
467 "|||",
468 "|||",
469 ufmt.Sprintf("[►](%s)", generateDirLink(cpath, &p, "right")),
470 "</gno-columns>",
471 }, "\n\n")
472
473 // Generate view
474 view := strings.Join([]string{
475 "<gno-columns>",
476 renderGrid3D(&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 ufmt.Sprintf("Position: (%d, %d) Direction: %fπ", p.CellX, p.CellY, 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}