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

MSc Thesis Proposal Announcement by Shrijan Karmacharya: Using lookahead to improve pathfinding in computer games

Thursday, June 13, 2019 - 10:00 to 12:00

 

SCHOOL OF COMPUTER SCIENCE

The School of Computer Science at the University of Windsor is pleased to present …

 

MSc Thesis Proposal by:

Shrijan Karmacharya

 
Date:  Thursday, June 13th, 2019
Time:  10: 00 am – 12:00 pm
Location: 3105, Lambton Tower
 

Abstract: 

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 OPEN LIST and a CLOSED LIST to keep track of all nodes generated and expanded respectively. The size and performance of these data structures are major drawbacks of A*.
Lookahead has been used to investigate future outcomes and improve the quality of our available choices. For this thesis, we use Lookahead in conjunction with A* search to exploit complementary benefits of both techniques. For informed search algorithms such as A*, lookahead can be used to improve the quality of search by improving the quality of evaluation function used. This has advantages when we don’t have to reorder OPEN list or re-open nodes in currently CLOSED list. By bounding the cost of lookahead carefully, we can ensure that there is no exponential increase in time. Furthermore, by using limited depth first lookahead from frontier nodes of A*, we use significantly less memory than regular A* and get a time speed up if the lookahead depth is set up correctly.
 

Thesis Committee:

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

MSc Thesis Proposal Announcement

5113 Lambton Tower, 401 Sunset Av. Windsor ON, N9B 3P4, (519) 253-3000 Ext. 3716 csgradinfo@uwindsor.ca

 

(519)253-3000