Navigation and collision demo

This is a demo that shows navigation using simple controls as well as detection of obstacles. Inspiration was the game "Iron Lung" I saw a video from recently, but the control scheme is also present in some old games, notably DOOM.

About the game

Screenshot of the controls in Iron Lung Iron Lung is played in a 3D world in the Unity engine, but the controls you're given only permit 2D navigation because your height is locked to the bottom of the map. Additionally, you're navigating without visuals, only using a crude radar system and a map. The radar is combined with the heading display. Close obstacles are shown by a flashing light that's approximately located where the hazard is relative to your heading. The rate of the flashing shows how close the obstacle is.
The other display component shows your X and Y coordinates, that you can use using a map to navigate. The map has points you have to navigate to.

About this page

This page was a pure exercise for me. I never coded collision detection, and I wanted to know whether I could do this or not. Don't come crying to me if you use this in production and suffer from performance issues. Complexity wise, this is basic geometry, which terrifies me. There's almost nothing in vanilla JS that helps you with anything else than basic angle calculations. A game engine does everything for you in regards to collisions, so don't do this by yourself, just use an engine.
The controls in this demo are identical to those in the game (rotation and acceleration), but for simplicity, you can also just click on the heading display or map display to set your heading and position. Dragging the mouse is also allowed.
Note that none of the gameplay mechanic was copied. This is a pure tech demo. Also, the collision detection is merely for show. You're not prevented from moving through the lines. The demo will clamp your position to within the bounds of the visible area though.
Features:

Direction

This shows the direction you're looking at. Accelerating forwards moves you into the direction that the needle points to. A grey dot on the circle is a close object (50 units or less). The darker the closer it is.
You can rotate yourself with left and right arrow keys.

Heading: °
Compass direction:
Rotation speed: ° per frame

Location

This shows your location as well as obstacles on the map. You can move forwards as well as backwards. Accelerate with up and down arrow keys. The values are simple units. For this demo, they translate 1:1 into pixels. A unit in a game is often around 1 meter.

X,Y: ,
Movement speed: per frame
Speed change: per frame
Collision:
Closest obstacle: units
Obstacle X,Y: ,
Angle to obstacle:

Collision detection

The collision detection is likely the most interesting part of this demo. All you need is basic trigonometry knowledge, most importantly about right angle triangles, and how to calculate the height of a triangle. Collision means that an obstacle overlaps with the player sprite. For simplicity, the player is just a circle.

Collision with a point

This is the simplest form of collision. You collide with a point if the distance to that point is less than the player radius. To get the distance between any two points in a coordinate system, you build a right angle triangle with them as shown on the right. If you are at (1,1) and the point is at (4,5), you can calculate the X and Y difference of (3,4). These two numbers are the lengths of the red sides. You can now get the distance (green side) with pythagorean theorem a2 + b2 = c2. In this case: 32 + 42 = c2 → 9 + 16 = c2 → 25 = c2 → 5 = c

To draw the red lines using the given two points of the green line, simply build a third point that takes the X coordinate of one of the points, and the Y coordinate of the other point. You now have the 3 points needed to draw a rectangle. In this example, the X coordinate was taken from the upper right point, and the Y coordinate from the lower left point. It doesn't matters from which point you take which coordinate. The triangle will just be on the other side of the green line but the side lengths and their perpendicular arrangement stay the same. In the preview to the right it would mean the point is in the top left instead of the bottom right.
Note: It doesn't matters if the difference between two coordinates is negative, simply use the absolute value for your calculations.
Also remember that you don't actually need to draw the triangle, this is just for visualization. Getting the absolute difference between two points automatically yields you the a and b sides of the virtual triangle.

Collision with a line

Collision with a line is a bit more complicated than with just two points, but not a lot more. All you need are two points that are on the line, and your own location. Finding two points on the line is usually not necessary because your line is likely already defined this way, and you can just take those two points. The other definition by the way is as a vector: a single point, and angle, and optional length, but we don't use that here.

Collision detection is done by building a virtual triangle using the two points of the line and the player position. This will almost always be an irregular triangle with 3 different side lengths. Using the distance calculation from the point collision chapter you can accurately determine the length of all 3 sides.
Given all 3 sides you can calculate the height between a side and the point that's opposite to it.

Note: irregular triangles have three different heights, depending on which side you use as the base. The height is the line that originates from the point that's opposite of your base side, and touches the base at a 90° angle. For our distance calculation, the base side is the line that's the obstacle, and the point is the player location.

