Institutional Repository of Vilnius University
Galvosūkio žaidimo sprendimas su A* paieška /
Abstract
dc:descriptionThe 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.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD88378804&prefLang=en_US