collab/mm20

git clone https://git.julia.blue/collab/mm20

AmmarAdded Simulator for A*9fadb5c

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