The Difficulties of an Infinite Video Game World

I've made arcade side scroller with potentialy infinite world. Everything (terrain, objects, backgrounds) was created on the fly, basing on the coordinates of the player.

It wasn't really infinite, but only because coordinates would wrap at 32 bit, if you fly far enough into one direction (but I've never had the patience to test this).

It's linux only, and not very playable, but if you want to test it - it's here http://alan.umcs.lublin.pl/~ajuc/programy/gry/hw3/

It requires libraries SDL, SDL_image, SDL_ttf, SDL_mixer, paragui (version >= 1.1.8). Works with software rendering so no acceleration needed.

I've been quite satisifed with terrain generation - I've calculated noise value (a few octaves of 2d Perlin noise) for every tile on screen, tiles with noise values over bias were solid, others were empty. I hadn't checked if there's always way out, but after tuning amplitudes and frequencies of noise generator I've never had problems with that in game.

Then I've had look up table that returned tile depending on which neighborns are solid and which are not. To cut the number of tiles I needed to draw I've used hex-like layout - every second row of rectangular tiles were shifted half an tile to the right. Thanks to that every tile had only 6 neighbourns, instead of 8. So I've needed 128 instead of 512 tiles. And it made levels look more "organic", than with regular 2d grid.

Also - I've had more promising idea to generate game worlds, which I've never got to work, but maybe it's time to try again..

The idea is - to use markov chain generation to generate level on the fly. First game designer will build small level from tiles by hand, then level editor app will analyse level for conditional probabilities that the next tile is Y given previous tiles in each direction are X0, X1, ..., Xn. Then in game levels would be generated on the fly, using these probabilities.

Unfortunately to ensure consistence of level, we must have some "frame", that is generated in some different way, and we must generate whole inside of frames at once, when player is near.

For example tiles on coordinates where (x%64 == 0 or y%64 == 0) are generated from Perlin noise, and inside is generated by doing markow chain "associated press algorithm", but on tiles instead of letters. Order of generation inside the frame needs to be specified, for example bottom-up, left-to-right.

The problems I've encountered were associated with big amount of memory needed to keep info about all conditional probabilities, and general complexity of this approach, but I need to try it again some day.