レーダーのアルゴリズムでお茶濁し

AI難しい。難しいよママン。
構成は大体決まっていて、命令を管理するステートメントと、そのステートメントを統括するルーチンと、ステートメントに与える情報。

特にややこしいのは情報で、ややこしい部分はまあいっぱいあるんだけど。

とりあえず、まず情報の作成のためにはレーダーが必要になるんだよね。
レーダーで自分の隣接地形にいるのが誰かとか、敵はどの方角かとかを調べる。
Aiは色々ややこしくてまだ一段落ついてないので、このレーダーの記事でもアップする。

レーダーとは

レーダーとは要は索敵に使うあれ。
今回は基本的に近場にあるものを優先して処理するという方針なので、近場から検索するというアルゴリズムが必要。
前優先、右回りであれば、こういう順番で探す。

□o5e□
nc16f
b4027
la38h
□k9i□

多分偉い人がもういっぱい書いてるだろうから、知ってる人は読み飛ばしてもらえれば。
一応頑張って考えはしたけど、多分俺のがベストじゃないだろうし。

レーダーのアルゴリズム

まず上で行く1-4が1回目、5-cが2回目。1-4は4個分、5-cは8個分なので、この1回に回る数ってのは、r*dだ。（r = 回転数、d = 方向数）

で、1は0から見てx+0, y-1、2はx+1, y+0、3はx+0, y+1、4はx-1,y+0だとかいう風になってくので、いったんこれをまとめてみる。

No	周	x	y
1	1	0	-1
2	1	1	0
3	1	0	1
4	1	-1	0
5	2	0	-2
6	2	1	-1
7	2	2	0
8	2	1	1
9	2	0	2
a	2	-1	1
b	2	-2	0
c	2	-1	-1
d	3	0	-3
e	3	1	-2
f	3	2	-1
g	3	3	0
h	3	2	1
i	3	1	2
j	3	0	3
k	3	-1	2
l	3	-2	1
m	3	-3	0
n	3	-2	-1
o	3	-1	-2

当たり前だけど法則として、xとyのabsをかけた合計数は周数と常に一緒のようなので、後はnの時にxが-2、yが-1になるように計算してやれば良い。

してやればいいんだけど、どうやんだべなと。
時計周りの動きを角度で計算して円形にすることも出来るけど、菱形でいいので円形だと逆におかしくなりそうだし、こういうのを用意する事にした。

var sequence = [];
if (rotateDirection == Direction.Right) {
	sequence.push({x: 0, y:-1, d:Direction.Forward});
	sequence.push({x: 1, y: 0, d:Direction.Right});
	sequence.push({x: 0, y: 1, d:Direction.Back});
	sequence.push({x:-1, y: 0, d:Direction.Left});
} else if (rotateDirection == Direction.Left) {
	sequence.push({x: 0, y:-1, d:Direction.Forward});
	sequence.push({x:-1, y: 0, d:Direction.Left});
	sequence.push({x: 0, y: 1, d:Direction.Back});
	sequence.push({x: 1, y: 0, d:Direction.Right});
//〜中略〜
switch (firstDirection) {
	case Direction.Forward:
		sequence.push({x: 0, y:-1, d:Direction.Forward});

要は0番目がx0, y-1、1番目がx1, y0とかを配列にする。
右回り左回りでちょっと違いがあったり、最初に見るのが前なのか右なのかとかでも少し違いがあるから、この順番は適当に組み替えると。

これを用意した後に、最後は計算。
計算は、こう。

r * s[i].x * (d-i) / r + r * s[i+1].x * i / r

式中のsはsequenceで、iはindex、rは回転数。

TypeScriptのコード

AIが出来たら全部出すけど、とりあえずこのレーダー部分だけを全然需要がなさそうなTypeScriptで書いてみたのがこちら。

enum Direction {
	Forward,
	Left,
	Right,
	Back,
	Enemy
}

search(firstDirection:Direction, rotateDirection:Direction, caller:any, callback:Function) {
	var sequence = [];
	if (rotateDirection == Direction.Right) {
		sequence.push({x: 0, y:-1, d:Direction.Forward});
		sequence.push({x: 1, y: 0, d:Direction.Right});
		sequence.push({x: 0, y: 1, d:Direction.Back});
		sequence.push({x:-1, y: 0, d:Direction.Left});
	} else if (rotateDirection == Direction.Left) {
		sequence.push({x: 0, y:-1, d:Direction.Forward});
		sequence.push({x:-1, y: 0, d:Direction.Left});
		sequence.push({x: 0, y: 1, d:Direction.Back});
		sequence.push({x: 1, y: 0, d:Direction.Right});
	} else
		throw "Invalid rotateDirection. (Only right or left)"
	switch (firstDirection) {
		case Direction.Forward:
			sequence.push({x: 0, y:-1, d:Direction.Forward});
		break;
		case Direction.Right:
			if (rotateDirection == Direction.Right) {
				sequence.push(sequence.shift());
			} else {
				sequence.push(sequence.shift());
				sequence.push(sequence.shift());
				sequence.push(sequence.shift());
			}
			sequence.push({x: 1, y: 0, d:Direction.Right});
		break;
		case Direction.Back:
			sequence.push(sequence.shift());
			sequence.push(sequence.shift());
			sequence.push({x: 0, y: 1, d:Direction.Back});
		break;
		case Direction.Left:
			if (rotateDirection == Direction.Right) {
				sequence.push(sequence.shift());
				sequence.push(sequence.shift());
				sequence.push(sequence.shift());
			} else {
				sequence.push(sequence.shift());
			}
			sequence.push({x:-1, y: 0, d:Direction.Left});
		break;
	}
	var power = 1;
	var pos = {x: 0, y: 0}
	do {
		var plen = power * 4;
		for (var i=0; i<plen; i++) {
			var j = i % power;
			var k = Math.floor(i / power);
			var l = power - j;

			pos = {
				x: Math.round(
					power * sequence[k].x * l / power
					+ power * sequence[k+1].x * j / power
				),
				y: Math.round(
					power * sequence[k].y * l / power
					+ power * sequence[k+1].y * j / power
				)
			}
			if ((Math.abs(pos.x)+Math.abs(pos.y)) != power)
				throw power+", "+pos.x+", "+pos.y;
			if (callback.call(caller, {
					distance: power,
					direction: j > l ? sequence[k+1].d : sequence[k].d,
					x: pos.x+this.offset.x,
					y: pos.y+this.offset.y
				}) == false)
				break;
		}
		power++;
	} while(power < 100);
}

レーダー用なので、その座標で何があるかはアプリケーション側にコールバックで戻してる。
あと、power < 100の部分は最大100マスまで走査って指定で、この辺はロボット系だとレーダー能力に変わるんじゃないかなと思われる。

適当に考えたけど、多分、一般的なアルゴリズムとそんなにずれてない、はず。

追記

すんません、レーダーのスペル間違ってました。
×lader
○rader
です。はい。

最終的にはこっちに置くので、もし必要な人いたらこっちから落としてください。
https://github.com/tsugehara/rader-ai