# Duane's Dungeon - a rogue-like game
# Copyright (C) 2023 Duane Robertson

# map_maker.gd - generates terrain

# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <https://www.gnu.org/licenses/>.


extends Node
class_name MapMaker


class BoundIter:
	# This is slower than a pair of simple loops by ~300%,
	#  but it's neater. The speed shouldn't be a major issue
	#  in the dungeon generation, which is fairly fast anyway.

	var rect:Rect2i
	var perim:bool
	var v:Vector2i

	func _init(r:Rect2i, perimeter := false):
		rect = r
		perim = perimeter

	func should_continue():
		return (v.y < rect.end.y and v.x < rect.end.x)

	func _iter_init(_arg):
		v = rect.position
		return should_continue()

	func _iter_next(_arg):
		v.x += 1

		if perim and v.y != rect.position.y \
		and v.y != rect.end.y - 1 \
		and v.x > rect.position.x \
		and v.x < rect.end.x - 1:
			v.x = rect.end.x - 1

		if v.x >= rect.end.x:
			v.x = rect.position.x
			v.y += 1
		return should_continue()

	func _iter_get(_arg):
		return v


const COLOR_FLOOR = '3f3f3f'		# background color for tiles
const COLOR_GREEN_DARK = '003000'
const COLOR_GREEN_LIGHT = '00a000'
const COLOR_STONE = 'bfbfbf'
const COLOR_STONE_FADED = '909090'
const COLOR_WATER = '0000c0'
const COLOR_WOOD_DARK = '808000'
const COLOR_WOOD_LIGHT = '999900'

var SSHOT_DIR = 'screenshots'
var SSHOT_FN = 'user://%s/dungeon_shot_%%02d.png' % [SSHOT_DIR]

var bounds:Rect2i
var default_parameters = {
	bounds = Rect2i(0, 0, 101, 101),
	bridges = {
		water = [ 'bridge_h', 'bridge_v' ],
		lava = [ 'lava_bridge_h', 'lava_bridge_v' ],
	},
	garden_size = 16,
	iterations = 7,
	junk_list = [ 'statue2', 'statue1', 'well', 'grate', 'rocks', 'dirt' ],
	junk_list_cave = [ 'bones', 'rocks', 'debris', 'stalagmites', 'dirt' ],
	liquid = 'water',
	max_aspect = 3.0,
	min_room_size = 2,
	plant_list = [ 'tree', 'bush', 'mushroom1', 'grass', 'mossy' ],
	tile_defs = [
		[ 'bones', 'bones', '808080', COLOR_FLOOR, true, true ],
		[ 'bridge_h', 'bridge', COLOR_WOOD_DARK, COLOR_WATER, true, true ],
		[ 'bridge_v', 'bridge', COLOR_WOOD_DARK, COLOR_WATER, true, true ],
		[ 'bush', 'bush', COLOR_GREEN_LIGHT, COLOR_GREEN_DARK, false, true ],
		[ 'column', 'column', COLOR_STONE, COLOR_FLOOR, false, false ],
		[ 'crystal', 'crystal', 'ffff80', COLOR_FLOOR, false, true ],
		[ 'debris', 'debris', '303030', COLOR_FLOOR, true, true ],
		[ 'dirt', 'dirt', '606000', COLOR_FLOOR, true, true ],
		[ 'floor', 'blank', null, COLOR_FLOOR, true, true ],
		[ 'grass', 'dirt', COLOR_GREEN_LIGHT, COLOR_GREEN_DARK, true, true ],
		[ 'grate', 'grate', COLOR_STONE_FADED, COLOR_FLOOR, true, true ],
		[ 'lava', 'blank', null, 'ff0000', false, true ],
		[ 'lava_bridge_h', 'bridge', 'ff0000', '000000', true, true ],
		[ 'lava_bridge_v', 'bridge', 'ff0000', '000000', true, true ],
		[ 'lava_hard', 'rocks', '000000', 'ff0000', true, true ],
		[ 'mossy', 'blank', null, COLOR_GREEN_DARK, true, true ],
		[ 'mushroom1', 'mushrooms', 'dfdfdf', COLOR_GREEN_DARK, false, true ],
		[ 'rock', 'rock', '202020', '000000', false, false ],
		[ 'rock2', 'rock', null, '000000', false, false ],
		[ 'rocks', 'rocks', 'c0c0c0', COLOR_FLOOR, false, true ],
		[ 'rocks2', 'rocks', 'c0c0c0', COLOR_FLOOR, false, true ],
		[ 'shallow', 'rocks', COLOR_GREEN_DARK, COLOR_WATER, true, true ],
		[ 'stalagmites', 'stalagmites', '303010', COLOR_FLOOR, true, true ],
		[ 'statue1', 'man', COLOR_STONE_FADED, COLOR_FLOOR, false, false ],
		[ 'statue2', 'woman', COLOR_STONE_FADED, COLOR_FLOOR, false, false ],
		[ 'tree', 'tree', COLOR_GREEN_LIGHT, COLOR_GREEN_DARK, false, false ],
		[ 'wall1', 'wall1', COLOR_STONE, COLOR_FLOOR, false, false ],
		[ 'wall2', 'wall2', COLOR_STONE, COLOR_FLOOR, false, false ],
		[ 'wall3', 'wall3', COLOR_STONE, COLOR_FLOOR, false, false ],
		[ 'water', 'blank', null, COLOR_WATER, false, true ],
		[ 'well', 'well', COLOR_STONE, COLOR_FLOOR, false, true ],
	],
	tile_file = 'art/dungeon_sprites.png',
	tile_size = Vector2i(16, 16),
}
var map:TileMap
var param:Dictionary
var terr_map:Dictionary
var terr_name = {}
var tile_set:TileSet


