Car AI Pathfinding
Winter 2022 - Present
Note: This project is still in progress and is far from complete. More information detailed below.
The Problem
For a project I'm working on through my job at the HCI lab, I was tasked with creating a car AI to race against the player.
My original quick solution to solve this problem used a localized approach to give the car limited information about its surroundings that it would then use to attempt to travel as far as possible. I implemented this by having the car shoot raycasts in a 180 degree arc around the direction it is traveling (to simulate a driver looking out of a windshield) and having the car try to move along whichever ray traveled the farthest distance. A crudely-drawn Microsoft Whiteboard diagram of this method is shown above. With properly tuned linear and angular acceleration values and speed caps to limit the car's movement from traveling strictly along these straight lines, this method will create great-looking car motion!
Despite the promise of this prior approach, there are a couple of notable issues:
First, there is no guarantee the car will avoid all obstacles. Because of the car's limited knowledge of the environment and lack of foresight, the car will not take care to slow down at any point, so if there is an obstacle the car can only avoid at a slower speed, the car will opt to simply get hit and deal with the consequences.
Second, there is little means to control the car. Through this method, the car is programmed to always head towards the location that will allow it to travel the furthest. There is no way for a user to direct the car to a specific location.
Though it is certainly possible to work around these issues and make use of this method (which I still may do since this method is so lightweight), I started to wonder if there was a better, more complex solution that mitigated these issues.
Frequently in video games, game developers handle pathfinding by creating a discrete graph to represent the environment and then running one of the many graphic pathfinding algorithms (Dijkstra's Algorithm, A*, etc) to create a path of optimal linear connections between nodes that will lead from the starting point to the end. I figured that a similar method could be used here for the car, though some alterations would need to be made to allow the car to travel along smooth, curved paths instead of the linear paths typically used in pathfinding problems.
As a side note, I know that many developers handle curved paths by applying the pathfinding algorithms on linear paths and then curving after the fact, but that method is risky in that it requires the assumption that curving the paths will not cause any intersections with the environment, and that assumption limits the possibilities of locations for environment nodes and of curves that can be used. Ideally, I would like to directly include the curves in the pathfinding process to guarantee the path is optimal for the given curves without any of these limitations.
To summarize, here are my hopes for a car AI that improves on my original design:
The car should have complete knowledge of the environment that it uses to mathematically guarantee crashes will never occur
Users should have the ability to supply individual points for the car to travel to
The car should travel along smooth, curved paths
The curved paths should be included as a part of the pathfinding process and should not be tacked on after the fact!
My Solution (so far)
My solution to this problem is to create a function that generates curved paths between two individual points and chains these paths across many points while maintaining the smoothness of the path. While researching this issue, I learned that this type of mathematics, creating smooth curves between points and chaining them together across multiple points while maintaining smoothness, is encapsulated through the concept of Splines. It turns out that splines are incredibly useful and can help with many different problems in computer science and game development, so I highly recommend looking into them if you're interested (this video by Freya Holmér is fantastic). I will not go too far into the formal math of splines here, but there will be a couple of points where Spline continuity will be useful.
To get started on my solution, I chose a simple function that guaranteed interpolation between two points along a curved path. The function I chose is the following (apologies for no LaTeX!): (r = kt, theta = theta_0 +( k * (theta_f - theta_0) / R) * t) where r is the radius from the previous point, theta is the angle about the x-axis relative to the previous point, k is the radial speed, theta_0 is the theta value at the previous point, theta_f is the theta value when reaching the next point, and R is the euclidian distance between the previous and next point. This function is a simple parametric polar function that ensures globally constant radial speed away from the most recent point at any point in the spline and a locally constant angular velocity between any two points. Once I make more progress on this project, I may change this function to a different, more complex function based on my newfound knowledge of splines and their common implementations.
After coming up with this function, I implemented this spline into a simple, barebones Unity scene. Here is a video demonstrating motion along these curves:
Constant_Radial_Speed_G1_Spline_002.mp4As shown in the video, the car (the cube) does successfully travel from point to point along a smooth curve without any incredibly sharp turns! However, there are still some extremely jarring and noticeable speed changes whenever the car reaches a new point. These speed changes occur because the current implementation of this spline as described above is only G_1 continuous. Sparing some math details, this means that while the direction of the first derivative is continuous at each control point, the magnitude is not, so the speed of the car at each of these points can vary greatly. My goal for this spline is to make the necessary adjustments to improve it to C_1 continuity, meaning the entire first derivative is continuous, including both the magnitude and direction, which would therefore prevent these massive speed changes.
Future Plans
As described in the previous section, I would like to improve the current implementation of the spline so it can have C_1 continuity, which would allow the car to travel along a much smoother path.
Once that is complete, I can begin the process of adding pathfinding. In order for pathfinding to work, it is necessary to add a means of detecting whether or not one of these curves (between 2 points) is colliding with any objects. The simplest way of accomplishing this is by segmenting the curve and using calculus to find the maximum and minimum x and y values of each segment to form a rectangular hitbox around each segment. This will necessarily include some additional padding space on either side of the curve, but the simplicity of this solution is great enough to render this minuscule padding inconsequential.
After adding collision detection, it will then be possible to create discrete graphs with edges representing these curves which will subsequently allow the A* pathfinding algorithm to run on these curves, thus solving the problem!