Для игры, над которой я работаю, у меня есть реализация алгоритма A *. У меня есть тест, который проверяет маршрут, который он генерирует для данной карты, который проходит в Python3 .8 / Windows, но не проходит в Python3 .5 / Ubuntu. Почему реализация дает в Python 38 другой маршрут, чем в Python 3,5?
Вот функция:
def a_star(start, goal, game_map,
cannot_enter=['edge', 'water']):
"""A* finds a path from the units location to goal.
start and goal are 2D coordinates
game_map is the map object with terrain.
cannot_enter is a list of impassible terrain
from the wiki page: https://en.wikipedia.org/wiki/A*_search_algorithm"""
# The set of discovered nodes that may need to be (re-)expanded.
# Initially, only the start node is known.
open_set = set([start])
# For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start to n currently known.
came_from = {}
#For node n, g_score[n] is the cost of the cheapest path from start to n currently known.
g_score = Map('G score', game_map.dims, 999999999, 9999999999)
g_score[start] = 0
#For node n, f_score[n] = g_score[n] + h(n).
f_score = Map('F score', game_map.dims, 999999999, 9999999999)
f_score[start] = ch_distance(start, goal)
while len(open_set) > 0:
current = min([kv for kv in f_score.items() if kv[0] in open_set], key=lambda i: i[1])[0]
print("{} fscore: {} gscore: {}".format(current,
f_score[current],
g_score[current]))
if current == goal:
return reconstruct_path(came_from, current)
open_set.remove(current)
for neighbor in game_map.neighbors(current):
#d(current, neighbor) is the weight of the edge from current to neighbor
#tentative_g_score is the distance from start to the neighbor through current
# print("{} is {} is it in {}?".format(neighbor,
# game_map[neighbor],
# cannot_enter))
if game_map[neighbor] not in cannot_enter:
tentative_g_score = g_score[current] + 1
else:
tentative_g_score = g_score[neighbor]
if tentative_g_score < g_score[neighbor]:
#This path to neighbor is better than any previous one. Record it!
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = g_score[neighbor] + ch_distance(neighbor, goal)
if neighbor not in open_set:
open_set.add(neighbor)
#open_set is empty but goal was never reached
return False
game_map - это Map объект, который является подклассом dict, который принимает в качестве ключей двухмерные координаты, а значения - это ландшафт, который вы хотите сохранить относительно квадратов карты. Map.neighbors((x, y)) возвращает список координат соседей данного квадрата.
У меня есть тест поиска маршрута, который проходит в моей системе Windows с Python 3.8, но не в моей Ubuntu система с Python 3.5 (IMO версии Python важны, но я упоминаю ОС, поскольку я мог бы убедить ее в противном случае).
def test_indirect_route(self):
"""
01234567890
0EEEEEEEEEEE
1EsPPPPPPPPE
2EP.PPPPPPPE
3EPP.PPPPPPE
4EPPP...PPPE
5EWWWWWW.WWE
6EPPPPP.PPPE
7EPPPPPP.PPE
8EPPPPPPP.PE
9EPPPPPPPPgE
0EEEEEEEEEEE
Not the route I would have chosen, but the same length
"""
test_map = Map()
for x in range(1, 7):
test_map[(x, 5)] = 'water'
for x in range(8, 10):
test_map[(x, 5)] = 'water'
self.assertListEqual(a_star((1, 1), (9, 9), test_map),
[(1, 1), (2, 2), (3, 3), (4, 4), (5, 4), (6, 4), (7, 5), (6, 6), (7, 7), (8, 8), (9, 9)])
Вывод бегуна теста следующий. Обратите внимание, что длины маршрутов одинаковы, просто указанный маршрут c зависит от системы.
Failure
Traceback (most recent call last):
File "/usr/lib/python3.5/unittest/case.py", line 58, in testPartExecutor
yield
File "/usr/lib/python3.5/unittest/case.py", line 600, in run
testMethod()
File "/home/rcriii/workspace/mPyre/src/test_a_star.py", line 47, in test_indirect_route
[(1, 1), (2, 2), (3, 3), (4, 4), (5, 4), (6, 4), (7, 5), (6, 6), (7, 7), (8, 8), (9, 9)])
File "/usr/lib/python3.5/unittest/case.py", line 1018, in assertListEqual
self.assertSequenceEqual(list1, list2, msg, seq_type=list)
File "/usr/lib/python3.5/unittest/case.py", line 1000, in assertSequenceEqual
self.fail(msg)
File "/usr/lib/python3.5/unittest/case.py", line 665, in fail
raise self.failureException(msg)
AssertionError: Lists differ: [(1, [20 chars](4, 4), (5, 4), (6, 4), (7, 5), (7, 6), (8, 7), (9, 8), (9, 9)] != [(1, [20 chars](4, 4), (5, 4), (6, 4), (7, 5), (6, 6), (7, 7), (8, 8), (9, 9)]
First differing element 7:
(7, 6)
(6, 6)
[(1, 1),
(2, 2),
(3, 3),
(4, 4),
(5, 4),
(6, 4),
(7, 5),
- (7, 6),
? ^
+ (6, 6),
? ^
- (8, 7),
? ^
+ (7, 7),
? ^
- (9, 8),
? ^
+ (8, 8),
? ^
(9, 9)]