Version 4.3
Summery
I’m creating a puzzle game, but having trouble with generating the puzzle solution. The essence of the game is selecting the pieces in the correct sequence so you select all pieces in one move.
The issue I’m having is generating the puzzle solution which determines what pieces go where. I want it to randomly generate so I can create and endless amount of levels. Here is how it works, or at least how it should work.
The game has a grid, each space represented by a Vector2i variable. I need to generate a path that starts on a random space, moves through the entire grid, and then returns each space by the order they were visited.
Additional Details
- The path can only visit a space one time.
- Each space must be adjacent to the previous selected space.
- Selection can be vertical horizontal, or diagonal.
- The path should visit every single space, (but I’ll settle for 70%)
This code generates a path sometimes, but in a grid of 10x10 it fails roughly 1 out of every 5 attempts, sometimes more.
> @export var grid_size : Vector2i
> @onready var grid : Dictionary = initialize_grid()
> enum Neighbor {
> N = 1,
> NE = 2,
> E = 4,
> SE = 8,
> S = 16,
> SW = 32,
> W = 64,
> NW = 128
> }
> var path : Array[Vector2i]
>
> #Called when the node enters the scene tree for the first time.
> func _ready() -> void:
> for key in grid:
> grid[key] = validate_neighbors(key)
>
> create_path()
>
> func initialize_grid() -> Dictionary:
> var new_grid = {}
> for x in grid_size.x:
> for y in grid_size.y:
> new_grid[Vector2i(x, y)] = 0
>
> return new_grid
>
> func create_path() -> void:
> path.clear()
> path.append(Vector2i(randi() % grid_size.x, randi() % grid_size.y))
> var max_spaces = grid_size.x * grid_size.y
> while path.size() < max_spaces:
> var timer = get_tree().create_timer(0.01)
> await timer.timeout
> validate_surrounding_neighbors(path.back())
> var neighbors = get_neighbors(path.back())
> print("neighbors found ", neighbors.size())
> if neighbors:
> path.append(neighbors[randi() % neighbors.size()])
> else:
> if path.size() >= int(max_spaces * 0.7):
> break
> else:
> print("no neighbors at ", path.back(), "backtracking")
> #grid[path.back()] = validate_neighbors(path.back())
> remove_neighbor(path[path.size() - 2], path[path.size() - 1])
> path.pop_back()
> print("final path ", path.size(), " spaces out of ", max_spaces)
> print(path)
> print("path is valid: ", validate_path())
>
> func validate_path() -> bool:
> for point in path:
> var frquency := 0
> for otherpoint in path:
> if point == otherpoint:
> frquency += 1
> if frquency != 1:
> return false
>
> return true
>
> func validate_neighbors(position : Vector2i) -> int:
> var neighbors := 0
>
> if grid.has(position + Vector2i.UP) && !path.has(position + Vector2i.UP):
> neighbors |= Neighbor.N
>
> if grid.has(position + Vector2i.UP + Vector2i.LEFT) && !path.has(position + Vector2i.UP + Vector2i.LEFT):
> neighbors |= Neighbor.NW
>
> if grid.has(position + Vector2i.LEFT) && !path.has(position + Vector2i.LEFT):
> neighbors |= Neighbor.W
>
> if grid.has(position + Vector2i.DOWN + Vector2i.LEFT) && !path.has(position + Vector2i.DOWN + Vector2i.LEFT):
> neighbors |= Neighbor.SW
>
> if grid.has(position + Vector2i.DOWN) && !path.has(position + Vector2i.DOWN):
> neighbors |= Neighbor.S
>
> if grid.has(position + Vector2i.DOWN + Vector2i.RIGHT) && !path.has(position + Vector2i.DOWN + Vector2i.RIGHT):
> neighbors |= Neighbor.SE
>
> if grid.has(position + Vector2i.RIGHT) && !path.has(position + Vector2i.RIGHT):
> neighbors |= Neighbor.E
>
> if grid.has(position + Vector2i.UP + Vector2i.RIGHT) && !path.has(position + Vector2i.UP + Vector2i.RIGHT):
> neighbors |= Neighbor.NE
>
> return neighbors
>
> func validate_surrounding_neighbors(coord : Vector2i) -> void:
> var neighbors := get_neighbors(coord)
> for neighbor in neighbors:
> grid[neighbor] = validate_neighbors(neighbor)
>
> func remove_neighbor(coord : Vector2i, neighbor : Vector2i) -> void:
> var direction : int = 0
> var offset := neighbor - coord
> match offset:
> Vector2i(0, -1):
> direction = Neighbor.N
> Vector2i(1, -1):
> direction = Neighbor.NE
> Vector2i(1, 0):
> direction = Neighbor.E
> Vector2i(1, 1):
> direction = Neighbor.SE
> Vector2i(0, 1):
> direction = Neighbor.S
> Vector2i(-1, 1):
> direction = Neighbor.SW
> Vector2i(-1, 0):
> direction = Neighbor.W
> Vector2i(-1, -1):
> direction = Neighbor.NW
> _:
> return
>
>
> grid[coord] &= ~direction
>
> func get_neighbors(coord : Vector2i) -> Array[Vector2i]:
> var neighbor_list : Array[Vector2i] = []
> var neighbors = grid[coord]
> if neighbors & Neighbor.N:
> neighbor_list.append(coord + Vector2i.UP)
> if neighbors & Neighbor.NE:
> neighbor_list.append(coord + Vector2i.UP + Vector2i.RIGHT)
> if neighbors & Neighbor.E:
> neighbor_list.append(coord + Vector2i.RIGHT)
> if neighbors & Neighbor.SE:
> neighbor_list.append(coord + Vector2i.DOWN + Vector2i.RIGHT)
> if neighbors & Neighbor.S:
> neighbor_list.append(coord + Vector2i.DOWN)
> if neighbors & Neighbor.SW:
> neighbor_list.append(coord + Vector2i.DOWN + Vector2i.LEFT)
> if neighbors & Neighbor.W:
> neighbor_list.append(coord + Vector2i.LEFT)
> if neighbors & Neighbor.NW:
> neighbor_list.append(coord + Vector2i.UP + Vector2i.LEFT)
>
> return neighbor_list