从 expanded/explored 个节点中找到 Pacman 的路径

Question

我为 Pacman 实现了 BFS。我得到了扩展节点的正确列表。但是，我找不到 Pacman 和食物之间的路径。为了简单起见，我在下面的代码中将堆栈反转为队列。

''' A Sample BFS Algorithm '''

import pprint
def bfs( r, c, pacman_r, pacman_c, food_r, food_c, grid):

    stack = [(pacman_r-1,pacman_c),(pacman_r,pacman_c-1),(pacman_r,pacman_c+1),(pacman_r+1,pacman_c)]
    queue = stack[::-1]


    visited = []
    path = []

    print 'The pacman start',grid[pacman_r][pacman_c]
    count = 0
    while grid[pacman_r][pacman_c] != '.':

        move = queue.pop()

        if move not in visited:
            visited.append(move)
            new_r, new_c  = move[0], move[1]

            if grid[new_r][new_c] == '-':
                path.append((new_r,new_c))
                print 'The path', (new_r, new_c)

                pacman_r = new_r
                pacman_c = new_c
                new_stack = [(pacman_r-1,pacman_c),(pacman_r,pacman_c-1),(pacman_r,pacman_c+1),(pacman_r+1,pacman_c)]
                new_queue = new_stack[::-1]
                queue = new_queue + queue
                count = count+1


            if grid[new_r][new_c] == '.':
                print "The destination", (new_r, new_c)
                pacman_r = new_r
                pacman_c = new_c
                count = count + 1

    print "Count", count

    return

pacman_r = 3
pacman_c = 9

food_r = 5
food_c = 1

r = 7
c = 20



grid = ['%%%%%%%%%%%%%%%%%%%%', '%--------------%---%', '%-%%-%%-%%-%%-%%-%-%', '%--------P-------%-%', '%%%%%%%%%%%%%%%%%%-%', '%.-----------------%', '%%%%%%%%%%%%%%%%%%%%']

bfs(r, c, pacman_r, pacman_c, food_r, food_c, grid)

我的pacman_bfs能够正确展开所有节点。我获得的输出是

但这是扩展节点列表。 "P" 表示的 Pacman 和食物 '.' 之间的路径是

总路径为32。我不知道我哪里有问题。

Answer 1

from Queue import Queue
def bfs(numRows, numCols, pacmanPos, grid):
    q = Queue()
    q.put((pacmanPos, [pacmanPos]))
    visited = set([pacmanPos])
    while not q.empty():
        currentPos, path = q.get()
        row, column = currentPos
        if grid[row][column] == '.':
            return len(path), path
        for newPos in [(row, column + 1), (row + 1, column), (row, column - 1), (row - 1, column)]:
            if newPos not in visited and newPos[0] < numRows and newPos[1] < numCols and grid[newPos[0]][newPos[1]] != '%':
                q.put((newPos, path + [newPos]))
                visited.add(newPos)

    return 0, []

r = 7
c = 20

pacmanPos = (3, 9)

grid = ['%%%%%%%%%%%%%%%%%%%%', 
        '%--------------%---%', 
        '%-%%-%%-%%-%%-%%-%-%', 
        '%--------P-------%-%', 
        '%%%%%%%%%%%%%%%%%%-%', 
        '%.-----------------%', 
        '%%%%%%%%%%%%%%%%%%%%']

pathLength, path = bfs(r, c, pacmanPos, grid)
print 'Path Length: {} \nPath: {}'.format(pathLength, path)

可能有多个路径，具体取决于您使用的方向顺序。我正在向右、向下、向左、向上探索。路径可能会因此改变。

输出

Path Length: 33 
Path: [(3, 9), (3, 10), (3, 11), (3, 12), (3, 13), (3, 14), (3, 15), (3, 16), (2, 16), (1, 16), (1, 17), (1, 18), (2, 18), (3, 18), (4, 18), (5, 18), (5, 17), (5, 16), (5, 15), (5, 14), (5, 13), (5, 12), (5, 11), (5, 10), (5, 9), (5, 8), (5, 7), (5, 6), (5, 5), (5, 4), (5, 3), (5, 2), (5, 1)]

从 expanded/explored 个节点中找到 Pacman 的路径

Find the path for Pacman from expanded/explored nodes

python

pacman

breadth-first-search