The University of Windsor has moved to an “essential service only” model. Learn More.

MSc Thesis Defense Announcement by Shrijan Karmacharya:"Improving Lookahead search for grid-based pathfinding"

Wednesday, January 22, 2020 - 15:00 to 17:00


The School of Computer Science is pleased to present…


MSc Thesis Defense by: Shrijan Karmacharya

Date: Wednesday January 22, 2020
Time:  3:00PM – 5:00 PM     
Location: LT 3105


Pathfinding is an essential part of navigation systems, often used in video games, route planning and robotic navigation. A* search has been one of the most well-known and frequently used algorithms for pathfinding.  A* uses an  and a  to keep track of all nodes generated and expanded. The size and performance of these data structures are major drawbacks of A*. Lookahead is used to investigate future outcomes and improve the quality of available choices. Lookaheads are done on a DFS manner from the frontier of A* search. This combination of A* and DFS lookahead has been shown to save space when working with puzzles. We leverage this concept with grid-based pathfinding in video games to save the amount of space consumed. However, because grids contain redundant paths, the DFS lookaheads end up being an overhead as they do not maintain a list of nodes visited or expanded. By using a domain-specific pruning technique, we significantly improve the time taken by the algorithm and further improve upon the space consumed. A combination of lookahead and A* search with this pruning technique is, therefore, able to achieve improvement in both space-consumed and time-taken over the standard A* search algorithm for grid-based pathfinding.

Thesis Committee:

Internal Reader: Dr. Sherif Saad Ahmed
External Reader: Dr. Myron Hlynka          
Advisor: Dr. Scott Goodwin
Chair: TBA

MSc Thesis Defense Announcement


5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716