Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
64 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:


 Intro & Movement
 Avoidance &

 Pursuit &

 Printable version


Obstacle Avoidance

Avoidance algorithms require the understanding of how your maps are going to work and how you want your units to interact with them while moving around. In our case we are going to assume an outdoor environment with relatively small and simple obstacles such as small buildings and objects. We will also assume that you cannot go inside an obstacle and that obstacles are convex polygons with 4 vertices.

In an environment such as this we are mostly dealing with open movement and obstacles that have to be avoided can be with only 1-2 avoidance movements.

In the example to the left we have a very thin 4 point poly that is between the unit and the destination. In this case we move away from the closest vertex to the destination and move several units away in the perpendicular angle from the unit's collision. This gives us the buffer space we need to move around the obstacle.

Obstacle avoidance has to be determined by the type of the obstacles you are going to be providing. In this simple example we are going to use convex 4 point polygons, which will usually be in a diamond or square shape. Because of these obstacle limitations we can simply find the edge closest to the destination which the unit trying to get to and move out from the obstacle a little thereby creating a simple way to avoid obstacles which works fairly well as long as obstacles dont get too close together.

When you want to get into some more advanced path finding algorithms, you should look into A*, which is a popular algorithm for finding the shortest path through very maze-like areas. Beyond A* there are various steering algorithms for gradually moving around obstacles and other more hard-coded situations such as creating funneling intersections that can be used to get to different areas of the map.

Targeting Enemies

Targeting for other units will greatly depend on what you want your player to be doing in your game. You may want your player's units to automatically fire on enemies they see, so that player can devote themselves to the big picture. You may want your units to only attack if specifically told to keep your player's attention on the units and their surroundings.

Either way, you will want your enemies to be on the look out for the player's units to provide the challenge of on-the-ball enemies.

In a situation where you have split up your directions 8 ways, you can assume that for a unit to be facing another unit, within vision range, they must be either directly in front of the unit or in one of the adjacent directions. A simple test to determine if the unit is within maximum sight distance and is in one of these three directions from the unit can give you good result with a minimal amount of time to test cases.

Of course you will want to add in a test for obstacles to see if the units are blocked, most likely you can use the same test for obstacle avoidance for this, as you usually either have a clear path or not . Adding in height to visibility testing will of course totally change the nature of these tests, but that is for another article.

Next : Pursuit & Conclusion