# Called when the node enters the scene tree for the first time.
func _ready():
	map = get_parent()

	bounds = default_parameters.bounds
	param = default_parameters.duplicate()

	G.sprite_sheet = SpriteSheet.new(param.tile_file)
	make_tiles()

	map.bounds = bounds
	map.param = param
	map.terr_map = terr_map
	map.terr_name = terr_name
	map.level = param.get('level', 1)


# Called every frame. 'delta' is the elapsed time since the previous frame.
#func _process(delta):
#	pass


func arena():
	var room = bounds.grow(- (min(bounds.size.x, bounds.size.y) * (randf() * 0.1 + 0.1)))
	house_room(room, [ ])


func big_maze():
	pass


func big_room():
	var room = bounds.grow(-3)
	boring_room(room)


func bomb_rad(room:Rect2i):
	var r = max(room.size.x, room.size.y) / 10
	return max(2, round(r))


func bomb(room:Rect2i, r:int, tile:String, reps := 1, only := [], square := false):
	var border := 0
	if not terr_map[tile].walkable:
		border = 1

	assert(room.get_area() > 0)
	assert(room.size.x > 0)
	assert(room.size.y > 0)

	var cs = [ ]
	var rc:Vector2 = room.get_center()
	var sqsz = maxf(room.size.x, room.size.y)
	assert(sqsz > 0)
	var asp = room.size / sqsz
	sqsz = ceili(sqsz / 2)

	if sqsz <= r:
		return

	var loop:int = ceil(reps * sqsz / 3.0)
	loop = max(1, loop)

	for i in loop:
		var c
		var trec

		for j in 100:
			var a = randf() * PI * 2
			var r2 = max(0, randi() % (sqsz - r))
			c = Vector2.from_angle(a) * r2 * asp + rc
			trec = Rect2i(c, Vector2i.ZERO).grow(r)

			if room.encloses(trec):
				break
			else:
				trec = null

		if trec:
			cs.push_back(c)

			if not only.is_empty():
				var btrec = trec.grow(border)
				for v in BoundIter.new(btrec):
					var n = map.get_tile(v)
					if trec.has_point(v):
						if not n in only:
							trec = null
							break
					elif not (terr_map[n].walkable or n in only):
						trec = null
						break

			if trec:
				assert(room.encloses(trec))
				for v in BoundIter.new(trec):
					var d2 = (Vector2i(c) - v).length_squared()
					var r3 = r - randf() + 0.5
					if (square or d2 <= r3 * r3) \
					and bounds.has_point(v):
						map.set_tile(v, tile)

	return cs


