#	Maze generator, version 1
#	Copyright (C) 2024  Foxarc
#
#	This program is free software: you can redistribute it and/or modify
#	it under the terms of the GNU Affero 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 Affero General Public License for more details.
#
#	You should have received a copy of the GNU Affero General Public License
#	along with this program.  If not, see <https://www.gnu.org/licenses/>.
extends Node
var language = TranslationServer.get_loaded_locales().find(TranslationServer.get_locale().left(-3))
# For every case size, /     1        2        3       4        5       6        7        8        9
var max_cases		= [0, [57,27], [28,13], [19,9], [14,6],  [11,5],  [9,4],   [8,3],   [7,3],   [6,3]]
var offset			= [0, [0,0],   [10,10], [0,0],  [10,30], [20,20], [30,30], [10,60], [10,30], [30,0]]
var render_cells	= []
var time_spent		= 0
var generating		= false
var JS_animation	= []

func clear_cells():
	for i in range(render_cells.size()):
		for j in range(render_cells[i].size()):
			render_cells[i][j].queue_free()
	render_cells.clear()

func rerender_cells(new_x,new_y):
	if $"Export".visible:
		$"Export".visible = false
	clear_cells()
	$"Progress".visible = false
	var border = StyleBoxFlat.new()
	border.bg_color = Color("303030")
	border.border_color = Color("ffffff")
	border.border_width_top = 1
	border.border_width_right = 1
	border.border_width_bottom = 1
	border.border_width_left = 1
	for x in range(new_x):
		render_cells.append([])
		for y in range(new_y):
			render_cells[x].append(Panel.new())
			render_cells[x][y].name = str(x) + " " + str(y)
			render_cells[x][y].add_theme_stylebox_override("panel",border)
			render_cells[x][y].size.x = 20*$"case_size".value
			render_cells[x][y].size.y = 20*$"case_size".value
			render_cells[x][y].position.x = render_cells[x][y].size.x*x + offset[$"case_size".value][0]
			render_cells[x][y].position.y = render_cells[x][y].size.y*y + offset[$"case_size".value][1]
			$"maze".add_child(render_cells[x][y])

func update_cell(x,y,state):
	var update = render_cells[x][y].get_theme_stylebox("panel").duplicate()
	var cell_type = {0:Color("303030"),1:Color("ff0000"),2:Color("00ff00"),3:Color("ffffff"),4:Color("800080"),5:Color("0000ff")}
	update.bg_color = cell_type[state]
	render_cells[x][y].add_theme_stylebox_override("panel",update)
	if Vector2(x,y) == get_tooltip_position():
		update_tooltip(-1,-1)

func get_cell_state(x,y):
	if x < 0 or x > render_cells.size()-1 or y < 0 or y > render_cells[x].size()-1:
		return -1
	
	var state = render_cells[x][y].get_theme_stylebox("panel").bg_color
	# 5: Visual only, 3-way intersection
	# 4: Visual only, openable wall cell
	# 3: Visual only, available cell
	# 2: Visited cell
	# 1: Unopenable wall cell
	# 0: Free cell
	var cell_type = {Color("303030"):0,Color("ff0000"):1,Color("00ff00"):2,Color("ffffff"):3,Color("800080"):4,Color("0000ff"):5}
	return cell_type[state]

func get_tooltip_position():
	return Vector2(int($"Tooltip/position/x".text) - 1,int($"Tooltip/position/y".text) - 1)

