DISADVANTAGES AND ADVANTAGES OF USING GRAPH THEORY IN VIDEO GAMES

Abstract

The paper discusses the disadvantages and advantages of using graph theory in video games.  The analysis of existing methods of applying the theory of graphs, how the algorithm for finding the shortest path and its modification looks like the algorithm of Dijkstree, Bellman, algorithm A *, greedy algorithm and others.  The article considers the use of graph theory to describe the state in which the character is located and transformations of such states, the reduction graph.  The general disadvantages of using graph theory include working only with structures containing graphs with an integral length of arcs, finding the shortest path from only one vertex, to implement the method, the algorithm needs to be repeated for each vertex, reflexive closures are not searched for, and are rather complicated in comparison with matrix  software implementation methods.

The advantages of the method include simplicity of implementation, low polynomial computational complexity, the possibility of machine implementation, and finding a solution to the problem, if any.

The above disadvantages and advantages of algorithms based on the use of graph theory in video games allow us to draw the following conclusion: the choice of an algorithm for implementation depends on the number of graph vertices, its orientation and the number of connections between graph vertices.  There is no single optimal problem algorithm according to which it is impossible to establish a graph with a certain number of vertices and connections between them.

For a small number of vertices, the A * algorithm is optimal for use in video games, but when the number of vertices in the graph reaches one hundred, then the use of this algorithm is ineffective.  This is due to the number of comparisons the algorithm conducts.  For a large number of vertices, taking into account the disadvantages and advantages, methods of sequential refinement from above and the method of generation and verification are proposed as optimal.  These methods have such drawbacks as the lack of reliable methods for evaluating the method, the risk of losing some of the possible ties and the search for all possible ties.  The advantages of these methods include the presence of an algorithm for clarifying the linkage and external influence on them in the process of finding a solution.

Key words: graph theory, search algorithms, A * algorithm, video game.