collab/mm20
git clone https://git.julia.blue/collab/mm20
9fadb5c
algorithms
1import pygame 2import math 3from queue import PriorityQueue 4 5width = 800 6win = pygame .display .set_mode ((width ,width )) 7pygame .display .set_caption ('A* Path finding Algorithm' ) 8 9# colors 10red = (255 ,0 ,0 ) 11green = (0 ,255 ,0 ) 12blue = (0 ,0 ,255 ) 13yellow = (255 ,255 ,0 ) 14black = (0 ,0 ,0 ) 15white = (255 ,255 ,255 ) 16purple = (128 ,0 ,128 ) 17orange = (255 ,165 ,0 ) 18grey = (128 ,128 ,128 ) 19turquoise = (64 ,224 ,208 ) 20 21 22class Spot : 23def __init__ (self ,row ,col ,width ,total_rows ): 24self .row = row 25self .col = col 26self .x = row * width 27self .y = col * width 28self .color = white 29self .neighbors = [] 30self .width = width 31self .total_rows = total_rows 32 33def get_pos (self ): 34return self .row ,self .col 35 36def is_closed (self ): 37return self .color == red 38 39def is_open (self ): 40return self .color == green 41 42def is_barrier (self ): 43return self .color == black 44 45def is_start (self ): 46return self .color == orange 47 48def is_end (self ): 49return self .color == turquoise 50 51def make_start (self ): 52self .color = orange 53 54def reset (self ): 55self .color = white 56 57def make_closed (self ): 58self .color = red 59 60def make_open (self ): 61self .color = green 62 63def make_barrier (self ): 64self .color = black 65 66def make_end (self ): 67self .color = turquoise 68 69def make_path (self ): 70self .color = purple 71 72def draw (self ,win ): 73pygame .draw .rect (win ,self .color , (self .x ,self .y ,self .width ,self .width )) 74 75def update_neighbors (self ,grid ): 76self .neighbors = [] 77if self .row < self .total_rows - 1 and not grid [self .row + 1 ][ 78self .col ].is_barrier ():# check if you can move down 79self .neighbors .append (grid [self .row + 1 ][self .col ]) 80 81if self .row > 0 and not grid [self .row - 1 ][self .col ].is_barrier ():# check if you can move up 82self .neighbors .append (grid [self .row - 1 ][self .col ]) 83 84if self .col < self .total_rows - 1 and not grid [self .row ][ 85self .col + 1 ].is_barrier ():# check if you can move right 86self .neighbors .append (grid [self .row ][self .col + 1 ]) 87 88if self .col > 0 and not grid [self .row ][self .col - 1 ].is_barrier ():# check if you can move left 89self .neighbors .append (grid [self .row ][self .col - 1 ]) 90 91def __lt__ (self ,other ):# lt means less than, this is how we will handle comparing two spot objects 92return False 93 94 95def h (p1 ,p2 ):# formula: manhattan distance where its like a L sum of the x and y distance 96x1 ,y1 = p1 97x2 ,y2 = p2 98return abs (x1 - x2 )+ abs (y1 - y2 ) 99 100 101def reconstruct_path (came_from ,current ,draw ):# drawing the main path 102while current in came_from : 103current = came_from [current ] 104current .make_path () 105draw () 106 107 108def algorithm (draw ,grid ,start ,end ): 109count = 0 110open_set = PriorityQueue () 111open_set .put ((0 ,count ,start ))# add the start node to the set 112came_from = {}# what node did we come from 113g_score = {spot :float ('inf' )for row in grid for spot in row }# setting all starting g scores to infinite 114g_score [start ]= 0 # setting start node g score to 0 115f_score = {spot :float ('inf' )for row in grid for spot in row }# setting all starting f scores to infinite 116f_score [start ]= h (start .get_pos (),end .get_pos ())# since f= g + h and g[start] =0 so f=h 117 118open_set_hash = {start }# keeps track of all items in the queue and not in the queue 119 120while not open_set .empty (): 121for event in pygame .event .get (): 122if event .type == pygame .QUIT : 123pygame .quit () 124 125current = open_set .get ()[2 ]# get just the node 126open_set_hash .remove (current )# syncing with priority queue 127 128if current == end :# found the end; now make path 129reconstruct_path (came_from ,end ,draw ) 130end .make_end () 131return True 132 133for neighbor in current .neighbors : 134temp_g_score = g_score [current ]+ 1 135 136if temp_g_score < g_score [neighbor ]:# if we find a better path than before update this as the better path 137came_from [neighbor ]= current 138g_score [neighbor ]= temp_g_score 139f_score [neighbor ]= temp_g_score + h (neighbor .get_pos (),end .get_pos ())# f score of neighbor 140if neighbor not in open_set_hash : 141count += 1 142open_set .put ((f_score [neighbor ],count ,neighbor ))# adding optimal node to the open set 143open_set_hash .add (neighbor )# syncing with priority queue 144neighbor .make_open ()# make this green for open 145 146draw () 147 148if current != start : 149current .make_closed ()# if the node we just looked at make it red bc we have already considered it. 150return False # we did not find a path 151 152 153def make_grid (rows ,width ):# this will make 154grid = []# a 2d list [ [ [ [], [], [], ], [], [] ] 155gap = width // rows 156for i in range (rows ): 157grid .append ([]) 158for j in range (rows ): 159spot = Spot (i ,j ,gap ,rows )# this tells spot where to make each block 160grid [i ].append (spot )# adding each block into the current row 161return grid 162 163 164def draw_grid (win ,rows ,width ):# this will the draw the grid lines 165gap = width // rows 166for i in range (rows ): 167pygame .draw .line (win ,grey , (0 ,i * gap ), (width ,i * gap ))# horizontal lines drawing 168 169for i in range (rows ): 170pygame .draw .line (win ,grey , (i * gap ,0 ), (i * gap ,width ))# vertical lines drawing 171 172 173# def draw_borders(win, rows, width): 174# borders = [] 175# def create_spot(rows) 176# for i in range(rows): 177# current = Spot() 178 179 180def draw (win ,grid ,rows ,width ):# main draw function that will draw everything 181win .fill (white )# fills the entire screen with white 182 183# drawing all the cubes 184for row in grid : 185for spot in row : 186if spot .row == 0 or spot .col == 0 or spot .row == rows - 1 or spot .col == rows - 1 : 187spot .make_barrier () 188spot .draw (win )# draws a cube 189 190draw_grid (win ,rows ,width ) 191pygame .display .update ()# this tells pygame to make all the changes we made above and update the display 192 193 194def get_clicked_pos (pos ,rows ,width ):# figuring out which block the user clicks on 195gap = width // rows 196y ,x = pos 197row = y // gap 198col = x // gap 199return row ,col 200 201 202def main (win ,width ):# main loop; determines all of the checks we are doing 203rows = 50 204grid = make_grid (rows ,width ) 205 206start = None 207end = None 208 209run = True 210started = False 211 212while run : 213draw (win ,grid ,rows ,width ) 214for event in pygame .event .get ():# check what events are happening 215if event .type == pygame .QUIT :# if we quit pygame end the pygame window 216run = False 217 218if started :# if the algorithm is started we don't want the user changing anything; only thing allowed is quitting the window 219continue 220 221if pygame .mouse .get_pressed ()[0 ]:# if left clicked then place start, stop, and barriers 222pos = pygame .mouse .get_pos () 223row ,col = get_clicked_pos (pos ,rows ,width ) 224spot = grid [row ][col ] 225if not start and spot != end : 226start = spot 227start .make_start () 228elif not end and spot != start : 229end = spot 230end .make_end () 231elif spot != end and spot != start : 232spot .make_barrier () 233 234elif pygame .mouse .get_pressed ()[2 ]:# if right clicked then reset clicked block 235pos = pygame .mouse .get_pos () 236row ,col = get_clicked_pos (pos ,rows ,width ) 237spot = grid [row ][col ] 238spot .reset () 239if spot == start : 240start = None 241elif spot == end : 242end = None 243 244if event .type == pygame .KEYDOWN :# check if space is press so start the algo 245if event .key == pygame .K_SPACE and start and end : 246for row in grid : 247for spot in row : 248spot .update_neighbors (grid ) 249 250algorithm (lambda :draw (win ,grid ,rows ,width ),grid ,start , 251end )# once we start we are gonna start the algo 252 253if event .key == pygame .K_c : 254start = None 255end = None 256grid = make_grid (rows ,width ) 257 258pygame .quit () 259 260 261main (win ,width )