Digitala Vetenskapliga Arkivet

Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Comparing node-sorting algorithms for multi-goal pathfinding with obstacles
Blekinge Tekniska Högskola, Fakulteten för datavetenskaper, Institutionen för datavetenskap.
Blekinge Tekniska Högskola, Fakulteten för datavetenskaper, Institutionen för datavetenskap.
2019 (engelsk)Independent thesis Basic level (degree of Bachelor), 10 poäng / 15 hpOppgave
Abstract [en]

Background. Pathfinding plays a big role in both digital games and robotics, and is used in many different ways. One of them is multi-goal pathfinding (MGPF) which is used to calculate paths from a start position to a destination with the condition that the resulting path goes though a series of goals on the way to the destination. For the most part research on this topic is sparse, and when the complexity is increased through obstacles that are introduced to the scenario, there are only a few articles in the field that relate to the problem.Objectives. The objective in this thesis is to conduct an experiment to compare four algorithms for solving the MGPF problem on six different maps with obstacles, and then analyze and draw conclusions on which of the algorithms is best suited to use for the MGPF problem. The first is the traditional Nearest Neighbor algorithm, the second is a variation on the Greedy Search algorithm, and the third and fourth are variations on the Nearest Neighbor algorithm. Methods. To reach the Objectives all the four algorithms are tested fifty times on six different maps of varying sizes and obstacle layout. Results. The data from the experiment is compiled in graphs for all the different maps, with the time to calculate a path and the path lengths as the metrics. The averages of all the metrics are put in tables to visualize the difference between the results for the four algorithms.Conclusions. The conclusions were that the dynamic version of the Nearest Neighbor algorithm has the best result if both the metrics are taken into account. Otherwise the common Nearest Neighbor algorithm gives the best results in respect to the time taken to calculate the paths and the Greedy Search algorithm creates the shortest paths of all the tested algorithms.

sted, utgiver, år, opplag, sider
2019. , s. 37
Emneord [en]
multi-goals, pathfinding, nearest neighbor algorithms
HSV kategori
Identifikatorer
URN: urn:nbn:se:bth-18256OAI: oai:DiVA.org:bth-18256DiVA, id: diva2:1333770
Fag / kurs
DV1478 Bachelor Thesis in Computer Science
Utdanningsprogram
DVGSP Game Programming
Veileder
Examiner
Tilgjengelig fra: 2019-07-26 Laget: 2019-07-01 Sist oppdatert: 2019-07-26bibliografisk kontrollert

Open Access i DiVA

BTH2019LjungbergF_Åleskog(1222 kB)878 nedlastinger
Filinformasjon
Fil FULLTEXT02.pdfFilstørrelse 1222 kBChecksum SHA-512
35019f0857ed6337ec9f5a4d870bd34b2eb021015019db233f64ee68e1f1e4ba389ef989574556e6cf892edb332213f3fdbfc0f703d7b99b3ddb9f323d1ad149
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 881 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 899 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf