ブレゼンハムのアルゴリズム

　始点と終点の間に連続した点を置き、近似的な直線を引く関数のコードを掲載します。ドキュメントは「bresenhamドキュメント」をご覧下さい。

　ブレゼンハムのアルゴリズム（Bresenham's line algorithm）は、与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズムです。

　以下のような線を引けます。

  --------------------
  --------------------
  --**----------------
  ----***-------------
  -------**-----------
  ---------***--------
  ------------***-----
  ---------------**---
  -----------------**-
  --------------------

　このアルゴリズムは、コンピュータグラフィックスの分野の最初期のアルゴリズムの1つです。コンピュータのディスプレイに直線を描画するのによく使われます。

　1962年にIBMのジャック・ブレゼンハムが開発したブレゼンハムのアルゴリズムは、シンプルかつ、整数の加減算とビットシフトのみで計算ができるので、高速に動作します。

　また、このアルゴリズムは、マス目のあるゲームで、攻撃の射線が通っているか確認するのにも利用できます。シミュレーションRPGなどで、敵が遮蔽物に隠れているか確かめたい時に、用いるとよいでしょう。

　ファイル構成は以下の通りです。>>ダウンロード

• sample/bresenham.js (※)
• sample/index.html
• sample/main.css
• sample/main.js

---

• sample/node_sample.js（Node.jsのサンプル）

※ 初期化用関数「init」の処理については「Webブラウザ/Node.js 互換関数」をご覧下さい。

サンプル動作

sample/bresenham.js

'use strict';

(function() {
	const _t = init('com.crocro.util');

	// bresenham | ブレゼンハムのアルゴリズム
	_t.bresenham = function(x0, y0, x1, y1, setPixel) {
		const dx = Math.abs(x1 - x0);
		const dy = Math.abs(y1 - y0);
		const sx = (x0 < x1) ? 1 : -1;
		const sy = (y0 < y1) ? 1 : -1;
		let err = dx - dy;

		while (true) {
			setPixel(x0, y0);
			if ((x0 == x1) && (y0 == y1)) {break}
			const e2 = err << 1;
			if (e2 > -dy) {err -= dy; x0  += sx}
			if (e2 <  dx) {err += dx; y0  += sy}
		}
	};

	// 初期化用関数
	function init(p) {
		try {return module.exports = {}} catch(e) {}
		return ((o, p) => {
			p.split('.').forEach(k => o = o[k]||(o[k]={}));
			return o})(window, p);
	};
})();

解説

　この関数は、始点「x0, y0」と終点「x1, y1」を指定して、結果を受け取る関数「setPixel」を指定して実行します。

　「setPixel」は「function(x, y)」を指定します。この関数は、始点と終点の間の直線の座標を受け取ります。この座標を利用して、直線を描画したり、ゲームの攻撃側と防御側の間に遮蔽物がないかを確認したりできます。

　以下、ある場所から、マップ上のどの場所に射線が通っているか（直線的に攻撃を加えることができるか）を確認するプログラムのサンプルです。

　20×10マスのマップで、「0」が平地、「1」が障害物です。プレイヤーは「x = 9, y = 4」のマスにいます。射線が取っていないマスを「-」、射線が取っているマスを「*」、プレイヤーがいるマスを「@」で表しています。

　こうした簡単なプログラムで、ある場所から、障害物に妨害されずに攻撃可能なマスの一覧を得られます。

sample2/node_sample.js

// モジュールの読み込み
const bresenham = require('./bresenham.js').bresenham;

// 変数の初期化
const w = 20, h = 10;
const map = 	// マップ（0は平地、1は障害物）
	  '00000000000000001000'
	+ '01101100000000111000'
	+ '01000100000000100000'
	+ '00000000000000100000'
	+ '01000100000000000000'
	+ '01101100000000000000'
	+ '00000000000111100000'
	+ '00000000000100000000'
	+ '00000000111100000000'
	+ '00000000100000000000'
	.split('');
const px = 9, py = 4;	// プレイヤーの位置
const arr = '-'.repeat(w*h).split('');	// 出力用配列

// マップを全て走査
for (let y = 0; y < h; y ++) {
	for (let x = 0; x < w; x ++) {
		// 射線が通っているかのフラグ
		let flgOk = true;

		// 射線の間に障害物「1」があるか確認
		bresenham(px, py, x, y, (x2, y2) => {
			if (map[x2 + y2 * w] === '1') {
				flgOk = false;	// 障害物
			}
		});
		if (! flgOk) {continue}	// 射線が通ってない

		// 射線が通っているので有効マスに
		arr[x + y * w] = '*';
	}
}

