使用坐标列表的广度优先搜索 python
Breadth First Search with list of coordinates python
我正在为 "spider game" 构建一个简单的 A.I(与贪吃蛇游戏的概念几乎相同,但移动逻辑略有不同)。我正在尝试实现 BFS 算法,以便蜘蛛找到将它引向蚂蚁的路径。该算法似乎适用于多次迭代,但是当我在调试器外部 运行 它时,它在 node_list
内部得到一个 None
值,这使得其他方法失败(因为你无法获得下一步行动)。
这是BFS算法:
def BFS(spider_state, ant_state):
goal = False
count = 0
initial_node = Node(spider_state, None, 0)
node_list = [initial_node]
initial_ant_state = ant_state
while goal == False or len(node_list) == 0:
e = node_list.pop(0)
future_ant_state = initial_ant_state
for i in range(0, e.depth):
future_ant_state = get_next_ant_move(border_choice, initial_ant_state)
for move in POSSIBLE_MOVES:
count += 1
next_node = Node(None, None, None)
next_node.state = get_next_spider_move(deepcopy(e.state), move)
next_node.parent = e
next_node.depth = e.depth + 1
if next_node.state == future_ant_state:
goal = True
break
else:
node_list.append(next_node)
return node_list
节点:
class Node():
def __init__(self, state, parent, depth):
self.state = state
self.parent = parent
self.depth = depth
蜘蛛和蚂蚁表示为 x
和 y
位置的简单列表:
spider = [15, 35]
ant = [20, 10]
get next move
方法如下所示:
def get_next_spider_move(spidy, move):
if spidy:
# check the bounds and assign the new value to spidy
spidy = spider_bounds(spidy)
# farthest right
if move == 0:
spidy[1] += 2
spidy[0] -= 1
# furhter up and right
if move == 1:
spidy[1] += 1
spidy[0] -= 2
# backwords
if move == 2:
spidy[0] += 1
# farthest left
if move == 3:
spidy[1] -= 2
spidy[0] -= 1
# furhter up and to the left
if move == 4:
spidy[1] += 1
spidy[0] -= 2
# one left
if move == 5:
spidy[1] -= 1
# one right
if move == 6:
spidy[1] -= 1
# side right
if move == 7:
spidy[1] += 1
spidy[0] += 1
# side left
if move == 8:
spidy[1] -= 1
spidy[0] -= 1
else:
# if no valid direction was given
return spidy
else:
raise ValueError('spidy must contain an x and y position. %s', spidy, ' was found')
运行时产生的错误:
File "spider_game_bfs.py", line 141, in <module>
path = BFS(spider, ant)
File "spider_game_bfs.py", line 130, in BFS
next_node.state = get_next_spider_move(deepcopy(e.state), move)
File "spider_game_bfs.py", line 100, in get_next_spider_move
raise ValueError('spidy must contain an x and y position. %s', spidy, ' was found')
ValueError: ('spidy must contain an x and y position. %s', None, ' was found')
您的移动函数底部存在逻辑错误。最后一个完整的语句是
if move == 8:
spidy[1] -= 1
spidy[0] -= 1
else:
# if no valid direction was given
return spidy
您的评论不正确:else
子句由 other 以外的任何移动执行 。如果移动 是 8,那么你 return None
,因为你跳过了 returns spidy
.
的语句
正如第一条评论所提到的,使用 if ... elif ... else
作为你的逻辑结构你会做得更好。比这更好的是,请遵循许多移动项目的在线示例:制作移动列表或字典,如下所示:
move_dir = [
(-1, +2), # move 0
(-2, +1), # move 1
(+1, 0), # move 2
... # fill in the rest
]
if move in range(len(move_dir)):
spidy[0] += move_dir[move[0]]
spidy[1] += move_dir[move[1]]
return spidy
else:
raise ValueError ...
我正在为 "spider game" 构建一个简单的 A.I(与贪吃蛇游戏的概念几乎相同,但移动逻辑略有不同)。我正在尝试实现 BFS 算法,以便蜘蛛找到将它引向蚂蚁的路径。该算法似乎适用于多次迭代,但是当我在调试器外部 运行 它时,它在 node_list
内部得到一个 None
值,这使得其他方法失败(因为你无法获得下一步行动)。
这是BFS算法:
def BFS(spider_state, ant_state):
goal = False
count = 0
initial_node = Node(spider_state, None, 0)
node_list = [initial_node]
initial_ant_state = ant_state
while goal == False or len(node_list) == 0:
e = node_list.pop(0)
future_ant_state = initial_ant_state
for i in range(0, e.depth):
future_ant_state = get_next_ant_move(border_choice, initial_ant_state)
for move in POSSIBLE_MOVES:
count += 1
next_node = Node(None, None, None)
next_node.state = get_next_spider_move(deepcopy(e.state), move)
next_node.parent = e
next_node.depth = e.depth + 1
if next_node.state == future_ant_state:
goal = True
break
else:
node_list.append(next_node)
return node_list
节点:
class Node():
def __init__(self, state, parent, depth):
self.state = state
self.parent = parent
self.depth = depth
蜘蛛和蚂蚁表示为 x
和 y
位置的简单列表:
spider = [15, 35]
ant = [20, 10]
get next move
方法如下所示:
def get_next_spider_move(spidy, move):
if spidy:
# check the bounds and assign the new value to spidy
spidy = spider_bounds(spidy)
# farthest right
if move == 0:
spidy[1] += 2
spidy[0] -= 1
# furhter up and right
if move == 1:
spidy[1] += 1
spidy[0] -= 2
# backwords
if move == 2:
spidy[0] += 1
# farthest left
if move == 3:
spidy[1] -= 2
spidy[0] -= 1
# furhter up and to the left
if move == 4:
spidy[1] += 1
spidy[0] -= 2
# one left
if move == 5:
spidy[1] -= 1
# one right
if move == 6:
spidy[1] -= 1
# side right
if move == 7:
spidy[1] += 1
spidy[0] += 1
# side left
if move == 8:
spidy[1] -= 1
spidy[0] -= 1
else:
# if no valid direction was given
return spidy
else:
raise ValueError('spidy must contain an x and y position. %s', spidy, ' was found')
运行时产生的错误:
File "spider_game_bfs.py", line 141, in <module>
path = BFS(spider, ant)
File "spider_game_bfs.py", line 130, in BFS
next_node.state = get_next_spider_move(deepcopy(e.state), move)
File "spider_game_bfs.py", line 100, in get_next_spider_move
raise ValueError('spidy must contain an x and y position. %s', spidy, ' was found')
ValueError: ('spidy must contain an x and y position. %s', None, ' was found')
您的移动函数底部存在逻辑错误。最后一个完整的语句是
if move == 8:
spidy[1] -= 1
spidy[0] -= 1
else:
# if no valid direction was given
return spidy
您的评论不正确:else
子句由 other 以外的任何移动执行 。如果移动 是 8,那么你 return None
,因为你跳过了 returns spidy
.
正如第一条评论所提到的,使用 if ... elif ... else
作为你的逻辑结构你会做得更好。比这更好的是,请遵循许多移动项目的在线示例:制作移动列表或字典,如下所示:
move_dir = [
(-1, +2), # move 0
(-2, +1), # move 1
(+1, 0), # move 2
... # fill in the rest
]
if move in range(len(move_dir)):
spidy[0] += move_dir[move[0]]
spidy[1] += move_dir[move[1]]
return spidy
else:
raise ValueError ...