2DPathfinder 0.2

2DPathfinder is a C library for performing fast pathfinding on 2D maps. Its highly portable and easy to use, and well documented. The source code is released under the Lesser General Public License. Theory: Finding paths between locations is one interesting problem that can be solved with the “informed search” theory. A “general search” consists in expanding the start node, placing its successors in a queue, and then examining the next node in the queue. function general_search(start_state, target_state, push_function()) start_node <- make_node(start_state) queue <- start_node loop if empty(queue) then return no_solution current_node <- pop(queue) mark_closed(current_node) if state(current_node) = target_state then return solution for each node in successors(current_node) do if not closed(node) then queue <- push_function(node) end Many different algorithms can be obtained by defining the push_function(). The successors() function depends on the structure that represents the space of the states (a graph, a 2D map, etc). The “ramification factor” (b) is the number of states that can succeed to each state; d is the total number of expansion levels. The complexity of the search is, in the worst case, O(bd). The mark_closed() function is used to avoid to re-consider a node that has already been analyzed. While there are different ways to implement every single search strategy, one of them is always derived from a general search. So the different strategies are determined by how the nodes data structures and algorithms are implemented. For example, a “best-first search” is obtained by maintaining the open nodes sorted by a function that evaluates their states. To estimate the “goodness” of a node, a heuristic function can be used (h()). This is a “greedy” strategy. function best_first_search(start_state, target_state, eval_function()) push_function() <- a function that sorts the nodes using eval_function() return general_search(start_state, target_state, push_function()) A greedy search is generally very efficient, but minimizes only the estimated cost. Another strategy is the “uniform-cost search”, which minimizes the current path cost: it is optimal but very little efficient on large data. The function that returns the current (and effective) path cost is usually called g(). function greedy_search(start_state, target_state) return best_first_search(start_state, target_state, h()) Such a search can also be implemented with “dynamic programming” or with “memoization” (see Dijkstras algorithm). The A* (pronounced “A-star”) search combines the advantages of the greedy and uniform-cost searches: it minimizes the total search cost by using the sum of the two functions as the evaluation function (f()): f = g + h In other words, the f cost of a node is the sum of the path generated to get there from the start node and the path estimated to reach the target. function A_star_search(start_state, target_state) return best_first_search(start_state, target_state, f()) In a 2D map, typical heuristics can be the Euclidean distance, the “Manhattan” distance or the Diagonal distance. After a few benchmarks, I realized that the Diagonal distance performs very well. Whats New in This Release: - A more precise "diagonal" heuristic was adopted..

Requirements:	No special requirements
Platforms:	Linux
Keyword:	Libraries,  Library,  Pathfinding,  Programming
Users rating:	0/10