Date of Award

9-17-2019

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

A* Search, Buckets, Min-Heap, Open list, Pathfinding, Shortest-path

Supervisor

Goodwin, S.

Rights

info:eu-repo/semantics/openAccess

Abstract

Pathfinding is the search for the least cost route between two points on a map. Given a map with a start node and a goal node, the pathfinding algorithm begins from the start node and searches through the map exploring its neighbours until it finds a path to the goal node. A* is the most popular pathfinding algorithm which uses heuristics for finding the least cost path from the start node to the goal node. The A* algorithm uses two parameters g cost(the actual cost of reaching the current node from the start node) and the h cost(the estimated cost of reaching the goal node from the current node). F cost is the sum of the g cost and the h cost. At each iteration, the A* algorithm chooses the node with the lowest f cost from the open list to be expanded. This node will be removed from the open list and added to the closed list. This process is repeated until reaching the final node. The A* algorithm for pathfinding is affected by its data structures, particularly by the frequent insertions and deletions in the open list. Min-Heap is the commonly used data structure for implementing the open list for A* algorithm, which takes O(log n) for insertion and deletion. Since this is very expensive, we explored the idea of implementing the open list with Buckets, which was initially introduced for improving the performance of Dijkstra's algorithm. We found that the bucket data structure produces better results as it takes O(1) for inserting a node into the open list and O(bucket size) for deletion. We compared the performance of both the algorithm under various factors to determine which was performing better.

Download

Share

COinS