dkh.dungeon source code

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