--For study, I will write a search using the A \ * (A-star) algorithm in Python. --Use a simple grid maze. For the maze code etc., I wrote "Write depth-first search in Python. ”will be used.
This algorithm uses the sum of g as the distance to the current point and the estimated value h to the goal as a parameter during search, and calculates the shortest distance of the route with a relatively low search cost. It is often used in games.
There are cases where the shortest distance is not calculated even though the search cost is low. Depth-first search / DFS and breadth-first search / BFS, which can calculate the shortest distance but tend to have a high calculation cost. ) Tends to give better results.
It was originally based on a paper published in 1968. The algorithm group that finds the shortest distance is described as "acceptable --Admissible" in the paper, so the first A is the set of algorithms, and the one that optimizes the number of evaluations for the shortest path calculation is A \ *. The notation is the origin of the name of the algorithm.
Paper link: A formal Basis for the Heuristic Determination of Minimum Cost Paths
The total cost of moving a certain position (node / node) to n is $ f (n) $, the cost from the start position to the node at n position is $ g (n) $, and a value called heuristic. Assuming that the function that calculates (estimated distance to the goal) is $ h (n) $, $ f (n) $ is calculated by the following sum.
f(n) = g(n) + h(n)
It's not exact, but in this article we'll simply calculate $ g (n) $ as the number of nodes moved from the start (simply 1 for each move) to simplify the calculation. Corresponding in the form of addition).
In addition, the calculation of $ h (n) $ is solved this time. Since the maze is a grid type that can be moved up, down, left, and right, the Manhattan distance is used, where one movement up, down, left, and right is the distance 1.
I will write the code in Python for understanding.
For the process of creating a maze grid, use the one from "Write depth-first search in Python". The details of the explanation are written in the link, so I will omit it, but it will be roughly summarized as follows.
-Represented by a grid of defined rows and columns. --The entrance (Start) of the maze is represented by S, the exit (Goal) is represented by G, the part that cannot be passed through the wall (Wall) is represented by W, the part that can be passed is represented by an empty cell, and the calculated route is represented by an asterisk (\ *). --Since the wall cells are randomly generated, it is possible that the generation result will not reach the exit.
from __future__ import annotations
from typing import Optional
from typing import List
import random
#Constant value for the entrance.
CELL_TYPE_START: str = 'S'
#A constant value for the passage.
CELL_TYPE_PASSAGE: str = ' '
#The constant value of the wall.
CELL_TYPE_WALL: str = 'W'
#Exit constant value.
CELL_TYPE_GOAL: str = 'G'
#A constant value for the calculated route path.
CELL_TYPE_PATH: str = '*'
class Location:
def __init__(self, row: int, column: int) -> None:
"""
A class that handles a single position information of the maze grid.
Parameters
----------
row : int
The line number of the position. Start from 0, 1 from top to bottom
Will be added.
column : int
The column number of the position. Start from 0, 1 from left to right
Will be added.
"""
self.row: int = row
self.column: int = column
class Maze:
#The number of vertical maze grids to generate.
_ROW_NUM: int = 7
#The number of cases next to the maze grid to generate.
_COLUMN_NUM: int = 15
#The ratio of walls to generate. 1.The closer it is to 0, the more walls there are.
_WALL_SPARSENESS: float = 0.3
def __init__(self) -> None:
"""
A class that handles the generation and control of a random maze grid.
Notes
-----
Since each cell type is set randomly, it is not always from the start
Note that you can't do anything that can reach your goal.
"""
self._set_start_and_goal_location()
self._grid: List[List[str]] = []
self._fill_grid_by_passage_cell()
self._set_wall_type_to_cells_randomly()
self._set_start_and_goal_type_to_cell()
def _set_start_and_goal_location(self) -> None:
"""
Set the coordinate attributes of the start point (entrance) and goal (exit).
"""
self.start_loc: Location = Location(row=0, column=0)
self.goal_loc: Location = Location(
row=self._ROW_NUM - 1,
column=self._COLUMN_NUM - 1)
def _fill_grid_by_passage_cell(self) -> None:
"""
Add cells to all cells and set the cell type of the passage.
"""
for row in range(self._ROW_NUM):
row_cells: List[str] = []
for column in range(self._COLUMN_NUM):
row_cells.append(CELL_TYPE_PASSAGE)
self._grid.append(row_cells)
def _set_wall_type_to_cells_randomly(self) -> None:
"""
Randomly set the wall cell type for each cell in the grid.
"""
for row in range(self._ROW_NUM):
for column in range(self._COLUMN_NUM):
probability = random.uniform(0.0, 1.0)
if probability >= self._WALL_SPARSENESS:
continue
self._grid[row][column] = CELL_TYPE_WALL
def _set_start_and_goal_type_to_cell(self) -> None:
"""
At the start (entrance) and goal (exit) positions, respectively
Set the cell type.
"""
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def is_goal_loc(self, location: Location) -> bool:
"""
Gets the boolean value of whether the specified position is the goal position.
Parameters
----------
location : Location
Position for judgment.
Returns
-------
result : bool
True is set if it is the goal position.
"""
if (location.row == self.goal_loc.row
and location.column == self.goal_loc.column):
return True
return False
def get_movable_locations(self, location: Location) -> List[Location]:
"""
Get a list of movable positions from the specified position.
Parameters
----------
location : Location
An instance of the reference position.
Returns
-------
movable_locations : list of Location
A list containing instances of movable locations.
"""
movable_locations: List[Location] = []
#Judgment processing of whether or not it can be moved up.
if location.row + 1 < self._ROW_NUM:
is_wall: bool = self._grid[location.row + 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row + 1, column=location.column))
#Judgment processing of whether it can be moved down.
if location.row - 1 >= 0:
is_wall = self._grid[location.row - 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row - 1, column=location.column))
#Judgment processing of whether it can be moved to the right.
if location.column + 1 < self._COLUMN_NUM:
is_wall = self._grid[location.row][location.column + 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column + 1))
#Judgment processing of whether it can be moved to the left.
if location.column - 1 >= 0:
is_wall = self._grid[location.row][location.column - 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column - 1))
return movable_locations
def set_path_type_to_cells(self, path: List[Location]) -> None:
"""
For cells contained within the specified path to the entrance and exit
Set the cell type of the path.
Parameters
----------
path : list of Location
The position information of each cell from the entrance to the exit obtained by the search
Stored list.
"""
for location in path:
self._grid[location.row][location.column] = CELL_TYPE_PATH
#The entrance and exit parts included in the path are the original
#Reflect the cell type.
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def __str__(self) -> str:
"""
Gets the type string for each cell in the grid.
Returns
-------
grid_str : str
A string of the type of each cell in the grid.
"""
grid_str: str = ''
for row_cells in self._grid:
grid_str += '-' * self._COLUMN_NUM * 2
grid_str += '\n'
for cell_type in row_cells:
grid_str += cell_type
grid_str += '|'
grid_str += '\n'
return grid_str
class Node:
def __init__(self, location: Location, parent: Optional[Node]):
"""
Data for a single node to hold information such as the position and transition of the maze
Class to handle.
Parameters
----------
location : Location
An instance that handles the location information of the target.
parent : Node or None
An instance of a node that handles location information before moving. At the start of the search
Etc. will be None.
"""
self.location: Location = location
self.parent: Optional[Node] = parent
def get_path_from_goal_node(goal_node: Node) -> List[Location]:
"""
From the exit node, the path from the entrance obtained by the search to the exit
get.
Parameters
----------
goal_node : Node
An instance of the target exit (goal) node.
Returns
-------
path : list of Location
A list containing instances of each location from entry to exit.
"""
path: List[Location] = [goal_node.location]
node: Node = goal_node
while node.parent is not None:
node = node.parent
path.append(node.location)
path.reverse()
return path
If you try to output the maze generated as a trial, it will be displayed in a grid as shown below.
if __name__ == '__main__':
maze = Maze()
print(maze)
------------------------------
S| |W| |W| | | |W| |W| |W| |W|
------------------------------
W| | | | | |W| | | |W|W| |W|W|
------------------------------
W| | | | |W| | | |W|W| | | | |
------------------------------
| |W| |W|W| | | | | | | |W|W|
------------------------------
W|W|W| | | |W| | | | | | | |W|
------------------------------
W|W| | | | | | | |W| |W| | | |
------------------------------
W|W| | | | |W| | | | | | | |G|
The A \ * algorithm uses a priority queue as the data structure. This is a special queue in which values are added to the queue with priority, and the value with the highest priority is also included when retrieving the value.
You need to add the __lt__ method to the Node class because the priority value is calculated by the less than comparison operator (<) for the instance of the node you want to queue.
In the __lt__ method, $ g (n) + h (n) $ is calculated in the cost formula and compared to another node.
Also, adjust the value of $ g (n) $ and the value of $ h (n) $ so that they are included in the class attributes because they are required for calculation.
class Node:
def __init__(
self, location: Location, parent: Optional[Node],
cost: float, heuristic:float) -> None:
"""
Data for a single node to hold information such as the position and transition of the maze
Class to handle.
Parameters
----------
location : Location
An instance that handles the location information of the target.
parent : Node or None
An instance of a node that handles location information before moving. At the start of the search
Etc. will be None.
cost : float
Cost value from the start position to the position of the corresponding node (g(n)so
Value obtained).
heuristic : float
Estimated distance from this node to the exit (h(n)Value obtained by).
"""
self.location: Location = location
self.parent: Optional[Node] = parent
self.cost = cost
self.heuristic = heuristic
def __lt__(self, other_node: Node) -> bool:
"""
Comparison operator( < )Method for processing by.
Used to control the priority queue.
Parameters
----------
other_node : Node
Instances of other nodes to compare.
Returns
-------
result_bool : bool
Comparison result. Calculation processing is the cost from the entrance (g(n))When
Heuristic value (h(n)) By comparing the total value
Will be done.
"""
left_value: float = self.cost + self.heuristic
right_value: float = other_node.cost + other_node.heuristic
result_bool: bool = left_value < right_value
return result_bool
I've never used the __lt__ method on my own, so I'll try creating multiple instances and compare them to see the results. The comparison is based on the sum of cost and heuristic, so the first comparison is False and the second is True.
if __name__ == '__main__':
node_1 = Node(
location=Location(row=0, column=0),
parent=None,
cost=2, heuristic=2)
node_2 = Node(
location=Location(row=0, column=0),
parent=None,
cost=1, heuristic=2)
node_3 = Node(
location=Location(row=0, column=0),
parent=None,
cost=3, heuristic=2)
print(node_1 < node_2)
print(node_1 < node_3)
False
True
Next, we will prepare the priority queue. Priority queue processing can be handled by using the heapq package of the Python standard module.
import heapq
...
class PriorityQueue:
def __init__(self) -> None:
"""
A class for controlling priority queues.
"""
self._container: List[Node] = []
@property
def empty(self) -> bool:
"""
Attribute value for whether the queue is empty.
Returns
-------
result : bool
Set to True if empty.
"""
return not self._container
def push(self, node: Node) -> None:
"""
Add an instance of a node to the queue.
Parameters
----------
node : Node
Instance of the node to be added.
"""
heapq.heappush(self._container, node)
def pop(self) -> Node:
"""
Take an instance of the highest priority node from the queue.
Returns
-------
node : Node
An instance of the retrieved Node class.
"""
return heapq.heappop(self._container)
Let's actually move it a little and try it to see if it is processed in a way that takes into account the priority. It should be noted that the "low cost is preferable (= high priority)" form. It is not taken out by pop from the one with the highest total cost value.
if __name__ == '__main__':
priority_queue = PriorityQueue()
priority_queue.push(
node=Node(
location=Location(row=0, column=0),
parent=None,
cost=1,
heuristic=1))
priority_queue.push(
node=Node(
location=Location(row=0, column=0),
parent=None,
cost=3,
heuristic=3))
priority_queue.push(
node=Node(
location=Location(row=0, column=0),
parent=None,
cost=2,
heuristic=3))
node: Node = priority_queue.pop()
print(node.cost, node.heuristic)
node = priority_queue.pop()
print(node.cost, node.heuristic)
node = priority_queue.pop()
print(node.cost, node.heuristic)
You can see that the output results are retrieved in ascending order of total cost.
1 1
2 3
3 3
This time, the heuristic ($ h (n) $) is calculated using the Manhattan distance because it is a grid-type maze, so add that function to the Maze class.
def get_manhattan_distance(self, location: Location) -> int:
"""
The Manhattan distance between the target position and the exit (goal) position
get.
Parameters
----------
location : Location
An instance of the target location.
Returns
-------
distance : int
Manhattan distance between the target position and the exit position. Column direction
The sum of the absolute value of the difference and the absolute value of the difference in the row direction is set.
"""
x_distance: int = abs(location.column - self.goal_loc.column)
y_distance: int = abs(location.row - self.goal_loc.column)
distance: int = x_distance + y_distance
return distance
Now that we have all the necessary preparations, let's create a function for the A \ * algorithm. The function name is astar.
from typing import Callable, Dict
...
def astar(
init_loc: Location,
is_goal_loc_method: Callable[[Location], bool],
get_movable_locations_method: Callable[[Location], List[Location]],
hueristic_method: Callable[[Location], int],
) -> Optional[Node]:
"""
A*Performs search processing by algorithm.
Parameters
----------
init_loc : Location
Search start position (position of maze entrance).
is_goal_loc_method : callable
A method that determines whether the target position is the exit (goal).
get_movable_locations_method : callable
A method to get a list of cell positions to move from the target position.
hueristic_method : callable
Get the distance between the target position and the exit (goal) position
A method for heuristics for.
Returns
-------
goal_node : Node or None
An instance of the node at the calculated exit location. To the exit
None is set in cases where the route cannot be calculated.
"""
frontier_queue: PriorityQueue = PriorityQueue()
frontier_queue.push(
node=Node(
location=init_loc,
parent=None,
cost=0,
heuristic=hueristic_method(init_loc)))
explored_loc_cost_dict: Dict[Location, float] = {init_loc: 0.0}
while not frontier_queue.empty:
current_node: Node = frontier_queue.pop()
current_loc: Location = current_node.location
if is_goal_loc_method(current_loc):
return current_node
movable_locations = get_movable_locations_method(current_loc)
for movable_location in movable_locations:
new_cost: float = current_node.cost + 1
#A new destination has already been searched, and it is not cost effective
#If so, skip it.
if (movable_location in explored_loc_cost_dict and
explored_loc_cost_dict[movable_location] <= new_cost):
continue
explored_loc_cost_dict[movable_location] = new_cost
frontier_queue.push(
node=Node(
location=movable_location,
parent=current_node,
cost=new_cost,
heuristic=hueristic_method(movable_location)))
return None
I wrote earlier, "Write depth-first search in Python. ", the flow is similar to the dfs function in the article. Since the processing is partially different, I will mainly explain the difference.
First of all, the argument is Callable for heuristic (hueristic_method). This specifies the method to calculate the Manhattan distance that was added a while ago in this sample.
frontier_queue: PriorityQueue = PriorityQueue()
frontier_queue.push(
node=Node(
location=init_loc,
parent=None,
cost=0,
heuristic=hueristic_method(init_loc)))
Also, the queue has been replaced with that of the priority queue (frontier_queue). We are adding nodes to be searched to this queue.
explored_loc_cost_dict: Dict[Location, float] = {init_loc: 0.0}
The dictionary that holds the searched nodes is in the form of holding the position in the key and the value of the cost ($ g (n) $) in the value. Since it is a simple method that increments by 1 each time it moves, set 0.0 at first.
while not frontier_queue.empty:
current_node: Node = frontier_queue.pop()
current_loc: Location = current_node.location
The process is repeated in a while loop until the node to be searched disappears from the queue.
if is_goal_loc_method(current_loc):
return current_node
If the target node is an exit (goal), the process is completed by returning the exit node.
movable_locations = get_movable_locations_method(current_loc)
for movable_location in movable_locations:
new_cost: float = current_node.cost + 1
Each position to be moved from the node to be searched is processed by a for loop. This time, it is implemented in a simple form that increments the cost ($ g (n) $) by 1 each time it moves.
#A new destination has already been searched, and it is not cost effective
#If so, skip it.
if (movable_location in explored_loc_cost_dict and
explored_loc_cost_dict[movable_location] <= new_cost):
continue
Even if the location has already been searched, it is worth searching if it is cost effective. If it has already been searched and the cost does not change or it deteriorates, there is no merit to search, so skip it.
explored_loc_cost_dict[movable_location] = new_cost
frontier_queue.push(
node=Node(
location=movable_location,
parent=current_node,
cost=new_cost,
heuristic=hueristic_method(movable_location)))
If the conditions are worth searching, we set values such as cost in the searched dictionary and add nodes to the priority queue to be searched.
Since the items with the highest priority are processed first, you can perform a search with excellent search cost.
return None
Depending on the maze generated, there may be no route to the exit, so in that case None is returned.
I will try it.
if __name__ == '__main__':
maze: Maze = Maze()
print(maze)
goal_node: Optional[Node] = astar(
init_loc=maze.start_loc,
is_goal_loc_method=maze.is_goal_loc,
get_movable_locations_method=maze.get_movable_locations,
hueristic_method=maze.get_manhattan_distance,
)
if goal_node is None:
print('This is a maze where the exit cannot be calculated.')
else:
print('-' * 20)
path: List[Location] = get_path_from_goal_node(
goal_node=goal_node)
maze.set_path_type_to_cells(path=path)
print('Calculated path:')
print(maze)
Calculated path:
------------------------------
S|*|*|*|*| | | |W| | | |W|W|W|
------------------------------
W| | |W|*|*|W|W|W| | | | |W| |
------------------------------
W|W| |W|W|*|W| | | | |W|W|W|W|
------------------------------
W|W|W| | |*|*|W| |W| | | | | |
------------------------------
|W|W|W| | |*|W| | | | | |W| |
------------------------------
| | | | |W|*|*|*|*|*| | |W| |
------------------------------
|W| | |W|W|W| |W| |*|*|*|*|G|
S on the grid is the entrance (start), G is the exit (goal), and the asterisk part is the path calculated by the search. The path from the entrance to the exit has been calculated safely.
Compared to breadth-first search, where the search results are slightly right-angled, the characteristic of A \ * is that diagonal paths are obtained. Even the sample I actually tried this time has a slightly diagonal path.
from __future__ import annotations
from typing import Optional
from typing import List
import random
import heapq
from typing import Callable, Dict
#Constant value for the entrance.
CELL_TYPE_START: str = 'S'
#A constant value for the passage.
CELL_TYPE_PASSAGE: str = ' '
#The constant value of the wall.
CELL_TYPE_WALL: str = 'W'
#Exit constant value.
CELL_TYPE_GOAL: str = 'G'
#A constant value for the calculated route path.
CELL_TYPE_PATH: str = '*'
class Location:
def __init__(self, row: int, column: int) -> None:
"""
A class that handles a single position information of the maze grid.
Parameters
----------
row : int
The line number of the position. Start from 0, 1 from top to bottom
Will be added.
column : int
The column number of the position. Start from 0, 1 from left to right
Will be added.
"""
self.row: int = row
self.column: int = column
class Maze:
#The number of vertical maze grids to generate.
_ROW_NUM: int = 7
#The number of cases next to the maze grid to generate.
_COLUMN_NUM: int = 15
#The ratio of walls to generate. 1.The closer it is to 0, the more walls there are.
_WALL_SPARSENESS: float = 0.3
def __init__(self) -> None:
"""
A class that handles the generation and control of a random maze grid.
Notes
-----
Since each cell type is set randomly, it is not always from the start
Note that you can't do anything that can reach your goal.
"""
self._set_start_and_goal_location()
self._grid: List[List[str]] = []
self._fill_grid_by_passage_cell()
self._set_wall_type_to_cells_randomly()
self._set_start_and_goal_type_to_cell()
def _set_start_and_goal_location(self) -> None:
"""
Set the coordinate attributes of the start point (entrance) and goal (exit).
"""
self.start_loc: Location = Location(row=0, column=0)
self.goal_loc: Location = Location(
row=self._ROW_NUM - 1,
column=self._COLUMN_NUM - 1)
def _fill_grid_by_passage_cell(self) -> None:
"""
Add cells to all cells and set the cell type of the passage.
"""
for row in range(self._ROW_NUM):
row_cells: List[str] = []
for column in range(self._COLUMN_NUM):
row_cells.append(CELL_TYPE_PASSAGE)
self._grid.append(row_cells)
def _set_wall_type_to_cells_randomly(self) -> None:
"""
Randomly set the wall cell type for each cell in the grid.
"""
for row in range(self._ROW_NUM):
for column in range(self._COLUMN_NUM):
probability = random.uniform(0.0, 1.0)
if probability >= self._WALL_SPARSENESS:
continue
self._grid[row][column] = CELL_TYPE_WALL
def _set_start_and_goal_type_to_cell(self) -> None:
"""
At the start (entrance) and goal (exit) positions, respectively
Set the cell type.
"""
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def is_goal_loc(self, location: Location) -> bool:
"""
Gets the boolean value of whether the specified position is the goal position.
Parameters
----------
location : Location
Position for judgment.
Returns
-------
result : bool
True is set if it is the goal position.
"""
if (location.row == self.goal_loc.row
and location.column == self.goal_loc.column):
return True
return False
def get_movable_locations(self, location: Location) -> List[Location]:
"""
Get a list of movable positions from the specified position.
Parameters
----------
location : Location
An instance of the reference position.
Returns
-------
movable_locations : list of Location
A list containing instances of movable locations.
"""
movable_locations: List[Location] = []
#Judgment processing of whether or not it can be moved up.
if location.row + 1 < self._ROW_NUM:
is_wall: bool = self._grid[location.row + 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row + 1, column=location.column))
#Judgment processing of whether it can be moved down.
if location.row - 1 >= 0:
is_wall = self._grid[location.row - 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row - 1, column=location.column))
#Judgment processing of whether it can be moved to the right.
if location.column + 1 < self._COLUMN_NUM:
is_wall = self._grid[location.row][location.column + 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column + 1))
#Judgment processing of whether it can be moved to the left.
if location.column - 1 >= 0:
is_wall = self._grid[location.row][location.column - 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column - 1))
return movable_locations
def set_path_type_to_cells(self, path: List[Location]) -> None:
"""
For cells contained within the specified path to the entrance and exit
Set the cell type of the path.
Parameters
----------
path : list of Location
The position information of each cell from the entrance to the exit obtained by the search
Stored list.
"""
for location in path:
self._grid[location.row][location.column] = CELL_TYPE_PATH
#The entrance and exit parts included in the path are the original
#Reflect the cell type.
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def get_manhattan_distance(self, location: Location) -> int:
"""
The Manhattan distance between the target position and the exit (goal) position
get.
Parameters
----------
location : Location
An instance of the target location.
Returns
-------
distance : int
Manhattan distance between the target position and the exit position. Column direction
The sum of the absolute value of the difference and the absolute value of the difference in the row direction is set.
"""
x_distance: int = abs(location.column - self.goal_loc.column)
y_distance: int = abs(location.row - self.goal_loc.column)
distance: int = x_distance + y_distance
return distance
def __str__(self) -> str:
"""
Gets the type string for each cell in the grid.
Returns
-------
grid_str : str
A string of the type of each cell in the grid.
"""
grid_str: str = ''
for row_cells in self._grid:
grid_str += '-' * self._COLUMN_NUM * 2
grid_str += '\n'
for cell_type in row_cells:
grid_str += cell_type
grid_str += '|'
grid_str += '\n'
return grid_str
class Node:
def __init__(
self, location: Location, parent: Optional[Node],
cost: float, heuristic:float) -> None:
"""
Data for a single node to hold information such as the position and transition of the maze
Class to handle.
Parameters
----------
location : Location
An instance that handles the location information of the target.
parent : Node or None
An instance of a node that handles location information before moving. At the start of the search
Etc. will be None.
cost : float
Cost value from the start position to the position of the corresponding node (g(n)so
Value obtained).
heuristic : float
Estimated distance from this node to the exit (h(n)Value obtained by).
"""
self.location: Location = location
self.parent: Optional[Node] = parent
self.cost = cost
self.heuristic = heuristic
def __lt__(self, other_node: Node) -> bool:
"""
Comparison operator( < )Method for processing by.
Used to control the priority queue.
Parameters
----------
other_node : Node
Instances of other nodes to compare.
Returns
-------
result_bool : bool
Comparison result. Calculation processing is the cost from the entrance (g(n))When
Heuristic value (h(n)) By comparing the total value
Will be done.
"""
left_value: float = self.cost + self.heuristic
right_value: float = other_node.cost + other_node.heuristic
result_bool: bool = left_value < right_value
return result_bool
def get_path_from_goal_node(goal_node: Node) -> List[Location]:
"""
From the exit node, the path from the entrance obtained by the search to the exit
get.
Parameters
----------
goal_node : Node
An instance of the target exit (goal) node.
Returns
-------
path : list of Location
A list containing instances of each location from entry to exit.
"""
path: List[Location] = [goal_node.location]
node: Node = goal_node
while node.parent is not None:
node = node.parent
path.append(node.location)
path.reverse()
return path
class PriorityQueue:
def __init__(self) -> None:
"""
A class for controlling priority queues.
"""
self._container: List[Node] = []
@property
def empty(self) -> bool:
"""
Attribute value for whether the queue is empty.
Returns
-------
result : bool
Set to True if empty.
"""
return not self._container
def push(self, node: Node) -> None:
"""
Add an instance of a node to the queue.
Parameters
----------
node : Node
Instance of the node to be added.
"""
heapq.heappush(self._container, node)
def pop(self) -> Node:
"""
Take an instance of the highest priority node from the queue.
Returns
-------
node : Node
An instance of the retrieved Node class.
"""
return heapq.heappop(self._container)
def astar(
init_loc: Location,
is_goal_loc_method: Callable[[Location], bool],
get_movable_locations_method: Callable[[Location], List[Location]],
hueristic_method: Callable[[Location], int],
) -> Optional[Node]:
"""
A*Performs search processing by algorithm.
Parameters
----------
init_loc : Location
Search start position (position of maze entrance).
is_goal_loc_method : callable
A method that determines whether the target position is the exit (goal).
get_movable_locations_method : callable
A method to get a list of cell positions to move from the target position.
hueristic_method : callable
Get the distance between the target position and the exit (goal) position
A method for heuristics for.
Returns
-------
goal_node : Node or None
An instance of the node at the calculated exit location. To the exit
None is set in cases where the route cannot be calculated.
"""
frontier_queue: PriorityQueue = PriorityQueue()
frontier_queue.push(
node=Node(
location=init_loc,
parent=None,
cost=0,
heuristic=hueristic_method(init_loc)))
explored_loc_cost_dict: Dict[Location, float] = {init_loc: 0.0}
while not frontier_queue.empty:
current_node: Node = frontier_queue.pop()
current_loc: Location = current_node.location
if is_goal_loc_method(current_loc):
return current_node
movable_locations = get_movable_locations_method(current_loc)
for movable_location in movable_locations:
new_cost: float = current_node.cost + 1
#A new destination has already been searched, and it is not cost effective
#If so, skip it.
if (movable_location in explored_loc_cost_dict and
explored_loc_cost_dict[movable_location] <= new_cost):
continue
explored_loc_cost_dict[movable_location] = new_cost
frontier_queue.push(
node=Node(
location=movable_location,
parent=current_node,
cost=new_cost,
heuristic=hueristic_method(movable_location)))
return None
if __name__ == '__main__':
maze: Maze = Maze()
print(maze)
goal_node: Optional[Node] = astar(
init_loc=maze.start_loc,
is_goal_loc_method=maze.is_goal_loc,
get_movable_locations_method=maze.get_movable_locations,
hueristic_method=maze.get_manhattan_distance,
)
if goal_node is None:
print('This is a maze where the exit cannot be calculated.')
else:
print('-' * 20)
path: List[Location] = get_path_from_goal_node(
goal_node=goal_node)
maze.set_path_type_to_cells(path=path)
print('Calculated path:')
print(maze)
――Because I was originally a graduate of a school in the design field, please forgive Masakari who has a strong knowledge of computer science.
Recommended Posts