Title page for ETD etd-03022012-094023

Document Type Master's Dissertation
Author Anguelov, Bobby
URN etd-03022012-094023
Document Title Video game pathfinding and improvements to discrete search on grid-based maps
Degree MSc
Department Computer Science
Advisor Name Title
Prof A P Engelbrecht Supervisor
  • navigation
  • graph search
  • hierarchical pathfinding
  • games
  • A*
  • hierarchical search algorithms
  • pathfinding
  • artificial intelligence
  • video games
Date 2012-04-19
Availability unrestricted
The most basic requirement for any computer controlled game agent in a video game is to be able to successfully navigate the game environment. Pathfinding is an essential component of any agent navigation system. Pathfinding is, at the simplest level, a search technique for finding a route between two points in an environment. The real-time multi-agent nature of video games places extremely tight constraints on the pathfinding problem. This study aims to provide the first complete review of the current state of video game pathfinding both in regards to the graph search algorithms employed as well as the implications of pathfinding within dynamic game environments. Furthermore this thesis presents novel work in the form of a domain specific search algorithm for use on grid-based game maps: the spatial grid A* algorithm which is shown to offer significant improvements over A* within the intended domain.

Copyright 2011, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria

Please cite as follows:

Anguelov, B 2011, Video game pathfinding and improvements to discrete search on grid-based maps, MSc dissertation, University of Pretoria, Pretoria, viewed yymmdd < http://upetd.up.ac.za/thesis/available/etd-03022012-094023 / >


  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  dissertation.pdf 8.50 Mb 00:39:20 00:20:13 00:17:42 00:08:51 00:00:45

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact UPeTD.