Cocos 官方国庆趣味挑战正式开启！
挑战题：
国庆出游的你，被困在了一座城堡里，请从当前位置开始，找到一条通往出口的路径。
已知城堡用一个二维矩阵组成，有的部分是墙，有的部分是路，路与路之间还有门，每扇门都在城堡的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法找到脱困的最短路径。
每个元素的值含义如下 ：0-墙，1-路，2-你的起始位置，3-迷宫出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙。
提交时间：即日起至10月7日24:00【已截止】
开奖时间：10月11日中午14:00
在评论区写下你的回答吧，不限语言，可直接帖代码。10月11日14:00，我们将抽选3位认真答题的开发者，送上 Cocos 周边盲盒。
期待各位发挥自己的聪明才智，带来多样解法！
题目是不是没有提及“死锁”的情况？例如B门锁后面是B钥匙 返回null么？
常规的BFS或A*加上几个改变：
默认地图周围一圈都是墙，因此代码中没有对范围进行检测，调用Map中的start函数开始计算，计算前需要先对Map中的map初始化
#define MAP_WIDTH 100
#define MAP_HEIGHT 100
//坐标类
class Position
{
public:
int x;
int y;
Position()
{
x = y = 0;
}
Position(int x, int y)
{
this->x = x;
this->y = y;
}
};
//行走记录点
class WalkRecord
{
public:
WalkRecord(const Position& pos)
{
currentPos.push_back(pos);
memset(arrive, 0, sizeof(arrive));
}
WalkRecord(const Position& pos, char arrive[MAP_WIDTH][MAP_HEIGHT])
{
currentPos.push_back(pos);
memcpy(this->arrive, arrive, sizeof(this->arrive));
}
WalkRecord getNext()
{
return WalkRecord(*currentPos.rbegin(), arrive);
}
//计算最小距离
int getMinDistance(const Position& start, const Position& end)
{
unsigned int** iDistance = new unsigned int*[MAP_WIDTH];
unsigned int* data = new unsigned int[MAP_WIDTH * MAP_HEIGHT];
for (int i = 0; i < MAP_WIDTH; i++)
{
iDistance[i] = data + MAP_HEIGHT * i;
}
memset(data, -1, MAP_WIDTH * MAP_HEIGHT * sizeof(data[0]));
iDistance[start.x][start.y] = 0;
_getMinDistance(start, end, iDistance, iDistance[end.x][end.y], 1);
int iMinDistance = iDistance[end.x][end.y];
delete[]data;
delete[]iDistance;
return iMinDistance;
}
std::vector<Position> currentPos; //走过的点
char arrive[MAP_WIDTH][MAP_HEIGHT]; //当前可到达的位置(0为不能到达，1为能到达)
private:
void _getMinDistance(const Position& current, const Position& end, unsigned int** iDistance, const unsigned int& iMinDistance, unsigned int step)
{
bool f[4] = { 0 };
if (arrive[current.x - 1][current.y] == 1)
{
if (iDistance[current.x - 1][current.y] > step)
{
iDistance[current.x - 1][current.y] = step;
f[0] = true;
}
}
if (arrive[current.x][current.y + 1] == 1)
{
if (iDistance[current.x][current.y + 1] > step)
{
iDistance[current.x][current.y + 1] = step;
f[1] = true;
}
}
if (arrive[current.x + 1][current.y] == 1)
{
if (iDistance[current.x + 1][current.y] > step)
{
iDistance[current.x + 1][current.y] = step;
f[2] = true;
}
}
if (arrive[current.x][current.y - 1] == 1)
{
if (iDistance[current.x][current.y - 1] > step)
{
iDistance[current.x][current.y - 1] = step;
f[3] = true;
}
}
for (int i = 0; i < 4; i++)
{
if (f[i])
{
switch (i)
{
case 0:
if (abs(current.x - 1 - end.x) + abs(current.y - end.y) + step < iMinDistance)
{
_getMinDistance(Position(current.x - 1, current.y), end, iDistance, iMinDistance, step + 1);
}
break;
case 1:
if (abs(current.x - end.x) + abs(current.y + 1 - end.y) + step < iMinDistance)
{
_getMinDistance(Position(current.x, current.y + 1), end, iDistance, iMinDistance, step + 1);
}
break;
case 2:
if (abs(current.x + 1 - end.x) + abs(current.y - end.y) + step < iMinDistance)
{
_getMinDistance(Position(current.x + 1, current.y), end, iDistance, iMinDistance, step + 1);
}
break;
case 3:
if (abs(current.x - end.x) + abs(current.y - 1 - end.y) + step < iMinDistance)
{
_getMinDistance(Position(current.x, current.y - 1), end, iDistance, iMinDistance, step + 1);
}
break;
}
}
}
}
};
//地图类
class Map
{
public:
char map[MAP_WIDTH][MAP_HEIGHT]; //地图
Position currentPos; //自己当前位置
Position endPos; //出口位置
std::map<char, Position> key_door; //钥匙和门的对应关系,键为钥匙
std::map<char, Position> keyPosition; //当前能拿到的钥匙<钥匙，坐标>
std::vector<WalkRecord> walkScheme; //最后计算出来的行走方案
unsigned int minDistance; //计算出的最小距离
//计算当前能到达的位置
void CalculationReachPosition(const Position& current, WalkRecord& wr)
{
wr.arrive[current.x][current.y] = 1;
if (map[current.x][current.y] >= 'a' && map[current.x][current.y] <= 'z')
{
//添加能到达的钥匙位置
keyPosition[map[current.x][current.y]] = current;
}
//向左
if (wr.arrive[current.x - 1][current.y] == 0)
{
char c = map[current.x - 1][current.y];
if(c == '1' || c == '3' || (c >= 'a' && c <= 'z'))
{
Position p(current.x - 1, current.y);
CalculationReachPosition(p, wr);
}
}
//向上
if (wr.arrive[current.x][current.y + 1] == 0)
{
char c = map[current.x][current.y + 1];
if (c == '1' || c == '3' || (c >= 'a' && c <= 'z'))
{
Position p(current.x, current.y + 1);
CalculationReachPosition(p, wr);
}
}
//向右
if (wr.arrive[current.x + 1][current.y] == 0)
{
char c = map[current.x + 1][current.y];
if (c == '1' || c == '3' || (c >= 'a' && c <= 'z'))
{
Position p(current.x + 1, current.y);
CalculationReachPosition(p, wr);
}
}
//向下
if (wr.arrive[current.x][current.y - 1] == 0)
{
char c = map[current.x][current.y - 1];
if (c == '1' || c == '3' || (c >= 'a' && c <= 'z'))
{
Position p(current.x, current.y - 1);
CalculationReachPosition(p, wr);
}
}
}
//初始化
void init()
{
for (int i = 0; i < MAP_WIDTH; i++)
{
for (int j = 0; j < MAP_HEIGHT; j++)
{
char c = map[i][j];
switch (c)
{
case '2':
currentPos.x = i;
currentPos.y = j;
break;
case '3':
endPos.x = i;
endPos.y = j;
break;
default:
if (c >= 'A' && c <= 'Z')
{
key_door[c - 'A' + 'a'] = Position(i, j);
}
}
}
}
minDistance = -1;
}
//调用此函数开始计算最短路径
void start()
{
init();
std::vector<WalkRecord> vecWR;
vecWR.push_back(WalkRecord(currentPos));
auto it = vecWR.rbegin();
CalculationReachPosition(currentPos, *it);
if (it->arrive[endPos.x][endPos.y] == 1)
{
walkScheme = vecWR;
minDistance = it->getMinDistance(currentPos, endPos);
}
move(vecWR, 0);
}
void move(std::vector<WalkRecord>& vecWR, int currentMoveDistance)
{
auto keyTemp = keyPosition;
auto& wr = *vecWR.rbegin();
for (auto& pair : keyTemp)
{
//走到钥匙位置的路程
unsigned int L = wr.getMinDistance(*wr.currentPos.rbegin(), pair.second) + currentMoveDistance;
if (L < minDistance)
{
char c = pair.first;
keyPosition.erase(c);
//走到钥匙位置
vecWR.rbegin()->currentPos.push_back(pair.second);
//开门
const Position& pos = key_door[c];
map[pos.x][pos.y] = '1';
bool bAlter = false;
//周围是否有能到达位置
if (wr.arrive[pos.x - 1][pos.y] == 1 || wr.arrive[pos.x][pos.y + 1] == 1
|| wr.arrive[pos.x + 1][pos.y] == 1 || wr.arrive[pos.x][pos.y - 1] == 1)
{
bAlter = true;
vecWR.push_back(wr.getNext());
auto it = vecWR.rbegin();
CalculationReachPosition(pos, *it);
if (it->arrive[endPos.x][endPos.y] == 1)
{
unsigned int L2 = it->getMinDistance(pair.second, endPos) + L;
if (L2 < minDistance)
{
walkScheme = vecWR;
minDistance = L2;
}
}
}
move(vecWR, L);
//还原
if (bAlter)
{
vecWR.pop_back();
}
vecWR.rbegin()->currentPos.pop_back();
keyPosition = keyTemp;
map[pos.x][pos.y] = c - 'a' + 'A';
}
}
}
};
class game {
getWaits(steps) {
let waits = [];
let { x, y, keys } = steps[steps.length - 1];
let pushWait = (x, y) => {
if (x < 0 || x > this.x - 1 || y < 0 || y > this.y - 1) {
return;
}
let s = this.map[x][y];
if (s === '0') {
return;
}
if (s === '3') {
waits = [{ x, y, keys, isAnswer: true }];
return true;
}
else if (s === '1') {
waits.push({ x, y, keys });
}
else if (s >= 'a' && s <= 'z') {
if (keys.includes(s)) {
waits.push({ x, y, keys });
}
else {
let _keys = [...keys];
_keys.push(s);
_keys.sort();
waits.push({ x, y, keys: _keys });
}
}
else if (s >= 'A' && s <= 'Z') {
if (keys.includes(s.toLowerCase())) {
waits.push({ x, y, keys });
}
}
}
if (pushWait(x - 1, y)) {
return waits;
}
if (pushWait(x + 1, y)) {
return waits;
}
if (pushWait(x, y - 1)) {
return waits;
}
if (pushWait(x, y + 1)) {
return waits;
}
return waits;
}
computeAnswer(allWaits) {
while (true) {
this.computeCount++;
let steps = allWaits.shift();
if (!steps) {
console.log('这个迷宫没有出口');
this.answer = [];
return;
}
let waits = this.getWaits(steps);
for (let wait of waits) {
let newSteps = [...steps, wait];
if (wait.isAnswer) {
this.answer = newSteps;
return;
}
let keyStr = JSON.stringify(wait);
if (this.allWay.has(keyStr)) {
continue;
} else {
this.allWay.set(keyStr, newSteps);
}
allWaits.push(newSteps);
}
}
}
getAnswer(map) {
this.computeCount = 0;
this.map = map.map(x => x.map(y => y));
this.x = map.length;
this.y = map[0].length;
this.allWay = new Map();
let step;
for (let x = 0; x < this.x && !step; x++) {
for (let y = 0; y < this.y && !step; y++) {
if (this.map[x][y] === '2') {
step = { x, y, keys: [] };
this.map[x][y] = '1';
}
}
}
let keyStr = JSON.stringify(step);
this.allWay.set(keyStr, []);
this.computeAnswer([[step]]);
console.log(this.answer.map(x => ({ x: x.x, y: x.y })));
console.log('计算次数： ' + this.computeCount);
}
}
let g = new game();
let map = [
['0', '1', '0', '0', '0', '0'],
['0', '1', '1', '1', '1', '0'],
['0', '1', '0', '0', '1', '0'],
['0', '1', '1', '0', '3', '0'],
['0', '0', '1', '0', '0', '0'],
['1', '1', 'B', '1', '1', '0'],
['0', '1', '0', '1', '0', '0'],
['0', 'A', '0', '0', '0', '0'],
['0', '1', '0', '0', '0', '0'],
['0', '1', '1', '1', '0', '0'],
['0', '0', '0', '1', '0', '0'],
['0', '1', '1', '1', '0', '0'],
['0', '2', '0', 'a', 'b', '0'],
]
g.getAnswer(map);先确定是用搜索来解决。
不过题目没给出问题的规模，这样就不大好评估算法的有效性。
如果用搜索解决问题，要考虑问题的状态空间大小。
假设迷宫大小是N*M，钥匙的数量是K，用(x,y,获得钥匙状态)来表示当前状态，那么状态空间大小=N*M*(2^K)。
如果取N<=100, M<=100, K<=26，这个状态空间大小数量级最大是10^11，相当恐怖，需要做一些优化
考虑到某一个时刻，我不是去拿钥匙，就是去开门，要么就是去出口，中间移动的过程是一些很次要的计算。
所以迷宫可以简化为另一个图G，G的节点只包含人(起点)、钥匙、门、出口(终点)
节点之间如果没有门、墙阻挡，则认为有路径连接。路径的长度通过朴素的迷宫BFS来求出。
迷宫转化成图的示意图如下:
K*(2^K)，远小于N*M*(2^K)
另外值得注意的是，右图中分实线和虚线两种路径
虚线部分表示这种移动方式可能导致没有钥匙开不了门，
实线部分则可以确定不需要开门或者确定有必要的钥匙。
可以用很小的代价先计算实现部分的子图，即用Dijkstra算法计算每个节点到出口的最短路径，复杂度是O(K*K)
这个数据可以作为搜索时代价函数的上界，帮助剪枝。
使用的普通的BFS算法
不过针对格子需要重复经过的问题，我用了楼层的概念。有多少种钥匙就有2^x个楼层。比如有3种钥匙abc，那么就有编号为0(000)1(001)2(010)3(011)4(100)5(101)6(110)7(111)八层楼。只要获得了某个钥匙，就会坐上电梯到对应的楼层。楼层里对应的门已经处理过了，不用再继续判断是否有钥匙。
通过这种手段，就可以达到每个格子只走一次的目的。
就像这样：
（有点像傅里叶变换，频域上的变化，最终反应到时域上）
下面是演示工具示例和代码，是html文件。可以全部复制到某个空的html文件里进行演示。
地图随机用的是递归分割法。
代码没有写注释，请见谅。
代码：楼层并不是一开始就创建完成的，是等到有需要才动态增加楼层。所以最终的楼层数量会小于2^x
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>cocos challenge</title>
</head>
<body>
<canvas id="cvs" width="500" height="500" style="border: 1px solid black;"></canvas>
<span id="console" style="position: absolute;top: 2px;"></span>
<br>
<input type="button" value="点击随机地图" onclick="drawMaze()" style="padding: 6px 50px;">
<input type="button" value="点击进行演示" onclick="showRoutes()" style="padding: 6px 50px;">
<br>
</body>
<script>
function getRoutes(mazeArray) {
const OUT_CODE = '3';
const SPAWNING_CODE = '2';
const DISABLE_CODE = '0';
const KEY_TEST = /^[a-z]$/;
const DOOR_TEST = /^[A-Z]$/;
const ROWS_AMOUNT = mazeArray.length;
const COLS_AMOUNT = mazeArray[0].length;
let curFloorCode = 0;
let firstStep = null;
let keysArray = [];
let floorsArray = [];
function Step(floorCode, rowIndex, colIndex, frontStep = null) {
this.floorCode = floorCode;
this._rowIndex = rowIndex;
this._colIndex = colIndex;
this._floor = floorsArray[floorCode] || initNewFloor(floorCode);
this._cell = this._floor[rowIndex][colIndex];
this._frontStep = frontStep;
}
Step.prototype = {
getNearCell(dRow, dCol) {
const _nearRowIndex = this._rowIndex + dRow;
if (_nearRowIndex >= ROWS_AMOUNT || _nearRowIndex < 0) return false;
const _nearColIndex = this._colIndex + dCol;
if (_nearColIndex >= COLS_AMOUNT || _nearColIndex < 0) return false;
return [this._floor[_nearRowIndex][_nearColIndex], _nearRowIndex, _nearColIndex];
},
setCellPass() {
this._cell[1] = 1;
},
getAllFrontStep() {
let _stepsArray = [[this._rowIndex, this._colIndex]];
let _step = this;
while (_step._frontStep) {
_stepsArray.push([_step._frontStep._rowIndex, _step._frontStep._colIndex]);
_step = _step._frontStep;
}
return _stepsArray.reverse();
}
}
function initFloors() {
floorsArray.push(mazeArray.map(row => row.map(col => [col, 0])));
mazeArray.forEach((row, rowIndex) => {
row.forEach((col, colIndex) => {
if (/[a-z]/.test(col) && !~keysArray.indexOf(col)) {
keysArray.push(col);
}
if (col == SPAWNING_CODE) {
firstStep = new Step(curFloorCode, rowIndex, colIndex);
}
})
})
keysArray.sort();
}
function initNewFloor(code) {
if (floorsArray[code]) return;
floorsArray[code] = mazeArray.map(row => row.map(col => {
if (DOOR_TEST.test(col) && (!!((1 << keysArray.indexOf(col.toLocaleLowerCase())) & code))) {
return ['1', 0];
}
return [col, 0];
}))
return floorsArray[code];
}
function bfs() {
const quene = [firstStep];
let _oir = [[-1, 0], [0, 1], [1, 0], [0, -1]];
while (quene.length) {
const _step = quene.shift();
_step.setCellPass();
for (let [dRow, dCol] of _oir) {
const _nearCell = _step.getNearCell(dRow, dCol);
if (_nearCell === false) continue;
const [[char, isPass], rowIndex, colIndex] = _nearCell;
if (isPass) continue;
if (char === OUT_CODE) return new Step(_step.floorCode, rowIndex, colIndex, _step);
if (char === DISABLE_CODE) continue;
if (DOOR_TEST.test(char)) continue;
if (!isPass) {
if (KEY_TEST.test(char)) quene.push(new Step(getTargetFloorCode(char, _step.floorCode), rowIndex, colIndex, _step));
else quene.push(new Step(_step.floorCode, rowIndex, colIndex, _step));
}
}
}
return false;
}
function getTargetFloorCode(keyChar, curFloorCode) {
initNewFloor(curFloorCode);
return (1 << keysArray.indexOf(keyChar)) | curFloorCode;
}
initFloors();
const _finalStep = bfs();
if (_finalStep === false) { return false }
else { return _finalStep.getAllFrontStep() };
}
</script>
<script>
function randomMaze(rowAmount, colAmount) {
const size = 20;
const ROWS_AMOUNT = rowAmount;
const COLS_AMOUNT = colAmount;
function createMaze(width, height) {
const mazeGrid = [];
for (let i = 0; i < height; i++) {
const _row = [];
for (let j = 0; j < width; j++) {
_row.push(1);
}
mazeGrid.push(_row);
}
const splitMaze = function (i, j, width, height) {
if (width <= 1 || height <= 1) return;
let crossI = Math.floor(Math.random() * ((height - 1) / 2)) * 2 + 1 + i;
let crossJ = Math.floor(Math.random() * ((width - 1) / 2)) * 2 + 1 + j;
for (let l = i; l < i + height; l++) {
mazeGrid[l][crossJ] = 0;
for (let m = j; m < j + width; m++) {
mazeGrid[crossI][m] = 0;
}
}
const arr = [
[[i, crossI - 1], crossJ],
[crossI, [crossJ + 1, j + width - 1]],
[[crossI + 1, i + height - 1], crossJ],
[crossI, [j, crossJ - 1]]].sort(() => Math.random() - 0.5);
arr.slice(0, 3).forEach(([row, col]) => {
if (Array.isArray(row)) {
let holeI = Math.floor(Math.random() * (row[1] - row[0]) / 2) * 2 + row[0];
mazeGrid[holeI][col] = 1;
} else {
let holeJ = Math.floor(Math.random() * (col[1] - col[0]) / 2) * 2 + col[0];
mazeGrid[row][holeJ] = 1;
}
})
const left_top = [i, j, crossJ - j, crossI - i];
const right_top = [i, crossJ + 1, j + width - crossJ - 1, crossI - i];
const left_bottom = [crossI + 1, j, crossJ - j, i + height - crossI - 1];
const right_bottom = [crossI + 1, crossJ + 1, j + width - crossJ - 1, i + height - crossI - 1];
splitMaze(...left_top);
splitMaze(...right_top);
splitMaze(...left_bottom);
splitMaze(...right_bottom);
}
splitMaze(0, 0, COLS_AMOUNT, ROWS_AMOUNT);
return mazeGrid;
}
const _mazeGrid = createMaze(COLS_AMOUNT, ROWS_AMOUNT);
const _colsArray = [];
let _mazeArray = _mazeGrid.map(row => row.map(col => {
if (col === 0) return '0';
const _col = ['1'];
_colsArray.push(_col);
return _col;
}))
_colsArray.sort(() => Math.random() - 0.5);
const _keysAmount = Math.min(Math.floor(_colsArray.length / 10), 10);
_colsArray[0][0] = '2';
_colsArray[1][0] = '3';
_colsArray.slice(2, 2 + _keysAmount).forEach((v, i) => v[0] = String.fromCharCode(i + 97));
_colsArray.slice(2 + _keysAmount, 2 + _keysAmount * 2).forEach((v, i) => v[0] = (String.fromCharCode(i + 97)).toLocaleUpperCase());
_mazeArray = _mazeArray.map(row => row.map(col => {
if (typeof col === 'string') return col;
return col[0];
}))
return _mazeArray;
}
</script>
<script>
let _mazeArray = null;
let _routes = null;
let _randomTimes = 0;
let _openDoorsAmount = 0;
let _interId = null;
const DFONT = 16;
const SIZE = 20;
const cvs = document.getElementById('cvs');
const ctx = cvs.getContext('2d');
const msg = document.getElementById('console');
function _drawMaze() {
ctx.beginPath();
ctx.clearRect(0, 0, 500, 500);
for (let i = 0; i < _mazeArray.length; i++) {
for (let j = 0; j < _mazeArray[i].length; j++) {
if (_mazeArray[i][j] === '0') {
ctx.fillStyle = 'black';
ctx.fillRect(j * SIZE, i * SIZE, SIZE, SIZE);
} else if (_mazeArray[i][j] === '1') {
ctx.fillStyle = 'grey';
ctx.fillRect(j * SIZE, i * SIZE, SIZE, SIZE);
} else if (/[2-3a-zA-Z]/.test(_mazeArray[i][j])) {
ctx.fillStyle = 'grey';
ctx.fillRect(j * SIZE, i * SIZE, SIZE, SIZE);
ctx.beginPath();
ctx.fillStyle = 'white';
ctx.font = "20px Consolas Consolas";
ctx.fillText(_mazeArray[i][j], j * SIZE, i * SIZE + DFONT);
}
}
}
msg.innerText = '随机次数：' + _randomTimes + '\n';
msg.innerText += '开门数：' + _openDoorsAmount + '\n';
msg.innerText += '路径长度:' + _routes.length + '\n';
msg.innerText += '------' + '\n';
}
function drawMaze() {
clearInterval(_interId);
msg.innerText = '';
while (true) {
_randomTimes++;
const _r = Math.floor(Math.random() * 10 + 2) * 2 - 1;
const _c = Math.floor(Math.random() * 10 + 2) * 2 - 1;
_mazeArray = randomMaze(_r, _c);
_routes = getRoutes(_mazeArray);
if (Array.isArray(_routes)) {
_openDoorsAmount = Array.from(new Set(_routes.map(([i, j]) => _mazeArray[i][j]))).reduce((s, char) => s += /[A-Z]/.test(char) ? 1 : 0, 0);
if (_routes.length > 10 && _openDoorsAmount > 3) break;
}
}
_drawMaze();
}
function showRoutes() {
clearTimeout(_interId);
if (Array.isArray(_routes)) {
_drawMaze();
msg.innerText += '闯入迷宫~TT' + '\n';
const _colorArray = ['green', 'blue', 'purple', 'orange', 'red', 'sienna', 'pink', 'cyan', 'gold', 'indigo', 'lime'];
const _alreadyHasKeyArray = [];
const _alreadyOpenDoorArray = [];
const _it = _routes.values();
let _index = 0;
_interId = setInterval(() => {
const _kv = _it.next();
if (_kv.done) {
clearTimeout(_interId);
msg.innerText += '走出迷宫!yeah!';
return;
};
const [i, j] = _kv.value;
const _char = _mazeArray[i][j];
ctx.fillStyle = _colorArray[_index]
if (/^[a-z]$/.test(_char) && !~_alreadyHasKeyArray.indexOf(_char)) {
_alreadyHasKeyArray.push(_char);
_index++;
msg.innerText += '拿到钥匙:' + _char + '\n';
}
ctx.fillRect(j * SIZE, i * SIZE, SIZE, SIZE);
ctx.fillStyle = 'white';
if (/^[a-zA-Z]$/.test(_char)) {
ctx.fillText(_char, j * SIZE, i * SIZE + DFONT);
if (/^[A-Z]$/.test(_char) && !~_alreadyOpenDoorArray.indexOf(_char)) {
_alreadyOpenDoorArray.push(_char);
msg.innerText += '打开门:' + _char + '\n';
}
}
if (/[2-3]/.test(_char)) {
ctx.fillText(_char, j * SIZE, i * SIZE + DFONT);
}
}, 200);
}
}
</script>
</html>
这是我的自拍：
首先，我的预想是这样的，使用 a星 算法直接逃出生天：
对应代码：
static aStarPathFind(mapData: MapData) {
const inIndex = v2(mapData.in.x, mapData.in.y)
const outIndex = v2(mapData.out.x, mapData.out.y)
console.log(`in: ${inIndex}, out: ${outIndex}`)
const map = mapData.data
const open: AStarObj[] = []
const close: AStarObj[] = []
// 曼哈顿估价法, 传入当前点与目标点, 返回估值
const manHattan = (nowPoint: Vec2, aimIndex: Vec2) => {
let dx = Math.abs(nowPoint.x - aimIndex.x)
let dy = Math.abs(nowPoint.y - aimIndex.y)
return dx + dy
}
const isInOpen = (mx: number, my: number) => {
for (let i = 0; i < open.length; i++) {
if (open[i].x === mx && open[i].y === my) {
return true
}
}
return false
}
const isInClose = (mx: number, my: number) => {
for (let i = 0; i < close.length; i++) {
if (close[i].x === mx && close[i].y === my) {
return true
}
}
return false
}
const pushInOpen = (v: Vec2, parent: AStarObj) => {
let obj = new AStarObj()
obj.x = v.x
obj.y = v.y
obj.g = manHattan(v, inIndex)
obj.h = manHattan(v, outIndex)
obj.f = obj.g + obj.h
obj.parent = parent
open.push(obj)
}
const pushInClose = (obj: AStarObj) => {
close.push(obj)
}
const aroundPos = (parent: AStarObj) => {
let dir = [[0,1],[1,0],[0,-1],[-1,0]]
for (let i = 0; i < 4; i++) {
let mx = parent.x + dir[i][0]
let my = parent.y + dir[i][1]
// 是否出界
if (mx < 0 || mx > 9 || my < 0 || my > 9) {
continue
}
// 是否为墙
if (map[mx][my] === ElementType.Wall) {
continue
}
// 是否已经在 close 中了
if (isInClose(mx, my)) {
continue
}
// 是否已经在 open 中了
if (isInOpen(mx, my)) {
continue
}
// 装入 open
pushInOpen(v2(mx, my), parent)
}
}
const findMinInOpen = () => {
let min = 999
let index = null
for (let i = 0; i < open.length; i++) {
if (open[i].f <= min) {
min = open[i].f
index = i
}
}
let obj = open.splice(index, 1)
pushInClose(obj[0])
return obj[0]
}
const startFunc = () => {
// 限制次数 500；
// 首先将小怪的位置装入 close 列表
let time = 500
let obj = new AStarObj()
obj.x = inIndex.x
obj.y = inIndex.y
obj.g = manHattan(inIndex, inIndex)
obj.h = manHattan(inIndex, outIndex)
obj.f = obj.g + obj.h
obj.parent = null
pushInClose(obj)
let temp = obj
while (true) {
time--
// 周围一圈装入 open
aroundPos(temp)
// 在 open 中找到 f 最小的，装入 close 并返回该点；
temp = findMinInOpen()
if (temp.x === outIndex.x && temp.y === outIndex.y) {
break
}
if (time <= 0) {
console.log('寻找不到')
break
}
}
// 根据 parent 最终确认路线
let l = close.length - 1
let p = close[l]
const final: AStarObj[] = []
while(p) {
final.push(p)
p = p.parent
}
// 翻转
final.reverse()
console.log(final)
return final
}
return startFunc()
}
a 星算法之前写的详细讲解：
CocosCreator之KUOKUO趣味文章：小怪会A星寻路 5
CocosCreator之KUOKUO趣味文章：小怪A星寻路详解
C 姐设置了很多的门，每个门开启需要钥匙，没办法，我只能先依照最短路径找到门，然后再去寻找对应的钥匙，因为我先前并不知道最短路径上有没有门，如果在前往门的路径中看到了钥匙，我必然会 push 到我的钥匙包中。
对算法进行修改，先是新增一个访问数组，因为 a 星寻路在搜索后不会再过去搜索，然后设置一个钥匙串数组：
寻路的过程中遇到钥匙就放入钥匙串，在寻路过程中没对应钥匙的门无法开启
遇到门就回头找钥匙
const findKeys = (nx: number, ny: number) => {
console.log(`findKeys, x:${nx}, y:${ny}`)
if (map[nx][ny] === ElementType.Key) {
// 访问过放到钥匙串中
keys.push('某个钥匙')
// 这是可以继续去寻找门前区域的其他钥匙
console.log('找到某个钥匙')
}
visit[nx][ny] = 8
let dir = [[0,1],[1,0],[0,-1],[-1,0]]
for (let i = 0; i < 4; i++) {
let mx = nx + dir[i][0]
let my = ny + dir[i][1]
// 是否出界
if (mx < 0 || mx > 9 || my < 0 || my > 9) {
continue
}
if (visit[mx][my] === 8 || map[mx][my] === ElementType.Wall || map[mx][my] === ElementType.Door) {
continue
}
findKeys(mx, my)
}
}
这样遇到门就回头搜索可把小 K 累坏了，有时候还绕出去很远，不过所幸最终能溜出去。
搜索到需要的钥匙就清空访问，并返回门处，遇到门再去搜索。
项目地址：
https://github.com/KuoKuo666/Pathfinding
https://gitee.com/kuokuo666/Pathfinding
不管怎样，我小 K 逃出来，这就去跟 C 姐要补偿礼品[手动狗头]。
则正常而言，a*算法得出的结果不一定最短
但如果F=G+H中，H恒为0的情况，则可以视作Dijkstra的一种
考虑到迷宫是二维矩阵的格式，可以定该方案作为最短路径的搜素方案
方向问题:没有定义四方向还是八方向，已四方向为例
1.正常而言，门视作可通行点，但前提是到达门时手上需要有钥匙
2.不存在先找到门，再去找钥匙的情况，路上来回的操作必定导致路径的延长
综述:进行搜索时，若遇到钥匙，则需记录已经取得的钥匙，再遇到门时，如果手上已经有对应的钥匙了，则视作可通行点，否则视作墙
class APoint {
//坐标x
x: number = -1;
//坐标y
y: number = -1;
//拥有钥匙
keys: any[] = []
//步长
step: number = 0;
//上一个点
lastPoint: APoint | undefined;
}
class Game {
public doMaze(mazes: any[][]) {
if (mazes.length == 0) {
console.error(`地图数据有误`)
return;
}
let startX: number = -1;
let startY: number = -1;
let endX: number = -1;
let endY: number = -1;
let closeMap: any[] = []
let rets: any[] = []
//遍历，确定起点和终点
for (let x = 0; x < mazes.length; x++) {
closeMap[x] = []
for (let y = 0; y < mazes[x].length; y++) {
if (mazes[x][y] == '2') {
startX = x
startY = y
}
if (mazes[x][y] == '3') {
endX = x
endY = y
}
closeMap[x][y] = 0
}
}
if (startX == -1 || startY == -1 || endX == -1 || endY == -1) {
console.error(`地图数据有误`)
return;
}
let width = mazes[0].length;
let height = mazes.length;
let opens: any[] = []
let point = new APoint()
point.x = startX;
point.y = startY;
point.keys = []
point.step = 1;
point.lastPoint = undefined;
opens.push(point)
let dirX = [0, 0, 1, -1]
let dirY = [1, -1, 0, 0]
while (opens.length) {
let pt: APoint = opens.shift()//取出距离最短的点
console.error("opes", pt)
for (let i = 0; i < 4; i++) {
let newPtx = pt.x + dirX[i];
let newPty = pt.y + dirY[i];
console.error(newPtx, newPty)
if (newPtx < 0 || newPtx >= width || newPty < 0 || newPty >= height) {
console.error("超出地图范围")
continue
}
if (closeMap[newPtx][newPty] == 1) {
console.error("已经访问过了")
continue
}
if (mazes[newPtx][newPty] == '1') {
console.log("是路")
let np = new APoint()
np.x = newPtx
np.y = newPty
np.keys = pt.keys
np.lastPoint = pt
np.step = pt.step + 1;
opens.push(np)
}
if (mazes[newPtx][newPty] == '0') {
console.error("是墙")
}
if (mazes[newPtx][newPty] >= 'a' && mazes[newPtx][newPty] <= 'z') {
console.log("是钥匙")
let np = new APoint()
np.x = newPtx
np.y = newPty
np.keys = pt.keys
np.keys.push(mazes[newPtx][newPty])//加入新钥匙
np.lastPoint = pt
np.step = pt.step + 1;
opens.push(np)
}
if (mazes[newPtx][newPty] >= 'A' && mazes[newPtx][newPty] <= 'Z') {
console.log("是门")
let bHasKey = false;
for (let key of pt.keys) {
//有门的情况下，判断有么有钥匙，有，通过，没有，视作墙
if ((mazes[newPtx][newPty].charCodeAt(0) + 32) == key.charCodeAt(0)) {
bHasKey = true;
break;
}
}
if (bHasKey) {
console.log("钥匙已经有了")
let np = new APoint()
np.x = newPtx
np.y = newPty
np.keys = pt.keys
np.lastPoint = pt
np.step = pt.step + 1;
opens.push(np)
} else {
console.error(`还没找到钥匙:${mazes[newPtx][newPty]}`)
continue
}
}
if (mazes[newPtx][newPty] == '3') {
console.log("到达终点", pt, pt.step + 1)
let np = new APoint()
np.x = newPtx
np.y = newPty
np.keys = pt.keys
np.lastPoint = pt
np.step = pt.step + 1;
rets.push(np)
break;
}
}
closeMap[pt.x][pt.y] = 1
opens.sort((a: APoint, b: APoint) => { return a.step - b.step })//排序
}
if (rets.length <= 0) {
console.error("找不到路径")
} else {
//既然是最短，可以把路径集合起来重新排序
rets.sort((a: APoint, b: APoint) => {
return a.step - b.step
})
let ret = rets.shift()//取出第一个
this.doPrintRet(ret)
}
}
public doPrintRet(ret: APoint) {
if (ret.lastPoint != undefined) {
this.doPrintRet(ret.lastPoint)
console.error(ret.x, ret.y, ret.step)
} else {
console.error(ret.x, ret.y, ret.step)
}
}
}
console.error("main strart")
let mazeArr = [
['0', '3', '0', '0', '0', '0', '0', '0', '0', '0'],
['0', '1', '0', '0', '0', '0', '0', '0', '0', '0'],
['0', '1', '1', '1', '1', '1', '0', '0', '0', '0'],
['0', '1', 'A', '1', '1', '1', '0', '0', '0', '0'],
['0', '1', '1', '0', '1', '1', '0', '0', '0', '0'],
['0', '1', '0', '0', '1', '1', '0', '0', '0', '0'],
['0', '0', '1', '1', 'a', '1', '0', '0', '0', '0'],
['0', '0', '1', '0', '0', '1', '0', '0', '0', '0'],
['0', '0', '1', '1', '1', '1', '0', '0', '0', '0'],
['0', '0', '1', '0', '0', '0', '0', '0', '0', '0'],
['0', '0', '2', '0', '0', '0', '0', '0', '0', '0'],
]
let g = new Game()
g.doMaze(mazeArr)
感谢参与国庆趣味挑战！请【私信】C 姐，留下您的联系方式（收件人、手机、收件地址），我们将送上 Cocos 周边盲盒1份！
感谢参与国庆趣味挑战！请【私信】C 姐，留下您的联系方式（收件人、手机、收件地址），我们将送上 Cocos 周边盲盒1份！
感谢参与国庆趣味挑战！请【私信】C 姐，留下您的联系方式（收件人、手机、收件地址），我们将送上 Cocos 周边盲盒1份！
啥呀，这是，国庆都过了，我才看到 