func update_tooltip(x,y):
	var update_only = (x == -1 and y == -1)
	var inside_maze_renderer = (x >= $"maze".position.x and x < $"maze".size.x+$"maze".position.x) and (y >= $"maze".position.y and y < $"maze".size.y+$"maze".position.y)
	var relative_position = Vector2(x - $"maze".position.x - offset[$"case_size".value][0] , y - $"maze".position.y - offset[$"case_size".value][1])
	var inside_case = (relative_position.x > 0 and relative_position.y > 0) and (relative_position.x < $"maze".size.x - offset[$"case_size".value][0]*2 and relative_position.y < $"maze".size.y - offset[$"case_size".value][1]*2)
	if update_only or inside_maze_renderer:
		if update_only or inside_case:
			if !$"Tooltip".visible:
				$"Tooltip".visible = true
			var case
			if !update_only:
				$"Tooltip".position = Vector2(x,y)
				case = (relative_position/(20*$"case_size".value)).floor()
				$"Tooltip/position/x".text = str(case.x + 1)
				$"Tooltip/position/y".text = str(case.y + 1)
			else:
				case = Vector2(int($"Tooltip/position/x".text) - 1,int($"Tooltip/position/y".text) - 1)
			var resize = ["CASE_FREE", "CASE_CLOSED", "CASE_VISITED", "CASE_AVAILABLE", "CASE_WALL", "CASE_INTERSECTION"]
			var state = get_cell_state(case.x,case.y)
			if state == -1:
				$"Tooltip".size.x = 86
				$"Tooltip/case_type".size.x = 73
				$"Tooltip/case_type".size.y = 24
				$"Tooltip/case_type".text = ""
			else:
				$"Tooltip/case_type".size.y = 43
				$"Tooltip/case_type".text = resize[state]
				$"Tooltip".size.x = max(86,$"Tooltip/case_type".get_content_width() + 4*2)
				$"Tooltip/case_type".size.x = $"Tooltip".size.x
			if x+$"Tooltip".size.x > $"maze".position.x+$"maze".size.x:
				$"Tooltip".position.x -= $"Tooltip".size.x
			if y+$"Tooltip".size.y > $"maze".position.y+$"maze".size.y:
				$"Tooltip".position.y -= $"Tooltip".size.y
			
			time_spent = Time.get_ticks_msec()
		elif $"Tooltip".visible:
			$"Tooltip".visible = false
			time_spent = 0
	elif $"Tooltip".visible:
		$"Tooltip".visible = false
		time_spent = 0
	return true

func update_progress(taken:float,remaining:float):
	$"Progress/bar".size.x = (taken/remaining)*1152
	$"Progress/count".position.x = 1110 - $"Progress/text".get_content_width() - 3
	$"Progress/count".text = str(taken) + "/" + str(remaining)

func get_save_path(file_format,callback):
	var path = FileDialog.new()
	path.name = "SAVE"
	path.file_mode = FileDialog.FILE_MODE_SAVE_FILE
	path.access = FileDialog.ACCESS_FILESYSTEM
	path.filters = PackedStringArray(["*." + file_format])
	path.use_native_dialog = true
	path.file_selected.connect(callback)
	path.visible = true
	add_child(path)

func write_save_path(file_format,path,content):
	var shortest = 2 + file_format.length() + 1
	# Werewolves are on your way
	if path.length() < shortest or\
	# For know-it-all users
	path.right(shortest-1) == "\\." + file_format or\
	# For normal users
	path.right(shortest-2) != "." + file_format:
		path += "." + file_format
	var file = FileAccess.open(path,FileAccess.WRITE)
	file.store_string(content)

func maze_to_CSV():
	get_save_path("csv",save_CSV)

func maze_to_JS():
	get_save_path("html",save_JS)

func save_CSV(path):
	var CSV = ""
	for y in range(render_cells[0].size()):
		for x in range(render_cells.size()):
			CSV += str(get_cell_state(x,y)) + ","
		CSV = CSV.left(-1) + "\n"
	write_save_path("csv",path,CSV)

