stackprobe7s_memo

何処にも披露する見込みの無いものを書き落とす場所

ポインタ

C言語のポインタってこんなことできるんだよという大人気ないこのコードを披露する機会は一生やってこないと思ったのでここに残しておく。
ちなみに、後から気づいたのだが ANSI C, Cxx などの規格的にやってはいけないことをやっている。
少なくとも 2_code, 2B_code で禁忌を侵している。(インクリメント・デクリメントした変数を同じ式内でポインタを介して再参照してはならなかったはず)
他にも何かを踏み抜いているかもしれない。
以上 2022/8/25 に追記


1_code

#include <stdio.h>

main()
{
	void *a[2];
	void ****************************************************************************************************************************p;
	void *que;

	p = (void *)a;

	a[1] = p;

	que = p[1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1]
		[1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1]
		[1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1]
		[1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1];

	printf("%p\n%p\n%p\n%p\n", a, a[1], p, que);
}

1_output

004FF860
004FF860
004FF860
004FF860

 
 
2_code

#include <stdio.h>

main()
{
	void *a[2];
	void ****p;

	p = (void *)a;

	a[0] = p;
	a[1] = p;

	++*++*p++; --*--*p--;
	++*++*p++; --*--*p--;
	++*++*p++; --*--*p--;
	++*++*p++; --*--*p--;

	printf("%p\n%p\n%p\n%p\n", a, a[0], a[1], p);
}

2_output

00D3F814
00D3F814
00D3F814
00D3F814

 
 
2B_code
https://paiza.io/projects/mRjXl_AEsvaXmI0imKoLWw (paiza.IO)

#include <stdio.h>

main()
{
	void *a[2];
	void ********************************************************************************************************************************
         ********************************************************************************************************************************p;
	void *q;

	p = (void *)a;

	a[0] = p;
	a[1] = p;

	q = *++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--
		*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--
		*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--
		*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--
		*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--
		*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--
		*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--
		*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*--*--*++*++*p++;

	printf("%p\n%p\n%p\n%p\n%p\n", a + 1, a[0], a[1], p, q);
}

2B_output

0x7ffc6fd1fe88
0x7ffc6fd1fe88
0x7ffc6fd1fe88
0x7ffc6fd1fe88
0x7ffc6fd1fe88

 
 
3_code

#include <stdio.h>

static void *f()
{
	return f;
}
main()
{
	void *(*(*(*(*(*(*(*(*(*(
         *(*(*(*(*(*(*(*(*(*(
         *(*(*(*(*(*(*(*(*(*(
         *(*(*(*(*(*(*(*(*(*(
         *(*(*(*(*(*(*(*(*(*(*p)())())())())())())())())())()
                               )())())())())())())())())())()
                               )())())())())())())())())())()
                               )())())())())())())())())())()
                               )())())())())())())())())())();
	void *q;

	p = (void *)f;

	q = p()()()()()()()()()()
         ()()()()()()()()()()
         ()()()()()()()()()()
         ()()()()()()()()()()
         ()()()()()()()()()();

	printf("%p\n%p\n%p\n", f, p, q);
}

3_output

00C21000
00C21000
00C21000

HTMLのcanvasタグ

これcanvas タグに書き直してみた。クリックすると花が避ける。





<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Shift_JIS">
<script>

console.log("花の画像に DESIGNALIKIE 様のフリーイラスト素材を使用しています。");
console.log("Flower illustrations copyright DESIGNALIKIE https://illustimage.com/");

var LoadImageRem = 0;

