迷路探索 AI

迷路生成・探索アプリケーションについて

このアプリケーションの詳細、使用技術、アルゴリズムについて紹介します。

アプリケーション概要
技術スタックと概要

このアプリケーションは、シード値を指定して再現性のある迷路を自動生成し、 A*アルゴリズムを用いて最短経路を探索できるWebアプリケーションです。

使用技術

  • バックエンド: Python、FastAPI、Uvicorn
  • フロントエンド: React、Next.js、TypeScript、Tailwind CSS
  • UI コンポーネント: shadcn/ui
  • データ通信: RESTful API
迷路生成アルゴリズム
深さ優先探索（DFS）/ 穴掘り法

このアプリケーションでは、深さ優先探索（DFS）を応用した「穴掘り法」と呼ばれる アルゴリズムを用いて迷路を生成しています。

アルゴリズムの流れ:

  1. 全てのセルが壁で埋められた迷路グリッドを初期化
  2. スタート地点をランダムに選択
  3. 現在のセルから未訪問の隣接セルをランダムに選び、間の壁を壊す
  4. 新しいセルに移動し、手順3を繰り返す
  5. 行き止まりの場合は一つ前のセルに戻る（バックトラック）
  6. 全てのセルを訪問するまで繰り返す
経路探索アルゴリズム
A*アルゴリズム

迷路の最短経路探索には、ヒューリスティック探索アルゴリズムである A*（エースター）アルゴリズムを使用しています。

A*アルゴリズムの特徴:

  • ゴールまでの推定コストを考慮した効率的な経路探索
  • f(n) = g(n) + h(n) の評価関数に基づいて探索順序を決定
  • g(n): スタートからノードnまでのコスト（実際の距離）
  • h(n): ノードnからゴールまでの推定コスト（ヒューリスティック）
  • このアプリケーションではマンハッタン距離をヒューリスティックとして使用
モダンUI/UXの特徴
優れたユーザー体験

このアプリケーションでは、最新のフロントエンド技術を活用して 優れたユーザー体験を提供しています。

UI/UX上の工夫

  • レスポンシブデザイン: 様々な画面サイズに対応
  • ダークモード対応: 明暗両方のテーマに対応
  • アクセシビリティ: キーボード操作やスクリーンリーダー対応
  • 直感的な操作: シンプルで分かりやすいインターフェース
  • リアルタイムフィードバック: 操作に対する即時反応
  • 視覚的エンハンスメント: ズーム、回転、カラーカスタマイズなどの機能