LCOV - code coverage report
Current view: top level - mapplanner - pathfinder.go Coverage Total Hit
Test: coverage.lcov Lines: 92.6 % 121 112
Test Date: 2026-11-19 00:25:22 Functions: - 0 0

            Line data    Source code
       1              : package mapplanner
       2              : 
       3              : import (
       4              :         "fmt"
       5              : 
       6              :         gc "github.com/kijimaD/ruins/internal/components"
       7              :         "github.com/kijimaD/ruins/internal/consts"
       8              : )
       9              : 
      10              : // PathFinder はパスファインディング機能を提供する
      11              : type PathFinder struct {
      12              :         planData *MetaPlan
      13              : }
      14              : 
      15              : // NewPathFinder はPathFinderを作成する
      16              : func NewPathFinder(planData *MetaPlan) *PathFinder {
      17            1 :         return &PathFinder{planData: planData}
      18            1 : }
      19              : 
      20              : // fourDirs は上下左右の4方向のタイル差分
      21              : var fourDirs = []consts.Coord[consts.Tile]{{X: 0, Y: 1}, {X: 1, Y: 0}, {X: 0, Y: -1}, {X: -1, Y: 0}}
      22              : 
      23              : // IsWalkable は指定座標が歩行可能かを判定する
      24              : func (pf *PathFinder) IsWalkable(pos consts.Coord[consts.Tile]) bool {
      25              :         // 境界チェック
      26            1 :         if pos.X < 0 || pos.X >= pf.planData.Level.TileWidth || pos.Y < 0 || pos.Y >= pf.planData.Level.TileHeight {
      27            1 :                 return false
      28            1 :         }
      29              : 
      30            1 :         idx := pf.planData.Level.CoordToIndex(pos)
      31            1 :         return !pf.planData.Tiles[idx].BlockPass
      32              : }
      33              : 
      34              : // FindPath はBFSでスタート地点からゴールまでのパスを探索する。
      35              : // 上下左右の4方向移動のみサポートする。到達できない場合は空を返す
      36              : func (pf *PathFinder) FindPath(start, goal consts.Coord[consts.Tile]) []consts.Coord[consts.Tile] {
      37            1 :         if !pf.IsWalkable(start) || !pf.IsWalkable(goal) {
      38            1 :                 return nil
      39            1 :         }
      40              : 
      41              :         // parent はパス復元用、visited は探索済み。どちらもタイル座標をキーにする
      42            1 :         parent := map[consts.Coord[consts.Tile]]consts.Coord[consts.Tile]{}
      43            1 :         visited := map[consts.Coord[consts.Tile]]bool{start: true}
      44            1 :         queue := []consts.Coord[consts.Tile]{start}
      45            1 : 
      46            1 :         for len(queue) > 0 {
      47            1 :                 cur := queue[0]
      48            1 :                 queue = queue[1:]
      49            1 : 
      50            1 :                 if cur == goal {
      51            1 :                         return pf.reconstructPath(parent, start, goal)
      52            1 :                 }
      53              : 
      54            1 :                 for _, d := range fourDirs {
      55            1 :                         next := cur.Add(d)
      56            1 :                         // IsWalkable が境界外を false にするので境界チェックは兼ねる
      57            1 :                         if visited[next] || !pf.IsWalkable(next) {
      58            1 :                                 continue
      59              :                         }
      60            1 :                         visited[next] = true
      61            1 :                         parent[next] = cur
      62            1 :                         queue = append(queue, next)
      63              :                 }
      64              :         }
      65              : 
      66            1 :         return nil
      67              : }
      68              : 
      69              : // reconstructPath は親マップからスタート→ゴール順のパスを復元する
      70              : func (pf *PathFinder) reconstructPath(parent map[consts.Coord[consts.Tile]]consts.Coord[consts.Tile], start, goal consts.Coord[consts.Tile]) []consts.Coord[consts.Tile] {
      71            1 :         var path []consts.Coord[consts.Tile]
      72            1 :         for cur := goal; ; cur = parent[cur] {
      73            1 :                 path = append(path, cur)
      74            1 :                 if cur == start {
      75            1 :                         break
      76              :                 }
      77              :         }
      78              : 
      79              :         // スタートからゴールの順序にする
      80            1 :         for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
      81            1 :                 path[i], path[j] = path[j], path[i]
      82            1 :         }
      83              : 
      84            1 :         return path
      85              : }
      86              : 
      87              : // IsReachable はスタート地点からゴール地点まで到達可能かを判定する
      88              : func (pf *PathFinder) IsReachable(start, goal consts.Coord[consts.Tile]) bool {
      89            1 :         return len(pf.FindPath(start, goal)) > 0
      90            1 : }
      91              : 
      92              : // countReachableFrom は指定位置からBFSで到達可能な歩行可能タイル数を返す
      93              : func (pf *PathFinder) countReachableFrom(start consts.Coord[consts.Tile]) int {
      94            1 :         if !pf.IsWalkable(start) {
      95            0 :                 return 0
      96            0 :         }
      97              : 
      98            1 :         visited := map[consts.Coord[consts.Tile]]bool{start: true}
      99            1 :         queue := []consts.Coord[consts.Tile]{start}
     100            1 :         count := 0
     101            1 : 
     102            1 :         for len(queue) > 0 {
     103            1 :                 cur := queue[0]
     104            1 :                 queue = queue[1:]
     105            1 :                 count++
     106            1 : 
     107            1 :                 for _, d := range fourDirs {
     108            1 :                         next := cur.Add(d)
     109            1 :                         if !visited[next] && pf.IsWalkable(next) {
     110            1 :                                 visited[next] = true
     111            1 :                                 queue = append(queue, next)
     112            1 :                         }
     113              :                 }
     114              :         }
     115              : 
     116            1 :         return count
     117              : }
     118              : 
     119              : // hasAdjacentFreeTile は隣接4方向のうち少なくとも1つが歩行可能かつ計画済みエンティティがないかを判定する
     120              : func (pf *PathFinder) hasAdjacentFreeTile(pos consts.Coord[consts.Tile]) bool {
     121            1 :         for _, d := range fourDirs {
     122            1 :                 next := pos.Add(d)
     123            1 :                 if pf.IsWalkable(next) && !pf.planData.existPlannedEntityOnTile(next) {
     124            1 :                         return true
     125            1 :                 }
     126              :         }
     127            1 :         return false
     128              : }
     129              : 
     130              : // minReachableTiles はスポーン位置から到達可能なタイルの最小数。
     131              : // 小さな孤立部屋にスポーンしてポータルが至近距離に配置される問題を防ぐ
     132              : const minReachableTiles = 100
     133              : 
     134              : // FindPlayerStartPosition はプレイヤーの開始位置を探す
     135              : func (pf *PathFinder) FindPlayerStartPosition() (consts.Coord[consts.Tile], error) {
     136            1 :         planData := pf.planData
     137            1 : 
     138              :         // SpawnPointsが設定されていればそれを使用(テンプレートマップ用)
     139            1 :         if len(planData.SpawnPoints) > 0 {
     140            1 :                 return consts.Coord[consts.Tile]{X: consts.Tile(planData.SpawnPoints[0].X), Y: consts.Tile(planData.SpawnPoints[0].Y)}, nil
     141            1 :         }
     142              : 
     143              :         // プロシージャルマップ用: 歩行可能でポータルに到達可能な位置を探す
     144            1 :         width := planData.Level.TileWidth
     145            1 :         height := planData.Level.TileHeight
     146            1 : 
     147              :         // 候補位置を試す(中央から外側へ)
     148            1 :         attempts := []consts.Coord[consts.Tile]{
     149            1 :                 {X: width / 2, Y: height / 2},
     150            1 :                 {X: width / 4, Y: height / 4},
     151            1 :                 {X: 3 * width / 4, Y: height / 4},
     152            1 :                 {X: width / 4, Y: 3 * height / 4},
     153            1 :                 {X: 3 * width / 4, Y: 3 * height / 4},
     154            1 :         }
     155              : 
     156            1 :         for _, pos := range attempts {
     157            1 :                 if pf.isValidSpawnPosition(pos) {
     158            1 :                         return pos, nil
     159            1 :                 }
     160              :         }
     161              : 
     162              :         // 見つからない場合は全体をスキャン
     163            1 :         for _i := range planData.Tiles {
     164            1 :                 if !planData.Tiles[_i].BlockPass {
     165            1 :                         pos := planData.Level.IndexToCoord(gc.TileIdx(_i))
     166            1 :                         if pf.isValidSpawnPosition(pos) {
     167            1 :                                 return pos, nil
     168            1 :                         }
     169              :                 }
     170              :         }
     171              : 
     172            1 :         return consts.Coord[consts.Tile]{}, fmt.Errorf("no walkable tile that can reach a portal found")
     173              : }
     174              : 
     175              : // isValidSpawnPosition は指定位置がスポーン可能かつ十分な広さに到達可能かを判定する
     176              : func (pf *PathFinder) isValidSpawnPosition(pos consts.Coord[consts.Tile]) bool {
     177            1 :         planData := pf.planData
     178            1 :         idx := planData.Level.CoordToIndex(pos)
     179            1 :         if int(idx) >= len(planData.Tiles) || planData.Tiles[idx].BlockPass {
     180            1 :                 return false
     181            1 :         }
     182              : 
     183              :         // NPC・アイテム・ポータルなど計画済みエンティティとの重複を防ぐ
     184            1 :         if planData.existPlannedEntityOnTile(pos) {
     185            1 :                 return false
     186            1 :         }
     187              : 
     188              :         // 隣接4方向のうち少なくとも1つは移動可能なタイルが必要。
     189              :         // 敵エンティティはBlockPassを持つため、全隣接タイルが占有されるとプレイヤーが移動不能になる
     190            1 :         if !pf.hasAdjacentFreeTile(pos) {
     191            1 :                 return false
     192            1 :         }
     193              : 
     194              :         // 到達可能なタイル数が十分であることを確認する。
     195              :         // 単一BFSで済むため、複数BFSを要するポータル到達性チェックより先に行う
     196            1 :         if pf.countReachableFrom(pos) < minReachableTiles {
     197            1 :                 return false
     198            1 :         }
     199              : 
     200              :         // NextPortalsへの到達性をチェック
     201            1 :         for _, portal := range planData.NextPortals {
     202            1 :                 if !pf.IsReachable(pos, portal) {
     203            0 :                         return false
     204            0 :                 }
     205              :         }
     206              : 
     207            1 :         return true
     208              : }
     209              : 
     210              : // ValidatePortalReachability はプレイヤー開始位置から全ポータルへの到達性を検証する
     211              : func (pf *PathFinder) ValidatePortalReachability() error {
     212              :         // プレイヤー開始位置を取得
     213            1 :         playerPos, err := pf.FindPlayerStartPosition()
     214            1 :         if err != nil {
     215            0 :                 return fmt.Errorf("%w: player start position is not set", ErrConnectivity)
     216            0 :         }
     217              : 
     218              :         // NextPortalsの到達性をチェック
     219            1 :         for i, portal := range pf.planData.NextPortals {
     220            1 :                 if !pf.IsReachable(playerPos, portal) {
     221            0 :                         return fmt.Errorf("%w: player start (%d,%d) cannot reach NextPortal[%d](%d,%d)",
     222            0 :                                 ErrConnectivity, playerPos.X, playerPos.Y, i, portal.X, portal.Y)
     223            0 :                 }
     224              :         }
     225              : 
     226            1 :         return nil
     227              : }
        

Generated by: LCOV version 2.0-1