Generating a map in runtime for a simple top-scrolling racing game

Question

I'm creating a simple top-scrolling racing game. The concept is quite simple - the player controls the car, which goes on a dynamically generated field with square blocks. Once the car hits a car, the game ends.

My first implementation was simply to put a few random blocks in each row being generated on the top of the screen, but this does lead to maps where going through is impossible.

What is the best algorithm for generating such type maps? My platform of choice is XNA and C#, if that's important.

EDIT: Here's an illustration: (pic)

In this case, there's no possible way for the player to pass.

Answer 1

You will have to do some pathfinding. I'd suggest something like this: Choose grace distance, the shorter, the harder the game may be. When you add a new row fist find out in what places the player may be after travelling the grace distance. You can use an A* search algorithm to find the group of points efficiently, then you remove any point that doesn't have a path through the currently generated rows from the group. Now you generate a new row and check that all the points in the group have a path all the way through the new row, if some of them doesn't you will have to regenerate the row.

Edit:
The pathfinding is very simple in this case, as the car can only occupy one of 8 different positions per row, so your pathfinding will never have to branch beyond 8 positions. You simply incrementally check what positions the car can reach in the next row, from the positions it may occupy in the previous row.

Edit:
Strike the A* reference, I better just refer to Dijkstra, almost the same but seems easier to understand.

Answer 2

Rather than try to generate a field to play in that you need to check to keep valid for play, instead generate a path the vehicle can follow, then randomly add obstructions to the parts of the map not filled in by the vehicle path generated.

1D Brownian motion: (http://classes.yale.edu/fractals/randfrac/brownian/Brownian3.html)

If you use low frequency brownian motion for the car path, filling in cells as not-obstructable, you can then simply have a low probability function for selecting whether each non filled cell is occupied/obstructed.

This will always lead to a game that can be played, but it can also be tuned to have sparse or dense obstructions patterns. You could even have the density function be brownian too ;)

Answer 3

Just use the last 'top-row' as reference, and generate a valid row from there (for each block, pick one at random, if it's invalid, do it again). Now valid is something you'll have to define, but my guess is 'valid' would be reachable from any of the three neighboring blocks from the reference row.

Answer 4

Quick idea written during compile-time(curse you c++):

When placing a block make sure that the top half of the map has three columns next to each other which are free. Do that by summing up the number of black squares in each column. Then iterate through the column sums three at a time.

First check will sum column 0 1 2.

If sum equals 0 tag chunk 0 as free.

Next check will sum 1 2 3.

If sum equals 0 tag chunk 1 as free

After that 2 3 4

If sum equals 0 tag chunk 2 as free.

etc.

After placing a wall check that at least one of your previously tagged chunks are empty. Redo procedure until at least one is left empty.

This method leaves you with an option for easy and hard mode where easy mode checks entire map for free spaces instead of just top half. Also, by setting an upper limit of wanted empty chunks you can increase the difficulty. Hard diff would mean that one or two chunks are allowed to be free at any time.

Hope you understand what I mean.

Answer 5

i know im really really REALLY late but wouldnt the simplest way to do this be to change the car so that its only 1 block thick? leaving only an incredibly small chance that the game will give you something impassable?