その説はお世話になりました！
現在、スライドパズルゲームの問題作成と難易度についてのアルゴリズムを組んでおります。
難しい問題を作ろうと悩んでいた所、最短手数の数で並び替えるのはどうかとアドバイスを頂きました。
制作しているものは下の横版
[youtube]QHg8CG8uVzg[/youtube]
前回、投稿スレッド
http://dixq.net/forum/viewtopic.php?f=3&t=16432
------------------------------------
>難しさの判定
単純にクリアするために必要な手数が多い ≒ 難しい という話なのかわかりませんけど…
(1)適当に（クリア可能な）ステージを生成する手段
(2)ステージを与えられたらそれを解く（最短の手順を求める）手段
の２つを用意し，
(1)の作ったステージを (2)に食わせて出力される手数が多い奴を収集
（ (1)ではクリア可能かどうかすら考えず，(2)が「これは解けないし」と判定するという形でもよい ）
------------------------------------
このようなアドバイスを頂き、
適当にクリアが可能かわからないステージの生成はできたのですが、
コレに対して、最短手数を求めるアルゴリズムの書き方がわかりません。
マップテーブルは以下の仕様です。
■番号
1・・・自機
2・・・動かせないオブジェクト
100〜199・・・横に動くオブジェクト
200〜299・・・縦に動くオブジェクト
2マスあったりする同じオブジェクトに関しては同じ番号を割り振っております。
たとえば、下部の201が↓に動く場合、隣り合っている201も下に動きます。
1番の自機の右側が全て0になるか、一番右端に到達していたらクリア出来るかと思うのですが、
ココらへんの最短手数を求める方法がわからなくて・・・。
{
{ 0,201,0,0,0,0,0 },
{ 0,201,0,0,202,0,200 },
{ 0,0,0,0,202,0,200 },
{ 1,1,0,2,0,101,101 },
{ 0,0,0,0,0,0,0 },
{ 0,0,0,0,0,0,0 },
{ 0,0,0,0,100,100,0 }
},
下限値(LowerBound)枝刈り法
などがあるようですが、自機以外は目標の場所がわからないので、どのようにすればよいか悩んでおります。
↓マップ生成プログラム
#define TBL_WIDTH 7
#define TBL_HEIGHT 7
#define OBJECT_SIZE_MIN 2
#define OBJECT_SIZE_MAX 3
// 変数の宣言
int tblMaster[TBL_HEIGHT][TBL_WIDTH] = {
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{1,1,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0}
};
/*
InitObject関数を呼んでOBJECT用の配列をセットしてから、InitMap関数を呼ぶこと。
*/
class MAP_EDIT{
public:
enum MOVE{ MOVE_NOT, MOVE_V, MOVE_H, MOVE_MAX };
enum{ OBJECT_PLAYER = 1, OBJECT_NOT_MOVE = 2, OBJECT_MOVE_V = 100, OBJECT_MOVE_H = 200 };
typedef struct{
int Size;
MOVE Move;
}OBJECT;
int tblMap[TBL_HEIGHT][TBL_WIDTH];
int ObjectMax;
int CountV, CountH;
std::vector<OBJECT> Obj;
void Init(); // 各種変数の初期化
void InitObject( int max ); // ランダムなオブジェクトをmax分生成
void InitObject( int move_not, int move_v, int move_h ); // オブジェクトの個数を指定して生成
void InitMap(); // Mapを生成
void SetMap( OBJECT obj );
void SetMap( int x, int y, MOVE move, int size );
bool IsSetCheck( int x, int y, MOVE move, int size ); // 置けるか
void Log();
};
void MAP_EDIT::Init(){
for(int y=0; y<TBL_HEIGHT; y++){
for(int x=0; x<TBL_WIDTH; x++){
this->tblMap[y][x] = tblMaster[y][x];
}
}
this->ObjectMax = 0;
this->CountV = 0;
this->CountH = 0;
this->Obj.resize( 0 );
}
void MAP_EDIT::InitObject( int max ){
this->ObjectMax = max;
this->Obj.resize( this->ObjectMax );
// 何のオブジェクトを置くか
for(int i=0; i<this->Obj.size(); i++){
int r = rand() % MOVE_MAX;
OBJECT obj;
// MOVE_NOT, MOVE_V, MOVE_H,
if( r==0 ){
obj.Size = 1;
obj.Move = MOVE_NOT;
}
if( r==1 ){
obj.Size = OBJECT_SIZE_MIN + ( rand()%( OBJECT_SIZE_MAX-OBJECT_SIZE_MIN ) );
obj.Move = MOVE_V;
}
if( r==2 ){
obj.Size = OBJECT_SIZE_MIN + ( rand()%( OBJECT_SIZE_MAX-OBJECT_SIZE_MIN ) );
obj.Move = MOVE_H;
}
this->Obj[i] = obj;
}
}
void MAP_EDIT::InitObject( int move_not, int move_v, int move_h ){
this->ObjectMax = move_not + move_v + move_h;
this->Obj.resize( this->ObjectMax );
// 何のオブジェクトを置くか
for(int i=0; i<this->Obj.size(); i++){
int r = 0;
if( i < move_not ) r = 0;
else if( i < move_not + move_v ) r = 1;
else if( i < move_not + move_v + move_h ) r = 2;
OBJECT obj;
// MOVE_NOT, MOVE_V, MOVE_H,
if( r==0 ){
obj.Size = 1;
obj.Move = MOVE_NOT;
}
if( r==1 ){
obj.Size = OBJECT_SIZE_MIN + ( rand()%( OBJECT_SIZE_MAX-OBJECT_SIZE_MIN ) );
obj.Move = MOVE_V;
}
if( r==2 ){
obj.Size = OBJECT_SIZE_MIN + ( rand()%( OBJECT_SIZE_MAX-OBJECT_SIZE_MIN ) );
obj.Move = MOVE_H;
}
this->Obj[i] = obj;
}
}
void MAP_EDIT::InitMap(){
// 探索開始
for(int i=0; i<this->Obj.size(); i++){
this->SetMap( this->Obj[i] );
}
}
void MAP_EDIT::SetMap( OBJECT obj ){
// 置ける場所を探索
bool tblIndex[TBL_HEIGHT][TBL_WIDTH];
for(int y=0; y<TBL_HEIGHT; y++){
for(int x=0; x<TBL_WIDTH; x++){
tblIndex[y][x] = false;
}
}
for(int y=0; y<TBL_HEIGHT; y++){
for(int x=0; x<TBL_WIDTH; x++){
tblIndex[y][x] = this->IsSetCheck( x, y, obj.Move, obj.Size );
}
}
// ログ
/*
for(int y=0; y<TBL_HEIGHT; y++){
for(int x=0; x<TBL_WIDTH; x++){
printf( "%d", tblIndex[y][x] );
}
printf( " \r\n" );
}
*/
int cnt = 0;
int cntMax = 0;
int r = 0;
for(int y=0; y<TBL_HEIGHT; y++){
for(int x=0; x<TBL_WIDTH; x++){
if( tblIndex[y][x] ) cntMax++;
}
}
//NSLog( @"max %d", cntMax );
// 置ける場所があったら
if( cntMax > 0 ){
r = rand() % cntMax;
NSLog( @"r %d", r );
for(int y=0; y<TBL_HEIGHT; y++){
for(int x=0; x<TBL_WIDTH; x++){
if( tblIndex[y][x] ){
if( r == cnt ){
this->SetMap( x, y, obj.Move, obj.Size );
cnt++;
break;
}else{
cnt++;
}
}
}
}
}
}
void MAP_EDIT::SetMap( int x, int y, MOVE move, int size ){
//if( this->IsSetCheck( x, y, move, size ) ){
// マップを置いていく処理
for(int i=0; i<size; i++){
if( move == MOVE_NOT ){
this->tblMap[y][x] = OBJECT_NOT_MOVE;
}
if( move == MOVE_V ){
this->tblMap[y][x+i] = OBJECT_MOVE_V + this->CountV;
}
if( move == MOVE_H ){
this->tblMap[y+i][x] = OBJECT_MOVE_H + this->CountH;
}
}
//
if( move == MOVE_V ){
this->CountV++;
}
if( move == MOVE_H ){
this->CountH++;
}
//}
}
bool MAP_EDIT::IsSetCheck( int x, int y, MOVE move, int size ){
// エラー処理
if( x < 0 ) return false;
if( x >= TBL_WIDTH ) return false;
if( y < 0 ) return false;
if( y >= TBL_HEIGHT ) return false;
if( move == MOVE_NOT ){
if( size != 1 ) return false;
}
if( move == MOVE_V ){
if( x > TBL_WIDTH-size ) return false;
}
if( move == MOVE_H ){
if( y > TBL_HEIGHT-size ) return false;
}
// 連続したマスが空欄なら
bool flg = true;
for(int i=0; i<size; i++){
if( move == MOVE_NOT ){
if( tblMap[y][x] != 0 ) flg = false;
}
if( move == MOVE_V ){
if( tblMap[y][x+i] != 0 ) flg = false;
}
if( move == MOVE_H ){
if( tblMap[y+i][x] != 0 ) flg = false;
}
}
// どれにも引っかからなければ
return flg;
}
void MAP_EDIT::Log(){
printf( "{ " );
printf( "\r\n" );
for(int y=0; y<TBL_HEIGHT; y++){
printf( "{ " );
for(int x=0; x<TBL_WIDTH; x++){
printf( "%d", this->tblMap[y][x] );
if( x!=TBL_WIDTH-1 ){
printf( "," );
}
}
printf( " }" );
if( y!=TBL_HEIGHT-1 ){
printf( "," );
}
printf( "\r\n" );
}
printf( "}," );
printf( "\r\n" );
}
static MAP_EDIT Map;
◆main系
Map.Init();
// Map.InitObject( 5 );
Map.InitObject( 1, 2, 3 );
Map.InitMap();
Map.Log();
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター