寝付けなくて以下のゲームを軽くやってました。
MYAOSOFTガラケーコレクション
https://store.steampowered.com/app/2091650/MYAOSOFT/
この中に倉庫番のゲームがあって、それが解けなくて逆に寝れなくなってしまったのでコンピューターの力でぶん殴ることにしました。
倉庫番とは？
Wiki読むんだwikiを！
倉庫番 – Wikipedia
荷物を押して目的の場所に置くパズルゲームです。
RPGとかのミニゲームにありがちなやつです。
プログラム
言語はC++、VSCodeでg++を使ってビルドして動かしました。
多分どの環境でも動くかなと思います。
※プログラムめちゃ汚いですごめんね(´・ω・｀)
※変な入力とかに対応しきれていません。あと、倉庫番がでかすぎると計算量死にます。
計算が終わらないと思ったら諦めて…
※例外処理とかしてないよ、正しく使ってあげてね！
※何かあっても責任取りません！！！！！！！
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
using namespace std;
#define SIZEX 8
#define SIZEY 8
int main(){
cout<<"1 start,2 block,3 goal,4 wall,5 road,6 start&goal,7 block&goal"<<endl;
string maze="";
for(int i=0;i<SIZEX+2;i++){
maze+="4";
}
for(int i=1;i<=SIZEY;i++){
string stmp;
cin>>stmp;
maze=maze+"4"+stmp+"4";
}
for(int i=0;i<SIZEX+2;i++){
maze+="4";
}
vector<pair<int,int>> gl;
for(int i=1;i<=SIZEY;i++){
for(int j=1;j<=SIZEX;j++){
if(maze[i*(SIZEX+2)+j]=='3'||maze[i*(SIZEX+2)+j]=='6'||maze[i*(SIZEX+2)+j]=='7'){
pair<int,int> tmp;
tmp.first=i;
tmp.second=j;
gl.push_back(tmp);
if(maze[i*(SIZEX+2)+j]=='3') maze[i*(SIZEX+2)+j]='5';
else if(maze[i*(SIZEX+2)+j]=='6') maze[i*(SIZEX+2)+j]='1';
else if(maze[i*(SIZEX+2)+j]=='7') maze[i*(SIZEX+2)+j]='2';
}
}
}
set<string> memo;
queue<pair<string,string>> q;
pair<string,string> pini;
pini.first=maze;
pini.second="";
q.push(pini);
string ans;
while(!q.empty()&&ans==""){
pair<string,string> ps;
ps=q.front();
q.pop();
string pmaze=ps.first;
string proad=ps.second;
pair<int,int> human;
bool find=false;
for(int i=1;i<=SIZEY;i++){
for(int j=1;j<=SIZEX;j++){
if(pmaze[i*(SIZEX+2)+j]=='1'){
human.first=i;
human.second=j;
find=true;
break;
}
if(find) break;
}
}
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
string dir[4]={"d","u","r","l"};
for(int i=0;i<4;i++){
int ty=dy[i]+human.first;
int tx=dx[i]+human.second;
int tty=dy[i]*2+human.first;
int ttx=dx[i]*2+human.second;
if(pmaze[ty*(SIZEX+2)+tx]=='5'){
string ins=pmaze;
ins[ty*(SIZEX+2)+tx]='1';
ins[human.first*(SIZEX+2)+human.second]='5';
if(memo.find(ins)==memo.end()){
memo.insert(ins);
pair<string,string> ptmp;
ptmp.first=ins;
ptmp.second=proad+dir[i];
q.push(ptmp);
}
}
if(pmaze[ty*(SIZEX+2)+tx]=='2'&&pmaze[tty*(SIZEX+2)+ttx]=='5'){
string ins=pmaze;
ins[tty*(SIZEX+2)+ttx]='2';
ins[ty*(SIZEX+2)+tx]='1';
ins[human.first*(SIZEX+2)+human.second]='5';
if(memo.find(ins)==memo.end()){
memo.insert(ins);
pair<string,string> ptmp;
ptmp.first=ins;
ptmp.second=proad+dir[i];
q.push(ptmp);
}
int c=0;
for(int j=0;j<gl.size();j++){
if(ins[gl[j].first*(SIZEX+2)+gl[j].second]=='2') c++;
}
if(c==gl.size()){
ans=proad+dir[i];
break;
}
}
}
}
cout<<ans<<endl;
}
実行例
今回、Wikipediaのパズルを使ってみます。
倉庫番 – Wikipedia
cout<<"1 start,2 block,3 goal,4 wall,5 road,6 start&goal,7 block&goal"<<endl;にある通り、
スタートは1、押したりする木箱は2、木箱を置く場所は3、壁は4、それ以外の道は5、スタートと木箱を置く場所が重なってる場合は6、押したりする木箱と木箱を置く場所が重なってる場合は7
で入力します。
#define SIZEX 8
#define SIZEY 8としているので倉庫番のマップサイズは8*8にします。
倉庫番のサイズが変わる場合はここの値を伸ばすか縮めるか、4で埋めるとかしてくださいね！
こんな感じです↓
44444444
44455544
43125544
44452344
43442544
45453544
42572234
45553554結果は以下になります。
rurrddddldruuuulllrdrdrddlldlluudruは上、dは下、rは右、lは左です。解けていそうですね…！
BFSで解いてるので、これが最短手(34手)になります。
ちなみに、これくらいのサイズなら2,3秒で終わります。
簡単なコード解説
※ほぼ自分用メモです。
ソース上にコメントなくてね…
string maze="";
for(int i=0;i<SIZEX+2;i++){
maze+="4";
}
for(int i=1;i<=SIZEY;i++){
string stmp;
cin>>stmp;
maze=maze+"4"+stmp+"4";
}
for(int i=0;i<SIZEX+2;i++){
maze+="4";
}迷路の入力部分です。
端っこの判定がめんどくさいので、端を壁で埋めてサボるようにしています。
※壁に行くことができないので、壁=行き止まりの判定ついでに端の判定もできる。
vector<pair<int,int>> gl;ゴールは事前に場所を記録して迷路上から消すようにしています。
これをすると、移動とか箱を押す際にゴールを気にしなくて良くなるので(多分)コーディングが楽になります。
set<string> memo;
queue<pair<string,string>> q;倉庫番はプレイヤーの位置以外に箱の位置も覚える必要があるので、マップをまるっと記録するようにします。
キューにはマップの状態と、その状態にするための手順を格納します。
毎移動で4方向に動けるので、1手順でBFSの枝葉が4倍ずつ増えます。これだと計算量が大変なので、setに訪れたマップは格納していって、別経路で訪れたマップに遷移するなら弾くようにします。
これで多少はよくなる….はず！
while(!q.empty()&&ans==""){
pair<string,string> ps;
ps=q.front();
q.pop();BFS部分です。
キューを使って全探索しています。
毎回popを書き忘れて無限ループしちゃいます….ひえぇ
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
string dir[4]={"d","u","r","l"};
for(int i=0;i<4;i++){
int ty=dy[i]+human.first;
int tx=dx[i]+human.second;
int tty=dy[i]*2+human.first;
int ttx=dx[i]*2+human.second;倉庫番は上下左右に動けるので4方向見るようにしています。
箱を押す場合、2マス先も気にする必要があるため、ある方向の2マス先の座標も計算しています。
if(pmaze[ty*(SIZEX+2)+tx]=='5'){
string ins=pmaze;
ins[ty*(SIZEX+2)+tx]='1';
ins[human.first*(SIZEX+2)+human.second]='5';
if(memo.find(ins)==memo.end()){
memo.insert(ins);
pair<string,string> ptmp;
ptmp.first=ins;
ptmp.second=proad+dir[i];
q.push(ptmp);
}
}『1マス先が通路なら移動する』の遷移です。
ただただ通路に移動するだけの部分ですね。訪れたことのないマップになったならキューに突っ込んで、次の探索時にさらに4方向に進むようにします。
if(pmaze[ty*(SIZEX+2)+tx]=='2'&&pmaze[tty*(SIZEX+2)+ttx]=='5'){
string ins=pmaze;
ins[tty*(SIZEX+2)+ttx]='2';
ins[ty*(SIZEX+2)+tx]='1';
ins[human.first*(SIZEX+2)+human.second]='5';
if(memo.find(ins)==memo.end()){
memo.insert(ins);
pair<string,string> ptmp;
ptmp.first=ins;
ptmp.second=proad+dir[i];
q.push(ptmp);
}
int c=0;
for(int j=0;j<gl.size();j++){
if(ins[gl[j].first*(SIZEX+2)+gl[j].second]=='2') c++;
}
if(c==gl.size()){
ans=proad+dir[i];
break;
}
}
『1マス先が木箱で、2マス先が通路なら箱を押す』の遷移です。
倉庫番で大事な動作ですね。
これも『1マス先が通路なら移動する』と同じく、訪れたことのないマップになったならキューに突っ込みます。
また、木箱を押した場合、クリア条件を満たしている場合があるのでそれも計算します。
事前に記録したゴール位置すべてに木箱がのっていることが条件です。
やり残したこと
計算量削減
→MYAOSOFTガラケーコレクションの倉庫番がそこそこ小さかったので結構ごり押しましたが、もう少し大きく複雑なマップでも解けるように計算量減らしたいですね。
GUI化
→1,2,3,4…で入れるの面倒なので、GUI操作で簡単入力したいですね。答えが分ればwikipediaのような解法アニメーションもつけてみたい…！
コードを整える
→レビュー出したらめちゃくちゃ怒られそう(´・ω・｀)
雑感想
こういうの書いてると競プロやりたくなってきますねー。
土日の予定はほぼ空けるようにしたので、暇だったら参加してみようかしら！
あと、MYAOSOFTさんごめんなさい…。倉庫番難しすぎるんだぁ…。
コメント