sunny_fragranttown_theholyfarmer_2.4.3/assets/Script/Unit/AStar/AStar.js

window.AStar = {};
var Constants = require('Constants');

var startMap =
	[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,]];

//全局变量用来调整的算法
//不必要的实时使用
var map, ctx, allowDiagonals, diagonalCost, dotTiebreaker, badSorting, nodesSearched, start,

	nextDraw = [];

//初始化节点地图
AStar.Init = function init() {

	map = new Array;
	for (var i = 0; i < Constants.TileMapWith; i++) {
		map[i] = new Array;
		for (var j = 0; j < Constants.TileMapWith; j++) {
			//第三个参数 startMap[i][j]
			map[i][j] = new Node(i, j, 1);
		}
	}
	nodesSearched = 0;
	// cc.log('map', map);
}


AStar.setMapSolid = function (x, y, isSolid) {
	map[x][y].solid = isSolid;
	// if (x!==29&&x!==30&&isSolid == 0)
	// 	console.log(x, y, isSolid);
}

AStar.getMap = function () {
	return map;
}

AStar.setStart = function (value) {
	start = value;
}

// 插入排序以获得更好的优先级队列性能
Array.prototype.insertSorted = function (v, sortFn) {
	if (this.length < 1 || sortFn(v, this[this.length - 1]) >= 0) {
		this.push(v);
		return this;
	}
	for (var i = this.length - 2; i >= 0; --i) {
		if (sortFn(v, this[i]) >= 0) {
			this.splice(i + 1, 0, v);
			return this;
		}
	}
	this.splice(0, 0, v);
	return this;
}

// for comparison this insert sort uses > not >= thus inserting new nodes nearer the back
// this provides much worse searching
Array.prototype.insertSorted2 = function (v, sortFn) {
	if (this.length < 1 || sortFn(v, this[this.length - 1]) > 0) {
		this.push(v);
		return this;
	}
	for (var i = this.length - 2; i >= 0; --i) {
		if (sortFn(v, this[i]) > 0) {
			this.splice(i + 1, 0, v);
			return this;
		}
	}
	this.splice(0, 0, v);
	return this;
}
//初始化信息
// allowDiagonals true 是开启八方向，false 是开启四方向
// diagonalCost true 是对角线，false是关闭
// dotTiebreaker 
// badSorting 添加新节点或重新插入旧节点

AStar.setInitInfo = function setInfo(tallowDiagonals, tdiagonalCost, tdotTiebreaker, tbadSorting) {
	//允许对角线
	allowDiagonals = tallowDiagonals;
	//调整对角线成本
	diagonalCost = tdiagonalCost;
	//点积短路器
	dotTiebreaker = tdotTiebreaker;
	//Prefer new nodes
	//首选新节点？
	badSorting = tbadSorting;

	// cc.log('this.allowDiagonals=', allowDiagonals,
	// 	'this.diagonalCost=', diagonalCost,
	// 	'this.dotTiebreaker=', dotTiebreaker,
	// 	'this.badSorting=', badSorting)

}

//算法里面的节点
function Node(x, y, t) {
	this.x = x;
	this.y = y;
	this.solid = t;
	this.coord = x + ":" + y;
	this.neighbours = function (goal) {
		var n = [];
		var dir = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, 1], [1, -1], [-1, -1]];
		for (var i = 0; i < (allowDiagonals ? 8 : 4); ++i) {
			//判断是否在边界外
			if (this.x + dir[i][0] < 0 || this.x + dir[i][0] > Constants.TileMapWith - 1) continue;
			if (this.y + dir[i][1] < 0 || this.y + dir[i][1] > Constants.TileMapWith - 1) continue;
			var p = map[this.x + dir[i][0]][this.y + dir[i][1]];
			if (p.solid && p != goal) continue;
			n.push(p);
		}
		// console.log('neighbours', n);
		return n;
	}

}

function h(a, b) {
	var cross = 0;
	if (dotTiebreaker) {
		var dx1 = a.x - b.x
		var dy1 = a.y - b.y
		var dx2 = start.x - b.x
		var dy2 = start.y - b.y
		var cross = Math.abs(dx1 * dy2 - dx2 * dy1)
	}

	if (allowDiagonals) {
		var straight = Math.abs(Math.abs(a.x - b.x) - Math.abs(a.y - b.y));
		var diagonal = Math.max(Math.abs(a.x - b.x), Math.abs(a.y - b.y)) - straight;
		return straight + diagonalCost * diagonal + cross * 0.001;
		//return Math.max(Math.abs(a.x-b.x), Math.abs(a.y-b.y)); simple version
	}

	return Math.abs(a.x - b.x) + Math.abs(a.y - b.y) + cross * 0.001;
}

AStar.setGraphics = function (graphics) {
	ctx = graphics;
},

	AStar.pathFind = function pathFind(x, y, x2, y2) {
		nextDraw = [];
		var start = map[x][y];
		var goal = map[x2][y2];

		var closed = {};
		var open = [start];

		var g_score = {}; // 从最优路径出发的距离
		var f_score = {}; // 通过节点估计从目标到目标的距离

		g_score[start.coord] = 0;
		f_score[start.coord] = h(start, goal);

		var cameFrom = {};

		var sortFn = function (b, a) { return f_score[a.coord] - f_score[b.coord]; };

		while (open.length > 0) {
			var node = open.pop(); //F值最低的节点
			// cc.log('node==',node);
			if (node == goal) {
				var path = [goal];
				while (cameFrom[path[path.length - 1].coord]) {
					path.push(cameFrom[path[path.length - 1].coord])
				}
				return path;
			}
			closed[node.coord] = true;

			var neighbours = node.neighbours(goal);

			for (var i = 0, c = neighbours.length; i < c; ++i) {
				var next = neighbours[i];
				if (closed[next.coord]) continue;

				var diagonal = next.x != node.x && next.y != node.y;

				var temp_g_score = g_score[node.coord] + (diagonal ? diagonalCost : 1);

				// cc.log('temp_g_score',temp_g_score);
				var isBetter = false;

				var idx = open.indexOf(next);
				if (idx < 0) {
					isBetter = true;
					nodesSearched++;
				}
				else if (temp_g_score < g_score[next.coord]) {
					open.splice(idx, 1); // remove old node
					isBetter = true;
				}

				if (isBetter) {
					cameFrom[next.coord] = node;
					g_score[next.coord] = temp_g_score;
					f_score[next.coord] = g_score[next.coord] + h(next, goal);

					// add the new node or reinsert the old node
					if (badSorting) open.insertSorted2(next, sortFn);
					else open.insertSorted(next, sortFn);

					// drawing
					if (ctx) {
						var s = Math.floor(g_score[next.coord] * 4);
						ctx.fillColor = new cc.Color(255 - s, 255, s, 255);
						ctx.rect(next.x * 10, next.y * 10, 10, 10);
						ctx.stroke();
						ctx.fill();

					}

				}
			}
		}
		// fail
		return [];
	}


function setIndex(next) {

	let index = 50 * next.y + next.x;
	nextDraw.push(index);
}
function isHasIndex(next) {
	let index = 50 * next.y + next.x;
	let ishas = false;

	for (let i = 0; i < nextDraw.length; i++) {
		if (index == nextDraw[i]) {
			ishas = true;
			break;
		}
	}

	return ishas;
}

AStar.Init();