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

标签 javascript algorithm path-finding maze

我正在开发一款基于 javascript 的实验性游戏。玩家必须在二维平铺 map 上旅行才能退出。

Feel free to check this fiddle and play

我只是随机放置障碍物,但有时障碍物会挡住玩家和导出之间的道路,关卡变得无法通过。

下面显示障碍物如何放置在 map 中的代码不是实际代码的一部分,我只是将这部分简化并翻译成英文以提高可理解性:

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) 开始,那么我们需要找到棋盘上下一步要移动的位置。这涉及计算我们可以从当前位置移动到的所有潜在方格。

首先想象这个问题是一个蜘蛛网,我们的起始方 block 位于它的中心。如果我们从蜘蛛网的中间开始,我们不希望随机选择一个方向并开始行走,直到我们到达边缘——我们可能会完全走错方向。这是计算路径的幼稚方法,并且比其他方法花费的时间长得多。更好的方法是横向浏览网络,只有在达到目标时才停止探索。

即将更新代码。

编辑:工作 javascript 代码,只需寻找 -1 来检测不可能的游戏。 LINK

关于javascript - 如何检查是否存在可能的路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20748986/

相关文章:

javascript - 为什么 Webpack 在我的主目录中寻找预设?

python - Numpy:如何找到矩阵 A 中子矩阵的唯一局部最小值?

algorithm - 在 Twitter 上识别重复问题的方法?

python - 使用加权顶点计算图中的最短路径

javascript - jQuery合并不同id的功能

javascript - 从新对象的属性更新对象的属性,但前提是新对象的属性不是未定义的

python - 如何使用协同过滤通过用户行为来预测用户?

c# - 在几何体上创建等边三角形网格

algorithm - 最快路径算法

javascript - 如何包含基于条件的参数(在 CoffeeScript/JavaScript 中)?