|
| |
|
|
Coordinated pathfinding with formations
Obrázek, Václav ; Surynek, Pavel (advisor) ; Balyo, Tomáš (referee)
The topic of cooperative pathfinding with the extension of formations is addressed in this thesis. The problem of cooperative pathfinding with formations was formally defined and a new scalable hierarchical modular solving algorithm named APriCA was introduced and implemented. For testing and benchmarking purposes an environment called ChessWars was developed. In order to measure the quality of maintaining formations we introduced a new quantity named "fragmentation". The APriCA algorithm performed better than external domain independent planners such as LPG, Blackbox and SASE in all aspects. In comparison with the LRA* algorithm the solutions found by APriCA were of better quality and with certain parameters settings were found faster.
|
|
| |
|
|
Graph labeling
Böhm, Martin ; Mareš, Martin (advisor) ; Balyo, Tomáš (referee)
We introduce the concept of adjacency labeling schemes and recent results in the area. These schemes have practical application in parallel algorithm design and they relate to the theory of universal graphs. We concentrate on the modern technique of "Traversal and Jumping". We present a less technical proof of its correctness as well as correcting some errors in the original proof. We also apply brute-force algorithms to find small induced-universal graphs. 1
|
|
|
Unified Editor for CEGUI
Preisler, Martin ; Babka, Martin (advisor) ; Balyo, Tomáš (referee)
This thesis presents a free software GUI application called the CEGUI Unified Editor. The application is mainly written in Python and is licensed under GPLv3. Its purpose is to create and modify assets of graphical interfaces made with the CEGUI library. Features include project management, imageset editing and layout editing. Data for older versions of CEGUI are transparently converted using compatibility layers. Big emphasis is put on ease of use, collaboration between multiple content authors and portability.
|
|
|
Comparing reactive techniques to classical planning for intelligent virtual agents
Černý, Martin ; Gemrot, Jakub (advisor) ; Balyo, Tomáš (referee)
Many contemporary computer games can be described as dynamic real-time simulations inhabited by autonomous intelligent virtual agents (IVAs) where most of the environment structure is immutable and navigating through the environment is one of the most common activities. Though controlling the behaviour of such agents seems perfectly suited for action planning techniques, planning is not widely adopted in existing games. This paper attempts to answer the question whether the current academic planning technology is ready for integration to existing games and under which conditions. The paper compares reactive techniques to classical planning in handling the action selection problem for IVAs in game-like environments. Several existing classical planners that occupied top positions in the International Planning Competition were connected to the virtual environment of Unreal Development Kit via the Pogamut platform. Performance of IVAs employing those planners and IVAs with reactive architecture was measured on a class of game like test environments under different levels of external interference. It was shown that agents employing classical planning outperform reactive agents only if the size of the planning problem is small or if the environment changes are either hostile to the agent or not very frequent.
|
|
|
Real-time strategy game with artificial intelligence
Fanta, Petr ; Balyo, Tomáš (advisor) ; Dvořák, Filip (referee)
The aim of this thesis is to create a real-time strategy game with artificial intelligence in 3D environment. The thesis includes theoretical analysis of combat real-time strategy games, methods for implementing artificial intelligence in this kind of games, and the basic knowledge of 3D environment implementation. A simple 3D real-time strategy game with artificial intelligence has been implemented as a part of this this thesis.
|
|
|
2D Platform Game Creator
Rybář, Milan ; Balyo, Tomáš (advisor) ; Babka, Martin (referee)
The aim of this thesis is to implement an application for creating 2D games with physics simulation. The game can be created without any programming knowledge. We propose an extendable visual scripting to define the behaviour of game objects. The game objects are described by finite state machines. Nodes with pre-defined behaviour are connected on a virtual space at the object states. The work contains a comparison with similar applications. The capabilities of the application and the visual scripting method are demonstrated on a sample project.
|
|
|
Efficient SAT Solver
Balyo, Tomáš ; Mareš, Martin (referee) ; Surynek, Pavel (advisor)
The boolean satisfaction problem (SAT) is one of the most important and most studied problems of artificial intelligence. Many theoretical and real life problems are transformed to SAT and solved using a SAT solver. During the research for this thesis two SAT solvers were developed. They are described and compared with several of today's state-of-art SAT solvers. The presented solvers in many cases outperform the 2007's SAT competition winner R-sat and other famous SAT solvers. These two new solvers thank their speed to the implementation techniques used and to their decision heuristic, which is very efficient while absolutely costless.
|
|
|
Solving Boolean satisfiability problems
Balyo, Tomáš ; Barták, Roman (referee) ; Surynek, Pavel (advisor)
In this thesis we study the possibilities of decomposing Boolean formulae into connected components. For this reason, we introduce a new concept - component trees. We describe some of their properties and suggest some applications. We designed a class of decision heuristics for SAT solvers based on component trees and experimentally examined their performance on benchmark problems. For this purpose we implemented our own solver, which uses the state-of-theart SAT solving algorithms and techniques.
|
guest ::
