Collision testing with with segments of a ring

About a month ago, someone on one of my college's Facebook pages made a request:

"I'm having a huge problem getting collision to work in my game. The game involves rotating rings around a planet and protecting it from enemies. My problem is that I can't find a technique that works for this. They are curved and constantly rotating so their height, width, x and y values change all the time. Any ideas??"

Most of the answers given were just suggesting pixel-perfect collision, which seemed like a bit of a cop-out to me. In many cases, pixel-perfect collision is somewhat unnecessary, and slow as well. If it's possible to do without it, I try to avoid pixel-perfect collisions and just go with a math-based check. Thus, I took the post as a bit of a challenge.

Defining The Problem

Before jumping straight into a solution, we need to know what the problem actually is. First, I should probably clarify what a ring segment is in this case.

Picture a donut, as seen from above. Now, imagine you were to cut a slice out of the donut. The resulting slice is what I refer to as a ring segment. You can also consider it a sort of curved rectangle, as well. If you're more of a visual type, here's a diagram:

Because one of these slices is cut straight from a ring, it can be defined with four values. The first two values, radius and width, represent the original ring. The radius is actually the radius of an invisible circle running through the ring's center. The width then expands from that, giving us the inside of the ring as r - 0.5w, and the outside as r + 0.5w. The other two values are the cut angles. The angles tell us what portion of the ring the segment takes up. If you notice, combining these two sets of values does exactly what I described above: It creates a ring, then cuts out a slice.

It might have been simpler just to use inner/outer radius, but I didn't think of that at the time.

Now that we have our ring segment, we can finish the problem. Our goal is simple: Given a circle and a segment, with arbitrary positions/rotations, we must determine if they overlap or not.

My Solution

As with the Circle-Rectangle collision algorithm, which I can post about if there's any interest in the subject, the goal of my Circle-Ring Segment algorithm is to reduce the second shape to a single 'closest point', then test it against the Circle's radius using the Pythagorean Theorem (A^2+B^2=C^2, perfect for testing the distance between 2 points). Since our ring segment is inherently radial in nature, we can represent the closest point with a magnitude and direction, a.k.a. a vector.

The magnitude is fairly easy to get. All we need is the distance between the radii of the circle and ring. Then, we clamp the magnitude to the inner/outer radius of the ring.

The direction is somewhat trickier, despite sounding simple. If the direction from the radius of the ring to the radius of the circle falls within the angles that form the ring segment, then that is the direction. Otherwise, the direction must be clamped to the closest of the two angles that form the segment. If this sounds familiar, that's because it is--we just did this to get the magnitude. However, doing this with angles can be very tricky. As far as I am aware, the method is as follows:

1. Translate all angles so that they fall between 0 and 360 degrees, or 0 and 2π radians. That way, we can accurately compare their values.
2. Determine if the lower angle has a higher or lower value. The lower angle can actually be larger than the higher angle, when crossing over 0, and it's important to keep this in mind.
3. With the previous information, determine which angle is closest to ours.

The main factor that makes this difficult is the fact that angles effectively 'wrap', returning to 0 once they hit a specified maximum.

Once we have a vector, we can combine it with our ring segments radius to get the closest point. From there, the process is as simple as testing whether the point lies within the circle or not. If it does, the shapes are overlapping.

The Demo

To test and demonstrate this method, I've constructed a simple demo application. Within it, you can place and size a circle, and see it collide with 9 different preset segments. It should run fine on Windows and Linux computers, and all code is included with the binaries.

A bit plain, but it gets the point across

Download: Windows Linux

Inaccuracies

I think it would be quite unfair of me to finish this post off without mentioning that this algorithm isn't going to cover all use cases. It works quite well when the circle is smaller than the ring, but as the circle's size increases the accuracy decreases. This is due to an issue with how the magnitude is calculated. The algorithm doesn't properly get the best magnitude at the specified angle, only the best in general. When an exceedingly large circle lies outside of the ring and collides with the inside of the segment (due to its shape-see below), then the algorithm will report a miss until the outside of the segment is overlapped as well. This leads to inconsistent collision checks, something you never want to have. However, the accuracy should be spot-on with smaller circles, so in many cases this algorithm will still be perfectly serviceable.

Notice how the misplaced 'closest point' fails to fall within the circle, resulting in a miss.

And so, we end our little detour into the land of collision checking. With any luck, I'll be posting soon with some more new stuff.

DFEngine: What's new

As I promised in my post about rewriting DFEngine, here's a look at some of the differences in the new version. Buckle up, this is going to be a long one.

To the West Postmortem, and 10 lessons for next year

Note: For those uninterested in reading too much, click here to scroll to the list of things I learned this time around.

It's a bit overdue, but here's a postmortem for my latest 7drl entry, To the West.
For those of you who haven't played, To the West is a roguelike that discards the typically 'vertical' gameplay of a roguelike where you go down a dungeon floor-by-floor, and instead replaces it with a long 'path' of naturally terrain, scrolling horizontally. While the game is not super-great, I actually think the jam went rather well, all things considered. My game has been reviewed twice, as far as I can tell, and while the reviews weren't very positive I still feel happy with the result. Here's why:

What Went Right

The feedback I received was very close to my own reaction to the game, and I like that.

