Original article, reprint please contact the author
Time only urge people old, do not believe affectionate, long hate from the pavilion, tears spring shirt wine is easy to wake up.
preface
Recently I came into contact with a very interesting small topic, and share it with you. The A* algorithm is used to calculate the possible path of the maze. For the knowledge of this algorithm, you can see the A* algorithm Wikipedia and A Star algorithm in detail to understand. The code address is here at Maze for those who like Python to get their hands on.
The feed that
The maze in this case, which is presented as a grid type, is presented in the code as a two-dimensional array. Secondly, in the maze of movement, only up, down, left, right four action options. As follows:
Where 1 represents the entrance, 2 represents the obstacle impassable, and 3 represents the exit
[[3, 2, 2, 2, 2, 2, 2, 2, 1], [0, 0, 2, 2, 2, 2, 2, 0, 0], [2, 0, 0, 2, 2, 2, 0, 0, 2], [2, 2, 0, 0, 2, 0, 0, 2, 2]. [2, 2, 2, 0, 0, 0, 2, 2, 2]Copy the codeIn fact, in A* algorithm, the unit search region is described as nodes. In this case, it’s easier to think of the search area as a square.
A* algorithm logic analysis
The logic of A* algorithm is actually not very difficult, which can be simplified into two words: evaluation, loop. Start with the starting point, first find the nodes around the starting point that can be walked, and then within this node, evaluate the optimal (shortest) distance to the end point. Then the optimal node will serve as the next point of action, and so on, until the end point is found. As you can see, the most important step in this logic is the evaluation step. The evaluation function of A* algorithm is: F (n) = G (n) + H (n)
G (n)– represents the cost of moving to this point, which in this case is 1, because you can only move horizontally or numerically. If the bevel could be moved, the value would be square root of 2 h(n)– the cost of moving from this point to the end point, which is a guess. In this case, considering the maze as a coordinate system, h(n) is the one that minimizes the difference between the two ends, x and y. For example, h(n) of point [4,2] and end point [1,1] is: 1
Code implementation
The points described in the code are actual values, not starting with 0.
Locate the starting and ending points, use the list to store four movement commands, the following codeenv_dataRepresents maze arrays:
# up, down, left and right four movement commands, only four movement commands
orders = ['u'.'d'.'l'.'r']
# Locate the starting and ending points
start_loc = []
des_loc = []
for index, value in enumerate(env_data, 1):
iflen(start_loc) == 0 or len(des_loc) ! = 0:if 1 in value:
start_loc = (index, value.index(1) + 1)
if 3 in value:
des_loc = (index, value.index(3) + 1)
else:
break
Copy the codeDetermine all executable movement commands of the node:
def valid_actions(loc):
""":param loc: :return: all available commands at the current location"""
loc_actions = []
for order in orders:
if is_move_valid(loc, order):
loc_actions.append(order)
return loc_actions
def is_move_valid(loc, act):
"""Determine whether this move command is available at the current point."""
x = loc[0] - 1
y = loc[1] - 1
if act not in orders:
return false
else:
if act == orders[0]:
returnx ! = 0 and env_data[x - 1][y] ! = 2elif act == orders[1]:
returnx ! = len(env_data) - 1 and env_data[x + 1][y] ! = 2elif act == orders[2]:
returny ! = 0 and env_data[x][y - 1] ! = 2else:
returny ! = len(env_data[0]) - 1 and env_data[x][y + 1] ! = 2Copy the codeGet around the node and move the unit1All reachable points of, excluding this node:
def get_all_valid_loc(loc):
"""Computes the current point, all nearby points available :param loc: :return:"""
all_valid_data = []
cur_acts = valid_actions(loc)
for act in cur_acts:
all_valid_data.append(move_robot(loc, act))
if loc in all_valid_data:
all_valid_data.remove(loc)
return all_valid_data
def move_robot(loc, act):
"""
移动机器人，返回新位置
:param loc:
:param act:
:return:
"""
if is_move_valid(loc, act):
if act == orders[0]:
return loc[0] - 1, loc[1]
elif act == orders[1]:
return loc[0] + 1, loc[1]
elif act == orders[2]:
return loc[0], loc[1] - 1
else:
return loc[0], loc[1] + 1
else:
return loc
Copy the codeh(n)Function expression:
def compute_cost(loc):
"""Calculate loc cost to destination :param loc: :return:"""
return min(abs(loc[0] - des_loc[0]), abs(loc[1] - des_loc[1]))
Copy the codeStart counting
Use road_list to hold the path traveled, and use another collection to hold the failed node — that is, a dead end with no available nodes nearby.
# List of paths that have been taken
road_list = [start_loc]
# Verify is the path to failure
failed_list = []
# Loop until you reach the end
whileroad_list[len(road_list) - 1] ! = des_loc:if len(road_list) == 0:
print("The maze has no solution.")
break
# the current point
cur_loc = road_list[len(road_list) - 1]
All available points around the current point
valid_loc_data = get_all_valid_loc(cur_loc)
# If available points include nodes that have already passed, remove them
for cl in road_list:
if cl in valid_loc_data:
valid_loc_data.remove(cl)
If the set of available points includes a failed node, remove it
for fl in failed_list:
if fl in valid_loc_data:
valid_loc_data.remove(fl)
If there are no available points, consider it a failure and abandon the node. Remove from the set of paths traveled
if len(valid_loc_data) == 0:
failed_list.append(road_list.pop())
continue
# Sort the set of available points with an evaluation function, take the end value, and add it to the set of paths traveled
valid_loc_data.sort(key=compute_cost, reverse=True)
road_list.append(valid_loc_data.pop())
Copy the codeLook at the results
conclusion
Life is short. I use Python. The code address is here at Maze for those who like Python to get their hands on. In the process of researching mazes, it is also interesting to discover the algorithms that generate mazes, so we can study them after this busy time. Above: hey ~ ~ ~ ~ ~
