Date of Award

2014

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Goodwin, Scott

Keywords

Communication and the arts, Applied sciences, A*, Heuristic, Pathfinding, Region, Search, Transit

Rights

info:eu-repo/semantics/openAccess

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 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.

Share

COinS