Game Dev Lab — Day 4
Tower Defense + BFS Pathfinding
Tower Defense
# INSTRUCTOR — Game Dev Lab Day 4: Tower Defense + BFS Pathfinding
# -------------------------------------------------------
# TEACH: This is the most challenging project of the week.
# The key new concept is BFS (Breadth-First Search) — the algorithm enemies
# use to find the shortest path through the grid from start to end.
#
# BFS in plain English:
# Start at START. Look at all neighbors. Look at THEIR neighbors. Keep going
# outward (like ripples in water) until you reach END. The path you trace
# back is the shortest one. We store "where did I come from?" in a dict
# called 'came_from', then walk it backward to get the path.
#
# GRID SYSTEM:
# The map is a 2D grid of COLS x ROWS cells.
# Cells can be: 'open', 'wall' (tower), 'path', 'start', 'end'
# Enemies walk cell-by-cell along the computed BFS path.
# Clicking an open cell places a tower (wall), then BFS reruns.
# If BFS can't find a path, the tower placement is blocked.
#
# MILESTONE (show me when done):
# Grid is visible. Enemies walk from START to END following the BFS path.
# Click an open cell to place a tower. Enemies reroute around it.
# Towers near enemies shoot them (enemy disappears, score goes up).
#
# EXTENSION challenges:
# - Add wave system: every 10 enemies → next wave, enemies faster
# - Add multiple tower types (slow tower, area tower)
# - Save/load the map layout to a file
import pygame
import sys
import random
from collections import deque
pygame.init()
COLS, ROWS = 20, 15
CELL = 40
WIDTH = COLS * CELL
HEIGHT = ROWS * CELL + 50 # extra bar for HUD
screen = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption("Tower Defense — Day 4")
clock = pygame.time.Clock()
font = pygame.font.SysFont("courier", 18, bold=True)
# ── Colors ────────────────────────────────────────────────────────────────────
BG_DARK = (20, 28, 40)
OPEN_CLR = (35, 50, 70)
WALL_CLR = (60, 100, 60)
PATH_CLR = (50, 80, 120)
START_CLR = (50, 180, 80)
END_CLR = (200, 60, 60)
ENEMY_CLR = (220, 180, 30)
BULLET_CLR= (255, 255, 100)
HUD_CLR = (180, 220, 255)
GRID_CLR = (30, 40, 55)
# ── Grid setup ────────────────────────────────────────────────────────────────
# Two entry points on the left, one shared target on the right.
# TEACH: two BFS calls — one per entry point. A tower is only allowed if
# BOTH paths still exist after placement. That's what makes it hard:
# you can't just wall off one lane; you have to cover both.
START_A = (0, ROWS // 4) # upper entry
START_B = (0, 3 * ROWS // 4) # lower entry
END = (COLS - 1, ROWS // 2)
grid = [['open'] * ROWS for _ in range(COLS)]
grid[START_A[0]][START_A[1]] = 'start'
grid[START_B[0]][START_B[1]] = 'start'
grid[END[0]][END[1]] = 'end'
# ── BFS ───────────────────────────────────────────────────────────────────────
def bfs(start):
"""Return list of (col, row) from start to END, or None if blocked."""
queue = deque([start])
came_from = {start: None}
while queue:
cur = queue.popleft()
if cur == END:
break
cx, cy = cur
for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
nx, ny = cx + dx, cy + dy
nxt = (nx, ny)
if (0 <= nx < COLS and 0 <= ny < ROWS
and nxt not in came_from
and grid[nx][ny] != 'wall'):
queue.append(nxt)
came_from[nxt] = cur
if END not in came_from:
return None # path is blocked
path = []
cur = END
while cur is not None:
path.append(cur)
cur = came_from[cur]
path.reverse()
return path
# ── Mark path cells in grid (visual only) ────────────────────────────────────
def mark_paths(path_a, path_b):
for c in range(COLS):
for r in range(ROWS):
if grid[c][r] == 'path':
grid[c][r] = 'open'
for path in (path_a, path_b):
if path:
for (c, r) in path[1:-1]:
grid[c][r] = 'path'
def reroute_enemy(e, new_path):
"""Snap a moving enemy to the closest point on the new path."""
best_idx, best_dist = 0, float('inf')
for i, (pc, pr) in enumerate(new_path):
px = pc * CELL + CELL // 2
py = pr * CELL + CELL // 2
d = ((e.x - px)**2 + (e.y - py)**2) ** 0.5
if d < best_dist:
best_dist = d
best_idx = i
e.path = new_path
e.path_idx = best_idx
path_a = bfs(START_A)
path_b = bfs(START_B)
mark_paths(path_a, path_b)
# ── Enemy ─────────────────────────────────────────────────────────────────────
class Enemy:
RADIUS = 12
SPEED = 1.5 # pixels per frame
def __init__(self, path, start):
self.path_idx = 0
self.path = path
self.start = start # which entry point — used for rerouting
col, row = path[0]
self.x = col * CELL + CELL // 2
self.y = row * CELL + CELL // 2
self.alive = True
self.reached_end = False
def update(self):
if self.path_idx >= len(self.path) - 1:
self.alive = False
self.reached_end = True # only this costs a life
return
col, row = self.path[self.path_idx + 1]
tx = col * CELL + CELL // 2
ty = row * CELL + CELL // 2
dx = tx - self.x
dy = ty - self.y
dist = (dx**2 + dy**2) ** 0.5
if dist < self.SPEED:
self.x = tx
self.y = ty
self.path_idx += 1
else:
self.x += dx / dist * self.SPEED
self.y += dy / dist * self.SPEED
def draw(self, surface):
pygame.draw.circle(surface, ENEMY_CLR, (int(self.x), int(self.y)), self.RADIUS)
# health bar placeholder
pygame.draw.circle(surface, (0, 0, 0), (int(self.x), int(self.y)), self.RADIUS, 2)
def rect(self):
return pygame.Rect(self.x - self.RADIUS, self.y - self.RADIUS,
self.RADIUS * 2, self.RADIUS * 2)
# ── Tower ─────────────────────────────────────────────────────────────────────
class Tower:
RANGE = 3 * CELL # pixels
RELOAD = 45 # frames between shots
def __init__(self, col, row):
self.col = col
self.row = row
self.cx = col * CELL + CELL // 2
self.cy = row * CELL + CELL // 2
self.countdown = 0
def update(self, enemies, bullets):
if self.countdown > 0:
self.countdown -= 1
return
for e in enemies:
dx = e.x - self.cx
dy = e.y - self.cy
if (dx**2 + dy**2) ** 0.5 < self.RANGE:
bullets.append(TowerBullet(self.cx, self.cy, e))
self.countdown = self.RELOAD
break
def draw(self, surface):
r = pygame.Rect(self.col * CELL + 4, self.row * CELL + 4, CELL - 8, CELL - 8)
pygame.draw.rect(surface, WALL_CLR, r, border_radius=4)
pygame.draw.rect(surface, (80, 160, 80), r, 2, border_radius=4)
# ── Tower bullet ──────────────────────────────────────────────────────────────
class TowerBullet:
SPEED = 4
def __init__(self, x, y, target):
self.x = float(x)
self.y = float(y)
self.target = target
self.active = True
def update(self):
if not self.target.alive:
self.active = False
return
dx = self.target.x - self.x
dy = self.target.y - self.y
dist = (dx**2 + dy**2) ** 0.5
if dist < self.SPEED:
self.target.alive = False
self.active = False
else:
self.x += dx / dist * self.SPEED
self.y += dy / dist * self.SPEED
def draw(self, surface):
pygame.draw.circle(surface, BULLET_CLR, (int(self.x), int(self.y)), 5)
# ── Drawing helpers ───────────────────────────────────────────────────────────
def draw_grid():
for col in range(COLS):
for row in range(ROWS):
x = col * CELL
y = row * CELL
cell_type = grid[col][row]
if cell_type == 'start':
color = START_CLR
elif cell_type == 'end':
color = END_CLR
elif cell_type == 'wall':
color = (20, 20, 20)
elif cell_type == 'path':
color = PATH_CLR
else:
color = OPEN_CLR
pygame.draw.rect(screen, color, (x, y, CELL, CELL))
pygame.draw.rect(screen, GRID_CLR, (x, y, CELL, CELL), 1)
def draw_hud(score, lives):
pygame.draw.rect(screen, (15, 20, 30), (0, ROWS * CELL, WIDTH, 50))
hud = font.render(f"Score: {score} Lives: {lives} Coins: {coins} (tower costs 5)", True, HUD_CLR)
screen.blit(hud, (10, ROWS * CELL + 14))
# ── Game state ────────────────────────────────────────────────────────────────
towers = []
enemies = []
bullets = []
score = 0
lives = 10
coins = 10 # earn 2 per kill, spend 5 to place a tower
SPAWN_EVENT = pygame.USEREVENT + 1
pygame.time.set_timer(SPAWN_EVENT, 1800)
# ── Main loop ─────────────────────────────────────────────────────────────────
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit(); sys.exit()
if event.type == pygame.MOUSEBUTTONDOWN and event.button == 1:
mx, my = event.pos
col = mx // CELL
row = my // CELL
if 0 <= col < COLS and 0 <= row < ROWS:
if (grid[col][row] == 'open' or grid[col][row] == 'path') and coins >= 5:
# Try placing tower — BOTH paths must still exist after placement
grid[col][row] = 'wall'
new_a = bfs(START_A)
new_b = bfs(START_B)
if new_a is None or new_b is None:
grid[col][row] = 'open' # would block a lane — undo
else:
coins -= 5
towers.append(Tower(col, row))
path_a, path_b = new_a, new_b
mark_paths(path_a, path_b)
# Reroute all live enemies onto their updated path
for e in enemies:
new_path = path_a if e.start == START_A else path_b
reroute_enemy(e, new_path[:])
if event.type == SPAWN_EVENT and lives > 0:
# Alternate spawn between the two entry points
chosen = random.choice([(START_A, path_a), (START_B, path_b)])
start, p = chosen
if p:
enemies.append(Enemy(p[:], start))
# Update
for t in towers:
t.update(enemies, bullets)
for e in enemies[:]:
e.update()
if not e.alive:
enemies.remove(e)
if e.reached_end:
lives -= 1 # only penalize if enemy got through
for b in bullets[:]:
b.update()
if not b.active:
bullets.remove(b)
score += 1
coins += 2 # earn coins for killing enemies
# Draw
screen.fill(BG_DARK)
draw_grid()
for t in towers:
t.draw(screen)
for e in enemies:
e.draw(screen)
for b in bullets:
b.draw(screen)
draw_hud(score, lives)
if lives <= 0:
msg = font.render("GAME OVER", True, (220, 60, 60))
r = msg.get_rect(center=(WIDTH // 2, ROWS * CELL // 2))
screen.blit(msg, r)
pygame.display.flip()
clock.tick(60)