Refine
Document Type
- Bachelor Thesis (1)
- Master's Thesis (1)
Year of publication
- 2018 (2) (remove)
Keywords
- Algorithmus (2) (remove)
Institute
Agenten in virtuellen Welten können sich mit Hilfe verschiedener Wegfindungsalgorithmen selbständig von einem Start- zu einem Zielpunkt bewegen. Dafür existieren zahlreiche Algorithmen, um beispielsweise im Rahmen eines Videospiels an die Agenten gestellten Anforderungen und Handlungssequenzen zu erfüllen. Eine solche Anforderung stellt häufig die Navigation durch einen Spielbereich dar. Bei der Anwendung auf Videospiele müssen besondere Voraussetzungen erfüllt werden. Hierzu gehört ein besonders effizienter Umgang mit den zur Verfügung stehenden Ressourcen, um echtzeitfähige Entscheidungen zu ermöglichen und eine nahtlose Integration ins Spielgeschehen zu gewährleisten.
Zu diesem Zweck sind verschiedene klassische Wegfindungsalgorithmen zu implementieren und auf ihre Qualität und Effizienz zu prüfen. Mithilfe der Unity Engine lassen sich verschiedene Szenarien kreieren, die Herausforderungen für unterschiedliche Agenten bilden. Dabei werden die zurückgelegten Wege und Zeiten, aber auch die benötigten Ressourcen mithilfe eines Logging-Systems aufgezeichnet, miteinander verglichen und deren Gute in Abhängigkeit zur Anwendungsdomäne evaluiert.
Path decomposition of a graph has received an important amount of interest over the past decades because of its applications in algorithmic graph theory and in real life problems. For the computation of a path decomposition of small width, we use different heuritics approaches. One of the most useful method is by Bodlaender and Kloks. In this thesis, we focus on the computation, applications, transformation and approximation of a path decomposition of small width.
It is easy to convert a path decomposition in to nice path decomposition with same width, which is more convinent to use to find the graph parameters like independent sets, chromatic polynomials etc. Inspired by [28], we find an algorithm to compute the chromatic polynomial of a graph via nice path decomposition with small width.