“Graph search techniques are ubiquitous in game programming”. The genre of the game does not matter, the basis of a game is inevitably formed by methods of graph search. The most popular genre of the moment FPS are normally very dependant on pathfinding methods that allow the NPC’s to move about in the game universe to perform various actions. This is also used in 2d/2.5d games which involve crossing a terrain or navigating a maze.
Typical problems encountered within the pathfinding universe normally relate to trees. (The start of the tree is considered to be the root). The root is then expanded on producing a number of new nodes (child nodes). The normal process followed in 2d pathfinding is most apparent when each child node represents a movement direction. As the path to the goal is extended, each of the child node are further expanded.
When problems are formulated in this sense, a graph traversal problem with starting and goal states inside the graph, we open the door to a number of algorithms.
Of all the available pathfinding algorithms, A* has emerged the most popular within game AI.
A* started with the breadth first search. In this search, all child nodes from the root node are expanded and explored before then algorithm progresses to the next level in the tree. If the goal node is not on the current tree level, the next level is accessed and all the children are expanded and evaluated. “Open” and “Closed” lists were then added to this algorithm as a modification by Dijkstra. This modification provided two fundamental capabilities:
- The cost of a path to the current node is kept by the current node. The “Open” list can then be sorted by this cost which allows for a “best first” search strategy. This comes in particularly handy when the cost between two nodes is not always the same i.e. traversing swampland compared to dry land. This allows the best path to be biased away from costly paths.
- All of the explored and evaluated nodes are stored in a sort of catalogue which stops the algorithm re-expanding nodes which it has already dealt with. This drastically improved the Breadth First search but more improvements were made through the introduction heuristics which allowed the incorporation of an “Informed Search” strategy.
The cost of any individual node up to this stage is viewed as the cost from the target/goal node to the current node and is normally referred to as g(). We can significantly improve an uninformed search of this sort if we include an estimate of the remaining cost between the current node and the goal node. This is the heuristic calculation – h() – gives us another method to make a good estimate at the total cost of the path and again is very bias in directing the search toward the goal. To get the total overall cost from any individual node we use the calculation f() = g() + h(). H() should always be admissible or an underestimate of the cost to the goal from that node. If h() holds an over-estimated value, promising paths could be missed out from the search or just delayed, causing the calculation to become more expensive. A* and Dijkstra both follow the same general algorithm. However the associated cost now takes into consideration the estimated cost to the goal as well (the heuristic cost).
It isn’t really a surprise to see that the fundamental weakness of A* is in it’s management of the two lists of the explored and un explored nodes. The open list has to always remained sorted in order of cost, i.e. the top node has the lowest cost to the goal. A* can create quite a high cost in terms of efficiency on the CPU as it constantly has to poll the two lists to see if a node has been evaluated yet. Although there have been many optimizations made to A* to try and speed it up a bit it doesn’t really matter as if the search space is huge, the application can experience serious loss of performance and possibly even stop functioning as the overall costs of maintaining the two lists increases with the size of the search space. Finding a path in a complex 3D environment can easily hinder A* with situations that may not be produced from a simple 2D pathfind.
A good example of showing the complexities of demanding situations would be to look at a Rubik’s Cube. Finding the quickest solution to a Rubik’s cube using A* can easily cause it to exceed it’s available memory after just a couple of minutes. This is because, in a 3x3x3 cube for example, any individual node can have as many as 18 child nodes to search. It doesn’t really matter if we place restrictions on the movement manipulations of the cube (for example, not turning the same side twice) would only limit a node’s children to 13 or so. Therefore after 8 turns, over 1 billion possible combinations appear. Therefore it is wise to find other methods to find a solution in a more timely and efficient manner.
The Iterative Deepening A*(IDA*)
IDA* is an extension to A*. This algorithm has a problem in that it is possible to evaluate the same node several times. This is because it kills the two lists and does not use them. However this problem can be catered for by carefully structuring how the nodes and evaluated and expanded. i.e. specific orders and stopping of backtracking.
It can sometimes also be self accommodating as nodes that are expanded earlier have a lower value of g() compared to nodes expanded later on. It should also have the same value for h() no matter when it was evaluated. A maximum threshold for the cost is defined and if a node exceeds this value, it will not be explored. If however after expanding all nodes that fall under this value and the goal has not been reached, the threshold is increased. The search must be reinitiated for the original node since no history is kept without the lists. Each node must then be expanded that fall under the new threshold. This might seem counter productive, but it costs less to re-expand a node than to store all expanded nodes in the lists and keeping them maintained. “In addition, the frontier nodes, those at the edge of the search that were not explored before, will always be greater in number than the number of expanded nodes below the threshold.” Therefore the cost of re-evaluating a node is smaller compared to the cost of expanding the new frontier. The ultimate goal is for the lowest possible overhead in memory, CPU time and the time for the actual search itself.
The Fringe Search Algorithm
In-between the two algorithms mentioned above is the Fringe algorithm. Similar to IDA* it expands nodes under the guidance of a cost threshold. But in this case, the frontier nodes are not lost. They are instead kept in two new lists called now and later.
The current node atop the now list is investigated. If the f() value exceeds the threshold it is moved to the later list. If the f() is lower, the child nodes are expanded and the current node is discarded. The child nodes are then placed on top of the now list.
The nodes are expanded much like the depth-first fashion of IDA* but this algorithm keeps the lists in a semi sorted state. Again like IDA* if the goal isn’t found under the current threshold value, it is increased. The later list is then made to be the now list and the search continues using the new now list. There is no sorting cost associated with the maintenance of the two lists. The extra memory needed to do this is less than A* on it’s own uses as there is no need to store all the previously explored nodes. There is no speed loss either compared to the loss when IDA* has to repeat searches from iteration to iteration.
Conclusion
There is an abundance of available pathfinding algorithms today. The biggest consideration behind picking one of these algorithms are the memory constraints and the time constraints (normally one has to be sacrificed for the other). A* is the most popular choice because of the degree to which it can be specialised and optimised for each applications. IDA* and fringe are very useful modifications of the traditional A* set of algorithms and could prove to be better compared to the usual approaches to pathfinding.
No comments:
Post a Comment