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