# カラー・コネクト・ループ 解法パス生成アルゴリズム（確定版仕様書）

## 1. 基本方針
開始点から「パスA」と「パスB」の2本のパスを同時に伸ばし、最終的に結合して1つの大きなループ（正解パス）を作成するアルゴリズム。

生成プロセスを **「ランダムウォークフェーズ」** と **「端点接続フェーズ」** に明確に分離することで、無限ループ（フリーズ）や開始点消失バグを完全に防止する。
また、極端に小さなループで終わってしまう「無限シュリンク」問題に対しては、マス数の厳密な制約（盤面の30%以上など）は設けず、**「直進率」**や**「最低直進数」**のパラメーター調整によって自然に緩和させるアプローチをとる。

---

## 2. アルゴリズムのステップ詳細

### ステップ1：初期化と開始方向の決定
1. 盤面内のランダムなマスを「開始点」として決定する。
2. 開始点から、パスAとパスBの初期進行方向を以下のルールで決定する。
   - まず、開始点から「一番近い壁（盤面の端）」の方角を基準とする。
   - **パスAの進行方向**：その壁に向かった状態から見て **右手（上から見下ろして時計回り）** の方向。
   - **パスBの進行方向**：その壁に向かった状態から見て **左手（上から見下ろして反時計回り）** の方向。

### ステップ2：ランダムウォークフェーズ（パスの伸長）
パスAとパスBを1マスずつ交互に進める。このフェーズではリワインド（後退・トリミング）処理は一切行わず、前進または停止のみを行う。

- **壁にぶつかった場合のルール**：
  行き止まりを減らし、盤面を大きく回るようにするため、壁際での旋回方向を固定する。
  - パスA：**時計回り** に進行方向を変える。
  - パスB：**反時計回り** に進行方向を変える。
- **自身の過去パスや、相手パスに衝突しそうな場合のルール**：
  - 目の前が既存パス（自分または相手）で塞がっている場合、進行可能な別の方向（空きマス）を探して進路を変える。
  - もし進行可能な方向が一つもない（三方が塞がった完全な行き止まり）場合、**そのパスは現在位置で「停止」**する。
- **フェーズの終了条件**：
  - 一方のパスが停止しても、もう一方のパスが動ける場合は、停止するまで進め続ける。
  - **「パスAとパスBの両方が停止状態」**になった段階で、ランダムウォークフェーズを終了し、次のフェーズへ移行する。

### ステップ3：端点接続フェーズ（ループの完成）
両者が停止した後、パスAの先端（端点）を動かしてパスBの端点へと安全に繋ぎ合わせ、1つの閉じたループを完成させる。このフェーズから初めてリワインド・トリミング処理の実行が許可される。

1. **パスAの前進探索ルール**：
   - パスBの端点がある方向を目指してパスAをさらに伸ばしていく。
2. **自身の過去パス（パスAの途中）に衝突した場合**：
   - 衝突したマス（交差点）の時点で、それより先にはみ出していたパスAの履歴を巻き戻し・削除（**リワインド・トリミング**）して端点を現在の衝突位置へと更新し、そこから再び進行を再開する。
3. **パスBの途中（端点以外）に衝突した場合**：
   - パスBの「侵入・退出（in, out）のパス進行方向情報」を読み取り、パスBの端点がある方向へと進路を合わせる。
   - ここから **「パスBに沿って進むフェーズ」** に移行する。
   - 進む中で行き止まりに達した場合、隣接しているパスBの候補の中から **「ループ全体のパスが最も長くなる（削られる履歴が最も少なくなる）接続点」** を選択してパスBと接続する。
   - 接続が決定したら、選択した接続点よりも先に伸びていた余分なパスBの履歴（余分なしっぽ部分）を削除（**トリミング**）する。
4. **パスBの先端（現在の端点）にそのまま衝突・到達した場合**：
   - その時点で両者をそのまま直接接続する。
5. **結合部の整形（ループ未完成の罠対策）【重要】**：
   - 接続が成立した直後、結合部となったマス（Aの先端およびBの接続先となったマス）の **「接続方向（上下左右のどこへ線が伸びているか）」を必ず再計算** する。
   - 計算された接続方向に合わせて、盤面データ（`tileBoard`）のタイルタイプを正しい形状（例：上と左に繋がったなら「左上カーブ」等）に**上書き修正**して完全にループを確定させる。

---

## 3. 生成パスの形状調整（パラメーター）
無限シュリンクを緩和するため、以下の調整パラメーターを導入し、ステップ2の進行方向決定時に加味する。

- **直進率 (`straightProbability`)**：
  直進可能な空きマスがある場合、高い確率で直進を優先させる。
- **曲がった後の最低直進数 (`minStraightSteps`)**：
  一度曲がったら、壁にぶつかるか行き止まるまでは、最低Nマスは強制的に直進させる。これにより階段状に細かく曲がることを防ぎ、パスを大きく広げる。

---

## 4. プログラム実装上の注意点と矛盾の予防策（要考慮）

### ① パスBに衝突した際の「ループが長くなる方」の厳密な判定法
- **問題点**：パスBに衝突した際、「どちらに進めばループが長くなるか」を単純な直線距離や方向だけで推測すると、パスBが蛇行している場合に逆走や誤判定を起こす可能性がある。
- **解決策**：パスBのデータ構造はリスト（または配列）で履歴順に格納されているため、**「衝突したマスの、パスB内におけるインデックス番号」** を直接チェックするのが最も確実。
  - 開始点に近い側のインデックスで接続すると、それ以降のパスBがすべてトリミング（削除）されてしまうためループが短くなる。
  - したがって、**「パスBのインデックス番号が、できるだけ末尾（先端）に近いマス」** を選んで接続・トリミングを行うロジックにすることで、矛盾なく最長のループを維持できる。

### ② パスA自身の「永久リワインドループ」の防止
- **問題点**：ステップ3でパスAがパスBを目指して進む際、自身のパスAにぶつかってリワインドしたあと、再び同じ動きをして全く同じ場所でぶつかり直す「無限リワインド」が確率的に発生する懸念がある。
- **解決策**：パスAが自身のパスにぶつかってリワインドを行う際は、ただ端点を更新するだけでなく、**「今ぶつかってトリミングされたばかりの方向」を、次の一歩の選択肢（一時的な進入禁止フラグ等）から除外する** 処理を入れることで、別のルートへの分岐を強制させ、フリーズを確実に防止できる。