How to check if a possible path exist?

Question

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.

Answer 1

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

Answer 2

What you have here is in fact a graph. The graph vertices are the free squares and there is an edge between two cells if and only if both of them are not black and they share a common side. Now that you converted the task to a graph problem, all you need to do is to perform any search for instance a BFS from the green square. The level is solvable if and only if the destination is visited when the search completes.

Answer 3

DBS has the right idea in his comment to your question.

You can generate a path before placing obstacles using BFS or DFS. (BFS will give you a shortest path which you may not want for a game, and DFS will just give you a path, which may be more interesting.) Then when you place obstacles, make sure it doesn't land on the path. If it does, replace the obstacle until it is not on the path.

Or if you prefer, you can generate a path after placing obstacles using Dijkstra's algorithm, which tells you the shortest possible path from where you're at to where you're going. Edges to squares with obstacles would have a very high weight, and edges to squares with no obstacles would have a very low, non-negative weight (1 or 0 probably). This would make for more interesting paths through the maze, but you would have to replace obstacles more often, probably, if Dijkstra's can't complete successfully.

Answer 4

The best way to make such a map is not to add obstacles into the map but to remove from it . First your map will consist of all obstacles and only start and destination doesnt have obstacle.Then you start removing obstacles one by one at random from the grid. Use union and find data structure to check if the source and destination is connected at any point. You can continue till they get connected or further you can continue removing obstacles, in such a way you can define complexity of the map as well.

Union and Find