# How to test if procedurally generated level for infinite runner can be passed?

I have a 2D infinite runner platformer game built in Unity 5, where the level procedurally generates itself. I need to check if it is possible to pass the holes on the level.

How could I do that?

• What is your question? Do you need an algorithm that checks if your level is passable, or do you need an AI that can jump through the level on its own? – bummzack Jan 16 '16 at 17:05
• Well yeah, I need to check if my level is passable. I thought creating player AI is the best solution. – John Doe Jan 16 '16 at 17:10
• Its always easier to generate valid level than to check it later. If you know how long your jump is, why then don't you just limit the gaps generation to that length? – Nikaas Jan 16 '16 at 19:01
• How exactly is it generated? Are obstacles stacked with the possibility of a solid wall? Does the player experience elevation change? (Jumping from higher means a larger gap could be cleared) – tyjkenn Jan 16 '16 at 19:02
• I've got Min Random Dist X, Max Random Dist X and same with Y. I have Min Random Dist X always 0, so obstacles won't go inside each other. So yeah, player might experience elevation change. – John Doe Jan 16 '16 at 19:15

I understand you are dealing with both box obstacles and gaps. The way it was described, I can see three possible situations. Correct me if the game is designed differently.

With the first, there are no obstacles before the gap, at least no obstacles that the player can jump atop. In this case, you would need only a fix max width for the gap.

In the second, the player can jump atop an obstacle before the gap, increasing his jump distance. This means we can increase the gap width.

The final sketch shows what happens when two obstacles before the gap allow an even higher jumping elevation.

Here is a possible algorithm to use during generation:

When creating a new obstacle:
If there is an obstacle before it and it is accessible:
If newObstacle height - lastObstacle.y < jumpHeight:
Mark the new obstacle as accessible.
Else if newObstacle height < jumpHeight
Mark the new obstacle as accessible

When creating a gap:
gapWidth = minimum gap distance
If there is an obstacle before that is accessible
gapWidth += lastObstacle.y * someConstant


This way, no matter how high the random staircase is, you will know how wide you can make your gap.

• This answer could be improved with some more rigorous math to calculate the intersection of the jump trajectory with the ground. If it's a parabola, then it won't vary linearly with height, the way it's shown in the pseudocode here (since the parabola gets steeper the longer you keep falling...) – DMGregory Jan 17 '16 at 18:47

Do it at the generator level: Always generate your level using a selection of passable gaps / obstacles section prefabs.

If two successive sections are not passable mark them as such so the generator does not put both in succession and/or adds some space between them.

These sections will also instruct the AIs on how to clear the obstacles.