Line data Source code
1 : package mapplanner
2 :
3 : import (
4 : "cmp"
5 : "maps"
6 : "math"
7 : "slices"
8 :
9 : gc "github.com/kijimaD/ruins/internal/components"
10 : "github.com/kijimaD/ruins/internal/consts"
11 : )
12 :
13 : // facingRow は向きを1つにそろえる置物の並び。sides は並びが向ける方向の候補
14 : type facingRow struct {
15 : members []consts.Coord[consts.Tile]
16 : sides []consts.Cardinal
17 : }
18 :
19 : // RowPoses は facing の置物ごとの置き方を返す。隣り合う置物をまっすぐな並びにまとめ、一番長い並びから順に1つの置き方を決める。
20 : // 並びと直角の2方向のうち、背の塞がりが重く前が軽い側を向き、1台でも背が塞がれば並び全体を背へ寄せる。
21 : // 塞がりは動かない壁 wall を2、置物 blockers を1に数え、同点なら南・東・西・北の順で先の側を向く
22 : func RowPoses(facers, blockers map[consts.Coord[consts.Tile]]bool, wall func(consts.Coord[consts.Tile]) bool) map[consts.Coord[consts.Tile]]gc.Pose {
23 1 : weight := func(c consts.Coord[consts.Tile]) float64 {
24 1 : switch {
25 : case wall(c):
26 1 : return 2
27 : case blockers[c]:
28 1 : return 1
29 : default:
30 1 : return 0
31 : }
32 : }
33 2 : order := slices.SortedFunc(maps.Keys(facers), func(a, b consts.Coord[consts.Tile]) int { return cmp.Or(cmp.Compare(a.Y, b.Y), cmp.Compare(a.X, b.X)) })
34 1 : left := maps.Clone(facers)
35 1 : poses := map[consts.Coord[consts.Tile]]gc.Pose{}
36 1 : decide := func(row facingRow) {
37 1 : best, bestScore, back := row.sides[0], math.Inf(-1), 0.0
38 1 : for _, d := range row.sides {
39 1 : score, b := 0.0, 0.0
40 1 : for _, m := range row.members {
41 1 : b += weight(m.Sub(d.Delta()))
42 1 : score += weight(m.Sub(d.Delta())) - weight(m.Add(d.Delta()))
43 1 : }
44 1 : if score > bestScore {
45 1 : best, bestScore, back = d, score, b
46 1 : }
47 : }
48 1 : anchor := gc.AnchorCenter
49 1 : if back > 0 {
50 1 : anchor = gc.AnchorBack
51 1 : }
52 1 : for _, m := range row.members {
53 1 : poses[m] = gc.Pose{Facing: best, Anchor: anchor}
54 1 : delete(left, m)
55 1 : }
56 : }
57 1 : for len(left) > 0 {
58 1 : row := longestRow(order, left)
59 1 : if len(row.members) > 1 {
60 1 : decide(row)
61 1 : continue
62 : }
63 : // 一番長い並びが1台なら残りはどれも1台なので、並びを探し直さずに順に決める
64 1 : for _, c := range order {
65 1 : if left[c] {
66 1 : decide(facingRow{members: []consts.Coord[consts.Tile]{c}, sides: aloneSides})
67 1 : }
68 : }
69 : }
70 1 : return poses
71 : }
72 :
73 : var (
74 : // rowAxes は並びの軸。東西を先に探す
75 : rowAxes = []struct{ back, ahead consts.Cardinal }{{consts.West, consts.East}, {consts.North, consts.South}}
76 : // 向きの候補。同点なら先の側を向く
77 : eastWestRowSides = []consts.Cardinal{consts.South, consts.North}
78 : northSouthRowSides = []consts.Cardinal{consts.East, consts.West}
79 : aloneSides = []consts.Cardinal{consts.South, consts.East, consts.West, consts.North}
80 : )
81 :
82 : // longestRow は残りの置物 left の中で一番長いまっすぐな並びを返す。同じ長さなら order で先の置物から始まる並びを返す
83 : func longestRow(order []consts.Coord[consts.Tile], left map[consts.Coord[consts.Tile]]bool) facingRow {
84 1 : var best facingRow
85 1 : for _, c := range order {
86 1 : if !left[c] {
87 1 : continue
88 : }
89 1 : if best.members == nil {
90 1 : best = facingRow{members: []consts.Coord[consts.Tile]{c}}
91 1 : }
92 1 : for _, axis := range rowAxes {
93 1 : if left[c.Add(axis.back.Delta())] || !left[c.Add(axis.ahead.Delta())] {
94 1 : continue
95 : }
96 1 : row := facingRow{sides: eastWestRowSides}
97 1 : if axis.back == consts.North {
98 1 : row.sides = northSouthRowSides
99 1 : }
100 1 : for m := c; left[m]; m = m.Add(axis.ahead.Delta()) {
101 1 : row.members = append(row.members, m)
102 1 : }
103 1 : if len(row.members) > len(best.members) {
104 1 : best = row
105 1 : }
106 : }
107 : }
108 1 : return best
109 : }
|