Pixel perfect bouncing

In the game I am making, I need to have objects which bounce off other objects accurately, and I have everything sorted, apart from one thing.

I have the collision detection done, and I can return the object collided with. And I also know the algorithm for finding the angle to bounce at, provided I know the direction the bouncing object is travelling at, and the angle of the surface.

And there is the problem, I don't know how to accurately find the angle of a surface on any particular point on a sprite. If you don't get what I mean yet, here is a diagram accidentally saved in JPG then converted to PNG.

you can not pixel perfect bounce.

you need to use polygons to calculate a surface normal which is needed to calculate the new direction vector, sorry.

Oh right. Then, is there a way of automatically creating these polygons? I'm sure there must be because I've seen bouncing done in other game creating tools without the need to stick in your own polygons.

Can you say which tools as people might know how those tools manage to do it? I know some tools come with a manual shape editor and that there are algos (convex hull? Giftwrap?) which can do it.

You do not necessarily have to use polygons, but that is an increasingly popular method.

What you need to do ultimately is find an angle, ie interpret the edge of the object in such a way to make it look like there is a single flat `face` where the other object strikes.

You could sample/read a small area of say 3x3 pixels at the point of impact and based on the contents of those pixels ie based on alpha values perhaps, create a straight or curved line which marks the edge of the shape, and then find the angle of that line.

tonyg: the tool I mean is Game Maker, the program I used when introduced to programming. It managed collisions and bouncing for you entirely; you quite literally called "move_bounce_solid()" in the event of a collision, and that was it. You didn't have to edit polygons or anything like that. Obviously I'm not looking for someone to provide that level of ease in blitz.

As for Convex hull algorithms, if someone else can implement them that would be cool, personally, I would have _no_ idea where to start.

ImaginaryHuman: That is an awesome idea, I think I'll look into it.

I didn't think GameMaker checked the point of contact and calculated the return angle though. I think it just reversed the direction. I could be wrong as GameMaker got quite powerful.
Anyway, this is good for creating hulls.

Game Maker did get very powerful; it doesn't just reverse the direction, it checks the point of contact as you said.

I have a feeling Game Maker probably uses a Convex Hull algorithm, or something similar to do with polygons. The thing is, everything on that page just flies straight over my head. I did notice that the C implementation seems to take an array of points as an argument... I'm not sure how well that would work out. Also, the thing is with convex hull, is that it seems to reduce the complexity of the shape, so although you end up with a set of points to use, you don't get very accurate collision. (correct me if I'm wrong there)

As for your suggestion ImaginaryHuman, I have an idea of how it would work, but I haven't tried to implement it yet.

It would work like this:


1) _Somehow_ find the point of collision, then _somehow_ extract a small square around it, making sure you differentiate between the pixels of the sprite, and of the background.

2) Find all pixels which are not adjacent to a pixel in the background, and 'disregard' them

3) Of the remaining pixels, find all the ones which do not touch the side of the small square, and 'disregard' them.

4) Figure out the angle from one remaining pixel to the other. In the whole plan, this is the only step I DO know how do do in Blitz.

This looks like the easier plan, and possibly more accurate than using hulls. Even still, I'm relatively new to Blitz, so I'd need some pointers on which direction to take.

Thats exactly what I'm going to do to improve my ball bouncing game game PinkEyes http://www.freegame.cz/en/game.php?id=4829


To code it you just need a circle algorithm and use readpixel from the background's imagebuffer to get those 2 points.

Yes that algorithm would be more accurate than a collusion hull because usually the hull is hugely approximated and not very close-fitting, so you could sometimes get collusions where there aren't collisions depending on how tightly the hull fits and thus how many points the polygon has.

With the above method - and you're understanding my idea pretty well - instead of having to store and figure out parts of a highly details hull polygon, you're basically creating one facet of the polygon in the location needed on the fly.

One drawback is if the edge of your sprite has pits or holes or is highly variegated, and if those features are smaller in detail than the size of your square sample, you might get confusing results as to exactly where the surface line should be. So you really need to sample as small an area as possible. Looks like your demo image is about 12x12 which is probably way too big. Probably 3x3 or 4x4 would be enough to get a good range of angles.

I was also thinking that some kind of averaging/smoothing should be involved. The angle of the line should approximately float through the middle of the contour. In your example you chose end pixels which are approximately in line with the rest of the edge, but that might not always be the case. I was thinking to either calculate the average line or to use the midpoint of a spline using the edge pixels for the two end points and then one or two additional control points near the middle of the contour.

It would be probably faster to read copies of your sprite data in main memory and figure out the collision than to try to read from the backbuffer lots of times.

Yea, 12x12 is too big. I would say 5x5 is probably the best, 3x3 and 4x4 would be a bit too inaccurate for my liking. I'm not so sure about averaging though, it might seem like a good idea, but consider this blown up diagram small part of a sprite with holes in (or just a small sprite)


The black lines in the first square try to justify averaging the pixels, but the thing is, all of them seem to fit, so which one do you use? (and, how do you even find this average?)

Then you have an extension of what I started before. You disregard all the pixels which aren't touching the background or next to the border, then pick the closest two to the colliding object and use them to create the angle. Of course there's room for error, but as long as the sprite is constructed correctly, there's shouldn't be too much to worry about.

I'll start trying to program this soon, but I don't know if I'll be busy so it could be a couple of days before I get to work on it.

EDIT: I just remembered, there's also the question of how exactly you find the point of collision. Can you do it using Max2D's collision functions, or do you have to write your own pixel collision functions which can return the point of collision?

In the past I just made a 2d array which represented pixels in the object and then just calculated where in the array to look and then it would contain a direction I could then manipulate. Cheating, but it worked fine.

That's not a bad idea actually JGOware. Maybe you can have a linked list or some kind of tree which looks kind of like a `perimeter`, with one entry per pixel on the perimeter, and then each of those entries stores the angle of the surface at that pixel. Then it's just a matter of figuring out which pixels in the source and destination objects `hit` each other, or overlap. I guess even with your method, Spacerat, we'd have to consider how to do that efficiently too.

Regarding averaging I think I'd go with a 3-point bezier curve. You've already found the two end points so then you just search along a perpendicular line towards the center until you hit a solid pixel and thats the midpoint. Then you can use the bezier math to figure out the exact angle at any point on the curve.

When I was talking about averaging I was talking about looking at the contour of the edge of the sprite which is being hit and finding the angle for each adjacent set of 2 pixels and then taking the overall average of those sub-angles.

JGOware@ its newer cheating its problemsolving, "if it behaves
and looks good, then use it" .. famous words from Carmac Id software :)

people that play games are often to busy on the task you have given them to solve, so there is room "for creative thinking" we as creators/artist tend to focus to much on details that we only see :)

a good example is Blizzards - World of warcraft, check out their textures, they have created illusions of 3d details on their textures by playing around with lights and shadows while pixlating em :)

//Gnasher

I have my own cunning little hack that works to some extent. Say you are testing sprite 1 against sprite 2. Do say sixteen collision checks, with sprite 1 offset by a different angle each time. Add up the vectors of the offsets that didn't produce a collision and you generally have the angle the two objects collided at or a good approximation thereof

BTW the blitzmax collision detection is not nearly fast enough so you must roll your own collision code. Collision detection between sprites that aren't scaled or rotated can be really fast. Unfortunately because blitzmax handles scaled/rotated sprites it is slow. If you need to handle scaling and rotation too, you can create scaled/rotated collision masks and test them quickly.

Or you could just move on to vectors