Whether you are building an action based shooter, a complex real time strategy game, or trying to present a rich RPG world with computer controlled characters, many games require sophisticated AI logic to provide an immersive, realistic and challenging gameplay experience. There are entire books on a variety of topics in artificial intelligence in games programming from path finding to swarm behaviors, but in this article I am going to focus on an extremely simple technique which I call vector field collision avoidance. This technique provides realistic, seemingly “intelligent” behaviors in a wide class of games with very simple and highly reusable code.

Note that this article links to some interactive demos on the Modit platform which does not support IE9, however all techniques that are used in this article are compatible with all modern browsers.

Lets start by considering a very simple problem: you have units in a game that are computer controlled and you want them to realistically avoid obstacles and/or each other. If you need the units to travel to specific destinations while taking shortest paths and avoiding obstacles, you would want to use a full-fledged path finding algorithm for this (or you can layer vector field collision avoidance on top of a path finding algorithm), but if instead you just need the units to stay out of the way of the obstacles you can save heavily on computation and often get more realistic looking behavior by using vector field based collision avoidance.

What is a Vector Field?

The above image belongs to AllenMcC. under the GNU Free Documentation License

In mathematics, a vector field is simply an assignment that specifies a vector for each point in a given region. Vector fields can be easily defined in 2-d or 3-d space (or any dimensional space), and mathematically you can define them by a single function that, when given a point x in space, returns a vector v for that point.

Using Vector Fields in Navigation

Using vector fields to have units navigate in a game can be done extremely simply. You can just write a function f that defines a vector field, and then in your main game loop you can tell each unit in your game to move in the direction of the vector that your vector field function returns for the units current position. In psuedo code:

Let’s take a closer look at this pseudo code. We iterate over each unit u in order to move it, first retrieving the vector field at the current location of this specific unit (we will call this our velocity vector). Then, because “moving” in the direction can be modeled by simply adding the velocity vector to the position vector, we add the components (xs and ys) of the velocity vector to the corresponding components of the position vector.

That’s all there is to it! Below is an example of this code to make units move;

• Simple Example of Static Vector Field from Modit.

Upon opening the example code we see that the ships are moving according to a static (unchanging) vector field. To change the static vector field yourself, just refer to the instructions shown at startup.

Using Vector Fields for Collision Avoidance

To adapt the above approach so that we can actually have units in our game avoid collisions with moving objects is actually quite simple. The key idea is that our vector field function f needs to update every tick such that the vector field it defines will cause our units to move in a way that avoids anything that they are not supposed to collide with.

In practice this can be done very simply by thinking of assigning negative gravity (anti-gravity) to any object that we want to avoid and then computing our vector field by summing all of those gravitational forces.

In introductory physics, gravity can be thought of as a force that a given object with mass applies on all objects around it, where the force decreases with the square of the distance between the two objects and is proportional to their mass. In code we can write this as follows.

One of the convenient properties of vector fields is that they sum, so if we have multiple obstacles applying forces on our units we can create the vector field function that represents the combination of all of those forces. So our vector field function can be as simple as.

We can then simply use the algorithm we started with:

And as long as we update the positions of our obstacles as part of our game loop, our units will now be reacting to a dynamically changing vector field and avoiding the given obstacles as they move. You can of course add other components to your vector field function f (eg. if you want units to generally move left to right while avoiding collisions, you can add a constant force in the positive x direction). You can also include your units themselves in the list of obstacles if you want your units to move around without bumping into each other.

• Collision avoidance example from Modit.

• To see the full youtube demo, click here.

Vector field based algorithms for path finding

If your game actually requires sophisticated path finding behaviors for the time being, you will generally want to use a path finding algorithm like the A* algorithm, because the vector field based algorithm described here acts on each tick without planning ahead and thus is not suitable for actually searching a space of possible paths and finding the shortest (or least resistance) results.

That said, there are techniques for finding minimum energy paths (MEPs) across vector fields and there have been some interesting research developments that involve combining global path finding algorithms with local collision avoidance algorithms by using dynamically changing vector fields as described above. The AAA title, Supreme Commander 2, claims to use a new type of flow-field based (flows are paths through vector fields) proprietary path finding alogrithm which was built based on research from the University of Washington which you can find here. There is a nice demo video of the path finding in Supreme Commander on youtube where they highlight some of the break throughs when compared to conventional pathfinding here.

I hope you enjoyed this tutorial; vector field and flow field based approaches to AI movement is an exciting area that has a lot of potential and allows for all sorts of interesting possibilities in games that need realistic autonomous behavior. I’d love to hear from you if you end up using any of these techniques in your games.

Follow me on twitter
Subscribe to the modit reddit

All code excerpts in this article are under the MIT License.

PS. I’d like to give a big shout out to Jesse Chen and Hirohisa Yamada who were invaluable in helping me put all this together.