Shortest Path Algorithm (Part 2)

In the first part of this study, we have implemented two classes to draw an empty board. Now that we have theses classes, we’ll change them a little bit just to randomly make a few nodes look like blocked. Just to remember, this study is divided into three parts.

The division intends to make it easier to understand and visualize the algorithm.

1 - Imports

Since we’ll randomly choose which node to block, we have to import a native library called random.

from PIL import Image, ImageDraw
import random

2 - Classes

To mark the node as blocked, we gonna add a new parameter on the __init__ method of the Node class.

Let’s call this parameter blocked and set the default value as False.

class Node:
    """
    Each node on the board
    """
    # size of each node
    SIZE=30
    
    def __init__(self, x, y, blocked=False, fill='#FFFFFF', outline='#000000'):
        # define node position
        self.x = x
        self.y = y
        
        # define status
        self.blocked = blocked

        # define node colors
        self.fill = fill
        self.outline = outline
        
    def draw(self, base):
        # define the start of the image
        left = self.x * self.SIZE
        top = self.y * self.SIZE
        
        # define the end of the image
        right = left + self.SIZE
        bottom = top + self.SIZE
        
        # shape
        shape = [(left, top), (right, bottom)]

        node = ImageDraw.Draw(base)   
        if self.blocked:
            # create rectangle with grey background
            node.rectangle(shape, fill=(173, 173, 173), outline=self.outline)
            
            # define the angles of the lines
            ltr = (left, top, right, bottom)
            rtl = (right, top, left, bottom)
            
            # add the lines on top of the rectangle
            node.line(ltr, fill=(100, 100, 100), width=1)
            node.line(rtl, fill=(100, 100, 100), width=1)
        else:
            node.rectangle(shape, fill=self.fill, outline=self.outline)

Another change we need is inside draw method. Let’s put an if to check if the node as free or blocked.

Inside the if, we create a rectangle with a grey background, and then, using left, top, right, and bottom variables define two lines that will be drawn on top of the rectangle as an X.

  • The ltr variable store a tuple with the coordinates from the left/top edge to the right/bottom edge of the node;
  • And the rtl variable store a tuple with the coordinates from the right/top edge to the left/bottom edge of the node.

After the definition, we pass the variables as a first parameter of the method line followed by the grey color (100, 100, 100) and the thickness of the line (which is 1px).

In the Board class, let’s add a new parameter to define the probability of the node being blocked.

class Board:
    """
    Matrix of Nodes
    """
    
    def __init__(self, rows, cols, max_to_block=15):
        # size of the board
        self.rows = rows
        self.cols = cols
        self.max_to_block = max_to_block
        
    def create(self):
        # start empty board
        self.board = [None] * self.rows

        for row in range(0, self.rows):
            self.board[row] = [None] * self.cols
            for col in range(0, self.cols):
                blocked = random.randint(1, 100)
                self.board[row][col] = Node(col, row, blocked < self.max_to_block)
                
    def draw(self):
        w = self.cols * 30
        h = self.rows * 30
        
        # define base image
        img = Image.new("RGB", (w, h), (173, 173, 173))

        for row in range(0, self.rows):
            for col in range(0, self.cols):
                self.board[row][col].draw(img)
        
        # draw final image
        img.show()

Inside create method, let’s call random.randint(1, 100) to get a random number from 1 to 100 and store the result on the variable blocked.

Now, we can compare the value of blocked and max_to_block value to randomly create a node as free or blocked.

3 - Drawing

After these changes, we just need to create an instance of the Board class with the number of rows and cols the board has.

board = Board(18, 18)

Then, call the methods create and draw to see the board.

board.create()
board.draw()