Getting Blue Balls or: What the hell was I thinking and how I learned to recreate Sonic 3 and Knuckles' Special Stages

So, Yo Noid 4: Episode 3 - The Special Stages... What the absolute hell was I thinking?

It started out as a simple meme game: Put The Noid in a Sonic Game, it'll be a nice work out for your Sonic Engine after learning lessons from Freedom the Eagle. But somewhere along the line I got an idea into my head: Why not make it a piss-take of Sonic 4, with an imaginary Episode 3.

Very very little was known about what would be in Sonic 4: Episode 3, outside of the general plot (Sonic goes frees Little Planet from the Death Egg Mk II) and what the special stages might be (some version of Blue Spheres, since Ep 1 remixes Sonic 1, and Ep 2 remixes Sonic 2 it made sense that Ep 3 would remix Sonic 3's special stages).

And so off I went on a naieve little tangent and went to recreate Blue Spheres.

Before going into it I knew I'd need a few things:

1. Some way to render or traverse a Toroid
2. Some way to work out how to turn chains of Red Spheres surrounding Blue Spheres into Rings
3. Some stupid 'gimmick' to make it different from Sonic 3 and Knuckles' Blue Spheres
   • Episode 1 had you control the level, rather than Sonic!
   • Episode 2 had half-pipes... but there was more than one and you bounce between them!
   • Episode 3 would have had... what?

Item 1 was done quite quickly, I found a nice Unity shader that displaced vertexes. This meant I could work on a 2D plane and have the shader do all the heavy lifting making it look like you're running around a sphere. 

While modifying it to work with Sprites I discovered you could give it a positive number and have it curve outwards, hyperbolically. Not only did I get a simple solution to the curved world problem, but I also got Item 3 for free.

Well kind of. I also had an idea from the start to add in the Trail mechanic as I'd previously did something similar in Snekman and realised while making it that this was essentially 2D Blue Spheres. But just the trail felt underwhelming. So making it curve outwards added that nice secondary gimmick. A visually useless gimmick. 

I also considered having a sphere pickup switch your view between Hyperbolic and Spherical. Just to make it a bit more nauseating. But I decided against that (for now).

But what about Item 2?

I knew that would require some Graph Theory. I've written my own A*/Dijkstra's/etc algorithms before so I'm no stranger to Graph Traversal but I'm hardly formally trained in it.

I figured that somewhere out there someone would have blogged about recreating Blue Spheres (especially since it was added to Sonic Mania) and my journey through that utter nonsense is detailed in this series of tweets and if you want to wallow in my nightmare go ahead and read it.

1. TL;DR: Finding Stealth's Post on Sonic Blue Spheres was hard. Figuring out how to describe "A Circle of red spheres around blue spheres" in terms of Graph Theory was horrible, but I eventually found out it was called a Cycle. I had to find the Longest Hamiltonian Cycle of Red Spheres in an undirected graph.

So finding the cycles was only part of it. Once you found the Cycles you had to find all the blues spheres that were inside it and change them to rings. So here's a quick pseudocode rundown of how my code works:

1. From the Sphere the player is on (having just turned it from Blue to Red)
2. Find all connected Red and Blue spheres. (we need both for later on and it's quicker just to grab them all now than traverse it twice)
3. Take only the Red Spheres from this set of Spheres. 
   • This is the Graph we're going to traverse to find cycles.
   • It's an undirected graph because connections are bi-directional.
4. Find the Longest Hamiltonian Cycle in this Undirected Graph 
   • This is the hard bit
5. Take only the Blue Spheres from step 2
   • For each Blue Sphere, find at least one Red Sphere found in Step 4 along each of the 4 cardinal directions.
   • If it has all 4, turn it into Rings.
6. Turn all the Red Spheres found in Step 4 into Rings.

Finding the Longest Hamiltonian Cycle in an Undirected Graph is Hard. NP Hard. That is to say (in non-graph theory terms) Fucking Hard. Not the algorithm, no, that's actually fairly simple when you understand graph theory. It's computationally hard. As in, you have to find every cycle in the graph, and then decide which one is longest. And this can make the system really chug. This is a bad thing.

For every Red Sphere, for every junction, for every start and end point, the complexity goes up exponentially.

Finding the Shortest Cycle, however, isn't that hard. Detecting that a Graph has a cycle is also not hard. So every time you turn a Blue Sphere into a Red Sphere, you can quickly check to see if you need to go mental and find all the cycles. So step-by-step you're not taxing the system much. 

Okay, maybe it'll chug a little bit if you have a huge swathe of red spheres with blue spheres touching it. Note, none of the Sonic 3 and knuckles special stages have groups of Blue Spheres larger than 8x8. And none of the Special Stages have Cycleable Blue Spheres touching large batches of Red Spheres. They're all padded by bouncers, or empty space.

But with modern hardware it wasn't a problem finding if a cycle exists. The problem is, again, finding the longest cycle.

I swapped out the Longest Cycle algorithm for the Shortest Cycle Algorithm as a stopgap. It worked 90% of the time in the classic levels. There was just one part where it wouldn't work. Sonic and Knuckles Special Stage 7.

My Algorithm would only turn the top cycle into rings, because it always found a short cycle, and only one of them.

This is where Stealth's post about it came in handy. He wasn't doing what I was doing. Rather than finding all the Cycles he was marking junctions and just going back to those. He wasn't finding all the cycles, just every red sphere involved in a cycle.

It was a lot less complex, and ran faster. Only problem was that by this point I'd decided on allowing custom levels. And my code is not efficient. I'm aware of this acutely. Because implementing this, and trying out a stage similar to #30 up there, there was still a noticeable frame drop when it looked for the cycles.

And so I went whole hog. Filled the entire stage (except for an empty border) with blue spheres and tested it. A single Cycle. Fine.

Deliberately screwing it up and adding dead ends, multiple possible cycles... Unacceptable level of frame drop for me.

So, I compromised. I simplified it.

Rather than going back to every junction I'd just go back to the start. At most I'd be finding 4 cycles, regardless of the complexity of the graph. And rather than using 'Best First Search' I used, well, 'Worst First Search'. From your current node, find the node that's furthest away from the start. If you hit a dead end, go back to the last junction and keep going. If you find a Cycle, you're done. Go back to the origin and choose the next adjacent node to go from.

It always prefers Vertical over Horizontal. Up/Down/Left/Right in that order.

Here's a worked example:

This works quickly, even on large amounts of blue spheres at about the same speed as it does on small groups. It does mean, however, there are still some edge-cases, especially when a cycle already exists and you trigger inside it, but it works well enough for 99% of the cases, and all the cases I'd expect to be intuitive for the player.

All this... For a fucking meme game.