247. WoT – how not to be seen

This post is about how not to be seen.

Suppose I have two teams of tanks, with maybe 3-5 tanks in each team, and only one is a human player, all the rest being bots. So I have 5-7 bot tanks running around trying to see and shoot each other.

How do bot tanks see enemy tanks? It’s not easy. But this challenge is the main reason I took on this project, and it hasn’t disappointed me. It’s really interesting.

As I think I’ve already said, you can send out “rays” in all directions and see what they hit, but that takes a lot of processing power. So you need to cheat as much as possible.

If you think about it, we can split the work we need to do into different “layers”, like this.

1. for each tank, find the enemy tanks which are in its field of view (usually 45 degrees in front of it)
2. for each enemy tank, find the trees and buildings that might be blocking the view
3. for each tree or building, figure out which part of the enemy tank it is blocking
4. calculate how much of the enemy tank is visible
5. decide if our tank can see it or not

1. Find enemy tanks in the field of view

This is fast and easy, using the culling method I explained in the last post.

2. Find trees and buildings that might block the view

We could have hundreds of objects in our scene, and if each of 7 tanks has to check all of them a couple of times (once for each enemy tank in its field of view), the work adds up quickly, even if it is fast. It helps if we can ignore objects that are nowhere near the field of view, so we don’t even bother testing them.

Grid / Tilemap

A simple way to do it is to split the scene up into a grid of squares (or “tilemap”, if you prefer), and have a table that tells us which objects are in each square. So when I am looking from tank A to tank B, I only have to worry about objects in the tiles between A and B, and I can ignore all the others in the scene.

Suppose I have a scene that is 2000 x 1800 pixels. I can split it into squares of 40 pixels square, which will give me 50 x 45 squares. I create a 2D table, to hold all the objects in each square. This table is only used to make quick decisions about which objects might be blocking the view from one tank to another.

So when I create my trees at the start, I also need to figure out which square they belong to, and add them to the table, something like this.

--create the grid
treeGrid={} --to hold lists of trees in each square
trees={} --the actual trees
for i=1,200 do --add 200 trees
    --create tree in random position, choose one of the tree images randomly
    local pos=vec3(math.random(1,2000),0,math.random(1,1800))
    local img=math.random(1,5)
    trees[i]={pos=pos,img=img} --store tree data
    AddToGrid(i,pos) --see below
end

What does AddToGrid do? I haven’t included the code, but it figures out which square the tree will be drawn in, and adds it to the list for that square. So if tree number 83 is being drawn at (1321, 0, 1512), I can calculate the table position, using integer division, so

1321//40 = 33
which is the same as, but faster than, math.modf(1321/40)

1512//40 = 37

and set treeGrid[33][37]={83}

If tree 147 is also drawn in that square, then treeGrid[33][37]={83,147}, and so on

So treeGrid has a list of all the trees drawn in each square.

There is just one complication. Trees can be drawn anywhere, so they may overlap two or even four different squares. However, it is easy to test which squares a tree overlaps, because it is a circle (remembering that it rotates to face the camera). You simply take four points on the edge of the circle (north, south, east and west), and calculate which square each point belongs to. Then you include the tree in each square (in treeGrid) that it overlaps.

Which squares need to be checked?

Suppose tank A is looking at tank B. Which tiles need to be checked?

The problem is that if you draw a line between the positions of A and B, it probably will look something like this, cutting through the corners of some squares.

How can you get a list of the squares that the line passes through?

Well, as usual, some very clever people have spent a lot of time developing methods for this, and I borrowed one that seemed to work quickly (it still took me two days to find it, though). It starts at one end of the line, then figures out where the line first reaches the edge of a square, and adds that square to the list. Then it figures out where the line hits the next square, and so on. It is here if you want it.

So I get a list of squares like this

And after all of this work, I can look at tank B from tank A, and quickly get a list of squares I need to check, and look in treeGrid to find out which trees are in those squares. I will end up with a list like this: {23,27,35,57,132,162,13}, which means I have to look at tree #23, tree #27, and so on.

I still have to decide whether I need to do the list twice, because if tank B is side on, it may be quite wide, and just basing my list of squares on its centre position may not be accurate. I may need to do the list twice, once for each side of the tank, and combine the lists. I need to test this.

 How much of the other tank is hidden by a tree?

All of this has been difficult enough, but when we look at whether a tree is hiding the other tank, it gets really tough.

Here we have tank A looking at tank B, around a tree which is partly blocking the view.

• How much of tank B can be seen?
• And what if there is another tree blocking even more of the view?
• And the width of tank B (as seen by A) will depend on its rotation angle.

Like I said, this is tough.

And even if we solve it, we need to make it fast as well.

 

I’m going to avoid complicating things, by assuming that tanks can’t see through, or over or under trees, so the full width of the tree will block the view.

Tangents

First, I need to draw a line from A to the edge of the tree on each side. The area in between is blocked by the tree.

 

The line from a point to the two sides of a circle is a tangent, and where it touches the edge of the circle, it forms a right angle with the centre of the circle, like this.

It takes a bit of work to find tangent points, so I wondered if there was a faster approach,

and there is,

 

 

If I take the direction from our tank to the centre of the circle, and find the points on the sides of the circle at 90 degrees to that direction, as shown alongside, it’s much quicker, and in most cases, is accurate enough for me.

It’s quicker because of a very neat geometry trick. If the direction from my tank to the tree is (x,0,z), the circle centre is at c, and the circle radius is r, then the two points are at

• left hand = c + r * (-z,0,x)
• right hand = c + r * (z,0,-x)

 

And the result looks like this. Note how it’s pretty accurate (the red lines don’t go inside the circle much unless you very close, when it probably doesn’t matter much.

Width of the other tank

I’m going to leave this for now, but for example, I could calculate it by taking the four corner positions of the target tank, and testing which was furthest to the left or right, from the viewpoint of our tank, to get the left and right positions and therefore the width.

Yes, but how does this help?

I’ve thought about all the different ways I could use the information above to figure out how much of the other tank is hidden.

And I think this is what I’m going to do.

I’m going to calculate angles. Yes, angles.

The direction from my tank to the two circle tangents, and to the two sides of the target tank, can be expressed as an angle, which I can calculate using atan (which is very fast).

I’ll calculate the angle for the left and right of the target tank, and split it into (say) 20 parts, and put them into  a table. So if the two angles are 0.5 and 0.7 (in radians), then my table will look like this: {0.5, 0.51, 0.52,… ..0.69, 0.7}.

Then for each tree, I’ll calculate the angles for the two radians, eg 0.45 and 0.55, and test my table of points against this range. Any point that falls into the tree range will get removed from the table, so in this case, the points 0.5 to 0.55 would get removed.

Then I test the next tree the same way, and when I’m done, I count the remaining points in my table and divide by 20, and that is the % of the tank which is visible.

I don’t really like having to do 20 tests per tree, but if I’m clever and make sure my list of trees is in order from closest to furthest, then the trees that are most likely to block the other tank will be looked at first, and my table may shrink very quickly. I also have the option of using my fast culling approach from my last post, to decide if trees even need to be tested at all.

Then what?

Once I have this working, I can use the % visible statistic to decide if a tank can be seen. For example, I might say that it can be seen is visibility exceeds 20%, unless the other tank is moving, in which case it is only 10%. Or if I want to be clever, I could say that if we are looking straight at the other tank, it only needs to be 20%, but if it is at the edge of our vision, it needs to be 40%.

But first I have to make all this work. That’s the boring part, programming and debugging…