For a game i am working on, I have an implementation of the A* algorithm. I have a test that checks the route it generates for a given map, that passes in Python3.8/Windows but fails in Python3.5/Ubuntu. Why does the implementation give a different route in Python 38 than it does in Python 3.5?
Here is the function:
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
The game_map is a Map object, which is a subclass of dict that takes as keys 2D coordinates and the values are terrain whatever else you want to store about map squares. Map.neighbors((x, y)) returns a list of the coordinates of the neighbors of the given square.
I have a test of the route finder that passes on my Windows system with Python 3.8, but not on my Ubuntu system with Python 3.5 (IMO the Python versions are important, but I'm mentioning the OS as I could be persuaded otherwise).
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)])
The test runner output is as follows. Note that the lengths of the routes are the same, just the specific route found varies between systems.
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)]
