LCOV - code coverage report
Current view: top level - activity - pathfind.go Coverage Total Hit
Test: coverage.lcov Lines: 92.5 % 67 62
Test Date: 2026-11-19 00:25:22 Functions: - 0 0

            Line data    Source code
       1              : package activity
       2              : 
       3              : import (
       4              :         gc "github.com/kijimaD/ruins/internal/components"
       5              :         "github.com/kijimaD/ruins/internal/consts"
       6              :         w "github.com/kijimaD/ruins/internal/world"
       7              : 
       8              :         "github.com/kijimaD/ruins/internal/world/query"
       9              :         "github.com/mlange-42/ark/ecs"
      10              : )
      11              : 
      12              : type bfsGrid struct {
      13              :         world w.World
      14              :         mover ecs.Entity
      15              :         si    *gc.SpatialIndex
      16              : }
      17              : 
      18              : func (g *bfsGrid) isPassable(pos consts.Coord[consts.Tile]) bool {
      19            1 :         if pos.X < 0 || pos.Y < 0 || pos.X >= g.si.MapWidth || pos.Y >= g.si.MapHeight {
      20            1 :                 return false
      21            1 :         }
      22            1 :         key := gc.GridElement{Coord: pos}
      23            1 :         if g.si.BlockPass[key] {
      24            1 :                 return false
      25            1 :         }
      26            1 :         if _, ok := g.si.Characters[key]; ok {
      27            1 :                 return false
      28            1 :         }
      29            1 :         return true
      30              : }
      31              : 
      32              : // canPassDiagonal は斜め移動時の壁すり抜けを禁じる。隣接する直交2方向の
      33              : // どちらかが通行可能なら斜めに進める。d は移動方向で各成分は -1/0/1
      34              : func (g *bfsGrid) canPassDiagonal(cur, d consts.Coord[consts.Tile]) bool {
      35            1 :         if d.X == 0 || d.Y == 0 {
      36            1 :                 return true
      37            1 :         }
      38            1 :         return g.isPassable(cur.Add(consts.Coord[consts.Tile]{X: d.X})) ||
      39            1 :                 g.isPassable(cur.Add(consts.Coord[consts.Tile]{Y: d.Y}))
      40              : }
      41              : 
      42              : // FindNextStep はBFSで最短経路を求め、次の1歩の座標を返す。
      43              : // 経路が見つからない場合はfalseを返す。
      44              : // ゴールが通行不能でも到達を認識する。ゴールはキューに入れないので通り抜ける経路は生まれない。
      45              : // キャラクターの通行可否はmoverとの関係性で決まる
      46              : func FindNextStep(world w.World, mover ecs.Entity, from, goal consts.Coord[consts.Tile]) (consts.Coord[consts.Tile], bool) {
      47            1 :         si := query.GetSpatialIndex(world)
      48            1 :         if si == nil {
      49            0 :                 return consts.Coord[consts.Tile]{}, false
      50            0 :         }
      51              : 
      52            1 :         if from == goal {
      53            1 :                 return consts.Coord[consts.Tile]{}, false
      54            1 :         }
      55              : 
      56            1 :         inBounds := func(p consts.Coord[consts.Tile]) bool {
      57            1 :                 return p.X >= 0 && p.Y >= 0 && p.X < si.MapWidth && p.Y < si.MapHeight
      58            1 :         }
      59            1 :         if !inBounds(from) || !inBounds(goal) {
      60            0 :                 return consts.Coord[consts.Tile]{}, false
      61            0 :         }
      62              : 
      63            1 :         g := &bfsGrid{world: world, mover: mover, si: si}
      64            1 : 
      65              :         // visited は探索済みタイル、firstStep はそのタイルへ到達する最初の1歩を記録する
      66            1 :         visited := map[consts.Coord[consts.Tile]]bool{from: true}
      67            1 :         firstStep := map[consts.Coord[consts.Tile]]consts.Coord[consts.Tile]{}
      68            1 : 
      69            1 :         queue := []consts.Coord[consts.Tile]{from}
      70            1 : 
      71            1 :         dirs := []consts.Coord[consts.Tile]{
      72            1 :                 {X: 0, Y: -1}, {X: 0, Y: 1}, {X: -1, Y: 0}, {X: 1, Y: 0},
      73            1 :                 {X: -1, Y: -1}, {X: 1, Y: -1}, {X: -1, Y: 1}, {X: 1, Y: 1},
      74            1 :         }
      75              : 
      76            1 :         for len(queue) > 0 {
      77            1 :                 cur := queue[0]
      78            1 :                 queue = queue[1:]
      79            1 : 
      80            1 :                 for _, d := range dirs {
      81            1 :                         next := cur.Add(d)
      82            1 : 
      83            1 :                         isGoal := next == goal
      84            1 : 
      85            1 :                         if !isGoal && !g.isPassable(next) {
      86            1 :                                 continue
      87              :                         }
      88            1 :                         if !g.canPassDiagonal(cur, d) {
      89            0 :                                 continue
      90              :                         }
      91            1 :                         if visited[next] {
      92            1 :                                 continue
      93              :                         }
      94            1 :                         visited[next] = true
      95            1 : 
      96            1 :                         if cur == from {
      97            1 :                                 firstStep[next] = next
      98            1 :                         } else {
      99            1 :                                 firstStep[next] = firstStep[cur]
     100            1 :                         }
     101              : 
     102            1 :                         if isGoal {
     103            1 :                                 return firstStep[next], true
     104            1 :                         }
     105              : 
     106            1 :                         queue = append(queue, next)
     107              :                 }
     108              :         }
     109              : 
     110            1 :         return consts.Coord[consts.Tile]{}, false
     111              : }
        

Generated by: LCOV version 2.0-1