window.onload = function() {
	var mCanvas = document.getElementsByClassName("mCanvas")[0];
	var wiw = -1;
	var wih = -1;
	var fwh = 250;
	var stores = [];
	var k = 300;
	var rk = 0.0;
	var xk = 0.0;
	var yk = 0.0;

	var imgs = [
		"flowers/flower301-00.png", // @res
		"flowers/flower301-10.png", // @res
		"flowers/flower301-01.png", // @res
		"flowers/flower301-11.png", // @res
		"flowers/flower302-00.png", // @res
		"flowers/flower302-10.png", // @res
		"flowers/flower302-01.png", // @res
		"flowers/flower302-11.png", // @res
	];

	for(var i = 0; i < imgs.length; i++) {
		var image = new Image();

		image.addEventListener("load", function() {
			LoadImageRem--;
		});

		image.src = imgs[i];
		imgs[i] = image;

		LoadImageRem++;
	}

	for(var i = 0; i < 100; i++) {
		var store = {};

		store.r = Math.random() * 360.0;
		store.x = (window.innerWidth  - fwh) / 2.0;
		store.y = (window.innerHeight - fwh) / 2.0;
		store.mxya = 4.0 + Math.random() * 4.0;
		store.ra = (Math.random() - 0.5) * 4.0;
		store.xa = (Math.random() - 0.5) * 2.0 * store.mxya;
		store.ya = (Math.random() - 0.5) * 2.0 * store.mxya;
		store.img = imgs[Math.floor(Math.random() * 8.0)];

		stores.push(store);
	}

	SetAnimeLoop(function() {
		if(0 < LoadImageRem) {
			return;
		}

		var twiw = window.innerWidth;
		var twih = window.innerHeight;

		if(twiw != wiw || twih != wih) {
			wiw = twiw;
			wih = twih;

			mCanvas.width  = wiw;
			mCanvas.height = wih;

			mCanvas.style.left   = 0   + "px";
			mCanvas.style.top    = 0   + "px";
			mCanvas.style.width  = wiw + "px";
			mCanvas.style.height = wih + "px";
		}

		var ctx = mCanvas.getContext("2d");

		ctx.fillStyle = "#000";
		ctx.fillRect(0, 0, wiw, wih);

		var sl = -fwh;
		var st = -fwh;
		var sr = wiw;
		var sb = wih;

		for(var i = 0; i < stores.length; i++) {
			var store = stores[i];

			store.ra += (Math.random() - 0.5) * 0.15 + rk;
			store.xa += (Math.random() - 0.5) * 0.15 + xk;
			store.ya += (Math.random() - 0.5) * 0.15 + yk;

			if(4.0 < Math.abs(store.ra)) {
				store.ra *= 0.9;
			}
			if(store.mxya < Math.abs(store.xa)) {
				store.xa *= 0.9;
			}
			if(store.mxya < Math.abs(store.ya)) {
				store.ya *= 0.9;
			}

			store.r += store.ra;
			store.x += store.xa;
			store.y += store.ya;

			if(store.x < sl) {
				store.x = sr;
			}
			else if(sr < store.x) {
				store.x = sl;
			}

			if(store.y < st) {
				store.y = sb;
			}
			else if(sb < store.y) {
				store.y = st;
			}

			if(store.R < 0.0) {
				store.R += 360.0;
			}
			else if(360.0 < store.R) {
				store.R -= 360.0;
			}

			ctx.save();
			ctx.globalAlpha = 0.8;
			ctx.translate(store.x + fwh / 2.0, store.y + fwh / 2.0);
			ctx.rotate(store.r * Math.PI / 180.0);
			ctx.drawImage(store.img, -fwh / 2.0, -fwh / 2.0);
			ctx.restore();
		}

		if(1 <= k) {
			k--;
		}
		else {
			k = 300;
			rk = Math.random() < 0.1 ? 0.0 : (Math.random() - 0.5) * 0.04;
			xk = Math.random() < 0.5 ? 0.0 : (Math.random() - 0.5) * 0.04;
			yk = Math.random() < 0.5 ? 0.0 : (Math.random() - 0.5) * 0.04;
		}
	});

	document.body.onclick = function(event) {
		var x = event.pageX;
		var y = event.pageY;

		for(var i = 0; i < stores.length; i++) {
			var store = stores[i];

			var ix = store.x + fwh / 2.0;
			var iy = store.y + fwh / 2.0;

			var dx = ix - x;
			var dy = iy - y;

			var d = Math.sqrt(dx * dx + dy * dy);
			var r = 0.0;

			if(d < 1.0) {
				// noop
			}
			else if(d < 100.0) {
				r = 11.0;
			}
			else if(d < 200.0) {
				r = 9.0;
			}
			else if(d < 300.0) {
				r = 7.0;
			}
			else if(d < 400.0) {
				r = 5.0;
			}
			else if(d < 500.0) {
				r = 3.0;
			}

			dx /= d;
			dy /= d;

			dx *= r;
			dy *= r;

			store.xa += dx;
			store.ya += dy;
		}
	};
}

var AnimeFrame;
var AnimeTime = 0;

