モチベーション
- C++を勉強しているので何かしらのアウトプットを求めて(特にベクターの操作)
- こちら(AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～)の記事で紹介されていたこの問題(ABC075 B問題 Minesweeper)を見て、マインスイーパくらいならそこそこ時間をかければ一人でも作れるのではないか？と思った
- ゲームを作ってオブジェクト指向についてわかった気になりたかった
- ゲームを作るに当たって自分の思考を追えるように記録しておきたかった
- 深さ優先探索の簡単な応用例(というかほぼそのまま)として
マインスイーパに最低限必要なもの
コードを書く前にマインスイーパをちょっと遊んでどういうゲームだったかを思い出す。
1. 縦H × 横Wの盤面にX個の爆弾が設置されている
→今回はWindowsに入っているものの中級(16×16マス、爆弾40個)を参考に作ってみる
2. 爆弾マスを開くとゲームオーバー、通常マスを開くと周りにある爆弾マスの数を表示しゲームを続行する
→１マスごとに開いているかそうでないか、爆弾かそうでないか、周りの爆弾の数
これらの情報を持たせておく
3. 爆弾マスでない全てのマスを開けるとゲームクリア
→爆弾マスを踏まなくてもループを切る処理を追加する
4. 最初に指定したマスとその隣接したマスは爆弾マスではない
→爆弾マスの位置は乱数を発生させて得るが、そのタイミングは最初のマスを開けたあとであることに注意、これがないと最初に爆弾を踏む可能性も充分あるクソゲーと化す
5.周りに爆弾の無いマスを開いた場合、自動的に周囲のマスを開く
→マスを開く関数を実装し、周りの爆弾の数(下のコードではblock.neighbor)==0で再帰的に呼び出す(深さ優先探索を行うことと同義、のはず)
コード内容
mine.cpp
#include<iostream>
#include<vector>
#include<random>
#include<algorithm>
#include<time.h>
#define WIDTH 16
#define HEIGHT 16
#define BOMBS 40
using namespace std;
bool game = true;
void open(int, int); //マスを開く関数, if(block.neighbor == 0)で再帰的に呼び出す
int countneighbor(int, int); //周囲の爆弾マスをカウントする(レンジオーバーしたときreturnする)
struct msg{
char header[128] = " | 0 1 2 3 4 5 6 7 8 9 a b c d e f\n--+---------------------------------\n";
char alreadyopen[128] = "already opened block. Please input again.\n";
char input[128] = "where to open?(input x-ax, y-ax)\n>>";
char over[32] = "------GAME OVER------\n";
char clear[32] = "/\\/\\/\\CONGRATS!\\/\\/\\/\n";
}sysmsg;
class block
{
public:
int neighbor; //隣接する爆弾マスの数 <- state==trueの場合coutでコンソールに表示する
bool state; //まだ開いていない->false | 開いている->true
bool isbomb; //爆弾マス->true | 普通のマス->false
};
void initialize(block[HEIGHT][WIDTH], int, int); //盤面の初期化
block field[HEIGHT][WIDTH]; //盤面そのもの
int count_opened = 0; //空いたマスをカウント
int main()
{
int x, y, ix, iy;
cout << sysmsg.header;
for(int i = 0; i < HEIGHT; i++)
{
cout << std::hex << i << " |";
for(int j = 0; j < WIDTH; j++)
{
field[i][j].state = false;
cout << " _";
}
cout << "\n";
}
cout << sysmsg.input;
cin >> std::hex >> ix >> std::hex >> iy;
initialize(field, ix, iy);
open(ix, iy);
if(count_opened == (HEIGHT * WIDTH - BOMBS))
game = false;
while(game){
cout << sysmsg.header;
for(int i = 0; i < HEIGHT; i++)
{
cout << std::hex << i << " |";
for(int j = 0; j < WIDTH; j++)
{
if(field[i][j].state)
cout << " " << field[i][j].neighbor;
else
cout << " _";
}
cout << "\n";
}
cout << sysmsg.input;
cin >> std::hex >> x >> std::hex >> y;
if(field[y][x].state)
{
cout << sysmsg.alreadyopen;
continue;
}
else
open(x, y);
if(count_opened == (HEIGHT * WIDTH - BOMBS))
game = false;
}
if(!game)
{
if(count_opened == (HEIGHT * WIDTH - BOMBS))
cout << sysmsg.clear;
cout << sysmsg.header;
for(int i = 0; i < HEIGHT; i++)
{
cout << std::hex << i << " |";
for(int j = 0; j < WIDTH; j++)
{
if(!field[i][j].isbomb)
cout << " " << field[i][j].neighbor;
else
cout << " *";
}
cout << "\n";
}
}
return 0;
}
//盤面の初期化を行う関数
void initialize(block[HEIGHT][WIDTH], int x, int y)
{
srand((unsigned int)time(NULL));
vector<int> bombv;
vector<int> notbombv;
if(y == 0)
{
if(x == 0)
notbombv = {0, 1, 16, 17};
else if(x == 15)
notbombv = {14, 15, 30, 31};
else
notbombv = {x-1, x, x+1, x+15, x+16, x+17};
}
else if(y == 15)
{
if(x == 0)
notbombv = {224, 225, 240, 241};
else if(x == 15)
notbombv = {238, 239, 254, 255};
else
notbombv = {x+223, x+224, x+225, x+239, x+240, x+241};
}
else
{
if(x == 0)
notbombv = {(y-1)*HEIGHT+x, (y-1)*HEIGHT+x+1, y*HEIGHT+x, y*HEIGHT+x+1, (y+1)*HEIGHT+x, (y+1)*HEIGHT+x+1};
else if(x==15)
notbombv = {(y-1)*HEIGHT+x-1, (y-1)*HEIGHT+x, y*HEIGHT+x-1, y*HEIGHT+x, (y+1)*HEIGHT+x-1, (y+1)*HEIGHT+x};
else
notbombv = {(y-1)*HEIGHT+x-1, (y-1)*HEIGHT+x, (y-1)*HEIGHT+x+1, y*HEIGHT+x-1, y*HEIGHT+x, y*HEIGHT+x+1,(y+1)*HEIGHT+x-1, (y+1)*HEIGHT+x, (y+1)*HEIGHT+x+1};
}
for(int i = 0; bombv.size() != BOMBS; i++)
{
int a = rand() / (1.0 + RAND_MAX) * (WIDTH * HEIGHT);
auto itr = find(bombv.begin(), bombv.end(), a);
auto itrn = find(notbombv.begin(), notbombv.end(), a);
if(itr == bombv.end() && itrn == notbombv.end())
bombv.push_back(a);
}
for(int i = 0; i < HEIGHT; i++)
{
for(int j = 0; j < WIDTH; j++)
{
auto itr = find(bombv.begin(), bombv.end(), 16 * i + j);
if(itr != bombv.end())
field[i][j].isbomb = true;
else
field[i][j].isbomb = false;
}
}
for(int i = 0; i < HEIGHT; i++)
{
for(int j = 0; j < WIDTH; j++)
{
for(int dy = -1; dy <= 1; dy++)
{
for(int dx = -1; dx <= 1; dx++)
{
if(dx != 0 || dy != 0)
field[i][j].neighbor += countneighbor(j + dx, i + dy);
}
}
}
}
return;
}
void open(int x_c, int y_c)
{
if(x_c < 0 || x_c >= WIDTH || y_c < 0 || y_c >= HEIGHT || field[y_c][x_c].state)
return;
field[y_c][x_c].state = true;
count_opened += 1;
if(field[y_c][x_c].isbomb)
{
cout << sysmsg.over;
game = false;
return;
}
if(field[y_c][x_c].neighbor == 0)
{
open(x_c-1, y_c-1);
open(x_c-1, y_c);
open(x_c-1, y_c+1);
open(x_c, y_c-1);
open(x_c, y_c+1);
open(x_c+1, y_c-1);
open(x_c+1, y_c);
open(x_c+1, y_c+1);
}
return;
}
int countneighbor(int x_s, int y_s)
{
if(x_s < 0 || x_s >= WIDTH || y_s < 0 || y_s >= HEIGHT)
return 0;
if(field[y_s][x_s].isbomb)
return 1;
else
return 0;
}
反省、感想、他
- ベクターの理解と習熟のため、半ば無理やり爆弾マスと非爆弾確定マス(最初に開いたマスとその周囲)の位置をベクターに入れており、少々煩雑なコードになっている気がしなくもない
- 爆弾マスの位置は16×16に対して0~255で取得しているが、盤面を表すfieldはblock[HEIGHT][WIDTH]の2次元配列の形で定義しているのでわかりにくさを覚える(vector bombv; などと定義することも考えたが実装に悩んだ)
- 他、関数とするべきであろう処理もいくつか思い当たるがまたもや実装に悩んだ
- 「深さ優先探索 マインスイーパ」でググっても目ぼしい結果が出てこなかったのでこの記事があわよくば上がってほしいと思う（そんなワードで検索する人間がいるのかわからないが）
- オブジェクト指向についてはあまり分かった気になれなかった（カードゲームとか書いてみれば分かるのかもしれない）
- 200数行コードを書けばゲーム（コンソールで入力するマインスイーパ）が作れることが分かり、いい勉強になった(その一方でゲーム制作の大変さも何となく分かった)
- 添削、ご指摘などあればよろしくお願いいたします。
参考
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
ABC075 B:Minesweeper
AtCoder Typical Contest A:深さ優先探索