func save_JS(path):
	var JS = '''<!--
	Maze replay, version 1
	Copyright (C) 2024  Foxarc

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Affero 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 Affero General Public License for more details.

	You should have received a copy of the GNU Affero General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
-->
<html>
	<head>
		<title>Maze replay</title>
		<style>
			body {
				background-color: black;
			}
			h1, h2, p, td {
				color: white;
			}
			a {
				color: orange;
			}
			
			#maze, #maze td {
				border: solid 1px white;
				border-spacing: 0;
			}
			#maze td {
				height: 1.2vw;
				width: 1.2vw;
			}
			*[state="0"] {background-color: #303030;}
			*[state="1"] {background-color: #ff0000;}
			*[state="2"] {background-color: #00ff00;}
			*[state="3"] {background-color: #ffffff;}
			*[state="4"] {background-color: #800080;}
			*[state="5"] {background-color: #0000ff;}

			#control, #caption {
				margin-top: 1vw;
			}
			#control p {
				display: inline;
			}

			#caption th {
				border: solid 1px white;
				border-spacing: 0;
				height: 1vh;
				width: 2vw;
			}
			#caption td {
				color: yellow;
			}

			footer {
				bottom: 0;
				color: white;
				white-space: pre-wrap;
			}
		</style>
	</head>
	<body>
		<h1>Maze replay</h1>
		<h2>By <a href="https://foxarc.website">Foxarc</a>, 2024.</h2>
		<noscript>JavaScript required to replay the maze.</noscript>
		<table id="maze"></table>
		<div id="control">
			<p>Speed: <input id="speed" type="number" min="0.1" max="1" step="0.1" value="0.1"> second(s). </p>
			<button id="replay" onclick="replay();">Replay</button>
			<button id="export_CSV" onclick="export_CSV();" disabled>Export as CSV (maze layout only)</button>
			<br>
			<button id="backward" onclick="set_frame(-1);" disabled>&lt;</button>
			<button id="pause" onclick="pause_replay();" disabled>Pause</button>
			<button id="forward" onclick="set_frame(1);">&gt;</button>
			<p>Frame: <span id="current_frame">0</span>/<span id="max_frames">1</span></p>
		</div>
		<table id="caption">
			<tr>
				<th state="0"></th>
				<td>Free</td>
			</tr>
			<tr>
				<th state="1"></th>
				<td>Closed wall</td>
			</tr>
			<tr>
				<th state="2"></th>
				<td>Visited</td>
			</tr>
			<tr>
				<th state="3"></th>
				<td>Available</td>
			</tr>
			<tr>
				<th state="4"></th>
				<td>Wall</td>
			</tr>
			<tr>
				<th state="5"></th>
				<td>3-way intersection</td>
			</tr>
		</div>
		<!-- Animation -->
		<script>
			/**
				Maze replay file format
				[x,y,preview,animation]

				x: the size of the maze along the x-axis.
				y: the size of the maze along the y-axis.
				preview: an x*y array preview of the untouched maze.
				
				animation:
					x,y,state
				
				From [x,y,preview,..., do x,y,state each time until the end of the array.
				When x == y == state == -1, it's the end of the animation: replace the remaining walls with closed walls.
				x,y: the coordinates where to change the state.
				state: the state to affect.
			**/
			const animation = JS_ANIMATION;
		</script>
		<!-- Maze replay -->
		<script>
			let current_frame = 0;
			let max_frames = (animation.length - 3 - 3)/3;
			let animations = [];
			let pause = true;

			document.getElementById("max_frames").innerText = max_frames;

			let tr;
			let td;
			for (let y = 0; y < animation[1]; y++) {
				tr = document.createElement("tr");
				for (let x = 0; x < animation[0]; x++) {
					td = document.createElement("td");
					td.id = x.toString() + " " + y.toString();
					td.setAttribute("state",animation[2][x][y]);
					tr.appendChild(td);
				}
				document.getElementById("maze").appendChild(tr);
			}

			function toggle(state,...ids) {
				for (const id of ids) {
					if (state == 2 && id == "pause") {
						document.getElementById("pause").disabled = false;
						if (document.getElementById("pause").innerText == "Resume") {
							document.getElementById("pause").innerText = "Pause";
						}
						pause = false;
					} else if (state == 3 && id == "pause") {
						if (document.getElementById("pause").innerText == "Pause") {
							document.getElementById("pause").innerText = "Resume";
							document.getElementById("pause").disabled = false;
						}
					} else {
						document.getElementById(id).disabled = !state;
					}
				}
			}

			function rewind() {
				for (let y = 0; y < animation[1]; y++) {
					for (let x = 0; x < animation[0]; x++) {
						document.getElementById(x + " " + y).setAttribute("state",animation[2][x][y]);
					}
				}
				current_frame = 0;
				document.getElementById("current_frame").innerText = 0;
			}
			function replay(do_rewind = true) {
				toggle(false,"export_CSV","replay","backward","forward");
				if (do_rewind) { rewind(); }
				toggle(2,"pause"); // Don't forget to unpause if the animation was paused!
				let speed = document.getElementById("speed").value;
				// 3 * the animation frame to resume from:
				for (let i = 3*(current_frame+1); i < animation.length; i += 3) {
					// An animation is made of 3 things: x,y and the state. Divide by 3 to get the whole frame then multiply by speed*1000 for
					// how long we wait before playing the next state in JavaScript. We will also remember to remove the previous frames in case
					// we resume the animation so that we won't have to wait and waste current_frame*speed*1000 of time for the cases that were
					// already drawn on the grid.
					animations.push(setTimeout(() => play(animation[i],animation[i+1],animation[i+2]), (i/3)*speed*1000 - current_frame*speed*1000));
				}
			}
			function play(x,y,state,ignore_pause = false,direction = 1) {
				if (!pause || ignore_pause) {
					if (x == -1 && y == -1 && state == -1) {
						for (let y2 = 0; y2 < animation[1]; y2++) { for (let x2 = 0; x2 < animation[0]; x2++) {
							if (document.getElementById(x2 + " " + y2).getAttribute("state") == 4) {
								document.getElementById(x2 + " " + y2).setAttribute("state",1);
							}
						}}
						toggle(true,"export_CSV","replay","backward");
						toggle(false,"pause");
						pause = true;
					} else {
						current_frame += direction;
						document.getElementById("current_frame").innerText = current_frame;
						document.getElementById(x + " " + y).setAttribute("state",state);
					}
				} else { for (let i = 0; i < animations.length; i++) { clearTimeout(animations[i]); }}
			}

			function pause_replay() {
				if (pause) {
					pause = false;
					document.getElementById("pause").innerText = "Pause";
					toggle(false,"export_CSV","replay");
					replay(false);
				} else {
					pause = true;
					document.getElementById("pause").innerText = "Resume";
					toggle(true,"export_CSV","replay");
					if (current_frame != 0) { toggle(true,"backward"); }
					if (current_frame != max_frames) { toggle(true,"forward"); }
				}
			}
			function set_frame(next_frame) {
				if (!current_frame) {
					play(animation[3],animation[4],animation[5],true,next_frame);
					toggle(3,"pause");
					toggle(true,"backward");
				} else if (next_frame == -1) {
					toggle(3,"pause");
					if (current_frame == 1) {
						toggle(false,"backward");
					} else if (current_frame == max_frames) {
						toggle(true,"pause");
					}
					
					if (current_frame == max_frames) {
						// We could have an array previously to store the walls at the last step but we didn't.
						// The reason being optimization at first so is memory. We have no choice therefore but
						// to rewind the animation then replay quickly the animation until the second to last.
						rewind();
						for (let i = 3; i < animation.length - 3*2; i += 3) {
							play(animation[i],animation[i+1],animation[i+2],true);
						}
						toggle(true,"forward");
					} else {
						// Get the current coordinates of this frame then undo the state using the state from the preview maze:
						let x = animation[ 2+3*current_frame-2 ] , y = animation[ 2+3*current_frame-1 ];
						play(x,y,animation[2][x][y],true,-1);
					}
				} else {
					toggle(3,"pause");
					play(animation[2+3*(current_frame+next_frame)-2],animation[2+3*(current_frame+next_frame)-1],animation[2+3*(current_frame+next_frame)],true,1);
					if (current_frame == max_frames) {
						play(-1,-1,-1,1);
						toggle(false,"forward");
					}
				}
			}

			function export_CSV() {
				let CSV = [""];
				for (let y = 0; y < animation[1]; y++) {
					for (let x = 0; x < animation[0]; x++) {
						CSV[0] += document.getElementById(x + " " + y).getAttribute("state") + ",";
					}
					CSV[0] = CSV[0].slice(0,-1) + "\\n";
				}
				let CSV_file = URL.createObjectURL(new File(CSV,window.location.href.split("/").pop().replace(".html",".csv"),{type:"text/csv"}));
				window.location.href = CSV_file;
			}
		</script>
		<footer>
			Maze replay, version 1
			Copyright (C) 2024  Foxarc
		
			This program is free software: you can redistribute it and/or modify
			it under the terms of the GNU Affero 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 Affero General Public License for more details.
		
			You should have received a copy of the GNU Affero General Public License
			along with this program.  If not, see <a href="https://www.gnu.org/licenses/">&lt;https://www.gnu.org/licenses/&gt;</a>.
		</footer>
	</body>
</html>'''
	var JS_array = "["
	JS_array += str(JS_animation[0]) + "," + str(JS_animation[1]) + ",["
	for x in range(JS_animation[2].size()):
		JS_array += "["
		for y in range(JS_animation[2][x].size()):
			JS_array += str(JS_animation[2][x][y]) + ","
		JS_array = JS_array.left(-1) + "],"
	JS_array = JS_array.left(-1) + "],"
	for i in range(3,JS_animation.size()):
		JS_array += str(JS_animation[i]) + ","
	JS_array = JS_array.left(-1) + "]"
	JS = JS.replace("JS_ANIMATION",JS_array)
	write_save_path("html",path,JS)

