EEEE4008: Host Machine Python Code

#import libraries and functions
import pygame
import math
from queue import PriorityQueue
from itertools import cycle
import io
import dropbox

#delete token when uploading
token = "" #add your own dropbox API token here
DBX = dropbox.Dropbox(token)

#setup the window
ROWS = 21
WIDTH = 16*ROWS
WIN = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("A* Path Finding Algorithm within a Maze")

#define global variables
global poolNext
poolNext = [3,0,1,2]
poolNext = cycle(poolNext)

#define colour codes in RGB format
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 255, 0)
YELLOW = (255, 255, 0)
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
PURPLE = (128, 0, 128)
ORANGE = (255, 165 ,0)
GREY = (128, 128, 128)
TURQUOISE = (64, 224, 208)

#define the Spot class - each spot is a cell
class Spot:
        #define each spots default parameters - default to black (obstacle)
    def __init__(self, row, col, width, total_rows):
        self.row = row
        self.col = col
        self.x = row * width
        self.y = col * width
        self.colour = BLACK
        self.neighbours = []
        self.width = width
        self.total_rows = total_rows

    def get_pos(self):
        return self.row, self.col

    def is_closed(self):
        return self.colour == RED

    def is_open(self):
        return self.colour == GREEN

    def is_barrier(self):
        return self.colour == BLACK

    def is_start(self):
        return self.colour == ORANGE

    def is_end(self):
        return self.colour == TURQUOISE

    def draw_path(self):
        self.colour = WHITE

    def make_start(self):
        self.colour = ORANGE

    def make_closed(self):
        self.colour = RED

    def make_open(self):
        self.colour = GREEN

    def make_barrier(self):
        self.colour = BLACK

    def make_end(self):
        self.colour = TURQUOISE

    def draw_shortest_path(self):
        self.colour = PURPLE

    def draw(self, win):
        pygame.draw.rect(win, self.colour, (self.x, self.y, self.width, self.width))

        #define the neighbours indexes to a specific cell
    def update_neighbours(self, grid):
        self.neighbours = []
        if self.row < self.total_rows - 1 and not grid[self.row + 1][self.col].is_barrier(): #down
            self.neighbours.append(grid[self.row + 1][self.col])

        if self.row > 0 and not grid[self.row - 1][self.col].is_barrier(): #up
            self.neighbours.append(grid[self.row - 1][self.col])

        if self.col < self.total_rows - 1 and not grid[self.row][self.col + 1].is_barrier(): #right
            self.neighbours.append(grid[self.row][self.col + 1])

        if self.col > 0 and not grid[self.row][self.col - 1].is_barrier(): #left
            self.neighbours.append(grid[self.row][self.col - 1])

    def __lt__(self, other):
        return False

