寻路代码产生意想不到的结果
Pathfinding code produces unexpected results
首先,请原谅标题不好,但我不知道如何用一句话来形容...
给定一个包含 3 种字段、空白字段、墙壁和出口的网格,我编写了一个程序来检查每个空白字段,是否该字段是 "safe"。
一个人穿过那个格子,但是只能走non-diagonally,不能穿墙。这个人从一个领域开始,随机选择一个方向并开始朝那个方向走。一旦撞到墙,它会再次随机选择一个方向,开始向 那个 方向移动,依此类推。
如果一个人按照上述方式穿过网格,从该字段开始,保证在某个点找到出口,则该字段被认为是安全的。
我写了一个Python程序来解决这个问题。它为它检查的每个字段构建一个 "tree" ,包含来自该字段的每条可能路径。
我有一个函数,它只是 returns 给定节点的 "parent",通过递归地将当前节点的 parent 添加到节点列表,直到它到达最顶层的节点。
当仅检查一个字段时,程序按预期工作,例如 (1, 4)。但是,当检查示例网格的所有字段时它不起作用。
我已经研究过它并意识到 alle_parents() 函数 returns 给定节点的所有 parent 在检查所有节点时会产生意外结果。例如。检查字段 (1, 4) 时,该节点的一个 child 是 (1, 8)。 (1, 8) 的 parent 应该只是 (1, 4)。但事实并非如此。 alle_parents((1, 8)) returns 许多不应该存在的不同字段。但是我无法弄清楚为什么它的行为如此。我唯一的猜测是它与 "left-over" data/GC 没有按预期工作有关。
相关代码:
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
我怀疑您的问题是一个常见的 Python 陷阱。这一行:
def alle_parents(knoten, parents = []):
加载模块时创建一个空数组,而不是每次调用函数时。对 alle_parents() 的未来调用将重用相同的数组(其大小可能已经增加)而不是新的空数组!一个很好的修复方法是这样做:
def alle_parents(knoten, parents = None):
parents = parents or []
首先,请原谅标题不好,但我不知道如何用一句话来形容...
给定一个包含 3 种字段、空白字段、墙壁和出口的网格,我编写了一个程序来检查每个空白字段,是否该字段是 "safe"。 一个人穿过那个格子,但是只能走non-diagonally,不能穿墙。这个人从一个领域开始,随机选择一个方向并开始朝那个方向走。一旦撞到墙,它会再次随机选择一个方向,开始向 那个 方向移动,依此类推。 如果一个人按照上述方式穿过网格,从该字段开始,保证在某个点找到出口,则该字段被认为是安全的。
我写了一个Python程序来解决这个问题。它为它检查的每个字段构建一个 "tree" ,包含来自该字段的每条可能路径。 我有一个函数,它只是 returns 给定节点的 "parent",通过递归地将当前节点的 parent 添加到节点列表,直到它到达最顶层的节点。
当仅检查一个字段时,程序按预期工作,例如 (1, 4)。但是,当检查示例网格的所有字段时它不起作用。
我已经研究过它并意识到 alle_parents() 函数 returns 给定节点的所有 parent 在检查所有节点时会产生意外结果。例如。检查字段 (1, 4) 时,该节点的一个 child 是 (1, 8)。 (1, 8) 的 parent 应该只是 (1, 4)。但事实并非如此。 alle_parents((1, 8)) returns 许多不应该存在的不同字段。但是我无法弄清楚为什么它的行为如此。我唯一的猜测是它与 "left-over" data/GC 没有按预期工作有关。
相关代码:
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
我怀疑您的问题是一个常见的 Python 陷阱。这一行:
def alle_parents(knoten, parents = []):
加载模块时创建一个空数组,而不是每次调用函数时。对 alle_parents() 的未来调用将重用相同的数组(其大小可能已经增加)而不是新的空数组!一个很好的修复方法是这样做:
def alle_parents(knoten, parents = None):
parents = parents or []