The Character Controller: Tile Map Collisions, Part 1

Yeah, I'm now doing a series within a series. Great.
I really wanted to do everything about grid based collision testing in one post, but I got the basics working in two or three different ways already, and haven't figured out non-square colliders quite yet. Since there's actually multiple of those that I want to make, I figured I have to make this at least three posts.

This is the first part. The easy part. Sigh.

Defining the Collision Map

First of all, we need to go back into the TileMap class and add collision data.

We could do crazy stuff like having a more fine grained collision map, so you'd have four (or nine, even sixteen) pieces of collision data per visual tile. This is actually what the first Pokémon games did, though their blocks were actually 32 by 32 pixels.
But! That's quadratically more colliders we need to test for an equally large character hit box. Time we could spend elsewhere. Like on more complex colliders that give us floating precision, rather than keeping us tied to the grid. We'll get to those later.

For now, let's just define a field of type TileCollider[,]. We'll then need to define the TileCollider type. If you wanted to parametrize the complex colliders, you could use a struct. I didn't see the need, so I went with an enum. We can switch later on, and define constants for the non-parametrized ones, leaving the previously written code functioning.
Since we're only doing the basics today, the only values we'll need are TileCollider.Passable and TileCollider.Impassable. The former isn't actually a collider and just lets us pass through, while the latter is a square collider around the entire block.
Add some code to the test constructor and we should be good to go.

Identifying Relevant Grid Cells

Back in the character controller, we now have to make use of the collision map somehow. It would be pretty easy to just iterate over the entire map and collision test against all cells. There's two problems with that: Obviously, it's really unnecessary because we can probably identify what cells are relevant, and because we might have to do two passes, depending on how we implement some colliders.

We could use the same optimization here as we did with tile rendering; calculate the bounds of the relevant subsection of the grid and only loop over that;
Do that twice - with slightly different loop bodies, and you should be able to get even complex colliders to work.

There's other options, though. For one, we probably don't actually need to do collision tests on the cells that don't intersect with the edges of the hit box. However, unless the hit box is larger than 1.0 on both axes, that's zero cells, so that's a completely stupid (and surprisingly hard) optimization to make, unless you want to have the player control a larger character at some point.
Or you want a theoretically complete, reusable engine. Which is a kind of ridiculous idea, because you'll probably want to make some changes with every new game you build, no matter how good your engine is.

You could also look at only the corners of the hit box in the first pass, and only the edges in the second pass. We'll get into why that would work (and what you need two passes for in the first place) in the next post, but for now, suffice it to say that it would probably work.

If you get either of the edge/corner only approaches to work, these are pretty easy to optimize, as you only need to check one edge (two corners) during horizontal and vertical movement, and two edges (three corners) during diagonal movement.
But both of them are somewhat inconvenient to implement, so I'm not sure that's really worth it, especially if you consider that the character controller only runs once per frame. Maybe two or three times, if you wanna have the kind of enemy/puzzle element that imitates the player's movement in a different collision environment.
Even if you have to optimize it, you'll probably want to start with entity collisions, because that takes a variable amount of time, depending on the number of entities.

Detecting and Handling Tile Collisions

Now that we have a loop, we can start detecting and handling collisions. How that is done depends on the collider, though, so let's start with a switch statement like this:
The passable collider doesn't actually have to do anything, since movement is supposed to be unaffected there, so we'll just leave it like that, and make it the default behaviour as well.
As for the impassable collider, we actually kind of have that already, as entity colliders are rectangles, and we just want an ol' square collision test.

I decided to make a function I called TestSquareCollision, which got the positionOffset as a ref, so it could modify it without returning it. I'm not sure implementing it exactly like that was the best idea, as there's actually some stuff in the entity collision handling that has yet to be added, which doesn't have to be shared with grid collision testing, namely the ColliderComponent.Passable flag, determining whether the collision should be handled or merely detected, and script hooks which may need to be called.

Either way, implementing the impassable collider now becomes trivial by calling TestSquareCollision like this:
Before we wrap this up, there's one more thing: If we leave the bounds of the map, we'll be greeted by an IndexOutOfBoundsException, because we try to test colliders outside of the collision map.
That's not really acceptable, so let's implement something akin to border blocks. Except we don't really need a border block collision map. Generally, we don't want the player to reach outside the map, so we can safely prevent it like so:
Testing this will reveal another bug though. When sliding along the edge of the map via diagonal movemene, we'll emcounter the "literal corner case" from before, which we currently handle by throwing an exceptioin. Which at least brought the issue to light, though the fix is just not doing anything, as it turns out. You may still want to log it, in case it occurs in other situations where not doing anything is inappropriate, but for now it's fine.

And that's the basics, really. If you don't want fancy collider shapes, you're done. Imma need at least six more, (though that's really more like two in various orientations), which we'll cover in parts 2 and 3.
Until then!

The Character Controller: Entity Collision Testing

Now that we can place sprite objects on our tile maps, it's time to make stuff move. We already did that with the AnimationComponent, to some degree, but we should give the player some control now, shall we?

Basic Movement

Thankfully, we already have our input mapping down, so there really isn't anything to get in our way with this. Let's just start with a CharacterController class like this:
You can imagine how the constructor goes, so let's jump straight to Update(). To consistently move (and later, animate) our character properly, we'll need the time that has passed since the last update, but for now, that's pretty much it:
Now, let's think about how we actually want to do this.
The very first thing we'll do is process input, since there is no point in doing anything else until we're certain the player actually wants to move their character. Now that we know we're not dealing with zeroes, we should also normalize the direction vector so diagonal movement doesn't become absurdly fast (although that might be an interesting option if you want to optimize your game for speed running). In the same step, we can also calculate the actual position offset: As you can see, I also added a "sneak button" which halves the movement speed. This is because I wanted something akin to the run button in many old RPGs, with a better reason not to press it; usually, people would hold it down all the time, unless they were in a tight area that required more precise navigation. This just inverts the roles, and spares you some thumb pain.
To complete basic sprite movement, we just need to add the positionOffset to our Character.WorldPosition.

Collision Detection

Now for the interesting part, I decided to implement collision testing against other entities before testing against the tile map, because it's easier to test quickly and presumably has greater implications for our data structures; making map collision suit that data would be easier than vice versa.

The Collider Component

Speaking of data, let's talk about the ColliderComponent class. Like the SpriteComponent from last time, it points to an Entity, holding its WorldPosition, and then has some data of its own.
For now, that's just data defining the size of the collider. Later we'll add collision behaviour related stuff, like script hooks. How do we define the size of the collider, though?

We could use circle colliders; with the entity position as the center point, we only need a radius, and collision testing circles is super easy. But since our maps are based on an orthogonal grid, using circle colliders is kinda janky when you need to block a path with entities or something.
I'd rather use AABBs, but the Entity.WorldPosition represents the entity's center point, and we can't use Rectangle because it's integer based to boot. So this is what I ended up with:
I decided to use a Vector2 to store the width and height of the bounding box - we'll have to do intersection tests manually.

To use this class, I just replaced the Entity Character with a ColliderComponent Character and changed all references to it to Character.Master.

Testing for Collision

To do the actual collision tests, we first of all need a list of other colliders to test against. Once we pass that into our Update method, we can just loop over the collection, calculating the actual bounds of the respective hit boxes:
Finally, we need to test if the two rectangles actually intersect. Since, they're axis aligned, that's pretty simple as well:

Two rectangles A and B intersect, if their edges are arranged ABAB or ABBA on both axes.

You can easily assert that by checking if the left edge of A is left of the right edge of B, and the left edge of B is left of the right edge of A. Repeat for other dimension/s.
In code, that looks like this:

Handling Collisions