func boring_room(bound):
	wall(bound)
	fill(bound, 'floor')
	deco(bound)


func build(map_seed = null):
	if map_seed:
		seed(map_seed)

	for p in BoundIter.new(Rect2i(-100, -100, 300, 300)):
		map.set_tile(p, 'rock')

	juggle_parameters()

	var ch = log_pick([ 'arena', 'cavern', 'complex' ])
	ch = 'complex' if map.level == 1 else ch
#	ch = 'arena'

	call(ch)

	# map.set_tile(Vector2i.ZERO, 'lava')

	get_open_spaces()


func cave(room, tile, cst):
	var c = room.get_center()
	cst.append(c)

	# Show the outline of the bound.
	# for v in BoundIter.new(room.grow(-2)):
	#     map.set_tile(v, 'grass')

	bomb(room, bomb_rad(room), tile, 10)


func cave_style(room, tile, tunn):
	var r = bomb_rad(room)
	var liq = param.liquid

	if liq == 'lava':
		if randi() % 4 == 0:
			crystals(room, tunn)
		else:
			lava_pools(room, tile)
	else:
		if randi() % 4 < r:
			garden(room)
		elif randi() % 4 == 1:
			crystals(room, tunn)

	# Use alternate rock to avoid walls.
	for i in range(ceil(r / 2), r + 1):
		bomb(room, max(2, i), 'rock2', 2, [ tile, 'rock2' ])


func cavern():
	var tile = 'floor'

	G.stopwatch()

	var rooms = room_splitter(4)[1]

	G.stopwatch('room_splitter')

	rooms = pare_small(rooms)

	var cst = []

	G.stopwatch('paring')

	for room in rooms:
		cave(room, tile, cst)

	G.stopwatch(' bombing')

	var tunn = connect_centers(cst, tile)

	G.stopwatch(' connecting')

	for room in rooms:
		cave_style(room, tile, tunn)

	G.stopwatch(' second bombing')

	deco(bounds.grow(-1), true)

	G.stopwatch(' decorations')

	flood_fill_test()

	G.stopwatch(' flood fill', true)


func check_central(pos:Vector2i, any:bool) -> bool:
	# Check if any/every tile is walkable, depending on "any".

	for y in range(-1, 2):
		for x in range(-1, 2):
			if x == 0 and y == 0:
				continue

			var p = Vector2i(x, y) + pos
			var n = map.get_tile(p)
			if any == terr_map[n].walkable:
				return any

	return not any


func check_clear(pos:Vector2i) -> bool:
	# Is every adjacent tile walkable?
	return check_central(pos, false)


func check_walk(pos:Vector2i) -> bool:
	# Is any adjacent tile walkable?
	return check_central(pos, true)


func column_room(room) -> bool:
	if room.size.x < 4 or room.size.y < 4:
		return false

	if not bounds.encloses(room.grow(1)):
		return false

	var m = (room.size + Vector2i.ONE) % 2
	room = room.grow_individual(0, 0, -m.x, -m.y)

	wall(room)
	fill(room, 'floor')

	var cb = room.grow(-1)
	while randi() %2 == 0 and cb.has_area():
		columns(cb)
		cb = cb.grow(-2)

	deco(room)

	return true


