src

Go monorepo.
Log | Files | Refs

commit 400f615a44fc0a7516c8c92c5756914854011a70
parent 8a6dcbffa4c18adb4ed4a98fe43aac51dd9cd9ed
Author: dwrz <dwrz@dwrz.net>
Date:   Thu, 22 Dec 2022 15:19:09 +0000

Add minotaur

Squashed commit of the following:

commit c162e3e480ba9f626681f30aeb482e9a7a5bbdbd
Author: dwrz <dwrz@dwrz.net>
Date:   Wed Dec 21 22:42:14 2022 +0000

    Refactor minotaur

commit 248a856a21b9808b040b61f9f30e95497b834726
Author: dwrz <dwrz@dwrz.net>
Date:   Mon Dec 19 20:16:05 2022 +0000

    Add minotaur

Diffstat:
Acmd/minotaur/main.go | 96+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Apkg/minotaur/maze/cell/cell.go | 15+++++++++++++++
Apkg/minotaur/maze/cell/cell_test.go | 43+++++++++++++++++++++++++++++++++++++++++++
Apkg/minotaur/maze/direction/direction.go | 68++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Apkg/minotaur/maze/generate.go | 84+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Apkg/minotaur/maze/maze.go | 153+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Apkg/minotaur/maze/position/position.go | 61+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Apkg/minotaur/minotaur.go | 233+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
8 files changed, 753 insertions(+), 0 deletions(-)

