Site Search
Computer Science


Imran Ahmad, Ph.D.Dr. Imran Ahmad
Dr. Imran Ahmad
Alioune Ngom, Ph.D.Dr. Alioune Ngom
Dr. Alioune Ngom
Dr. Luis RuedaDr. Luis Rueda
Dr. Luis Rueda
Robin Gras, Ph.D.Dr. Robin Gras
Dr. Robin Gras
Jessica Chen, Ph.D.Dr. Jessica Chen
Dr. Jessica Chen
Lambton TowerLambton Tower
Lambton Tower
Windsor WaterfrontWindsor Waterfront Park
Windsor Waterfront Park
Dr. Robert KentDr. Robert Kent
Dr. Robert Kent
Dr. Scott GoodwinDr. Scott Goodwin
Dr. Scott Goodwin
Arunita Jaekel, Ph.D.Dr. Arunita Jaekel
Dr. Arunita Jaekel
Christie Ezeife, Ph.D.Dr. Christie Ezeife
Dr. Christie Ezeife
Xiaobu Yuan, Ph.D.Dr. Xiaobu Yuan
Dr. Xiaobu Yuan
Dr. Ziad Kobti lecturingDr. Ziad Kobti
Dr. Ziad Kobti

Analyzing Map Complexity based on Heuristic Error

Add this event into your calendar using the iCAL format
  • Fri, 10/12/2018 - 1:00pm - 3:00pm

Analyzing Map Complexity based on Heuristic Error

MSc Thesis Proposal by:

Sheeba Mohanraj

Date:  Friday, October 12th, 2018
Time:  1: 00 pm – 2:00 pm
Location: 3105, Lambton Tower

Abstract: Pathfinding is the search for the least cost route between two points on a map. A* is the most popular pathfinding algorithm. It uses problem specific heuristics to reduce search costs. If the heuristic used never over estimates the true cost, then A* is guaranteed to find the optimal solution. Moreover, if the heuristic error, the difference between the estimated cost and the true cost, grows no faster than the logarithm of the true cost, the time complexity of the algorithm is polynomial. We propose to use this property to analyze game maps to identify problem areas that cause search complexity to become exponential. This will provide game designers with the ability to revise their maps to improve pathfinding efficiency.

Thesis Committee:
Internal Reader: Dr. Xiaobu Yuan
External Reader: Dr. Myron Hlynka
Advisor: Dr. Scott Goodwin

See More: