Search code examples
javascriptalgorithmpath-findingmaze

How to check if a possible path exist?


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

Feel free to check this fiddle and play

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

I'm just searching for a path-finding algorithm or an idea for me to write one.


Solution

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

    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).

    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.

    About to update with the code.

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