dkh.dungeon source code

1 module dkh.dungeon;
2 
3 /// [+row, +col, -row, -col]
4 immutable static int[2][4] direction4 = [
5     [1, 0], [0, 1], [-1, 0], [0, -1],
6 ];
7 
8 /// [+col, +row+col, +row, +row-col, ...]
9 immutable static int[2][8] direction8 = [
10     [1, 0],
11     [1, 1],
12     [0, 1],
13     [-1, 1],
14     [-1, 0],
15     [-1, -1],
16     [0, -1],
17     [1, -1],
18 ];
19 
20 static int[2] addInt2(in int[2] a, in int[2] b) {
21     int[2] c;
22     c[] = a[] + b[];
23     return c;
24 }
25 
26 /**
27 プロコンでよくある2Dダンジョン探索を支援するライブラリ
28 $(D int[2] = [row, column])をベースとする
29  */
30 struct Dungeon {
31     /// pからdir方向に移動したときの座標
32     static int[2] move4(int[2] p, int dir) {
33         return addInt2(p, direction4[dir]);
34     }
35     /// pからdir方向に移動したときの座標, 8方向
36     static int[2] move8(int[2] p, int dir) {
37         return addInt2(p, direction8[dir]);
38     }
39 
40     immutable int R, C;
41     /**
42     Params:
43         R = row_max
44         C = column_max
45     */
46     this(int R, int C) {
47         this.R = R;
48         this.C = C;
49     }
50     /// pが[0, 0] ~ [R-1, C-1]に入っているか？
51     bool isInside(int[2] p) const {
52         int r = p[0], c = p[1];
53         return 0 <= r && r < R && 0 <= c && c < C;
54     }
55     /// 1次元に潰したときのID, r*R+c
56     int getID(int[2] p) const {
57         int r = p[0], c = p[1];
58         return r*R+c;
59     }
60 }
61 
62 ///
63 auto neighbors4(int[2] p) {
64     static struct Rng {
65         int[2] center;
66         size_t i;
67         bool empty() const { return i == 4;}
68         int[2] front() const { return addInt2(center, direction4[i]); }
69         void popFront() { i++; }
70     }
71     return Rng(p, 0);
72 }
73 
74 ///
75 unittest {
76     import std.algorithm : equal;
77     assert(equal(
78         [3, 5].neighbors4,
79         [[4, 5], [3, 6], [2, 5], [3, 4]],
80         ));
81 }
82 
83 /// list neighbors only inside
84 auto neighbors4(int[2] p, in Dungeon dg) {
85     static struct Rng {
86         int[2] center;
87         Dungeon dg;
88         size_t i;
89         this(in int[2] center, in Dungeon dg) {
90             this.center = center;
91             this.dg = dg;
92             while (!empty() && !dg.isInside(front)) i++;
93         }
94         bool empty() const { return i == 4;}
95         int[2] front() const { return addInt2(center, direction4[i]); }
96         void popFront() {
97             i++;
98             while (!empty() && !dg.isInside(front)) i++;
99         }
100     }
101     return Rng(p, dg);
102 }
103 
104 ///
105 unittest {
106     import std.algorithm : equal;
107     assert(equal(
108         [0, 0].neighbors4(Dungeon(3, 3)),
109         [[1, 0], [0, 1]],
110         ));
111 }