ダンジョン自動生成の検証

既に前回の記事からひと月半が経ちました。
なんかイラスト描くとか言ってましたが、既に打ち砕かれました。
普通に忙しいのもありますが、ある週はノロになったり別の週も体調壊したり、色々です。

さて、そういうどうでも良い話はさておき、タイトルの通りダンジョン自動生成のアルゴリズムを検証してみたという話。
前々からやってみたかったものですが、なんだかめんどくさそーとか思って手を付けてなかった部分です。
気まぐれでやる気になったのでやってみました。

アルゴリズムの選定

こういった要件で使用されるアルゴリズムは、主に「穴掘り法」と呼ばれるもの、「区域分割法」と呼ばれるものの二種類のようです。
よりマッチすると思われる後者を選択しました。

アルゴリズム解説

ということで区域分割法をベースに、自分なりに理想に近くなるようにアレンジしたものをざっくりまとめます。

空間の分割

初めに大きな空間を一つ用意し、縦横いずれかに二つに分割します。
このとき幅（縦分割の場合は高さ）は一定の範囲内でランダムとします。
求められた乱数と、元の大きさからその乱数を減算して残った分とで二つに空間になります。
その二つの空間を、また同じようにそれぞれ縦横いずれかに分割します。
そしてまた四つの空間を分割。。。
という具合に、「次に分割したら小さくなりすぎるよ」というところまで続け、分割が終わったものからリストへ放り込みます。
↓みたいな結果になります。

https://twitter.com/blackpman/status/1353821098400387074

部屋を作る

分割が終わった空間の中に収まるように、ランダムな大きさで部屋を作っていきます。
空間と部屋は必ず一対一となります。
部屋が空間の中のどの位置にあるかも、はみ出ない範囲でランダムに取ります。
↓みたいな結果になります。

https://twitter.com/blackpman/status/1354175134777503744

部屋を通路でつなげる

部屋を作っただけだと行き来ができないので、必ず全部屋に到達できるように通路でつなげてやる必要があります。
これが結構ややこしかったのですが、最終的に
・左上の部屋から全部順番に繋げていく
・一本道だとつまらないので、ランダムで余分な道を作る
というやり方を採用しました。
↓みたいな結果になります。

https://twitter.com/blackpman/status/1355135054029021187

完成

という感じで最低限の実装はできたかな、と思います。
実際はこの作り方だとえらく部屋数が少なくなってしまったり、乱数次第で微妙な結果が出たりするので要調整ということで。

ソースコード

何の整理もしていないし、変数名もあまりにいい加減ですが載せておきます。
描画はDXライブラリを使っています。

ではまたそのうち。

細々と謎の物体を制作中

さてさてだいぶお久しぶり。
相変わらずちょっと何やってんだか自分でもよくわかってませんが、毎日ちょっとずつ何かをしています。

2020/09/06の記録-キャラクターラフ、戦闘プログラム

寝落ちしました。
疲れてるのだろうか・・・。

イラスト制作

僧侶ポジションなキャラを考えた結果、こうなりました。

シスターっぽい感じです。

あとこの前描いた狼男のポーズがちょっと気に食わなかったので、

描き直しました。
また時間があるときに綺麗に描きます。

プログラム

戦闘画面処理をちまちま作っています。
そもそもどういう仕様にするかというところですが、全員のコマンドを入れてから進行ではなく、順番が来たらコマンドを入れて都度処理していくタイプにします。
これ代表的なゲームだと何なんでしょうね。
SRPGから移動取ったような感じでしょうか。

というのをどう実現するか。
1.各々が持つ素早さから計算して「行動コスト」を出す
2.全体の時間を進める
3.全体の時間と各キャラの「行動コスト」を比べ、等しいキャラからキューへ追加
みたいな感じの処理を考えています。
「行動コスト」が少ないキャラは、他のキャラが動くまでに複数動かしたりできます。
1の変換式は全く考えていません。

2020/09/05の記録-キャラクターラフとデータ設計

今日はお昼寝してないので眠いのですが、寝落ちからは逃げ切りました。
実質勝ちです。

キャラクターラフ

小豆をコトコト煮込んでる間暇だったので、キャラクターを考えていました。

チャイナな女の子を・・・描きたかったんや・・・。
ベタなところで格闘家っぽいキャラです。
名前はまだ無い。吾輩は猫ではない。
中国人ぽい可愛い名前って何でしょうね・・・。

次。

でかい武器ぶん回す系のキャラが欲しかったので。
これもまた名前はまだありません。

年齢設定とかそういうのすらふわふわしてます。
おっさんなのかお兄さんなのか・・・。

データ設計

戦闘部分の処理を作りたくて、データをどうするか考えていました。
ということでざっくり整理したエクセルのキャプチャがこちらです。

なんか微妙に矢印ズレてるけど・・・まあ気にしないことにします。

味方キャラクター

常にどこかにデータがあって、パラメータも都度変動していくものです。
装備品があったりもします。
基本的にインスタンス化してポインタを常にどこかで保持しています。

敵キャラクター

固定の初期データを戦闘開始時にマスターデータから引っ張れば良いです。
そのためポインタではなく構造体の実体から読むことになります。

そういった違いがあるため、コンストラクタはオーバーロードで2種類用意しています。
要するに両方を戦闘処理をするのに都合の良いデータにしてしまえというわけですね。
素早さによる行動順ソートなどもあるので、そのほうが都合が良いのです。
自分がよくやるパターンの設計です。

というところまで考えて今日はお開きとなります。

2020/09/04の記録-文字列置換を作ってたら寝落ち！

画像は寂しいサムネを回避するために出てきて貰ったドラゴンくん。

今日はプログラミングの日。
文字列置換処理が欲しいと思い、Cには純正で存在しないため自作していました。
途中で子供の寝かしつけをしていたら自分も寝ていました。
子持ちあるある。

私は別にものすごく出来が良いわけでもないので、とても苦労しました。
とりあえず何とか動いてるっぽいものができたのでコードをぺたぺた。

int Util::StrReplace(const char* target, const char* needle, const char* replace, char* ret, int maxSize) {
	int result = -1;

	const char* resultPtr = strstr(target, needle); // どこにあるか調べておく

	int index = 0;
	int retIndex = 0;

	while (target[index] != '\0') {
		// ヌル文字に当たるまで繰り返す
		if (&target[index] == resultPtr) {
			// 検索した結果のポインタに当たったら置き換え文字の挿入
			result = index;
		
			strncat_s(ret, maxSize, replace, sizeof(replace));

			// 検索位置をその分進める
			index += strlen(needle);
			retIndex = strlen(ret);

		} else {
			// 異なる場合は単純にコピー
			ret[retIndex] = target[index];
			++retIndex;
			++index;
		}

	}

	ret[retIndex] = '\0'; // 末尾にNULL文字を入れておく

	return result;
}

多分結構危ないコード。
例外処理とか色々足りてないと思われます。
個人使用なのであまり細かくケアするつもりはありませんが、実行環境をぶっ壊すバグだけは入れないように気を付けます。