The formula for the height of a triangle is h = 2 × A ÷ b where A is the area of the triangle and b is the side you use as base for the height. This means we need the area of the triangle to continue. The area of any triangle can be calculated using Heron's formula if you know the length of all 3 sides. The formula is A = ¼ × √‾(s × (s - a) × (s - b) × (s - c)). s is the semi-perimeter of the triangle, which is s = (a + b + c) ÷ 2. This formula is nice because it avoids having to include angles.
If you prefer to use a single formula without calculating s first: A = ¼ × √‾((a + b + c) × (-a + b + c) × (a - b + c) × (a + b - c))

Note that the formula can cause troubles with floating point numbers if the triangle has at least one very small angle. The linked wikipedia article has a solution for this. See chapter "Numerical stability"

The above algorithm works well for real mathematical lines that span infinitely across the grid, but the lines in this demo start and end at the given points (They're called "closed line segments")
This means we have to combine the line and point distance methods, and pick correctly which one to use.

The situation on the right shows the problem. The blue line is the obstacle, the red lines form the virtual triangle. The yellow dot is the player, and the green line is the height, which represents the computed distance between player and line. As you see, the height in this example lands outside of the line. This is not a mistake in the formula. It's correct and still represents the height of the triangle. If the height lands outside of the line, the shortest distance to the obstacle is no longer the height, but simply the distance to the closest point.
In case the height is inside of the blue line limit, it will split the blue line into two parts, and because the height is perpendicular to the blue line, it splits the triangle into two right angle triangles. We know two sides of each of these two triangles: one side is the height we just calculated, and the other side is the distance between player and one of the line points. We can calculate the third side (the part of the blue line that is now part of our chosen right angle triangle), and can calculate how much this is of the full line by simply dividing the value by the length of the blue line. You can do this twice, once for each of the two right angle triangles. If the height is inside of the blue line, both results will be in the range 0 < x < 1, but if the line is outside of the blue line, the value between player and the point that's further away will not make sense, because the length we calculate is more than the blue line, or negative. If that happens, we return the shorter of the two red distances.

Collision angle

If we want to draw a collision line (the blue line in the actual demo) we need to know the start and end point of the line. The start point is always the player location. The end point is easy if the function that is described in the previous chapter decides the closest distance is to one of the two line points, because we know those values.
If the shortest distance is to the line it gets a bit trickier. I've made my life easy in the help section by aligning the base line horizontally and placing the player above the line, so I knew the height is vertical and extends downwards.
But if your lines are slanted like shown in the demo, you need actual direction calculation. For this, you need to know the point where the height intersects the line. In the previous chapter I explained how you can calculate the percentage of where the height intersects as a factor between 0 and 1. You can use this factor to offset one of the two line points accordingly. The easiest way to do this is to virtually move the line so one point is at (0,0), then simply multiply the X and Y of the other point with your factor.
Note: depending on which point you offset, you may need to offset it by 1 - factor instead.

JS provides a function to get the angle between two points in the form of Math.atan2(y,x). This returns the angle that points to the given X and Y coordinates if you are at (0,0). All you have to do is offsetting the target coordinates by the player position, this makes the player (0,0) and correctly returns the direction. Note that the returned value from this function needs to be processed before you can convert it into a 360° reading. An object to the right is at 0°, top is 90°, left is 180°, but for anything that's below you (negative Y) the numbers become negative. They start at -180° at the left, go to -90° at the bottom and back to 0° at the right. Note that the Y coordinate comes first in the function. The function returns the value in radians, that is a range of -Math.PI ≤ x ≤ Math.PI. Once you have the direction, you can convert it into a compass reading.

Collision with shapes

Collision with shapes at this point is easy. Simply build your shape out of multiple lines. The triangle and square in the demo are made this way. One thing this demo isn't doing is preventing the player from moving into the object he collided with. Preventing movement is not actually that hard once you have the angle from the previous chapter. If collision is detected, simply move the player opposite to the collision angle (not opposite to the angle the player faces) until the distance is at least the collision distance (5 in this demo by the way). This approach would allow a player to collide with a line, and if the collision is not perfectly perpendicular, to slide along the line like they can slide alongside walls in actual games.

When implementing collision with shapes, it's possible that the player can enter the shape if he moves more than his width between two collision checks. In this demo it's not possible, because the maximum speed is limited to 5 units, which is only half the player size. What happens is different between games. Some allow it because you're not supposed to be able to do this in the first place, so the required checks are missing. Some other games detect when you're out of bounds, and then move you back into the bounds.

Multiple obstacles

This demo will only show the distance to the closest obstacle. This is a limitation I have chosen myself to not draw yet more lines on the demo canvas. There's a function that calculates the distance to every obstacle and returning the closest. If you couple this with the drawing function and make it draw every obstacle, you get your multiple lines. After a few lines your canvas will get cluttered, so you may only want to draw obstacle distances that are below a certain threshold. As an example, this demo also draws the obstacle on the compass, but only if it's 50 units or less from the player. It starts as a white circle, that gets darker as you get closer.