extends Node3D
const SPACE = 0
const WALL = 1
const BRICK = preload("res://Scenes/brick.tscn")

var maze := []
var bricks := []
var maze_width := 10
var maze_height := 10
var offsetX := 2
var offsetZ := 2
var tile_size := 0.6
var brickY
var brick_width

func make_maze(cols, rows):
    maze_width = cols;
    maze_height = rows;

    # set the offsets so that (0, 0) is in the center of the maze
    offsetX = maze_width / 2;
    offsetZ = maze_height / 2;
     
    # allocate the array
    make_tables(cols, rows)
                       
    # create the CellType maze
    prim()
    # create the maze of wall 3D objects
    build_maze()

# Create the two 2D tables. It fills the maze with walls 
# and the bricks with null
func make_tables(cols, rows):
    maze = []
    bricks = []
    for i in cols:
        maze.append([])
        bricks.append([])
        for j in rows:
            maze[i].append(WALL)
            bricks[i].append(null)

# Initialize all the cells in the maze with the same value
func init_maze(val):
    for i in maze_width:
        for j in maze_height:
              maze[i][j] = val

# returns the cells neighboring the given one in a list
# considers a 4-cell neighborhood.
# returns less than 4 nodes if close to a border
func neighbors(cx, cz):
    var neighbs = []
    if cx > 1:
        neighbs.append(Vector2i(cx - 1, cz))
    if cx < maze_width - 2:
        neighbs.append(Vector2i(cx + 1, cz))
    if cz > 1:
        neighbs.append(Vector2i(cx, cz - 1))
    if cz < maze_height - 2:
        neighbs.append(Vector2i(cx, cz + 1))
    return neighbs

# converts a column number into a position on the stage
func col2X(c):
    return c * tile_size - offsetX * tile_size

# converts a column number into a position on the stage
func row2Z(r):
    return r * tile_size - offsetZ * tile_size

# converts an x position to a column number
func x2col(xVal):
    return offsetX + (int)(xVal / tile_size)

# converts a z position to a row number
func z2row(zVal):
    return offsetZ + (int)(zVal / tile_size)

# Builds the physical maze out of wall objects, 
# assuming that we have generated it beforehand in the maze array.
# Assumes the bricks array was created with the right size and contains null values
func build_maze():
    tile_size = brick_width + 0.001; # a small gap between the bricks to be able to see them
    for i in maze_width:
        for j in maze_height:
            if maze[i][j] == WALL: # place a brick where we have a wall in the maze
                bricks[i][j] = BRICK.instantiate()
                add_child(bricks[i][j])
                bricks[i][j].position = Vector3(col2X(i), brickY, row2Z(j))
            else:
                bricks[i][j] = null

# counts the spaces in the list
func count_spaces(neighb):
    var count := 0
    for n in neighb:
        if maze[n.x][n.y] == SPACE:
            count += 1
    return count

# checks if the frontier contains a point of coordinates (dx, dz)
func contains_node(frontier, dx, dz):
    for n in frontier:
        if n.x == dx and n.y == dz:
            return true
    return false

# implementation of Prim's algorithm to generate a maze
func prim():
    var node
    var cx
    var cz
    var dx
    var dz
    var neighbs

    # start by filling up the maze with walls
    init_maze(WALL)

    # start from the center of the maze with a space
    # that's where the player should be
    var startx = maze_width / 2
    var startz = maze_height / 2

    # the frontier contains all the neighbors of the starting position
    var frontier = neighbors(startx, startz)
    maze[startx][startz] = SPACE

    while frontier.size() > 0:             # while we still have nodes in the frontier
        node = frontier.pick_random()
        cx = node.x;
        cz = node.y;
        frontier.erase(node)               # remove it from the frontier
        neighbs = neighbors(cx, cz)
        if count_spaces(neighbs) == 1:     # make sure it doesn't close a cycle
            maze[cx][cz] = SPACE           # make it a space
            for nod in neighbs:
                dx = nod.x;
                dz = nod.y;
                # if the neighbor is not a space
                if maze[dx][dz] != SPACE:
                    var n = neighbors(dx, dz)
                    # if it has exactly one space among its neighbors and is not already in the frontier
                    if count_spaces(n) == 1 and not contains_node(frontier, dx, dz):
                        #add this neighbor to the frontier;
                        frontier.append(Vector2i(dx, dz))

# Called when the node enters the scene tree for the first time.
func _ready() -> void:
    var brick = BRICK.instantiate()
    add_child(brick)
    brickY = brick.position.y
    brick_width = brick.find_child("MeshInstance3D").mesh.size.x
    brick.queue_free()
    print(Global.level)
    make_maze(10, 10)


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