---

title: "Project: Map Navigation API & Game AI" description: "Use FastAPI to build a pathfinding API, and implement enemy tracking AI with obstacle avoidance in games." order: 5

Project: Map Navigation API & Game AI

In this chapter, we apply A* pathfinding to two real-world scenarios:

1. Map Navigation API - wrapped as a RESTful API with FastAPI
2. Game AI - enemy auto-tracking with pathfinding

Project 1: Pathfinding API

Building the FastAPI Service

from fastapi import FastAPI, HTTPException
from pydantic import BaseModel
import heapq
from typing import List, Tuple

app = FastAPI(title="Pathfinding API", version="1.0.0")

def astar_search(grid, start, goal):
    """A* search with 8-direction movement"""
    height, width = len(grid), len(grid[0])

    def heuristic(a, b):
        return max(abs(a[0]-b[0]), abs(a[1]-b[1]))

    directions = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1)]
    pq = [(0, 0, start[0], start[1])]
    g_score = {start: 0}
    came_from = {start: None}
    explored_count = 0

    while pq:
        f, g, x, y = heapq.heappop(pq)
        current = (x, y)
        explored_count += 1

        if current == goal:
            path = []
            while current is not None:
                path.append(current)
                current = came_from[current]
            return list(reversed(path)), explored_count, len(path)

        for dx, dy in directions:
            nx, ny = x+dx, y+dy
            neighbor = (nx, ny)
            if 0 <= nx < width and 0 <= ny < height and grid[ny][nx] == 0:
                move_cost = 1.414 if dx != 0 and dy != 0 else 1
                tentative_g = g + move_cost
                if tentative_g < g_score.get(neighbor, float('inf')):
                    g_score[neighbor] = tentative_g
                    heapq.heappush(pq, (tentative_g+heuristic(neighbor,goal), tentative_g, nx, ny))
                    came_from[neighbor] = current
    return None, explored_count, 0

class PathRequest(BaseModel):
    grid: List[List[int]]
    start: Tuple[int, int]
    goal: Tuple[int, int]

class PathResponse(BaseModel):
    path: List[Tuple[int, int]]
    explored_count: int
    path_length: float
    success: bool

@app.post("/pathfind", response_model=PathResponse)
def pathfind(req: PathRequest):
    if not req.grid or not req.grid[0]:
        raise HTTPException(400, "Empty grid")
    h, w = len(req.grid), len(req.grid[0])
    if not (0 <= req.start[0] < w and 0 <= req.start[1] < h):
        raise HTTPException(400, "Start out of bounds")
    if not (0 <= req.goal[0] < w and 0 <= req.goal[1] < h):
        raise HTTPException(400, "Goal out of bounds")
    if req.grid[req.start[1]][req.start[0]] == 1:
        raise HTTPException(400, "Start is obstacle")
    path, explored, length = astar_search(req.grid, req.start, req.goal)
    return PathResponse(path=path or [], explored_count=explored, path_length=length, success=path is not None)

Testing the API

python pathfinding_api.py
curl -X POST "http://localhost:8000/pathfind" \
  -H "Content-Type: application/json" \
  -d '{"grid":[[0,0,0,1,0],[0,1,0,1,0],[0,1,0,0,0],[0,0,0,1,0],[1,0,0,0,0]],"start":[0,0],"goal":[4,4]}'

Project 2: Game AI Enemy Tracking

import pygame, sys, random, heapq

WIDTH, HEIGHT = 800, 600
GRID = 40
COLS, ROWS = WIDTH//GRID, HEIGHT//GRID

WHITE, BLACK, GREEN, RED, GRAY = (255,)*3, (0,)*3, (0,200,0), (200,0,0), (100,)*3

