How to Build a 2D Sonic Engine

Actually, this doesn't paint the entire picture for collision, and there are multitidue of ways to check for collision, some faster than others. While you are correct, for the purposes of Sonic, at some point, you're going to need to do this (which is really just basic trigonometry), how you check for collision, and how often is incredibly important. For example, you don't want to have to check every single point on the screen, that is what results in poor performance (and usually will make your CPU load increase by a ton). There are plenty of collision checking methods out there, from a simple axis-aligned bounding box, to complex circle collision, and a near infinite amount of methods in between.

However, what is smart (and generally not talked about, and not covered at all in the physic guide) is the general approach one should probably take for collision detection. In most game programming, this involves splitting collision into two phases - a broad collision detection phase, and a narrow collision detection phase. You have described one manner of narrow collision detection, but broad collision detection is just as important. The idea behind this principle is that you have a speedier method of collision detection that checks the entire screen first, to determine where and within what range to do the slower, narrower check that you just described.

Myself? I use morton encoding, it's a variant of octrees that isn't really taught very often. Moron encoding is a method where you keep a list of every object available on screen at once, be they ground tiles or enemies or whatever. By taking these objects X and Y coordinates and representing them in binary, then interleaving their bits, you arrive at a morton encoded string. To give an example, say I have 4 objects, at the following positions:

1, 2 -> 001, 010 -> 000110
2, 2 -> 010, 010 -> 001100
4, 3 -> 100, 011 -> 100101
5, 4 -> 101, 100 -> 110010

There is an interesting phenomenon regarding binary representations of space which morton encoding exploits. Due to the nature of binary spacing, each bit in a morton encoded string will divide the considered screen space in half. This means that, if you begin at 000000 and increase all the way to 111111 you will follow a Z-ordered space filling curve like so:



This plays into the concept of the principle of locality, where objects near each other are stored next to each other in memory. Using such curves for general collision detection allows you, for example, to limit a range around sonic (or whatever) to ensure you only check collision around immediately relative objects. It makes no sense, for example, to use expensive narrow collision detection half-way across the screen when it'd be impossible for those two objects to collide.

You could visualize the collision checks like so:



Where each "box" is a collision check. You see that using a space filling curve like this drastically reduces the number of collision checks necessary.

I generally use morton encoding to check for collisions among objects in my memory pool (which, again, plays into how important properly implimenting a memory pool is, because, for example, if objects spawned in your pool automatically spawn in-order then that's one more sort that you don't have to spend time doing -- I use what is known as a free list, that is -- a linked list that uses a union in memory to act as a map for the next available open slot simultaneously -- to speed up my auto sort upon creation. Also -- there are many, many ways to morton encode - some faster than others), but for ground collision detection, I use another method.

The way Sonic levels are organized -- by chunk -> block -> tile -- lends itself to a method known as Data Binning. I only have to check the number of chunks visible on the screen, then check the number of blocks visible in each chunk, in order to accurately figure out where to narrow my collision detection to, rather than using narrow collision detection all over the screen at once, because if Sonic is in 1 chunk, he is assuredly not in any other.

This is precisely what I mean when I say that there is no single right or wrong way to implement any of this stuff. You can get 10 programmers together and have them write the "same" collision detection routines, and wind up with 10 radically different collision detection systems, that all do precisely the same narrow logic.

 

Well, I suppose I would keep a track of which objects need to be loaded on screen plus a bigger area (maybe 3 x 3 screens, with the actual screen as the center one), and check their collision boundaries are inside others' boundaries as well if relevant, so I'd check only objects too near to sonic's position to know about his collisions, but others could interact between them in other positions if necessary. Since the terrain is a collision map, I would have it loaded, not sure if for all the map once or for the above described area each time it changes, and make proper collision checks for every present object with the terrain when necessary (for example, not necessary for buzz bombers which fly and ignore the terrain). Objects in the given area should probably mapped as some sort of "collision tiles" to track their collision more easily, or maybe outright by necessity. Well, I think I messed a couple of concepts here, and I won't talk any more to avoid evidencing my ignorance, but that's the rough idea that makes sense to me to start with.

That said, I don't get most of the technical terms, callback functions and binary trees are the farthest they taught me about that level of programming when I learnt C. With C++ they went directly to object specific questions, so I'm OK with operator overloads, inheritance, etc., but nothing more about algorhytms when working with the "big picture" (no pun intended). It's still great because it helps me getting interested in learning more and go for it, a shame I didn't try to learn this before.

 

How far did you get with game making? Can you show some examples in pictures or a video? It'll help with giving you further advice.

 

@Cooljerk - Thanks for writing that out. As someone who dipped his toes in handling 3D collision, it's neat to see some good ideas how to handle it if someone were to go and make it all from scratch. For now, I use Nvidia PhysX for collision detection, and handle response by myself, but there's reasons why I'd want to be able to code collision detection from scratch-ish sometime down the line. What I do is that I go for a simple higher level (but not the world's most efficient) approach:

- Get the start point and end point of a physics calculation.
- Divide the path into a few nodes.
- Do collision on each node. If I don't hit anything, apply position from the physics calculation, otherwise apply position from collision response.

I got the idea from Mario 64s half-steps and quarter-steps. Simply dividing your path into 4 can handle insane speeds reliably. Obviously it's not ground breaking, but there's a whole lot of ways you can tackle this if you're like me, and don't have all that technical know-how (yet ).

It's neat to have some direction if I eventually try to make this faster and do the detection part myself, you can skip a whole lot of checks having to deal things in a broad-narrow kind of way. For now I'm worried more about functionality. But as you said, there's many ways to tackle this (although, not all methods will be as efficient).

 

Depends on how much you knew about programming before starting learning C++, but looks to me like you're trying to run before knowing how to walk. You should try having a solid knowledge of the language and a comfortable use of it at its base to start building something over it, not to mention CoolJerk gave us an extensive list of things to know, so just C++ may not be enough to try what you want. As WinterHell says, it would be easier to answer you if you give more details.

 

That tileengine thing is sweet. I might start faffing about in real programming languages and get away from Game Maker with stuff like that available.

I wouldn't make a Sonic game, though. Classic Sonic is one the most advanced and complicated 2D platformers out there. I think a lot of people underestimate just how much of a technical marvel Sonic the Hedgehog was and still is. There were no games like it before 1991 and there haven't been very many since '94. It kind of blows my mind how they wrote all of that stuff in assembly. It's way above my head.