INTRODUCTION

I was interested in how NPC (non player character) cars work in the video game series called “Grand Theft Auto”. I found a thread on Twitter written by an ex-Technical Director at Rockstar North. He revealed that they use a “pure pursuit type” algorithm for the cars.

ALGORITHM

I do not claim to be an expert in autonomous vehicles. I would consider myself a game development enthusiast who is interested in the methods used by the industry.

Besides video games, there is probably no real world application for this approach. It would never be used for an autonomous navigation system that is responsible for real people’s lives.

Based on my research, pure pursuit is the most basic autonomous navigation algorithm that exists. I am sure more advanced implementations of it can be found.

We start with the car’s position (point A) on the road. The car’s forward vector is used to calculate a line and a look ahead position (point B) that lies on this line. A second line is calculated that lies perpendicular to the first at (point B). The point where the second line intersects with the curve representing the road is our (point C).

basic idea of pure pursuit

As the car moves forward along the road, these 3 points form a triangle. The car’s required steering is calculated by taking the normalized angle between vectors AB and AC.

It works well in the context of the demo. However, there are many issues that would need to be addressed before integration into a more complex simulation.

One issue to solve would be an adjustable look ahead (point B) in order to handle all kinds of turns. For example, for sharper turns, the look ahead (point B) should be much closer to the vehicle (point A).

For wider turns, the look ahead would be further away from the vehicle. To accomplish this, the vehicle would need the ability to detect the curvature of segments on the road ahead.

To maintain high performance in a 3D gaming environment aiming for 60 FPS (frames per second), having an advanced object detection system for every NPC vehicle might not be feasible.

There are lower cost ways to accomplish the task using pure pursuit. Although not implemented in the demo, one approach could be to use a second look ahead (point D) to check the upcoming curvature of the road ahead and then adjust (point B) on the fly as needed.

RUNNING THE DEMO

The demo runs locally on your machine using the web browser. If you already have NODE JS installed on your machine, then you are finished with installations. All you need to do is download the source code from the GitHub repository that is attached to this publication.

If you do not have NODE JS, it is quick and painless to install. You can find it here:

https://nodejs.org/en

After you have installed node and downloaded the source code, extract the folder from the zip and then navigate to the root of the directory using your preferred command line tool.

From the root directory, run the command:

node server

Open up your browser and go to the link:

http://localhost:8080/