One of my big goals in with the game was to have an engine that would allow me to create interesting things for players to encounter, and it seems like I was able to accomplish this, at least on the engine side. Of the positive feedback in the game, most of it related to the variety, and the fact that there were some interesting and unique things to be found. One of the reviews mentioned liking the Potion of Lakes, and item that forms a lake wherever it lands. The other mentions liking the occasional pieces of flavor text that vary from area to area.
I also really like the negative feedback. Much of it reflects problems and frustrations that I personally had, and parts of the game that I knew weren't very good. This is actually a good sign, because it means that the premise I was working with was sound.

What Went Horribly, Horribly Wrong

Unfortunately, not cool bugs like this one.

BUGS!

This game is an incredibly unstable kludge. In fact, I'm amazed it runs at all. About halfway through, the engine began to collapse under itself in a veritable torrent of segmentation faults. Turns out, when you rush and play willy-nilly with your pointers, bad things happen! You'd think I'd know that by now, but apparently not. Anyway, the result was the loss of multiple cool features, as well as hours of good development time. The faction system that allowed for interesting interactions between different units had to be totally scrapped, which is why there are no sheep, mountain dwarves, or other friendly sorts in the world anymore.  On top of that, the lost time meant that I had significantly less time to polish and balance things at the end. I can actually still think of a few major issues with the game, including a game-breaking crash that no one else seems to have noticed.

My other big issue during the week was in fact balancing. At the end, I must've spent close to 5 hours playing the game over and over, constantly tweaking numbers. In the end, I had to stick to a beatable game, but the result was the loss of a lot of interesting strategic challenges and scary early-mid game fights. Instead we just have a boring grind that ends in an interesting but too easy boss fight. With another day, or even a few more hours, I might've had a good shot at making a well-balanced game. However, I simply ran out of time. It didn't help that I had some interesting variety, but there wasn't enough content to keep the game interesting.

The last issue, but certainly not the least of them, was the porting. My first issue was trying to figure out how to cross-compile a console application to Windows. It *should* be so easy, but you can't search for a solution on Google. Due to the nature of the subject, you'll only find tangentially-related topics, making it much harder to learn the process. I then had to try pdcurses, which can handle curses output to a proper window. Unfortunately, this comes with certain issues of its own, which delayed the windows release for way too long. It wasn't until someone left a comment here asking about it that I found the motivation to sit down and fix all the issues and get the build out. On top of that, pdcurses has limits that I didn't expect from the windowed version. (For more information on color limits and such in curses, look here) I don't know why the version that renders text with SDL has a 16-color limit and can't render bold or blinking text, but it's pretty ridiculous. I've heard tales of a patch that removes these limits, but I haven't had time to explore further. The result was a working but half-baked colorscheme that pulled my review scores even lower. (Also, there's the bug where for some reason the cursor won't move in the SDL version, so I had to rewrite parts of the tile targeting code to match. That was extra-dumb).

Lessons Learned

I learned a lot, so this list may be incomplete. That said, here are 10 lessons that I learned during 7drl, mostly the hard way:

1. The panel curses library is pretty great, but next time I need to be more careful how I use it.
2. There are a few other curses libraries/techniques that I ought to learn, especially scroll.
3. With enough care and diligence, it's actually possible to get some fairly decent performance out of curses. I can make it pretty snappy if I'm more careful about my draw calls!
4. If the jam is 7 days or longer, I need to spend more time on architecture and setup. Some of the issues I had might've been better avoided with a nicer structure, and the small amount of architectural work I did payed off nicely.
5. I must stay consistent to my coding style, no matter how short a jam is. If you actually look at my code, it's a mess of naming conventions, which probably slowed me down considerably.
6. In retrospect, switching to NeoVim mid-jam might not have been the brightest idea.
7.  I should get all of my tech working on all of my target platforms pre-jam, even if I already know they'll work later. I should also relese binary demos if time permits it.
8. Before next 7DRL, I should put together a small set of useful utility functions that will make my life easier during the jam. Logging would be extra-useful, as would some form of color palette management.
9.  People like interesting and varied content, and I should reserve at least a day or two for just content building. However, I shouldn't start too soon, or it might end up making more work for me in the long run.
10. Valgrind, everything, always.

I enjoyed last year's 7drl, and I loved this one even more. I haven't made anything great so far, but I think I'm improving well. Hopefully, next year's entry will be really great!

If you read all the way here, then enjoy this little announcement: To the West isn't over! I really like this idea, and I want to see it reach it's full potential. Thus, I'm going to continue working on it until I feel like it's done and polished. Obviously, this will require me to rewrite all of the code, so don't expect much anytime soon, but I figured this was a good time to say it.

7DRL 2015: Done!

It was a bit rough towards the end, but I finished. This is going to be a short post, but I'll be putting up a longer postmortem of the whole thing soon. In the mean time:

Development Album: here
Main Posts: 0, 1, 2, 3, 4, 5, 6, 7
Code: here
Postmortem: here

EDIT:
The Windows build is (finally) available here!

EDIT 2:
The postmortem is done: here

7DRL 2015: Day 4

I have created the next indie hit: Dragon not-dying simulator 2015

All silliness aside, I've made some pretty decent progress. Sonce Monday, I've made the scripting side of things significantly more powerful, and I also finished up the base monster ai. Any monster-specific ai quirks occur in scripts, which so far work pretty well. I had some bug issues, but they seem to be sorted out now. I added levelling on Tuesday, although it needs to be fleshed out more. I finished the effect system today, which is why the dragons are basically walking tanks now. The effect system is designed to be very general and powerful, so that I can do quite a bit with it, such as altering terrain, spawning enemies, and more.

The data-driven setup is really paying off now. I have 7 biomes and 12 creatures already!