Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
This Go program is a re-implementation of the Ruby code found in Chapter 2 of the book Mazes for Programmers by Jamis Buck.
// Copyright (c) 2019 Torbjørn Marø
//
// This Go program is a re-implementation of the Ruby code found
// in Chapter 2 of the book Mazes for Programmers by Jamis Buck.
// The source contains:
// - General purpose Grid implementation
// - Grid to string function (ASCII maze)
// - Grid to PNG function (using gg package)
// - Binary Tree maze generation algorithm
// - Sidewinder maze generation algorithm
//
// $ go run mazeChapter2.go
//
// Binary Tree Maze:
// +---+---+---+---+---+---+---+---+---+---+---+---+
// | |
// +---+ +---+ +---+---+ + + +---+ + +
// | | | | | | | |
// + + +---+ +---+ + + +---+---+---+ +
// | | | | | | | |
// +---+ + +---+ + + + +---+ +---+ +
// | | | | | | | | |
// +---+ + +---+ +---+---+---+ +---+---+ +
// | | | | | |
// +---+---+ +---+ + + + + + +---+ +
// | | | | | | | | |
// + +---+---+---+---+ + + +---+---+ + +
// | | | | | | |
// +---+---+---+---+---+---+---+---+---+---+---+---+
//
// Sidewinder Maze:
// +---+---+---+---+---+---+---+---+---+---+---+---+
// | |
// +---+ + + +---+ + + + +---+---+ +
// | | | | | | | | |
// + + +---+ + + + +---+ + + +---+
// | | | | | | | | | |
// + +---+ + +---+ + + + +---+ + +
// | | | | | | | | | |
// + + + +---+ +---+---+---+---+ + +---+
// | | | | | | |
// +---+ +---+ + +---+ + + + + + +
// | | | | | | | | | |
// + +---+---+ +---+ + +---+---+ +---+ +
// | | | | | | |
// +---+---+---+---+---+---+---+---+---+---+---+---+
//
package main
import (
"fmt"
"image/color"
"math/rand"
"strings"
"time"
"github.com/fogleman/gg"
)
type cell struct {
row int
column int
north *cell
south *cell
east *cell
west *cell
links map[*cell]bool
}
func newCell(row, column int) *cell {
return &cell{row: row, column: column, links: make(map[*cell]bool)}
}
func (c *cell) link(other *cell) {
c.links[other] = true
other.links[c] = true
}
func (c *cell) unlink(other *cell) {
delete(c.links, other)
delete(other.links, c)
}
func (c *cell) isLinked(other *cell) bool {
_, ok := c.links[other]
return ok
}
func (c *cell) linkedCells() (result []*cell) {
result = make([]*cell, len(c.links))
i := 0
for k := range c.links {
result[i] = k
i++
}
return
}
func (c *cell) neighbors() (list []*cell) {
list = make([]*cell, 0, 4)
if c.east != nil {
list = append(list, c.east)
}
if c.west != nil {
list = append(list, c.west)
}
if c.north != nil {
list = append(list, c.north)
}
if c.south != nil {
list = append(list, c.south)
}
return
}
type grid struct {
rows int
columns int
grid [][]*cell
}
func newGrid(rows, columns int) (g grid) {
g = grid{rows: rows, columns: columns}
g.grid = make([][]*cell, rows)
for i := range g.grid {
g.grid[i] = make([]*cell, columns)
for j := 0; j < columns; j++ {
g.grid[i][j] = newCell(i, j)
}
}
g.eachCell(func(c *cell) {
row := c.row
col := c.column
c.north = g.cellAt(row-1, col)
c.south = g.cellAt(row+1, col)
c.west = g.cellAt(row, col-1)
c.east = g.cellAt(row, col+1)
})
return
}
func (g *grid) cellAt(row, column int) *cell {
if row >= 0 && row < g.rows {
if column >= 0 && column < len(g.grid[row]) {
return g.grid[row][column]
}
}
return nil
}
func (g *grid) randomCell() *cell {
row := rand.Intn(g.rows)
column := rand.Intn(len(g.grid[row]))
return g.cellAt(row, column)
}
func (g grid) size() int {
return g.rows * g.columns
}
func (g *grid) eachRow(fn func([]*cell)) {
for _, row := range g.grid {
fn(row)
}
}
func (g *grid) eachCell(fn func(*cell)) {
g.eachRow(func(row []*cell) {
for _, sell := range row {
fn(sell)
}
})
}
func (g grid) String() string {
var sb strings.Builder
sb.WriteString("+")
for i := 0; i < g.columns; i++ {
sb.WriteString("---+")
}
sb.WriteString("\n")
g.eachRow(func(row []*cell) {
top := "|"
bottom := "+"
for _, c := range row {
if c == nil {
c = newCell(-1, -1)
}
body := " "
eastBoundary := "|"
if c.isLinked(c.east) {
eastBoundary = " "
}
top += body + eastBoundary
southBoundary := "---"
if c.isLinked(c.south) {
southBoundary = " "
}
corder := "+"
bottom += southBoundary + corder
}
sb.WriteString(top)
sb.WriteString("\n")
sb.WriteString(bottom)
sb.WriteString("\n")
})
return sb.String()
}
func (g grid) Png(path string) error {
cellSize := 20
imgWidth := cellSize * g.columns
imgHeight := cellSize * g.rows
dc := gg.NewContext(imgWidth+4, imgHeight+4)
dc.SetColor(color.Black)
dc.DrawRectangle(0.0, 0.0, float64(imgWidth), float64(imgHeight))
dc.Fill()
dc.SetLineWidth(2.0)
dc.SetRGB255(66, 244, 116)
g.eachCell(func(c *cell) {
x1 := float64(c.column*cellSize + 1)
y1 := float64(c.row*cellSize + 1)
x2 := float64((c.column+1)*cellSize + 1)
y2 := float64((c.row+1)*cellSize + 1)
if c.north == nil {
dc.DrawLine(x1, y1, x2, y1)
dc.Stroke()
}
if c.west == nil {
dc.DrawLine(x1, y1, x1, y2)
dc.Stroke()
}
if !c.isLinked(c.east) {
dc.DrawLine(x2, y1, x2, y2)
dc.Stroke()
}
if !c.isLinked(c.south) {
dc.DrawLine(x1, y2, x2, y2)
dc.Stroke()
}
})
return dc.SavePNG(path)
}
func sample(cells []*cell) *cell {
return cells[rand.Intn(len(cells))]
}
func (g *grid) binaryTreeMaze() {
g.eachCell(func(c *cell) {
neighbors := make([]*cell, 0, 2)
if c.north != nil {
neighbors = append(neighbors, c.north)
}
if c.east != nil {
neighbors = append(neighbors, c.east)
}
if len(neighbors) > 0 {
index := rand.Intn(len(neighbors))
neighbor := neighbors[index]
c.link(neighbor)
}
})
}
func coinflip() bool {
return rand.Intn(2) == 0
}
func (g *grid) sidewinderMaze() {
g.eachRow(func(row []*cell) {
run := make([]*cell, 0, len(row))
for _, c := range row {
run = append(run, c)
atEastBound := c.east == nil
atNorthBound := c.north == nil
shouldClose := atEastBound || (!atNorthBound && coinflip())
if shouldClose {
member := sample(run)
if member.north != nil {
member.link(member.north)
}
run = make([]*cell, 0, len(row))
} else {
c.link(c.east)
}
}
})
}
func main() {
rand.Seed(time.Now().UnixNano())
fmt.Println("\nBinary Tree Maze:")
grid := newGrid(7, 12)
grid.binaryTreeMaze()
fmt.Print(grid)
fmt.Println("\nSidewinder Maze:")
grid = newGrid(7, 12)
grid.sidewinderMaze()
fmt.Print(grid)
path := "out.png"
fmt.Println("Saving 20x30 Sidewinder maze to " + path)
grid = newGrid(20, 30)
grid.sidewinderMaze()
if err := grid.Png(path); err != nil {
panic(err)
}
}
@tormaroe

This comment has been minimized.

Copy link
Owner Author

tormaroe commented Jan 10, 2019

Sample PNG output:

out

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.