10
\$\begingroup\$
/*
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?

\$\endgroup\$
  • 2
    \$\begingroup\$ Looks very good to me. To be perfect you could produce the test and benchmark files too... \$\endgroup\$ – Denys Séguret Sep 12 '12 at 14:12
  • \$\begingroup\$ very nice, what algorithm are you using? \$\endgroup\$ – Steven Ferrer Oct 9 '17 at 8:20
2
\$\begingroup\$

General notes:

  • the code would benefit from splitting it into more methods,
  • go uses camelCaseConvention, not onlylowerletters.

Now, some particulars.

stack = append(stack, room{0, 0})

You can use start variable here.

func (r room) neighbors() []room {

In this function, it'd be more idiomatic to use switch { ... } instead of sequence of ifs. Same for the if-elses in the main().

Also it may be more efficient to have a single global re-used [4]room array and have neighbors/nonvisitedneighbors returns slices on it instead of make-ing a new one each call.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.