Hitboxes

[DivFord]

While talking about enemies, we mentioned hit-boxes. I thought it could do with its own issue.

I believe my thinking on hit-boxes stems from this article: http://devmag.org.za/2011/01/18/11-tips-for-making-a-fun-platformer/

Basically, if the player wants to hit something, make it easy to hit, otherwise, make it hard to hit.

[Fyll]

T'is an interesting read... Is that where you got the jumping leeway from?

With regards to hitboxes, I did just guess the numbers by looking at the pixels on the first image on the spritesheet. The main difficulty is the difference in hitboxes between frames: Either the walking RL is going to have too small a hitbox (and thus be hard to shoot (counter to big hitbox for good things) and walk a bit into walls), or the rolling RL is going to have too large a hitbox (and thus be against the spirit of small hitbox for bad things).

Having thought about it a bit, the best solution I can think of is to just have an optional parameter for SpriteMaps being the temporary hitbox. It'd then be a bit fiddly passing the new dimensions back to the Object (the thing that cares about the hitbox) from the Sprite (the thing that recieves the information on the SpriteMap).

[DivFord]

Or we could do pixel-perfect collisions (http://www.shamusyoung.com/twentysidedtale/?p=21007). It's more elegant, but very possibly not worth the hassle.

[Fyll]

While pixel perfect hitboxes would be nice, it would run against the small hitboxes for bad things concept. Also, seeing as this is going to have to be handling collisions between many objects (not just bullets), it seems like it could be quite cumbersome.

glReadPixels() seems like it would be the function to use, but that still involves a lot of moving things in and out of the buffer. Also, it would alter how the collisions would be detected. As is, it tries to push things out of bounding boxes, but if we're going pixel perfect, I have no idea where you'd try pushing things to.

EDIT: Actually, having posted this, it immediately occurred to me that you would only have to read the pixels once, and then just keep polling an array with all of the alpha values in. That'd be a bit nicer, but still leads to collision problems.

[DivFord]

Good point(s).

Here's another idea; could we have one hit-box for colliding with the world and with bullets, but a different one for attacking?

[Fyll]

But how is attacking defined? At the moment, what you're calling attacking is just running. The RL is always deadly to the touch, it's just that it rolls at you if it sees you, so looks like it's attacking.

[DivFord]

Surely, whichever way we choose to solve this, we have to know when to use each hit-box?

[Fyll]

I'd prefer just having different hitboxes for different sets of sprites, in case we want something later down the line that wants three different hitboxes.

[DivFord]

Fair enough. Is your plan to just manually enter the dimensions for each frame on the sprite map? Sounds quite labour-intensive.

[Fyll]

I'll have a default hitbox for the Unit, but have the option for a SpriteMap to have it's own hitbox. Yeah this'll mean some frames are a little off of the right size (e.g. the jumping/falling frames are taller and thinner than running ones, but it's close enough that I probably won't be bothered to redefine the hitbox for them), but the drastically different ones (e.g. the rolling ones) will be separately defined.

And maybe someone could go through and change them all to be frame specific towards the end of the project when we're just prettifying things... :P

[DivFord]

I imagine that would work… Thinking about, you'd want to define it by animation rather than frame anyway.

[Fyll]

Aye, true. it's not like we need to be completely exact anyway.

[Fyll]

Actually, looking at the code I've got, if I can get this up to working it'll use hitboxes defined by a series of vertices, so we could have the hitboxes be arbitrary shapes, which would be nice.

[DivFord]

Arbitrary rectangles, I assume?

[Fyll]

Nah. Any series of corners. E.g. If you wanted a cactus, you could have a hitbox like:

[DivFord]

I bet it turns out to be more complicated than that...

[Fyll]

Well, it mostly did. However, it's pretty solid(-ish) for boxes, and can handle silly objects, e.g.:

...ended up as:

There're still a few issues, but they're glitches rather than bugs (things have a nasty habit of spinning around at the slightest provocation). I'll try to iron them out, implement friction, then glue it into the code.

Also, the code contains a time step variable, so that should make the speed-up/slow-down pickups a lot easier.

[DivFord]

Looks good. I'm excited to see it in-game.

[Fyll]

Okay, another step further. I'm now just testing every shape I can think of in whatever combination I can think of, to see if there are any bugs or whatnot wherever. Ideally, once it's in the code we'll never have to look at or fiddle with this again.

Consequently, I'm curious if we think we'll want circular hitboxes (e.g. rolling RL), as they'll need a lot of exceptions in the code (not in a bad way. They'll just skip over a lot of the checks (as I only need to check radii). I haven't tried implementing it yet, but I believe it'll be simple...

[DivFord]

I reckon we probably do… Bullets, for example, would make more sense as circles than squares. Plus, if the circle is simpler, we can probably boost efficiency (a tiny bit) by having circular bullets.

[Fyll]

Actually, having had a quick stab at it, I'm going to have to correct my previous statement. Circle-circle interactions will be simple. Circle-polygon interactions are just a mess... :(

Do we still want them? Bullets should be small enough that we can get away with squares.

EDIT: Never mind my whining. Circles work now (and probably are slightly more efficient than squares).

[Fyll]

Okay. A final set of pictures before I try gluing this into the code. There's still a slight problem with it, but it only shows up in very specific circumstances, and I have absolutely no idea how to go about fixing it without being horrifically inefficient:

...stabilises at:

[Fyll]

Hooray, an update! Ahem.

That bug that I described as "only shows up in very specific circumstances" is now causing me loads of problems. >.> I should have seen that coming.

Here's a (big, so if anyone knows how to make compact boxes, that'd be great) .gif of me playing (just to prove that it works. The fuchsia boxes are the outlines of the hitboxes, the small yellow lines show how far you've moved last frame, and the blue circles mark which nodes have been moved):

You can see things mess up when I get stuck on top of the crate. What's happening is that my bottom right corner is going over the top right corner of the crate, then when it gets pushed out after that, it gets pushed out across, rather than back up. Thus, we get locked together until I smash it. Also, the jumping is very dodgy (I generally can't jump whenever the bottom of the Player's hitbox has the two circles on it).

[DivFord]

"and the blue circles mark which nodes have been moved" <- This seems like it can't be what you mean… Lots of static geometry has blue circles on the vertices, and the top two vertices of the player hitbox mostly don't. Do you mean nodes that have been adjusted to meet physics constraints?

Could you explain (in broad terms) how your system works? I assume we're looking at some sort of graph structure. Does it include surface normals?

[Fyll]

Okay, what I said was inaccurate. Any corner which has a blue circle on it has had an attempt made to move it since the last update. Whether or not it actually moved is irrelevant.

Graph structure? I'm using Verlet integration to update it (with 8 iterations). In brief, it does (up to) 8 loops, and on each loop it checks if each node is anywhere it shouldn't be. If it is, then it corrects the nodes (simultaneously), then reshapes everything that got deformed by having one of its nodes moved.

[DivFord]

Could it just be a mass problem? The thing with the crate is presumably what you'd expect to see if the crate and the player had similar masses. Does your system have friction?

[Fyll]

Yup, I don't think it's all that visible in the gif though, but I do slow down. The reason for the lack of jumping I imagine is the fault of nextToDir() being too sensitive, and telling the Player that he's not standing on anything because he's overlapping a couple of pixels into the crate.

To be honest, that's my big problem with Verlet: it's implicit. It just feels bad that I'm having to make approximations to overcome the inherent approximate nature of the engine.

[DivFord]

So, is it just a question of tweaking values now?

[Fyll]

Not so much. There's the getting-stuck-on-corners issue to sort out to.

Also, having tweaked where the circles are drawn, it correctly no longer implies that the walls are moving, and only draws circles on nodes that have actually moved.

EDIT: Also also, having quickly desensitised nextToDir(), I can confirm that this allows you to jump off of crates. It unfortunately has a few knock on effects elsewhere, but this at least tells me that the problem is what I think it is.

[DivFord]

Ah. Thought that was the same problem.

So, are we looking at something like this? If so, surely vertex B isn't being constrained, since it isn't penetrating the other volume. Why would it get pushed sideways?

[Fyll]

That situation is fine. What goes wrong is when both corners overlap each other (pink arrows are the effect of the green box on the red one, and the yellow arrows are the red box's effect on the green. Unnecessarily complicated diagrams away!):

The trouble point is that they're both trying to push themselves right, and the other one left. Unfortunately, they end up in a comfy equilibrium when crossed over like this.

EDIT: In fact, here's a picture of it happening in-game:

[DivFord]

I thought you disabled rotation. Surely a double-overlap is impossible.

[Fyll]

I've only disabled rotations on Units. Props can still sit at funny angles and fall off of edges if they overbalance.

I suppose removing all rotation would be a potential solution (nearly. There's actually another problem I just remembered wherein, by the same logic, identically width'd objects can fall int one another), but that feels like a waste of the potential we have. I'll bear it in mind as an idea though (it should speed things up a hell of a lot to...).

[Fyll]

Update: Jumping is now all good.

Advantages:

• You can jump whenever it's sensible to jump.
• nextToDir() is called approximately a million times less frequently.

Disadvantages:

• Swimming is back to being a far away mystery (I can see a possible path there, but I'll leave thinking about that until later).
• Gravity is now always applied, so the net effect is to actually slow everything down somehow.

[Fyll]

Actually, how big are you picturing the levels being? I've been picturing them as 2 screens by 2 screens at the absolute largest (so, 20x14 tiles), with levels usually being 1x1 screens, maybe a bit wider.

If the levels are going to be generally quite big, it'll probably be worth turning the updates and collisions off for anything outside of the screen (plus a margin of one or two tiles).

[DivFord]

I've been using 20x10 as the default in the editor, which feels about right for the average level. I can definitely see us wanting to make some larger than that though.

[Fyll]

Hmm. In that case, how do you feel about turning the collisions off for things that are (suitably) off screen?

Also, is the goal to make a quick game, or one you need to make a bit of an investment in? 30 zones per world, at least 4 zones (that I can think of) per playthrough. That's a lot of rooms to get through without any permanent save feature (as in, not Nethack style suspend saves). This is one of the reasons I'd assumed we were having smaller rooms (hence, my confusion and dubiousness about gates and teleporting things. I was expecting to have about a screen's worth of space).

[DivFord]

Hmm… You make good points. My thinking is, it's meant to be a puzzle game, and the more elements we can have within a single room, the more design space we have for making puzzles. Based on that, it would seem wiser to reduce the number of rooms in each zone, but increase the size of those rooms.

EDIT: Oh, and I think disabling offscreen collisions/ai would be fine.

[Fyll]

Update again ('cos updating is fun)!

That fix I put in a while ago to fix the thing that wasn't fixed, that didn't work for some reason, is now fixed (thus fixing the thing it was originally trying to fix). I.e. There are now a lot less unnecessary collisions (the problem was that I forgot to scale the magnitude of the collisions, so they were taking ages to fix any slight overlaps).

As to where this puts everything, the only two things holding me off of pushing are that identically shaped objects can still sink into one another, and that everything still lags a little, even at the lowest number of loops (i.e. 1). The speed issue could just be my laptop being a pathetic old thing (as the -O2 flag seems to sort that out), and the speed only drops by a factor of about 1/3 when there are all 24 crates on screen at the same time, so I'm not too fussed about that.

[DivFord]

"That fix I put in a while ago to fix the thing that wasn't fixed, that didn't work for some reason, is now fixed (thus fixing the thing it was originally trying to fix)" - I think you need to requisition a few more verbs…

I wouldn't worry about the speed problem for now. If you push the laggy version, we can test to see if it is indeed your hardware causing the problem.

As for the identical objects, all I can think of is to treat vertices as really small circles rather than points. Not sure that helps, and probably comes with a performance cost.

[Fyll]

I think the performance cost would be a bit too great for that. I know that adding a node to the middle of each edge works, but that obviously doubles the number of nodes to worry about (and thus, doubles the time it takes to loop). Also, this doesn't solve the problem of the corners overlapping (although it does drastically reduce how noticeable it is).

I think what I'd ideally be able to do would be able to make the nodes realise which edge they want to push back away from, as it currently just use the edge they're nearest to.

[DivFord]

So… vertex normals?

[Fyll]

Huh. That seems really obvious. There must be a catch.... >.>

I'll have a go, and report back soon.

[Fyll]

Hooray! It works!

Not to sound cheeky, but I'll leave pushing it until next weekend (so I have plenty of time to resolve all of the billion clashes that will occur). I'm happy to resolve the collisions, seeing as it's my mess, so I'd recommend pushing and being up to date come next weekend, so there are no clashes when you pull afterwards.

[mspraggs]

For merge conflicts I recommend a merge tool, such as meld, which allows you to compare each version side by side.

[Fyll]

Aye, but someone's still going to have to actually go through and make sure to take the relevant half of the code.

I assume this would just be git commit -am "Blah"; git meld?

[DivFord]

Shouldn't be too bad. I'm pretty sure I haven't touched any code since you started. Have you @mspraggs ?

[Fyll]

Okay. I've just pushed everything. As it turned out, there weren't any collisions! :D

I did spot a slight bug when quickly testing it (if you jump onto the crate in the exit, you get pushed into the wall). I'll sort that out at some point, but it's not game-threatening so I don't mind. EDIT: This has been fixed. The problem was due to norms on concave polygons.

Also, beware that you can run back out through the entrance. I'm still thinking about how to fix that.

Also also, Bullets start a long way away from the Player and bounce oddly for one frame after collision. I'll put that latter down to the mess that is the circle-polygon collision code, and look into it at some point, while the former I'll ignore until Bullets get rewritten.

[mspraggs]

Awesome! Thanks for pushing. Would you be able to add some option to draw the circles and rectangles that we can see in the images you posted?

Did you reduce the walking speed? Because it feels like everything is a lot slower than before. I will profile the game using linux-tools to determine the location of any performance bottlenecks.

And a belated reply: I haven't changed the code in ages. I do have one small change I'll push though.

[Fyll]

Okay, done. There's now a command line option --draw-hitbox or -dh to turn all of those lines back on.

Also, while pulling your push, you seemed to have missed a #include <stdexcept> from Sprite.hpp, as I was getting compiler errors about std::except's existence (also, O.o, That code looks scary. I don't think I've ever seen an XOR-equals before. I don't think I've ever actually used an XOR in C++!).

EDIT: Also, I've fixed the bullet bouncing oddity. As expected, the circle-polygon collision code was doing something blatantly stupid. It's fixed now (and theoretically, a whole deal faster).

EDITx2: I did fiddle with the walking speed, because the way it got applied changed, so the number's probably aren't perfect. I believe the crates and dirt tiles also have (and had) a surprisingly high friction.

[mspraggs]

I'll let you in on a little secret: I googled how to overload the std::hash function, and found some code that's used in the Boost libraries, so it's not something I came up with, I just stole it off stack overflow :-P. I'll have a look at your changes.

Thanks for adding the option!