Date of Award

9-12-2018

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Supervisor

Goodwin, Scott

Rights

info:eu-repo/semantics/openAccess

Abstract

With a given map and a start and a goal position on the graph, a pathfinding algorithm typically searches on this graph from the start node and exploring its neighbour nodes until reaching the goal. It is closely related to the shortest path problem. A* is one of the best and most popular heuristic-guided algorithms used in pathfinding for video games. The algorithm always picks the node with the smallest f value and process this node. The f value is the sum of two parameters g (the actual cost from the start node to the current node) and h (estimated cost from the current node to the goal). At each step of the algorithm, the node with lowest f will be removed from an open list and its neighbour nodes with their f values would be updated in this list. The main cost of this algorithm is the frequent insertion and deleteMin operations of the open list. Typically, implementation of A* uses a priority queue or min-heap to implement the open list, which takes O(log n) for the operations in the worst case. But this is still expensive when using the algorithm in a large and complicated map with numerous nodes. We came up with a new data structure called multi-stack heap for the open list based on the 2D grid map and Manhattan distance, which only costs O(1) for insertion and deleteMin. It is very efficient especially when we have a considerable number of nodes to explore. Additionally, traditional A* requires checking whether the open list contains a duplicated of the being inserted node before every insertion, which takes O(n). We proposed a new implementation method based on admissible and consistent heuristic called “Check From Closed List”, it can reduce the time of this process to O(1).

Download

Share

COinS