掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.28223

パズルゲームのアルゴリズムについて
投稿者---へろり(2006/09/20 14:37:00)


現在下記のルールのパズルゲームを作成しているのですが、そのルールの一部において
表題の通りどのようなアルゴリズムで実装すれば良いか悩んでおります。

ルールとは縦8マス・横8マスのフィールドがあり、そこに数種類のキャラクターが
配置されています。

そして隣接したキャラクターを置き換えて、縦あるいは横に3つ以上同じキャラクターを
並べるとそれを消すことが出来ます。 イメージとしては次のようになります。

CDFAB
BFDFA

  ↓FとDを置き換える

CDDAB
BFFFA

  ↓Fが消える

CDDAB
B・・・A

なお、キャラクターを置き換えた後、キャラクターを消す条件が成立しない場合、つまり
置き換えたキャラクターのいずれか、あるいは両方のキャラクターが3つ以上揃わないと
置き換えることは出来ません。

また、キャラクターを消す事が出来た場合、より上にあるキャラクターが下へシフトされ
空いた場所へは新しいキャラクターが詰められます。
ですから、全てのマス目には何かしらのキャラクターが必ず存在しています。

ZooKeeperというゲームがありますが、これと全く同じルールです。


以上のルールに従いますと、どうあがいてもキャラクターを消すことが出来ない局面が
出てきます。 以下のような場合は消すことが出来ません。

ABCDE
AAFBD
DBFCA
FCDAB

私が悩んでいるのはこの、まだ消すことが可能な場所があるか? もうないか?
の判定部分です。

長くなりましたが、お知恵をお貸しください。 よろしくお願いします。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:パズルゲームのアルゴリズムについて 28224 nano 2006/09/20 14:47:20
<子記事> Re:パズルゲームのアルゴリズムについて 28225 気分屋 2006/09/20 15:18:45
<子記事> Re:パズルゲームのアルゴリズムについて 28228 円零 2006/09/20 16:10:22


No.28224

Re:パズルゲームのアルゴリズムについて
投稿者---nano(2006/09/20 14:47:20)


例えば、横方向にAnA(nはA以外)と並んでいて、
nの上にも下にもAがなければ、そのAは消せない、
というような判定を、横方向・縦方向のすべての
組み合わせについて行なうとか…。

盤面の端については、何か特殊な処理が必要かもしれません。


この投稿にコメントする

削除パスワード

No.28225

Re:パズルゲームのアルゴリズムについて
投稿者---気分屋(2006/09/20 15:18:45)


判定するだけのプログラム
なお、端判定は-1の詰め物を入れる派です。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_X         10
#define MAX_Y         10
#define FLG_ON        1
#define FLG_OFF       0

int main(void)
{
    int map[MAX_Y][MAX_X];
    int x, y;
    int flg;

    // 初期化
    srand((unsigned int)time(NULL));
    for (y = 0; y < MAX_Y; y++) {
        for (x = 0; x < MAX_X; x++) {
            if (y >= 1 && y <= (MAX_Y - 2) && x >= 1 && x <= (MAX_X - 2)) {
                map[y][x] = rand() % 8;
            } else {
                map[y][x] = -1;
            }
            printf("%3d", map[y][x]);
        }
        printf("\n");
    }

    // マスを判定
    flg = FLG_OFF;
    for (y = 1; y < MAX_Y - 2; y++) {
        for (x = 1; x < MAX_X - 2; x++) {
            if ((map[y][x] == map[y-1][x] && map[y][x] == map[y+1][x]) ||
                (map[y][x] == map[y][x-1] && map[y][x] == map[y][x+1])) {
                flg = FLG_ON;
                printf("x = %d y = %d\n", x, y);
                x = MAX_X - 2;
                y = MAX_Y - 2;
            }
        }
    }
    if (flg == FLG_ON) {
        printf("消せるところがあります。\n");
    } else {
        printf("消せるところがありません。\n");
    }
    return 0;
}





この投稿にコメントする

削除パスワード

No.28227

Re:パズルゲームのアルゴリズムについて
投稿者---nano(2006/09/20 15:57:38)


へろりさんの意図とは少し違うような気が…。
というわけで、少し修正してみました。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_X   (10)
#define MAX_Y   (10)
#define FLG_ON  (1)
#define FLG_OFF (0)

