Мои тесты моих реализаций Dijkstra и A-Star показали, что моя реализация A-star примерно в 2 раза SLOWER . Обычно эквивалентные реализации Dijkstra и A-star должны видеть, как A-star выбивает Dijkstra. Но это не тот случай, и поэтому я поставил под сомнение мою реализацию A-star. Поэтому я хочу, чтобы кто-то сказал мне, что я делаю неправильно в моей реализации A-star.
Вот мой код:
from copy import deepcopy
from math import inf, sqrt
import maze_builderV2 as mb
if __name__ == '__main__':
order = 10
space = ['X']+['_' for x in range(order)]+['X']
maze = [deepcopy(space) for x in range(order)]
maze.append(['X' for x in range(order+2)])
maze.insert(0, ['X' for x in range(order+2)])
finalpos = (order, order)
pos = (1, 1)
maze[pos[0]][pos[1]] = 'S' # Initializing a start position
maze[finalpos[0]][finalpos[1]] = 'O' # Initializing a end position
mb.mazebuilder(maze=maze)
def spit():
for x in maze:
print(x)
spit()
print()
mazemap = {}
def scan(): # Converts raw map/maze into a suitable datastructure.
for x in range(1, order+1):
for y in range(1, order+1):
mazemap[(x, y)] = {}
t = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
for z in t:
if maze[z[0]][z[1]] == 'X':
pass
else:
mazemap[(x, y)][z] = [sqrt((pos[0]-z[0])**2+(pos[1]-z[1])**2),
sqrt((finalpos[0]-z[0])**2+(finalpos[1]-z[1])**2)] # Euclidean distance to destination (Heuristic)
scan()
unvisited = deepcopy(mazemap)
distances = {}
paths = {}
# Initialization of distances:
for node in unvisited:
if node == pos:
distances[node] = [0, sqrt((finalpos[0]-node[0])**2+(finalpos[1]-node[1])**2)]
else:
distances[node] = [inf, inf]
while unvisited != {}:
curnode = None
for node in unvisited:
if curnode == None:
curnode = node
elif (distances[node][0]+distances[node][1]) < (distances[curnode][0]+distances[curnode][1]):
curnode = node
else:
pass
for childnode, lengths in mazemap[curnode].items():
# Length to nearby childnode - G length, Euclidean (Heuristic) length from curnode to finalpos - H length
# G length + H length < Euclidean length to reach that childnode directly + Euclidean length to finalpos from that childnode = Better path found, update known distance and paths
if lengths[0] + lengths[1] < distances[childnode][0] + distances[childnode][1]:
distances[childnode] = [lengths[0], lengths[1]]
paths[childnode] = curnode
unvisited.pop(curnode)
def shortestroute(paths, start, end):
shortestpath = []
try:
def rec(start, end):
if end == start:
shortestpath.append(end)
return shortestpath[::-1]
else:
shortestpath.append(end)
return rec(start, paths[end])
return rec(start, end)
except KeyError:
return False
finalpath = shortestroute(paths, pos, finalpos)
if finalpath:
for x in finalpath:
if x == pos or x == finalpos:
pass
else:
maze[x[0]][x[1]] = 'W'
else:
print("This maze not solvable, Blyat!")
print()
spit()
Для тех, кто считает мой код слишком запутанным и может Не потрудитесь прочитать комментарии, которые я добавил, чтобы помочь с чтением ... Вот суть моего кода:
- Создает карту лабиринта (все координаты и связанные с ними соседи вместе с их евклидовыми расстояниями от этой соседней точки до начальной позиции (стоимость G), а также до конечной позиции (стоимость H) ... в словаре)
- начальная позиция выбрана в качестве текущего узла. Все расстояния до других узлов инициализируются как бесконечность.
- Для каждого узла мы сравниваем общую стоимость пути, т.е. это стоимость G + стоимость H. Тот с наименьшей общей стоимостью выбирается как следующий текущий узел. Каждый раз, когда мы выбираем новый текущий узел, мы добавляем этот узел в словарь, который отслеживает, через какой узел он был достигнут, чтобы было легче вернуться назад и найти наш путь.
- Процесс продолжается до тех пор, пока текущий узел не будет окончательная позиция.
Если кто-то может помочь мне в этом, это было бы здорово!
РЕДАКТИРОВАТЬ: Из-за людей, просящих алгоритм построения лабиринта, вот оно:
# Maze generator - v2: Generates mazes that look like city streets (more or less...)
from copy import deepcopy
from random import randint, choice
if __name__ == "__main__":
order = 10
space = ['X']+['_' for x in range(order)]+['X']
maze = [deepcopy(space) for x in range(order)]
maze.append(['X' for x in range(order+2)])
maze.insert(0, ['X' for x in range(order+2)])
pos = (1, 1)
finalpos = (order, order)
maze[pos[0]][pos[1]] = 'S' # Initializing a start position
maze[finalpos[1]][finalpos[1]] = 'O' # Initializing a end position
def spit():
for x in maze:
print(x)
blocks = []
freespaces = [(x, y) for x in range(1, order+1) for y in range(1, order+1)]
def blockbuilder(kind):
param1 = param2 = 0
double = randint(0, 1)
if kind == 0:
param2 = randint(3, 5)
if double:
param1 = 2
else:
param1 = 1
else:
param1 = randint(3, 5)
if double:
param2 = 2
else:
param2 = 1
for a in range(blockstarter[0], blockstarter[0]+param2):
for b in range(blockstarter[1], blockstarter[1]+param1):
if (a+1, b) in blocks or (a-1, b) in blocks or (a, b+1) in blocks or (a, b-1) in blocks or (a, b) in blocks or (a+1, b+1) in blocks or (a-1, b+1) in blocks or (a+1, b-1) in blocks or (a-1, b-1) in blocks:
pass
else:
if a > order+1 or b > order+1:
pass
else:
if maze[a][b] == 'X':
blocks.append((a, b))
else:
spaces = [(a+1, b), (a-1, b), (a, b+1), (a, b-1)]
for c in spaces:
if maze[c[0]][c[1]] == 'X':
break
else:
maze[a][b] = 'X'
blocks.append((a, b))
for x in range(1, order+1):
for y in range(1, order+1):
if (x, y) in freespaces:
t = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
i = 0
while i < len(t):
if maze[t[i][0]][t[i][1]] == 'X' or (t[i][0], t[i][1]) == pos or (t[i][0], t[i][1]) == finalpos:
del t[i]
else:
i += 1
if len(t) > 2:
blockstarter = t[randint(0, len(t)-1)]
kind = randint(0, 1) # 0 - vertical, 1 - horizontal
blockbuilder(kind)
else:
pass
# rch = choice(['d', 'u', 'r', 'l'])
b = 0
while b < len(blocks):
block = blocks[b]
t = {'d': (block[0]+2, block[1]), 'u': (block[0]-2, block[1]),
'r': (block[0], block[1]+2), 'l': (block[0], block[1]-2)}
rch = choice(['d', 'u', 'r', 'l'])
z = t[rch]
# if z[0] > order+1 or z[1] > order+1 or z[0] < 1 or z[1] < 1:
# Decreased chance of having non solvable maze being generated...
if z[0] > order-2 or z[1] > order-2 or z[0] < 2+2 or z[1] < 2+2:
pass
else:
if maze[z[0]][z[1]] == 'X':
if randint(0, 1):
set = None
if rch == 'u':
set = (z[0]+1, z[1])
elif rch == 'd':
set = (z[0]-1, z[1])
elif rch == 'r':
set = (z[0], z[1]-1)
elif rch == 'l':
set = (z[0], z[1]+1)
else:
pass
if maze[set[0]][set[1]] == '_':
# Checks so that no walls that block the entire way are formed
# Makes sure maze is solvable
sets, count = [
(set[0]+1, set[1]), (set[0]-1, set[1]), (set[0], set[1]+1), (set[0], set[1]-1)], 0
for blyat in sets:
while blyat[0] != 0 and blyat[1] != 0 and blyat[0] != order+1 and blyat[1] != order+1:
ch = [(blyat[0]+1, blyat[1]), (blyat[0]-1, blyat[1]),
(blyat[0], blyat[1]+1), (blyat[0], blyat[1]-1)]
suka = []
for i in ch:
if ch not in suka:
if maze[i[0]][i[1]] == 'X':
blyat = i
break
else:
pass
suka.append(ch)
else:
pass
else:
blyat = None
if blyat == None:
break
else:
pass
else:
count += 1
if count < 1:
maze[set[0]][set[1]] = 'X'
blocks.append(set)
else:
pass
else:
pass
else:
pass
b += 1
mazebuilder(maze, order)
spit()
Извините за это!