Directed Recursion Search: A Directed DFS for Online Pathfinding in Random Grid-Based Environments

摘要

The most popular pathfinding approach used in video games is the A* algorithm. This paper looks at depth-first search to determine if, with modifications, it can be made into a viable alternative. Proposed is a method of directing a search, which utilises a scoring system. Tests conducted on randomly generated maps of varying sizes showed that Directed Recursion Search calculated near-optimal paths in less time, by expanding fewer nodes, and with less memory required to store the paths, than A* or depth-first search.