// 自分がいるマスの記号を変える
arr[px + py * w] = '@';

// 射線が取っているマスのマップを出力
console.log(arr.join('').replace(/(.{20})/g, '$1\n'));

　以下、出力結果です。

-----**********-----
------********------
--**--********------
--************-----*
------***@**********
------**************
----*******-----****
--*********--------*
********------------
********------------

bresenham | ブレゼンハムのアルゴリズム

引数の始点（x0, y0）と終点（x1, y1）の間に連続した点を置き、近似的な直線を引くためのアルゴリズムです。
直線は、引数のsetPixelに関数を与えることで、「function(x, y)」として、連続する座標を得ることができます。

@param {Integer} x0 - 始点のX座標。
@param {Integer} y0 - 始点のY座標。
@param {Integer} x1 - 終点のX座標。
@param {Integer} y1 - 終点のY座標。
@param {Integer} setPixel - 「function(x, y)」を引数として、始点と終点の間の直線の座標を得ます。

サンプル

// Webブラウザ
const bresenham = com.crocro.util.bresenham;
const w = 20, h = 10;
const arr = '-'.repeat(w*h).split('');
bresenham(2, 2, 18, 8, (x, y) => {
	arr[x + y * w] = '*';
});
console.log(arr.join('').replace(/(.{20})/g, '$1\n'));
//--------------------
//--------------------
//--**----------------
//----***-------------
//-------**-----------
//---------***--------
//------------***-----
//---------------**---
//-----------------**-
//--------------------

// Node.js
const bresenham = require('./bresenham.js').bresenham;
const w = 20, h = 10;
const arr = '-'.repeat(w*h).split('');
bresenham(2, 2, 18, 8, (x, y) => {
	arr[x + y * w] = '*';
});
console.log(arr.join('').replace(/(.{20})/g, '$1\n'));
//--------------------
//--------------------
//--**----------------
//----***-------------
//-------**-----------
//---------***--------
//------------***-----
//---------------**---
//-----------------**-
//--------------------

sample/index.html

<!DOCTYPE html>
<html lang="ja">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <title>ブレゼンハムのアルゴリズム - JavaScript実用サンプルコード解説付き</title>

    <script src="https://ajax.googleapis.com/ajax/libs/jquery/3.3.1/jquery.min.js">
    </script>

    <script src="bresenham.js"></script>
    <script src="main.js"></script>
    <link rel="stylesheet" href="main.css">
  </head>
  <body>
    <textarea id="src"></textarea>
    <button id="exec">実行</button>
    <textarea id="dst"></textarea>
  </body>
</html>

sample/main.js

'use strict';

$(function() {
	// 変数の初期化
	const $src  = $('#src');
	const $dst  = $('#dst');
	const $exec = $('#exec');

	// 値のセット
	$src.val(String.raw`
const bresenham = com.crocro.util.bresenham;
const w = 20, h = 10;
const arr = '-'.repeat(w*h).split('');
bresenham(2, 2, 18, 8, (x, y) => {
	arr[x + y * w] = '*';
});
console.log(arr.join('').replace(/(.{20})/g, '$1\n'));
	`.trim());

	// コンソール ログのラップ
	const log = console.log;
	console.log = function() {
		for (let i = 0; i < arguments.length; i ++) {
			$dst.append(arguments[i] + ' ');
		}
		$dst.append('\n');
		log.apply(console, arguments);
	};

	// クリック時の処理
	$exec.click(() => {
		$dst.empty();
		eval($src.val());
	});
});

sample/main.css

html,
body {
	margin: 0;
	padding: 0;
}

textarea,
button {
	box-sizing: border-box;
	width: 100%;
	vertical-align:bottom;
}
textarea {
	height: 8em;
}

sample/node_sample.js

// モジュールの読み込み
const bresenham = require('./bresenham.js').bresenham;

// 実行
const w = 20, h = 10;
const arr = '-'.repeat(w*h).split('');
bresenham(2, 2, 18, 8, (x, y) => {
	arr[x + y * w] = '*';
});
console.log(arr.join('').replace(/(.{20})/g, '$1\n'));