     |
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Fine-Tuning Your Search Engine There are also ways of tweaking the search algorithm to help get good results while working with limited resources: Beam search. One way of dealing with restricted memory is to limit the number of nodes on the Open list; when it is full and a new node is to be inserted, simply drop the node with the worst rating. The Closed list could also be eliminated, if each tile stores its best path length. There is no promise of an optimal path since the node leading to it may be dropped, but it may still allow finding a reasonable path. Iterative-deepening A*. The iterative-deepening technique used for depth-first search (IDDFS) as mentioned above can also be used for an A* search. This entirely eliminates the Open and Closed lists. Do a simple recursive search, keep track of the accumulated path cost g(n), and cut off the search when the rating f(n) = g(n) + h(n) exceeds the limit. Begin the first iteration with the cutoff equal to h(start), and in each suceeding iteration, make the new cutoff the smallest f(n) value which exceeded the old cutoff. Similar to IDDFS among bruteforce searches, IDA* is asymptotically optimal in space and time usage among heuristic searches. Inadmissible heuristic h(n). As discussed above, if the heuristic estimate h(n) of the remaining path cost is too low, then A* can be quite inefficient. But if the estimate is too high, then the path found is not guaranteed to be optimal and may be abysmal. In games where the range of terrain cost is wide--from swamps to freeways--you may try experimenting with various intermediate cost estimates to find the right balance between the efficiency of the search and the quality of the resulting path. There are also other algorithms that are variations of A*. Having toyed with some of them in PathDemo, I believe that they are not very useful for the geometric path-finding domain.
|
||||||||||||||||||||||||||||||||||||
Features
|
|
|