Very Basic Pathfinding For Infinite Runner

Hi everyone!

I’ve been scratching my head over this one for a day now. I know there’s some pathfinding / A* whizzes that can probably answer this in 10 seconds, but pathfinding isn’t really my strong suit.

Here’s the scenario:

We have a 4x10 grid, as (hopefully) shown below.

10 |__|__|__|__|
09 |__|__|__|__|
08 |__|__|__|__|
07 |__|__|__|__|
06 |__|__|__|__|
05 |__|__|__|__|
04 |__|__|__|__|
03 |__|__|__|__|
02 |__|__|__|__|
01 |__|__|__|__|
00 |__|__|__|__|  
     A  B  C  D

Think of this grid as a treadmill. Once every second, row 00 gets deleted, and row 11 gets instantiated. The whole thing is moving down, and the player is also moving up one unit.

Also once every second, one block is randomly chosen and is destroyed, or otherwise marked as unwalkable. If the player lands on this block, (s)he looses the game.

My issue is finding a way to check whether or not the player will have a viable path before destroying a block. I want to have it so that it’s always possible for the player to progress forward.

I am currently spawning this grid row by row, if that gives you an idea of the hierarchy.

It seems like A* could be a solution here, but it seems like I would need to ‘faux destroy’ the block, check if there’s a viable path, and then give up and try again if there isn’t one. I guess that could go on for many iterations if I took that approach, and that just doesn’t seem efficient.

Help is appreciated, as are links to where I can find out more about solving this sort of thing on my own!




Here’s an example of the scenario, where ‘█’ represents a destroyed block, P represents the player, and ?? represents the block that is being checked to see whether or not it may be placed.

10 |__|__|__|__|
09 |__|__|__|__|
08 |__|__|__|__|
07 |__|__|__|__|
06 |__|__|__|__|
05 |??|__|__|__|
04 |__|█_|__|__|
03 |__|█_|__|__|
02 |__|__|█_|__|
01 |__|__|█_|__|
00 |P_|__|█_|__|  
     A  B  C  D

Given your example you could try something along these lines:

  1. Find all reachable positions in this row, given your current position (A, B, C, or D) by moving left and right until you hit a wall or the ‘edge’
  2. Store those positions in a list and then move on to the next row
  3. For each of those valid positions (potentially A, B, C, D) check if there is a wall at that position in the new row
  4. If there is a wall (assuming you can’t move diagonally) then remove this position from the list
  5. Now go back to step 1 (checking all reachable fields when going left and right from positions in our list)
  6. When you reach the ‘last row’ you will have all the positions the player could be
  7. Now use these positions to check if the player could still go forwards (i.e. list count is > 0) if you block a particular field

Hope that makes sense, might add some mockup code to clarify.