a game about throwing hammers made for the github game off
Diffstat (limited to 'classes/Maze.gd')
| -rw-r--r-- | classes/Maze.gd | 224 |
1 files changed, 112 insertions, 112 deletions
diff --git a/classes/Maze.gd b/classes/Maze.gd index 8e57fda..f64f92b 100644 --- a/classes/Maze.gd +++ b/classes/Maze.gd @@ -27,143 +27,143 @@ const _dirs := [Vector2i.UP, Vector2i.RIGHT, Vector2i.DOWN, Vector2i.LEFT] ## The image representation of this maze. var image: Image = null: - get: - if not image: - _gen_image() - return image + get: + if not image: + _gen_image() + return image func _init(p_size: Vector2i) -> void: - size = p_size - generate() - erase_walls() + size = p_size + generate() + erase_walls() ## Get a maze cells value. func get_cellv(cell: Vector2i) -> int: - return maze[cell.y][cell.x] + return maze[cell.y][cell.x] ## Turns a 4b tile into a array of walls. [code]4[/code] => [code][Vector2i.DOWN][/code]. static func tile_4b_to_wall_array(tile_4b: int) -> Array[Vector2i]: - var array: Array[Vector2i] = [] - for dir in _dirs: - if tile_4b & cell_walls[dir]: - array.append(dir) - return array + var array: Array[Vector2i] = [] + for dir in _dirs: + if tile_4b & cell_walls[dir]: + array.append(dir) + return array ## Turns a 4b tile into a array of paths. [code]4[/code] => [code][Vector2i.UP, Vector2i.LEFT, Vector2i.RIGHT][/code]. static func tile_4b_to_path_array(tile_4b: int) -> Array[Vector2i]: - var array: Array[Vector2i] = [] - for dir in cell_walls.keys(): - if not tile_4b & cell_walls[dir]: - array.append(dir) - return array + var array: Array[Vector2i] = [] + for dir in cell_walls.keys(): + if not tile_4b & cell_walls[dir]: + array.append(dir) + return array func _check_neighbours(cell: Vector2i, unvisited: Array[Vector2i]) -> Array[Vector2i]: - # checks if neighbour is visited. - # returns array of unvisited neighbours. - var list: Array[Vector2i] = [] - for n in cell_walls.keys(): - if cell + n in unvisited: - list.append(cell + n) - return list + # checks if neighbour is visited. + # returns array of unvisited neighbours. + var list: Array[Vector2i] = [] + for n in cell_walls.keys(): + if cell + n in unvisited: + list.append(cell + n) + return list func _set_cellv(cell: Vector2i, v: int) -> void: - maze[cell.y][cell.x] = v + maze[cell.y][cell.x] = v ## Generates the maze using the [url=https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_depth-first_search]recursive backtracker algorithm[/url]. func generate() -> void: - randomize() - var unvisited: Array[Vector2i] = [] - var stack: Array[Vector2i] = [] - - # fill maze - maze.clear() - for x in range(size.x): - var row: PackedInt32Array = [] - for y in range(size.y): - row.append(N|E|S|W) - unvisited.append(Vector2i(x, y)) - maze.append(row) - - var current := Vector2i(0, 0) - unvisited.erase(current) - - # recurive backtracking algorithm - while unvisited.size() > 0: - # check neighbours of current cell. - var neighbours := _check_neighbours(current, unvisited) - - # if neighbours exist, pick one at random and move in that direction. - # remove wall between current cell and neighbour cell. - if neighbours.size() > 0: - var next := neighbours[randi() % neighbours.size()] - stack.append(current) - - # remove wall from both cells. - var dir := next - current - var current_walls: int = get_cellv(current) - cell_walls[dir] - var next_walls: int = get_cellv(next) - cell_walls[-dir] - _set_cellv(current, current_walls) - _set_cellv(next, next_walls) - current = next - unvisited.erase(current) - elif stack: - # if neighbours don't exist, retrieve new current from stack. - current = stack.pop_back() + randomize() + var unvisited: Array[Vector2i] = [] + var stack: Array[Vector2i] = [] + + # fill maze + maze.clear() + for x in range(size.x): + var row: PackedInt32Array = [] + for y in range(size.y): + row.append(N|E|S|W) + unvisited.append(Vector2i(x, y)) + maze.append(row) + + var current := Vector2i(0, 0) + unvisited.erase(current) + + # recurive backtracking algorithm + while unvisited.size() > 0: + # check neighbours of current cell. + var neighbours := _check_neighbours(current, unvisited) + + # if neighbours exist, pick one at random and move in that direction. + # remove wall between current cell and neighbour cell. + if neighbours.size() > 0: + var next := neighbours[randi() % neighbours.size()] + stack.append(current) + + # remove wall from both cells. + var dir := next - current + var current_walls: int = get_cellv(current) - cell_walls[dir] + var next_walls: int = get_cellv(next) - cell_walls[-dir] + _set_cellv(current, current_walls) + _set_cellv(next, next_walls) + current = next + unvisited.erase(current) + elif stack: + # if neighbours don't exist, retrieve new current from stack. + current = stack.pop_back() ## Randomly remove walls. Prefers deleting 3 and 2 walled cells. func erase_walls() -> void: - randomize() - const three_walls: Array[int] = [7, 11, 13, 14] - const two_walls: Array[int] = [3, 5, 6, 9, 10, 12] - - for x in range(size.x): - for y in range(size.y): - if maze[y][x] in three_walls or maze[x][y] in two_walls or randi() % 3 == 0: - var cell := Vector2i(x, y) - var i := randi() % 4 - for _i in range(4): - var n: Vector2i = cell_walls.keys()[i] - i = wrapi(i + _i, 0, 3) - if get_cellv(cell) & cell_walls[n]: - var n_cell := (cell + n) - if n_cell.x > size.x - 1 or n_cell.y > size.y - 1 or n_cell.x < 0 or n_cell.y < 0: - continue - var walls: int = get_cellv(cell) - cell_walls[n] - var n_walls: int = get_cellv(n_cell) - cell_walls[-n] - if ( - (x == 0 and walls & W) - or (y == 0 and walls & N) - or (x == size.x and walls & E) - or (y == size.y and walls & S) - or (n_cell.x == 0 and n_walls & W) - or (n_cell.y == 0 and n_walls & N) - or (n_cell.x == size.x and n_walls & E) - or (n_cell.y == size.y and n_walls & S) - ): - continue - if walls in three_walls or n_walls in three_walls: - continue - _set_cellv(cell, walls) - _set_cellv(n_cell, n_walls) - break + randomize() + const three_walls: Array[int] = [7, 11, 13, 14] + const two_walls: Array[int] = [3, 5, 6, 9, 10, 12] + + for x in range(size.x): + for y in range(size.y): + if maze[y][x] in three_walls or maze[x][y] in two_walls or randi() % 3 == 0: + var cell := Vector2i(x, y) + var i := randi() % 4 + for _i in range(4): + var n: Vector2i = cell_walls.keys()[i] + i = wrapi(i + _i, 0, 3) + if get_cellv(cell) & cell_walls[n]: + var n_cell := (cell + n) + if n_cell.x > size.x - 1 or n_cell.y > size.y - 1 or n_cell.x < 0 or n_cell.y < 0: + continue + var walls: int = get_cellv(cell) - cell_walls[n] + var n_walls: int = get_cellv(n_cell) - cell_walls[-n] + if ( + (x == 0 and walls & W) + or (y == 0 and walls & N) + or (x == size.x and walls & E) + or (y == size.y and walls & S) + or (n_cell.x == 0 and n_walls & W) + or (n_cell.y == 0 and n_walls & N) + or (n_cell.x == size.x and n_walls & E) + or (n_cell.y == size.y and n_walls & S) + ): + continue + if walls in three_walls or n_walls in three_walls: + continue + _set_cellv(cell, walls) + _set_cellv(n_cell, n_walls) + break func _gen_image() -> void: - var img = Image.create(size.x * 3, size.y * 3, false, Image.FORMAT_L8) - var position := Vector2i.ZERO - for i in len(maze): - for j in len(maze[i]): - var paths := Maze.tile_4b_to_path_array(maze[i][j]) - if not paths.is_empty(): - var middle := position + Vector2i.ONE - img.set_pixelv(middle, Color.WHITE) - for path in paths: - img.set_pixelv(middle + path, Color.WHITE) - position.x += 3 - position.y += 3 - position.x = 0 - image = img + var img = Image.create(size.x * 3, size.y * 3, false, Image.FORMAT_L8) + var position := Vector2i.ZERO + for i in len(maze): + for j in len(maze[i]): + var paths := Maze.tile_4b_to_path_array(maze[i][j]) + if not paths.is_empty(): + var middle := position + Vector2i.ONE + img.set_pixelv(middle, Color.WHITE) + for path in paths: + img.set_pixelv(middle + path, Color.WHITE) + position.x += 3 + position.y += 3 + position.x = 0 + image = img |