I'm writing this answer with the intent to help you learn.
Yet, I should say DMGregory is correct. Pick an algorithm based on what you want for your game. And might get rid of the invalidation process entirely too.
On your solution
In the spirit of teaching and learning, I'll look at your implementation. I'll also point out that Godot can has an A* solution built-in. I'll get to that.
Getting the Neighbors
As you have correctly identified, you need to be able to query which are the valid neighbors for a cell.
But this is not right:
func getNeighbors(cell, maze):
for i in range(maze.size()):
for j in range(maze[i].size()):
if maze[cell.x][cell.y] == wall:
return
# add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
return neighbors
Here you are adding to - presumably - a field neighbors, which you also return. So the field neighbors would have all the elements added across all the calls to getNeighbors, including duplicates. And, remember, we only want the neighbors of the specific cell.
So, first of all, make neighbors local (I have also added types to the signature):
func getNeighbors(cell:Vector2, maze:Array) -> Array:
var neighbors := []
for i in range(maze.size()):
for j in range(maze[i].size()):
if maze[cell.x][cell.y] == wall:
return
# add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
return neighbors
Second, you don't need to iterate over the whole maze to find the neighbors. You only need to check adjacent cells (to which the comment you have alludes to). So do that:
func getNeighbors(cell:Vector2, maze:Array) -> Array:
var neighbors := []
for i in [cell.x - 1, cell.x, cell.x + 1]:
for j in [cell.y - 1, cell.y, cell.y + 1]:
if maze[i][j] == wall:
return
# add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
return neighbors
Wait a minute. Something tells me your maze is rows not columns. Look you have it defined like this:
var maze = [[2, 0, 0], [1, 1, 1], [1, 1, 3]]
Rearrange and it is like this:
var maze = [
[2, 0, 0],
[1, 1, 1],
[1, 1, 3]
]
So the outer array is the vertical, and the inner is the horizontal. Thus, it is like this:
func getNeighbors(cell:Vector2, maze:Array) -> Array:
var neighbors := []
for i in [cell.x - 1, cell.x, cell.x + 1]:
for j in [cell.y - 1, cell.y, cell.y + 1]:
if maze[j][i] == wall:
return
# add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
return neighbors
Better yet:
func getNeighbors(cell:Vector2, maze:Array) -> Array:
var neighbors := []
for j in [cell.y - 1, cell.y, cell.y + 1]:
for i in [cell.x - 1, cell.x, cell.x + 1]:
if maze[j][i] == wall:
return
# add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
return neighbors
Ah, skip the cell itself:
func getNeighbors(cell:Vector2, maze:Array) -> Array:
var neighbors := []
for j in [cell.y - 1, cell.y, cell.y + 1]:
for i in [cell.x - 1, cell.x, cell.x + 1]:
if i == cell.x and j == cell.y:
continue
if maze[j][i] == wall:
return
# add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
return neighbors
Skip walls. Don't exit on walls:
func getNeighbors(cell:Vector2, maze:Array) -> Array:
var neighbors := []
for j in [cell.y - 1, cell.y, cell.y + 1]:
for i in [cell.x - 1, cell.x, cell.x + 1]:
if i == cell.x and j == cell.y:
continue
if maze[j][i] == wall:
continue
# add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
return neighbors
And, yes, add to the neighbors:
func getNeighbors(cell:Vector2, maze:Array) -> Array:
var neighbors := []
for j in [cell.y - 1, cell.y, cell.y + 1]:
for i in [cell.x - 1, cell.x, cell.x + 1]:
if i == cell.x and j == cell.y:
continue
if maze[j][i] == wall:
continue
neighbors.append(Vector2(i, j))
return neighbors
Interlude: Dictionary
Let me introduce you to Dictionary.
You can declare a Dictionary like this:
var dict := {}
Or like this:
var dict := Dictionary.new()
You can set (adds if the element is not there) elements like this:
dict[key] = value
And you can get elements like this:
value = dict[key]
Crucially, the dictionary won't store two elements on the same key. There will not be duplicated keys. If I do this:
dict[key] = value
dict[key] = another_value
The second replaces the first one.
You might want to check if the element is there (since getting a elements that isn't there is an error):
if dict.has(key):
value = dict[key]
Or you can use get which lets you define a fallback which is returned if the element isn't there:
value = dict.get(key, fallback)
Oh, and you remove from the dictionary like this:
dict.erase(key)
Therefore, we add whatever (e.g. null or true) we can use the keys as a set. Thus, this is a set:
var set := {}
You add an element to the set like this:
set[value] = true
Note that the set cannot have a value twice.
You remove an element from the set like this:
set.erase(value)
And you check if the set has a value like this:
set.has(value)
This is faster than adding the elements to an Array and then checking if the Array has the elements (with has) because looking in the array requires Godot to iterate over it, but for the set... I mean Dictionary Godot creates an index for quick lookup.
Breadth-first search
Ok, let us look to your code:
func bfs():
var queue = []
var source = Vector2(0, 0)
var destination = Vector2(2, 2)
queue.append(source)
while queue.size() > 0:
var current = queue.pop_back()
var neighbors = getNeighbors (current, maze)
for n in neighbors:
queue.append(n)
Hmm… You are hard-coding source and destination. Why do you have them in the maze then? Those are two sources of truth. That is not good, because it means that you need to update in two different places if it changes (and if you forget, or you do it wrong, you got a bug).
I'll promote them to parameters. The method call this can pass them. In fact the method that calls this can both pass them and also write them to the maze.
func bfs(source:Vector2, destination:Vector2):
var queue = []
queue.append(source)
while queue.size() > 0:
var current = queue.pop_back()
var neighbors = getNeighbors (current, maze)
for n in neighbors:
queue.append(n)
In fact, traditionally the graph maze is a parameter too. You made it a parameter in the prior method, so why not here too?
func bfs(maze:Array, source:Vector2, destination:Vector2):
var queue = []
queue.append(source)
while queue.size() > 0:
var current = queue.pop_back()
var neighbors = getNeighbors (current, maze)
for n in neighbors:
queue.append(n)
On your main issue: visited cells. You need to know which cells you have explored already. How to do that? The simplest solution is to add them to an Array… But we will use a set, I mean a Dictionary.
func bfs(maze:Array, source:Vector2, destination:Vector2):
var queue := []
var visited_cells := {}
queue.append(source)
while queue.size() > 0:
var current = queue.pop_back()
var neighbors = getNeighbors (current, maze)
for n in neighbors:
queue.append(n)
And the source should be marked visited right away:
func bfs(maze:Array, source:Vector2, destination:Vector2):
var queue := []
var visited_cells := {}
visited_cells[source] = true
queue.append(source)
while queue.size() > 0:
var current = queue.pop_back()
var neighbors = getNeighbors (current, maze)
for n in neighbors:
queue.append(n)
And yes, you add the source to the queue. I'll leave it as you have it, but know you could have done var queue := [source].
We iterate until the queue is empty. Again, I'll leave it as you have it, but know there is an empty method you can use.
And you dequeue… pop_back removes and returns the last element. And append adds at the end. Thus, the combination of pop_back and append means you are using your Array as a stack not as a queue.
There are two built-in ways to use an Array as a queue:
- With
pop_back and push_front.
- With
pop_front and push_back (append).
We could take our time and implement something else (pre-allocate and use indexing), but let's do with what is available already since it is less error prone (look into it if you want).
Operations on the back of the Array are faster. Although we will do both operations equally as much (we will remove everything we add), I'll add at the back since it is in the inner loop (I expect elements to be added in quick succession, at least at the start). Thus:
func bfs(maze:Array, source:Vector2, destination:Vector2):
var queue := []
var visited_cells := {}
visited_cells[source] = true
queue.append(source)
while queue.size() > 0:
var current:Vector2 = queue.pop_front()
var neighbors = getNeighbors (current, maze)
for n in neighbors:
queue.append(n)
Next we check if it is the goal. If it is, we return the path… Wait, we also need to declare the path we are going to return! That is an issue, because we will actually be building multiple paths. Well, we can use a Dictionary for this… But for the moment I'll return an empty path.
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
var paths := {}
var queue := []
var visited_cells := {}
visited_cells[source] = true
queue.append(source)
while queue.size() > 0:
var current:Vector2 = queue.pop_front()
if current == destination:
return [] # TODO
var neighbors = getNeighbors (current, maze)
for n in neighbors:
queue.append(n)
return [] # TODO
Yes, we iterate over the neighbors. And we skip the ones that we visited:
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
var paths := {}
var queue := []
var visited_cells := {}
visited_cells[source] = true
queue.append(source)
while queue.size() > 0:
var current:Vector2 = queue.pop_front()
if current == destination:
return [] # TODO
var neighbors = getNeighbors (current, maze)
for n in neighbors:
if visited_cells.has(n):
continue
queue.append(n)
return [] # TODO
Now we mark the cell as visited:
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
var paths := {}
var queue := []
var visited_cells := {}
visited_cells[source] = true
queue.append(source)
while queue.size() > 0:
var current:Vector2 = queue.pop_front()
if current == destination:
return [] # TODO
var neighbors = getNeighbors (current, maze)
for n in neighbors:
if visited_cells.has(n):
continue
visited_cells[n] = true
queue.append(n)
return [] # TODO
We make the… current the parent of the neighbor … What we are doing is the path up to the neighbor. That is, we need to say that to get to the neighbor, we first need to get to the current cell.
And I said we will use a Dictionary for the paths. The plan is to use the cells as keys, and store the paths as values. So, first of all, the path to get to the source, is just the source:
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
var paths := {}
var queue := []
var visited_cells := {}
visited_cells[source] = true
queue.append(source)
paths[source] = [source]
while queue.size() > 0:
var current:Vector2 = queue.pop_front()
if current == destination:
return [] # TODO
var neighbors = getNeighbors (current, maze)
for n in neighbors:
if visited_cells.has(n):
continue
visited_cells[n] = true
queue.append(n)
return [] # TODO
Let me re-arrange that:
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
var queue := []
queue.append(source)
var visited_cells := {}
visited_cells[source] = true
var paths := {}
paths[source] = [source]
while queue.size() > 0:
var current:Vector2 = queue.pop_front()
if current == destination:
return [] # TODO
var neighbors = getNeighbors (current, maze)
for n in neighbors:
if visited_cells.has(n):
continue
visited_cells[n] = true
queue.append(n)
return [] # TODO
Now, the path to get to the neighbor is the path to the current cell, plus the neighbor (and yes, we can just add Arrays here):
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
var queue := []
queue.append(source)
var visited_cells := {}
visited_cells[source] = true
var paths := {}
paths[source] = [source]
while queue.size() > 0:
var current:Vector2 = queue.pop_front()
if current == destination:
return [] # TODO
var neighbors = getNeighbors (current, maze)
for n in neighbors:
if visited_cells.has(n):
continue
visited_cells[n] = true
paths[n] = paths[current] + [n]
queue.append(n)
return [] # TODO
And yes, we add to the queue…
Finally we return the path to the destination:
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
var queue := []
queue.append(source)
var visited_cells := {}
visited_cells[source] = true
var paths := {}
paths[source] = [source]
while queue.size() > 0:
var current:Vector2 = queue.pop_front()
if current == destination:
return paths[destination] # There is a path
var neighbors = getNeighbors (current, maze)
for n in neighbors:
if visited_cells.has(n):
continue
visited_cells[n] = true
paths[n] = paths[current] + [n]
queue.append(n)
return [] # There isn't a path
Please notice that Breadth-first search will find a path if there is a path, but it might not be the shortest one.
What I mention in the next few paragraphs is beyond this question, but I want to bring it up if you want to continue learning how these work:
If you want to make sure you get the shortest one, you want to implement Dijkstra's algorithm. The reason you don't see game developers talking about Dijkstra's algorithm as much is because it is exhaustive, in fact it compute the shortest path between all the points.
However we don't need to be exhaustive to get the shortest path between two points, we need a way to guess what parts to check… We get that from adding an heuristic. Which is what the famous A* does.
It is also possible to further modify A* to limit its memory use or some other constraints. Usually in exchange of losing the guarantee of getting the shortest path (instead we get a short enough path).
Godot A*
Alright, if you are using Godot, you can save yourself the trouble of implementing those algorithms and use the AStar2D class (there is also a 3D counterpart). They implements - as the name suggests - the A* algorithm.
However, you needed the lessons about using arrays and dictionaries we went over. Thus, I encourage you to - at least - go over the code I presented before.
You can use the class AStar2D by adding cells with add_point. It requires ids. It is a good idea to be clever with the ids so you can compute the id for a given position. Something like this would work assuming the maze is rectangular:
var astar := AStar2D.new()
var height := maze.size()
var width := maze[0].size()
for j in height:
for i in width:
var id := j * width + i
astar.add_point(id, Vector2(i, j))
Here the id is the number of the row multiplied by the length of the row (which gives you how many elements were before the start of the row) plus the position inside the row.
We, of course, don't need to add impasable points, so skip walls:
var astar := AStar2D.new()
var height := maze.size()
var width := maze[0].size()
for j in height:
for i in width:
if maze[j][i] == wall:
continue
var id := j * width + i
astar.add_point(id, Vector2(i, j))
That also highlights that ids don't need to be continous. It is more important to be able to compute the id from the coordinates (which is why I didn't just have an id variable start at zero and increment it with each point).
You also want to connect them with connect_points. Which means we need to check the neighbors!
We are not going to connect to neighbors that has not been added. That includes:
- Positions outside the maze (we don't add those).
- Positions that are not passable (we don't add those).
- Positions that we haven't checked (when we check them we might add them).
In fact, we are not in a hurry to check positions ahead. When the loop gets to them, we can connect them (the connection is bidirectional by default). Thus, we can limit ourselves to position that we have already passed.
var astar := AStar2D.new()
var height := maze.size()
var width := maze[0].size()
for j in height:
for i in width:
if maze[j][i] == wall:
continue
var id := j * width + i
astar.add_point(id, Vector2(i, j))
for jn in [j - 1, j]:
for i in [i - 1, i]:
var idn := jn * width + in
if astar.has_point(idn):
astar.connect_points(idn, id)
I'll admit that the code above is a little too nested for my taste. If you see fit to refactor it by extracting functions, go ahead. In fact, you probably want to pass astar as a parameter because you will likely populate it once and query it multiple times.
Ah, of course, you will query the AStar! Use get_point_path:
var path := astar.get_point_path(
source.y * width + source.x,
destination.y * width + destination.x
)
And there is your path. Guaranteed to be the shortest. And with good performance.
Be aware that it is computing the path you ask for (it does not compute all the paths in advance). Thus, it is a good idea to hold on to the result while you are using it instead querying it every frame or something like that.
Wait… maze generation?
The challenging part was to check if any paths exist in the maze, and to return them. If there are no solutions, generate another maze. However, I don't know how to do this yet.
You are checking if the maze is valid. There are maze generation algorithms that can guarantee to generate a valid maze.
You are generating by placing walls at random:
I decided to generate each maze with specified width and height, then choose both the source and the destination cells, and finally randomly assign each cell to be either a space or a wall.
But you don't only know there isn't a path. You know, for each cell if there is a path.
Thus, instead of throwing away this maze, you could random-walk from the destination until it connects to one of the cells that has a path. Start by storing from where we are walking:
var walking := destination
The plan is to pick a neighbor at random. For this I'll declare a RandomNumberGenerator, and seed it with randomize:
var random := RandomNumberGenerator.new()
random.randomize()
Now compute the list of your possible neighbors:
var possible_neighbors := [
Vector2(walking.x - 1, walking.y - 1),
Vector2(walking.x, walking.y - 1),
Vector2(walking.x + 1, walking.y - 1),
Vector2(walking.x - 1, walking.y),
Vector2(walking.x + 1, walking.y),
Vector2(walking.x - 1, walking.y + 1),
Vector2(walking.x, walking.y + 1),
Vector2(walking.x + 1, walking.y + 1),
]
Make sure you aren't going outside the maze:
for index in range(possible_neighbors.size(), -1, -1, -1):
var n:Vector2 = possible_neighbors[index]
if n.x < 0.0 or n.x >= width or n.y < 0.0 or n.y >= height:
possible_neighbors.remove_at(index)
Note that I'm iterating backwards to avoid re-indexing.
Now pick at random:
var neighbor := possible_neighbors[
random.randi_range(0, possible_neighbors.size() - 1)
]
If it is a wall, carve it (I mean make it passable).
if maze[neighbor.y][neighbor.x] != wall:
maze[neighbor.y][neighbor.x] = space # something like this?
If it was already passable, then check if there is a path from the source to it (if you are inside the bfs method you can check if paths has it as a key, if you are using astar ask it for a path to it). If there is a path, you are done.
Otherwise set walking to the neighbor and repeat. Until you find that there is a path.
Addendum: The random-walk is random™. Nothing prevents it from going over cells it already went over. So keeping a list of visited cells (similar to breath-first search) can allow you prevent that. Similarly, if you use a weighted random (look it up), you can make it more likely for it to pick a position that is closer to the source (by vector distance). And the closer is a cell to the source the more likely there is a path from to source to that cell (that, by the way, is an heuristic). This improvements will make the carving process go faster.
Be aware that I came up with this approach because:
- I'm keeping the same vein of what you were doing.
- I think there is plenty for you to learn from it.
However, you will likely get better results by picking an algorithm based on what you want for your game.