Many tutorials bail at this point, or explain the obvious options, like projectile hits (Apply projectile effects, Remove projectile from play) and knock back (Move the object into the direction it came from or do more fancy calculation to determine knock back direction).
Turns out creating an object that's simply impassible is pretty hard to get right; you might encounter jittering sprites or weird jumpy behaviour. Neither is particularly pleasing to look at, and might cause more serious bugs down the line (e.g. if the object jumps somewhere it can't get back out from).

So, how to do it right?
I decided to approach this very carefully, ignoring diagonal movement for a while:
Essentially, we find the relevant edges, depending on which direction we're moving in, and reduce the positionOffset by the difference. If we changed direction, rather than speed (i.e. changed the sign), we set the speed to zero instead - this keeps the sprite from moving at all if it can't go some direction without a collision.

To add diagonal movement to the mix, we actually only need to modify the outer conditions a bit. If we're moving diagonally downward, for example, but can't go downwards without a collision, we want to keep the horizontal speed, while reducing the vertical speed.
To determine which axes we need to keep intact, we need to introduce another rectangle; the bounding box of the Character at its current location:
As to what we'll do with that: We'll test the intersection condition mentioned earlier, except we'll test the axes separately. If the box is above or below the other rectangle, we need to limit vertical movement, if it's to the sides, we need to limit horizontal movement:
There's one literal corner case unaccounted for in this code: if you approach a collider vertically, and it does not fulfill either condition, you get unhandled behaviour. Try as I might, though, I haven't been able to force that behaviour, and it's difficult to say how to handle it appropriately. I decided to just log that and not worry about it too much. If it practically never happens, and there isn't too much to worry about (I suspect a little jump at worst), there's better places to spend your time.

Better places, such as collision testing against the map.
Which is what I'll be doing next.

Until then!

Map Objects: Rendering and Animating Sprites

Yes, that's right. I actually started working on my supposed main project again.

The Results

Before we delve into the code, here's a shitty gif of what we have so far. You'll have to excuse the quality, I haven't looked into screen capturing software yet, so I made this with screenshots and a simple gif converter:

At 500 FPS, which I'm currently getting on my machine,
this actually doesn't look like a strobe light.

Also, here's my Tilemap.cs file, copied verbatim. That should give you an idea of why I haven't been working on this for a while. It's feature creep at it's finest.
But that's okay, it's mostly throwaway code I wrote knowing it'd be rewritten once I knew how everything should fit together.

The Code

Okay, let's talk business. Right at the top, there's a monstrous [Flags] enum that I haven't talked about before, but that doesn't get used until much later, and it's not like the enumeration itself needs a lot of explaining, once we get to that bit.
The truly new part, though, are the following type definitions: The all important Entity class with one whopping member, the SpriteComponent and AnimationComponent, and some other animation related data structures.

Sprite Rendering

The SpriteComponent is relatively simple, mostly because it doesn't define any methods. Scrolling down to TileMap.DrawSpriteLayer(...), it should be pretty easy to see how it's used:
The TileMap has a List of sprites and simply renders them in order, if the passed layerIndex is equal to their own Layer member. The position a sprite is rendered at, of course, depends on the Entity.WorldPosition, but just rendering there won't do too much good; generally, we don't want the sprite's top left to be the Entity's center point, so we use half the sprite's width and it's full height, converted to world units, as a negative offset.
In case you're wondering why I don't use a different SprteSortMode if I'm just rendering in order, it's because sprite sorting seems to be broken in MonoGame [citation needed], so I just sort all sprites in the same list, before calling DrawSpriteLayer() multiple times. Also, n*log(n) scales better than n*m*log(n/m).

Animations

