# 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><</button>
<button id="pause" onclick="pause_replay();" disabled>Pause</button>
<button id="forward" onclick="set_frame(1);">></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/"><https://www.gnu.org/licenses/></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