日経ソフトウェア2024年2・3月号掲載「C言語で弾幕系シューティングゲーム」を拝読しDXライブラリの使い方が少しだけ理解できたので、それを用いた迷路作成と探索に挑戦しました。どうせならと、以前投稿したArduino版の「穴掘り法」とはあえて違う「壁伸ばし法」で迷路を作成しました。
先ずは「壁伸ばし法」の実装例を探しました。Python、C#、C++などの例は見つかりますが、今更70過ぎの私の頭で理解できるはずもなく計画倒れになりそうでした。しかし、伝説的な名著「奥村晴彦著 C言語による最新アルゴリズム事典(1991版)」（以下、アルゴリズム事典と呼ぶ）を再発見（以前所有のモノは残念ながら処分してました）、その中に簡潔かつ優れた方法が載ってましたので使わせていただきました。
さて、今回のポイントは次の４つです。
１．DXライブラリで動きを付ける
２．C言語で作成
３．壁伸ばし法で迷路を作成する
４．迷路探索のスタートとゴールはデフォルトで左上と右下だが、画面上をマウスクリックして選べるように工夫した。ただし、有らぬ場所を選んだ場合の補償はしない。
Visual Studio 2022 で、DXライブラリを使えるようにするまでは次のサイトをご覧ください。
細かい注意点はいろいろありますが、一つだけ私もハマったところを紹介します。
『アプリケーションの種類(T)』の項目を
『デスクトップ アプリケーション (.exe)』にする
間違えて『コンソール アプリケーション (.exe)』にしない！
迷路作成において、「アルゴリズム事典」掲載のプログラムでは周囲の壁にそって通路が作られ易く、結果として単純になりがちなのでそこを私なりに直しました。以下にコードを示します。一応、「C++」ファイルにしていますが、中身はCそのものです。
main.cpp
#include "DxLib.h"
#include <time.h>
#define XMAX 60 // 偶数
#define YMAX 40 // 偶数
#define MAXSITE (XMAX * YMAX / 4)
const int Y0 = 20;
int map[XMAX + 1][YMAX + 1];
int nsite = 0;
int xx[MAXSITE], yy[MAXSITE];
int dx[4] = { 2, 0,-2, 0 };
int dy[4] = { 0, 2, 0,-2 };
int SX = 3, SY = 3; // スタート奇数
int GX = XMAX - 3, GY = YMAX - 3;// ゴール奇数
bool a;// ゴール到達フラッグ
unsigned int W = GetColor(255, 255, 255); // WinMain内からここに移動
unsigned int WG = GetColor(190, 190, 190);
unsigned int BK = GetColor(0, 0, 0);
unsigned int BL = GetColor(100, 100, 255);
unsigned int R = GetColor(255, 100, 100);
unsigned int Y = GetColor(255, 255, 100);
int dirtable[24][4] = {
0,1,2,3, 0,1,3,2, 0,2,1,3, 0,2,3,1, 0,3,1,2, 0,3,2,1,
1,0,2,3, 1,0,3,2, 1,2,0,3, 1,2,3,0, 1,3,0,2, 1,3,2,0,
2,0,1,3, 2,0,3,1, 2,1,0,3, 2,1,3,0, 2,3,0,1, 2,3,1,0,
3,0,1,2, 3,0,2,1, 3,1,0,2, 3,1,2,0, 3,2,0,1, 3,2,1,0 };
void add(int i, int j) { // 壁の起点となる柱（サイト）を順次加えていく
xx[nsite] = i;
yy[nsite] = j;
nsite++;
}
int select(int* i, int* j) { // 壁の起点を選ぶ
if (nsite == 0) return 0;
nsite--;
int r;
r = (int)( nsite * rand() / (RAND_MAX + 1.0));
*i = xx[r];
*j = yy[r];
// 周囲の壁から伸びる確率を上げるため、swap仕様から前に詰める仕様に変更
// xx[r]=xx[nsite];
// yy[r]=yy[nsite];
for (int k = r; k < nsite; k++) {
xx[k] = xx[k+1]; // 前に詰める
yy[k] = yy[k+1]; // <- yy[r]=yy[nsite]
}
return 1;
}
/*経路探索*/
void Root(int x, int y) {
map[x][y] = 2; // まずは経路とする
DrawString(10 * x, Y0 + 10 * y, "+", Y);
if (x == GX && y == GY) {
a = true; // ゴール到達。探索終了
ScreenFlip();
}
if (a == false && map[x][y - 1] == 0) Root(x, y - 1); // 上
if (a == false && map[x][y + 1] == 0) Root(x, y + 1); // 下
if (a == false && map[x - 1][y] == 0) Root(x - 1, y); // 左
if (a == false && map[x + 1][y] == 0) Root(x + 1, y); // 右
if (a == false) { // ゴールではないし、袋小路
map[x][y] = 0; // 経路から外す
DrawString(10 * x, Y0 + 10 * y, "+", BK); // DxLib が Root() 内でも使える
WaitTimer(100);
ScreenFlip();
}
}
int WINAPI WinMain(_In_ HINSTANCE hInstance, _In_opt_ HINSTANCE hPrevInstance, _In_ LPSTR lpCmdLine, _In_ int nShowCmd)
{
int i, j, i1, j1, d, t, *tt;
ChangeWindowMode(TRUE), DxLib_Init(), SetDrawScreen(DX_SCREEN_BACK);
SetMainWindowText("Dxlib Hello Maze. 標準で640×480 [SetGraphMode()で変更可能]");
int Font0= CreateFontToHandle("ＭＳ ゴシック", 14, 1, DX_FONTTYPE_NORMAL);
DrawStringToHandle(5, 4, "迷路の作成と探求", W, Font0);
SetFontSize(11);
for (j = 0; j <= YMAX; j++) {
for (i = 0; i <= XMAX; i++) {
map[i][j] = 1;
DrawString(10 * i, Y0 + 10 * j, "■", W);
}
}
for (j = 3; j <= YMAX - 3; j++) {
for (i = 3; i <= XMAX - 3; i++) {
map[i][j] = 0;
DrawString(10 * i, Y0 + 10 * j, "■", BK);
}
}
SetFontSize(11);
// 壁伸ばしの起点となる周囲の壁の(偶数,偶数)点（柱）をリストアップ
for (i = 4; i <= XMAX - 4; i += 2) {
add(i, 2);
DrawString(i * 10, Y0 + 2 * 10, "■", WG);
}
for (j = 4; j <= YMAX - 4; j += 2) {
add(2, j);
DrawString(2 * 10, Y0 + j * 10, "■", WG);
}
for (i = 4; i <= XMAX - 4; i += 2) {
add(i, YMAX - 2);
DrawString(i * 10, Y0 + (YMAX - 2) * 10, "■", WG);
}
for (j = 4; j <= YMAX - 4; j += 2) {
add(XMAX - 2, j);
DrawString((XMAX - 2) * 10, Y0 + j * 10, "■", WG);
}
DrawString(147, 5, "Remaining Columns=", WG);
srand((unsigned)time(NULL));
while (select(&i, &j)) { // 迷路作成
char ns[4],si[3],sj[3];
sprintf_s(ns, "%d", nsite); sprintf_s(si, "%d", i); sprintf_s(sj, "%d", j);
DrawBox(280, 5, 600, 20, BK, true);
DrawString(280, 5, ns, WG);
DrawString(310, 5, si, W);
DrawString(340, 5, sj, W);
ScreenFlip();
for (int n=0; n < 11; n++) { // n=10 までで止める。壁が短いほうが変化に富むと思われる
tt = dirtable[(int)(24 * (rand() / (RAND_MAX + 1.0)))];
for (d = 3; d >= 0; d--) {
t = tt[d];
i1 = i + dx[t];
j1 = j + dy[t];
if (map[i1][j1] == 0)break;
}
if (d < 0)break;
map[(i + i1) / 2][(j + j1) / 2] = 1;
DrawString(10 * (i + i1) / 2, Y0 + 10 * (j + j1) / 2, "■", W);
WaitTimer(50);
ScreenFlip();
map[i1][j1] = 1;
DrawString(10 * i1, Y0 + 10 * j1, "■", WG);
WaitTimer(50);
ScreenFlip();
i = i1; j = j1;
add(i, j);
}
ScreenFlip();
}
ScreenFlip();
SetMainWindowText("スタート地点をマウスでクリック");
int SXbuf, SYbuf,GXbuf,GYbuf;
SetFontSize(12);
while (1) {
if (GetMouseInput() & MOUSE_INPUT_LEFT) {
GetMousePoint(&SXbuf, &SYbuf);
SX = (int)(SXbuf / 10);
SY = (int)((SYbuf - Y0) / 10); break;
}
}
map[SX][SY] = 0; // Start point
DrawString(10 * SX + 2, Y0 + 10 * SY, "S", BL);
ScreenFlip();
SetMainWindowText("スペースキーでゴール地点の選択へ");
while (!CheckHitKey(KEY_INPUT_SPACE)) {;}
SetMainWindowText("ゴール地点をマウスでクリック");
while (1) {
if (GetMouseInput() & MOUSE_INPUT_LEFT) {
GetMousePoint(&GXbuf, &GYbuf);
GX = (int)(GXbuf / 10);
GY = (int)((GYbuf - Y0) / 10); break;
}
}
map[GX][GY] = 0; // Goal
DrawString(10 * GX + 2, Y0 + 10 * GY, "G", R);
ScreenFlip();
SetMainWindowText("リターンキーで探索開始");
while (!CheckHitKey(KEY_INPUT_RETURN)) {;}
a = false; // ゴール未到達
Root(SX, SY); // スタート(SX,SY)から探索開始
SetMainWindowText("探索終了");
while (1) {
if (ProcessMessage() == -1)break;
if (CheckHitKey(KEY_INPUT_ESCAPE) != 0) break;
}
DxLib_End();
return 0;
}
迷路探索関数の Root() は以前のArduino版がほとんどそのまま動きました。もっと驚いたのは、グラフィックや時間関連がサブルーチン(古いですね）の中でも普通に動作する、オブジェクト化されていないと思われることです。私にとってはラッキーでしたが。
最後までご覧いただき有難うございました。