- Breadth-First Search
- A* Search
- Applying the A* Search
- Enhancing the A* Search
- About This Article
Applying the A* Search
In order to use the A* search algorithm in a game, you'll have to interpret the game environment as a graph, or in other words, decide what the nodes and edges represent.
In a 2D, top-down, tiled-based world, this is easy: the nodes represent the tiles. You can travel from one tile to any of its neighboring tiles (unless one or more of the neighboring tiles is an obstacle).
However, tiled-based worlds aren't the only situation where we can use the A* algorithm. Let's consider a typical floor plan for a 3D world. In this world, what could our nodes be?
First, the nodes could be placed by hand. All you would have to do is make sure the edges between neighbor nodes have a clear path (no obstacles in the way) and there are enough nodes to cover the entire map. However, this can be a bit tedious. Who wants to sit around defining where path finding nodes are on a map? So let's try to come up with an automatic solution for node placement.
3D engines that use BSP trees and/or portal techniques have the advantage that the world is subdivided into convex polyhedral cells, or "rooms," with entryways between adjacent rooms. This means traveling from one entryway of the room to another will never hit any walls, as long as the two entryways aren't collinear. (If two entryways are collinear—that is, they exist on the same line in space—and a wall is between them, a creature could collide with that wall. So extra care might be needed to define room boundaries so that collinear entryways in the same room don't occur.)
Entryways between convex rooms are often called "portals." Portals are generally an invisible polygon that separate two convex areas. See Figure 3 for an example: The dotted lines represent the portals. We can easily use these portals as nodes in a graph.
)
Figure
3 The portals can be the nodes in a graph representing the map.
The only issue is that the start and goal locations will be within a room, not on a portal. However, because rooms are convex, a creature can move in a straight line from any location in a room to one of the room's portals without running into any walls. So, when we are doing an A* search, we can make temporary nodes that represent the start and the goal. These node's neighbors will be all the portals of the room they are in.
Note that using portals as nodes only takes the world into account—obstacles based on game objects aren't considered. So if you have a game object in the way, you'll need some extra code to move around those objects or at least consider them in the search.