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