I implemented a BFS for Pacman. I am getting correct list for nodes expanded. But, I couldn't find the path between Pacman and food. For simplicity, I reversed the stack into queue in the following code.
''' 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)
My pacman_bfs is able to expand all nodes correctly. The output I am obtaining is
3 9
3 8
3 10
3 7
2 10
3 11
2 7
3 6
1 10
3 12
1 7
3 5
1 9
1 11
3 13
1 6
1 8
3 4
1 12
2 13
3 14
1 5
2 4
3 3
1 13
3 15
1 4
3 2
1 14
3 16
1 3
3 1
2 16
1 2
2 1
1 16
1 1
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
But this the list of expanded nodes. The path between the Pacman denoted by "P" and food '.' is
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
The total path is 32. I don't know where I am having problem.
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)
Multiple paths are possible depending on which orientation sequence you go with. I'm exploring right, down, left, up. The path might change based on that.
Output
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)]