//=============================================================================
// SA_AnotherRouteSearch.js
// ----------------------------------------------------------------------------
// Created by seea
// License: MIT License  https://opensource.org/licenses/mit-license.php
//
// Original code copyright:
//  ©2015 KADOKAWA CORPORATION./YOJI OJIMA
//
// Plugin author:
//  Contact: https://nekono.org
//
// Free of charge.
// Allow any encryption or digital rights management.
// The method of copyright notation is left to the user.
//=============================================================================
// History
// 18.0 2018/03/13 Initial release.

//=============================================================================
// 更新履歴
// 18.0 2018/03/13 初版

/*:
 * ==============================================================================
 * @plugindesc v18.0 SA Another route search
 * @author seea
 * @require rpg_core.js v1.6.0, HalfMove.js 1.11.7
 *
 * @help
 * SA Another route search -- 別の経路探索システム
 *
 * 必須 - rpg_core.js v1.6.0, HalfMove.js 1.11.7
 * 推奨 - SA_CoreSpeedImprovement.js 18.1
 *
 * RPGツクールMV標準の経路探索とは別の経路探索を導入するプラグインです。
 * MV標準の経路探索を置き換えるものです。
 * 半歩移動プラグインと組み合わせての利用に限りサポートしています。
 *
 * 8方向移動専用です。8方向移動を利用しない場合は、本プラグインは不要です。
 *
 * コアスクリプト速度改善(SA_CoreSpeedImprovement.js)と組み合わせることで
 * マウスを使って移動するときのMVの速度が大きく改善されます。
 *
 * ★プラグインの順序に注意!!
 *   プラグイン管理では、本プラグイン(SA_AnotherRouteSearch.js)が
 * 半歩移動プラグイン(HalfMove.js)よりも上に来るように登録してください。
 *   順序を逆にすると正しく動作しないことがあります。プラグインが
 * 意図した通りに動かないときは、順序を間違えていないかを確認してください。
 *
 * ★半歩移動プラグインの設定に注意!
 *   半歩移動プラグインの「8方向移動」が true になっているか確認してください。
 *
 *
 * 【補足】
 * ・本プラグインの内容がコアスクリプトに適用されることを望みます。
 *   むしろ最初からどうしてこう作らなかった？　という疑問が込められています。
 *
 * 【今後の改善予定】
 * ・マウスを使った移動の補助としては、本プラグインは十分な性能があります。
 *   課題は長距離の移動に findDirectionTo が使われた場合です。
 * ・今の実装は制限付きA-starアルゴリズムなので、計算量の爆発を防ぐため
 *   距離が長くなると探索が打ち切りになり、間違った道を選んで
 *   マップ上の袋小路に迷い込む可能性があります。
 *   別のアルゴリズムと組み合わせないと、長距離の移動に使いにくいです。
 *   障害物の大きさにもよりますが、川や水路とかあると大体引っ掛かりますね。
 *   何を持ってくるかは検討中です。わざとこの手のアルゴリズムを急所を突いて
 *   引っ掛ける迷路を持ち出されない限りは目的地に辿り着けるようにしたいです。
 *
 *
 * @param Logging level
 * @desc ログ出力量を指定します  0:No Log 1:Fatal 2:+Error 3:+Warning 4:+Info 5:+Debug
 * @default 4
 * @type number
 */

var Imported = Imported || {};
Imported.SA_AnotherRouteSearch = true;