Since the animation data structures also don't define any methods, let's jump straight to the code that processes them. It's in TileMap.Update(...), and enclosed in the second profiler.BeginOperation /* ... */ EndOperation block. That's lines 368 through 418.
Again, the TileMap keeps track of all AnimationComponents in a List, and iterates over that list, though the update logic is a tad more complex than sprite rendering.
Of course, we skip null entries, as well as components that currently aren't playing an animation, as signified by a negative index. We then update the timer and pull out the current frame's duration from the nested data structures.
We then calculate a new world position, which was actually pretty difficult to get right: we regularly sort by position, and so we can't use an offset we add during rendering, so no lerping. I'm still not convinced this is right, but at the moment, testing is rather difficult, and it's still throwaway code, so I don't really care quite yet.

The next part, you'd be familiar with; if the timer is past a threshold, we increment a frame counter and subtract from the timer, in preparation for the next frame.
Then we need to find the next frame in the animation, which is the short bit in the following else block. If there is no next frame (signified by another threshold), we look at the AnimationSequence.
This is the least self-explanatory part in this update, I think; the AnimationSequence is essentially a list of animation definitions that we want to play back in order. This would be used by both passive behaviour (instead of parallel script execution) and event scripts.
To reflect this duality, each AnimationComponent has two sequences: the active sequence, which is the one we use to look up the next frame, and the default sequence, which is set as the active sequence when we're not executing scripts.

The script engine would have to lock sprites by setting the active sequence to null and could then animate them by setting another sequence. The sprite could later be released by resetting the active sequence to the default sequence.
This is not actually reflected in the code at the moment (I don't know why, actually - I'll fix that once I'm done writing this), but it will be at some point.

Other changes

It's been quite a while since the last time I let you people look at my map rendering code, so there's some other new features, such as parallax backgrounds, but that's actually not that much code, and more related to the camera, which has to get a different matrix calculation method.
There's also unmentioned leftovers from the initial refactoring, such as the LayerSettings enumeration, but I think if you look at the Draw method, that shouldn't be too hard to figure out. The complicated part there was precalculating the look up tables, so if you take those for granted, the code itself isn't that bad.

What's next?

Now that this ordeal is over with, there's a few options of what to implement next.

• Of course, I could do another refactoring, but the other subsystems will also tie into the TileMap class, so prototyping these will mess it up again. I'll do that when the TileMapView is feature complete and I want to thoroughly debug it.
• Now that we have the visual aspect of maps down, we could think about implementing BURGLE, the level editor for this engine. That would simplify testing quite a bit, but keeping two code bases up to date on an experimental API is a lot of work.
• Testing could also be simplified by implementing debug visualization, but I refuse to do that until I overhaul the configuration and logging facilities, and by extension, the profiler. Making the latter two non-static was a stupid mistake, and the .NET standard config and logging facilities are just awful to work with.
• We could also ignore all that and get to work on the next engine subsystem, either the audio engine or the character controller, as a prerequisite to the physics system (which will not be a complex simulation; collision will only be tested between the player character and other entities).

That's all I can think of as sensible at the moment, but I'm a bit torn. Blogspot statistics tell me I have, like, two loyal readers, so if either of you have a strong preference there, let me know in the comments or message me on reddit (/u/teryror), if that suits you better.

UPDATE: The two page views I expected are in, and I haven't gotten any messages concerning this, so I decided to approach the choice from first principles.
First of all, coding the level editor would require a significant amount of work in areas other than map rendering, and I don't think I should leave this code to be half-forgotten before rewriting it. The same goes for the entirely unrelated debug facilities.
Choosing what subsystem to implement next is a little non-obvious in this regard. The audio engine is on the same level as map rendering, as it should also work regardless of game state. However, the code is not all that involved with the map itself. There are a couple of related map properties, such as the default background music and echo settings, but collision detection is inherently involved with the map, so that's what I'll work on next.

Of course, you can also let me know if you have questions about this rather terrible code, though I'd understand if you wouldn't want to touch that with a ten feet pole.

Anyway, see you later!

Analyzing Color Palettes: Introducing Impale.fs

As announced last week, I've been working on an image analysis utility called Impale. It's just 39 lines of F#, but not being used to the language and fucking around with various plotting frameworks (none of which I got to work in a reasonable time) led it to take like 12 hours of work.

You can find the code here, but we'll be going over it now anyway, before we apply it and see if we can learn something new about pixel art and color palettes.

The Source Code

First of all, we open some stuff, which is essentially using in C# terms. We use System.Drawing to read image files, System.IO to write CSV files, and I had to add System.Globalization because my PC is running a German locale, which means I usually can't just use ToString on floating point numbers and expect it to play nicely with basically any tool ever made in the US. Which is practically any tool, ever.

We then define the main function and mark it as the EntryPoint, which could be any top-level function in an F# program, I just decided to name it main anyway. It doesn't actually do anything interesting by itself; we just define a local function analyze, and use Array.Map to apply it to all arguments that were passed to the program. Finally, we return 0, for no particular reason, other than not bothering to look up how to properly return unit, the F# equivalent of void.
Note that map actually returns a new array, where each element corresponds to the result of analyze when applied to an element in args. Since we only call analyze for its side effects (creating two files), we have to ignore the result explicitly, since F# expects us to write programs without side effects.
ignore is actually a function itself: the |> operator redirects the value on its left into the function on its right.

The analyze function

This is where all the actual work happens. We start off by opening a bitmap, and converting it into a flat list of colors using list comprehension. We then use List.distinct (which doesn't seem to appear on MSDN for some reason) to get the set of all colors in the bitmap, except it's still a list, not an actual set.

We then define writeLine, a local function that prints a properly formatted (float, float) tuple to a StreamWriter.
We also define getValueSaturation, which extracts such a tuple from a Color instance using the GetBrightness and GetSaturation methods. We then get our first set of data points using List.map again.
Next, we create a StreamWriter to a (hopefully) new CSV file and use partial function application to create an anonymous function based on the writer and the writeLine function. If you think of it as a family of functions distinguished by the StreamWriter they use, this is a pretty cool form of metaprogramming.
Finally, we close the stream because we're good citizens.

Room for improvement

These last couple steps are then repeated with a different file extension and a different color-to-data-point conversion function. Since you can pass functions around easily, this is actually redundant code, I just copy-pasted it as an afterthought after I got the first step working.

We could also have done a more sophisticated data analysis, for example by grouping the colors into color ramps, adding more valuable information.

Since I didn't want to bother getting XPlot to work, the script currently puts out CSV files which I have to manually paste into fooplot. Visualizing data automatically would be a great boon.
At least I don't have to manually gather color information with Paint.NET or something...

But... why?

Essentially, you can learn pixel art by trial and error. You can get better quicker by looking at other people's work. Outlining, dithering, applying texture to a surface. I feel like I'm reasonably good at those techniques, and you can learn them by zooming in and studying images that do them well.

However, learning to properly construct palettes is hard. You need to reconstruct the palette from the image to get an overview, you need to understand basic color theory and understand how the palette relates to the image as a whole.
Just extracting the palette is tedious work and easy to mess up. Visualizing it in a meaningful way to understand why it works is itself pretty boring, but necessary to perform any kind of analysis.
This tool is supposed to help with these two steps in particular.

We gather all colors in the image and spit out two scatter plots in CSV: One shows the relationship between saturation and brightness, the other between hue and brightness.
Let's look at a couple of examples to see how that can be an immense help in palette analysis.

Pokémon Garnet

Okay, so this is a long dead RPG Maker XP based fan game, but it's easily the best looking fan game I've ever seen, it arguably looks better than the original Pokémon games, and it's up there on my list of best looking pixel art game, full stop.

I mean, just look at this:

This game is gorgeous! And that's because it has an obviously carefully crafted color palette.
Of course, the line work and shading are pretty good, too, but most of these tiles are recolors from freely available tile sets; they just aren't the distinguishing factor.
The palette alone isn't enough to make it stand out, though. The levels (or, at least, the few screenshots we have, the game never saw a release) are actually designed with the palette in mind: Each area has a very distinct color scheme.
Anyway, let's do this analysis.

First of all, we need to beware of the screen overlays this game uses. We could keep them in, but since I plan on using some too, we should only run the analysis on portions of the screen that aren't affected by the overlay.
For instance, the scene at the beach is complicated by god rays and lens flare. Using the magic wand tool with global selection and zero percent tolerance, I selected and copied an area of the screen that wasn't overlaid with anything and ran the analysis on that.

Starting with x=Brightness; y=Hue for the beach scene

Immediately, we can see clear bands of color. That's the color scheme I mentioned. We have some obvious outliers; the medium-bright purple/pink at the top is the NPC in the top right corner, the really bright blues on the right are at the water/land border, where there's spume. The yellow near the middle of the lower left quarter is probably from one of the NPCs as well, though it's not obvious.
Other than that, there's two obvious groups, one in the 0-45 degree range, the other in the 180-225 degree range. So we're actually dealing with near-complementary colors.
Furthermore, both groups can be split into at least two color ramps each. It's a little difficult to tell from the diagram alone, but we know that the orange group is made up of the light, yellow sand and the dark, brown rock, while the water is split into the light blue rock surface and the dark blue rock walls. While it's not necessarily easy to tell which color belongs to which ramp, it's clear there's no definite trend within a ramp. For example, I remember quite a few tutorials saying that as colors get brighter, their hue should trend towards 60 degrees, i.e. yellow, making the light source appear yellow. Here, there seems to be mostly steady hue within a ramp.

x=Brightness; y=Saturation, also for the beach scene

For saturation in relation to brightness, we see a general upwards trend, with few colors in the lower right and upper left quarters. We can also see that the density in the lower left is a lot higher. There are few obvious color ramps, though.
You might also notice that, other than black for sprite outlines, in this image there's exactly zero colors that have less than ten percent value or saturation.

I'm not going to write a full analysis like this for every screenshot I have, but looking at some other saturation/brightness diagrams, there's one rule that feels really important: saturation and brightness rarely sum to more than one, and when they do, it's usually on an interactive object.
You can see this for yourself by drawing the function f(x)=1-x. Only few colors will ever fall above the line. For example, this is from the top-right forest scene:

Of course, this diagram doesn't show the general upwards trend, and there's colors with less than ten percent brightness and less than ten percent saturation, though there's still no zeros there, and none with both values in the deep end.
In fact, in this scene, if you were to color code the dots by which ramp they belong to (which I actually did using Paint.NET and Excel one time, motivating me to write the script), you'd notice that the saturation in each color ramp decreases as brightness increases.
In the portion of the screenshot I analyzed, there's no NPCs visible. The only colors above the previously mentioned line are outlines of collidable background objects. If I added NPCs, the top right of the chart would get filled in more.

When combined with the black outlines Sprites use in this game, this is a great way to lead the eye and to make interactivity visually obvious without placing silly exclamation points above characters' heads.

Conclusion

All in all, I think this was totally worth the two evening-nights I actually worked on the script and the past couple hours I spent analyzing this. As always, we could go more in depth, both with the script and our manual interpretation, but I think that's enough for today.

See you!

Staying Alive

Just a quick update on what I've been up to, since it wasn't a great idea to release five queued up blog posts in two weeks, as it turns out.
I couldn't have known, really, I just happened to lose almost all my motivation over these two weeks, and got hooked on Dontnod's Life is Strange. I played through all four available episodes in, like three days. Twice. Once the fifth episode is out, I'll try and write an in-depth analysis of that game's design.

Until then, I'll try to stay focused on building a game, but before I return to doing actually useful stuff for the project, there's one last F# project I want to work on.
I call it IMPALE, the IMage PAlette anaLyzEr. It's just a small console app that takes an image file, performs some data mining and spits out a couple of diagrams in another image file.

I don't have any big plans in store for that, and I don't intend to let it take longer than like a week, but no promises. Until it's done,

see ya!