int main(void)
{
    int map[MAX_Y][MAX_X];
    int x, y;
    int flg;
    
    // 初期化
    srand((unsigned int) time(NULL));
    for (y = 0; y < MAX_Y; y++) {
        for (x = 0; x < MAX_X; x++) {
            if ((1 <= y && y <= MAX_Y - 2) && (1 <= x && x <= MAX_X - 2))
                map[y][x] = rand() % 8;
            else
                map[y][x] = -1;
            printf("%3d", map[y][x]);
        }
        printf("\n");
    }
    
    // マスを判定
    flg = FLG_OFF;
    for (y = 1; y <= MAX_Y - 2; y++) {
        for (x = 1; x <= MAX_X - 2; x++) {
            int t;
            
            if (((t = map[y-1][x]) == map[y+1][x]) && (t != map[y][x]) &&
                (t == map[y][x-1] || t == map[y][x+1])) {
                flg = FLG_ON;
                printf("x = %d y = %d\n", x, y);
            }
            if (((t = map[y][x-1]) == map[y][x+1]) && (t != map[y][x]) &&
                (t == map[y-1][x] || t == map[y+1][x])) {
                flg = FLG_ON;
                printf("x = %d y = %d\n", x, y);
            }
        }
    }
    if (flg == FLG_ON)
        printf("置き換えて消せるところがあります。\n");
    else
        printf("置き換えても消せるところがありません。\n");
    return 0;
}




この投稿にコメントする

削除パスワード

No.28229

Re:パズルゲームのアルゴリズムについて
投稿者---nano(2006/09/20 16:27:36)


円零さんの考え方に従うと、このアルゴリズムではまだ不足です。
置き換えて消せる他のケースを見落としていますね。


この投稿にコメントする

削除パスワード

No.28230

Re:パズルゲームのアルゴリズムについて
投稿者---気分屋(2006/09/20 16:34:58)


>へろりさんの意図とは少し違うような気が…。
失礼しました。
置き換えて消せるパターンがあるかないかでしたね(汗


この投稿にコメントする

削除パスワード

No.28231

Re:パズルゲームのアルゴリズムについて
投稿者---へろり(2006/09/21 08:05:59)


早レスありがとうございます。

ソースを読ませて頂きました。 全てのマスを縦の並びのパターンと横の並びのパターンを
総当たりで解くのですね。 最大でもたかだか8X8マス数の比較ですから、これで行けそうです。

お付き合い戴きありがとうございました。


この投稿にコメントする

削除パスワード

No.28228

Re:パズルゲームのアルゴリズムについて
投稿者---円零(2006/09/20 16:10:22)


一つ置き換えると消せるパターンはいくつかありますが、
端からサーチしていく方法を採る場合は、AAのような2つ連続した形か、
AXAのような一つ間を置いて並んだ形を取っ掛かりにすると良いと思われます。

さて、行を端から見ていくとした場合、前者で引っかかる場合と後者で引っかかる場合に二分できます。
仮に、前者のパターン
A           A
XAA  XAA  AAX  AAXA  AAX
     A                A
をパターン1とし、後者のパターン
       A
AXAA  AXA  AXA
            A
をパターン2としましょう。
(列でサーチする場合には上記を90度回したパターン。)

そこで、キャラクタが3つ入るバッファを用意して、全ての行と全ての列に対して、

・[   ]:次の文字を読み込む
・[A  ]:次の文字を読み込む
・[AA ]:Aについて、パターン1で判定。
     該当すれば終了、さもなければバッファクリア
・[AB ]:次の文字を読み込む
・[ABA]:Aについて、パターン2で判定。
     該当すれば終了、さもなければ[BA ]のようにずらす
・[ABB]:Bについて、パターン1で判定。
     該当すれば終了、さもなければバッファクリア
・[ABC]:[BC ]のようにずらす

のような処理を行なえば良さそうです。
実際のコードで検証してはいませんが、どうでしょうか。



この投稿にコメントする

削除パスワード

No.28232

Re:パズルゲームのアルゴリズムについて
投稿者---へろり(2006/09/21 08:25:58)


>そこで、キャラクタが3つ入るバッファを用意して、全ての行と全ての列に対して、

ちょっと分からないのですが、これはバッファを利用するメリットと言うのは何でしょう。
判定を行う列・行の各マス目へのポインタではダメなのですか?
これですと、バッファをシフトする場合も、ポインタを1つずらすだけで事足ります。

>のような処理を行なえば良さそうです。
>実際のコードで検証してはいませんが、どうでしょうか。

記号「?」を不定のキャラクターとするならば、AA?A 等といったパターンをマッチングさせる
オートマトンを作成するという事ですか。

ちょっとやってみます。 ありがとうございました。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