func _on_surface_size_x_changed(value):
	rerender_cells(value,$"surface_size_y".value)

func _on_surface_size_y_changed(value):
	rerender_cells($"surface_size_x".value,value)

func _on_case_size_value_changed(value):
	$"surface_size_x".max_value = max_cases[value][0]
	$"surface_size_y".max_value = max_cases[value][1]
	$"Limitations/x/max".text = str(max_cases[value][0])
	$"Limitations/y/max".text = str(max_cases[value][1])
	rerender_cells($"surface_size_x".value,$"surface_size_y".value)

func _on_record_toggled(toggled_on):
	if (toggled_on):
		$"Captions/Visualization box".visible = false
		$"Captions/Visualization text".visible = false
	else:
		$"Captions/Visualization box".visible = true
		$"Captions/Visualization text".visible = true

func _on_generate_pressed():
	if $"Language hint".visible:
		$"Language hint".visible = false
	
	if $"Export".visible:
		$"Export".visible = false
		JS_animation = []
	$"Progress".visible = false
	if generating:
		generating = false
		$"Generate".text = "GENERATE"
		return true
	
	var generated = false
	# For know-it-all users
	if $"surface_size_x".value == 1:
		for y in range(render_cells[0].size()):
			update_cell(0,y,1)
		generated = true
	elif $"surface_size_y".value == 1:
		for x in range(render_cells.size()):
			update_cell(x,0,1)
		generated = true
	elif $"surface_size_x".value == 2 and $"surface_size_y".value == 2:
		update_cell(0,0,1)
		update_cell(1,0,1)
		update_cell(0,1,1)
		update_cell(1,1,1)
		generated = true
	elif $"surface_size_x".value == 2 or $"surface_size_y".value == 2:
		for x in range($"surface_size_x".value):
			for y in range(render_cells[x].size()):
				update_cell(x,y,1)
		generated = true
	elif $"surface_size_x".value >= 100 or $"surface_size_y".value >= 100:
		return "foxes will now attack u"
	
	if !generated:
		$"surface_size_x".editable = false
		$"surface_size_y".editable = false
		$"case_size".editable = false
		$"Generate".text = "CANCEL"
		$"record".disabled = true
		if $"record".button_pressed:
			generated = await generate_and_record(Vector2($"surface_size_x".value,$"surface_size_y".value),render_cells)
		else:
			var cells = await generate(Vector2($"surface_size_x".value,$"surface_size_y".value),$"case_size".value)
			for x in range(render_cells.size()):
				for y in range(render_cells[x].size()):
					update_cell(x,y,cells[x][y])
			generated = true
		$"surface_size_x".editable = true
		$"surface_size_y".editable = true
		$"case_size".editable = true
		$"Generate".text = "GENERATE"
		$"record".disabled = false
	if generated:
		if !JS_animation.size():
			$"Export/JS".disabled = true
			$"Export/JS".text = "NO_JS"
		else:
			$"Export/JS".disabled = false
			$"Export/JS".text = "EXPORT_JS"
		$"Export".visible = true

