-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.py
55 lines (42 loc) · 1.55 KB
/
dijkstra.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import pygame
import asyncio
from queue import PriorityQueue
async def reconstruct_path(came_from, current, do_draw):
while current in came_from:
current = came_from[current]
current.make_path()
do_draw()
await asyncio.sleep(0)
async def dijkstra(do_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
open_set_hash = {start}
while not open_set.empty():
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
current = open_set.get()[2]
open_set_hash.remove(current)
if current == end:
await reconstruct_path(came_from, end, do_draw)
end.make_end()
start.make_start()
return True
for neighbour in current.neighbours:
if g_score[current] + 1 < g_score[neighbour]:
came_from[neighbour] = current
g_score[neighbour] = g_score[current] + 1
if neighbour not in open_set_hash:
count = count + 1
open_set.put((g_score[neighbour], count, neighbour))
open_set_hash.add(neighbour)
neighbour.make_open()
do_draw()
await asyncio.sleep(0)
if current != start:
current.make_closed()
return False