Во-первых, я хотел бы сказать, что если у вас есть информация о проблеме, такая, что «есть несколько препятствий, которые необходимо устранить» (имеется в виду, что препятствия редки), алгоритм, который работает только с учетом препятствий, может оказаться Быстрее. Но я дам общее решение ( Я превратил проблему в задачу поиска пути ) и несколько советов.
1 - В играх используется хитрость (по крайней мере, я знаю это по игры). Помните, что в алгоритме A * есть затраты. Например, в играх, если вы хотите, чтобы водный путь был более дорогостоящим, чем наземный, вы увеличиваете значение «g» в акваториях по сравнению с земными участками. Хитрость заключается в умном использовании этой функции стоимости. В некоторых играх, когда вы пытаетесь переместить персонажа из точки А в точку Б, и между точками нет пустого пути, персонаж не просто стоит там, а идет к точке Б столько, сколько может. Это делается с помощью вместо того, чтобы полностью отбрасывать непроходимые области, вы назначаете им очень высокую стоимость . В результате персонаж начинает идти к тончайшему препятствию между двумя точками, вместо того чтобы стоять и ничего не делать. Если мы примем эту идею к вашей проблеме, проблема в основном превратится в «найти путь с наименьшим количеством 1 с». (Строки 46, 106 и 139 в моем коде)
2 - Я обычно ничего не делаю в python, поэтому я оборачиваю операции с кучей в классе PriorityQueue (я взял этот код класса откуда-то, а не конечно где). Но я думаю, что управлять этими вещами проще, также основной корпус A * выглядит ясным.
3 - Вам не нужно писать отдельный оператор if для разных направлений (вправо, вверх, влево, вниз) , Да, есть аргумент, что это быстрее, но если вам действительно нужна такая скорость, вы можете не использовать python. (строки 92-93 и 122-124, чтобы увидеть использование)
4- Я использовал манхэттенское расстояние в качестве heuristi c, предполагая, что только 4 кардинальных направления разрешены для перемещения, если разрешены диагональные перемещения, это должно быть изменено на евклидово расстояние и необходимо учитывать 4 других направления.
import time
import random
# use whichever data structure you like
import heapq
class Node():
# maybe calculate h value inside function instead of taking as arg
def __init__(self, parent_node, row, col, g, h):
self.parent_node = parent_node
self.row = row
self.col = col
self.g = g
self.h = h
def __lt__(self, other):
return self.g + self.h < other.g + other.h
class PriorityQueue:
def __init__(self):
self.elements = []
def empty(self):
return len(self.elements) == 0
def put(self, item, priority):
heapq.heappush(self.elements, (priority, item))
def get(self):
return heapq.heappop(self.elements)[1]
class Maze:
def __init__(self, maze_map):
self.maze_map = maze_map
self.maze_height = len(self.maze_map)
self.maze_width = len(self.maze_map[0])
# this number must be large enough compared to your maze size
self.OBSTACLE_COST = 1000
def print_maze(self):
for row in self.maze_map:
for col in row:
print(col, end='')
print("")
def calculate_h(self, row, col):
# lets use manhattan distance, since we do not go diagonally
#convert to euclidian if diagonal movement is allowed
return abs(row - end_row) + abs(col - end_col)
def solve(self, start_row, start_col, goal_row, goal_col):
self.start_row = start_row
self.start_col = start_col
self.end_row = end_row
self.end_col = end_col
# initialize result variables
found_path = []
found_path_cost = 0
# create root A* node
h_initial = self.calculate_h(start_row, start_col)
s0 = Node(None, start_row, start_col, 0, h_initial)
# create our priority queue and put root node in it
Q = PriorityQueue()
Q.put(s0, s0.h+0)
# keep visited/closed set, (so we are performing graph search)
closed_set = {}
# these will be useful
#these numbers correspond to RIGHT,UP,LEFT,DOWN respectively
#for right change in y=0 and change in x = 1
#...
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
while (not Q.empty()):
# pop a node from the priority queue
s = Q.get()
if (s.row == self.end_row and s.col == self.end_col):
# solved, obtain the path by following parents of nodes
current_node = s
while current_node.parent_node != None:
found_path.append(current_node)
if (self.maze_map[current_node.row][current_node.col] == 0):
found_path_cost += 1
else:
found_path_cost += self.OBSTACLE_COST
current_node = current_node.parent_node
found_path.reverse()
break
# expand node s
# here I converted current position into a tuple of
#row and col, then converted this tuple to a string
#so it can be used as a dictionary key
closed_set[str((s.row, s.col))] = 1
# continue searching, create child nodes of current node
s_row = s.row
s_col = s.col
for d in range(4): #letter "d" represent direction
#letter "n" represent neighbour
n_row = s.row + dy[d]
n_col = s.col + dx[d]
# check if neighbour node is in maze bounds
if (n_row >= 0 and n_row < self.maze_height and
n_col >= 0 and n_col < self.maze_width):
# if this neighbour is already visited (already in
#closed list) discard it
if (str((n_row, n_col)) in closed_set):
continue
# calculate new g and h value for the child node
new_g = s.g+1 if (self.maze_map[n_row][n_col] == 0) else s.g+self.OBSTACLE_COST
new_heuristic = self.calculate_h(n_row, n_col)
# create new child node and add it to the priority queue
new_s = Node(s, n_row, n_col, new_g, new_heuristic)
Q.put(new_s, new_s.g + new_s.h)
print("Number of obstacles along the path:", int(found_path_cost/self.OBSTACLE_COST))
print("Found path manhattan dist:", len(found_path))
return found_path, found_path_cost
if __name__ == "__main__":
#
# MAZE 1
#
print("\n MAZE 1\n")
m = [[0, 1, 1, 0],
[0, 0, 1, 0],
[1, 1, 1, 0],
[1, 0, 1, 0]]
maze = Maze(m)
maze.print_maze()
start_row = 0
start_col = 0
end_row = len(m)-1
end_col = len(m[0])-1
maze.solve(start_row, start_col, end_row, end_col)
#
# MAZE 2
#
print("\n MAZE 2\n")
m = [[0, 1, 1, 0],
[0, 0, 1, 0],
[1, 1, 1, 1],
[1, 0, 1, 0]]
maze = Maze(m)
maze.print_maze()
start_row = 0
start_col = 0
end_row = len(m)-1
end_col = len(m[0])-1
maze.solve(start_row, start_col, end_row, end_col)
Выходы:
MAZE 1
0110
0010
1110
1010
Number of obstacles along the path: 1
Found path manhattan dist: 6
MAZE 2
0110
0010
1111
1010
Number of obstacles along the path: 2
Found path manhattan dist: 6