CODEWITHSUNDEEP
algorithmartificial-intelligencemazepacmanbreadth-first-search
ali mardani
ali mardani

Reputation: 345

How to implement BFS algorithm for pacman?

I'm implementing AI for pacman in a maze world using search algorithms like DFS , BFS , UCS and A* . the implementing for DFS is very simple, but for BFS I'm mixed up. I don't know how to implement it , because I can't understand how could it possible that pacman start from a location and enqueue its neighbor's location and check them and go through to them. :/ can anyone help me? !

Upvotes: 0

Views: 9392

Answers (2)

Tolokoban
Tolokoban

Reputation: 2339

If you're looking for the shortest path, you have to memorize the already visited positions, because the shortest path will use all its positions only once.

Here is a simplified version of the algorithm:

Q := an empty queue of positions
V := an empty set of already visited positions
Q.pushBack( initial position )
While Q is not empty:
    current_position := Q.popFront()
    If current_position == goal_position:
        Return "You won!"
    If current_position Is Not In V:
        Q.pushBack( NeighboursOf(current_position) )

I used a very simple state, holding only the position. But if you want a full algorithm, your state must contain the position plus the path to this position. And when you compare two states, just compare the positions, not the path.

Upvotes: 1

amit
amit

Reputation: 178431

In BFS, you traverse the algorithm and discover a shortest path to each node.

In order to get this path later on, you need to store parent:V->V, in other words, you need to "remember" from which cell you got to the current one. This is easily done by storing a dictionary/map, where the key is a cell, and the value is the cell you used to discover the key.

In pseudo code:

BFS(source, target):
   queue = empty new queue
   queue.add(source)
   parent= new dictionary
   parent.add(source, None)
   while (queue.empty() == false): 
      curr = queue.dequeue()
      if (curr == target)
          return getPath(dict, curr)
      for each neighbor u of curr:
          if u is not a key in parent:
             parent[u] = curr
             queue.add(u)

The above BFS fills the parent dictionary, and the path is returned by the following getPath() function, which basically traverses the dictionary until it finds the "root" (which is the original source node).

getPath(dict, target):
   sol = [] //empty list
   curr = target
   while curr != None:
         sol.addFirst(curr)
         curr = dict.get(curr)

Upvotes: 2

Related Questions