console
// var i;
// var j;
var target = [12, 9]; //行（从上而下）,列（从做到右），
//创建构成地图的二维数组
//画地图的函数
var dir = "";
var currentPos = [1, 1];
var mapimg = new Image();
var map = [
[3, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2],
[2, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 2],
[3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2],
[3, 3, 0, 0, 0, 0, 2, 2, 3, 3, 2, 0, 2],
[2, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 3],
[2, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 3],
[0, 0, 0, 3, 0, 0, 3, 3, 2, 2, 3, 0, 0],
[2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[3, 0, 0, 3, 3, 3, 0, 0, 3, 3, 3, 0, 3],
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3],
[2, 2, 2, 2, 2, 3, 3, 3, 0, 0, 3, 3, 3],
];
//定四个方向,这里的1或-1是相对原来位置的增量或减量，这里的数组表示的是方向，而不是位置
var dirArr = {
left: [0, -1], //[行（从上到下）,列（从左到右）]， "left":
right: [0, 1], //[行（从上到下）,列（从左到右）]，"right"
top: [-1, 0], //[行（从上到下）,列（从左到右）]， "top"
bottom: [1, 0] //[行（从上到下）,列（从左到右）]，"bottom":
}
var OBJ = {};
//可以到达结果的方案列表
const ResultTypeArray = [];
window.onload = function() {
gamemap(()=>{
createdTree(undefined, [1, 1], {});
console.log("最终方案",ResultTypeArray)
});
}
//上一级的可选方向数组
var getPrevDirArr = function(obj) {
let arr = [];
for (let v in obj) {
arr.push(v);
}
return arr;
};
var deleOption=function(dir,tmpDir){
if (dir == "left") {
delete tmpDir.right;
} else if (dir == "right") {
delete tmpDir.left;
} else if (dir == "top") {
delete tmpDir.bottom;
} else if (dir == "bottom") {
delete tmpDir.top;
}
}
///获取可能的方向
var getNextDir = function(dir, positon) {
let tmpDir = { ...dirArr };
let arr = ["left", "right", "top", "bottom"];
let pervDirArr = getPrevDirArr(positon.dir);
let prevLess=[];
for (let i = 0; i < arr.length; i++) {
if (pervDirArr.indexOf(arr[i]) == -1) {
prevLess.push(arr[i]);
}
}
deleOption(dir,tmpDir);
//上一级禁用的方向，它的下一级同样禁用
if (prevLess.length) {
for(let v=0;v<prevLess.length;v++){
delete tmpDir[prevLess[v]];
}
}
// console.log("上一个缺少的",prevLess,"当前的",dir,"最终",tmpDir,"上一个位置：",positon.pos)
return tmpDir;
}
//获取上一个位置
var getPrevPositonLessDir = function() {
}
//判断是否有下一个位置
var hasNext = function(dirObj, posPrev) {
let hasNext = false;
for (let v in dirObj) {
let pos = [Number(posPrev[0]) + Number(dirObj[v][0]), Number(posPrev[1]) + Number(dirObj[v][1])];
if (map[pos[0]] && map[pos[0]][pos[1]] === 0) {
hasNext = true;
break;
}
}
return hasNext;
};
//获取路径
var getPath = function(obj) {
let tmpObj = obj;
let currPosArr=[obj.pos];
while (tmpObj["father"]) {
currPosArr.unshift(tmpObj["father"]["pos"])
tmpObj = tmpObj["father"];
}
ResultTypeArray.push(currPosArr)
return currPosArr;
}
let t = 0;
let countResult = 0;
var createdTree = function(parent, posPrev, position) {
let dirSet = position.dir ? position.dir : dirArr;
for (let v in dirSet) {
let pos = [Number(posPrev[0]) + Number(dirSet[v][0]), Number(posPrev[1]) + Number(dirSet[v][1])];
// if (map[pos[0]] && map[pos[0]][pos[1]] === 0) {
// console.error("pos->" + v, pos, map[pos[0]][pos[1]])
// }
// console.log("countResult计算了",countResult,"次")
if (!parent) {
if (map[pos[0]] && map[pos[0]][pos[1]] === 0) {
//删除数据来源的相反方向
let t={...dirSet};
deleOption(v,t);
console.log("第一次==============",t)
OBJ[v] = {
value: map[pos[0]][pos[1]],
pos: pos,
next: {},
dir: t
};
createdTree(OBJ[v].next, pos, OBJ[v])
}
} else {
if (map[pos[0]] && map[pos[0]][pos[1]] === 0) {
t++;
let tmpDirr = getNextDir(v, position);
// console.error(`${pos[0]}-${pos[1]}的下一个位置`,tmpDirr)
//他的周围有0
let hasNextResult = hasNext(tmpDirr, pos);
parent[v] = {
value: map[pos[0]][pos[1]],
pos: pos,
next: {},
dir: tmpDirr,
father: position
};
// console.log(pos, target)
countResult++;
if (pos[0] == target[0] && pos[1] == target[1]) {
getPath(parent[v]);
//console.error(`====================OK(${countResult}) ****${pos} ====================================`);
} else if (hasNextResult) {
//console.error("countResult",countResult)
createdTree(parent[v].next, pos, parent[v])
}
}
}
}
//console.log("OBJ", OBJ, "最终方案有", ResultTypeArray)
};
/**
{
0：{
value:1,
pos[1,1],
next:{
0:{
value：0，
pos:[1,2],
next:{}
},
1:{
value:1,
pos:[1,2],
next:{}
}
}
}，
1：{
}
}
*/
//绘制地图
function gamemap(func) {
var canvas = document.getElementById("map");
var context = canvas.getContext("2d");
mapimg.src = "https://images.cnblogs.com/cnblogs_com/ducle/412065/r_map.png";
console.log("currentPos", currentPos)
if (currentPos[0] == target[0] && currentPos[1] === target[1]) {
alert("YOU WIN");
return;
}
mapimg.onload = function() {
context.fillRect(0, 0, 416, 416);
//画一个长416，宽416的矩形
console.log("map", map)
for (i = 0; i < 13; i++) {
for (j = 0; j < 13; j++) {
if (i === target[1] && j === target[0] &&
(currentPos[0] != target[0] || currentPos[1] != target[1])) {
drawTarget(i * 32, j * 32);
} else {
drawTile(i * 32, j * 32, map[j][i]);
}
}
}
//循环调用绘制地图的函数，直到画完为止
//执行程序放到最后必须堵塞绘图
setTimeout(()=>{
func();
}, 500);
}
}
function drawTile(x, y, type) {
var canvas = document.getElementById("map");
var context = canvas.getContext("2d");
context.drawImage(mapimg, type * 32, 0, 32, 32, x, y, 32, 32);
}
function drawTarget(x, y) {
var canvas = document.getElementById("map");
var context = canvas.getContext("2d");
context.fillStyle = "#FF0000";
context.fillRect(x, y, 32, 32);
context.font = '24px Arial';
context.fillStyle = '#FFF';
context.fillText('T', x + 8, y + 28);
//context.drawImage(mapimg, type * 32, 0, 32, 32, x, y, 32, 32);
}
function move() {
let currentX = currentPos[0];
let currentY = currentPos[1];
if (dir === "down" && map[currentX + 1] && map[currentX + 1][currentY] === 0) {
map[currentX + 1][currentY] = 1;
map[currentX][currentY] = 0;
currentPos = [currentX + 1, currentY];
gamemap();
} else if (dir === "top" && map[currentX - 1] && map[currentX - 1][currentY] === 0) {
map[currentX - 1][currentY] = 1;
map[currentX][currentY] = 0;
currentPos = [currentX - 1, currentY];
gamemap();
} else if (dir === "left" && map[currentX][currentY - 1] === 0) {
map[currentX][currentY - 1] = 1;
map[currentX][currentY] = 0;
currentPos = [currentX, currentY - 1];
gamemap();
} else if (dir === "right" && map[currentX][currentY + 1] === 0) {
map[currentX][currentY + 1] = 1;
map[currentX][currentY] = 0;
currentPos = [currentX, currentY + 1];
gamemap();
}
}
document.onkeydown = function(ev) {
var ev = ev || window.event;
switch (ev.keyCode) {
case 37:
case 100:
dir = "left";
move();
console.log("left")
break;
case 38:
case 104:
dir = "top";
move();
console.log("top")
break;
case 39:
case 102:
dir = "right";
move();
console.log("right")
break;
case 40:
case 98:
dir = "down";
move();
console.log("down")
break;
}
};
<canvas id="map" width="415px" height="415px" style="border: 1px solid gray;width:100%;"></canvas>
</html>