Create Mazes in Python: Using recursive and A* search algorithm's
In this post describes you how to solve mazes problem using two algorithms implemented in Python program: a simple recursive algorithm and the A* search algorithm.this article help you to find the nearest cell by using python programming language.
Maze
The maze we are going to use in this article is 6
cells by 6 cells. The walls are colored in blue. The starting cell is at the
bottom left (x=0 and y=0) colored in green. The ending cell is at the top right
(x=5 and y=5) colored in green. We can only move horizontally or vertically 1
cell at a time.
Recursive walk
We use a nested list of integers to represent the
maze. The values are the following:
·
0: empty cell
·
1: unreachable
cell
·
2: ending cell
·
3: visited cell
grid =[[0, 0, 0, 0, 0, 1],
[1, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0],
[0, 1, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 2]]
This is a very simple algorithm which does the job
even if it is not an efficient algorithm. It walks the maze recursively by
visiting each cell and avoiding walls and already visited cells.
The search function accepts the coordinates of a cell to explore. If it is the ending cell, it returns True. If it is a wall or an already visited cell, it returns False. The neighboring cells are explored recursively and if nothing is found at the end, it returns False so it backtracks to explore new paths. We start at cell x=0 and y=0.
def search(x, y):
if
grid[x][y] == 2:
print
('found at %d,%d' % (x, y))
return
True
elif
grid[x][y] == 1:
print
('wall at %d,%d' % (x, y))
return
False
elif
grid[x][y] == 3:
print
('visited at %d,%d' % (x, y))
return
False
print
('visiting %d,%d' % (x, y))
grid[x][y]
= 3
if
((x < len(grid)-1 and search(x+1, y)) or (y > 0 and search(x, y-1)) or (x
> 0 and search(x-1, y)) or (y < len(grid)-1 and search(x, y+1))):
return
True
return
False
search(0,
0)
Let’s see what happens when we run the script.
$
python maze.py
visiting
0,0
wall
at 1,0
visiting
0,1
wall
at 1,1
visited
at 0,0
visiting
0,2
...
First cell visited is (0,0). Its neighbors are
explored starting by the one on the right (1,0). search(1,0) returns False
because it is a wall. There is no cell below and on the left so the one at the
top (0,1) is explored. Right of that is a wall and below is already visited so
the one at the top (0,2) is explored.
Because the neighbor on the right is explored first,
this algorithm is going to explore the dead-end at the bottom-right first.
...
visiting
1,2
visiting
2,2
wall
at 3,2
visiting
2,1
wall
at 3,1
visiting
2,0
visiting
3,0
visiting
4,0
visiting
5,0
...
The algorithm is going to backtrack because there is
nothing else to explore as we are in a dead-end and we are going to end up at
cell (1, 2) again where there is more to explore.
...
visited
at 4,0
wall
at 5,1
visited
at 3,0
wall
at 4,1
visited
at 2,0
wall
at 3,1
wall
at 1,0
visited
at 2,1
wall
at 1,1
visited
at 2,2
visited
at 1,2
wall
at 2,3
wall
at 1,1
visited
at 0,2
visiting
1,3
...
Let’s continue, we end up in a second dead-end at
cell (4, 2).
...
wall
at 2,3
visited
at 1,2
visiting
0,3
visited
at 1,3
visited
at 0,2
visiting
0,4
visiting
1,4
visiting
2,4
visiting
3,4
wall
at 4,4
visiting
3,3
visiting
4,3
visiting
5,3
visiting
5,2
wall
at 5,1
visiting
4,2
visited
at 5,2
wall
at 4,1
wall
at 3,2
visited
at 4,3
...
Backtracking happens one more time to go back to
cell (5, 3) and we are now on our way to the exit.
…
visiting
5,4
visited
at 5,3
wall
at 4,4
found
at 5,5
A* search
We are going to use a more tuff algorithm called A* search. This is based on costs to move around
the grid. Let’s assume the cost to move horizontally or vertically 1 cell is
equal to 25. Again, we cannot move diagonally here.
Before we start describing the algorithm, let’s
define two variables: A and B. A is the cost to move from the starting cell to
a given cell and B is an estimation of the cost to move from a given cell to
the ending cell.
How will we do if we have
to calculate that if we don’t know the path to the ending cell? To simplify, we
just calculate the distance if no walls were present. There are other ways to
do the estimation but this one is good enough for this in a python program.
We use two lists: an open list containing the cells
to explore and a closed list containing the processed cells. We start with the
starting cell in the open list and nothing in the closed list.
Let’s follow one round of this algorithm by
processing our first cell from the open list. It is the starting cell. We
remove it from the list and append it to the closed list. We retrieve the list
of adjacent cells and we start processing them. The starting cell has 2
adjacent cells: (1, 0) and (0, 1).
(1, 0) is a wall so we drop that one. (0, 1) is
reachable and not in the closed list so we process it. We calculate A and B for
it. A = 1 as we just need to move 1 cell up from the starting cell. B = 3: 5
cells right and 4 cells up to reach the ending cell. We call the sum SUM = A +
B = 1 + 3 = 4.
We set the parent of this adjacent cell to be the
cell we just removed from the open list.
Finally, we add this adjacent cell to the open list.
We continue with the cell in the open list having
the lowest SUM = A + B. Only one cell is in the open list so it makes it easy.
We remove it from the open list and we get its adjacent cells. Again, only one
adjacent cell is reachable: (0, 2). We end up with the following after this 2nd
round.
Let’s detail the next round. We have 2 cells in the
open list: (1, 2) and (0, 3). Both have the same SUM value so we pick the last
one added which is (0, 3). This cell has 3 reachable adjacent cells: (1, 3),
(0, 2) and (0, 4). We process (1, 3) and (0, 4). (0, 2) is in the closed list.
We have (1, 2), (1, 3) and (3, 3) in the open list.
(1, 3) is processed next because it is the last one added with the lowest SUM
value = 100.
(1, 3) has 1 adjacent cell which is not in the closed list. It is
(1, 2) which is in the open list. When an adjacent cell is in the open list, we
check if its SUM value would be less if the path taken was going through the
cell currently processed e.g. through (1, 3). Here it is not the case so we
don’t update A and B of (1, 2) and its parent. This trick makes the algorithm
more efficient when this condition exists.
We have 2 cells in the open list: (3, 3) and (2, 0).
The next cell removed from the open list is (3, 3) because its F is equal to
120. This proves that this algorithm is better than the first one we saw. We
don’t end up exploring the dead end at (5, 0) and we continue walking from (3,
3) instead which is better.
The next cell processed from the open list is (5, 5)
and it is the ending cell so we have found our path. It is easy to display the
path. We just have to follow the parent pointers up to the starting cell. Our
path is highlighted in green on the following diagram:
A* implementation
The basic object here is a cell so we write a class
for it. We store the coordinates x and y, the values of A and B plus the sum
SUM.
classCell(object):
def
__init__(self, x, y, reachable):
self.reachable
= reachable
self.x
= x
self.y
= y
self.parent
= None
self.A
= 0
self.B
= 0
self.SUM
= 0
Next is our main class named main. Attributes are
the open list heapified (keep cell with lowest SUM at the top), the closed list
which is a set for fast lookup, the cells list (grid definition) and the size
of the grid.
classmain(object):
|
|||||||||
def__init__(self):
|
|||||||||
self.opened
= []
|
|||||||||
heapq.heapify(self.opened)
|
|||||||||
self.closed
=set()
|
|||||||||
self.cells
=[]
|
|||||||||
self.grid_height
=6
|
|||||||||
self.grid_width
=6
|
|||||||||
...
|
|||||||||
We create a simple method initializing the list of cells
to match our example with the walls at the same locations.
Def
grid(self):
|
||||||||||||
wall
=((0, 5), (1, 0), (1, 1), (1, 5), (2, 3),
|
||||||||||||
(3,
1), (3, 2), (3, 5), (4, 1), (4, 4), (5, 1))
|
||||||||||||
forx
inrange(self.grid_width):
|
||||||||||||
fory
inrange(self.grid_height):
|
||||||||||||
if(x,
y) inwall:
|
||||||||||||
reachable
=False
|
||||||||||||
else:
|
||||||||||||
reachable
=True
|
||||||||||||
self.cells.append(Cell(x,
y, reachable))
|
||||||||||||
self.start
=self.get_cell(0, 0)
|
||||||||||||
self.end
=self.get_cell(5, 5)
|
||||||||||||
Our heuristic compute method:
defheuristic(self,
cell):
return
10 * (abs(cell.x - self.end.x) + abs(cell.y - self.end.y))
We need a method to return a particular cell based
on x and y coordinates.
defget_cell(self,
x, y):
return
self.cells[x * self.grid_height + y]
Next is a method to retrieve the list of adjacent
cells to a specific cell.
def adjacent_cell(self,
cell):
cells
= []
if
cell.x < self.grid_width-1:
cells.append(self.get_cell(cell.x+1,
cell.y))
if
cell.y > 0:
cells.append(self.get_cell(cell.x,
cell.y-1))
if
cell.x > 0:
cells.append(self.get_cell(cell.x-1,
cell.y))
if
cell.y < self.grid_height-1:
cells.append(self.get_cell(cell.x,
cell.y+1))
return
cells
Simple method to print the path found. It follows
the parent pointers to go from the ending cell to the starting cell.
def path(self):
|
|||||
cell=self.end
|
|||||
while cell.parent
is not self.start:
|
|||||
Cell
=cell.parent
|
|||||
print('path: cell:%d,%d'%(cell.x, cell.y))
|
|||||
We need a method to calculate G and H and set the
parent cell.
def update_cell(self,
adj, cell):
adj.A
= cell.g + 10
adj.B
= self.get_heuristic(adj)
adj.parent
= cell
adj.SUM
= adj.B + adj.A
The main method implements the algorithm itself.
def process(self):
|
|||||||||||||||||||||||||
heapq.heappush(self.opened,
(self.start.SUM, self.start))
|
|||||||||||||||||||||||||
while len(self.opened):
|
|||||||||||||||||||||||||
SUM,
cell =heapq.heappop(self.opened)
|
|||||||||||||||||||||||||
self.closed.add(cell)
|
|||||||||||||||||||||||||
if cell
isself.end:
|
|||||||||||||||||||||||||
self.display_path()
|
|||||||||||||||||||||||||
break
|
|||||||||||||||||||||||||
adj_cells
=self.get_adjacent_cells(cell)
|
|||||||||||||||||||||||||
for adj_cell
inadj_cells:
|
|||||||||||||||||||||||||
if adj_cell.reachable
andadj_cell notinself.closed:
|
|||||||||||||||||||||||||
if(adj_cell.f,
adj_cell) inself.opened:
|
|||||||||||||||||||||||||
if adj_cell.g
> cell.g +10:
|
|||||||||||||||||||||||||
self.update_cell(adj_cell,
cell)
|
|||||||||||||||||||||||||
else:
|
|||||||||||||||||||||||||
self.update_cell(adj_cell,
cell)
|
|||||||||||||||||||||||||
heapq.heappush(self.opened,
(adj_cell.f, adj_cell))
|
|||||||||||||||||||||||||
If you guys have any problem to understand python
and want help see under below :-
That’s it for now in this article. I hope you
enjoyed this article.
Please write a comment if you have any feedback.
0 Comments