# 225. World of Warships – navigation and more collisions

I’ve posted updated code for you to try at the bottom.This is how it looks now.

I’ve included automatic navigation, so unless you actively steer the ship with the joystick, it will sail itself, avoiding islands and turning (I hope) if it gets to the edge. The enemy ship uses the same system.

I’ve also added code to stop shots going right through the islands. That was interesting.

I explain the changes below. (By the way, if you’re wondering why I haven’t been including a lot of code in my posts on this project, it’s because the code has become large, and I don’t want to swamp you in detail).

### Automatic navigation

This is the beginnings of an AI system for the enemy player, so he will give you a decent battle. At the moment, all the AI does is turn to avoid islands, and vary speed in shallow waters. It’s a bit clunky, but it’s a start.

The island detection system is very simple. When I create the scene and all the islands, I also create a 2D table in memory, with one square for every 5 pixels. Then I fill it with the water depth in each square, which is 0 for the islands, and for the edge all round the scene, and increases by 1 for each square you move away from the islands, with a maximum of 15.

Then when I am sailing, I look ahead 5 squares (25 pixels), and also the same distance at 45 degree angles to left and right. If there is no advantage to turning left or right, I keep sailing, my speed guided by the depth of the water. If turning gives me deeper water, I turn. It really is as simple as that. (Of course, there is always some complication, eg the ship can turn left and then find that turning right is better, then left, then right….so I got the program to remember which way it is turning and not change its mind all the time).

To look ahead 25 pixels, I take the current position, and add vec3(25,0,0), rotated by the current ship’s angle plus any additional left or right angle I want to test. The reason I use vec3(25,0,0) is that the ship’s mesh points to the right, in the direction vec3(1,0,0), so 25 pixels straight ahead is just 25 x that vector.

This little function will rotate a vector left or right on the y axis, by a degrees

RotateVector(v,a) local m=matrix(1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1):rotate(a,0,1,0) return m*v end

### Improved collision detection

I never thought I would have to put so much work in on detecting where my shots hit something..

Water splashes

In the last post, I talked about detecting hits on the enemy ship. But I realised I needed to improve my water splashes, because currently, I only draw them when the height of the shot falls below zero – but the shot is moving so fast, it might have entered the water 5 pixels further back.

So I need to interpolate the previous position and current position to find the point where the shot entered the water. Well, that’s really easy, because all I have to do is interpolate the height (y value), eg if the height was 5 previously and it is -10 now, then the shot entered the water 1/3 of the way between the previous and current positions.

Islands

This one is way harder. I need to detect if a shot hits the side of an island, and if it does, explode it there.

Each island is made up of vertex triangles at different angles. How am I possibly going to figure out if my shot goes through one of those triangles into the inside of the island?

Well, we can break it down to reduce the work (bearing in mind that if all the guns are firing, there can be 16 shots in the air at once).

First, is the shot passing over an island? I can test this for each island by seeing whether the position of the shot is within the rectangle formed by the bottom of each island. I actually do it a little faster by calculating the distance to the centre of all the islands, and only doing detailed testing on the closest one. (If I need more speed, I can make it faster by starting with a list of all the islands, and dropping off any that the shot is moving away from, so I’ll test fewer and fewer with each frame).

So suppose I test the closest island, and my shot is over it (ie within its rectangle). Now how do I know which triangle it is going through, and whether it has done so?

My next step is to loop through all the triangles in the mesh for that island, and test whether the shot is

- within the 2D (x,z) triangle of that mesh (ie ignoring height), and
- whether it is below that triangle or above it

If this isn’t clear, imagine you are above the island, looking *directly down on it* as the shot passes over it. At any time, the shot will be over (or under) one of the triangles, based purely on the x and z values (ignoring height y). Once we know which triangle it is over/under, we can test whether the y value is under or over it.

For the first step above, I googled a good barycentric method on the net (of course I don’t know what that means). This tells me if my shot is within any of the triangles (using just the x and z values of all the points).

Once I know the shot is directly above/below a triangle, I can use a little trick to see whether it is below or not. The normal of a triangle (which I explain in this post) points outwards from it. If I take the line between my shot and any one of the three vertices of the triangle (by subtracting my point from the triangle vertex), and calculate the dot product with the normal, then the result will be positive if my shot is above the triangle (ie in the same broad direction as the normal), and negative if it is below (in the opposite direction to the normal).

I’m sorry for the technical talk, but this is what it takes to write 3D code.

Fortunately, the barycentric method also gives me the position where the shot meets the triangle, ie where it hits the side of the island, so I can draw an explosion there. There is just one little remaining problem. Because the explosion will be centred on this point, half of it will be hidden inside the island, so only half of it shows. That looks rather odd. So I had to calculate a point a couple of pixels further back, along the path of the shot and away from the island, so the whole explosion would show.

How do you move the point backwards? Well, we have the previous and current positions of the shot, let’s call them p0 and p1. The direction they are travelling is p1-p0, so to go backwards, we want p0-p1.

This vector includes speed as well as direction, so if we want to go (say) 3 pixels backwards, we need to get rid of the current speed (which we do with the normalize() function)and then multiply it by 3, ie

explosionPos = collisionPos + (p0-p1):normalize() * 3

This is all very clever, but if you look at the video, some of the explosions are still half buried in the island. I think I have a little more work to do…

### Code

If you’ve read this far, you’ve been very patient, thank you. The code is here.

function setup() http.request("http://bit.ly/1hCd8bK", function(d) loadstring(d)() setup() end, function(e) print(e) end ) end

- Use the joystick to steer
- touch the screen to shoot (the program aims for you, at the moment)
- touch the camera views at the bottom to look around
- the enemy health is the upper green strip at bottom right
- your health is the green strip under it
- the state of your 4 guns (from front to back) is shown by the dots – green = ready to fire, yellow = reloading, red = disabled by enemy fire – note your guns can’t fire at certain angles, so turn sideways to the enemy if you want to fire all the guns.