I have built an A* Pathfinding algorithm that finds the best route from Point A to Point B, there is a timer that starts and ends post execute of the algorithm and the path is draw, this is parsed to a global variable. so it is accessable when i run the alogrithm more than once (to gain an average time).
the global variable gets added to a list, except when i run the algorithm 5 times, only 4 values get added (I can see 5 times being recorded as the algorithm prints the time after completion). when displaying the list it always misses the first time, and only has times 2,3,4,5 if i run the algorithm 5 times. here is main.py
import astar
import pygame
def main():
timing_list = []
WIDTH = 800
WIN = pygame.display.set_mode((WIDTH, WIDTH))
for x in range(0, 4):
astar.main(WIN, WIDTH)
timing_list.insert(x, astar.full_time)
print(timing_list)
if __name__ == "__main__":
main()
and
astar.py
from queue import PriorityQueue
from random import randint
import pygame
from timing import Timing
WIDTH = 800
WIN = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("A* Path Finding Algorithm")
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)
global full_time
class Spot:
def __init__(self, row, col, width, total_rows):
self.row = row
self.col = col
self.x = row * width
self.y = col * width
self.color = WHITE
self.neighbors = []
self.width = width
self.total_rows = total_rows
def get_pos(self):
return self.row, self.col
def is_closed(self):
return self.color == RED
def is_open(self):
return self.color == GREEN
def is_barrier(self):
return self.color == BLACK
def is_start(self):
return self.color == ORANGE
def is_end(self):
return self.color == TURQUOISE
def reset(self):
self.color = WHITE
def make_start(self):
self.color = ORANGE
def make_closed(self):
self.color = RED
def make_open(self):
self.color = GREEN
def make_barrier(self):
self.color = BLACK
def make_end(self):
self.color = TURQUOISE
def make_path(self):
self.color = PURPLE
def draw(self, win):
pygame.draw.rect(win, self.color, (self.x, self.y, self.width, self.width))
def update_neighbors(self, grid):
self.neighbors = []
if self.row < self.total_rows - 1 and not grid[self.row 1][self.col].is_barrier(): # DOWN
self.neighbors.append(grid[self.row 1][self.col])
if self.row > 0 and not grid[self.row - 1][self.col].is_barrier(): # UP
self.neighbors.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.neighbors.append(grid[self.row][self.col 1])
if self.col > 0 and not grid[self.row][self.col - 1].is_barrier(): # LEFT
self.neighbors.append(grid[self.row][self.col - 1])
def __lt__(self, other):
return False
def generate_num(x, y):
return randint(x, y)
def h(p1, p2):
x1, y1 = p1
x2, y2 = p2
return abs(x1 - x2) abs(y1 - y2)
def reconstruct_path(came_from, current, draw):
while current in came_from:
current = came_from[current]
current.make_path()
draw()
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] = h(start.get_pos(), end.get_pos())
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:
reconstruct_path(came_from, end, draw)
end.make_end()
return True
for neighbor in current.neighbors:
temp_g_score = g_score[current] 1
if temp_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = temp_g_score
f_score[neighbor] = temp_g_score h(neighbor.get_pos(), end.get_pos())
if neighbor not in open_set_hash:
count = 1
open_set.put((f_score[neighbor], count, neighbor))
open_set_hash.add(neighbor)
neighbor.make_open()
draw()
if current != start:
current.make_closed()
return False
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
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))
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()
def get_clicked_pos(pos, rows, width):
gap = width // rows
y, x = pos
row = y // gap
col = x // gap
return row, col
def main(win, width):
rows = 50
grid = make_grid(rows, width)
start = None
end = None
t = Timing()
run = True
setup_config = True
while run:
draw(win, grid, rows, width)
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
setup_config = False
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE:
run = False
setup_config = False
while setup_config:
for x in range(0, 800):
row_pos = generate_num(0, rows - 1)
col_pos = generate_num(0, rows - 1)
spot = grid[row_pos][col_pos]
if not start and spot != end:
start = spot
start.make_start()
elif not end and spot != start:
end = spot
end.make_end()
elif spot != end and spot != start:
spot.make_barrier()
t.start()
for row in grid:
for spot in row:
spot.update_neighbors(grid)
algorithm(lambda: draw(win, grid, rows, width), grid, start, end)
global full_time
full_time = t.stop()
setup_config = False
run = False
pygame.QUIT
main(WIN, WIDTH)
and timing.py my timer class
import time
class TimerError(Exception):
"""A custom exception used to report errors in use of Timer class"""
class Timing:
def __init__(self):
self._start_time = None
def start(self):
"""Start a new timer"""
if self._start_time is not None:
raise TimerError(f"Timer is running. Use .stop() to stop it")
self._start_time = time.perf_counter()
def stop(self):
"""Stop the timer, and report the elapsed time"""
if self._start_time is None:
raise TimerError(f"Timer is not running. Use .start() to start it")
elapsed_time = time.perf_counter() - self._start_time
self._start_time = None
print(f"Elapsed time: {elapsed_time:0.4f} seconds")
return elapsed_time
CodePudding user response：
EDIT:
the misterious 5th print is coming from this line, of course
full_time = t.stop()
With 4 iteractions of your main loop, you reach at this line 5 times. That's the reason you have 5 prints.
You are very right on your comment, when you import astar with the command
import astar
on your main.py file, you are executing the main(WIN, WIDTH) that you have at the end of astar.py. Thus resulting in 5 prints.
>>> for i in range(0, 4):
... print(i)
...
0
1
2
3
>>>
Your main for loop iterates 4 times, each time inserting one element to your empty list. By the way, I would to it like this rather than the cumbersome insert.
list.append(astar.full_time) # append inserts at the end of the list
I am surprised that you have 5 of the output of the format
print(f"Elapsed time: {elapsed_time:0.4f} seconds")
By the way, I am also wondering why do you have these statements:
run = True
while run:
run = False
and a similar statement with a boolean named setup_config and a while. You could get yourself a cleaner code by suppressing this while, since it only executes once. Please, correct me if I am wrong or I am missing something from your context.
CodePudding user response：
Notice that you can also remove the ifs related to the pass commands.
def main(win, width):
rows = 50
grid = make_grid(rows, width)
start = None
end = None
t = Timing()
draw(win, grid, rows, width)
for event in pygame.event.get():
if event.type == pygame.QUIT:
pass
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE:
pass
for x in range(0, 800):
row_pos = generate_num(0, rows - 1)
col_pos = generate_num(0, rows - 1)
spot = grid[row_pos][col_pos]
if not start and spot != end:
start = spot
start.make_start()
elif not end and spot != start:
end = spot
end.make_end()
elif spot != end and spot != start:
spot.make_barrier()
t.start()
for row in grid:
for spot in row:
spot.update_neighbors(grid)
algorithm(lambda: draw(win, grid, rows, width), grid, start, end)
global full_time
full_time = t.stop()
pygame.QUIT
The extra print is mostly like coming from a surprising extra iteraction of this for loop
for event in pygame.event.get():
Check the value of event, by printing it and check if there's something unusual there.