diff --git a/cmd/minotaur/main.go b/cmd/minotaur/main.go @@ -0,0 +1,96 @@ +package main + +import ( + "context" + "flag" + "os" + "os/signal" + "path/filepath" + "syscall" + "time" + + "code.dwrz.net/src/pkg/log" + "code.dwrz.net/src/pkg/minotaur" + "code.dwrz.net/src/pkg/terminal" +) + +var ( + height = flag.Int("h", 2, "height") + width = flag.Int("w", 2, "width") + tick = flag.Int("t", 250, "ms between minotaur movement") +) + +func main() { + var l = log.New(os.Stderr) + + // Parse flags. + flag.Parse() + if *height <= 0 { + l.Error.Fatalf("invalid height: %d", *height) + } + if *width <= 0 { + l.Error.Fatalf("invalid width: %d", *width) + } + if *tick <= 0 { + l.Error.Fatalf("invalid tick: %d", *tick) + } + + // Setup the main context. + ctx, cancel := context.WithCancel(context.Background()) + + // Setup workspace and log file. + cdir, err := os.UserCacheDir() + if err != nil { + l.Error.Fatalf( + "failed to determine user cache directory: %v", err, + ) + } + wdir := filepath.Join(cdir, "minotaur") + + if err := os.MkdirAll(wdir, os.ModeDir|0700); err != nil { + l.Error.Fatalf("failed to create tmp dir: %v", err) + } + + f, err := os.Create(wdir + "/log") + if err != nil { + l.Error.Fatalf("failed to create log file: %v", err) + } + defer f.Close() + + // Retrieve terminal info. + t, err := terminal.New(os.Stdin.Fd()) + if err != nil { + l.Error.Fatalf("failed to get terminal attributes: %v", err) + } + + // TODO: refactor; handle sigwinch. + go func() { + var signals = make(chan os.Signal, 1) + signal.Notify(signals, syscall.SIGTERM, syscall.SIGINT) + + // Block until we receive a signal. + s := <-signals + l.Debug.Printf("received signal: %s", s) + + cancel() + }() + + // Setup the game. + game, err := minotaur.New(minotaur.Parameters{ + Height: *height, + In: os.Stdin, + Log: log.New(f), + Out: os.Stdout, + Terminal: t, + Tick: time.Duration(*tick) * time.Millisecond, + Width: *width, + }) + if err != nil { + l.Error.Fatalf("failed to create game: %v", err) + } + + // Run the game. + if err := game.Run(ctx); err != nil { + l.Error.Fatal(err) + } +} diff --git a/pkg/minotaur/maze/cell/cell.go b/pkg/minotaur/maze/cell/cell.go @@ -0,0 +1,15 @@ +package cell + +import ( + "code.dwrz.net/src/pkg/minotaur/maze/direction" +) + +type Cell uint8 + +func (c Cell) HasDirection(d direction.Direction) bool { + return c&(1<<d) != 0 +} + +func (c *Cell) SetDirection(d direction.Direction) { + *c |= 1 << d +} diff --git a/pkg/minotaur/maze/cell/cell_test.go b/pkg/minotaur/maze/cell/cell_test.go @@ -0,0 +1,43 @@ +package cell + +import ( + "testing" + + "code.dwrz.net/src/pkg/minotaur/maze/direction" +) + +func TestSetDirection(t *testing.T) { + var c Cell + t.Logf("start: %08b", c) + + c.SetDirection(direction.Right) + t.Logf("set right: %08b", c) + + c.SetDirection(direction.Down) + t.Logf("set down: %08b", c) + + var ( + hasRight = c.HasDirection(direction.Right) + hasDown = c.HasDirection(direction.Down) + hasLeft = c.HasDirection(direction.Left) + hasUp = c.HasDirection(direction.Up) + ) + + t.Logf("has right: %v", hasRight) + t.Logf("has down: %v", hasDown) + t.Logf("has left: %v", hasLeft) + t.Logf("has up: %v", hasUp) + + if !hasRight { + t.Errorf("expected cell to have right") + } + if !hasDown { + t.Errorf("expected cell to have down") + } + if hasLeft { + t.Errorf("expected cell to not have left") + } + if hasUp { + t.Errorf("expected cell to not have up") + } +} diff --git a/pkg/minotaur/maze/direction/direction.go b/pkg/minotaur/maze/direction/direction.go @@ -0,0 +1,68 @@ +package direction + +import ( + "math/rand" + "time" +) + +type Direction int + +const ( + Down Direction = iota + Left + Right + Up +) + +func (d Direction) Opposite() Direction { + switch d { + case Down: + return Up + case Left: + return Right + case Right: + return Left + case Up: + return Down + default: + return d + } +} + +func (d Direction) String() string { + switch d { + case Down: + return "down" + case Left: + return "left" + case Right: + return "right" + case Up: + return "up" + default: + return "" + } +} + +var ( + directions = [4]Direction{Down, Left, Right, Up} + random = rand.New(rand.NewSource(time.Now().UnixNano())) +) + +func Directions() [4]Direction { + return [4]Direction{Down, Left, Right, Up} +} + +func Random() Direction { + return directions[random.Intn(len(directions))] +} + +func RandomDirections() [4]Direction { + var dirs = [...]Direction{Down, Left, Right, Up} + + random.Shuffle(len(dirs), func(i, j int) { + dirs[i], dirs[j] = dirs[j], dirs[i] + }) + + return dirs +} diff --git a/pkg/minotaur/maze/generate.go b/pkg/minotaur/maze/generate.go @@ -0,0 +1,84 @@ +package maze + +import ( + "code.dwrz.net/src/pkg/minotaur/maze/cell" + "code.dwrz.net/src/pkg/minotaur/maze/direction" + "code.dwrz.net/src/pkg/minotaur/maze/position" +) + +func inBounds(h, w, x, y int) bool { + if x < 0 || x >= w { + return false + } + if y < 0 || y >= h { + return false + } + + return true +} + +// http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm +func generate(h, w int) [][]cell.Cell { + var layout = make([][]cell.Cell, h) + + // Create the rows. + for i := range layout { + layout[i] = make([]cell.Cell, w) + for j := range layout[i] { + layout[i][j] = 0 + } + } + + // Connect the cells. + var ( + current = position.Position{X: 0, Y: 0} + stack = []position.Position{current} + visited = map[position.Position]struct{}{ + current: {}, + } + ) + for len(stack) > 0 { + // Get newest. + current = stack[len(stack)-1] + + dirs := direction.RandomDirections() + found := false + for _, d := range dirs { + var neighbor = current.WithDirection(d) + + // Ignore if out of bounds. + if !inBounds(h, w, neighbor.X, neighbor.Y) { + continue + } + + // Ignore if already visited. + if _, seen := visited[neighbor]; seen { + continue + } + + // We've found a cell to connect. + found = true + + // Mark it as visited. + visited[neighbor] = struct{}{} + + // Add it to the queue. + stack = append(stack, neighbor) + + // Connect the cells. + layout[current.Y][current.X].SetDirection(d) + layout[neighbor.Y][neighbor.X].SetDirection( + d.Opposite(), + ) + + break + } + + // If no neighbor was found, remove this cell from the list. + if !found { + stack = stack[:len(stack)-1] + } + } + + return layout +} diff --git a/pkg/minotaur/maze/maze.go b/pkg/minotaur/maze/maze.go @@ -0,0 +1,153 @@ +package maze + +import ( + "bytes" + + "code.dwrz.net/src/pkg/log" + "code.dwrz.net/src/pkg/minotaur/maze/cell" + "code.dwrz.net/src/pkg/minotaur/maze/direction" + "code.dwrz.net/src/pkg/minotaur/maze/position" + "code.dwrz.net/src/pkg/terminal" +) + +type Maze struct { + height int + layout [][]cell.Cell + log *log.Logger + width int +} + +type Parameters struct { + Height int + Log *log.Logger + Width int +} + +func New(p Parameters) (*Maze, error) { + return &Maze{ + height: p.Height, + layout: generate(p.Height, p.Width), + log: p.Log, + width: p.Width, + }, nil +} + +func (m *Maze) Cell(p position.Position) cell.Cell { + return m.layout[p.Y][p.X] +} + +func (m *Maze) InBounds(p position.Position) bool { + return inBounds(m.height, m.width, p.X, p.Y) +} + +func (m *Maze) Solve(start, end position.Position) (s []position.Position) { + var q = [][]position.Position{{start}} + for len(q) > 0 { + // Get the current search from the queue. + s, q = q[0], q[1:] + + // Use the last cell as the current candidate. + var ( + current = s[len(s)-1] + cell = m.Cell(current) + previous *position.Position + ) + + // If we've reached the end, we have a solution. + if current.Equal(end) { + return s + } + + // Explore new routes. + // Determine the previous cell, to avoid backtracking. + if len(s) > 1 { + previous = &s[len(s)-2] + } + for _, d := range direction.Directions() { + if !cell.HasDirection(d) { + continue + } + + // Get the next position with this direction. + next := current.WithDirection(d) + + // Prevent backtracking. + if previous != nil && next.Equal(*previous) { + continue + } + + // Next is valid; add it to the search queue. + // TODO: is there a way to reuse the backing array? + var route = make([]position.Position, len(s)+1) + copy(route, s) + route[len(route)-1] = next + + q = append(q, route) + } + } + + return nil +} + +type RenderParameters struct { + Passage string + // Positions is used to render a cell with the mapped string. + // The order in which you list positions matters. + // If there are overlapping positions, the last set one wins. + Positions map[position.Position]string + Wall string +} + +func (m *Maze) Render(p RenderParameters) []byte { + var buf bytes.Buffer + + buf.WriteString(terminal.CursorHide) + buf.WriteString(terminal.CursorTopLeft) + + // Print the top wall. + // We need to print each cell, and its right connection. + // Thus the wall needs to be twice the width. + // We also need to cover the right wall, thus +1. + topWidth := 2*m.width + 1 + for i := 0; i < topWidth; i++ { + buf.WriteString(p.Wall) + } + buf.WriteString("\r\n") + + for y, row := range m.layout { + buf.WriteString(p.Wall) // left wall + + // Print each cell and the passage or wall to its right. + for x, cell := range row { + var block = p.Positions[position.Position{X: x, Y: y}] + if block == "" { + block = p.Passage + } + + buf.WriteString(block) + + if cell.HasDirection(direction.Right) { + buf.WriteString(p.Passage) + } else { + buf.WriteString(p.Wall) + } + } + buf.WriteString("\r\n") + + // Print the cell's bottom passage or wall. + // Print a wall to the cell's lower-right. + buf.WriteString(p.Wall) // left wall + for _, cell := range row { + if cell.HasDirection(direction.Down) { + buf.WriteString(p.Passage) + } else { + buf.WriteString(p.Wall) + } + + buf.WriteString(p.Wall) + } + buf.WriteString("\r\n") + } + + return buf.Bytes() +} diff --git a/pkg/minotaur/maze/position/position.go b/pkg/minotaur/maze/position/position.go @@ -0,0 +1,61 @@ +package position + +import ( + "fmt" + "math/rand" + "time" + + "code.dwrz.net/src/pkg/minotaur/maze/direction" +) + +type Position struct { + X, Y int +} + +func (p Position) Equal(v Position) bool { + return p.X == v.X && p.Y == v.Y +} + +func (p Position) Down() Position { + return Position{X: p.X, Y: p.Y + 1} +} + +func (p Position) Left() Position { + return Position{X: p.X - 1, Y: p.Y} +} + +func (p Position) Right() Position { + return Position{X: p.X + 1, Y: p.Y} +} + +func (p Position) Up() Position { + return Position{X: p.X, Y: p.Y - 1} +} + +func (p Position) String() string { + return fmt.Sprintf("%d,%d", p.X, p.Y) +} + +func (p Position) WithDirection(d direction.Direction) Position { + switch d { + case direction.Down: + return p.Down() + case direction.Left: + return p.Left() + case direction.Right: + return p.Right() + case direction.Up: + return p.Up() + default: + return p + } +} + +var random = rand.New(rand.NewSource(time.Now().UnixNano())) + +func Random(width, height int) Position { + return Position{ + X: random.Intn(width), + Y: random.Intn(height), + } +} diff --git a/pkg/minotaur/minotaur.go b/pkg/minotaur/minotaur.go @@ -0,0 +1,233 @@ +package minotaur + +import ( + "context" + "fmt" + "os" + "time" + + "code.dwrz.net/src/pkg/color" + "code.dwrz.net/src/pkg/log" + "code.dwrz.net/src/pkg/minotaur/maze" + "code.dwrz.net/src/pkg/minotaur/maze/direction" + "code.dwrz.net/src/pkg/minotaur/maze/position" + "code.dwrz.net/src/pkg/terminal" + "code.dwrz.net/src/pkg/terminal/input" +) + +const ( + // Game over messages. + slain = "You were slain by the Minotaur. Score: %v.\r\n" + escaped = "You escaped the labyrinth. Score: %v.\r\n" + + // Blocks for rendering. + end = color.BackgroundGreen + " " + color.Reset + minotaur = color.BackgroundYellow + " " + color.Reset + passage = " " + theseus = color.BackgroundMagenta + " " + color.Reset + solution = color.BackgroundBlue + " " + color.Reset + wall = color.BackgroundBlack + " " + color.Reset +) + +type Game struct { + errs chan error + events chan *input.Event + input *input.Reader + log *log.Logger + maze *maze.Maze + out *os.File + start time.Time + terminal *terminal.Terminal + ticker *time.Ticker + + // Maze positions. + end position.Position + theseus position.Position + minotaur position.Position + solution []position.Position +} + +type Parameters struct { + Height int + In *os.File + Log *log.Logger + Out *os.File + Terminal *terminal.Terminal + Tick time.Duration + Width int +} + +func New(p Parameters) (*Game, error) { + var g = &Game{ + errs: make(chan error), + events: make(chan *input.Event), + log: p.Log, + out: p.Out, + terminal: p.Terminal, + ticker: time.NewTicker(p.Tick), + } + + maze, err := maze.New(maze.Parameters{ + Height: p.Height, + Log: g.log, + Width: p.Width, + }) + if err != nil { + return nil, fmt.Errorf("failed to generate maze: %v", err) + } + g.maze = maze + + g.input = input.New(input.Parameters{ + Chan: g.events, + In: os.Stdin, + Log: g.log, + }) + + // Set start and end. + g.theseus = position.Random(p.Width, p.Height) + g.end = position.Random(p.Width, p.Height) + g.minotaur = position.Random(p.Width, p.Height) + + return g, nil +} + +func (g *Game) Run(ctx context.Context) error { + // Setup the terminal. + if err := g.terminal.SetRaw(); err != nil { + return fmt.Errorf( + "failed to set terminal attributes: %v", err, + ) + } + + // Clean up before exit. + defer g.quit() + + // TODO: refactor to use a terminal output package. + g.out.WriteString(terminal.ClearScreen) + g.out.WriteString(terminal.CursorTopLeft) + g.out.WriteString(terminal.CursorHide) + g.render() + + // Start reading user input. + go func() { + if err := g.input.Run(ctx); err != nil { + g.errs <- err + } + }() + + // Main loop. + g.start = time.Now() + for { + select { + case <-ctx.Done(): + return nil + + case err := <-g.errs: + return err + + case <-g.ticker.C: + g.moveMinotaur() + g.render() + + case event := <-g.events: + switch event.Rune { + case 'q': // Quit + return nil + + case 's': // Toggle the solution. + if g.solution == nil { + g.solve() + } else { + g.solution = nil + } + g.render() + continue + } + switch event.Key { + case input.Up: + g.moveTheseus(direction.Up) + case input.Left: + g.moveTheseus(direction.Left) + case input.Down: + g.moveTheseus(direction.Down) + case input.Right: + g.moveTheseus(direction.Right) + } + // If the solution is set, update it. + if g.solution != nil { + g.solve() + } + + g.render() + + default: + // Check for game over conditions. + switch { + case g.escaped(): + fmt.Fprintf(g.out, escaped, g.score()) + return nil + + case g.slain(): + fmt.Fprintf(g.out, slain, g.score()) + return nil + } + } + } +} + +func (g *Game) render() { + var params = maze.RenderParameters{ + Positions: map[position.Position]string{}, + Passage: passage, + Wall: wall, + } + for _, p := range g.solution { + params.Positions[p] = solution + } + params.Positions[g.end] = end + params.Positions[g.theseus] = theseus + params.Positions[g.minotaur] = minotaur + + g.out.Write(g.maze.Render(params)) +} + +func (g *Game) score() int { + return int(time.Since(g.start).Round(time.Second).Seconds()) +} + +func (g *Game) quit() { + g.out.Write([]byte(terminal.CursorShow)) + + if err := g.terminal.Reset(); err != nil { + g.log.Error.Printf( + "failed to reset terminal attributes: %v", err, + ) + } +} + +func (g *Game) escaped() bool { + return g.theseus == g.end +} + +func (g *Game) moveMinotaur() { + path := g.maze.Solve(g.minotaur, g.theseus) + if len(path) < 2 { + return + } + + g.minotaur = path[1] +} + +func (g *Game) moveTheseus(d direction.Direction) { + if cell := g.maze.Cell(g.theseus); cell.HasDirection(d) { + g.theseus = g.theseus.WithDirection(d) + } +} + +func (g *Game) slain() bool { + return g.minotaur == g.theseus +} + +func (g *Game) solve() { + g.solution = g.maze.Solve(g.theseus, g.end) +}