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 : }
|