#define the manhattan distance heuristic
def heuristic(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
    return abs(x1 - x2) + abs(y1 - y2)

#define the shortest path visualisation
def reconstruct_path(came_from, current, draw):
    while current in came_from:
        current = came_from[current]
        current.draw_shortest_path()
        draw()

#define the A-star algorithm
def algorithm(draw, grid, start, end):
    count = 0
    open_set = PriorityQueue()
    open_set.put((0, count, start))
    came_from = {}
    g_score = {spot: float("inf") for row in grid for spot in row}
    g_score[start] = 0
    f_score = {spot: float("inf") for row in grid for spot in row}
    f_score[start] = heuristic(start.get_pos(), end.get_pos())

    open_set_hash = {start}

        #when not at the end node or whole maze not explored
    while not open_set.empty():
                #if the close button is pressed
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()

        current = open_set.get()[2]
        open_set_hash.remove(current)

                #once at the end node
        if current == end:
            reconstruct_path(came_from, end, draw)
            end.make_end()
            return True

                #for each of the neighbours, calculate and select the one with the lowest manhattan distance
        for neighbour in current.neighbours:
            temp_g_score = g_score[current] + 1

            if temp_g_score < g_score[neighbour]:
                came_from[neighbour] = current
                g_score[neighbour] = temp_g_score
                f_score[neighbour] = temp_g_score + heuristic(neighbour.get_pos(), end.get_pos())
                if neighbour not in open_set_hash:
                    count += 1
                    open_set.put((f_score[neighbour], count, neighbour))
                    open_set_hash.add(neighbour)
                    neighbour.make_open()

        draw()

        if current != start:
            current.make_closed()

    return False

#define the grid generation parameters
def make_grid(rows, width):
    grid = []
    gap = width // rows
    for i in range(rows):
        grid.append([])
        for j in range(rows):
            spot = Spot(i, j, gap, rows)
            grid[i].append(spot)

    return grid

#define the gridline parameters
def draw_grid(win, rows, width):
    gap = width // rows
    for i in range(rows):
        pygame.draw.line(win, GREY, (0, i * gap), (width, i * gap))
        for j in range(rows):
            pygame.draw.line(win, GREY, (j * gap, 0), (j * gap, width))

#define the update to the whole window
def draw(win, grid, rows, width):
    win.fill(WHITE)

    for row in grid:
        for spot in row:
            spot.draw(win)

    draw_grid(win, rows, width)
    pygame.display.update() #update the pygame window

#define the main function
def main(win, width, ROWS):
        #make the initial grid full of obstacles
    grid = make_grid(ROWS, width)

                #path = 'C:/Users/natda/Desktop/maze.txt'
    _, res = DBX.files_download("/maze.txt")
    res.raise_for_status()

    with io.BytesIO(res.content) as stream:
        temp = stream.read().decode()

                #maze_file = open(path,'r')
                #temp = maze_file.read()
    maze_path = temp.split(',')     #seperate string at commas
    length = len(maze_path)

    #mark start
    start = grid[int(ROWS/2)][ROWS-1]
    start.make_start()

    #set current position as start point
    current_x = int(ROWS/2)
    current_y = ROWS - 1

    #draw inital forward motion
    step_total = int(maze_path[0])
    for step in range(1,step_total):
        path = grid[current_x][current_y - step]
        path.draw_path()

    #update current position
    current_y = current_y - step

    #draw all paths
    for i in range(1,length):
        #print (maze_path[i])
        path_var = maze_path[i]

        if path_var == 'L':
            #print ("Turn")
            dirFlag = next(poolNext)
            dirFlag = next(poolNext)
            dirFlag = next(poolNext)
            #print("Q: " + str(dirFlag))
        elif path_var == 'R':
            dirFlag = next(poolNext)
            #print("Q: " + str(dirFlag))
        else :
            if dirFlag == 0 or dirFlag == 4:
                #draw down
                path_var = int(path_var)+1
                for step in range(1,path_var):
                    path = grid[current_x][current_y + step]
                    path.draw_path()
                    draw(WIN, grid, ROWS, WIDTH)
                current_y = current_y + step
            if dirFlag == 1:
                #draw left
                path_var = int(path_var)+1
                for step in range(1,path_var):
                    path = grid[current_x - step][current_y]
                    path.draw_path()
                    draw(WIN, grid, ROWS, WIDTH)
                current_x = current_x - step
            if dirFlag == 2:
                #draw up
                path_var = int(path_var)+1
                for step in range(1,path_var):
                    path = grid[current_x][current_y - step]
                    path.draw_path()
                    draw(WIN, grid, ROWS, WIDTH)
                current_y = current_y - step
            if dirFlag == 3:
                #draw right
                path_var = int(path_var)+1
                for step in range(1,path_var):
                    path = grid[current_x + step][current_y]
                    path.draw_path()
                    draw(WIN, grid, ROWS, WIDTH)
                current_x = current_x + step


    #print("X: " + str(current_x))
    #print("Y: " + str(current_y))

    #mark end
    end = grid[current_x][current_y]
    end.make_end()

    run = True
    while run:
        draw(win, grid, ROWS, width)
        #if the close button is pressed
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                run = False

            #if the spacebar pressed - start algorithm
            if event.type == pygame.KEYDOWN:
                if event.key == pygame.K_SPACE:
                    for row in grid:
                        for spot in row:
                            spot.update_neighbours(grid)

                    algorithm(lambda: draw(win, grid, ROWS, width), grid, start, end)

                                        ##start shortest path extraction
                    #open & clear text file
                    path2 = 'C:/Users/natda/Desktop/extracted_route.txt'
                    extracted_route = open(path2,'w') #w overwrites existing file

                    #extract route
                    current_x = int(ROWS/2)
                    current_y = ROWS - 1
                    current_pos = grid[current_x][current_y]
                    route_string = ""
                    prev_move = ''

                    neighbour_up = grid[current_x][current_y - 1]
                    neighbour_left = grid[current_x - 1][current_y]
                    neighbour_right = grid[current_x + 1][current_y]

                    if neighbour_up.colour == PURPLE:
                        prev_move = 'U'
                        route_string += "U"
                        current_y = current_y - 1

                    if neighbour_left.colour == PURPLE:
                        prev_move = 'L'
                        route_string += "L"
                        current_x = current_x - 1

                    if neighbour_right.colour == PURPLE:
                        prev_move = 'R'
                        route_string += "R"
                        current_x = current_x + 1
                    #print(route_string)
                    current_pos = grid[current_x][current_y]

                    #while not at the end
                    while current_pos.colour != TURQUOISE:
                        neighbour_up = grid[current_x][current_y - 1]
                        neighbour_down = grid[current_x][current_y + 1]
                        neighbour_left = grid[current_x - 1][current_y]
                        neighbour_right = grid[current_x + 1][current_y]

                                                #move to the next unexplored cell on the shortest path
                        if neighbour_up.colour == PURPLE and prev_move != 'D':
                            prev_move = 'U'
                            route_string += "U"
                            current_y = current_y - 1

                        elif neighbour_left.colour == PURPLE and prev_move != 'R':
                            prev_move = 'L'
                            route_string += "L"
                            current_x = current_x - 1

                        elif neighbour_right.colour == PURPLE and prev_move != 'L':
                            prev_move = 'R'
                            route_string += "R"
                            current_x = current_x + 1

                        elif neighbour_down.colour == PURPLE and prev_move != 'U':
                            prev_move = 'D'
                            route_string += "D"
                            current_y = current_y + 1

                        else:
                            break

                        #print(route_string)
                        current_pos = grid[current_x][current_y]

                    #print(route_string)

                    #clean up string & write to text file
                    count = 1
                    compact_route_string = ""
                    for i in range(1, len(route_string) + 1):
                        if i == len(route_string):
                            compact_route_string += route_string[i - 1] + str(count)
                            break
                        elif route_string[i - 1] == route_string[i]:
                            count += 1
                        else:
                            compact_route_string += route_string[i - 1] + str(count)
                            count = 1

                    #print(compact_route_string)

                    compact_route_string_spaced = ""
                    compact_route_string_spaced = compact_route_string[0] + ","

                    for i in range(1, len(compact_route_string)):
                        try:
                            int(compact_route_string[i])
                            compact_route_string_spaced += compact_route_string[i]
                        except:
                            compact_route_string_spaced += "," + compact_route_string[i] + ","

                    print(compact_route_string_spaced)

                    extracted_route = open(path2,'a')
                    extracted_route.write(compact_route_string_spaced)
                    extracted_route.close()

                    with io.BytesIO(compact_route_string_spaced.encode()) as stream:
                        stream.seek(0)

                        # Write a text file
                        DBX.files_upload(stream.read(), "/extracted_route.txt", mode=dropbox.files.WriteMode.overwrite)


    pygame.quit()

main(WIN, WIDTH, ROWS)