Thought experiments for collision detection using vectors

We've been using our almost-pixel-perfect line-of-sight algorithms for a while now, and they work really well. We've made about three or four revisions to the actual games using them, but the underlying method of detecting collisions between a moving and a stationary object remain pretty much the same each time.

The general idea is pretty simple - take a bitmap snapshot of the playing area, from the two points you want to test a line-of-sight between, then walk along the diagonal to see if there are any non-white pixels in the way. Wherever a non-white pixel is encountered, there's an obstacle and a collision is detected.

For shooty games, this is great - we can use the same routines not just for line of sight, but to resolve when a shot is fired at a target. We even know exactly where the place the little "bullet explosion" - should the bullet collide with anything along it's intended path - and then a quick loop around the objects on the screen, comparing their distance from the point of contact allows us to include varying degrees of damage from anyone standing within the "blast radius". This method not only allows us to have simple bullets flying around in our games, but also explosive projectiles, like rockets and grenades, which can have a large impact in the centre of the explosion, with lesser effect radiating outwards from the point of explosion.

Exactly the same technique can be used for sports-sim games, for throwing a ball from on spot to another - if another player character is in the way (i.e. would get struck by the ball) they can attempt an interception.

Something that did come up in conversation - and it's an idea that we really should just put to bed as "for another time" but it just won't go away - is reflected shots and ricochet. What if the bullet/ball were to hit an obstacle, but continue moving? Our current routines simply stop the movement dead - this is fine for bullets and projectiles which might otherwise embed themselves into any obstacle hit, but a bit unrealistic for things like sports games and throwing things around.

The problem with our current collision detection is that is uses a point and not a vector to determine collision. This means that we have no idea in which direction the ricochet should travel:

The first problem with our current approach is that the angle of reflection/ricochet is dependent not just on the angle of approach, but also the angle of the object striking it. If the blue dots in the example above represented points along a wall, for example, the angle/facing of the wall would have an impact on the angle of reflection.

In order to correctly show the angle of ricochet, we need to be able to calculate the angle of approach to the perpendicular plane of the object/shape being struck. We can then make the object bounce off, at the same angle:

All this basically leads to us defining our obstacles layer not as a bitmap that we can walk along, looking for non-white (or non-transparent) pixels, but describing each obstacle as one or more vectors.

We'll need to convert our starting point and destination point (e.g. character moving could be the starting point and the target being shot at - or place where the ball is being thrown in a sports simulator - could be a destination point) into a vector. As a vector, we can write this as an equation for a straight line, y=mx+c.

In this equation, m is the gradient of the line and c is a constant value describing where the line cuts the y-axis when x has the value zero. This is a typical equation for a straight line.

If we were able to describe - in this case, for example, a wall as a vector - i.e. a straight line passing from one point to another - we could also express this as a straight line equation y=mx+c

Using simple trigonometry we should be able to calculate the gradient of each straight line, and thus, the collision point (where the two intersect) if there is one, is the point where the two equations are equal. Solving equations is probably best left for another blog post - the idea is to demonstrate that this is not only a feasible alternative to our previous method of collision detection, but an enhancement to it.

Once we have found our intersection point (if one exists) we can simple report back that intersection point (as we currently do, but using bitmap probing) or we can calculate the angle between our "approach" to the obstacle, and its perpendicular: this gives us the angle that we should bounce any object (ball, bullet, projectile) off it.

That's it for now.
No code written. Nothing actually put down on paper and tested - just a theory. But it could prove to be quite a useful one. For objects on the map (such as playing pieces) we could create a bounding box (four vectors arranged in a square) and use these in any vector-based collision detection (it's not likely that we'd want to "bounce" anything off a playing piece, but for completeness, it would be nice to be able to use the same routines to see if a playing piece is acting as an obstacle, as for walls and immovable objects too).

It's possible that this approach might lead us up a dead-end and we end up wishing we'd never even tried it. That's fine. If that's what happens, we've always got our bitmap based method to fall back on. But there's also a chance that it could add some really exciting physics to our gaming engine. And for that reason, it's got to be worth at least giving it a try........