javascript – 如何检查是否存在可能的路径?

我正在研究基于 JavaScript的实验性游戏.玩家必须前往二维平铺地图上退出.

Feel free to check this fiddle and play

我只是随机地放置障碍物,但有时候障碍阻挡了玩家和退出之间的方式,并且水平变得不可能被击败.

下面的代码显示了如何将障碍放置在地图中不是实际代码的一部分,我只是简化并将此部分翻译成英语以提高可懂度:

var arrayCoordinates;
var targetSquare;
var obstacleAmount = 30;
for (var i = 1; i <= obstacleAmount; i++) {
    arrayCoordinates= randomCoordinates();
    targetSquare = document.getElementById(arrayCoordinates[0] + '-' + arrayCoordinates[1]);
    targetSquare.className = 'obstacle';
}

我只是在寻找寻路算法或者我想写一个想法.

前几天在接受采访时有这样的问题.

你的问题归结为找到从A点到B点的最短路径,因为它们之间的所有步骤都是有效的(根据你的规则集).

所以我们假设我们有一个X乘Y空格的网格.如果我们从太空(x,y)开始,那么我们需要在板上找到下一步的位置.这包括计算我们可以从当前位置移动到的所有潜在方格.

首先想象一下,这个问题是一个蜘蛛网,我们的起始广场在它的震中.如果我们从蜘蛛网的中间开始,我们不希望选择随机方向并开始行走,直到我们到达边缘 – 我们可能完全朝错误的方向行走.这是计算路径的天真方法,花费的时间远远超过它的替代方案.更好的是在网上横向行走,只有当我们达到目标时才停止探索.

即将更新代码.

编辑:使用javascript代码,只需查找-1即可检测不可能的游戏. LINK

相关文章
相关标签/搜索