<commit_before>// many ideas here from articles found at http://www.roguebasin.com/

package main

import (
	"sort"
)

type dungeon struct {
	Gen   dungen
	Cells []cell
}

type cell struct {
	T        terrain
	Explored bool
}

type terrain int

const (
	WallCell terrain = iota
	FreeCell
)

type dungen int

const (
	GenCaveMap dungen = iota
	GenRoomMap
	GenCellularAutomataCaveMap
	GenCaveMapTree
	GenRuinsMap
	GenBSPMap
)

func (dg dungen) Use(g *game) {
	switch dg {
	case GenCaveMap:
		g.GenCaveMap(DungeonHeight, DungeonWidth)
	case GenRoomMap:
		g.GenRoomMap(DungeonHeight, DungeonWidth)
	case GenCellularAutomataCaveMap:
		g.GenCellularAutomataCaveMap(DungeonHeight, DungeonWidth)
	case GenCaveMapTree:
		g.GenCaveMapTree(DungeonHeight, DungeonWidth)
	case GenRuinsMap:
		g.GenRuinsMap(DungeonHeight, DungeonWidth)
	case GenBSPMap:
		g.GenBSPMap(DungeonHeight, DungeonWidth)
	}
	g.Dungeon.Gen = dg
	g.Stats.DLayout[g.Depth] = dg.String()
}

func (dg dungen) String() (text string) {
	switch dg {
	case GenCaveMap:
		text = "OC"
	case GenRoomMap:
		text = "BR"
	case GenCellularAutomataCaveMap:
		text = "EC"
	case GenCaveMapTree:
		text = "TC"
	case GenRuinsMap:
		text = "RR"
	case GenBSPMap:
		text = "AT"
	}
	return text
}

func (dg dungen) Description() (text string) {
	switch dg {
	case GenCaveMap:
		text = "open cave"
	case GenRoomMap:
		text = "big rooms"
	case GenCellularAutomataCaveMap:
		text = "eight cave"
	case GenCaveMapTree:
		text = "tree-like cave"
	case GenRuinsMap:
		text = "ruined rooms"
	case GenBSPMap:
		text = "deserted town"
	}
	return text
}

type room struct {
	pos position
	w   int
	h   int
}

func (d *dungeon) Cell(pos position) cell {
	return d.Cells[pos.idx()]
}

func (d *dungeon) Border(pos position) bool {
	return pos.X == DungeonWidth-1 || pos.Y == DungeonHeight-1 || pos.X == 0 || pos.Y == 0
}

func (d *dungeon) SetCell(pos position, t terrain) {
	d.Cells[pos.idx()].T = t
}

func (d *dungeon) SetExplored(pos position) {
	d.Cells[pos.idx()].Explored = true
}

func roomDistance(r1, r2 room) int {
	return Abs(r1.pos.X-r2.pos.X) + Abs(r1.pos.Y-r2.pos.Y)
}

func nearRoom(rooms []room, r room) room {
	closest := rooms[0]
	d := roomDistance(r, closest)
	for _, nextRoom := range rooms {
		nd := roomDistance(r, nextRoom)
		if nd < d {
			n := RandInt(10)
			if n > 3 {
				d = nd
				closest = nextRoom
			}
		}
	}
	return closest
}

func nearestRoom(rooms []room, r room) room {
	closest := rooms[0]
	d := roomDistance(r, closest)
	for _, nextRoom := range rooms {
		nd := roomDistance(r, nextRoom)
		if nd < d {
			n := RandInt(10)
			if n > 0 {
				d = nd
				closest = nextRoom
			}
		}
	}
	return closest
}

func intersectsRoom(rooms []room, r room) bool {
	for _, rr := range rooms {
		if (r.pos.X+r.w-1 >= rr.pos.X && rr.pos.X+rr.w-1 >= r.pos.X) &&
			(r.pos.Y+r.h-1 >= rr.pos.Y && rr.pos.Y+rr.h-1 >= r.pos.Y) {
			return true
		}
	}
	return false
}

