// Maze generation program using Kruskal’s algorithm with random edge
// weights.
package main

import (
	"io"
	"log"
	"math/rand"
	"os"
	"strconv"
)

type Cell int32

const maxwidth = 65536

func (c Cell) row() int             { return int(c / maxwidth) }
func (c Cell) col() int             { return int(c % maxwidth) }
func (c Cell) below() Cell          { return c + maxwidth }
func (c Cell) right() Cell          { return c + 1 }
func Cell_at(row int, col int) Cell { return Cell(row*maxwidth + col) }

// Data structure for rapidly determining whether two maze cells are
// already connected.
type Unionfind map[Cell]Cell

func (u Unionfind) root(c Cell) (root Cell) {
	parent, ok := u[c]
	if !ok {
		return c
	}
	root = u.root(parent)
	u[c] = root
	return
}

func (u Unionfind) Connect(start, end Cell) {
	u[u.root(start)] = u.root(end)
}

func (u Unionfind) Connected(a, b Cell) bool {
	return u.root(a) == u.root(b)
}

// Maze contains two two-dimensional arrays of booleans (slices of
// horizontal rows, which are slices of booleans).  Each boolean is
// true if a wall exists in the corresponding position.  Because the
// ultimate destination is an array of character cells, each of which
// can contain walls on the top, left, bottom, and/or right, the array
// of vertical walls contains one more row and one less column than
// the array of horizontal walls.
type Maze struct {
	Horizontal, Vertical [][]bool
}

func New(width, height int) Maze {
	h := trues(width+1, height)
	v := trues(width, height+1)

	// Shave the outside of the maze.
	// i.e. convert
	// ╋╋╋╋      ┏┳┳┓
	// ╋╋╋╋	     ┣╋╋┫
	// ╋╋╋╋ into ┣╋╋┫
	// ╋╋╋╋	     ┗┻┻┛
	for r := 0; r < height; r++ {
		h[r][0] = false
		h[r][width] = false
	}

	for c := 0; c < width; c++ {
		v[0][c] = false
		v[height][c] = false
	}

	// Add in and out doors.
	h[0][1] = false
	h[height-1][width-1] = false

	// Dig out the maze as such; first, build a slice of all
	// internal walls.
	type wall struct {
		cell     Cell
		vertical bool
	}

	walls := []wall{}
	for r := 1; r < height-1; r++ {
		for c := 1; c < width; c++ {
			walls = append(walls, wall{cell: Cell_at(r, c), vertical: false})
		}
	}

	for r := 1; r < height; r++ {
		for c := 1; c < width-1; c++ {
			walls = append(walls, wall{cell: Cell_at(r, c), vertical: true})
		}
	}

	// Now, dig out the walls in random order, except where that
	// would create a cycle.  This is precisely Kruskal’s
	// algorithm.
	state := Unionfind{}
	for _, i := range rand.Perm(len(walls)) {
		w := walls[i]
		cell_b := w.cell.below()
		if w.vertical {
			cell_b = w.cell.right()
		}

		if state.Connected(w.cell, cell_b) {
			continue
		}

		state.Connect(w.cell, cell_b)

		to_demolish := h
		if w.vertical {
			to_demolish = v
		}
		to_demolish[w.cell.row()][w.cell.col()] = false
	}

	return Maze{Horizontal: h, Vertical: v}
}

func trues(width, height int) [][]bool {
	trues := [][]bool{}
	for y := 0; y < height; y++ {
		line := []bool{}
		for x := 0; x < width; x++ {
			line = append(line, true)
		}
		trues = append(trues, line)
	}
	return trues
}

type context struct {
	up, down, left, right bool
}

var glyphs = map[context][]byte{}

func init() {
	chars := "━┃┏┓┗┛┣┫┳┻╋╸╺╹╻ "
	lefts := "1..1.1.11111...." // 1 if line touches left, . otherwise
	right := "1.1.1.1.111.1..." // mutatis mutandis
	topbs := ".1..1111.11..1.."
	bottm := ".111..111.1...1."

	for i, glyph := range []rune(chars) {
		k := context{
			up:    topbs[i] == '1',
			down:  bottm[i] == '1',
			left:  lefts[i] == '1',
			right: right[i] == '1',
		}
		glyphs[k] = []byte(string(glyph))
	}
}

func (m Maze) Show(output io.Writer) {
	h, v := m.Horizontal, m.Vertical

	for r := 0; r < len(h); r++ {
		s := []byte{}
		for c := 0; c < len(v[0]); c++ {
			k := context{
				up:    v[r][c],
				down:  v[r+1][c],
				left:  h[r][c],
				right: h[r][c+1],
			}
			s = append(s, glyphs[k]...)
		}
		output.Write(append(s, '\n'))
	}
}

func main() {
	var m Maze

	rand.Seed(int64(os.Getpid()))

	if len(os.Args) == 1 {
		m = New(64, 16)
	} else {
		var height int
		width, err := strconv.Atoi(os.Args[1])
		if err == nil {
			height, err = strconv.Atoi(os.Args[2])
		}
		if err != nil {
			log.Fatal(err)
		}
		m = New(width, height)
	}

	m.Show(os.Stdout)
}