def heuristic(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

def astar_move(grid, start, goal):
    if start == goal: return start
    pq = [(0, start[0], start[1])]
    g_score, came_from = {start: 0}, {start: None}
    while pq:
        _, x, y = heapq.heappop(pq)
        current = (x, y)
        if current == goal:
            while came_from[current] != start:
                current = came_from[current]
            return current
        for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx, ny = x+dx, y+dy
            neighbor = (nx, ny)
            if 0 <= nx < COLS and 0 <= ny < ROWS and grid[ny][nx] == 0:
                tg = g_score[current] + 1
                if tg < g_score.get(neighbor, float('inf')):
                    g_score[neighbor] = tg
                    heapq.heappush(pq, (tg+heuristic(neighbor,goal), nx, ny))
                    came_from[neighbor] = current
    return start

def run_game():
    pygame.init()
    screen = pygame.display.set_mode((WIDTH, HEIGHT))
    pygame.display.set_caption("A* Game AI - Enemy Chases Player")
    clock = pygame.time.Clock()
    grid = [[0]*COLS for _ in range(ROWS)]
    random.seed(123)
    for _ in range(int(COLS*ROWS*0.15)):
        x, y = random.randint(0,COLS-1), random.randint(0,ROWS-1)
        if (x,y) not in [(0,0), (COLS-1,ROWS-1)]: grid[y][x] = 1
    player, enemy = [0,0], [COLS-1,ROWS-1]
    font = pygame.font.Font(None, 24)
    running = True
    while running:
        for event in pygame.event.get():
            if event.type == pygame.QUIT: running = False
            elif event.type == pygame.KEYDOWN:
                if event.key == pygame.K_UP and player[1]>0 and grid[player[1]-1][player[0]]==0: player[1]-=1
                elif event.key == pygame.K_DOWN and player[1]<ROWS-1 and grid[player[1]+1][player[0]]==0: player[1]+=1
                elif event.key == pygame.K_LEFT and player[0]>0 and grid[player[1]][player[0]-1]==0: player[0]-=1
                elif event.key == pygame.K_RIGHT and player[0]<COLS-1 and grid[player[1]][player[0]+1]==0: player[0]+=1
        next_move = astar_move(grid, tuple(enemy), tuple(player))
        enemy = list(next_move)
        screen.fill(BLACK)
        for y in range(ROWS):
            for x in range(COLS):
                rect = pygame.Rect(x*GRID, y*GRID, GRID-1, GRID-1)
                pygame.draw.rect(screen, GRAY if grid[y][x] else (30,30,40), rect, 0 if grid[y][x] else 1)
        pygame.draw.rect(screen, GREEN, (player[0]*GRID, player[1]*GRID, GRID-1, GRID-1))
        pygame.draw.rect(screen, RED, (enemy[0]*GRID, enemy[1]*GRID, GRID-1, GRID-1))
        screen.blit(font.render(f"Player: {player} Enemy: {enemy}", True, WHITE), (10,10))
        if player == enemy:
            screen.blit(font.render("Game Over! Enemy caught you!", True, RED), (WIDTH//2-150, HEIGHT//2))
        pygame.display.flip()
        clock.tick(5)
    pygame.quit()
    sys.exit()

if __name__ == "__main__":
    run_game()

Summary

1. FastAPI pathfinding API: wrapped A* as a RESTful service
2. Input validation: ensures grid, start, goal correctness
3. Game AI enemy tracking: A*-based auto-navigation
4. Pygame implementation: main loop, event handling, drawing
5. 8-direction movement for more natural paths

Next Chapter: Large-Scale Optimization

The next chapter covers JPS, hierarchical pathfinding, and dynamic obstacle handling for massive maps.

---

Commercial Value of Graph Search

| Domain | Application | Algorithm | |--------|-------------|-----------| | Delivery | Optimize delivery routes | A* + TSP heuristic | | Game Dev | NPC auto-pathfinding | A* + NavMesh | | Logistics | Truck route planning | Dijkstra + time windows | | Social | Friend recommendations | BFS | | Web Crawling | Crawl all pages | DFS | | Circuit Design | Chip routing | A* (multi-constraint) |

Course Summary

This graph search course covered: NetworkX, BFS/DFS, Dijkstra, A*, and pathfinding API. These algorithms power Google Maps, Uber, and game NPC behavior.