func columns(room:Rect2i, full := false):
	if room.size.x < 3 or room.size.y < 3:
		return

	if full:
		for v in BoundIter.new(room):
			if (v.x - room.position.x) % 2 == 0 \
			and (v.y - room.position.y) % 2 == 0:
				map.set_tile(v, 'column')
	else:
		for v in BoundIter.new(room, true):
			if (v.x - room.position.x) % 2 == 0 \
			and (v.y - room.position.y) % 2 == 0:
				map.set_tile(v, 'column')


func complex() -> void:
	var min_rooms = roundi(sqrt(bounds.get_area()) * 15.0 / 100.0)
	G.debug('starting rooms, looking for %d rooms' % min_rooms)

	var ret = room_splitter(min_rooms)
	var r_tree = ret[0]
	var rooms = ret[1]

	G.stopwatch()
	var nrooms = []
	for room in rooms:
		var r = rectangle_to_room(room)
		if r != null:
			nrooms.push_back(r)
	rooms = nrooms
	G.stopwatch(' rectangle_to_room')

	var corrs = corridors(r_tree)

	G.stopwatch(' corridors')

	for room in rooms:
		assert(room.get_area() > 0)
		assert(room.size.x > 0)
		assert(room.size.y > 0)
		if randi() % 3 == 0 and column_room(room):
			pass
		elif randi() % 3 == 0 and maze_room(room):
			pass
		elif randi() % 2 == 0 and garden_room(room):
			pass
		elif randi() % 2 == 0 and pit_room(room, corrs):
			pass
		elif house_room(room, corrs):
			pass
		else:
			boring_room(room)

	G.stopwatch(' filled rooms')

	flood_fill_test()

	G.stopwatch(' flood fill', true)


func connect_centers(cs, tile):
	var c1
	var tunn = {}
	var bound = bounds.grow(-1)

	for c2 in cs:
		for i in range(1000):
			if not c1 or c1 == c2:
				break

			var a = (randf() - 0.5) * PI
			var g = Vector2(c1).direction_to(c2).rotated(a)

			if abs(g.x) > abs(g.y):
				c1.x += round(g.x)
			else:
				c1.y += round(g.y)

			if bound.has_point(c1):
				tunn[c1] = true
				if not walkable(c1):
					map.set_tile(c1, tile)
					if randi() % 8 == 0:
						var temr = Rect2i(c1, Vector2i(1, 1)).grow(1)
						for v in BoundIter.new(temr):
							map.set_tile(v, tile)

			if i == 1000:
				G.error('connect failure')
		c1 = c2

	return tunn


func corridor_tree(tree, list):
	if not tree.lchild:
		return

	var l = tree.lchild.leaf
	var r = tree.rchild.leaf

	var mins = min(l.size.x, l.size.y, r.size.x, r.size.y)
	if mins < param.min_room_size:
		return

	var v1 = l.get_center()
	var v2 = r.get_center()

	assert(v1.x == v2.x or v1.y == v2.y)

	list.append(Rect2i(v1, v2 - v1 + Vector2i.ONE))

	corridor_tree(tree.lchild, list)
	corridor_tree(tree.rchild, list)


func corridors(tree) -> Array:
	var corr = []
	var inner = bounds.grow(-1)

	corridor_tree(tree, corr)

	for c in corr:
		c = inner.intersection(c)
		wall(c)
		fill(c, 'floor')

	return corr


func crystals(room, tunn):
	pass


func deco(bound, is_cave := false) -> void:
	for v in BoundIter.new(bound):
		var n = map.get_tile(v)
		var chance = randi() % 100

		if n == 'mossy' and chance < 70:
			n = log_pick(param.plant_list)
			map.set_tile(v, n)
		elif is_cave and n == 'floor' and chance < 20:
			n = log_pick(param.junk_list_cave)
			if terr_map[n].walkable or check_clear(v):
				map.set_tile(v, n)
		elif n == 'floor' and chance < 5:
			n = log_pick(param.junk_list)
			if terr_map[n].walkable or check_clear(v):
				map.set_tile(v, n)
		elif n == 'water' and chance < 30 and check_walk(v):
			map.set_tile(v, 'shallow')
		elif n == 'lava' and chance < 30 and check_walk(v):
			map.set_tile(v, 'lava_hard')
		elif n == 'rock2':
			map.set_tile(v, 'rock')


