logo标签列表

路径规划代码产生意外结果。

pythonpath-finding
3
首先，抱歉标题不太好，但我不知道如何用一句话来描述它...
给定一个有三种类型的区域，空区域、墙和出口的网格，我编写了一个程序，检查每个空区域是否“安全”。一个人穿过这个网格，但只能沿着非对角线的方向走，不能穿过墙。这个人从一个区域开始，随机选择一个方向，然后开始朝着那个方向行进。一旦碰到墙，它再次随机选择一个方向，开始向那个方向移动，以此类推。如果一个人以上述方式穿越网格，从该区域开始，则该区域被认为是安全的，保证可以找到出口。
我编写了一个解决这个问题的Python程序。它为检查的每个区域构建一个“树”，包含从该区域出发的所有可能路线。我有一个函数，它只返回给定节点的“父”节点，通过将当前节点的父节点递归地添加到节点列表中，直到达到最顶层节点。
当仅检查一个区域（例如(1, 4)）时，程序按预期工作。但是，在检查示例网格的所有区域时，它不起作用。我已经研究过它，并意识到当检查所有节点时，返回给定节点的所有父节点的alle_parents()函数会产生意外的结果。例如，当检查(1, 4)区域时，该区域的一个子区域是(1, 8)。(1, 8)的父节点应该只是(1, 4)，但实际上情况并非如此。alle_parents((1, 8))返回许多不应存在的不同区域。然而，我无法弄清楚为什么它会表现出这样的行为。我的唯一猜测是它与“剩余”数据/垃圾回收没有按预期工作有关。
相关代码：
class Knoten():
    def __init__(self, x, y, parent = None):
        self.x = x
        self.y = y
        self.parent = parent
        self.children = []

n = len(spielfeld)
m = len(spielfeld[0])
for k in range(n):
    for j in range(m):      
        if spielfeld[k][j] not in [None, '#', 'E']:
            baum = []
            i = 0
            ebene = []
            ebene.append(Knoten(k, j))
            baum.append(ebene)

            i += 1
            while i <= 100:
                ebene = []

                for knoten in baum[i - 1]:
                    children = []

                    if spielfeld[knoten.x][knoten.y] == 'E':
                        continue

                    for feld in next_feld(knoten.x, knoten.y):
                        knoten_neu = Knoten(feld[0], feld[1], knoten)

                        hinzufuegen = True
                        for parent in alle_parents(knoten_neu):
                            if knoten_neu.x == parent.x and knoten_neu.y == parent.y:
                                hinzufuegen = False

                        if hinzufuegen:
                            ebene.append(knoten_neu)
                            children.append(knoten_neu)

                    knoten.children = children

                    if children == []:
                        if spielfeld[knoten.x][knoten.y] != 'E':
                            spielfeld[k][j] = '%' # Field not safe

                baum.append(ebene)
                i += 1

def alle_parents(knoten, parents = []):
    if knoten.parent == None:
        return parents
    else:
        parents.append(knoten.parent)
        return alle_parents(knoten.parent, parents)

我使用的示例地图：

############
# #      # #
#   ##     #
#   #   E# #
#       ## #
#          #
# #E    E###
############

完整代码（其中部分为德语，对此表示抱歉）：http://pastebin.com/3XUBbpkK
如果有人需要任何进一步的信息/解释/代码，只需说出来。由于我自己也不太确定问题是什么，所以我也不确定什么是相关的 :) - J. Pawelczyk
你的代码缩进有问题，请修复它。 - Hugh Bothwell
1
请向您的老师或学习伙伴寻求帮助。 - rbp
1个回答
1
我猜测你遇到了一个常见的 Python 陷阱。这行代码：
def alle_parents(knoten, parents = []):

在模块加载时创建一个空数组，而不是每次调用函数时都创建。将来对alle_parents()的调用将重用相同的数组（可能已经增长），而不是新的空数组！修复的好方法是这样做：
def alle_parents(knoten, parents = None):
    parents = parents or []
谢谢！至少我不会再犯那个错误了:D - J. Pawelczyk
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接