/*
Create a random maze
*/
package main
import (
"fmt"
"math/rand"
"time"
)
const (
mazewidth = 15
mazeheight = 15
)
type room struct {
x, y int
}
func (r room) String() string {
return fmt.Sprintf("(%d,%d)", r.x, r.y)
}
func (r room) id() int {
return (r.y * mazewidth) + r.x
}
// whetwher walls are open or not.
// There are (num_rooms * 2) walls. Some are on borders, but nevermind them ;)
type wallregister [mazewidth * mazeheight * 2]bool
var wr = wallregister{}
// rooms are visited or not
type roomregister [mazewidth * mazeheight]bool
var rr = roomregister{}
func main() {
rand.Seed(time.Now().Unix())
stack := make([]room, 0, mazewidth*mazeheight)
start := room{0, 0}
// mark start position visited
rr[start.id()] = true
// put start position on stack
stack = append(stack, room{0, 0})
for len(stack) > 0 {
// current node is in top of the stack
current := stack[len(stack)-1]
// Slice of neighbors we can move
availneighbrs := current.nonvisitedneighbors()
// cannot move. Remove this room from stack and continue
if len(availneighbrs) < 1 {
stack = stack[:len(stack)-1]
continue
}
// pick a random room to move.
next := availneighbrs[rand.Intn(len(availneighbrs))]
// mark next visited
rr[next.id()] = true
// open wall between current and next:
first, second := orderrooms(current, next)
// second is either at the right or bottom of first.
if second.x == first.x+1 {
wr[first.id()*2] = true
} else if second.y == first.y+1 {
wr[first.id()*2+1] = true
} else { // probably impossible or maybe not...
panic("Wot?!?")
}
// push next to stack
stack = append(stack, next)
}
// print maze
// print upper border
for x := 0; x < mazewidth; x++ {
if x == 0 {
fmt.Printf(" ")
} else {
fmt.Printf("_ ")
}
}
fmt.Println()
for y := 0; y < mazeheight; y++ {
fmt.Printf("|") // left border
for x := 0; x < mazewidth; x++ {
id := room{x, y}.id()
right := "|"
bottom := "_"
if wr[id*2] {
right = " "
}
if wr[id*2+1] {
bottom = " "
}
if x == mazewidth-1 && y == mazeheight-1 {
right = " "
}
fmt.Printf("%s%s", bottom, right)
}
fmt.Println()
}
}
// return slice of neighbor rooms
func (r room) neighbors() []room {
rslice := make([]room, 0, 4)
if r.x < mazewidth-1 {
rslice = append(rslice, room{r.x + 1, r.y})
}
if r.x > 0 {
rslice = append(rslice, room{r.x - 1, r.y})
}
if r.y < mazeheight-1 {
rslice = append(rslice, room{r.x, r.y + 1})
}
if r.y > 0 {
rslice = append(rslice, room{r.x, r.y - 1})
}
return rslice
}
// return rooms that are not visited yet
func (r room) nonvisitedneighbors() []room {
rslice := make([]room, 0, 4)
for _, r := range r.neighbors() {
if rr[r.id()] == false {
rslice = append(rslice, r)
}
}
return rslice
}
// order to rooms by closeness to origin (upperleft)
func orderrooms(room1, room2 room) (room, room) {
dist1 := room1.x*room1.x + room1.y*room1.y
dist2 := room2.x*room2.x + room2.y*room2.y
if dist1 < dist2 {
return room1, room2
}
return room2, room1
}
http://play.golang.org/p/8W_FbBfUjb (You can run it here. But since time.Now() is fixed there, you will always get same maze.)
In any aspect of it, how does it look?