Date of Award
2014
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Communication and the arts, Applied sciences, A*, Heuristic, Pathfinding, Region, Search, Transit
Supervisor
Goodwin, Scott
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
Pathfinding is an area of research and of practical importance in Computer Science. The A* algorithm is well known as a pathfinding algorithm that finds optimal paths. As demands increase on pathfinding systems, we need faster algorithms to keep up. We propose an algorithm that uses preparation to partition the search space into regions that we may be able to skip while searching. We call this algorithm Transit Search, and by potentially skipping regions of the search space we can expand less nodes than A*. It accomplishes this by using a maximum allowed heuristic value to tell the search if it is possible the goal is within a region. If this isn't the case the algorithm can skip the region entirely, saving us from expanding unneeded nodes.
Recommended Citation
Moore, Justin, "Transit Search" (2014). Electronic Theses and Dissertations. 5109.
https://scholar.uwindsor.ca/etd/5109