mdh.sePublications
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
A* Algorithm for Graphics Processors
Mälardalen University, School of Innovation, Design and Engineering. (MRTC)ORCID iD: 0000-0001-7448-3381
Department of Computing Science and Engineering, Chalmers University. (Distributed Computing and Systems Research Group)
Department of Computing Science and Engineering, Chalmers University. (Distributed Computing and Systems Research Group)
2010 (English)In: THIRD SWEDISH WORKSHOP ON MULTI-CORE COMPUTING - MCC'10, Chalmers University of Technology, Sweden, 2010Conference paper, (Refereed)
Abstract [en]

Today's computer games have thousands of agents moving at the same time in areas inhabited by a large number of obstacles. In such an environment it is important to be able to calculate multiple shortest paths concurrently in an efficient manner. The highly parallel nature of the graphics processor suits this scenario perfectly. We have implemented a graphics processor based version of the A* path finding algorithm together with three algorithmic improvements that allow it to work faster and on bigger maps. The first makes use of pre-calculated paths for commonly used paths. The second use multiple threads that work concurrently on the same path. The third improvement makes use of a scheme that hierarchically breaks down large search spaces. In the latter the algorithm first calculates the path on a high level abstraction of the map, lowering the amount of nodes that needs to be visited. This algorithmic technique makes it possible to calculate more paths concurrently on large map settings compared to what was possible using the standard A* algorithm. Experimental results comparing the efficiency of the algorithmic techniques on a NVIDIA GeForce GTX 260 with 24 multi-processors are also presented in the paper.

Place, publisher, year, edition, pages
Chalmers University of Technology, Sweden, 2010.
Keyword [en]
A* algorithm, Graphics Processing Unit
National Category
Computer Engineering
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-10933OAI: oai:DiVA.org:mdh-10933DiVA: diva2:369272
Conference
THIRD SWEDISH WORKSHOP ON MULTI-CORE COMPUTING - MCC'10, November 2010, Göteborg, Sweden
Available from: 2012-02-16 Created: 2010-11-10 Last updated: 2013-12-03Bibliographically approved

Open Access in DiVA

fulltext(622 kB)134 downloads
File information
File name FULLTEXT01.pdfFile size 622 kBChecksum SHA-512
df655bf8c7a9575339088a0fa4b0cbc8b5325b401e6b03887d671c57c69fbbee780dc09fe83280490c683ce26a3b5ae8932db363661ed21b54fa12da8aaed8f7
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Inam, RafiaCederman, DanielTsigas, Philippas
By organisation
School of Innovation, Design and Engineering
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 134 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

Total: 104 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