func _ready():
	$"Captions/Visualization box".size.x = min(137 + $"Captions/3-way intersection text".get_content_width() + 3,293)
	$"Captions/Visualization text".position.x = $"Captions/Visualization box".position.x + $"Captions/Visualization box".size.x + 2
	$"Captions/Visualization text".size.x = min($"Captions/Visualization text".get_content_width(),637)
	rerender_cells($"surface_size_x".value,$"surface_size_y".value)

func _input(event):
	if event is InputEventMouseMotion:
		update_tooltip(event.position.x,event.position.y)

func _process(_delta):
	if time_spent:
		if Time.get_ticks_msec() > time_spent + 1*1000:
			if Input.get_mouse_mode() == Input.MOUSE_MODE_VISIBLE:
				Input.set_mouse_mode(Input.MOUSE_MODE_HIDDEN)
		elif Input.get_mouse_mode() == Input.MOUSE_MODE_HIDDEN:
			Input.set_mouse_mode(Input.MOUSE_MODE_VISIBLE)
	elif Input.get_mouse_mode() == Input.MOUSE_MODE_HIDDEN:
		Input.set_mouse_mode(Input.MOUSE_MODE_VISIBLE)
	
	if Input.is_action_just_pressed("language"):
		language = (language + 1) % TranslationServer.get_loaded_locales().size()
		TranslationServer.set_locale(TranslationServer.get_loaded_locales()[language])
		$"Captions/Visualization box".size.x = min(137 + $"Captions/3-way intersection text".get_content_width() + 3,293)
		$"Captions/Visualization text".position.x = $"Captions/Visualization box".position.x + $"Captions/Visualization box".size.x + 2
		$"Captions/Visualization text".size.x = min($"Captions/Visualization text".get_content_width(),637)
		$"Progress/count".position.x = 1110 - $"Progress/text".get_content_width() - 3
		update_tooltip(-1,-1)

# Input: Surface size, Case size.
# Output: Maze.
func generate(floor_surface,size):
	size = 1 # Not now for a version 1 of the maze generator.
	var floor_size = floor_surface/size
	# Recursive backtracker algorithm using stack for low-performance computers
	#
	# From Wikipedia (06/29/2024):
	# Randomized depth-first search
	# This algorithm, also known as the "recursive backtracker" algorithm, is a randomized version of the depth-first search algorithm.
	#
	# Frequently implemented with a stack, this approach is one of the simplest ways to generate a maze using a computer. Consider the space for a
	# maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then
	# selects a random neighbouring cell that has not yet been visited. The computer removes the wall between the two cells and marks the new cell as
	# visited, and adds it to the stack to facilitate backtracking. The computer continues this process, with a cell that has no unvisited neighbours
	# being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing
	# the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited,
	# causing the computer to backtrack all the way back to the beginning cell. We can be sure every cell is visited.
	#
	# As given above this algorithm involves deep recursion which may cause stack overflow issues on some computer architectures. The algorithm can be
	# rearranged into a loop by storing backtracking information in the maze itself. This also provides a quick way to display a solution, by starting
	# at any given point and backtracking to the beginning. 
	#
	# Mazes generated with a depth-first search have a low branching factor and contain many long corridors, because the algorithm explores as far as
	# possible along each branch before backtracking.
	#
	# Iterative implementation (with stack)
	#
	# A disadvantage of the first approach is a large depth of recursion – in the worst case,
	# the routine may need to recur on every cell of the area being processed, which may exceed the maximum recursion stack depth in many environments.
	# As a solution, the same backtracking method can be implemented with an explicit stack, which is usually allowed to grow much bigger with no harm.
	#
	#	1. Choose the initial cell, mark it as visited and push it to the stack
	#	2. While the stack is not empty
	#		1. Pop a cell from the stack and make it a current cell
	#		2. If the current cell has any neighbours which have not been visited
	#			1. Push the current cell to the stack
	#			2. Choose one of the unvisited neighbours
	#				1. Remove the wall between the current cell and the chosen cell
	#				2. Mark the chosen cell as visited and push it to the stack
	
	# 2D cells
	var cells = []
	# But first:
	# Our game is going to have its own rules for making the maze. Recall there is a distance between walls.
	# All algorithms will assume that the size of the walls around our cells doesn't matter at all. On the
	# contrary, recall there is a size for the floor of the backrooms. If we didn't consider the size for
	# the walls, we will find walls of a thickness of a paper and they will be out of touch for a backroom.
	#
	# Walls thickness must be considered: we do not need to make a new layer above the cells to mark the
	# walls around the cells but we can reuse the existing cells to mark walls around them that is for
	# each cell, there is exactly 8 cells of walls around it. It will make sense and won't cause a problem
	# to any algorithm in existence as we can simply skip the wall cell.
	
	# We will enclose the edges of the floor by walls.
	# For each cell:
	# - 0 means the cell is free
	# - 1 means the cell is a wall
	# - 2 means the cell was visited
	for x in range(floor_size.x):
		cells.append([])
		cells[x].resize(floor_size.y)
		cells[x].fill(0)
		cells[x][0] = 1 # The first row will always be walls
	for y in range(1,floor_size.y-1):
		# Add walls on the edges of the floor
		cells[0][y] = 1
		cells[floor_size.x-1][y] = 1
	for x in range(floor_size.x):
		cells[x][floor_size.y-1] = 1 # We finish the last row with walls
	# How many cells are really available? We need another calculation for that.
	# Recall that each cell will have exactly 8 walls cells around it. Since there are 8 walls cells around a
	# cell, that means a cell takes a cell above and under, left and right for walls.
	#
	# 2 more rules:
	# 1. A cell is allowed to own the walls at the edges of the floor.
	# 2. A new cell will share another cell's walls if there are existing walls created by this previous cell.
	#
	# As a result, the first cell will have 8 walls around it, the next ones 8-3 = 5 walls from by sharing the
	# previous cell's walls, all the way up until the edge of the floor.
	var free_x = int(1 + (floor_size.x - 3)/2) # First cell will take 3 cases for walls, the next ones 2.
	var free_y = int(1 + (floor_size.y - 3)/2) # Ditto.
	# Apply the instructions from Wikipedia:
	var stack = []
	# 1. Choose the initial cell, mark it as visited and push it to the stack
	var cur = [2*(randi() % free_x) + 1,2*(randi() % free_y) + 1] # Start with the cells, add +1 to find the free cell
	cells[cur[0]][cur[1]] = 2
	stack.append(cur)
	# 2. While the stack is not empty
	while stack.size() != 0:
		# 1. Pop a cell from the stack and make it a current cell
		cur = stack.back()
		stack.pop_back()
		# 2. If the current cell has any neighbours which have not been visited
		var sides = []
		if cur[1]-2 > -1 and cells[cur[0]][cur[1]-2] == 0: # Up
			sides.append([cur[0],cur[1]-2])
		if cur[0]+2 < floor_size.x and cells[cur[0]+2][cur[1]] == 0: # Right
			sides.append([cur[0]+2,cur[1]])
		if cur[1]+2 < floor_size.y and cells[cur[0]][cur[1]+2] == 0: # Down
			sides.append([cur[0],cur[1]+2])
		if cur[0]-2 > -1 and cells[cur[0]-2][cur[1]] == 0: # Left
			sides.append([cur[0]-2,cur[1]])
		if sides.size():
			# 1. Push the current cell to the stack
			stack.append(cur)
			# 2. Choose one of the unvisited neighbours
			var next = sides[randi() % sides.size()]
			# 1. Remove the wall between the current cell and the chosen cell
			# 2. Mark the chosen cell as visited and push it to the stack
			cells[ cur[0] + (next[0]-cur[0])/2 ][ cur[1] + (next[1]-cur[1])/2 ] = 2
			cells[next[0]][next[1]] = 2
			stack.append(next)
	# When we are done with generating the maze, fill the remaining "free" cells with walls.
	for x in range(cells.size()):
		for y in range(cells[x].size()):
			if cells[x][y] == 0:
				cells[x][y] = 1
	return cells

