CODEWITHSUNDEEP
pythonalgorithmbreadth-first-search
LordLightingXII
LordLightingXII

Reputation: 51

Understanding a python breadth-first-search algorithm

I'm trying to understand this Breadth First Search python implementation and I understand most of it shown in my commenting but I don't get this line here:

for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
           a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

           if maze.in_maze(a, b) and not maze.is_wall(a, b) and (a, b) not in parent: #Check to see if the coordinates that are searching is inside the wall is not a wall and not inside of parent
               parent[(a, b)] = current #?
               dist[(a, b)] = dist[current] + 1; #?
               queue.append((a, b)) #Add the coordinates to the end of the queue

The whole code can be found here, please feel free to call me out on any commenting error. I'm still new to python so I don't know exactly what every line does but I get a rough idea.

from collections import deque #A double-ended queue, or deque, supports adding and removing elements from either end. Import this from collections

nodes = 0 #Initialise nodes with value 0


def solve(maze, start, end): #Solve function that takes in the maze, start and end points as arguments
   global nodes #Declare nodes as a global variable
   nodes = 0 #Set nodes value to 0

   queue = deque() #Set queue as a double ended queue
   parent, dist = dict(), dict() #Set parent and dist

   queue.append(start) #Add start point to the queue
   parent[start], dist[start] = start, 1

   while len(queue): #While there are items in the list
       current = queue.popleft() #Set current to the first thing in the queue from the left
       nodes += 1 #Increment nodes by 1

       if current == end: #If the current place is the end target then solution has been found and we can exit the loop
           break #Exit the loop

       for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
           a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

           if maze.in_maze(a, b) and not maze.is_wall(a, b) and (a, b) not in parent: #Check to see if the coordinates that are searching is inside the wall is not a wall and not inside of parent
               parent[(a, b)] = current #Set later
               dist[(a, b)] = dist[current] + 1; #set later
               queue.append((a, b)) #Add the coordinates to the end of the queue

   if end not in parent: #If there is no solution
      return [] #Return an empty solution
   else: #Otherwise if there is a solution
      path = [] #Initialise path as an empty list
      while start != end: #While the starting point is not the end point, the solution has not be found so
          path.append(end) #Keep appending the end node to the path queue until they meet the condition
          end = parent[end] #Set end point to the position it is in the parent dictionary
      path.append(start) #Insert the starting point to the end of the queue
      path.reverse() #Reverse the path queue since the solution was found back to front
      return path #Return the final solution

Upvotes: 0

Views: 306

Answers (2)

illusion
illusion

Reputation: 1301

So, in the above code, after reading, I am assuming, that start and end are represented by coordinates like (x, y). Also, if you select any coordinate in the "maze", you can only traverse in up, down, left, right directions i.e. if you are on the coordinates (x, y) you can only go to one of the following coordinates: (x+1, y), (x-1, y), (x, y+1), (x, y-1)

So basically, the for loop is used to select the neighboring coordinates in which you can traverse, one by one. Then a, b = current[0] + dx, current[1] + dy this line is used to get the absolute coordinates of the neighboring coordinates. Then we check if the new coordinate exists in the maze or if it is a wall. If it is in the maze and not a wall and also we have not already traversed through it, we update the parent dict and also update the dist dict (for the distance).

The parent dict stores the parent of the coordinate. So for (x+1, y) the parent will be (x, y) which is current. parent[(x+1, y)] = (x, y) that means the parent of (x+1, y) is (x, y)

the dist dict stores the distance or non of steps required to reach the new coord. dist[(x+1, y)] = dist[(x,y)] + 1 that means, distance of new coordinate is equal to distance of parent + 1 new step.

Then we add it to the queue.

Upvotes: 1

Błotosmętek
Błotosmętek

Reputation: 12927

parent[(a, b)] = current

is used to store the coordinates (current) of the location from which you came to coordinates (a, b). Oh, and BTW, this comment here is wrong:

   for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
       a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

It should be "Search in every direction, one at a time". There is nothing random here.

Upvotes: 1

Related Questions