Coders Packet

Shortest Path Finder using Python

By Sritiman Adak

This is the shortest pathfinder program that uses the concept of BFS(Breadth-First Search) to find out the shortest path between a start and an end point.

The Python modules used:
Turtle, Tkinter, Random, Numpy


Overview:

A window is opened in front of the user once the program is run.
The window consists of an empty grid of dimension 48x20 and a set of quick instructions about how to use the program.

grid empty

Following the instructions provided, the user can put a start point, an end point and as many hurdles as possible inside the grid. The start point can be recognized as a green square and the end point as a blue square. Positions of the start and end points can be changed by the user as and when they want.

Hurdles are red in colour. These are the locations through which no path can pass. User can place the hurdles manually by clicking at the grid location, where they want it to be placed. Apart from this, the user can also press 'r', which automatically places 100 hurdles at different locations of the grid randomly.

start-end-hurdles

There is no limit in placing hurdles. User can place as many hurdles as possible. But there can be only one start and one end point in the grid.

full-grid
After pressing the spacebar on the keyboard, the program will find the shortest path between the start and end point and display it in the grid. The shortest path will be denoted using black colour.

shortest path

If no path is found, then a popup will be displayed showing: "No path found between the start and the end points".

no path found

Pressing 'o' will remove everything from the grid.

Implementation:

The window is a Turtle Screen object with a width of 1000px and a height of 700px. Inside the window, a grid is drawn using a Turtle object.
Since our target is to make the grid of dimension 48x20, therefore, 21 lines are drawn parallel to the x-axis and 49 lines are drawn parallel to the y-axis with a spacing of 20 pixels in both cases. That makes each square inside the grid of dimension 20x20, and there will be a total of 48*20 = 960 positions inside the grid.

 

def grid(self):

  self.g = tl.Turtle()
  self.g.color("black") 
  self.g.hideturtle()
  self.g.speed(-1)
  for i in range(21):
    self.g.penup()
    self.g.goto(-480,+120-(20*i))
    self.g.pendown()
    self.g.forward(480*2)	
  for i in range(49):
    self.g.penup()
    self.g.setheading(-90)
    self.g.goto(-480+20*i,+120)
    self.g.pendown()
    self.g.forward(400)	

 

 

To draw the start point, end point and hurdles, I have maintained 3 boolean flag variables (start, end, hurdles). Activation of one of these will deactivate the other two.
For eg., if one presses 'e' on the keyboard, the end flag will be set to 'true' and the start and hurdles flag will be set to 'false'.
In this way we can decide what type of entity to draw in the grid, once there is a mouse click.

 

def draw_start(self):
  self.start=True
  self.end = False
  self.hurdles=False

def draw_end(self):
  self.start=False
  self.end = True
  self.hurdles=False

def draw_hurdles(self):
  self.start=False
  self.end = False
  self.hurdles=True

 

 

The draw_square() method finds out the exact location to draw an entity in the grid once a mouse click is listened to. The calculated exact location is (xcor, ycor) and the drawn entity will be a Turtle square object with dimension 20x20. While making a hurdle object, it is also added to the hurdle set (hs).

def draw_squares(self,x,y):
  xcor =None
  ycor =None
  for i in range(self.dx):
    if x<(self.cx+20*i)+10 and x>(self.cx+20*i)-10:
      xcor= self.cx+20*i
      break
  for j in range(self.dy):
    if y<(self.cy-20*j)+10 and y>(self.cy-20*j)-10:
      ycor= self.cy-20*j
      break
  if self.hurdles:		
    if xcor and ycor:	
      loc =j*self.dx + i
      self.prohibited.append(loc)	
      self.t = tl.Turtle()
      self.t.penup()
      self.t.shape("square")
      self.t.color("red")
      self.t.speed(-1)
      self.t.goto(xcor,ycor)
      self.hs.append(self.t)
  if self.start:
    if xcor and ycor:	
      self.start_pt =j*self.dx + i
      try:
        self.st.goto(xcor,ycor)
      except:	
        self.st = tl.Turtle()
        self.st.penup()
        self.st.shape("square")
        self.st.color("green")
        self.st.speed(-1)
        self.st.goto(xcor,ycor)
  if self.end:
    if xcor and ycor:	
      self.end_pt = j*self.dx + i
      try:
        self.et.goto(xcor,ycor)
      except:	
        self.et = tl.Turtle()
        self.et.penup()
        self.et.shape("square")
        self.et.color("blue")
        self.et.speed(-1)
        self.et.goto(xcor,ycor)	

 


