Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Video game pathfinding and improvements to discrete search on grid-based maps
Dissertation (MSc)--University of Pretoria, 2011.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Published: |
University of Pretoria
2013
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613644184879104 |
|---|---|
| access_status_str | Open Access |
| author2 | Engelbrecht, Andries P. |
| author_browse | Engelbrecht, Andries P. |
| author_facet | Engelbrecht, Andries P. |
| collection | Thesis |
| dc_rights_str_mv | © 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 |
| description | Dissertation (MSc)--University of Pretoria, 2011. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/22940 |
| institution | University of Pretoria (South Africa) |
| last_indexed | 2026-06-10T12:39:25.358Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2013 |
| publishDateRange | 2013 |
| publishDateSort | 2013 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/22940 Video game pathfinding and improvements to discrete search on grid-based maps Engelbrecht, Andries P. bobby.anguelov@gmail.com Anguelov, Bobby Navigation Graph search Hierarchical pathfinding Games A* Hierarchical search algorithms Pathfinding Artificial intelligence Video games UCTD Dissertation (MSc)--University of Pretoria, 2011. 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 Computer Science unrestricted 2013-09-06T14:02:33Z 2012-05-08 2013-09-06T14:02:33Z 2012-04-19 2011 2012-03-02 Dissertation Anguelov, B 2011, Video game pathfinding and improvements to discrete search on grid-based maps, MSc dissertation, University of Pretoria, Pretoria, viewed yymmdd < http://hdl.handle.net/2263/22940 > C12/4/196/gm http://hdl.handle.net/2263/22940 http://upetd.up.ac.za/thesis/available/etd-03022012-094023/ © 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 application/pdf University of Pretoria |
| spellingShingle | Navigation Graph search Hierarchical pathfinding Games A* Hierarchical search algorithms Pathfinding Artificial intelligence Video games UCTD Video game pathfinding and improvements to discrete search on grid-based maps |
| title | Video game pathfinding and improvements to discrete search on grid-based maps |
| title_full | Video game pathfinding and improvements to discrete search on grid-based maps |
| title_fullStr | Video game pathfinding and improvements to discrete search on grid-based maps |
| title_full_unstemmed | Video game pathfinding and improvements to discrete search on grid-based maps |
| title_short | Video game pathfinding and improvements to discrete search on grid-based maps |
| title_sort | video game pathfinding and improvements to discrete search on grid based maps |
| topic | Navigation Graph search Hierarchical pathfinding Games A* Hierarchical search algorithms Pathfinding Artificial intelligence Video games UCTD |
| url | http://hdl.handle.net/2263/22940 http://upetd.up.ac.za/thesis/available/etd-03022012-094023/ |