Documentation
¶
Overview ¶
Package maze implements a simple maze type and some convenience functions around it. It is intended to be used in maze generating and solving programs. By using this package different maze generators and solvers can exchange mazes.
Index ¶
- Constants
- Variables
- type Coord
- type Maze
- func (m *Maze) And(c Coord, v uint32)
- func (m *Maze) At(c Coord) uint32
- func (m *Maze) CellType(c Coord) uint32
- func (m *Maze) Cols() int
- func (m *Maze) Extract(bitn int) *Maze
- func (m *Maze) IsSet(c Coord, v uint32) bool
- func (m *Maze) Neighbors(c Coord, cellType uint32) uint
- func (m *Maze) Or(c Coord, v uint32)
- func (m *Maze) Overlay(m2 *Maze, shift int) error
- func (m *Maze) OverlayAt(m2 *Maze, topLeft Coord, shift int) error
- func (m *Maze) PrettyPrint(w io.Writer, stringAt func(Coord) string) (int64, error)
- func (m *Maze) ReadFrom(r io.Reader) (int64, error)
- func (m *Maze) ReadOneFrom(r io.Reader) (int64, error)
- func (m *Maze) Rows() int
- func (m *Maze) SafeAt(c Coord) uint32
- func (m *Maze) Set(c Coord, v uint32)
- func (m *Maze) StringAtUTF8(c Coord) string
- func (m *Maze) WriteOneTo(w io.Writer) (int64, error)
- func (m *Maze) WriteTo(w io.Writer) (int64, error)
- type Vec
Examples ¶
Constants ¶
const ( WallBit = iota GoalBit SolutionBit VisitedBit Empty = 0 Wall = 1 << WallBit Goal = 1 << GoalBit Solution = 1 << SolutionBit Visited = 1 << VisitedBit )
When using the Syms* maps for pretty printing the first 4 bits of a cell are reserved to represent:
0:wall 1:goal 2:solution 3:visited
Variables ¶
var ( Directions = [...]Vec{ {0, -1}, {-1, 0}, {0, 1}, {1, 0}, } EmptyUTF8 = []string{ ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, } WallUTF8 = []string{ `·`, `╴`, `╵`, `┘`, `╶`, `─`, `└`, `┴`, `╷`, `┐`, `│`, `┤`, `┌`, `┬`, `├`, `┼`, } GoalUTF8 = []string{ `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, `◆`, } SolutionUTF8 = []string{ `●`, `╸`, `╹`, `┛`, `╺`, `━`, `┗`, `┻`, `╻`, `┓`, `┃`, `┫`, `┏`, `┳`, `┣`, `╋`, } VisitedUTF8 = []string{ `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, `░`, } SymsUTF8 = map[uint32][]string{ Empty: EmptyUTF8, Goal: GoalUTF8, Wall: WallUTF8, Solution: SolutionUTF8, Visited: VisitedUTF8, } EmptyASCII = []string{ ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, ` `, } WallASCII = []string{ `+`, `-`, `|`, `+`, `-`, `-`, `+`, `+`, `|`, `+`, `|`, `+`, `+`, `+`, `+`, `+`, } GoalASCII = []string{ `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, `@`, } SolutionASCII = []string{ `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, `*`, } VisitedASCII = []string{ `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, `.`, } SymsASCII = map[uint32][]string{ Empty: EmptyASCII, Goal: GoalASCII, Wall: WallASCII, Solution: SolutionASCII, Visited: VisitedASCII, } )
Directions represents directions to look when printing wall characters. It is an array to make sure it cannot be changed and to allow easily making copies.
The various *UTF8 and *ASCII slices and the Syms* maps they make up represent strings to write based on a bitwise OR of adjacent cells. The bit positions come from the Directions array. Although the Empty*, Goal*, and Visited* slices contain the same character for every entry, they are left for symmetry and to allow whatever interesting uses you can come up with. See Neighbors().
1 0 . 2 3 3:down 2:right 1:up 0:left 0 none 1 left 2 up 3 up left 4 right 5 right left 6 right up 7 right up left 8 down 9 down left a down up b down up left c down right d down right left e down right up f down right up left
var ErrDimensions = errors.New(`dimensions do not match`)
ErrDimensions is returned from Overlay() when the dimensions of the two mazes do not match.
var ErrInvalidSize = errors.New(`invalid size`)
ErrInvalidSize is returned from ReadFrom() when the header line with the number of rows and columns is malformed.
var ErrLongLine = errors.New(`line too long`)
ErrLongLine is returned from ReadFrom() when a line is longer than the number of columns specified in the header.
Functions ¶
This section is empty.
Types ¶
type Coord ¶
type Coord struct {
I, J int
}
Coord represents a coordinate in a Maze. It was added along with Vec to simplify some operations. For an example see Neighbors().
type Maze ¶
type Maze [][]uint32
Maze is a 2D grid representing the navigable space of a maze. Originally Maze was a [][]bool to represent the walls. It quickly became apparent that having more options available opened up possibilities not just for solving but creating as well. It could have remained bool to simplify it, but then users would be forced to create copies more often. uint32 was picked over int to allow for atomic operations if the user feels so inclined. The switch also made for more PrettyPrint opportunities.
func New ¶
New returns a new *Maze of size rows x cols. The rows of the maze are contiguous in memory.
func ReadFrom ¶
ReadFrom creates an empty maze m and calls m.ReadFrom(r).
Example ¶
package main
import (
"fmt"
"os"
"strings"
"bitbucket.org/emg/maze"
)
func main() {
example := `21 21
########### #########
# # # # #
# # ### ### ##### ###
# # # # #
# # ##### ### ##### #
# # # # # #
### # # # # ##### ###
# # # # # #
# ### ########### # #
# # # # # #
# # # # # ######### #
# # # # # # #
# ####### # # ### # #
# # # # # #
##### ##### ### # ###
# # # # # #
# # ### ####### ### #
# # # # #
# ####### # # ### ###
# # # # #
################### #
21 21
x
x
`
m, err := maze.ReadFrom(strings.NewReader(example))
if err != nil {
fmt.Println(err)
}
m.PrettyPrint(os.Stdout, m.StringAtUTF8)
}
Output: ┌─┬───┬───╴◆┌───────┐ │ │ │ │ │ │ │ ╶─┘ ╶─┐ ├───╴ ╶─┤ │ │ │ │ │ │ ╵ ┌───┐ └─┤ ╶───┐ │ │ │ │ │ │ │ ├─╴ │ ╷ ╵ ╷ └───┐ └─┤ │ │ │ │ │ │ │ ╶─┤ ├─┬─┴─────┘ ╷ │ │ │ │ │ │ │ │ ╷ │ ╵ │ ┌─────┬─┘ │ │ │ │ │ │ │ │ │ └─┴───┘ │ ╷ ╶─┤ ╷ │ │ │ │ │ │ │ ├─┬─╴ ┌───┘ ├─╴ │ └─┤ │ │ │ │ │ │ │ ╵ ┌─┘ ╶─┬─┴─┐ └─╴ │ │ │ │ │ │ │ ╶─┴───┐ ╵ ╷ └─┐ ╶─┤ │ │ │ │ │ └───────┴───┴───┴─╴◆╵
func (*Maze) CellType ¶
CellType returns the least significant set bit in m at c. It is used to translate a cell value that may have multiple bits set to key for the Syms* maps.
func (*Maze) Extract ¶
Extract creates a new Maze and sets a cell to 1 if the correspsonding cell in m has bit number bitn set. It is useful for separating a solution from walls to write two files.
Example ¶
package main
import (
"os"
"strings"
"bitbucket.org/emg/maze"
)
var exampleMazeString = `21 21
########### #########
# # # # #
# # ### ### ##### ###
# # # # #
# # ##### ### ##### #
# # # # # #
### # # # # ##### ###
# # # # # #
# ### ########### # #
# # # # # #
# # # # # ######### #
# # # # # # #
# ####### # # ### # #
# # # # # #
##### ##### ### # ###
# # # # # #
# # ### ####### ### #
# # # # #
# ####### # # ### ###
# # # # #
################### #
`
var exampleSolutionString = `21 21
o
ooooo
o
ooooo
o
o
o
ooo ooo
o o o
o ooooooooo o
o o o
o o ooo
o o o
ooooooooo o
o
ooo
o
ooo
o
ooo
o
`
func main() {
s := exampleMazeString + exampleSolutionString
m, _ := maze.ReadFrom(strings.NewReader(s))
m.Extract(maze.WallBit).WriteTo(os.Stdout)
// Examples trim trailing whitespace from expected output. This is an
// open issue[0]. Comment this out for now so the test doesn't fail,
// but leave it to explain the example.
//
// [0] https://github.com/golang/go/issues/26460
//
// m.Extract(maze.SolutionBit).WriteTo(os.Stdout)
//
// Would Output:
// 21 21
// #
// #####
// #
// #####
// #
// #
// #
// ### ###
// # # #
// # ######### #
// # # #
// # # ###
// # # #
// ######### #
// #
// ###
// #
// ###
// #
// ###
// #
}
Output: 21 21 ########### ######### # # # # # # # ### ### ##### ### # # # # # # # ##### ### ##### # # # # # # # ### # # # # ##### ### # # # # # # # ### ########### # # # # # # # # # # # # # ######### # # # # # # # # # ####### # # ### # # # # # # # # ##### ##### ### # ### # # # # # # # # ### ####### ### # # # # # # # ####### # # ### ### # # # # # ################### #
func (*Maze) Neighbors ¶
Neighbors iterates through Directions checking the cell value at the neighboring cells. It checks the neighbors for the first set bit in cellType, and ORs the values together as explained in the comment for Directions. It is used to lookup symbols for pretty printing. Check the PrettyPrint() example functions for usage examples.
func (*Maze) Overlay ¶
Overlay left shifts every value in m2 and ORs it with the corresponding cell in m, placing the result in m. This is useful for reading in a separate solution and overlaying it on a maze. If the two mazes are not the same size ErrDimensions is returned, except for the special case of empty m. In that case m is set to a new Maze the same size as m2. This is useful for starting a series of overlays with an empty Maze so the first one does not have to be treated specially.
Example ¶
package main
import (
"os"
"strings"
"bitbucket.org/emg/maze"
)
var exampleMazeString = `21 21
########### #########
# # # # #
# # ### ### ##### ###
# # # # #
# # ##### ### ##### #
# # # # # #
### # # # # ##### ###
# # # # # #
# ### ########### # #
# # # # # #
# # # # # ######### #
# # # # # # #
# ####### # # ### # #
# # # # # #
##### ##### ### # ###
# # # # # #
# # ### ####### ### #
# # # # #
# ####### # # ### ###
# # # # #
################### #
`
var exampleGoalString = `21 21
@
@
`
var exampleSolutionString = `21 21
o
ooooo
o
ooooo
o
o
o
ooo ooo
o o o
o ooooooooo o
o o o
o o ooo
o o o
ooooooooo o
o
ooo
o
ooo
o
ooo
o
`
func main() {
m, _ := maze.ReadFrom(strings.NewReader(exampleMazeString))
s, _ := maze.ReadFrom(strings.NewReader(exampleSolutionString))
g, _ := maze.ReadFrom(strings.NewReader(exampleGoalString))
m.Overlay(s, maze.SolutionBit)
m.Overlay(g, maze.GoalBit)
// syms index bits: 3:solution 2:goal 1:wall
// least significant set bit determines symbol
syms := []string{
` `, `#`, `O`, ``, `.`,
}
m.PrettyPrint(os.Stdout,
func(c maze.Coord) string { return syms[m.CellType(c)] })
}
Output: ###########O######### # # #.....# # # # ###.### ##### ### # #..... # # # # #.##### ### ##### # # .# # # # # ###.# # # # ##### ### #...# # # #...# #.### ###########.#.# #. # # #.........#.# #.# # # #.#########.# #.# # #.# #...# #.#######.# # ###.# # #.........# # #.# # ##### ##### ### #.### # # # # #...# # # ### ####### ###.# # # # # ...# # ####### # # ###.### # # # #...# ###################O#
func (*Maze) OverlayAt ¶
OverlayAt performs the same bitwise ORing as Overlay but the position on m where m2 is overlayed can be supplied. Cell (0,0) of m2 is overlayed at cell topLeft of m. If topLeft is out of bounds or m2 does not fit in the supplied location ErrDimensions is returned.
func (*Maze) PrettyPrint ¶
PrettyPrint is used to print a maze in more interesting ways. For each cell in m it prints the result of calling stringAt() with the Coord that repsents that cell. stringAt() returns a string, not a rune, in order to be more versatile and allow e.g. double wide printing or special even/odd printing.
Example ¶
package main
import (
"os"
"strings"
"bitbucket.org/emg/maze"
)
var exampleMazeString = `21 21
########### #########
# # # # #
# # ### ### ##### ###
# # # # #
# # ##### ### ##### #
# # # # # #
### # # # # ##### ###
# # # # # #
# ### ########### # #
# # # # # #
# # # # # ######### #
# # # # # # #
# ####### # # ### # #
# # # # # #
##### ##### ### # ###
# # # # # #
# # ### ####### ### #
# # # # #
# ####### # # ### ###
# # # # #
################### #
`
var exampleGoalString = `21 21
@
@
`
var exampleSolutionString = `21 21
o
ooooo
o
ooooo
o
o
o
ooo ooo
o o o
o ooooooooo o
o o o
o o ooo
o o o
ooooooooo o
o
ooo
o
ooo
o
ooo
o
`
var exampleVisitedString = `21 21
x
xxxxx xxxxxxx
x x x
xxxxxxx x xxxxxxx
x x x x
x xxx xxx xxxxx x
x x x x x x
xxx x xxx xxxxx xxx
x x x x
xxx x x xxxxxxxxx x
x x x x x x
x x xxx x xxx
x x x x
xxxxxxxxx x x
x
xxx
x
xxx
x
xxx
x
`
func main() {
s := exampleMazeString + exampleGoalString + exampleSolutionString + exampleVisitedString
m, _ := maze.ReadFrom(strings.NewReader(s))
// Example using default StringAtUFT8() function
m.PrettyPrint(os.Stdout, m.StringAtUTF8)
}
Output: ┌─┬───┬───╴◆┌───────┐ │ │ │┏━━━┛│░░░░░░░│ │ │ ╶─┘┃╶─┐░├───╴░╶─┤ │ │┏━━━┛░░│░│░░░░░░░│ │ ╵┃┌───┐░└─┤░╶───┐░│ │ ┃│░░░│░░░│░░░░░│░│ ├─╴┃│░╷░╵░╷░└───┐░└─┤ │┏━┛│░│░░░│░░░░░│┏━┓│ │┃╶─┤░├─┬─┴─────┘┃╷┃│ │┃░░│░│░│┏━━━━━━━┛│┃│ │┃╷░│░╵░│┃┌─────┬─┘┃│ │┃│░│░░░│┃│ │┏━┛│ │┃└─┴───┘┃│ ╷ ╶─┤┃╷░│ │┗━━━━━━━┛│ │ │┃│░│ ├─┬─╴ ┌───┘ ├─╴ │┃└─┤ │ │ │ │ │┗━┓│ │ ╵ ┌─┘ ╶─┬─┴─┐ └─╴┃│ │ │ │ │ ┏━┛│ │ ╶─┴───┐ ╵ ╷ └─┐┃╶─┤ │ │ │ │┗━┓│ └───────┴───┴───┴─╴◆╵
Example (WideASCII) ¶
package main
import (
"os"
"strings"
"bitbucket.org/emg/maze"
)
var exampleMazeString = `21 21
########### #########
# # # # #
# # ### ### ##### ###
# # # # #
# # ##### ### ##### #
# # # # # #
### # # # # ##### ###
# # # # # #
# ### ########### # #
# # # # # #
# # # # # ######### #
# # # # # # #
# ####### # # ### # #
# # # # # #
##### ##### ### # ###
# # # # # #
# # ### ####### ### #
# # # # #
# ####### # # ### ###
# # # # #
################### #
`
var exampleGoalString = `21 21
@
@
`
var exampleSolutionString = `21 21
o
ooooo
o
ooooo
o
o
o
ooo ooo
o o o
o ooooooooo o
o o o
o o ooo
o o o
ooooooooo o
o
ooo
o
ooo
o
ooo
o
`
var exampleVisitedString = `21 21
x
xxxxx xxxxxxx
x x x
xxxxxxx x xxxxxxx
x x x x
x xxx xxx xxxxx x
x x x x x x
xxx x xxx xxxxx xxx
x x x x
xxx x x xxxxxxxxx x
x x x x x x
x x xxx x xxx
x x x x
xxxxxxxxx x x
x
xxx
x
xxx
x
xxx
x
`
func main() {
s := exampleMazeString + exampleGoalString + exampleSolutionString + exampleVisitedString
m, _ := maze.ReadFrom(strings.NewReader(s))
// Assume this is a function defined elsewhere. It's defined here using
// a function literal so it's included in the example.
wideASCII := func(m *maze.Maze, c maze.Coord) string {
sym := maze.SymsASCII[m.CellType(c)][m.Neighbors(c, m.CellType(c))]
if c.J%2 == 1 {
if m.CellType(c) == maze.Wall {
sym += sym + sym
} else {
sym = ` ` + sym + ` `
}
}
return sym
}
// Example using a closure to call a function that takes a *maze.Maze.
m.PrettyPrint(os.Stdout, func(c maze.Coord) string { return wideASCII(m, c) })
}
Output: +---+-------+-------- @ +---------------+ | | | * * * * * | . . . . . . . | | | ----+ * ----+ . +-------- . ----+ | | * * * * * . . | . | . . . . . . . | | | * +-------+ . +---+ . --------+ . | | * | . . . | . . . | . . . . . | . | +---- * | . | . | . | . +-------+ . +---+ | * * * | . | . . . | . . . . . | * * * | | * ----+ . +---+---+-----------+ * | * | | * . . | . | . | * * * * * * * * * | * | | * | . | . | . | * +-----------+---+ * | | * | . | . . . | * | | * * * | | * +---+-------+ * | | ----+ * | . | | * * * * * * * * * | | | * | . | +---+---- +-------+ +---- | * +---+ | | | | | * * * | | | +---+ ----+---+---+ +---- * | | | | | * * * | | ----+-------+ | | +---+ * ----+ | | | | * * * | +---------------+-------+-------+---- @ |
Example (WideHash) ¶
package main
import (
"os"
"strings"
"bitbucket.org/emg/maze"
)
var exampleMazeString = `21 21
########### #########
# # # # #
# # ### ### ##### ###
# # # # #
# # ##### ### ##### #
# # # # # #
### # # # # ##### ###
# # # # # #
# ### ########### # #
# # # # # #
# # # # # ######### #
# # # # # # #
# ####### # # ### # #
# # # # # #
##### ##### ### # ###
# # # # # #
# # ### ####### ### #
# # # # #
# ####### # # ### ###
# # # # #
################### #
`
func main() {
m, _ := maze.ReadFrom(strings.NewReader(exampleMazeString))
// Example using a function literal
sAt := func(c maze.Coord) string { return []string{` `, `##`}[m.At(c)] }
m.PrettyPrint(os.Stdout, sAt)
}
Output: ###################### ################## ## ## ## ## ## ## ## ###### ###### ########## ###### ## ## ## ## ## ## ## ########## ###### ########## ## ## ## ## ## ## ## ###### ## ## ## ## ########## ###### ## ## ## ## ## ## ## ###### ###################### ## ## ## ## ## ## ## ## ## ## ## ## ## ################## ## ## ## ## ## ## ## ## ## ############## ## ## ###### ## ## ## ## ## ## ## ## ########## ########## ###### ## ###### ## ## ## ## ## ## ## ## ###### ############## ###### ## ## ## ## ## ## ## ############## ## ## ###### ###### ## ## ## ## ## ###################################### ##
func (*Maze) ReadFrom ¶
ReadFrom implements io.ReaderFrom. It continually calls ReadOneFrom() then Overlay() incrementing the bit number passed to Overlay() for each succesive maze.
func (*Maze) ReadOneFrom ¶
ReadOneFrom reads the header line from r, two integers separated by whitespace signifying the number of rows and columns, and creates a new Maze of the given size. It then reads from r line by line and sets the corresponding cells in a maze for runes that are not white space. It only reads the number of lines specified, instead of reading until EOF, so that it can be used multiple times on the same io.Reader (e.g. ReadFrom() overlaying multiple layers). Short lines and EOF before reading the expected number of lines are accepted and treated as empty spaces. If the header is malformed it will return ErrInvalidSize. If there are too many characters on a line it will return ErrLongLine.
func (*Maze) SafeAt ¶
SafeAt does a bounds check on c, returning 0 if c is out of bounds, and the result of m.At(c) otherwise.
func (*Maze) StringAtUTF8 ¶
StringAtUTF8 returns the character for each cell based on SymsUTF8. It is provided as a default and example function to be used with PrettyPrint(). It uses CellType() to determine the key for the SymsUTF8 map. This looks best when using a square font e.g. http://strlen.com/square/
func (*Maze) WriteOneTo ¶
WriteOneTo writes m to w in its canonical form. It writes a header line, two integers separated by whitespace signifying the number of rows and columns, then it writes rows number of lines each with columns number of characters. Each cell is a space if 0 and a hash if non-0. To differentiate between which bits are set in a maze use Extract() first. There is no version of WriteTo() that takes a stringAt func in order to ensure the output is canonical, i.e. single character per cell using hash and space. Use WriteTo() to write multiple layers/bits.
func (*Maze) WriteTo ¶
WriteTo implements io.Writer. It finds the most significant bit set in any cell in m then writes a series of mazes, one for each bit position, to w. It uses Extract() and WriteOneTo() to do so. The mazes can later be recombined using ReadFrom().
Example ¶
package main
import (
"os"
"strings"
"bitbucket.org/emg/maze"
)
func main() {
exampleMazeString := `21 21
+-+---+---- +-------+
| | | | |
| | --+ --+ +---- --+
| | | | |
| | +---+ +-+ ----+ |
| | | | | |
+-- | | | | +---+ +-+
| | | | | |
| --+ +-+-+-----+ | |
| | | | | |
| | | | | +-----+-+ |
| | | | | | |
| +-+---+ | | --+ | |
| | | | | |
+-+-- +---+ +-- | +-+
| | | | | |
| | +-+ --+-+-+ +-- |
| | | | |
| --+---+ | | +-+ --+
| | | | |
+-------+---+---+-- |
`
m, _ := maze.ReadFrom(strings.NewReader(exampleMazeString))
// Ideally this would write multiple layers analagous to the ReadFrom
// example but examples trim trailing whitespace from expected output.
// This is an open issue[0].
//
// [0] https://github.com/golang/go/issues/26460
m.WriteTo(os.Stdout)
}
Output: 21 21 ########### ######### # # # # # # # ### ### ##### ### # # # # # # # ##### ### ##### # # # # # # # ### # # # # ##### ### # # # # # # # ### ########### # # # # # # # # # # # # # ######### # # # # # # # # # ####### # # ### # # # # # # # # ##### ##### ### # ### # # # # # # # # ### ####### ### # # # # # # # ####### # # ### ### # # # # # ################### #
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
cmd
|
|
|
mcreate
mcreate is an example naive maze generator used to demonstrate usage of bitbucket.org/emg/maze.
|
mcreate is an example naive maze generator used to demonstrate usage of bitbucket.org/emg/maze. |
|
mpretty
mpretty is an example pretty printer used to demonstrate usage of bitbucket.org/emg/maze.
|
mpretty is an example pretty printer used to demonstrate usage of bitbucket.org/emg/maze. |
|
msolve
msolve is an example naive maze solver used to demonstrate usage of bitbucket.org/emg/maze.
|
msolve is an example naive maze solver used to demonstrate usage of bitbucket.org/emg/maze. |