# Input: Surface size, Case size, Render cells.
func generate_and_record(floor_size,cells):
	var progress_speed = (1/floor_size.x + 1/floor_size.y)
	generating = true
	
	for x in range(floor_size.x):
		update_cell(x,0,1)
	if !generating:
		return false
	await get_tree().create_timer(progress_speed).timeout
	for y in range(1,floor_size.y-1):
		for x in range(floor_size.x):
			update_cell(x,y,0)
		
		update_cell(0,y,1)
		if !generating:
			return false
		await get_tree().create_timer(progress_speed).timeout
		update_cell(floor_size.x-1,y,1)
		if !generating:
			return false
		await get_tree().create_timer(progress_speed).timeout
	for x in range(floor_size.x):
		update_cell(x,floor_size.y-1,1)
	
	var free_x = int(1 + (floor_size.x - 3)/2)
	var free_y = int(1 + (floor_size.y - 3)/2)
	var free_cells = free_x*free_y
	var progress = 0
	$"Progress".visible = true
	update_progress(progress,free_cells)
	
	var stack = []
	
	# Mark available cells for visualization
	for x in range(free_x):
		for y in range(free_y):
			update_cell(2*x+1,2*y+1,3)
	if !generating:
		return false
	await get_tree().create_timer(progress_speed).timeout
	# Mark walls cells for visualization
	for x in range(1,cells.size()-1):
		for y in range(1,cells[x].size()-1):
			if y % 2 == 0:
				update_cell(x,y,4)
			elif 2*x < cells.size()-1 and y < cells[x].size()-1:
				update_cell(2*x,y,4)
	# Copy the untouched maze (preview) into JS animation
	JS_animation = [floor_size.x,floor_size.y,[]]
	for x in range(floor_size.x):
		JS_animation[2].append([])
		for y in range(floor_size.y):
			JS_animation[2][x].append(get_cell_state(x,y))
	
	var cur = [2*(randi() % free_x) + 1,2*(randi() % free_y) + 1]
	update_cell(cur[0],cur[1],2)
	progress += 1
	update_progress(progress,free_cells)
	JS_animation.append(cur[0])
	JS_animation.append(cur[1])
	JS_animation.append(2)
	if !generating:
		return false
	await get_tree().create_timer(progress_speed).timeout
	stack.append(cur)
	
	while stack.size() != 0:
		cur = stack.back()
		stack.pop_back()
		
		var unchecked = [ [cur[0],cur[1]-2] , [cur[0]+2,cur[1]] , [cur[0],cur[1]+2] , [cur[0]-2,cur[1]] ] # Up, Right, Down, Left
		var sides = []
		for pos in unchecked:
			if get_cell_state(pos[0],pos[1]) == 0 or get_cell_state(pos[0],pos[1]) == 3 or get_cell_state(pos[0],pos[1]) == 4:
				sides.append(pos)
		unchecked = [ [cur[0],cur[1]-1] , [cur[0]+1,cur[1]] , [cur[0],cur[1]+1] , [cur[0]-1,cur[1]] ]
		var connected = []
		for pos in unchecked:
			if get_cell_state(pos[0],pos[1]) == 2 or get_cell_state(pos[0],pos[1]) == 5:
				connected.append(pos)
		if sides.size():
			stack.append(cur)
			# We consider an intersection to be a cell with 3 sides connected to the cell
			if connected.size() == 2: # It is 2 as the algorithm always resumes from a +1 connected cell (2+1 = 3)
				update_cell(cur[0],cur[1],5) # Mark the cell as intersection for render only
				JS_animation.append(cur[0])
				JS_animation.append(cur[1])
				JS_animation.append(5)
			var next = sides[randi() % sides.size()]
			
			update_cell(cur[0] + (next[0]-cur[0])/2, cur[1] + (next[1]-cur[1])/2, 2)
			JS_animation.append(cur[0] + (next[0]-cur[0])/2)
			JS_animation.append(cur[1] + (next[1]-cur[1])/2)
			JS_animation.append(2)
			if !generating:
				return false
			await get_tree().create_timer(progress_speed).timeout
			update_cell(next[0],next[1],2)
			progress += 1
			update_progress(progress,free_cells)
			JS_animation.append(next[0])
			JS_animation.append(next[1])
			JS_animation.append(2)
			if !generating:
				return false
			await get_tree().create_timer(progress_speed).timeout
			stack.append(next)
	for x in range(cells.size()):
		for y in range(cells[x].size()):
			if get_cell_state(x,y) == 0 or get_cell_state(x,y) == 4:
				update_cell(x,y,1)
	JS_animation.append(-1)
	JS_animation.append(-1)
	JS_animation.append(-1)
	generating = false
	return true