function SetAnimeLoop(f) {
	AnimeFrame = f;
	setTimeout(function() { AnimeLoop(); }, 0);
}

function AnimeLoop() {
	var currTime = new Date().getTime();

	AnimeTime = Math.max(AnimeTime, currTime - 100);
	AnimeTime = Math.min(AnimeTime, currTime + 100);

	if(AnimeTime < currTime) {
		AnimeFrame();
		AnimeTime += 16; // target to 60 hz
	}
	requestAnimationFrame(AnimeLoop);
}

</script>
<style>

body {
	background-color: #000;
	margin: 0px;
	cursor: pointer;
	user-select: none;
	touch-callout: none;
}

.mCanvas {
	position: fixed;
}

</style>
</head>
<body>
<canvas class="mCanvas">
</canvas>
</body>
</html>
  • 素材
    • 花の画像に DESIGNALIKIE 様のフリーイラスト素材を使用しています。
    • Flower illustrations copyright DESIGNALIKIE https://illustimage.com/

ラングトンのアリ

基本的なやつのみ

仕様

  • 100x100
  • 上下左右ループ
  • 背景色 = 黒
  • 動画
    • Length = 1:30
    • 20 fps
    • 100 step/frame

LangtonAnt_000.mp4

初期位置 初期方向
50, 50

http://stackprobe.ccsp.mydns.jp:58946/_rosetta/Hatena/20191107/LangtonAnt_000.mp4

LangtonAnt_001.mp4

初期位置 初期方向
30, 50
70, 50

http://stackprobe.ccsp.mydns.jp:58946/_rosetta/Hatena/20191107/LangtonAnt_001.mp4

LangtonAnt_002.mp4

初期位置 初期方向
30, 50
70, 50 ダークシアン

http://stackprobe.ccsp.mydns.jp:58946/_rosetta/Hatena/20191107/LangtonAnt_002.mp4

LangtonAnt_003.mp4

初期位置 初期方向
30, 30
70, 70

http://stackprobe.ccsp.mydns.jp:58946/_rosetta/Hatena/20191107/LangtonAnt_003.mp4

LangtonAnt_004.mp4

初期位置 初期方向
30, 30
70, 70 ダークシアン

http://stackprobe.ccsp.mydns.jp:58946/_rosetta/Hatena/20191107/LangtonAnt_004.mp4

LangtonAnt_005.mp4

初期位置 初期方向
30, 30
70, 30
30, 70
70, 70

http://stackprobe.ccsp.mydns.jp:58946/_rosetta/Hatena/20191107/LangtonAnt_005.mp4

LangtonAnt_006.mp4

  • Length = 6:00
初期位置 初期方向
30, 30 マゼンタ暗
70, 30 マゼンタやや明
30, 70 マゼンタやや暗
70, 70 マゼンタ明

http://stackprobe.ccsp.mydns.jp:58946/_rosetta/Hatena/20191107/LangtonAnt_006.mp4

16bitのRSAを実装してみる (C)

  • 昔実装した16bitのRSAが見事に間違っていたことに気付き、狼狽した勢いで書き直しました。
    • 実用性はありませんが、仕組みを理解するために作成
  • 仕様
    • 平文 ... 16ビットの符号なし整数 (或いは2バイトのデータ) とする。
      • 平文の最上位ビットを1にするなどして値の大きさを確保するらしいので、実質的には16ビット未満?

ソースコード

rsa.c

#include <stdio.h>

typedef unsigned __int8 uchar;
typedef unsigned __int32 uint;
typedef unsigned __int64 uint64;

#define SWAP(a, b) (a ^= b, b ^= a, a ^= b)

// VC ---->

#include <windows.h>
#include <wincrypt.h>

#pragma comment(lib, "ADVAPI32")

