経路探索APIとゲームAI

経路探索アルゴリズムA*をWeb APIとして公開し、さらにゲームAIの敵追跡に応用する方法を学びます。

🔥 Vibe プロンプト

「FastAPI経路探索サービスを作成：POST /pathfindでグリッド地図を受け取り、最短経路と探索ノード数を返す。」

構築するもの

A*アルゴリズムをFastAPIサービスとして公開し、フロントエンドアプリが経路探索できるようにします。

リクエスト形式

| フィールド | 型 | 説明 | |-----------|------|------| | grid | List[List[int]] | 0=通路, 1=障害物の二次元配列 | | start | Tuple[int, int] | スタート地点 (row, col) | | goal | Tuple[int, int] | ゴール地点 (row, col) |

レスポンス形式

| フィールド | 型 | 説明 | |-----------|------|------| | path | Optional[List[Tuple[int, int]]] | 最短経路の座標リスト（見つからない場合はnull） | | found | bool | 経路が見つかったかどうか | | nodes_explored | int | 探索中に調べたノード数 |

実装

from fastapi import FastAPI
from pydantic import BaseModel
from typing import List, Tuple, Optional

app = FastAPI(title="経路探索API", version="1.0.0")

class PathRequest(BaseModel):
    grid: List[List[int]]  # 0=通路, 1=障害物
    start: Tuple[int, int]
    goal: Tuple[int, int]

class PathResponse(BaseModel):
    path: Optional[List[Tuple[int, int]]]
    found: bool
    nodes_explored: int

@app.post("/pathfind", response_model=PathResponse)
def pathfind(req: PathRequest):
    """A*で最短経路を探索"""
    path, explored = astar_with_stats(req.grid, req.start, req.goal)
    return PathResponse(
        path=path,
        found=path is not None,
        nodes_explored=explored
    )

@app.get("/health")
def health():
    return {"status": "ok", "algorithm": "A*"}

if __name__ == "__main__":
    import uvicorn
    uvicorn.run(app, host="0.0.0.0", port=8000)

A*アルゴリズム本体

import heapq
from typing import List, Tuple, Optional

def astar_with_stats(grid: List[List[int]], start: Tuple[int, int], goal: Tuple[int, int]):
    """A*探索を行い、経路と探索ノード数を返す"""
    rows, cols = len(grid), len(grid[0])
    open_set = [(0, start)]
    came_from = {}
    g_score = {start: 0}
    explored = 0

    while open_set:
        _, current = heapq.heappop(open_set)
        explored += 1

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1], explored

        r, c = current
        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                neighbor = (nr, nc)
                tentative = g_score[current] + 1
                if neighbor not in g_score or tentative < g_score[neighbor]:
                    g_score[neighbor] = tentative
                    f_score = tentative + abs(nr - goal[0]) + abs(nc - goal[1])  # マンハッタン距離
                    heapq.heappush(open_set, (f_score, neighbor))
                    came_from[neighbor] = current

    return None, explored

テスト

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

# 応答:
# {"path": [[0,0],[0,1],[0,2],[1,2],[2,2]], "found": true, "nodes_explored": 7}

ゲームAI：敵追跡

A*をゲームの敵キャラクターの移動に応用します。プレイヤーの位置を目標として毎フレーム経路を再計算し、敵がプレイヤーを追跡します。

class Enemy:
    def __init__(self, x, y, speed=1):
        self.x, self.y = x, y
        self.speed = speed

    def update(self, grid, player_pos):
        """A*を使ってプレイヤーに向かって移動"""
        path = astar(grid, (self.x, self.y), player_pos)
        if path and len(path) > 1:
            next_pos = path[1]
            self.x, self.y = next_pos
            return True
        return False

enemies = [Enemy(5, 5), Enemy(3, 8), Enemy(9, 2)]
# ゲームループ内で毎フレーム:
# for enemy in enemies:
#     if enemy.update(grid, player_pos):
#         if (enemy.x, enemy.y) == (player.x, player.y):
#             game_over()

ゲームループ例（Pygame）

import pygame
import sys

# Pygameの初期化
pygame.init()
screen = pygame.display.set_mode((800, 600))
clock = pygame.time.Clock()

# グリッド設定
CELL = 40
grid = [[0]*20 for _ in range(15)]
# 障害物を配置
for i in range(5, 15):
    grid[7][i] = 1

player_pos = [0, 0]
enemy = Enemy(12, 7)

running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        if event.type == pygame.KEYDOWN:
            r, c = player_pos
            if event.key == pygame.K_UP and r > 0 and grid[r-1][c] == 0:
                r -= 1
            elif event.key == pygame.K_DOWN and r < 14 and grid[r+1][c] == 0:
                r += 1
            elif event.key == pygame.K_LEFT and c > 0 and grid[r][c-1] == 0:
                c -= 1
            elif event.key == pygame.K_RIGHT and c < 19 and grid[r][c+1] == 0:
                c += 1
            player_pos = [r, c]

    # 敵の移動
    enemy.update(grid, tuple(player_pos))

    # 描画
    screen.fill((255, 255, 255))
    for r in range(15):
        for c in range(20):
            color = (0, 0, 0) if grid[r][c] == 1 else (255, 255, 255)
            pygame.draw.rect(screen, color, (c*CELL, r*CELL, CELL, CELL), 1)
    # プレイヤー
    pygame.draw.circle(screen, (0, 0, 255),
                       (player_pos[1]*CELL+CELL//2, player_pos[0]*CELL+CELL//2), 15)
    # 敵
    pygame.draw.circle(screen, (255, 0, 0),
                       (enemy.y*CELL+CELL//2, enemy.x*CELL+CELL//2), 15)

    pygame.display.flip()
    clock.tick(10)

pygame.quit()
sys.exit()

🔥 Vibe プロンプト

「Pygameで敵がA*を使ってプレイヤーを追跡するゲームを作成。矢印キーで移動。探索過程を可視化。」

まとめ

| 項目 | 詳細 | |------|------| | API | FastAPIによるA*経路探索サービス | | ゲームAI | 毎フレームの敵移動制御 | | 性能 | 大規模マップではJPS+で高速化 | | 拡張 | 経路平滑化、群行動、予測追跡 |