python - A* 实现的测试在 Python3.8/Windows 中通过，但在 Python3.5/Ubuntu 中失败

Question

对于我正在开发的游戏，我有一个 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它以 2D 坐标为键，值是地形，无论您想存储关于地图方块的任何其他内容。Map.neighbors((x, y))返回给定正方形的邻居的坐标列表。

我对使用 Python 3.8 在我的 Windows 系统上传递的路由查找器进行了测试，但在我的使用 Python 3.5 的 Ubuntu 系统上却没有（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)])

测试运行器输出如下。请注意，路线的长度是相同的，只是找到的具体路线因系统而异。

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)]

标签： pythonpython-3.xunit-testing

Answer 1

问题在于这条线决定了接下来要考虑的路线：

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]))

f_score是一个字典，其键是坐标，值是 f 分数。在 Python 3.7 之前，dict.__items 是 non-deterministic。所以打印语句的输出在 Py3.5 vs Py3.8 中如下所示：

Python 3.5                    Python 3.8
-----------------------       -----------------------                 
(1, 1) fscore: 8 gscore: 0    (1, 1) fscore: 8 gscore: 0
(2, 2) fscore: 8 gscore: 1    (2, 2) fscore: 8 gscore: 1
(3, 3) fscore: 8 gscore: 2    (3, 3) fscore: 8 gscore: 2
(4, 4) fscore: 8 gscore: 3    (4, 4) fscore: 8 gscore: 3
(1, 2) fscore: 9 gscore: 1    (5, 5) fscore: 8 gscore: 4 <= Here they start to vary
(3, 2) fscore: 9 gscore: 2    (6, 6) fscore: 8 gscore: 5
(2, 1) fscore: 9 gscore: 1    (7, 7) fscore: 8 gscore: 6
(2, 3) fscore: 9 gscore: 2    (8, 8) fscore: 8 gscore: 7
(4, 3) fscore: 9 gscore: 3    (9, 9) fscore: 8 gscore: 8
(5, 4) fscore: 9 gscore: 4    (1, 1) fscore: 8 gscore: 0
(3, 4) fscore: 9 gscore: 3    (2, 2) fscore: 8 gscore: 1
(6, 4) fscore: 10 gscore: 5   (3, 3) fscore: 8 gscore: 2
(1, 3) fscore: 10 gscore: 2   (4, 4) fscore: 8 gscore: 3
(7, 5) fscore: 10 gscore: 6   (1, 2) fscore: 9 gscore: 1
(6, 6) fscore: 10 gscore: 7   (2, 1) fscore: 9 gscore: 1
(7, 7) fscore: 10 gscore: 8   (2, 3) fscore: 9 gscore: 2
(4, 2) fscore: 10 gscore: 3   (3, 2) fscore: 9 gscore: 2
(5, 3) fscore: 10 gscore: 4   (3, 4) fscore: 9 gscore: 3
(7, 6) fscore: 10 gscore: 7   (4, 3) fscore: 9 gscore: 3
(8, 7) fscore: 10 gscore: 8   (5, 4) fscore: 9 gscore: 4
(9, 8) fscore: 10 gscore: 9   (1, 3) fscore: 10 gscore: 2
(3, 1) fscore: 10 gscore: 2   (3, 1) fscore: 10 gscore: 2
(8, 8) fscore: 10 gscore: 9   (2, 4) fscore: 10 gscore: 3
(8, 6) fscore: 10 gscore: 7   (4, 2) fscore: 10 gscore: 3
(9, 7) fscore: 10 gscore: 8   (5, 3) fscore: 10 gscore: 4
(9, 9) fscore: 10 gscore: 10  (6, 4) fscore: 10 gscore: 5
 Here Python3.5 is done       (7, 5) fscore: 10 gscore: 6
 in 26 steps                  ... Not done yet! ...
                              Python3.8 keeps going
                              to 36 steps total

所以它们不仅生成了不同的路线，而且 Python3.8 版本需要多 50% 的步骤才能到达路线。

请注意，要通过测试，我应该测试路线经过起点、终点、水上单桥，并且长度为 11 个方格。这在两个系统中都通过：

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'
    route = a_star((1, 1), (9, 9), test_map)
    self.assertIn((1, 1), route)
    self.assertIn((7, 5), route)
    self.assertIn((9, 9), route)
    self.assertEqual(11, len(route))