Return to “Everything & Anything”

Post

Procedural Level Generation in Sonic the Hedgehog

#1
Some of you guys might know my secret identity as a bit of a Sonic fan. I know, it's a character flaw, but it's there nonetheless. You guys aren't interested in the second half of the title. But I'm pretty proud of this and I think the PCG aspect might be of interest to some, so here it is.

------------

Development backstory: (skip if you're not interested in my life story)

S1RL: Random Levels Project is a hack/mod of Sonic the Hedgehog, a well-known Sega platformer released for the Sega Mega Drive in 1991. S1RL modifies the code to allow the game to generate its own levels in real-time. The idea for this hack first came about in 2009. I was writing a maze generator and experimenting with tiling patterns and fitting different types of tiles together with different rules, and I wondered if the same could be done with the large chunks in a Sonic game. In 2010 I tried with limited success, getting Sonic 2 generating usually traversable levels in this way in the timespan of ~12 seconds. However, the levels weren't frequently traversable enough, nor was the generation time low enough, for myself to consider it a success. At the time I was also suffering a nasty breakup as well as needing to focus on my Games Computing degree, and the stress of it all left me abandoning it entirely for a while.

For my Final Year Project I chose to study real-time adaptive track generation in racing games, creating a racing game which dynamically produces a road ahead of the player tailored to their driving style, and writing a dissertation about it, complete with user testing showing its effectiveness. It was successful enough that I was asked to cut down the dissertation into journal paper format and submit it to GAMEON'2012 with help from my supervisor.

During that time I read a lot about procedural generation, took a thorough look at how other games used it and how well it worked, and began forming new ideas about creating random levels in a Sonic game. Gone was the original tile-based generator, replaced with a strip-based generator instead. Objects could and should be attached to chunks that they're not contained in, and even in entirely different strips, provided it makes sense for them to be there. Strips that are otherwise the same can be duplicated to allow object placements that prevent certain tile placements, making the objects as much part of the level generator as the terrain.

However, I couldn't work on it in any serious capacity. I was too busy applying for jobs and attending interviews (and not getting the jobs), working with a team and a publisher as my own company to produce a shmup (and getting rejected by the publisher), spiralling into a depression at the first two not going anywhere, getting a new girlfriend, and working on my own mobile games - I still intend to make this professional when I eventually find software I like. I had a few small attempts at it; inspired by Sonic Runners in 2014 I recreated the boss and playstyle, testing the infinite-level concept, along with using strips that were 8 chunks long and tall and attempting to tile them correctly. I also made a quick prototype of S1RL towards the end of 2015 and... it was a massive improvement over my 2010 attempts.

But after simply not finding any engine up to snuff, I got stuck in a rut again. I still wanted (nay, needed) to code, and the focus shifted back to S1RL. I had no distractions. Studies were over, job well was dry, relationship was stable, and mobile games were going nowhere. So I dug deep into 68k (I'd learned it previously, but only with frequent reference to an instruction list), learnt how the game engine works, which parts needed to change and how, and plugged away at it. I didn't manage to do everything I wanted to, but I'm happy enough with the results to release it now. Of course, I'm going to continue working on it...

------------

About the original game:

In Sonic the Hedgehog, the goal of the game is to defeat the main villain, Dr. Eggman, who has kidnapped all the tiny creatures of the island and is using them to power his machines. The main goal of most levels in the game is simply to reach the end without dying, with destroying robots and freeing creatures scoring points, and the occasional boss battle against Eggman himself required to progress.

Sonic's main attack is curling into a ball; while in this form, he can smash enemies and other obstacles with ease, and he accelerates quickly downhill while rolling. Enemies and other obstacles will hurt Sonic if they come in contact with him while he is not rolling, and for some he is not safe even then. His main protection from attacks is found in the many rings floating about; while holding a ring, most attacks will simply knock Sonic back and cause him to drop his collected rings. When he is not holding a ring, any attack will kill him. Being crushed and falling out of the level will result in Sonic being killed regardless of how many rings he is holding. There are also monitors to be found throughout the levels; these offer many benefits, from an easy ten rings, to a protective shield that allows Sonic to survive one attack without dropping his rings, to powerups that make him faster or invincible for a limited period of time, to extra lives.

What makes Sonic different from other platformers, however, is the use of momentum. Although you might hear the claim that Sonic is about speed, this isn't true (at least, not in the original games) - it's about gaining and keeping speed. Sonic accelerates slowly relative to his top speed, and must use the curves of the terrain to gain speed and jump height in order to reach new places. This makes it a very different beast from its rivals of the time, and few games have used this style of platforming (the two most prominent series being N and Fancy Pants Adventures). This makes its level design very different from the likes of Super Mario Bros., and as such generating levels requires a different approach.

------------

About S1RL:

S1RL: Random Levels Project is a hack/mod of Sonic the Hedgehog that allows the game to generate its own levels in real-time. Other changes have been made with this in mind: Sonic's moveset is now tailored for maximum control rather than risk/reward payoffs; acts are much longer than usual; the timer now shows hours, minutes, and seconds, and the time limit has been extended to 24 hours; the life system has been removed entirely, with any death resulting in going back to the previous checkpoint; the camera moves in front of Sonic to reveal more of the level ahead; checkpoints trigger when going past them at any height; and there are multiple palettes to each level that change either with time or with a monitor. There are also numerous other minor cosmetic changes and bugfixes.

S1RL contains a number of monitors additional or changed from the original game.
- Static: changes the level palette
- S: gives both invincibility and speed shoes
- Eggman: hurts Sonic
- Sonic: produces a number of rings

Code added to the game was written in 68k ASM. Data added to the game was first produced by a program written in C#, and then tweaked by hand.

------------

Technical explanations:

The original Sonic the Hedgehog structures its levels using what I'll refer to as "terrain" and "objects". Terrain consists of a number of "chunks" that are 256x256 pixels in size (approximately the height of the screen and 3/4 of the width) that are put together in various ways to give the illusion of continuous ground. These chunks are fixed and do not change (with some hardcoded exceptions in the form of loops), but make the biggest contribution to the path of the level.

Objects on the other hand are typically much smaller, and represent everything that moves, and even some things that don't. Rings, monitors, spikes, springs, checkpoints, bridges, platforms, collapsing cliffs, rocks, breakable walls, and enemies are all objects that are placed on the terrain to bring it to life and actually make it a game.

All of the classic Sonic games work in this way, and most other 2D platformers do similar things. As I was interested in having the random level generation work in real time on the Sega Mega Drive, using the original game's engine was the easiest way to go about it; so level generation has to include both terrain and objects.

Levels in S1RL are strip-based. A strip is a portion of level one chunk wide and up to eight chunks tall (or 256x2048 pixels). Objects are included in the strip, but are not required to be within the area of the strip itself, to allow for things like collapsing ledges and more complex ring arrangements. Strips are arranged into adjacency groups. All strips in the same adjacency group can be placed to the right the same strip in some capacity, and every strip indicates an adjacency group for strips placed to its right.

This would work by itself, but would require a lot of superfluous and repeated tilings. Instead, strips can be moved vertically to fit if needed, with each strip labelling a tile for joining on both sides, as well as tiles to fill at the top when moving down (in Green Hill Zone, the level featured in this prototype, this is always the empty sky tile - but this won't be the case for other zones).

Levels in the original Sonic the Hedgehog can only be 64 chunks long (or 16384 pixels, approximately 50 screen widths). In order to extend this, the level is silently shifted every checkpoint to make more room. Checkpoints are not included in the strips directly, but each strip contains the height of a potential checkpoint so that they can be spaced across the level as needed. Bridges are also treated differently; potential bridge start and ends are included in strips; if a bridge fits between them, they are turned into stumps and the appropriate bridge is added.

Rather than generate the entire level at once, a small amount is created each frame. The generator has four main states that it cycles through: strip choice, object loading, additional objects, and object sorting.

- Strip choice chooses the next strip to place, generates the terrain, and updates all the related variables. If the chosen strip doesn't fit in the level, it is skipped and a new strip is chosen next frame.
- Object loading determines whether the strip should contain objects, loads the objects and moves them according to the strip position and offset; monitor types are randomly chosen as they are loaded.
- Additional objects determines whether a checkpoint or signpost should be placed, and works out whether a bridge can be placed and where.
- Object sorting sorts the objects in order of x-position (required for the in-game engine). In order to keep this as lag free as possible, this is done using a simple bubble sort with only one pass per frame. Objects within the data are already sorted into order of x-position, but the introduction of additional objects in the previous state means this part is necessary to maintain it.

There is also a move state activated by checkpoints, where the entire level is shifted so more level can be generated, and an end state that forces the game to revert to a linear path so it can generate a signpost.

------------

The strip data format:

The game has all the information it needs in the strip data format. It looks like this:

Number of adjacency groups (4 bytes) (unused)
Pointer to adjacency group 0 (4 bytes)
Pointer to adjacency group 1 (4 bytes)
Pointer to adjacency group 2 (4 bytes)
etc.

Adjacency group:
Number of strips in adjacency group (4 bytes)
Pointer to strip 0 (4 bytes)
Pointer to strip 1 (4 bytes)
Pointer to strip 2 (4 bytes)
etc.

Strip:
Entrance height (1 byte)
Exit height (1 byte)
Bottom height (1 byte)
Filler chunk (1 byte)
Next adjacency group (2 bytes)
Checkpoint height (2 bytes)
Bubble height (2 bytes) (unused in Green Hill Zone)
Dummy height (2 bytes) (unused, reserved to experiment with adding platforms)
Dummy height (2 bytes) (unused, reserved to experiment with adding enemies)
Dummy height (2 bytes) (unused, reserved to experiment with adding enemies)
Number of object sets in strip (4 bytes)
Chunk layout of strip (8 bytes)
Pointer to object set 0 (4 bytes)
Pointer to object set 1 (4 bytes)
Pointer to object set 2 (4 bytes)
etc.

Object set:
Number of objects in object set (4 bytes)
Object 0 (6 bytes, in the format used by the original game)
Object 1 (6 bytes)
Object 2 (6 bytes)
etc.

All pointers are relative to the start of the data. I've structured the various types of data as follows:

Adjacency group 0
- Strip 0,0
--- Object set 0,0,0
--- Object set 0,0,1
- Strip 0,1
--- Object set 0,1,0
--- Object set 0,1,1
Adjacency group 1
- Strip 1,0
--- Object set 1,0,0
--- Object set 1,0,1
- Strip 1,1
--- Object set 1,1,0
--- Object set 1,1,1
etc.

This is mostly for my own debugging purposes; the data can be structured in any way, even with all object sets entirely distanced from strips, as long as the pointers are correct and the start of the data contains pointers to adjacency groups. The same strip/object set can have multiple adjacency groups/strips pointing to it without problems, but again I haven't done this for debugging ease.

I've also used a long for all counts and pointers despite a word being more than adequate for these, because I'd rather leave room to expand later without having to change the format. Each adjacency group must contain at least one strip, and each strip must contain at least one object set (the generator will hang indefinitely if this is not the case); however, an object set can have zero objects.

The generator starts by generating strip 0,0 with the exit at height 3, as this puts Sonic in the middle of the level heightwise and allows the following strips to equally go higher or lower. It then reads the next adjacency group, chooses a random strip, moves it down such that the new strip's entrance is aligned with the old strip's exit, chooses a random object set, and repeats. For speed's sake, only strips and object sets numbered from 0 to 15 are chosen (this doesn't affect the provided data, and I'll change it when I need more than 16 strips in one adjacency group).

When in the end state, the generator will always choose the first strip in the adjacency group. These should be structured such that it always forms a path back to strip 0,0; this can be achieved by swapping strip numbers or pointers. Objects are still chosen randomly until approaching the signpost, at which point they stop being created.

The entrance and exit heights could be marked in any way, as long as the exit of one strip aligns correctly with the entrance of the next. I've generally chosen to make the joining point the highest part of ground that continues past the edge of the strip. The bottom indicates the highest chunk that can be safely shifted off the bottom of the level; this is typically the tile below the lowest part of ground. The filler is chosen from the chunk list and is tiled above the top of the strip when it is moved down.

------------

Generating the data:

There's a lot of data, and if I had to make it all by hand it would take forever and be riddled with mistakes. So I automated the process somewhat.

To start, I created my own Green Hill Zone acts in SonLVL, a utility created by MainMemory designed to allow hackers and modders to easily create their own levels. The more data available, the better results possible - so I created 36 new Green Hill Zone acts. After that, I manually indicated tiles which could safely be shifted off the level in either direction, tiles with ground that continues to the left or right, and potential bridge and checkpoint positions, and then wrote a program in C# to compile all 2304 strips present, assuming all objects within the strip belong to that strip. Each strip has its own adjacency group, and points to another adjacency group. The program uses the data to shift every strip as far up as it can go (so the generator can move them back down again when necessary). It finds duplicate strips, and merges the object sets of the two strips, as well as merging the adjacency groups that they both point to.

The bulk of the job is done; the rest is just a matter of tweaking. I ran the generator on this data, and it frequently got stuck on some adjacency groups. This is usually because all of the strips in the adjacency group move the level downwards, when the last strip is already as low as it can go. I fixed most of these by lowering the bottom of the previous strip such that it cannot be chosen at that height. In more extreme cases I simply removed it entirely.

The strip merging also frequently caused strips being placed next to each other that simply didn't fit, like waterfalls not being placed between ground tiles. I pointed these strips to new adjacency groups and duplicated only the appropriate strips to put in the new adjacency groups. Occasionally strips were misaligned - this is a simple fix that just requires shifting the entrance or exit to fit.

Objects are a bigger problem; some objects don't fit in some strips when they're beside other strips or object sets. I split these strips and pointed strips containing the offending object sets to new adjacency groups, duplicating only the appropriate strips and object sets to put in the new adjacency groups.

Finally, when trying to end the level, choosing the first strip in the adjacency group didn't always form a path back to strip 0,0; swapping appropriate strips solves this problem.

------------

The result:

Here's a peaceful video of the game panning through a generated level for an hour.

Forums can frequently be iffy about sharing ROMs (with good reason), so I'll just ask you to look at the video description for that instead. To play it, you'll need to use a Sega Mega Drive emulator - I recommend Kega Fusion or Gens, but other emulators are available.

Controls:
- left/right: walk/run
- down while walking/running: roll
- A/B/C: jump
- down+A/B/C while standing: Spindash (press A/B/C repeatedly to charge, release down to speed away)
- up+A/B/C while standing: Peelout (hold to charge, release to speed away)
- up while rolling: unroll
- down or A/B/C while airborne: curl in air
- start: start/pause the game
- A while paused: regenerate level (only loses progress since last checkpoint)

Note that all controls are described in terms of the original Sega Mega Drive controller; you will need to configure your emulator so that these controls make sense to you. Here's a picture of how the original controller looked if you need inspiration.

------------

Known bugs:
- Objects respawn after hitting a checkpoint. This is not so much a bug as a workaround; I couldn't figure out the object loading routines, so I chose to have objects consistently respawn rather than unpredictably despawn/respawn/not load in the first place.
- Checkpoints sometimes load already activated, causing the level beyond to stop loading. I'm not sure what causes this, but regeneration (start+A) usually fixes it.
- Signposts sometimes load earlier than they should, with corrupted graphics and typically causing death shortly after touching it. Again, I'm not sure what causes this, but regeneration (start+A) usually fixes it.
Games I like, in order of how much I like them. (Now permanent and updated regularly!)
Post

Re: Procedural Level Generation in Sonic the Hedgehog

#2
Hmm...looks really interesting. I would love to test it out, but these emulators are too much of a hassle to me.

Hmm...the track in the video looks a little easy. Is that caused by the generative nature of your hack/mod?
Automation engineer, lateral thinker, soldier, addicted to music, books and gaming.
Nothing to see here
Flatfingers wrote: 23.01.2017: "Show me the smoldering corpse of Perfectionist Josh"
Post

Re: Procedural Level Generation in Sonic the Hedgehog

#3
JanB1 wrote:Hmm...the track in the video looks a little easy. Is that caused by the generative nature of your hack/mod?
Not sure. For now I'm putting it down to the fact that it's based on the first zone in the game and that's easy too. I'm going to try a harder zone next to see how different the results are.
Games I like, in order of how much I like them. (Now permanent and updated regularly!)
Post

Re: Procedural Level Generation in Sonic the Hedgehog

#4
DigitalDuck wrote:
JanB1 wrote:Hmm...the track in the video looks a little easy. Is that caused by the generative nature of your hack/mod?
Not sure. For now I'm putting it down to the fact that it's based on the first zone in the game and that's easy too. I'm going to try a harder zone next to see how different the results are.
Cool. Post the results, will ya? :D
Automation engineer, lateral thinker, soldier, addicted to music, books and gaming.
Nothing to see here
Flatfingers wrote: 23.01.2017: "Show me the smoldering corpse of Perfectionist Josh"

Online Now

Users browsing this forum: No registered users and 33 guests

cron