Hacker News new | past | comments | ask | show | jobs | submit login
A guide to implementing 2D platformers (higherorderfun.com)
307 points by ingve on Sept 11, 2015 | hide | past | favorite | 32 comments



> Before anything on the scene is stepped, determine whether the character is standing on a moving platform. This can be done by checking, for example, whether his center-bottom pixel is just one pixel above the surface of the platform. If it is, store a handle to the platform and its current position inside the character.

I implemented a 2D platformer with moving platforms once; we solved this simply by using another rule in the article — the one for ladders:

> when you’re in a ladder, you ignore most of the standard collision system, and replace it with a new set of rules.

There was a special flag on the entity for "is on a platform" (and which platform, too); thus, you trivially knew if something was on the platform. During normal collision detection, if you found yourself falling through a platform, your fall was truncated, and you were affixed to the platform. (An entity's platform variable became, essentially, Some(a_ref_to_the_platform).) The affixing was two-way, IIRC: the platform knew about you, mainly s.t. when it moved, it could update linked entities. And if it was destroyed — which could happen — then it could unref itself from whatever was on it; really, one had a weakref to the other, but I was not that good a programmer then, so it was more manually implemented.

It worked quite well. We tried the whole pixel business, but it was troublesome; the game engine itself needed to deal with characters falling >1px per game state step, so it already knew "you are falling into a platform" bit.


I've kept a list of 'touching' entities (and where they are touching) on each entity before. Every frame this was cleared and rebuild as collision detection is performed.

The moving platform's update code will then move any entity that was touching it's top.

Having this list available was also handy for other gameplay too, so I'm a fan of this solution, even if it has some overhead.


It's fairly disingenuous to say that implementing polygon-based (the article calls it "vectorial") collision detection on platforms is "very difficult to implement properly" without a physics engine.

The collision detection code for this can be done in probably less than a thousand lines (probably less if everything is OBBs). Adding support for arcs, and even bezier curves becomes much, much easier as well (for both, probably another thousand lines, at most). It is also easier to add support for continuous collision detection this way, should that be something you want (although this would increase the amount of code a fair amount).

FWIW, I used to go the pixel-based route, but after having done it this way I'm not sure I would do it again. It ends up being much cleaner, more robust, and easier to extend. I'd go as far as to say that your collision detection and physics code shouldn't have any knowledge of pixels, only your renderer (and maybe the gameplay code, if you insist) should have an idea about these.

I will say that it requires a stronger math background, however, but in all honesty, probably not that much stronger than is required to make the rest of a game.


Could you recommend some resources or a good place to start for this approach?

I've experimented some with what I consider to be "hack" solutions where your character is basically covered in collision shapes and sensors and I've yet to feel it is robust compared to a solution that uses actual math. My reference point for "great controls" would have to be Super Meat Boy and N+ -- though for all I know they've taken an approach described in the article.


N+ (and I believe Super Meat boy as well) don't use pixel-level physics and rely on AABB collisions and computations. There's even a tutorial published on how the original N game resolved basic collisions and physics:

http://www.metanetsoftware.com/technique/tutorialA.html


Awesome, thank you.


Matt Thorson, the developer of Towerfall, also has some notes on implementing robust platformer physics: http://mattmakesgames.tumblr.com/post/127890619821/towerfall....

The overall idea is to use integer pixel coordinates (to avoid floating point error accumulation) and to step all physics by one pixel at a time (to avoid fast-moving objects passing through the environment).


I think I have implemented all of those methods for various projects.

An extra method of doing platforms that I have used in the past is a simple functional approach, All scene objects return a value for their floor level at a given X. It comes out as similar to the vector approach, but can be more dynamic. Anything standing on a floor is standing on an object so everything is effectively a moving platform, just with most of them stationary. Makes undulating floors easy


Did some really cool stuff with "pixel-perfect bitmask collision" back in the day:

1. You treat 64-bit unsigned longs as 8x8 pixel squares.

2. You do "bit magic" (shifts etc.) to align the mask of your character/entities with the landscape.

3. AND the two masks.

4. Nonzero = collision.

I never really used it for anything (wasn't sure if it was faster than more naive approaches), but it was a neat concept/challenge. I guess it would help if you were on a resource-constrained environment (NES etc.).


I used it. It's not as fast an approach as it sounds; you want to do hitbox collision first. But if there's a better way to really do pixel-perfect collision, I couldn't figure it out - maybe subdividing hitboxes would have been, but how does that work when the sprites change? I always thought of plain old hitboxes as being unnecessarily cruel - the player can't see them - but if you were on the NES, you probably wouldn't have CPU time for much of anything better.

Fortunately, I was on something less basic. Unfortunately, I was working on a bitplane mode (for my sins); the CPU didn't have a barrel shifter (so, for speed, one needed to store pre-shifted copies of sprites and masks); and, because the assembly instruction of course wants to modify the output, I ended up copying the dest mask and doing the source as self-modifying code with chains of unrolled andi.l #<character mask>,-(a0) / bne.w pairs; if the chain falls through, the player's just scraped by a mob.

This was of course back in the day that one didn't have to worry about pipeline or cache invalidation, because one simply didn't have the luxury of such things. The naïve loop/temp register implementation would be faster now (and, thanks to µcode and register renaming, would be what the CPU really does inside anyway).

Incidentally, you want to really look out for your animation code in games like this, because it impacts directly on game logic. Anything that might reset the animation counters will have side effects. I'm not sure if it was intended that Tiki - despite being a flightless kiwi - from Taito's The NewZealand Story actually can fly with repeated pushes of up mid-jump, for example (although the presence of secret level design elements catering for it suggests it may be, and could actually be a huge easter egg considering it wasn't documented!).

Similarly, Turrican II has a trick involving what happens if you fire and let off a smart bomb (space) at the same time while jumping, and then jump again - and I don't know if that's intended, but there's at least a couple of platforms with some nice goodies I don't think you can get to any other way.


IMO plain hitboxes are actually less cruel. Pixel perfect collision doesn't distinguish between solid parts of the object and things like cloth/hair/grass/feathers that would brush past without a real collision, or small loose items that would be knocked aside without the whole object catching. Hitboxes better represent these types of collisions, and you easily get a feel for where they are. Pixel perfect collision feels unfair when you collide on a single stray pixel.


> I'm not sure if it was intended that Tiki - despite being a flightless kiwi - from Taito's The NewZealand Story actually can fly with repeated pushes of up mid-jump, for example (although the presence of secret level design elements catering for it suggests it may be, and could actually be a huge easter egg considering it wasn't documented!).

Surely it was intentional. I remember very early in the game was a section where you fell just far enough to reverse your fall by rapidly tapping into flight (a very subtle tutorial), and several secret parts where a fall onto spikes could be turned into flight to a secret area.

IIRC, you could fly in the flying saucer too, but it was 2 tiles wide so many places could only be reached by flying "unassisted".

It's been a very long time since I played that game though! Arcades back in the 90s. Fantastic, difficult game.


> I always thought of plain old hitboxes as being unnecessarily cruel - the player can't see them [...]

Err on the side of the player. Ie give the player sprite a little smaller hitbox than would be warranted by pixel perfect collision detection, and the enemy sprites a little bigger one. That will feel very fair, and you can ramp up the difficulty in other ways.

Following the same principle, Canabalt famously allows you to jump a little bit after you already left the rooftop.


> 64-bit unsigned longs

> resource-constrained environment (NES etc.)

While it's a cool technique, the NES could definitely not do it. It used an 8 bit architecture (so no 64-bit unsigned longs), and didn't have nearly enough memory to store the landscape in pixel perfect format.


I have no retort, simply, thanks for the reality check. We come up with all these hypothetical optimization scenarios for nothing more than the challenge - my trick is probably useless, but it was fun to code.


A bit OT, but I recall being surprised to read somewhere that some chess engines do the very same thing.

That is, if one pictures the board as a 64bit bitmask, one can store masks for the locations of each side's pieces, as well as masks for the legal moves of each piece type when in each position. Then tasks like determining if a move is legal can be done with ANDs and so on.



If you want to watch a game being built, follow this project: https://handmadehero.org


Great idea, but an advance warning based on the earliest videos: it's windows-based programming. Just in case that puts you off (which it did me, I'm afraid).


You should give it another chance. The Windows aspects are very minimized. Make a display buffer, make an audio buffer, read a file, read the keyboard. Setting these up only take a few episodes. The other 100+ episodes deal with raw buffers.


From the frontpage:

    Will the game support multiple platforms?

    Yes! Windows will be the first platform, since it is currently the most
    common gaming platform, but the series will later cover (at least) Mac,
    Linux, and Raspberry Pi. Portability will be a major topic in the series,
    so all the code will be structured to demonstrate how to write code that
    is easy to port to new platforms.


I hate to tell you this but a large majority of game development is done on Windows.


Sadly agreeing here. I'm a Mac person and the only thing I still use Windows for is game development. I do my game development on a mix of Windows and Mac, but the reality is just that some of the tools I need/use are Windows only.

The situation is much better than it was 5 years ago and it is certainly possible for people to develop games without using Windows.


People were porting it to Linux with SDL at Handmade Pengiun: https://davidgow.net/handmadepenguin/

I am not sure if they've kept up or not, as I haven't kept up with the series, despite my attempts. Nothing against the series, I just haven't taken the time to follow yet.


Not sure if it's the same one, but there is a SDL-based port that is up-to-date. There's also native mac ports in various levels of completeness.

Casey recently added a github repo (with auth) and so it's a lot easier to keep up with the changes.


And C in a C++ mix. Not exactly vanilla C.



I've actually been looking to explore this for literally ages... I hope to play with this sort of thing someday at both ends of the spectrum, to get a bit of a practical education on how architectures have developed over the past two dozen years or so, and hopefully to have a bit of fun.

On the one hand, I'm really, really interested to understand how the pieces fit together such that it was possible to have supersmooth sidescrolling on the 4MHz CPU in a Game Boy.

On the other hand, I want to learn how to best optimize for the CPU/GPU targets in current- and next-gen desktop and portable devices (PCs, laptops, phones, tablets, etc). It might sound bizarre to want to get the most out of even a 4k-core GPU just for 2D (with maybe some fancy parallax), but 3x4K is going to be a thing more frequently than not going forward... and a pixel-perfect 144fps sidescroller would look truly amazing on something like that.

I want to understand both sides of the coin in-depth so I can optimize for each but also maintain a sense of balance: the majority of game engines are overwhelmingly future-oriented, and when presented with older hardware something like Unity will invariably choke or at least stutter, and Box2D likely would as well.

I do at least realize the complexity in building a game engine from the ground up - like I said before, this is purely for fun and education - but I have no idea where to actually start, no knowledge of older architectures (and their quirks), I still need to learn assembly language (!!) and machine code (it's on the todo list... has been for months...), etc etc.

Advice will truly be hugely appreciated.


I'm fairly certain scrolling on all Nintendo devices was a hardware thing. You were responsible for the tiles not for the pixel level scrolling.

http://wiki.nesdev.com/w/index.php/PPU_scrolling


For vector based levels I would put Elasto Mania as an early example. I don't know how much it fits into the "platformer" category though. It obviously provides the benefit of having the surface normals naturally compared to the bitmask model.


Sadly the blog was abandoned back in 2012, and never saw any other cool updates.


Great read! I'm a web developer but I play the hell out of video games. I really liked how the author explained what effects you're trying to mitigate in the collision detection algorithms. It instantly put it into a very clear and familiar context for me - I haven't programmed under these conditions, but I've definitely played games and seen silly things like this happen:

>This will prevent characters from “popping” through the slope from the opposite side.

>If you don’t ensure this, the player will move horizontally right off the ramp for a while, until gravity catches up and drags him down, making him bounce on the ramp, instead of smoothly descending it.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: