Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Automated generation of waypoints: for pathfinding in a static environment
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Video game characters must almost always be able to travel from point A to point B and this task can be solved in various ways. There exist grid maps, waypoints, mesh navigation and hierarchical techniques to solve this problem. On randomly generated terrain we make use of automatically generated waypoints to solve pathfinding queries. The waypoints are connected by edges to create a waypoint graph and the graph can be used in real time pathfinding for a single agent in a static environment. This is done by finding the vertices of the blocked triangles from the terrain and place a waypoint on each. We make use of the GPU to create the waypoint graph. The waypoints are connected by utilizing a serialized GPU quad tree to find the relevant blocked geometry to do a line-triangle intersection test. If a line between two waypoints do not intersect any blocked geometry the connection is valid and stored. We found out that it is possible to generate a waypoint graph during the startup of the game with acceptable time results, make use of such a graph for real time pathfinding and that players perceive the paths generated by the algorithm as realistic and responsive. Our conclusion is that our solution is well suited for a deterministic environment with agents of the same size.

Place, publisher, year, edition, pages
2019. , p. 33
Keywords [en]
Pathfinding, Waypoint generation, Terrain generation, User perception
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-18324OAI: oai:DiVA.org:bth-18324DiVA, id: diva2:1333581
Subject / course
DV1478 Bachelor Thesis in Computer Science
Educational program
DVGSP Game Programming
Supervisors
Examiners
Available from: 2019-07-26 Created: 2019-07-01 Last updated: 2019-07-26Bibliographically approved

Open Access in DiVA

BTH2019NyqvistOlsson(1291 kB)44 downloads
File information
File name FULLTEXT02.pdfFile size 1291 kBChecksum SHA-512
7332de3074adced1a284f0fac04e6963ad512488033f7ec1614439ceea89ff801b1955613aa83fa9678992fcd06991006d221b6981056d26495057c538ebe3ab
Type fulltextMimetype application/pdf

By organisation
Department of Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 44 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 92 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf