Pathfinding & Navigation

From AI Wiki

Jump to: navigation, search

Pathfinding is an essential part of autonomous entities. You want them to respect the physical aspects of the environment instead of having them pass through walls and other types of obstacles. The first part of successful navigation is having a reliable map. Maps were addressed in the previous section Creating a city map. These maps can then be used to calculate a path from a starting point to a destination. In the section Moving your Iam we already introduced the NavigatingBehavior class. For many intents and purposes, this class will do all that you need. The sections below are for those that have special needs in terms of navigation or for those who simply would like to understand a bit more about how this all works under the hood.

The industry standard for path-finding is based on a simple algorithm called A* (pronounced A-star). More information about it is available on Wikipedia [1]. The advantage is that it's fairly easy to program and it pretty much guarantees to return the shortest path between two points. At least that is the claim, it's not actually true. It only gives the shortest path if the angles in which you can walk is always a multiple of 45 degrees. Another drawback of the algorithm is that it's not very efficient. The computation time goes up exponentially with the length of the path. For this reason game-developing companies spend and extraordinary amount of time optimizing their path-finding. The IamFramework is no exception. And it's never finished.

First of all, as with so many parts in the IamFramework, nothing forces you to use the classes that are provided. Feel free to develop your own path-finding methods if you feel the need. In your Iam you can always call getMap() to get an instance of the city-map and use it to do your own path-finding and navigation. The provided NavigatingBehavior has a few specifics that are probably worth paying attention to. First of all, it can optionally take into account the presence of other avatars nearby. This is through the following property:

		<property name="avoidsOthers" value="true"/>

This property is set to "true" by default. The effect is that the path-finding will attempt to avoid passing through other avatars. Sometimes this is not possible, for example in case of an avatar blocking the entrance to a building or in case of a large moving crowd where completely avoiding collision is too complex. Just know that it will try. The consequence of this is that the NavigatingBehavior recomputes the path on a regular basis. This is necessary because nearby avatars may have moved in the meantime, blocking your original path. Although the performance of the path-searching in the IamFramework is pretty impressive given the potentially large distances you can travel, this recomputing of the search-path may be something to take into consideration when navigating to distant destinations. If you find your Iam experiences a considerable 'lag' when moving there are two things you can consider to ameliorate this. Firstly, try to think whether you really need to travel so far. Ask yourself if it can't travel to a closer immediate destination first. Secondly, try not to combine other computationally expensive tasks with walking to a distant location.

If you are happy with the NavigatingBehavior in itself, but that you'd just like to have influence on the actual path-finding algorithm itself, then you'd be glad to hear there's a hook for that as well. Behaviors have a property called 'pathFinder' that is set to a class that implements the com.avatar_reality.blue_mars.iam.map.PathFinder interface. Replace this with your own implementation and the NavigatingBehavior will use that to compute the paths. By default this property is set to com.avatar_reality.blue_mars.iam.map.CityPathFinder. It is called because this particular implementation is optimized to perform extremely well in what could be called a 'well-connected' environment. That is an environment where there are usually many possible paths from any starting point to any destination point. It does not nearly do so well in environments that are poorly connected, like mazes or areas that are connected by a small number of narrow bridges. It also doesn't do as well in rough terrain, although so far the performance in that case still looks acceptable.

Even if you would never implement your own PathFinder, it may still be worth being aware of this possibility. Because in the future it is well possible that we'd provide different implementations beside CityPathFinder that would be more suitable to different environments and terrains. In that case it will pay to know you can select the PathFinder implementation that you think best matches the environment your Iam is going to operate in.

Personal tools