Back to search

Institutional Repository of Vilnius University

Galvosūkio žaidimo sprendimas su A* paieška /

Abstract

dc:description

The essence of the work is to apply the A* algorithm in solving various puzzle games by creating artificial intelligence that will have a flair for the game and will be able to evaluate various game positions by using heuristic calculation and develop potential moves with existing knowledge that will lead to a successful level completion. The aim of this work is to review various algorithms that can be used to solve this kind of problems and compare their runtime and memory load, as well as to review several computer puzzles where various algorithms can be used to overcome level problems and compare the branching factor and memory load. Also create an Atomix game and apply the A* algorithm to its solution. To be able to calculate best move for computer in Atomix position various heuristic calculations were made. One of them is BFS usage in position analysis when atoms try to calculate moves to achieve needed coordinate. BFS algorithm will expand states until needed coordinate would be hited and children count for parent position is taken as moves that are needed. If BFS have no longer moves to expand because all states are already visited some value of t will be assigned as penalty and graph will me marked as disconnected for this patern Manhattan distance will be aplied for distance calculation. The problem is that Manhattan distance calculates vector between atoms but this vector does not equal to moves that have to be made to achieve the desired position. For various optimizations used data structers in A* algorithm are: Minimum priority queue to have fast ability to extract position that have minimum penalty count with O(1) speed and insert position with O(log N) time complexity. For already analized position Hash table is used because it have ability to check it O(1) speed. The results of the work are: developed Atomix game and created various levels that the applied A* algorithm is able to solve using heuristic calculations. Problem is solved when player is able to assemble given molecule from atoms on the map. Also examined similar games for example Sokoban, (n^2 - 1) - puzzle , and algorithms that can be applied to solve various problems.

Degree

thesis:*
Grantor dc:publisher
Institutional Repository of Vilnius University
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Špakovskij, Daniel,
Contributors dc:contributor
  • Astrauskas, Rokas

Rights

dc:rights
Statement dc:rights
  • info:eu-repo/semantics/openAccess
Language dc:language
lit

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Špakovskij, Daniel,. Galvosūkio žaidimo sprendimas su A* paieška /. Institutional Repository of Vilnius University, 2021. https://repository.vu.lt/VU:ELABAETD88378804&prefLang=en_US