The random_hurdles() method will draw 100 hurdles at random positions on the grid. Note that, this function does not check overlapping. So, more than one hurdles can be drawn at the same location.

def random_hurdles(self):
  if self.allow:
    for i in range(100):
      loc = random.randint(0,959)
      self.prohibited.append(loc)	
      self.t = tl.Turtle()
      self.t.penup()
      self.t.shape("square")
      self.t.color("red")
      self.t.speed(-1)
      self.t.goto(self.cx+20*(loc%self.dx),self.cy-20*(loc//self.dx))	
      self.hs.append(self.t)	
      self.allow =False				
  self.allow =True

 


The main method will be called to find the shortest path and also display it in the grid. It will make a BFS object and take its help to find the shortest path.

def main(self):
  b= BFS(self.dx,self.dy)
  b.adjacency(self.prohibited)
  try:
    b.calculate_distance(self.start_pt,self.end_pt)
    for i in self.rs:
      i.goto(1000,1000)
    self.rs.clear()
    for i in b.traversed:
      self.draw_point(i)
  except:
    tmsg.showinfo("Not Found","No path found between the start and the end points")		

 

The BFS class is used to make an adjacency matrix out of the present grid status and also run the Breadth-First Search Algorithm to find the shortest path.
adjacency() method is used to create the adjacency matrix. It makes the adjacency matrix in such a way that every location in the grid is adjacently connected to its upper, left, right and bottom locations. The prohibited list contains all such positions in the grid, where a hurdle is present. Therefore, these positions will not be considered and will be kept isolated from the other positions on the grid. So, its respective values in the adjacency matrix will be all zeroes.

calculate_distance() will calculate the shortest path using the BFS algorithm with the help of the adjacency matrix. The parent variable will keep track of the parent node of the node that is currently being explored. The traversed list will contain all the nodes that were explored while moving from the start point to the end point.
This list will finally be used by the main method to draw the shortest path on the grid.

class BFS:
  def __init__(self,a,b):
    self.x = a
    self.y = b
    self.n = self.x*self.y 
    self.matrix = np.zeros((self.n, self.n))
    #self.vis= []
  
  def adjacency(self, prohibited):
    for i in range(self.n):
      if i not in prohibited:
        for j in range(self.n):
          if j==i+self.x or j==i-self.x:
            self.matrix[i][j] = 1
          if i%self.x==0:
            if j==i+1:
              self.matrix[i][j] = 1
          elif (i+1)%self.x==0:
            if j==i-1:
              self.matrix[i][j] = 1			
          else:
            if j==i+1 or j==i-1:
              self.matrix[i][j] = 1

  def calculate_distance(self ,m, n):
    self.visited = np.zeros(self.n)
    self.parent = np.zeros(self.n)
    self.visited[m] =1
    self.queue =[]
    self.queue.append(m)
    while len(self.queue)>0:
      a = self.queue[0]
      self.queue.remove(a)
      for i in range(self.n):
        if self.matrix[a][i]==1 and self.visited[i]==0:
          self.parent[i]= a
          self.visited[i]= 1
          self.queue.append(i)
          if i==n:
            self.queue=[]
            break					
    if i!=n:
      return				
    self.traversed =[]
    p=int(self.parent[n])
    self.traversed.append(p)
    while(p!=m):
      p = int(self.parent[p])
      if p==m:
        break
      self.traversed.append(p)

 

Though BFS has an exponential time complexity, it can ensure that the path found between any two points in a graph is always the shortest one.

Download project

Reviews Report

Submitted by Sritiman Adak (adaksritiman24)

Download packets of source code on Coders Packet