Math.sqrt関数を使わない距離計算で処理速度を向上させる【enchant.js ゲーム制作】

結論

距離計算にMath.sqrt使っていたけど、処理が重い関数なので、加減乗除で距離を求められる方法を使ったら処理速度改善した。
また、誤差評価をしたところ4%以下となった。

以下ブラウザゲームの処理速度を向上させた

ファンタジー村人一揆　フォーエバー
ブラウザゲームです。
http://hothukurou.firebird.jp/game/Tobatsu/index.html

課題

このゲームはRPGっぽいフィールドで人間と魔物が互いの拠点を攻めあうゲームである。
ライフゲームのように観戦するだけでも楽しいですが、プレイヤーも人間側のキャラクタとして転生し、戦うこともできる。

ゲーム内に登場する各キャラクタ（人間・魔物）のアルゴリズムは以下となる。

・自分から最も近い敵キャラクタ・拠点を探して、その座標を取得。
・取得した座標へ移動。

この処理を登場キャラすべてにおいて毎フレームごとに繰り返す。そして、想定フレームレートは15fps。
PCなら余裕でフレームレートを満たすことができるが、スマホで確認したところ6fpsまで低下してしまった。

解決策

毎フレーム毎の処理を減らすことで8fps位まで向上したが、さらなる改善のため、距離計測のアルゴリズム改善を試みた。
普通に計算すると、自キャラの座標を$(x_1,y_1)$ 検索対象のキャラクタ座標を$(x_2,y_2)$としたときの二点の距離は以下の式で求められる。

L=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

この時、平方根を求める関数はMath.sqrtだが、この関数は数値解析で計算する関数なので処理に時間がかかる。
以下URLを見ると、for文やwhile文を何回も回していることがわかる。

・ニュートン法で平方根を求める　（数学アルゴリズム演習ノート）
http://www.etcnotes.info/almath/mathnewton.html

処理時間削減のため、できれば加減乗除一発で答えにたどり着いてほしい。探してみたところ、あった。
どうやら最大値を求める$max()$,と最小値を求める$min()$を足し算するだけでそこそこの精度で近似できるようだ。

・平方根を使わずに高速で２点間の距離を近似する　（きしだのはてな）
http://d.hatena.ne.jp/nowokay/20120604#1338773843

maxとmin に係数をつけて、誤差が激しい部分に補正のために項を追加することで加減乗除による距離計算を行うことができる。
上記のサイトから係数を引用して以下の関数を作成した。

main.js

function CalcDistance(x, y) {
	x = Math.abs(x);
	y = Math.abs(y);
	var max = Math.max(x, y);
	var min = Math.min(x, y);
	var leng = 1007 / 1024 * max + 441 / 1024 * min;
	if (max < 16 * min) leng -= 5 / 128 * max;
	return leng;
}

実際にゲームに使用して問題がないか検証するために、誤差計算を行った。
エクセルで引数をランダムで設定して計算を行ったところ、以下となった。

誤差が4%を下回っている。

また、今回はゲーム制作なのでプレイヤーに「なんかヘンな動きしてないか」と思われなければ問題ないと考える。

実際にゲームに実装してみたところ、特に不自然な動きがなく「それっぽく見える」ため採用することにした。
結果、8fpsだったフレームレートが10fps程度まで向上した。15fpsまでは届かなかったが、処理速度が向上したことが確認できた。

#【蛇足】ゲーム制作における「それっぽく見えること」
作りたいゲームを実現するとき、完全な仕組みを作る必要はなく、「それっぽく見える」ことに全力を注ぐと簡単に作れることが多い。
例えばリバーシのAIプログラムを作るとき、複数の可能な行動から完全にランダムに１手を決定するアルゴリズムを生成しても、プレイヤーから見て面白ければ問題ない。
（しかも、可能な行動に角が含まれている時だけは必ず打つようにすれば、初心者相手だとそこそこの勝率になるらしい。）

ちなみに、任天堂から発売されたFCソフト「役満」のアルゴリズムは以下となっている。
・役満 (任天堂)　（wikipedia）
https://ja.wikipedia.org/wiki/%E5%BD%B9%E6%BA%80_(%E4%BB%BB%E5%A4%A9%E5%A0%82)

CPUは対局のアルゴリズムは持っておらず、最初からテンパイしていてプレイヤーが上がれないと適当なタイミングで上がるというからくりだった（この頃の雑誌などに掲載されていた8ビットパソコン用麻雀ゲームも、同じようなロジックを採用していた）。

この手の話はすごくロマンがあると思うので、蛇足で載せた次第。

まとめ

・Math.sqrt関数を使わず、Math.maxとMath.minを使用して距離を求める方法がある。
・ある程度の精度で良いのであれば採用の価値がある。
・ゲーム制作では「それっぽく見えること」が大事。

作成したゲーム

ファンタジー村人一揆　フォーエバー
http://hothukurou.firebird.jp/game/Tobatsu/index.html

以上です。