Collision in Drop Dimensions
Author: HS_Dave
- Posted on: 06/05/2017
Post Type: Blog Entry
The past few dev days have been spent working on the collision in Drop Dimensions. The original Drop used a very simple tile based collision which functioned, sure, but was less than perfect. It was possible to skip over gaps in the floor by moving too fast for one thing which in a game where survival depends on you going DOWN was a big problem.

It quickly became an even bigger problem in Drop Dimensions because the player characters are larger (twice the size infact) and the inclusion of different characters of varying shapes really meant it was time to overhaul the system. What I needed was a pixel-perfect collision system so that is what I've written. Its feeling quite nice and I'm happy with the turn out! For the curious amongst you the rest of the blog post will be about how that works. I wont bloat out the post with code but give a quick overview of the system. I've put in pictures :)

The process can be split into three headings:
-Collecting Collision Data (init)
-Collision Detection
-Collision Response

Collecting Collision Data

The first step is gathering the pixel data for the character that has been selected. Most graphics libraries (I am using MonoGame for this project) provide some sort of method to read the pixel data from a texture. It's usually quite expensive on the CPU so it is something you only really want to do once if possible. I chose to grab the data when the level starts - if I had done it when the game first loads it would mean no delay to grab data in the future but the more HD characters I added the more ridiculous the memory requirements would of become. Here was where I hit my first snag: My character sprites are large, HD, animated sprite sheets. The game engine renders them at different size to the source image depending on what is going on. The character preview for example has a very large render and in game the character is scaled down to fit the world. That means the source pixel data is completely inappropriate for collision as its way too large!

(source image size versus scaled size [what the player sees])

The solution I went with was actually very simple. I created a render target (a special texture you can draw things to) that was the correct/final size the character would appear in the game world. I then iterate through the different frames of animation stored in the character sprite sheet(s) and draw them to the render target at their scaled resolution. I then grab the pixel data for the frame and add it to my scaled pixel data array for the current source sheet. At the end of this process I have a completely accurate array of scaled pixel data.

Collision Detection

When you have all that information to look up detecting collisions becomes fairly easy and not that different from tile collision. I still use tile-based lookups for the world itself as I know in this game every collidable object is the same size as one world tile so doing a pixel lookup on the world data would be a complete waste of time. So doing a pixel to tile collision detection becomes the simple case of:

Fetch pixel data for players current animation frame
for each pixel in the data..
-Is it transparent (alpha == 0)? If so, skip to next pixel, no collision
-else get the position of this pixel in the WORLD by adding the players world x/y position to the pixel x/y
-does the pixel world x/y exist inside a tile?
--if so collision detected
--else move on to next pixel, no collision here

The "fetch pixel data" stage has a lot of potential optimisation. The first thing to note is, fortunately, character sprites in in Drop Dimensions do not get rotated at runtime. That is a big saving in headaches! But they DO get flipped. If a sprite is flipped (mirrored on either x/y axis) then you simply have to read the pixel data backwards and job is done. Now you've got your data reading well the next step is to make sure you only read it when its needed. How many times will your collision routine be called per frame by different parts of the engine? Maybe once, but likely lots. Reading out the same pixel data every time is an expensive waste. I made sure to track what frame we last requested pixel data for and I store that pixel data in a persistent array named something like LastFramePixels. If another request for the data comes in and the player is still on the same frame as the last request then it simply returns LastFramePixels again without updating it at all.

(in this image the gray represents an area the algorithm is checking inside for collisions, the blue is world tiles that are within that area, the magenta is pixels in the player sprite which are transparent and the inner gray are player pixels which can collide)

Collision Response

How you respond to a collision when it has been detected will vary greatly game to game. In Drop Dimensions I've opted for a more handcrafted situational approach than a one size fits all routine. I chose this because the simple design of Drop means there are not many edge cases to catch and it allowed me to tweak the feel of the game to just "feel nice". One thing that became quickly apparent is sometimes pixel PERFECT collision felt.. not nice. One character, a panda who moves around the world by rolling, has two cute ears sticking out the top. But whenever she rolled onto her head the pixel perfect routine would push her up and then down again and then up... and then down. It started feeling jerky and unpleasant.

So maybe it was a waste of time and I should of stuck with tiles? Well no. Some of the humanoid characters are quite tall and thin and when they try to drop off the edge of ledge but can't unless a full tile width over despite "looking" like they are stood on thin air.. well thats bad.

Solution? I modified the collision detection method to take two new parameters that specified if the X and Y axis should, independently, use pixel or tile based collision. Because my collision response is situational this meant I could finely control how each situation behaved. For example when its trying to adjust your vertical/Y axis for floor collision it uses Tile based collision for the Y and pixel based for the X to give you a consistent "ground level" but pixel-perfect pass through for the width of the character.

A few more modifications were made that allowed me to specify WHERE to check for collisions (anywhere, to the left, below the player, etc) and this means when moving in a certain direction etc its only ever looking at things relevant to what is happening. This felt really nice to play.

Heres a GIF demonstrating it all in action. Purple = player collision area (sometimes tile based, sometimes pixel, etc), green = world tile that is worth "considering" for a collision. Red = this tile caused a collision.

And now you know what I've been up to lately and more than you'd want to know about how collision works in Drop Dimensions! :)