func fill(bound, tile):
	for pos in BoundIter.new(bound):
		map.set_tile(pos, tile)


func flood_fill_test() -> void:
	# This finds all accessible tiles.

	var atl_wal = {}
	var looked

	for i in 10:
		var ct = 0
		var curr = null
		looked = { }
		var q = [ ]

		for j in 1000:
			var v = rect_rand(bounds)

			if walkable(v):
				curr = v
				map.open_spaces_dic[v] = true
				break

		if not curr:
			G.error('flood fill failure')
			return

		q.push_back(curr)
		while not q.is_empty():
			curr = q.pop_back()
			looked[curr] = true

			for ly in range(curr.y - 1, curr.y + 2):
				for lx in range(curr.x - 1, curr.x + 2):
					var l = Vector2i(lx, ly)
					if not looked.get(l):
						var coo = map.get_cell_atlas_coords(0, l)
						var w = atl_wal.get(coo)

						# Cache tiles' walkable by atlas coordinates.
						#  This gives a modest speed increase.
						if w == null:
							w = walkable(l)
							atl_wal[coo] = w

						if w:
							map.open_spaces_dic[l] = true
							ct = ct + 1
							q.push_back(l)

						looked[l] = true

		if ct > 1000:
			G.debug(' available spaces: %d' % ct)
			break
		else:
			G.warn('flood fill started in an isolated area -- trying again')


func garden(room:Rect2i, tile := 'floor') -> void:
	assert(room.get_area() > 0)
	assert(room.size.x > 0)
	assert(room.size.y > 0)
	var wf = 'mossy'
	var fallow = [ tile, wf, 'dirt', 'rocks', 'grate' ]

	var r:int = bomb_rad(room)
	var liq = self.param.liquid
	assert(liq == 'water')

	# wet floor
	for i in range(r / 2, r + 1):
		bomb(room, max(2, i), wf, 2, fallow)

	# pools
	for i in range(r / 2, r + 1):
		bomb(room, max(2, i), liq, 2, [ wf, liq ])

	# islands
	for i in range(r / 2, r + 1):
		bomb(room, max(3, i), wf, 1, [ liq ])


func garden_room(room) -> bool:
	assert(room.get_area() > 0)
	assert(room.size.x > 0)
	assert(room.size.y > 0)

	if param.liquid != 'water':
		return false

	var sz = min(room.size.x, room.size.y)
	if sz < param.garden_size:
		return false

	wall(room)
	fill(room, 'floor')
	garden(room)
	deco(room)

	return true


func find_tile(bound, tile):
	for v in BoundIter.new(bound):
		if map.get_tile(v) == tile:
			return true
	return false


func get_open_spaces():
	if len(map.open_spaces_dic) == 0:
		for v in BoundIter.new(bounds):
			if walkable(v):
				map.open_spaces_dic[v] = true

	map.open_spaces = map.open_spaces_dic.keys()
	map.open_spaces.shuffle()


func house_room(room, _corrs) -> bool:
	if room.size.x < 8 or room.size.y < 8:
		return false

	wall(room)
	fill(room, 'floor')

	var r = bomb_rad(room)
	var hs = [ ]
	for i in 100:
		var v:Vector2i = rect_rand(room)
		var r2 = r if r < 4 else randi_range(3, r)
		var b = Rect2i(v, Vector2i.ZERO).grow(r2)
		var c = b.grow(1)
		if room.encloses(c) and not find_tile(c, 'rock'):
			fill(b, 'rock')
			hs.push_back(b)

	for h in hs:
		var inside = h.grow(-1)
		wall(inside)
		fill(inside, 'floor')

		var ps = [ ]
		for v in BoundIter.new(h, true):
			var ch = randi() % 20
			if ch == 0:
				map.set_tile(v, 'floor')
			elif ch < 5:
				map.set_tile(v, 'rocks')
			else:
				ps.push_back(v)

		var k = ps.pick_random()
		map.set_tile(k, 'floor')

	deco(room)

	return true


func juggle_parameters():
	var d = default_parameters
	param.garden_size = d.garden_size + randi() % 6 - 3
	param.iterations = d.iterations + randi() % 7 - 4
	param.max_aspect = d.max_aspect + randf() * 2 - 2.0
	param.min_room_size = d.min_room_size + randi() % 3
	param.liquid = 'lava' if (randi() % 3 == 0) else 'water'


func lava_pools(room, tile):
	var r = bomb_rad(room)
	var liq = param.liquid

	# pools
	for i in range(ceil(r / 2), r + 1):
		bomb(room, max(2, i), liq, 2, [ tile,  liq ])

	# islands
	for i in range(ceil(r / 2), r + 1):
		bomb(room, max(3, i), tile, 1, [ liq ])


func make_tiles() -> void:
	#var ss := SpriteSheet.new(param.tile_file)
	var ss:SpriteSheet = G.sprite_sheet
	var tile_size = param.tile_size

	# Create the atlas texture from sprites.
	var isz = Vector2i(1, len(param.tile_defs)) * tile_size
	var atl := Image.create(isz.x, isz.y, false, Image.FORMAT_RGBA8)

	var ncoord = { }
	var defct := 0
	var fin_sz = Rect2i(Vector2i.ZERO, tile_size)
	for def in param.tile_defs:
		var n = def[0]
		var rot = 'bridge_v' in def[0]
		var img = ss.image(def[1], def[2], def[3], rot)
		var nc = Vector2i(0, defct)
		atl.blit_rect(img, fin_sz, nc * tile_size)
		ncoord[n] = nc
		defct += 1

	tile_set = TileSet.new()

	#################################################
	# var back = TextureRect.new()
	# back.texture = ImageTexture.create_from_image(atl)
	# add_child(back)
	# # back.size = back_sz
	#################################################

	var tss1 = TileSetAtlasSource.new()
	tss1.texture = ImageTexture.create_from_image(atl)

	for def in param.tile_defs:
		var n = def[0]
		var ac = ncoord[n]

		terr_map[n] = { }
		terr_map[n].atlas_coords = ac
		terr_map[n].walkable = def[4]
		terr_map[n].transparent = def[5]

		var mmc
		if mmc == null and def[2] != null:
			if def[2] and def[3]:
				var c3 = Color(def[2])
				c3.a = 0.5
				mmc = Color(def[3]).blend(c3).to_html()
			else:
				mmc = def[2]
		if mmc == null and def[3] != null:
			mmc = def[3]

		assert(mmc)
		terr_map[n].minimap_color = mmc

		terr_name[ac] = n

		tss1.create_tile(ac)

	tile_set.add_source(tss1)
	map.tile_set = tile_set


func log_pick(tab:Array):
	var rg = 2 ** len(tab)
	var i = randi_range(2, rg)
	var j = ceili(log(i) / log(2))
	return tab[j - 1]


