JPS algoritmin käyttö

Abstract

Polunetsintä on keskeinen ongelma tietotekniikassa. Tämä tutkielma vertailee vanhoja polunetsimisalgoritmeja uudenpiin, kuten Jump Point Searchiin. Se luotiin vuonna 2011 ja se karsii turhia solmuja ja hyppii hyppypisteiden välillä, tehden siitä nopeamman ja muistitehokkaamman. Polunetsimisalgoritmeilla on monta käyttötarkoitusta, robotiikas- ta videopeleihin. Tämä tutkielma käy läpi JPS derivatiiveja, joilla on eri käyttötarkoituksia, sekä miten niitä käytetään. Vaikka JPS on julkaistu yli vuosikymmen sitten, on sen käyttö jäänyt ilmeisen vähäiseksi, vaikka sen suorituskyky on jopa kymmenkertainen klassisiin me- netelmiin verrattuna. Tämä tutkielma päättyy reflekioihin potentiaalisista syistä, jotka voivat vaikuttaa siihen.

Pathfinding is an ever evolving problem in computer science. This thesis will compare old pathfinding algorithms to newer ones, like the Jump Point Search. It was created in 2011 and it prunes unnecessary nodes and jumps between jump points, making it much faster and memory efficient. Pathfinding algorithms have many use cases, ranging from robotics to video games. This thesis will talk about some JPS derivatives, which have more versatile use cases and why one should use them. Despite JPS being out for over a decade, it has no public show of use anywhere, while outperforming the industry standards up to tenfold. This thesis ends with reflections on potential reasons contributing to this.