Friday, 26 September 2014

More thoughts on using vectors for collision detection

Yet more ramblings, with very little code produced - just ideas that may or may not work in a generic game/physics engine. We've already considered the benefits of using vectors for collision detection. Now it's time to consider how they would actually be useful.

Firstly, using vectors is not without its drawbacks. Collision maps - at the minute simple bitmaps - become much more complex, with each "barrier" in the collision map becoming a straight line vector (we're not even contemplating using arcs and curves just yet - even though it should, theoretically, be possible, we're just sticking to the "simpler" approach for now).

So a building in the middle of a map, at present is represented by a rectangle drawn onto a bitmap. In our new vector-based method, the same obstacle would be represented by four connected points (or four lines, joined at the ends, whichever way you want to think about it!). Instead of testing for collision by "walking along" a path, we now compare our movement/line-of-sight vector (a line drawn from the starting object, to a destination point somewhere on the map can be described by a straight-line vector) with every "vector" that makes up every obstacle on the map.

Wherever two vectors collide, we know we have a collision point.
Bearing in mind that it's quite possible that we may end up with more than one potential collision point (where obstacles are placed one behind another) we'll deal with that later, and work with simple examples for now

Let's say our green line represents a straight-line wall, running from point x1,y1 to point x2,y2.
Our playing piece is at x3,y3, and is looking/firing/throwing an object at point x4,y4.

Using simple trigonometry, we're able to work out the point at which the two lines intersect (using variations on the y=mx+c straight line equation). So far, that re-creates what we already have, using bitmaps. Already we have simple line of sight sorted, but using vectors instead of bitmaps (a binary operation which says is there a line of sight from this point to this point).

What we're particularly interested in is re-using this approach for projectiles, and to work out the angle at which this thrown/fired object, from x3,y3 to x4,y4 rebounds off the wall obstacle, running from x1,y1 to x2,y2. To begin with, we need to calculate the "angle of approach" between the starting point, and the tangent or perpendicular plane of the obstacle.

Since we're using cartesian co-ordinates, we can convert our sets of points into triangles. And using nothing more than tanA = opposite / adjacent, we can work out the angles A and B in the diagram above. But how does that help us calculate the angle of reflection off the green wall?

Since we know that the angles of a triangle all add up to 180 degrees, and we know the angles a and b, it's relatively trivial to work out the missing angle (which we've called C). And since we're after the angle between the "approach" and the perpendicular, we can simply subtract 90 degrees (or pi/2 radians if you're that way inclined).

Incidentally, if ever our angles are such that C is less than 90 degrees, we're effectively approaching the point of collision from right-to-left, instead of left-to-right, so can easily work out the angle on the "flip side" by subtracting from 180 instead.

Now we're getting somewhere. And it's getting exciting. No, it really is. Maths is fun.
Let's say we have our proposed destination point (where the ball would land, bullet would hit etc) if the obstacle was not in the way. To move the object from the start point to the destination point would require some effort or force to get it to move. We don't need to get bogged down with physics equations (though that too would be nothing but fun) we can simply use relative distances  to simplify things:

To get the object to travel from the starting point to the destination point, uses up all it's force or energy or work or effort or whatever you want to call it. So if the object is deflected, say, one third along it's path, it still has two-thirds of it's force/energy (which would otherwise propel it the other two-thirds of the way, when it would come to rest with all it's energy used up).

So we could, at the point of impact, work out the distance remaining to the original destination point, apply the angle of reflection, and work out where the final, actual destination point is going to be.

Now, obviously, at each point that the object is deflected, we need to start our checks for collision again, this time using point C as the starting point, with the final actual destination point as the new proposed destination point. And so on and so on, until the object has travelled the full distance.

What's really exciting about this approach (and it is exciting, and fun, dammit) is that it would allow us to set up complex chain-reaction type obstacles, allowing an object to be thrown/fired and have it ricochet off four or five different obstacles - resulting in an almost random (yet, completely predictable) flight path.

The excitement doesn't stop there.
Hold onto your hats, because this doesn't stop getting better:
Each obstacle could have a "hardness" or "bounciness" rating - reducing the amount of distance remaining on the flight path (or increasing it, if it's a bouncy material) whenever it is struck. So instead of collision detection being something that immediately halts the flight path of a ball/bullet/projectile, it is now something that merely affects it. And we can now have different obstacles with different surface types. Without a single line of code written, this already feels awesome!

We could have soft wall types, which absorb all the energy in whatever has hit them (like throwing a football into a wall of porridge - although a more useful example in a boardgame context might be a laser that hits, and is dissipated by, something like a force field).

We could have bouncy wall types - which actually increase the amount of energy remaining in whatever object has hit them - like throwing a rock at a trampoline.

We could even have "knobbly" wall types, which absorb (reduce the length of the remaining flight path by) say, 20%, but also add a random element to the angle of reflection (having calculated the correct angle the ricochet would ordinarily take, we could add some random value to this, to create the effect of hitting an uneven surface).

In a wild west scenario, we could have both wooden walls (non-reflective, bullets get embedded in them) and stone walls (bullets ricochet off them with a loud ping). For our space game, we could have similar wall types - force fields which absorb lasers fired at them, shiny, reflective mirrored surfaces which make them bounce all over the place.

There's no doubt about it; vectors look fun.
We're going to have a go at coding some up, over the weekend. So, unless they become tricky and just too much hassle to implement in two days, we're very likely to have some of the best collision detection routines in our boardgame apps.

Well, maybe. Surely, it's got to be better than "roll for scatter, roll for distance" as most dice-based games currently use?