enum { WALL, SPACE }
const CARD_DIR = [
	Vector2i.LEFT,
	Vector2i.RIGHT,
	Vector2i.UP,
	Vector2i.DOWN,
]
func maze(room, mult):
	################################################
	# rare problem with mazes not opening any paths
	################################################
	for v in BoundIter.new(room, true):
		if map.get_tile(v) == 'rock':
			random_wall_tile(v)

	for v in BoundIter.new(room.grow(-1)):
		random_wall_tile(v)

	var plan = { }
	var planb = Rect2i(Vector2i.ZERO, room.size / mult)

	for v in BoundIter.new(planb):
		plan[v] = WALL

	var st = [ ]
	var visited = { }
	var bv:Vector2i = rect_rand(planb)
	bv = bv + Vector2i.ONE - bv % 2
	var start = bv

	plan[start] = SPACE
	visited[start] = true
	st.push_back(start)

	while not st.is_empty():
		var curr:Vector2i = st.pop_back()
		var unv = [ ]

		for cc in CARD_DIR:
			var n = cc * 2 + curr
			if planb.has_point(n):
				if not visited.get(n):
					unv.push_back(cc)

		if not unv.is_empty():
			st.push_back(curr)
			assert(visited[curr])

			var nex = unv.pick_random()
			var p2 = curr + nex * 2

			plan[curr + nex] = SPACE
			plan[p2] = SPACE
			visited[p2] = true
			st.push_back(p2)

	for v in BoundIter.new(planb):
		var p = (v - Vector2i.ONE) * mult + Vector2i.ONE
		var tar = Rect2i(room.position + p, Vector2i.ONE * mult)
		if plan[v] == SPACE:
			fill(tar, 'floor')


func maze_room(room):
	var sz = min(room.size.x, room.size.y)
	if sz < 10 or sz > 35:
		return false

	var m = (room.size + Vector2i.ONE) % 2
	room = room.grow_individual(0, 0, -m.x, -m.y)

	wall(room)
	maze(room, 1)

	return true


func pare_small(rooms):
	# Leave out some rooms, mostly smaller ones.

	var rooms2 = []
	for r in rooms:
		var chance = min(r.size.x, r.size.y)
		if randi() % chance > 2:
			rooms2.append(r)

	return rooms2


func pit_room(room, corrs):
	if room.size.x < 6 or room.size.y < 6:
		return

	assert(room.get_area() > 0)
	assert(room.size.x > 0)
	assert(room.size.y > 0)

	var liq = param.liquid
	var pit = room.grow(-1)
	var tile = 'floor'

	assert(pit.get_area() > 0)
	assert(pit.size.x > 0)
	assert(pit.size.y > 0)

	wall(room)
	fill(room, tile)
	fill(pit, liq)

	var r = bomb_rad(room)

	# islands
	for i in range(r / 2, r + 1):
		bomb(pit, max(3, i), tile, 1, [ liq ], true)

	deco(room)

	pit_bridges(pit, corrs)

	return true


func pit_bridges(room:Rect2i, corrs):
	var liq = param.liquid
	var bridges = param.bridges[liq]
	var repl = [ liq, 'lava_hard', 'shallow' ]

	for corr in corrs:
		var t = room.intersection(corr)
		if t:
			if t.size.x == 1:
				var br = bridges[1]
				t.position.y = room.position.y
				t.end.y = room.end.y
				replace(t, repl, br)
			elif t.size.y == 1:
				var br = bridges[0]
				t.position.x = room.position.x
				t.end.x = room.end.x
				replace(t, repl, br)
			else:
				G.error('bridge error')


