# Algorithm to detect impossible scenarios

I'm making a simple game where a surface is split up into 4 parts, rows, obstacles spawn in them, and a player tries to dodge them.

Up to 3 obstacles are generated in each row, and this can lead to some impossible scenarios such as:

And

What would be the best way to implement an algorithm to check if it is possible to get through or not?

What we're doing here is called finding connected components of the graph representing your play space.

In this graph, the nodes are the squares of your playfield, and the edges are the allowed transitions between them (ie. pairs of adjacent non-obstacle tiles)

With this frame in mind, we can apply standard graph search algorithms.

You can start a depth-first search from.the bottom row (following only legal moves as defined by the edges described above), and check whether that search ever touches the top row.(Defining a single "start" node adjacent to all cells in the bottom row, and an "end" node adjacent to all cells in the top can help with this)

If you reach the end this way, then the start & end are in the same connected component and the end is reachable.

If the depth first search returns without ever reaching the end row, then there is no viable solution path, and the obstacles cut the graph into at least two disjoint connected components.

A different approach to generating passable challenges which you could use here is to not generate a challenge but instead generate a possible solution (a sequence of moves the player is supposed to perform) and then randomly add obstacles which do not interfere with the generated solution.

In this case that would mean that you decide which tile on each row is the one the player is supposed to be in or move through. Generate obstacles in all other tiles of that row.

On the next row, randomly decide if the player is supposed to stay, move left or move right (or move left or right by several tiles, if your game allows the player to do that). Those tiles which need to be free in order to perform that move need to be omitted when generating obstacles.

On every subsequent row, assume the player performed the move they were supposed to perform and apply the same rule.

You can tweak the difficulty by changing:

• The probability of obstacles being generated on the columns which are not marked as required for the solution.
• The probability of "move" rows vs. "stay" rows. The more move-rows and the fewer stay-rows you have, the harder the game will be. You can also increase difficulty by forcing the player to switch between moving left, moving right and staying in short intervals.