245. WoT – Self driving tanks that don’t collide

A playable demo is coming soon, but I have to sort out a few things first.

Initially, I’m going to have the enemy tanks drive around in random directions. Obviously, I don’t want all the tanks to drive through each other, or to drive off the edge of the map, so I need to program some behaviour for them.

Like this (a test with many tanks so there are lots of collisions).

(I realise the other tanks don’t avoid my tank, and drive straight through it, but that’s because I still have to program special behaviour for that, like shooting at me!).

Keeping them on the map is pretty easy. I just check if they are getting close to the edge, and if they are, I make a large random turn left or right.

I had to think hard about avoiding collisions, however, and I looked up some articles on “steering behaviour”.In the end, however, I created my own collision test. Normally, I wouldn’t do this, because I am never going to write a better algorithm than the best of the internet, but in this case, I wanted to minimise the work involved, since I am going to have to test every tank against every other tank, 60 times a second.

And I think the result is quite interesting.

First, although the tanks are rectangular, I am going to treat them as circles (as suggested by several sites) because that makes testing much simpler. For any given tank, I’m going to start by calculating the distance to every other tank. If a tank is within a certain minimum distance, then I need to check if they are going to collide soon. But I will only do this check for one tank – the closest one.

This approach means I only need to do a single distance calculation for each pair of tanks, and if I have any tanks close by, I’ll just look at the closest one in detail.

Assuming I do have a nearby tank I need to check for a collision, and there are many alternatives, including

• checking whether the line made by the direction our tank is going in, will pass inside the circle of the other tank
• calculating where our tank’s direction comes closest to the other tank’s position (which means calculating the shortest distance from a point to a line) and whether this is less than the tank’s circle radius
• calculating the direction required to miss the other tank and checking that our direction is outside it

But they all require quite a few calculations, and I want to minimise the work.

I remembered something I had done a while back when figuring out whether a shot fired from a laser would hit a 3D target. I simply calculated the distance to the target, and then multiplied that distance by the direction of my shot and added the result to my current position. This tells me exactly where my shot will be when it gets to the same distance as the target. Then it’s easy to calculate the distance between that “hit point” and the target, to see if it is close enough to hit.

I can do much the same thing here. I already know the distance d to the other tank, and I know the direction I am going in, so I can multiply them (and add my current position) to get the position of my tank when it has travelled a distance of d. If this “hit point” is inside the circle of the other tank, then I need to turn to avoid a collision.

Before we do that, I should answer an obvious question. The other tank is moving too, so shouldn’t I allow for that in my calculations? Possibly, but since we can adjust our position 60 times a second, and the other tank will take avoiding action too, there is no real need.

How much should I turn? Clearly, it should be in a direction away from the other tank, and how much I turn should depend on how big the collision is likely to be. But because I am doing this test many times per second, I have many chances to turn, so I only need to turn a small amount each time, and I chose 0.5 degrees.

I just need to know one more thing – whether to turn left or right, and I found a formula on the net that tells me whether my “hit point” is to the left or right of the other tank’s position, so I can then turn in the same direction (away from the other tank).

All of this means that checking for collisions mainly requires one distance calculation for each pair of tanks, and if a collision is likely, I only need a few extra arithmetic calculations.

And the video at the top, filled with colliding tanks, seems to show it works quite well.

The full collision code is given below.

function Tank:CheckForCollisions() 
    --look for tanks within collision distance (collisionRange)
    --initialise variables to hold details of the closest tank
    --minDist holds shortest distance so far, we aren't interested 
    --unless it is within collision range, so start with that
    local minDist,minP,minT=collisionRange,nil,nil
    for _,t in pairs(Tanks) do
        if t~=self then
            local d=self.pos:dist(t.pos)
             if d<minDist then --this tank is closest so far
                local p=self.pos+d*dir --calc "hit point"
                if p:dist(t.pos)<Tank.radius then --we will hit!
                    minDist=d --store distance to tank
                    minP=p --and the "hit point"
                    minT=t.pos --and the other tank position
                end
            end
        end
    end
    if minT then --we need to turn to avoid a tank
        --this formula is positive if our "hit point" is 
        --on the left of the other tank
        if (minP.x-self.pos.x)*(minT.z-self.pos.z)
           -(minP.z-self.pos.z)*(minT.x-self.pos.x)>0 then
            self:rotate(0.5) else self:rotate(-0.5) end
        return true
    end
end