I have an arbitrary destructible bitmap terrain like the one in "Worms". It's easy to work out if a character or missile intersects the terrain, but how do I work out the angle of the slope at the contact point, so I can make grenades roll down hills, bounce off at the right angle, etc. I know it can be down by somehow taking a sample of points around the impact point and seeing which ones intersect, but I'm not sure exactly how to go about it, and in an efficient way.


5 Answers 5


If you're happy sampling then run a coarse sample at a defined radius around your hit point. 16 samples in a circle will provide you with quite accurate curvature. If you add up all the vectors that "missed", you'll have a vector that can be normalised to a surface normal.

If you hit the flat floor, all the vectors will miss if they're pointing up at all, so they add up to an up vector. If you hit a 45 degree slope, the vectors that point away from the slope will miss and add up to a 45 degree vector away from the slope. Even a rough surface will provide a reasonable surface normal as you're checking for "misses" not a surface.

This works fine until you get into really tight spaces, at which point, curvature is all shot to crap anyway, and you would probably not get a sensible result in any technique other than precomputed surface normals (which can be found by blurring a "vector to closest feature" map where feature is non colliding / non matter).


Vec collisionPoint # point of collision
Vec acc(0,0)
for f = 0 to 2pi:
 vec check = vec( sin( f ), cos( f ) )
 if ( check + collisionPoint ).collides():
  acc += check
normal = acc.normalise() # yes, there is a chance of a divide by zero.
  • 1
    \$\begingroup\$ If you're worried about speed, you can precalculate the positions relative to the impact point for the (e.g. 16) samples, avoiding sin/cos and float->integer conversion. This technique can be combined with the collision detection: if you do collision detection on points in a circle around the edge of the grenade, then the vector from the point which collides with the terrain first to the centre of the grenade is a normal to the surface. \$\endgroup\$ Commented Aug 17, 2010 at 11:08
  • 1
    \$\begingroup\$ I felt the "sin/cos" stuff needed to go in there to describe the values. I don't recommend using sin/cos ever. There is never* a good reason to use trigonometry. *if you happen to find one, then kudos and let me know. ;) \$\endgroup\$ Commented Aug 17, 2010 at 11:26
  • \$\begingroup\$ so should I store offsets for each pixel to check? e.g. [x:0, y:-10], [x:2, y:-7], etc? \$\endgroup\$
    – Iain
    Commented Aug 17, 2010 at 11:44
  • \$\begingroup\$ You could, and i probably would, but your performance is going to be bound on the collision check per iteration, not on your implementation of the vector array. \$\endgroup\$ Commented Aug 17, 2010 at 12:35
  • \$\begingroup\$ I would recommend you read up on texture swizzling, to increase cache coherency if it's just an image lookup as your collision check. \$\endgroup\$ Commented Aug 17, 2010 at 12:36

You need two points to calculate it. The slope is then the coefficient of the line passing for the two points, i.e.:

m = ( y2 - y1 ) / ( x2 - x1 )

To get it in form of an angle use the arctan(m) function.

  • \$\begingroup\$ yep - how do I find the second point in an efficient manner? \$\endgroup\$
    – Iain
    Commented Aug 17, 2010 at 10:13
  • \$\begingroup\$ You should find two points which are near enough to give a good approximation. This can be done by sampling points around your collision point. \$\endgroup\$
    – tunnuz
    Commented Aug 17, 2010 at 10:19
  • \$\begingroup\$ The distance around your point at which you sample will be important: if you sample just at the 8 pixels immediately surrounding the current one, you will only get angles in multiples of 45 degrees. A sensible radius at which to sample is something close to the radius of the object you wish to bounce. \$\endgroup\$ Commented Aug 17, 2010 at 10:40

If you want to go crazy, you could take a grid of samples around your test-point, do an edge-detection algorithm to identify the surface (i.e. any point part of the terrain with a neighbour which isn't, or vice-versa, is a surface point), and then find the best-fit line through those points to use as an approximation to the surface.

Might be overkill though :)


The original Worms probably didn't do anything more complex than bitmap/bitmap intersections - i.e. does the bitmap of the grenade intersect with the collision map of the world. Moving the grenade (or whatever) would follow these steps:

  1. Can the object move down one pixel without a collision? If so, move object down one pixel and end test.
  2. Can the object move left and down without a collision? If so, move object down and left one pixel and end test.
  3. Can the object move right and down without a collision? If so, move object down and right one pixel and end test.
  4. If object moved left and down (2) last time, can object move left one pixel? If so, move object left one pixel and end test.
  5. If object moved right and down (3) last time, can object move left one pixel? If so, move object right one pixel and end test.

You probably only want to do (4) and (5) for a few frame to simulate friction, e.g. repeat (4) for each preceding (2).

  • \$\begingroup\$ A down vote? Don't forget that the original Worms ran on the Amiga which had a Motorola 68000 CPU - an integer only unit with no FPU whatsoever. \$\endgroup\$
    – Skizz
    Commented Aug 23, 2010 at 23:28

Late reply but I was looking for something similar and found an algorithm that works pretty well :

Take a bunch of samples around your test point (in my case I get all points that are below a given radius). Calculate the average position of all points that are inside collider (black) in this case and the average position of all points that are outside collider (white).

enter image description here

At the end, you got two points. From there you can calculate a vector, normalize it and your get your surface normal.

Some pseudo-code:

vec collisionpoint, pa(0, 0), pb(0, 0)
counta = 0, countb = 0

for y = 0 to r:
for x = 0 to r:
    vec offset(x, y)
    if offset.sqrMagnitude < (r * r):
        if (collisionpoint + offset).collides():
            pa += offset
            pb += offset

if counta > 0: pa /= counta
if countb > 0: pb /= countb
normal = (pb - pa).normalized

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .