My side-project is to make a self-driving car in Unity. I've been working on it for about four years and the last update was 2017. This year I decided to make another update because I've learned one or two things since 2017.
A self-driving car is not one algorithm - it consists of several algorithms combined together. The main algorithm in this self-driving car is a path-finding algorithm called Hybrid A*, which is a modification of the classic A* algorithm. Most games are using A* to make characters find their way around the map. But unlike a character, a car can't turn 360 degrees on the spot, so some modifications have to be made. But no matter how many modifications you make, Hybrid A* will never find the target with the exact position and rotation, so we need some kind of path that ends up exactly where we want to go.
One such path is called a Dubins path, which is the shortest path from point A (with heading A) to point B (with heading B). In total, there are six Dubins paths and you have to measure all of them to find the shortest one. They look like this:
The problem with those paths is that sometimes a car has to reverse into the spot where it want to go, and a Dubins path is just forward (or just reverse if you make some modifications). If you can both drive forward and reverse, the shortest path from point A (with heading A) to point B (with heading B) is called a Reeds-Shepp path.
While then Dubins paths are six in total, the Reeds-Shepp paths are 48. Also, the original Reeds-Shepp report called Optimal paths for a car that goes both forwards and backwards is not the easiest report to read. Luckily, Matt Bradley has managed to implement the report in C# - but in another game engine than Unity. So I decided to translate the code to make it work in Unity. The main challenge I met was that it took some time to realize that Unity is using a different coordinate system than the coordinate system used in the original implementation.
This is the end result (black means that the car should reverse and white means forward):
You can download the Reeds-Shepp paths (and Dubins paths) here.
Comments
Post a Comment