//-----------------------------------------------------------------------------
(function() {
'use strict';

	// Get parameters
	var params = PluginManager.parameters('SA_AnotherRouteSearch');
	const paramLoggingLevel = Number(params['Logging level'] || 4);
	const LDEBUG = paramLoggingLevel >= 5 ? true : false;
	const LINFO  = paramLoggingLevel >= 4 ? true : false;
	const LWARN  = paramLoggingLevel >= 3 ? true : false;
	const LERROR = paramLoggingLevel >= 2 ? true : false;
	const LFATAL = paramLoggingLevel >= 1 ? true : false;

	// Log parameters
	if (LINFO) {
		console.log('== SA_AnotherRouteSearch ==');
		console.log('paramLoggingLevel = ' + paramLoggingLevel);
	}

	//-----------------------------------------------------------------------------
	// Game_Character
	//

	/**
	 * 次の移動方向（斜め移動を含む方向）を検索して返す  ★半歩移動(8方向移動ON)対応
	 *
	 * @param {number} goalX - X-coord of the goal
	 * @param {number} goalY - Y-coord of the goal
	 * @return {number} Return direction to
	 */
	Game_Character.prototype.findDirectionTo = function(goalX, goalY) {
		if (LDEBUG) {
			console.log('SA_AnotherRouteSearch: findDirectionTo start');
			console.log('SA_AnotherRouteSearch: start:(' + this.x + ',' + this.y + ') - goal:(' + goalX + ',' + goalY + ')');
		}

		// 経路バッファを調べる
		if (typeof this._activeRouteBuffer === 'undefined') {
			// initialize
			this._activeRouteBuffer = [];
			if (LDEBUG) {
				console.log('SA_AnotherRouteSearch: _activeRouteBuffer initialized');
			}
		} else {
			// if initialized
			if (this._activeRouteBuffer.length > 0) {
				// 経路バッファに何か残っている場合
				if (LDEBUG) {
					console.log('SA_AnotherRouteSearch: _activeRouteBuffer size:' + this._activeRouteBuffer.length);
				}
				// 経路バッファを使用して、次の行き先を決める
				var nextRoute = this._activeRouteBuffer.shift();
				while (this._activeRouteBuffer.length > 0 && nextRoute.x === this.x && nextRoute.y === this.y) {
					nextRoute = this._activeRouteBuffer.shift();
				}
				if (nextRoute.x === this.x && nextRoute.y === this.y) {
					// 行き先が見つからなかった
					if (LDEBUG) {
						console.log('SA_AnotherRouteSearch: No route');
					}
				} else {
					if (LDEBUG) {
						console.log('SA_AnotherRouteSearch: Next route:(' + nextRoute.x + ',' + nextRoute.y + ')');
					}
					var sx = $gameMap.deltaX(nextRoute.x, this.x);
					var sy = $gameMap.deltaY(nextRoute.y, this.y);
					var direction = this.getDirectionFromDelta(sx, sy);
					if (direction > 0) {
						if (LDEBUG) {
							console.log('SA_AnotherRouteSearch: findDirectionTo #4 return ' + direction + ' (Buffer)');
						}
						return direction;
					}
				}
			}
		}

		var searchLimit = this.searchLimit();
		var mapWidth = $gameMap.width();
		var nodeList = [];
		var openList = [];
		var closedList = [];
		var start = {};
		var best = start;
		var cnt_calc = 0; // ループ内の実行回数

		if (this.x === goalX && this.y === goalY) {
			if (LDEBUG) {
				console.log('SA_AnotherRouteSearch: findDirectionTo return 0 (same coord)');
			}
			return 0;
		}

		// 移動後の座標を求めるための変換テーブル
		//               (index) 0  1  2  3  4  5  6  7  8  9
		const xDirectionTable = [0, 4, 2, 6, 4, 0, 6, 4, 8, 6];
		const yDirectionTable = [0, 2, 2, 2, 4, 0, 6, 8, 8, 8];

		start.parent = null;
		start.x = this.x;
		start.y = this.y;
		start.g = 0;
		start.f = $gameMap.distance8(start.x, start.y, goalX, goalY);
		if (LDEBUG) {
			console.log('SA_AnotherRouteSearch: findDirectionTo start.f = ' + start.f);
		}
		nodeList.push(start);
		openList.push(start.y * 2 * mapWidth + start.x); // 半歩移動対応

		while (nodeList.length > 0) {
			var bestIndex = 0;
			for (var i = 0; i < nodeList.length; i++) {
				if (nodeList[i].f < nodeList[bestIndex].f) {
					bestIndex = i;
				}
			}

			var current = nodeList[bestIndex];
			var x1 = current.x;
			var y1 = current.y;
			var pos1 = y1 * mapWidth * 2 + x1;
			var g1 = current.g;

			nodeList.splice(bestIndex, 1);
			openList.splice(openList.indexOf(pos1), 1);
			closedList.push(pos1);

			if (current.x === goalX && current.y === goalY) {
				best = current;
				break;
			}

			if (g1 >= searchLimit) {
				continue;
			}

			for (var k = 1; k < 10; k++) {
				if (k === 5) {
					continue; // 何もしない
				}
				cnt_calc++;

				// 移動後の座標を求める
				var x_direction = xDirectionTable[k];
				var y_direction = yDirectionTable[k];
				//
				// 半歩移動プラグイン(HalfMove.js)と併用する前提で
				// roundXWithDirection(), roundYWithDirection() の注意点:
				//   第2引数は2,4,6,8のいずれかの値でなくてはならない。0を渡してはいけない。
				//   東に移動（X軸に変更がない場合）でも、東移動をあらわす「6」を渡す。
				var x2 = $gameMap.roundXWithDirection(x1, x_direction);
				var y2 = $gameMap.roundYWithDirection(y1, y_direction);
				var pos2 = y2 * mapWidth * 2 + x2;

				if (closedList.contains(pos2)) {
					continue;
				}
				// 斜め移動かを判定する、少々トリッキーなif文（仕様通りに動作する）
				// 丁寧に書くなら、条件式を並べたほうが良い。
				if (x_direction === y_direction) {
					// 斜め移動ではない
					if (!this.canPass(x1, y1, k)) {
						continue;
					}
				} else {
					// 斜め移動
					if (!this.canPassDiagonally(x1, y1, x_direction, y_direction)) {
						continue;
					}
				}

				var g2 = g1 + 1;
				var index2 = openList.indexOf(pos2);

				if (index2 < 0 || g2 < nodeList[index2].g) {
					var neighbor; // 隣接ノード
					if (index2 >= 0) {
						neighbor = nodeList[index2];
					} else {
						neighbor = {};
						nodeList.push(neighbor);
						openList.push(pos2);
					}
					neighbor.parent = current;
					neighbor.x = x2;
					neighbor.y = y2;
					neighbor.g = g2;
					neighbor.f = g2 + $gameMap.distance8(x2, y2, goalX, goalY);
					if (!best || neighbor.f - neighbor.g < best.f - best.g) {
						best = neighbor;
					}
				}
			}
		}

		var node = best;
		var pathsAry = []; // 経路
		while (node.parent && node.parent !== start) {
			var path = {};
			path.x = node.x;
			path.y = node.y;
			pathsAry.push(path);
			node = node.parent;
		}
		if (node) {
			pathsAry.push(node);
		}
		// 経路は goal から辿っているので、逆順にする。
		var pathsAryRev = pathsAry.reverse();
		if (LDEBUG) {
			var pathStrAry = [];
			pathsAryRev.forEach(function(path) {
				pathStrAry.push('(' + path.x + ',' + path.y + ')');
			});
			console.log('SA_AnotherRouteSearch: ' + pathStrAry.join('-'));
		}
		this._activeRouteBuffer = pathsAryRev;

		var deltaX1 = $gameMap.deltaX(node.x, start.x);
		var deltaY1 = $gameMap.deltaY(node.y, start.y);
		if (LDEBUG) {
			console.log('SA_AnotherRouteSearch: deltaX1=' + deltaX1 + ', deltaY1=' + deltaY1);
		}
		var direction = this.getDirectionFromDelta(deltaX1, deltaY1);
		if (direction > 0) {
			if (LDEBUG) {
				console.log('SA_AnotherRouteSearch: findDirectionTo #1 return ' + direction + ' (N = ' + cnt_calc + ')');
			}
			return direction;
		}

		var deltaX2 = this.deltaXFrom(goalX);
		var deltaY2 = this.deltaYFrom(goalY);
		// deltaX2, deltaY2 は goalX, goalY からの移動方向なので、符号を反転させる。
		direction = this.getDirectionFromDelta(-deltaX2, -deltaY2);
		if (direction > 0) {
			if (LDEBUG) {
				console.log('SA_AnotherRouteSearch: findDirectionTo #2 return ' + direction + ' (N = ' + cnt_calc + ')');
			}
			return direction;
		}
		if (LDEBUG) {
			console.log('SA_AnotherRouteSearch: findDirectionTo #3 return 0 (No route) (N = ' + cnt_calc + ')');
		}
		return 0;
	};

	/**
	 * Deltaの値を元に、方向を返す（汎用）
	 *
	 * @param {number} deltaX
	 * @param {number} deltaY
	 * @return {number} Return direction to
	 */
	Game_Character.prototype.getDirectionFromDelta = function(deltaX, deltaY) {
		const directionTable = [
			[7, 8, 9],
			[4, 0, 6],
			[1, 2, 3]
		];
		var snX = Math.sign(deltaX); // -1 or 0 or 1
		var snY = Math.sign(deltaY); // -1 or 0 or 1
		return directionTable[1 + snY][1 + snX];
	};

	//-----------------------------------------------------------------------------
	// Game_Map
	//

	/**
	 * 2点間の正確な距離を返す  ★半歩移動(8方向移動ON)対応
	 * 歩数は返しません。
	 *
	 * @param {number} x1
	 * @param {number} y1
	 * @param {number} x2
	 * @param {number} y2
	 * @return {number} Return distance
	 */
	Game_Map.prototype.distance8 = function(x1, y1, x2, y2) {
		var a = this.deltaX(x1, x2);
		var b = this.deltaY(y1, y2);
		return Math.sqrt(a * a + b * b);
	};

})();
