如何检查可能的路径? [英] How to check if a possible path exist?

问题描述

我正在研究基于JavaScript的实验性游戏.玩家必须旅行才能退出二维平铺地图.

I'm working on an experimental javascript-based game. Player has to travel to exit on a 2-dimensional tiled map.

随时检查此小提琴并播放

我只是随机放置障碍物，但有时障碍物会阻碍玩家与出口之间的通行，并且水平变得无法击败.

I'm just randomly placing obstacles, but sometimes obstacles block the way between player and exit, and level becomes impossible to beat.

下面的代码显示了如何在地图上放置障碍物不是实际代码的一部分，我只是将其简化并翻译成英文以提高清晰度:

The code below which showing how obstacles being placed in the map is not a part of actual code, I've just simplified and translated this part to English to improve intelligibility:

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';
}  

---

我只是在寻找一种寻路算法或一个写一个主意的想法.

推荐答案

前几天在采访中遇到这样的问题.

Had a question like this in an interview the other day.

考虑到介于两者之间的所有步骤都是有效的(根据您的规则)，您的问题归结为寻找从A点到B点的最短路径.

What your problem boils down to is finding the shortest path from point A to point B, given that all the steps in between are valid (according to your set of rules).

所以可以说我们有一个X X Y空间的网格.如果我们从空间(x，y)开始，则需要在木板上找到下一个要移动的位置.这涉及到计算我们可以从当前位置移动到的所有潜在平方.

So lets say we have a grid of X by Y spaces. If we start in space (x,y) then we are required to find where to move next on the board. This involves calculating all the potential squares we can make a move to from our current position.

首先想象一下这个问题是一个蜘蛛网，我们的起始方块在震中.如果我们从蜘蛛网的中间开始，我们不希望选择随机的方向并开始行走，直到我们撞到边缘，否则我们可能会完全朝错误的方向行走.这是计算路径的幼稚方法，并且比替代方法花费的时间长得多.更好的方法是在网络上进行广泛的漫游，并且只有在达到目标时才停止我们的探索.

Imagine first that this problem is a spiderweb, with our starting square in it's epicentre. If we start in the middle of the spiderweb, we do not wish to pick a random direction and start walking until we hit the edge- we could be walking in the wrong direction entirely. This is the naive method of calculating the path and takes far longer than it's alternative. Better then is to walk breadthwise through the web, and only halt our exploration when we hit our goal.

关于更新代码.

工作中的javascript代码，只需寻找-1即可检测不可能的游戏. LINK

Working javascript code, just look for -1 to detect impossible games. LINK

这篇关于如何检查可能的路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！