/*
	CSPRNG

	0 以上 2^16 未満の乱数を返す。
*/
static uint CRandom16(void)
{
	uchar v[2];

	{
		HCRYPTPROV hp;

		if(!CryptAcquireContext(&hp, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
			exit(1); // fatal

		if(!CryptGenRandom(hp, 2, v))
			exit(1); // fatal

		CryptReleaseContext(hp, 0);
	}

	return (uint)v[0] << 8 | v[1];
}

// <---- VC

/*
	ユークリッド互除法

	(x, y) の最大公約数を返す。
*/
static uint GCD(uint x, uint y)
{
	while(y)
	{
		x %= y;

		SWAP(x, y);
	}
	return x;
}

/*
	拡張ユークリッド互除法

	(x, y) の最大公約数を返す。

	(*a) * x + (*b) * y === GCD(x, y) (mod m) となるような (*a), (*b) をセットする。
*/
static uint ExtGCD(uint x, uint y, uint *a, uint *b, uint m)
{
	uint ret;

	if(y)
	{
		ret = ExtGCD(y, x % y, b, a, m);

		*b += m - ((uint64)(x / y) * (*a)) % m;
		*b %= m;
	}
	else
	{
		ret = x;

		*a = 1;
		*b = 0;
	}
	return ret;
}

/*
	(v ^ e) % m を返す。
*/
static uint ModPow(uint v, uint e, uint m)
{
	uint64 r;

	if(!e)
		return 1;

	r = ModPow(v, e / 2, m);
	r *= r;
	r %= m;

	if(e & 1)
	{
		r *= v;
		r %= m;
	}
	return r;
}

/*
	1 以上 2^16 未満の奇数について、素数でなければ真を返す。
*/
static int IsComposite(uint value)
{
	static uchar ops[0x1000];

#define op(p) (ops[(p) / 16] & 1 << (p) / 2 % 8)

	if(!ops[0])
	{
		uint c;
		uint d;

		ops[0] = 1;

		for(c = 3; c < 0x100; c += 2)
			if(!op(c))
				for(d = c * c / 2; d < 0x10000 / 2; d += c)
					ops[d / 8] |= 1 << d % 8;
	}
	return op(value);

#undef op
}

//
// ======================
// ==== ここから RSA ====
// ======================
//

/*
	鍵生成

	(*e) <--- 暗号鍵のext
	(*d) <--- 復号鍵のext
	(*m) <--- mod

	をそれぞれセットする。

	( (*e), (*m) ) を暗号鍵として使用する。
	( (*d), (*m) ) を復号鍵として使用する。
*/
static void GenKey(uint *e, uint *d, uint *m)
{
	uint p;
	uint q;
	uint tmp;

	do
	{
		while(p = CRandom16() | 1, IsComposite(p));
		while(q = CRandom16() | 1, p == q || IsComposite(q));
	}
	while(p * q < 0x10000);

	*m = p * q;

	p--;
	q--;

	p *= q / GCD(p, q);

	while(*e = CRandom16() | 1, IsComposite(*e) || ExtGCD(*e, p, d, &tmp, p) != 1);
}

/*
	暗号化

	p を平文 (e, m) を暗号鍵とする。
*/
static uint Enc(uint p, uint e, uint m)
{
	return ModPow(p, e, m);
}

/*
	復号

	c を暗号文 (d, m) を復号鍵とする。
*/
static uint Dec(uint c, uint d, uint m)
{
	return ModPow(c, d, m);
}

//
// ======================
// ==== ここまで RSA ====
// ======================
//

/*
	簡単なテスト
*/
static void DoTest(void)
{
	uint e;
	uint d;
	uint m;
	uint p;
	uint c;
	uint q;

	GenKey(&e, &d, &m);

	printf("暗号鍵 = %u (%u)\n", e, m);
	printf("復号鍵 = %u (%u)\n", d, m);

	p = CRandom16();

	printf("平文 = %u\n", p);

	c = Enc(p, e, m);

	printf("暗号文 = %u\n", c);

	q = Dec(c, d, m);

	printf("復号した平文 = %u\n", q);

	if(p == q)
		printf("■成功!\n");
	else
		printf("□失敗!\n");

	printf("\n");
}
int main()
{
	uint c;

	for(c = 0; c < 10; c++)
	{
		DoTest();
	}
}

実行結果 (出力例)

暗号鍵 = 40519 (850836101)
復号鍵 = 89955727 (850836101)
平文 = 31043
暗号文 = 175750552
復号した平文 = 31043
■成功!

暗号鍵 = 22447 (34618007)
復号鍵 = 9042127 (34618007)
平文 = 18870
暗号文 = 32960880
復号した平文 = 18870
■成功!

暗号鍵 = 20231 (861475339)
復号鍵 = 125032867 (861475339)
平文 = 1253
暗号文 = 221583236
復号した平文 = 1253
■成功!

暗号鍵 = 51713 (530318947)
復号鍵 = 124438833 (530318947)
平文 = 30961
暗号文 = 265166145
復号した平文 = 30961
■成功!

暗号鍵 = 15817 (1299805879)
復号鍵 = 394184833 (1299805879)
平文 = 25409
暗号文 = 254132619
復号した平文 = 25409
■成功!

暗号鍵 = 7933 (1367940043)
復号鍵 = 242017 (1367940043)
平文 = 38417
暗号文 = 226452582
復号した平文 = 38417
■成功!

暗号鍵 = 41911 (427479329)
復号鍵 = 207319555 (427479329)
平文 = 28550
暗号文 = 74597128
復号した平文 = 28550
■成功!

暗号鍵 = 5431 (847469081)
復号鍵 = 65065219 (847469081)
平文 = 52017
暗号文 = 774888864
復号した平文 = 52017
■成功!

暗号鍵 = 7309 (1558907309)
復号鍵 = 722680363 (1558907309)
平文 = 680
暗号文 = 1035114472
復号した平文 = 680
■成功!

暗号鍵 = 9221 (3715798837)
復号鍵 = 4029581 (3715798837)
平文 = 7644
暗号文 = 3582662490
復号した平文 = 7644
■成功!

平文と復号した平文が一致することしか見てないけど、ちゃんと実装できている。多分。...と思う。...と信じたい。


アルゴリズム (ほとんど自分用メモ)

鍵生成 (GenKey関数)

do
{
	while(p = CRandom16() | 1, IsComposite(p));           // p が奇素数になるまで繰り返す。
	while(q = CRandom16() | 1, p == q || IsComposite(q)); // q が p 以外の奇素数になるまで繰り返す。
}
while(p * q < 0x10000); // p * q (法n)が 16 bit に満たない場合はやり直す。
  • 異なる16ビットの奇素数を p, q とする。
*m = p * q;
  • m(法n)
p--;
q--;

p *= q / GCD(p, q);
  • (p - 1) * (q - 1) / GCD(p - 1, q - 1) を求め p にセットする。
    • 0 以上 m 未満の整数 x について x^p % m == 1 が成り立つ。⇒ 何でだっけ... ⇒ フェルマーの小定理
    • なので (n ^ (p + 1)) % m == n も成り立つ。
    • なので e * d == (p の倍数 + 1) となるような e, d を求めれば (((x ^ e) % m) ^ d) % m == x という風に使える。
      • x が平文
      • (x ^ e) % m が暗号文
while(*e = CRandom16() | 1, IsComposite(*e) || ExtGCD(*e, p, d, &tmp, p) != 1);
  • p と互いに素な e を求める。
    • 素数から選ぶのは、素数の方が p と互いに素になりやすいから?
    • だいぶ前に 3 など小さい素数が使われると聞いた気がする。(うろ覚え)
      • 暗号鍵は総当たり攻撃への耐性を求められないため、計算量を少なくした方が良いため。
    • Wikipedia によると 65537 がよく使われるらしい。
      • 使われるということは 65537 は常に p と互いに素になるってこと???
  • GCD(e, p) == 1 なので、ExtGCD の第3引数 a の指す先には e * d == (p の倍数 + 1) となるような d がセットされる。
    • (*a) * x + (*b) * y == 1 (mod m) ということは ((*a) * x) % y == 1 なので
    • 本実装における ExtGCD は (*a), (*b) に m を法とする整数をセットしてくれるので、(*a) をそのまま d として使える。

暗号化 (Enc関数)

  • 暗号文 = 平文 ^ e mod m
    • 平文は 16 ビットの符号無し整数

復号 (Dec関数)

  • 平文 = 暗号文 ^ d mod m

自動生成したRPGのダンジョンマップをゲームにしてみた (C#, DXライブラリ)

  • ダンジョンマップを自動生成するで自動生成したダンジョンマップを使ったゲームを作った。
  • 昔の3D
    • 2Dで3Dっぽく見せるやつ。真メガテンみたいな。(もちろん実装したのは迷路だけ、他の要素は何もない)
  • とりあえず動くことを目指した。ゲーム性は二の次

使っているライブラリ(ゲームエンジン)等

  1. DXライブラリ
  2. DXライブラリをラップする自作ライブラリ (C, C++)
  3. (2.) をC#に移植したもの
  4. (2.) を利用するプロジェクトのテンプレート
  5. (3.) を利用するプロジェクトのテンプレート

今回使用したのは (1.) と (3.) と (5.)

動作環境

  • Windows10

操作方法

  • キーボード
    • カーソル ... 移動・選択等
    • スペース ... プレイ中にポーズ・メニュー表示等
    • Z ... 決定
    • X ... キャンセル
    • エスケープ ... 直ちにゲーム終了
  • ゲームパッド
    • ボタンの割り当ては製品によってまちまち。ゲームパッドのボタン設定から機能を再割り当てして下さい。

素材 (敬称略)

三すくみ

二次元テーブルに (0, 1, 2) をランダムに配置して
三すくみで(じゃんけんの関係のように)侵食

  • 隣り合う2つのセルをランダムに選んで
    • 0 の隣が 1 だったら 1 を 0 にする。
    • 1 の隣が 2 だったら 2 を 1 にする。
    • 2 の隣が 0 だったら 0 を 2 にする。

というのを繰り返す。
定期的に画像に保存する。

    • 0 ⇒ シアン
    • 1 ⇒ マゼンタ
    • 2 ⇒ 黄色

保存した画像を(ちょっと拡大して)繋げて動画にすると...
http://stackprobe.ccsp.mydns.jp:58946/_rosetta/Hatena/20191031/Movie.mp4


CMYDispute()

public void CMYDispute()
{
	Random rand = new Random();

	const int w = 100;
	const int h = 100;

	int[,] map = new int[w, h];

	for (int x = 0; x < w; x++)
	{
		for (int y = 0; y < h; y++)
		{
			map[x, y] = rand.Next(3);
		}
	}
	for (int c = 0; c < 600; c++)
	{
		for (int d = 0; d < w * h; d++)
		{
			int x1 = rand.Next(w);
			int x2 = x1;
			int y1 = rand.Next(h);
			int y2 = y1;

			if (rand.Next(2) == 0)
				x2 = (x2 + 1) % w;
			else
				y2 = (y2 + 1) % h;

			if (map[x1, y1] == (map[x2, y2] + 1) % 3)
				map[x1, y1] = map[x2, y2];
			else
				map[x2, y2] = map[x1, y1];
		}
		using (Bitmap bmp = new Bitmap(w, h))
		{
			Color[] colors = new Color[]
			{
				Color.Cyan,
				Color.Magenta,
				Color.Yellow,
			};

			for (int x = 0; x < w; x++)
			{
				for (int y = 0; y < h; y++)
				{
					bmp.SetPixel(x, y, colors[map[x, y]]);
				}
			}
			bmp.Save(string.Format(@"C:\temp\{0}.bmp", c.ToString("D4"))); // 適当な場所にビットマップで保存
		}
	}
}

RPGのダンジョンマップを自動生成する(C#)

  • ダンジョンマップらしきもののときはマップが孤立した空間だらけでそのまま使えなかった。
  • なので、ちゃんとした迷路に仕立ててみる。
    • MakeLikeADungeonMap() の pattern == 24 を使用する。
    • 全ての空間を繋げて孤立を無くし、ついでにスタート地点とゴール地点を設置してみる。

ソースコード

MakeDungeonMap()

public class DungeonMapMaker
{
	/// <summary>
	/// ダンジョンマップを作る。
	/// </summary>
	/// <param name="w">マップの幅</param>
	/// <param name="h">マップの高さ</param>
	public void MakeDungeonMap(int w, int h)
	{
		Random rand = new Random();

		Map_W = w;
		Map_H = h;
		Map = MakeLikeADungeonMap(24); // pattern == 24

		OutputToImageFile(); // 初期状態

		for (; ; ) // 全ての通路を繋げる。
		{
			Point[] cps = AllClosedAreaPoints().ToArray();

			if (cps.Length == 1) // ? 全ての通路が繋がった。
				break;

			ClosedArea[] cas = AllClosedAreas(cps).ToArray();
			Array.Sort(cas, (a, b) => a.Size - b.Size); // 狭い順
			ClosedArea ca = cas[0]; // 最も狭い空間を選択
			Point[] breakingWalls = GetBreakingWalls(ca).ToArray(); // 選択された空間の破壊可能な(厚さ1枚の)壁を列挙

			if (breakingWalls.Length == 0) // ? 破壊可能な壁が無い。⇒ この空間は壁で埋める。
			{
				Fill(ca.Pt.X, ca.Pt.Y, 1);

				OutputToImageFile(); // 途中経過

				continue;
			}

			Point breakingWall = breakingWalls[rand.Next(breakingWalls.Length)]; // ランダムに選択
			Map[breakingWall.X, breakingWall.Y] = 0; // 壁を破壊

			OutputToImageFile(); // 途中経過

			Fill(breakingWall.X, breakingWall.Y, 2); // 途中経過用に塗りつぶし

			OutputToImageFile(); // 途中経過

			Fill(breakingWall.X, breakingWall.Y, 0); // 復元

			OutputToImageFile(); // 途中経過
		}

		// スタート地点とゴール地点を設置
		{
			Point[] pts = AllPoints().Where(p => Map[p.X, p.Y] == 0).ToArray();

			Point startPt = default(Point);
			Point goalPt = pts[rand.Next(pts.Length)]; // 適当な通路から開始

			for (int c = 0; c < 10; c++) // スタート地点から最も遠い場所、そこから最も遠い場所、そこから最も遠い場所 ... と何回か繰り返す。
			{
				startPt = goalPt;
				pts = Farthest(startPt);
				goalPt = pts[rand.Next(pts.Length)];
			}

			Map[startPt.X, startPt.Y] = 2; // スタート地点を設置
			Map[goalPt.X, goalPt.Y] = 2; // ゴール地点を設置
		}

		OutputToImageFile(); // 結果
	}

	private int Map_W; // マップの幅
	private int Map_H; // マップの高さ

	// Map[MAP_W, MAP_H]
	//
	// 0 ... 通路
	// 1 ... 壁
	// 2 ... スタート地点など
	//
	private int[,] Map;

	private class ClosedArea
	{
		public Point Pt;
		public int Size;
	}

	private IEnumerable<Point> GetBreakingWalls(ClosedArea ca)
	{
		Fill(ca.Pt.X, ca.Pt.Y, 2);

		OutputToImageFile(); // 途中経過

		for (int x = 1; x < Map_W - 1; x++)
		{
			for (int y = 1; y < Map_H - 1; y++)
			{
				if (
					Map[x - 1, y] == 0 ||
					Map[x + 1, y] == 0 ||
					Map[x, y + 1] == 0 ||
					Map[x, y - 1] == 0
					)
					if (
						Map[x - 1, y] == 2 ||
						Map[x + 1, y] == 2 ||
						Map[x, y + 1] == 2 ||
						Map[x, y - 1] == 2
						)
						yield return new Point(x, y);
			}
		}
		//Fill(ca.Pt.X, ca.Pt.Y, 0); // 復元
	}

	private IEnumerable<ClosedArea> AllClosedAreas(Point[] cps)
	{
		foreach (Point pt in cps)
		{
			if (Map[pt.X, pt.Y] == 0) // ? 通路
			{
				Fill(pt.X, pt.Y, 2);
				int size = AllPoints().Where(p => Map[p.X, p.Y] == 2).Count();
				Fill(pt.X, pt.Y, 0); // 復元
				yield return new ClosedArea() { Pt = pt, Size = size, };
			}
		}
		AllPoints().Where(p => Map[p.X, p.Y] == 2).ToList().ForEach(p => Map[p.X, p.Y] = 0); // 復元
	}

	private IEnumerable<Point> AllClosedAreaPoints()
	{
		foreach (Point pt in AllPoints())
		{
			if (Map[pt.X, pt.Y] == 0) // ? 通路
			{
				Fill(pt.X, pt.Y, 2);
				yield return pt;
			}
		}
		AllPoints().Where(p => Map[p.X, p.Y] == 2).ToList().ForEach(p => Map[p.X, p.Y] = 0); // 復元
	}

	private IEnumerable<Point> AllPoints()
	{
		for (int x = 0; x < Map_W; x++)
		{
			for (int y = 0; y < Map_H; y++)
			{
				yield return new Point(x, y);
			}
		}
	}

	private void Fill(int x, int y, int fillValue)
	{
		int targValue = Map[x, y];

		if (targValue == fillValue)
			throw null; // never

		Queue<Point> seekers = new Queue<Point>();

		seekers.Enqueue(new Point(x, y));

		while (1 <= seekers.Count)
		{
			Point pt = seekers.Dequeue();

			if (
				pt.X < 0 || Map_W <= pt.X ||
				pt.Y < 0 || Map_H <= pt.Y
				)
				continue;

			if (Map[pt.X, pt.Y] != targValue)
				continue;

			Map[pt.X, pt.Y] = fillValue;

			seekers.Enqueue(new Point(pt.X + 1, pt.Y));
			seekers.Enqueue(new Point(pt.X - 1, pt.Y));
			seekers.Enqueue(new Point(pt.X, pt.Y + 1));
			seekers.Enqueue(new Point(pt.X, pt.Y - 1));
		}
	}

	private Point[] Farthest(Point startPt)
	{
		// 途中経過として
		{
			Map[startPt.X, startPt.Y] = 2;
			OutputToImageFile();
			Map[startPt.X, startPt.Y] = 0; // 復元
		}

		List<Point> farthestPts = null;
		List<Point> pts = new List<Point>();

		pts.Add(startPt);

		for (; ; )
		{
			List<Point> acceptPts = new List<Point>();
			List<Point> nextPts = new List<Point>();

			foreach (Point pt in pts)
			{
				if (
					pt.X < 0 || Map_W <= pt.X ||
					pt.Y < 0 || Map_H <= pt.Y
					)
					continue;

				if (Map[pt.X, pt.Y] != 0)
					continue;

				Map[pt.X, pt.Y] = 2;

				acceptPts.Add(pt);

				nextPts.Add(new Point(pt.X + 1, pt.Y));
				nextPts.Add(new Point(pt.X - 1, pt.Y));
				nextPts.Add(new Point(pt.X, pt.Y + 1));
				nextPts.Add(new Point(pt.X, pt.Y - 1));
			}
			if (nextPts.Count == 0)
				break;

			farthestPts = acceptPts;
			pts = nextPts;
		}
		AllPoints().Where(p => Map[p.X, p.Y] == 2).ToList().ForEach(p => Map[p.X, p.Y] = 0); // 復元

		// 途中経過として
		{
			farthestPts.ForEach(p => Map[p.X, p.Y] = 2);
			OutputToImageFile();
			farthestPts.ForEach(p => Map[p.X, p.Y] = 0); // 復元
		}

		return farthestPts.ToArray();
	}

	// ----

	// 画像として出力

	private int ImageIndex = 0;

	private void OutputToImageFile()
	{
		using (Bitmap bmp = new Bitmap(Map_W, Map_H))
		{
			for (int x = 0; x < Map_W; x++)
			{
				for (int y = 0; y < Map_H; y++)
				{
					Color color;

					switch (Map[x, y])
					{
						case 0: color = Color.Gray; break;
						case 1: color = Color.Yellow; break;
						case 2: color = Color.Red; break;

						default:
							throw null; // never
					}
					bmp.SetPixel(x, y, color);
				}
			}
			bmp.Save(string.Format(@"C:\temp\{0}.bmp", (ImageIndex++).ToString("D4")), ImageFormat.Bmp); // 適当な場所にビットマップで出力する。
		}
	}

	// ----

	// マップの元 作成
	// https://stackprobe.hateblo.jp/entry/2019/10/21/011102

	private int[,] MakeLikeADungeonMap(int pattern) // pattern: 0 ~ 1023
	{
		Random rand = new Random();
		int[,] map = new int[Map_W, Map_H];

		for (int x = 0; x < Map_W; x++)
		{
			for (int y = 0; y < Map_H; y++)
			{
				map[x, y] = rand.Next(2);
			}
		}
		for (int c = 0; c < Map_W * Map_H * 30; c++)
		{
			int x = rand.Next(Map_W);
			int y = rand.Next(Map_H);
			int count = 0;

			for (int xc = -1; xc <= 1; xc++)
			{
				for (int yc = -1; yc <= 1; yc++)
				{
					count += map[(x + Map_W + xc) % Map_W, (y + Map_H + yc) % Map_H];
				}
			}
			map[x, y] = (pattern >> count) & 1;
		}
		return map;
	}

	// ----
}

出力例

  • マップの上下・左右はループしていない。
  • マップの色
    • 灰色 ... 通路
    • 黄色 ... 壁
    • 赤色 ... スタート地点またはゴール地点