func (d *dungeon) connectRooms(r1, r2 room) {
	x := r1.pos.X
	if x < r2.pos.X {
		x += r1.w - 1
	}
	y := r1.pos.Y
	if y < r2.pos.Y {
		y += r1.h - 1
	}
	d.SetCell(position{x, y}, FreeCell)
	count := 0
	for {
		count++
		if count > 1000 {
			panic("ConnectRooms")
		}
		if x < r2.pos.X {
			x++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x > r2.pos.X {
			x--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if y < r2.pos.Y {
			y++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if y > r2.pos.Y {
			y--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		break
	}
	d.SetCell(r2.pos, FreeCell)
}

func (d *dungeon) connectRoomsDiagonally(r1, r2 room) {
	x := r1.pos.X
	if x < r2.pos.X {
		x += r1.w - 1
	}
	y := r1.pos.Y
	if y < r2.pos.Y {
		y += r1.h - 1
	}
	d.SetCell(position{x, y}, FreeCell)
	count := 0
	for {
		count++
		if count > 1000 {
			panic("ConnectRooms")
		}
		if x < r2.pos.X && y < r2.pos.Y {
			x++
			d.SetCell(position{x, y}, FreeCell)
			y++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x > r2.pos.X && y < r2.pos.Y {
			x--
			d.SetCell(position{x, y}, FreeCell)
			y++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x > r2.pos.X && y > r2.pos.Y {
			x--
			d.SetCell(position{x, y}, FreeCell)
			y--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x < r2.pos.X && y > r2.pos.Y {
			x++
			d.SetCell(position{x, y}, FreeCell)
			y--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x < r2.pos.X {
			x++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x > r2.pos.X {
			x--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if y < r2.pos.Y {
			y++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if y > r2.pos.Y {
			y--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		break
	}
	d.SetCell(r2.pos, FreeCell)
}

func (d *dungeon) Area(area []position, pos position, radius int) []position {
	area = area[:0]
	for x := pos.X - radius; x <= pos.X+radius; x++ {
		for y := pos.Y - radius; y <= pos.Y+radius; y++ {
			pos := position{x, y}
			if pos.valid() {
				area = append(area, pos)
			}
		}
	}
	return area
}

func (d *dungeon) ConnectRoomsShortestPath(r1, r2 room) {
	var r1pos, r2pos position
	r1pos.X = r1.pos.X + RandInt(r1.w)
	if r1pos.X < r2.pos.X {
		r1pos.X = r1.pos.X + r1.w - 1
	}
	r1pos.Y = r1.pos.Y + RandInt(r1.h)
	if r1pos.Y < r2.pos.Y {
		r1pos.Y = r1.pos.Y + r1.h - 1
	}
	r2pos.X = r2.pos.X + RandInt(r2.w)
	if r2pos.X < r1.pos.X {
		r2pos.X = r2.pos.X + r2.w - 1
	}
	r2pos.Y = r2.pos.Y + RandInt(r2.h)
	if r2pos.Y < r1.pos.Y {
		r2pos.Y = r2.pos.Y + r2.h - 1
	}
	mp := &dungeonPath{dungeon: d}
	path, _, _ := AstarPath(mp, r1pos, r2pos)
	for _, pos := range path {
		d.SetCell(pos, FreeCell)
	}
}

func (d *dungeon) ConnectIsolatedRoom(doorpos position) {
	for i := 0; i < 200; i++ {
		pos := d.FreeCell()
		dp := &dungeonPath{dungeon: d, wcost: unreachable}
		path, _, _ := AstarPath(dp, pos, doorpos)
		wall := false
		for _, pos := range path {
			if d.Cell(pos).T == WallCell {
				wall = true
				break
			}
		}
		if !wall {
			continue
		}
		for _, pos := range path {
			d.SetCell(pos, FreeCell)
		}
		break
	}
}

func (d *dungeon) DigRoom(r room) {
	for i := r.pos.X; i < r.pos.X+r.w; i++ {
		for j := r.pos.Y; j < r.pos.Y+r.h; j++ {
			rpos := position{i, j}
			if rpos.valid() {
				d.SetCell(rpos, FreeCell)
			}
		}
	}
}

func (d *dungeon) PutCols(r room) {
	for i := r.pos.X + 1; i < r.pos.X+r.w-1; i += 2 {
		for j := r.pos.Y + 1; j < r.pos.Y+r.h-1; j += 2 {
			rpos := position{i, j}
			if rpos.valid() {
				d.SetCell(rpos, WallCell)
			}
		}
	}
}

func (d *dungeon) PutDiagCols(r room) {
	n := RandInt(2)
	for i := r.pos.X + 1; i < r.pos.X+r.w-1; i++ {
		m := n
		for j := r.pos.Y + 1; j < r.pos.Y+r.h-1; j++ {
			rpos := position{i, j}
			if rpos.valid() && m%2 == 0 {
				d.SetCell(rpos, WallCell)
			}
			m++
		}
		n++
	}
}

func (d *dungeon) IsAreaFree(pos position, h, w int) bool {
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() || d.Cell(rpos).T != FreeCell {
				return false
			}
		}
	}
	return true
}

func (d *dungeon) RoomDigCanditate(pos position, h, w int) (ret bool) {
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() {
				return false
			}
			if d.Cell(rpos).T == FreeCell {
				ret = true
			}
		}
	}
	return ret
}

func (d *dungeon) IsolatedRoomDigCanditate(pos position, h, w int) (ret bool) {
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() {
				return false
			}
			if d.Cell(rpos).T == FreeCell {
				return false
			}
		}
	}
	return true
}

func (d *dungeon) DigArea(pos position, h, w int) {
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() {
				continue
			}
			d.SetCell(rpos, FreeCell)
		}
	}
}

func (d *dungeon) BlockArea(pos position, h, w int) {
	// not used now
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() {
				continue
			}
			d.SetCell(rpos, WallCell)
		}
	}
}

func (d *dungeon) BuildRoom(pos position, w, h int, outside bool) map[position]bool {
	spos := position{pos.X - 1, pos.Y - 1}
	if outside && !d.IsAreaFree(spos, h+2, w+2) {
		return nil
	}
	for i := pos.X; i < pos.X+w; i++ {
		d.SetCell(position{i, pos.Y}, WallCell)
		d.SetCell(position{i, pos.Y + h - 1}, WallCell)
	}
	for i := pos.Y; i < pos.Y+h; i++ {
		d.SetCell(position{pos.X, i}, WallCell)
		d.SetCell(position{pos.X + w - 1, i}, WallCell)
	}
	if RandInt(2) == 0 || !outside {
		n := RandInt(2)
		for x := pos.X + 1; x < pos.X+w-1; x++ {
			m := n
			for y := pos.Y + 1; y < pos.Y+h-1; y++ {
				if m%2 == 0 {
					d.SetCell(position{x, y}, WallCell)
				}
				m++
			}
			n++
		}
	} else {
		n := RandInt(2)
		m := RandInt(2)
		//if n == 0 && m == 0 {
		//// round room
		//d.SetCell(pos, FreeCell)
		//d.SetCell(position{pos.X, pos.Y + h - 1}, FreeCell)
		//d.SetCell(position{pos.X + w - 1, pos.Y}, FreeCell)
		//d.SetCell(position{pos.X + w - 1, pos.Y + h - 1}, FreeCell)
		//}
		for x := pos.X + 1 + m; x < pos.X+w-1; x += 2 {
			for y := pos.Y + 1 + n; y < pos.Y+h-1; y += 2 {
				d.SetCell(position{x, y}, WallCell)
			}
		}

	}
	area := make([]position, 9)
	if outside {
		for _, p := range [4]position{pos, {pos.X, pos.Y + h - 1}, {pos.X + w - 1, pos.Y}, {pos.X + w - 1, pos.Y + h - 1}} {
			if d.WallAreaCount(area, p, 1) == 4 {
				d.SetCell(p, FreeCell)
			}
		}
	}
	doorsc := [4]position{
		position{pos.X + w/2, pos.Y},
		position{pos.X + w/2, pos.Y + h - 1},
		position{pos.X, pos.Y + h/2},
		position{pos.X + w - 1, pos.Y + h/2},
	}
	doors := make(map[position]bool)
	for i := 0; i < 3+RandInt(2); i++ {
		dpos := doorsc[RandInt(4)]
		doors[dpos] = true
		d.SetCell(dpos, FreeCell)
	}
	return doors
}

func (d *dungeon) BuildSomeRoom(w, h int) map[position]bool {
	for i := 0; i < 200; i++ {
		pos := d.FreeCell()
		doors := d.BuildRoom(pos, w, h, true)
		if doors != nil {
			return doors
		}
	}
	return nil
}

func (d *dungeon) DigSomeRoom(w, h int) map[position]bool {
	for i := 0; i < 200; i++ {
		pos := d.FreeCell()
		dpos := position{pos.X - 1, pos.Y - 1}
		if !d.RoomDigCanditate(dpos, h+2, w+2) {
			continue
		}
		d.DigArea(dpos, h+2, w+2)
		doors := d.BuildRoom(pos, w, h, true)
		if doors != nil {
			return doors
		}
	}
	return nil
}

func (d *dungeon) DigIsolatedRoom(w, h int) map[position]bool {
	for i := 0; i < 3000; i++ {
		pos := d.WallCell()
		dpos := position{pos.X - 1, pos.Y - 1}
		if !d.IsolatedRoomDigCanditate(dpos, h+2, w+2) {
			continue
		}
		d.DigArea(pos, h, w)
		doors := d.BuildRoom(pos, w, h, false)
		if doors != nil {
			return doors
		}
	}
	return nil
}

func (d *dungeon) ResizeRoom(r room) room {
	if DungeonWidth-r.pos.X < r.w {
		r.w = DungeonWidth - r.pos.X
	}
	if DungeonHeight-r.pos.Y < r.h {
		r.h = DungeonHeight - r.pos.Y
	}
	return r
}

func (g *game) GenRuinsMap(h, w int) {
	d := &dungeon{}
	d.Cells = make([]cell, h*w)
	rooms := []room{}
	for i := 0; i < 43; i++ {
		var ro room
		count := 100
		for count > 0 {
			count--
			ro = room{
				pos: position{RandInt(w - 1), RandInt(h - 1)},
				w:   3 + RandInt(5),
				h:   2 + RandInt(3)}
			ro = d.ResizeRoom(ro)
			if !intersectsRoom(rooms, ro) {
				break
			}
		}

		d.DigRoom(ro)
		if RandInt(60) == 0 {
			if RandInt(2) == 0 {
				d.PutCols(ro)
			} else {
				d.PutDiagCols(ro)
			}
		}
		if len(rooms) > 0 {
			r := RandInt(100)
			if r > 75 {
				d.connectRooms(nearRoom(rooms, ro), ro)
			} else if r > 25 {
				d.ConnectRoomsShortestPath(nearRoom(rooms, ro), ro)
			} else {
				d.connectRoomsDiagonally(nearRoom(rooms, ro), ro)
			}
		}
		rooms = append(rooms, ro)
	}
	doors := d.DigSomeRooms(5)
	g.Dungeon = d
	g.Fungus = make(map[position]vegetation)
	g.DigFungus(1 + RandInt(2))
	g.PutDoors(30)
	for pos := range doors {
		if g.DoorCandidate(pos) && RandInt(100) > 20 {
			g.Doors[pos] = true
		}
	}
}

func (g *game) DigFungus(n int) {
	d := g.Dungeon
	fungus := g.Foliage(DungeonHeight, DungeonWidth)
	for i := 0; i < 100; i++ {
		if n <= 0 {
			break
		}
		pos := d.FreeCell()
		if _, ok := fungus[pos]; ok {
			continue
		}
		conn, count := d.Connected(pos, func(npos position) bool {
			_, ok := fungus[npos]
			return ok && d.IsFreeCell(npos)
		})
		if count < 3 {
			continue
		}
		dig := RandInt(2) == 0
		for pos := range conn {
			if dig {
				d.SetCell(pos, FreeCell)
			}
			g.Fungus[pos] = foliage
		}
		n--
	}
}

type roomSlice []room

func (rs roomSlice) Len() int      { return len(rs) }
func (rs roomSlice) Swap(i, j int) { rs[i], rs[j] = rs[j], rs[i] }
func (rs roomSlice) Less(i, j int) bool {
	return rs[i].pos.Y < rs[j].pos.Y || rs[i].pos.Y == rs[j].pos.Y && rs[i].pos.X < rs[j].pos.X<commit_msg>always dig when adding fungus in ruin and tree-like cave maps<commit_after>// many ideas here from articles found at http://www.roguebasin.com/

package main

import (
	"sort"
)

type dungeon struct {
	Gen   dungen
	Cells []cell
}

type cell struct {
	T        terrain
	Explored bool
}

type terrain int

const (
	WallCell terrain = iota
	FreeCell
)

type dungen int

const (
	GenCaveMap dungen = iota
	GenRoomMap
	GenCellularAutomataCaveMap
	GenCaveMapTree
	GenRuinsMap
	GenBSPMap
)

func (dg dungen) Use(g *game) {
	switch dg {
	case GenCaveMap:
		g.GenCaveMap(DungeonHeight, DungeonWidth)
	case GenRoomMap:
		g.GenRoomMap(DungeonHeight, DungeonWidth)
	case GenCellularAutomataCaveMap:
		g.GenCellularAutomataCaveMap(DungeonHeight, DungeonWidth)
	case GenCaveMapTree:
		g.GenCaveMapTree(DungeonHeight, DungeonWidth)
	case GenRuinsMap:
		g.GenRuinsMap(DungeonHeight, DungeonWidth)
	case GenBSPMap:
		g.GenBSPMap(DungeonHeight, DungeonWidth)
	}
	g.Dungeon.Gen = dg
	g.Stats.DLayout[g.Depth] = dg.String()
}

func (dg dungen) String() (text string) {
	switch dg {
	case GenCaveMap:
		text = "OC"
	case GenRoomMap:
		text = "BR"
	case GenCellularAutomataCaveMap:
		text = "EC"
	case GenCaveMapTree:
		text = "TC"
	case GenRuinsMap:
		text = "RR"
	case GenBSPMap:
		text = "AT"
	}
	return text
}

func (dg dungen) Description() (text string) {
	switch dg {
	case GenCaveMap:
		text = "open cave"
	case GenRoomMap:
		text = "big rooms"
	case GenCellularAutomataCaveMap:
		text = "eight cave"
	case GenCaveMapTree:
		text = "tree-like cave"
	case GenRuinsMap:
		text = "ruined rooms"
	case GenBSPMap:
		text = "deserted town"
	}
	return text
}

type room struct {
	pos position
	w   int
	h   int
}

func (d *dungeon) Cell(pos position) cell {
	return d.Cells[pos.idx()]
}

func (d *dungeon) Border(pos position) bool {
	return pos.X == DungeonWidth-1 || pos.Y == DungeonHeight-1 || pos.X == 0 || pos.Y == 0
}

func (d *dungeon) SetCell(pos position, t terrain) {
	d.Cells[pos.idx()].T = t
}

func (d *dungeon) SetExplored(pos position) {
	d.Cells[pos.idx()].Explored = true
}

func roomDistance(r1, r2 room) int {
	return Abs(r1.pos.X-r2.pos.X) + Abs(r1.pos.Y-r2.pos.Y)
}

func nearRoom(rooms []room, r room) room {
	closest := rooms[0]
	d := roomDistance(r, closest)
	for _, nextRoom := range rooms {
		nd := roomDistance(r, nextRoom)
		if nd < d {
			n := RandInt(10)
			if n > 3 {
				d = nd
				closest = nextRoom
			}
		}
	}
	return closest
}

func nearestRoom(rooms []room, r room) room {
	closest := rooms[0]
	d := roomDistance(r, closest)
	for _, nextRoom := range rooms {
		nd := roomDistance(r, nextRoom)
		if nd < d {
			n := RandInt(10)
			if n > 0 {
				d = nd
				closest = nextRoom
			}
		}
	}
	return closest
}

func intersectsRoom(rooms []room, r room) bool {
	for _, rr := range rooms {
		if (r.pos.X+r.w-1 >= rr.pos.X && rr.pos.X+rr.w-1 >= r.pos.X) &&
			(r.pos.Y+r.h-1 >= rr.pos.Y && rr.pos.Y+rr.h-1 >= r.pos.Y) {
			return true
		}
	}
	return false
}

func (d *dungeon) connectRooms(r1, r2 room) {
	x := r1.pos.X
	if x < r2.pos.X {
		x += r1.w - 1
	}
	y := r1.pos.Y
	if y < r2.pos.Y {
		y += r1.h - 1
	}
	d.SetCell(position{x, y}, FreeCell)
	count := 0
	for {
		count++
		if count > 1000 {
			panic("ConnectRooms")
		}
		if x < r2.pos.X {
			x++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x > r2.pos.X {
			x--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if y < r2.pos.Y {
			y++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if y > r2.pos.Y {
			y--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		break
	}
	d.SetCell(r2.pos, FreeCell)
}

func (d *dungeon) connectRoomsDiagonally(r1, r2 room) {
	x := r1.pos.X
	if x < r2.pos.X {
		x += r1.w - 1
	}
	y := r1.pos.Y
	if y < r2.pos.Y {
		y += r1.h - 1
	}
	d.SetCell(position{x, y}, FreeCell)
	count := 0
	for {
		count++
		if count > 1000 {
			panic("ConnectRooms")
		}
		if x < r2.pos.X && y < r2.pos.Y {
			x++
			d.SetCell(position{x, y}, FreeCell)
			y++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x > r2.pos.X && y < r2.pos.Y {
			x--
			d.SetCell(position{x, y}, FreeCell)
			y++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x > r2.pos.X && y > r2.pos.Y {
			x--
			d.SetCell(position{x, y}, FreeCell)
			y--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x < r2.pos.X && y > r2.pos.Y {
			x++
			d.SetCell(position{x, y}, FreeCell)
			y--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x < r2.pos.X {
			x++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if x > r2.pos.X {
			x--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if y < r2.pos.Y {
			y++
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		if y > r2.pos.Y {
			y--
			d.SetCell(position{x, y}, FreeCell)
			continue
		}
		break
	}
	d.SetCell(r2.pos, FreeCell)
}

func (d *dungeon) Area(area []position, pos position, radius int) []position {
	area = area[:0]
	for x := pos.X - radius; x <= pos.X+radius; x++ {
		for y := pos.Y - radius; y <= pos.Y+radius; y++ {
			pos := position{x, y}
			if pos.valid() {
				area = append(area, pos)
			}
		}
	}
	return area
}

func (d *dungeon) ConnectRoomsShortestPath(r1, r2 room) {
	var r1pos, r2pos position
	r1pos.X = r1.pos.X + RandInt(r1.w)
	if r1pos.X < r2.pos.X {
		r1pos.X = r1.pos.X + r1.w - 1
	}
	r1pos.Y = r1.pos.Y + RandInt(r1.h)
	if r1pos.Y < r2.pos.Y {
		r1pos.Y = r1.pos.Y + r1.h - 1
	}
	r2pos.X = r2.pos.X + RandInt(r2.w)
	if r2pos.X < r1.pos.X {
		r2pos.X = r2.pos.X + r2.w - 1
	}
	r2pos.Y = r2.pos.Y + RandInt(r2.h)
	if r2pos.Y < r1.pos.Y {
		r2pos.Y = r2.pos.Y + r2.h - 1
	}
	mp := &dungeonPath{dungeon: d}
	path, _, _ := AstarPath(mp, r1pos, r2pos)
	for _, pos := range path {
		d.SetCell(pos, FreeCell)
	}
}

func (d *dungeon) ConnectIsolatedRoom(doorpos position) {
	for i := 0; i < 200; i++ {
		pos := d.FreeCell()
		dp := &dungeonPath{dungeon: d, wcost: unreachable}
		path, _, _ := AstarPath(dp, pos, doorpos)
		wall := false
		for _, pos := range path {
			if d.Cell(pos).T == WallCell {
				wall = true
				break
			}
		}
		if !wall {
			continue
		}
		for _, pos := range path {
			d.SetCell(pos, FreeCell)
		}
		break
	}
}

func (d *dungeon) DigRoom(r room) {
	for i := r.pos.X; i < r.pos.X+r.w; i++ {
		for j := r.pos.Y; j < r.pos.Y+r.h; j++ {
			rpos := position{i, j}
			if rpos.valid() {
				d.SetCell(rpos, FreeCell)
			}
		}
	}
}

func (d *dungeon) PutCols(r room) {
	for i := r.pos.X + 1; i < r.pos.X+r.w-1; i += 2 {
		for j := r.pos.Y + 1; j < r.pos.Y+r.h-1; j += 2 {
			rpos := position{i, j}
			if rpos.valid() {
				d.SetCell(rpos, WallCell)
			}
		}
	}
}

func (d *dungeon) PutDiagCols(r room) {
	n := RandInt(2)
	for i := r.pos.X + 1; i < r.pos.X+r.w-1; i++ {
		m := n
		for j := r.pos.Y + 1; j < r.pos.Y+r.h-1; j++ {
			rpos := position{i, j}
			if rpos.valid() && m%2 == 0 {
				d.SetCell(rpos, WallCell)
			}
			m++
		}
		n++
	}
}

func (d *dungeon) IsAreaFree(pos position, h, w int) bool {
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() || d.Cell(rpos).T != FreeCell {
				return false
			}
		}
	}
	return true
}

func (d *dungeon) RoomDigCanditate(pos position, h, w int) (ret bool) {
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() {
				return false
			}
			if d.Cell(rpos).T == FreeCell {
				ret = true
			}
		}
	}
	return ret
}

func (d *dungeon) IsolatedRoomDigCanditate(pos position, h, w int) (ret bool) {
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() {
				return false
			}
			if d.Cell(rpos).T == FreeCell {
				return false
			}
		}
	}
	return true
}

func (d *dungeon) DigArea(pos position, h, w int) {
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() {
				continue
			}
			d.SetCell(rpos, FreeCell)
		}
	}
}

func (d *dungeon) BlockArea(pos position, h, w int) {
	// not used now
	for i := pos.X; i < pos.X+w; i++ {
		for j := pos.Y; j < pos.Y+h; j++ {
			rpos := position{i, j}
			if !rpos.valid() {
				continue
			}
			d.SetCell(rpos, WallCell)
		}
	}
}

func (d *dungeon) BuildRoom(pos position, w, h int, outside bool) map[position]bool {
	spos := position{pos.X - 1, pos.Y - 1}
	if outside && !d.IsAreaFree(spos, h+2, w+2) {
		return nil
	}
	for i := pos.X; i < pos.X+w; i++ {
		d.SetCell(position{i, pos.Y}, WallCell)
		d.SetCell(position{i, pos.Y + h - 1}, WallCell)
	}
	for i := pos.Y; i < pos.Y+h; i++ {
		d.SetCell(position{pos.X, i}, WallCell)
		d.SetCell(position{pos.X + w - 1, i}, WallCell)
	}
	if RandInt(2) == 0 || !outside {
		n := RandInt(2)
		for x := pos.X + 1; x < pos.X+w-1; x++ {
			m := n
			for y := pos.Y + 1; y < pos.Y+h-1; y++ {
				if m%2 == 0 {
					d.SetCell(position{x, y}, WallCell)
				}
				m++
			}
			n++
		}
	} else {
		n := RandInt(2)
		m := RandInt(2)
		//if n == 0 && m == 0 {
		//// round room
		//d.SetCell(pos, FreeCell)
		//d.SetCell(position{pos.X, pos.Y + h - 1}, FreeCell)
		//d.SetCell(position{pos.X + w - 1, pos.Y}, FreeCell)
		//d.SetCell(position{pos.X + w - 1, pos.Y + h - 1}, FreeCell)
		//}
		for x := pos.X + 1 + m; x < pos.X+w-1; x += 2 {
			for y := pos.Y + 1 + n; y < pos.Y+h-1; y += 2 {
				d.SetCell(position{x, y}, WallCell)
			}
		}

	}
	area := make([]position, 9)
	if outside {
		for _, p := range [4]position{pos, {pos.X, pos.Y + h - 1}, {pos.X + w - 1, pos.Y}, {pos.X + w - 1, pos.Y + h - 1}} {
			if d.WallAreaCount(area, p, 1) == 4 {
				d.SetCell(p, FreeCell)
			}
		}
	}
	doorsc := [4]position{
		position{pos.X + w/2, pos.Y},
		position{pos.X + w/2, pos.Y + h - 1},
		position{pos.X, pos.Y + h/2},
		position{pos.X + w - 1, pos.Y + h/2},
	}
	doors := make(map[position]bool)
	for i := 0; i < 3+RandInt(2); i++ {
		dpos := doorsc[RandInt(4)]
		doors[dpos] = true
		d.SetCell(dpos, FreeCell)
	}
	return doors
}

func (d *dungeon) BuildSomeRoom(w, h int) map[position]bool {
	for i := 0; i < 200; i++ {
		pos := d.FreeCell()
		doors := d.BuildRoom(pos, w, h, true)
		if doors != nil {
			return doors
		}
	}
	return nil
}

func (d *dungeon) DigSomeRoom(w, h int) map[position]bool {
	for i := 0; i < 200; i++ {
		pos := d.FreeCell()
		dpos := position{pos.X - 1, pos.Y - 1}
		if !d.RoomDigCanditate(dpos, h+2, w+2) {
			continue
		}
		d.DigArea(dpos, h+2, w+2)
		doors := d.BuildRoom(pos, w, h, true)
		if doors != nil {
			return doors
		}
	}
	return nil
}

func (d *dungeon) DigIsolatedRoom(w, h int) map[position]bool {
	for i := 0; i < 3000; i++ {
		pos := d.WallCell()
		dpos := position{pos.X - 1, pos.Y - 1}
		if !d.IsolatedRoomDigCanditate(dpos, h+2, w+2) {
			continue
		}
		d.DigArea(pos, h, w)
		doors := d.BuildRoom(pos, w, h, false)
		if doors != nil {
			return doors
		}
	}
	return nil
}

func (d *dungeon) ResizeRoom(r room) room {
	if DungeonWidth-r.pos.X < r.w {
		r.w = DungeonWidth - r.pos.X
	}
	if DungeonHeight-r.pos.Y < r.h {
		r.h = DungeonHeight - r.pos.Y
	}
	return r
}

func (g *game) GenRuinsMap(h, w int) {
	d := &dungeon{}
	d.Cells = make([]cell, h*w)
	rooms := []room{}
	for i := 0; i < 43; i++ {
		var ro room
		count := 100
		for count > 0 {
			count--
			ro = room{
				pos: position{RandInt(w - 1), RandInt(h - 1)},
				w:   3 + RandInt(5),
				h:   2 + RandInt(3)}
			ro = d.ResizeRoom(ro)
			if !intersectsRoom(rooms, ro) {
				break
			}
		}

		d.DigRoom(ro)
		if RandInt(60) == 0 {
			if RandInt(2) == 0 {
				d.PutCols(ro)
			} else {
				d.PutDiagCols(ro)
			}
		}
		if len(rooms) > 0 {
			r := RandInt(100)
			if r > 75 {
				d.connectRooms(nearRoom(rooms, ro), ro)
			} else if r > 25 {
				d.ConnectRoomsShortestPath(nearRoom(rooms, ro), ro)
			} else {
				d.connectRoomsDiagonally(nearRoom(rooms, ro), ro)
			}
		}
		rooms = append(rooms, ro)
	}
	doors := d.DigSomeRooms(5)
	g.Dungeon = d
	g.Fungus = make(map[position]vegetation)
	g.DigFungus(1 + RandInt(2))
	g.PutDoors(30)
	for pos := range doors {
		if g.DoorCandidate(pos) && RandInt(100) > 20 {
			g.Doors[pos] = true
		}
	}
}

func (g *game) DigFungus(n int) {
	d := g.Dungeon
	fungus := g.Foliage(DungeonHeight, DungeonWidth)
	for i := 0; i < 100; i++ {
		if n <= 0 {
			break
		}
		pos := d.FreeCell()
		if _, ok := fungus[pos]; ok {
			continue
		}
		conn, count := d.Connected(pos, func(npos position) bool {
			_, ok := fungus[npos]
			return ok && d.IsFreeCell(npos)
		})
		if count < 3 {
			continue
		}
		//dig := RandInt(2) == 0
		dig := true // looks always better
		for pos := range conn {
			if dig {
				d.SetCell(pos, FreeCell)
			}
			g.Fungus[pos] = foliage
		}
		n--
	}
}

type roomSlice []room

func (rs roomSlice) Len() int      { return len(rs) }
func (rs roomSlice) Swap(i, j int) { rs[i], rs[j] = rs[j], rs[i] }
func (rs roomSlice) Less(i, j int) bool {
	return rs[i].pos.Y < rs[j].pos.Y || rs[i].pos.Y == rs[j].pos.Y && rs[i].pos.X < rs[j].pos.X
{'fraction_non_alphanumeric': 0.17991208620220173, 'fraction_numerical': 0.019060956159800833, 'mean_word_length': 2.533745704467354, 'pattern_counts': {'":': 0, '<': 113, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2033268', 'n_tokens_mistral': 13102, 'n_tokens_neox': 11740, 'n_words': 2810}