summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.idea/misc.xml2
-rw-r--r--path_finding/astar.py247
-rw-r--r--path_finding/pygame_spot.py105
-rw-r--r--path_finding/tutorials/01_init_grid_world.py47
-rw-r--r--path_finding/备课/01_init_grid_world.py41
5 files changed, 441 insertions, 1 deletions
diff --git a/.idea/misc.xml b/.idea/misc.xml
index 676412f..7a5c067 100644
--- a/.idea/misc.xml
+++ b/.idea/misc.xml
@@ -1,6 +1,6 @@
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
- <component name="ProjectRootManager" version="2" project-jdk-name="Python 3.7 (py3.7)" project-jdk-type="Python SDK" />
+ <component name="ProjectRootManager" version="2" project-jdk-name="Python 3.6" project-jdk-type="Python SDK" />
<component name="PyCharmProfessionalAdvertiser">
<option name="shown" value="true" />
</component>
diff --git a/path_finding/astar.py b/path_finding/astar.py
new file mode 100644
index 0000000..f87f706
--- /dev/null
+++ b/path_finding/astar.py
@@ -0,0 +1,247 @@
+import pygame
+import math
+from queue import PriorityQueue
+
+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)
+
+
+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 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
+
+ run = True
+ while run:
+ draw(win, grid, ROWS, width)
+ for event in pygame.event.get():
+ if event.type == pygame.QUIT:
+ run = False
+
+ if pygame.mouse.get_pressed()[0]: # LEFT
+ pos = pygame.mouse.get_pos()
+ row, col = get_clicked_pos(pos, ROWS, width)
+ spot = grid[row][col]
+ 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()
+
+ elif pygame.mouse.get_pressed()[2]: # RIGHT
+ pos = pygame.mouse.get_pos()
+ row, col = get_clicked_pos(pos, ROWS, width)
+ spot = grid[row][col]
+ spot.reset()
+ if spot == start:
+ start = None
+ elif spot == end:
+ end = None
+
+ if event.type == pygame.KEYDOWN:
+ if event.key == pygame.K_SPACE and start and end:
+ for row in grid:
+ for spot in row:
+ spot.update_neighbors(grid)
+
+ algorithm(lambda: draw(win, grid, ROWS, width), grid, start, end)
+
+ if event.key == pygame.K_c:
+ start = None
+ end = None
+ grid = make_grid(ROWS, width)
+
+ pygame.quit()
+
+
+main(WIN, WIDTH)
diff --git a/path_finding/pygame_spot.py b/path_finding/pygame_spot.py
new file mode 100644
index 0000000..4017704
--- /dev/null
+++ b/path_finding/pygame_spot.py
@@ -0,0 +1,105 @@
+
+import pygame
+from pygame.locals import *
+height = 800
+width = height
+win = pygame.display.set_mode((width, width))
+
+pygame.display.set_caption("grid world")
+
+rows = 50
+cols = rows
+
+spot_width = height//rows
+spot_height = spot_width
+
+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)
+
+
+class Spot:
+ def __init__(self, r, c):
+ self.r = r
+ self.c = c
+ self.x = c * spot_width
+ self.y = r * spot_height
+ self.color = WHITE
+
+
+ def make_start(self):
+ self.color = ORANGE
+
+ def make_end(self):
+ self.color = TURQUOISE
+
+ def draw(self, win):
+ pygame.draw.rect(win, self.color, (self.x, self.y, spot_width, spot_height))
+
+
+def make_grid(win):
+ grid_world = []
+ for i in range(rows):
+ grid_world.append([])
+ for j in range(rows):
+ spot = Spot(i, j)
+ grid_world[i].append(spot)
+ return grid_world
+
+
+def draw_grid(win):
+ gap = width//rows
+ for i in range(rows):
+ pygame.draw.line(win, GREY, (0, i*gap), (width, i*gap))
+ for j in range(cols):
+ pygame.draw.line(win, GREY, (j*gap, 0), (j*gap, height))
+
+
+def draw(win, grid_world):
+ win.fill(WHITE)
+
+ for i in range(rows):
+ for j in range(cols):
+ grid_world[i][j].draw(win)
+ draw_grid(win)
+ pygame.display.update()
+
+
+def map_clicked_pos(pos):
+ x, y = pos
+ r = y//spot_width
+ c = x//spot_width
+ return r, c
+
+if __name__ == '__main__':
+ run = True
+ start, end = None, None
+ grid_world = make_grid(win)
+ while run:
+ draw(win, grid_world)
+ for event in pygame.event.get():
+ if event.type == pygame.QUIT:
+ run = False
+ if event.type == KEYDOWN:
+ if event.key == K_ESCAPE:
+ run = False
+ left, center, right = pygame.mouse.get_pressed()
+ if left:
+ pos = pygame.mouse.get_pos()
+ r, c = map_clicked_pos(pos)
+ print(r, c, 'clicked')
+ spot = grid_world[r][c]
+ if not start:
+ start = spot
+ start.make_start()
+ elif not end:
+ end = spot
+ end.make_end()
+
diff --git a/path_finding/tutorials/01_init_grid_world.py b/path_finding/tutorials/01_init_grid_world.py
new file mode 100644
index 0000000..4ac4324
--- /dev/null
+++ b/path_finding/tutorials/01_init_grid_world.py
@@ -0,0 +1,47 @@
+import pygame
+from pygame.locals import *
+
+WIDTH = 800
+HEIGHT = WIDTH
+
+COLS = 50
+ROWS = COLS
+
+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)
+
+# spot
+spot_width = WIDTH//COLS
+spot_height = HEIGHT // ROWS
+
+win = pygame.display.set_mode((WIDTH, HEIGHT))
+pygame.display.set_caption('grid world')
+
+
+def draw():
+ win.fill(WHITE)
+ for i in range(ROWS):
+ pygame.draw.line(win, GREY, (0, i*spot_height), (WIDTH, i*spot_height))
+ for j in range(COLS):
+ pygame.draw.line(win, GREY, (j*spot_width, 0), (j * spot_width, HEIGHT))
+ pygame.display.update()
+
+
+if __name__ == '__main__':
+ run = True
+ while run:
+ draw()
+ for event in pygame.event.get():
+ if event.type == pygame.QUIT:
+ run = False
+ if event.type == KEYDOWN:
+ if event.key == K_ESCAPE:
+ run = False
diff --git a/path_finding/备课/01_init_grid_world.py b/path_finding/备课/01_init_grid_world.py
new file mode 100644
index 0000000..698f47d
--- /dev/null
+++ b/path_finding/备课/01_init_grid_world.py
@@ -0,0 +1,41 @@
+import pygame
+
+WIDTH = 800
+HEIGHT = WIDTH
+
+COLS = 50
+ROWS = COLS
+
+SPOT_WIDTH = WIDTH//COLS
+SPOT_HEIGHT = HEIGHT//ROWS
+
+
+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)
+
+
+win = pygame.display.set_mode((WIDTH, HEIGHT))
+pygame.display.set_caption('grid world')
+
+def draw():
+ win.fill(WHITE)
+ for i in range(COLS):
+ pygame.draw.line(win, GREY, (i*SPOT_WIDTH, 0), (i*SPOT_WIDTH, HEIGHT))
+ for j in range(ROWS):
+ pygame.draw.line(win, GREY, (0, j*SPOT_HEIGHT), (WIDTH, j*SPOT_HEIGHT))
+ pygame.display.update()
+
+
+if __name__ == '__main__':
+ run = True
+
+ while run:
+ draw()
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-06 07:52:34 +0000