func random_split(r:Rect2i) -> Array:
	# Returns two smaller rectangles from a large one.
	# This is used for partitioning the dungeon into rooms
	# with the split_rect() method.

	var msize = param.min_room_size + 3
	if r.size.x < msize or r.size.y < msize:
		return []

	var r1:Rect2i
	var r2:Rect2i
	var asp:float
	var bounds_room:Rect2i = bounds.grow(-2)

	for ct in 20:
		var frac := ((randi() % 50) + 25) / 100.0
		if randi() % 2 == 0:
			var half := roundi(r.size.x * frac)
			r1 = r.grow_side(SIDE_RIGHT, half - r.size.x)
			r2 = r.grow_side(SIDE_LEFT, -half)
		else:
			var half := roundi(r.size.y * frac)
			r1 = r.grow_side(SIDE_BOTTOM, half - r.size.y)
			r2 = r.grow_side(SIDE_TOP, -half)

		r1 = bounds_room.intersection(r1)
		r2 = bounds_room.intersection(r2)

		var mins = min(r1.size.x, r1.size.y, r2.size.x, r2.size.y)
		if mins < msize:
			continue

		var maxs = max(r1.size.x, r1.size.y, r2.size.x, r2.size.y)
		if maxs < bounds.size.x / 2 and randi() % 10 < ct:
			return []

		asp = max (r1.size.y / r1.size.x, r2.size.y / r2.size.x,
			r1.size.x / r1.size.y, r2.size.x / r2.size.y)

		if asp <= param.max_aspect:
			return [r1, r2]

	return []


const WALL_TILES = [ 'wall3', 'wall2', 'wall1' ]
func random_wall_tile(v:Vector2i):
	map.set_tile(v, log_pick(WALL_TILES))


func rect_rand(rect:Rect2i) -> Vector2i:
	# because you can't multiply a Vector2 by a Vector2i,
	#  for some stupid reason...
	var v = Vector2i(rect.size.x * randf(), rect.size.y * randf())
	v = v + rect.position
	return v


func rectangle_to_room(r:Rect2i):
	# Shrink the rectangles a bit to make them separate.

	var x = ceili(r.size.x / 2.0)
	var y = ceili(r.size.y / 2.0)

	var mrs = param.min_room_size
	var size_x = maxi(mrs, r.size.x - randi() % x)
	var size_y = maxi(mrs, r.size.y - randi() % y)

	size_x = (size_x - r.size.x) / 2.0
	size_y = (size_y - r.size.y) / 2.0

	if size_x > 0 or size_y > 0:
		return r

	var x1 = floori(size_x)
	var x2 = ceili(size_x)
	var y1 = floori(size_y)
	var y2 = ceili(size_y)

	var rout = r.grow_individual(x1, y1, x2, y2)

	if not bounds.encloses(rout):
		G.error('rectangle exceeds bounds')
		return r

	return rout


func replace(room:Rect2i, repl:Array, tile:String):
	for v in BoundIter.new(room):
		if map.get_tile(v) in repl:
			map.set_tile(v, tile)


func room_splitter(min_rooms:int):
	G.stopwatch()

	var juggled := 0
	var r_tree:BTree
	var rooms := []
	while true:
		r_tree = split_rect(bounds)
		rooms = r_tree.get_leaves()

		if len(rooms) >= min_rooms:
			break
		else:
			juggle_parameters()
			juggled += 1

	if juggled > 0:
		G.debug('juggled %d times' % [juggled])
	G.stopwatch('room_splitter', true)
	return [r_tree, rooms]


func split_rect(bound:Rect2i):
	var root := BTree.new(bound)
	var stack = []
	var i := 0
	var curr:BTree = root
	var curr_rect:Rect2 = bound

	stack.push_back({ tree=curr, iter=i })
	while not stack.is_empty():
		var p = stack.pop_back()
		curr = p.tree
		curr_rect = curr.leaf
		i = p.iter

		if i < param.iterations:
			var sr = random_split(curr_rect)
			if len(sr) == 2:
				curr.add(sr)
				stack.push_back({ tree=curr.rchild, iter=i+1 })
				stack.push_back({ tree=curr.lchild, iter=i+1 })

	return root


func walkable(p:Vector2i) -> bool:
	return map.terr_map[map.get_tile(p)].walkable


func wall(bound):
	var outer = bound.grow(1)
	outer = bounds.intersection(outer)
	if not (bound.has_area() and outer.has_area()):
		return

	for pos in BoundIter.new(outer):
		if not bound.has_point(pos):
			if map.get_tile(pos) == 'rock':
				random_wall_tile(pos)