Abstract
Content
- Introduction
- 1. Research goals and objectives
- 2. Work description
- 2.1 Algorithm A star
- 2.2 Wave algorithm
- 2.3 Graphics engine
- References
Introduction
From primitive rituals to modern high–budget computer projects, games have been one of the most important parts of our being. They entertain, have a therapeutic effect and educate people. In this paper, we will consider a specific type of games that originated in the 40s of the twentieth century. But it became widespread in the 70s – 80s of the last century. We are talking about computer games.
According to Wikipedia «A computer game is a computer program used to organize the game process (gameplay), to communicate with game partners, or itself acting as a partner» [1]. Technological advances have made entertainment software development open source and easy
One of the important elements of the game is game mechanics, that is, a set of rules and methods that implement the gameplay. Interacting with NPCs is one such mechanic. Developing the mechanics and rules by which these characters exist in the game is a very laborious process. But no less important, since the interaction with characters in role–playing or arcade games is the main backbone of the game itself.
1. Research goals and objectives
The goal of my research is to develop a software implementation of the behavior of an NPC. Also develop a game engine for future use.
The aim of my thesis is the development and software implementation of a behavior model for NPCs.
One of the ways to emotionally tie a person to a fictional game world is to create the illusion of life and fulfillment. The characters of the computer game are responsible for this, and in particular their behavior and reaction to the player's actions. They can be, like, friendly, they are called non–player characters (NPC from the English. Non–player character), and hostile to the player bots (from the English. Bot) and mobs (from the English. Mob).
According to Wikipedia «A non–player character is a character in games that is not under the player's control.» [2]
The planned results of my work are the development of an algorithm for making decisions by an NPC and the implementation of the main part of the game mechanics in pygame. In the future, I plan to develop the game and, when moving to a better PC, transfer to a better PC.
2. Work description
The aim of my thesis is the development and software implementation of a behavior model for NPCs.
The goal of my research is to develop a software implementation of the behavior of an NPC. Also develop a game engine for future use.
One of the ways to emotionally tie a person to a fictional game world is to create the illusion of life and fulfillment. The characters of the computer game are responsible for this, and in particular their behavior and reaction to the player's actions. They can be, like, friendly, they are called non–player characters (NPC from the English. Non–player character), and hostile to the player bots (from the English. Bot) and mobs (from the English. Mob).
According to Wikipedia «A non–player character is a character in games that is not under the player's control.» [2]
The planned results of my work are the development of an algorithm for making decisions by an NPC and the implementation of the main part of the game mechanics in pygame. In the future, I plan to develop the game and, when moving to a better PC, transfer to a better PC.
2.1 Algorithm A star
A * iterates through all the paths leading from the initial vertex to the final one until it finds the minimum. Like all informed search algorithms, it looks first at those routes that «seem» to lead to the target. What distinguishes it from the greedy algorithm, which is also a first–best match search algorithm, is that when choosing a vertex, it takes into account, among other things, the entire path traveled to it. The component g (x) is the cost of the path from the initial vertex, not from the previous one, as in the greedy algorithm.
At the beginning of work, the nodes adjacent to the initial one are viewed; the one with the minimum value f (x) is selected, after which this node is expanded. At each stage, the algorithm operates with a set of paths from the starting point to all not yet opened (leaf) vertices of the graph – a set of particular solutions – which are placed in the queue with priority. The priority of the path is determined by the value f (x) = g (x) + h (x).
The algorithm continues its work until the value f (x) of the target vertex is less than any value in the queue, or until the entire tree has been scanned. The solution with the lowest cost is selected from the set of solutions. The smaller the heuristic h (x), the higher the priority, so sorting trees can be used to implement the queue. Like Breadth First Search, A * is complete in the sense that it always finds a solution if one exists.
If the heuristic function h is admissible, that is, it never overestimates the actual minimum cost of achieving the goal, then A * itself is admissible (or optimal), also provided that we do not cut off the passed vertices. If we do this, then for the algorithm to be optimal it is required that h (x) be also a monotonic, or successive heuristic. A * is both admissible and bypasses the minimum number of vertices, due to the fact that it works with an «optimistic» estimate of the path through the vertex. Optimistic in the sense that if it goes through this vertex, the algorithm "has a chance" that the real cost of the result will be equal to this estimate, but not less. But since A * is an informed algorithm, such equality may be quite possible.
When A * completes its search, it has, by definition, found a path whose true cost is less than the estimated cost of any path through any open node. But since these estimates are optimistic, the corresponding nodes can be discarded without a doubt. In other words, A * will never miss an opportunity to minimize the path length, and therefore is valid.
Suppose now that some Algorithm B returned as a result a path whose length is greater than the estimated cost of the path through some vertex. Based on the heuristic information, for Algorithm B it is impossible to exclude the possibility that this path had a smaller real length than the result. Accordingly, as long as Algorithm B has scanned fewer vertices than A *, it will not be valid. So, A * traverses the least number of graph vertices among admissible algorithms using the same exact (or less accurate) heuristic. Figure 1 shows an example of how the algorithm works.
Figure 1 – An example of the algorithm A *(25 frames, loop of repetitions: infinite, size: 45 kb)
2.2 Wave algorithm
The algorithm works on a discrete working field (DRP), which is a figure bounded by a closed line, not necessarily rectangular, divided into rectangular cells, in a particular case – square. The set of all cells of the DRP is divided into subsets: «passable» (free), that is, when searching for a path, they can be passed, «impassable» (obstacles), the path through this cell is prohibited, the starting cell (source) and finishing (receiver). The designation of the starting and finishing cells is conditional, it is enough – specifying a pair of cells between which you need to find the shortest path.
The algorithm is designed to find the shortest path from the starting cell to the final cell, if possible, or, if there is no path, to issue a message about obstruction. The operation of the algorithm includes three stages: initialization, wave propagation and path restoration. During initialization, an image of a set of cells of the processed field is built, each cell is assigned the attributes of passability / obstruction, the start and finish cells are remembered.
Further, from the starting cell, a step is generated into the neighboring cell, while checking whether it is passable and whether it belongs to a cell previously marked in the path. Neighboring cells are usually classified in two ways: in the sense of the Moore neighborhood and the von Neumann neighborhood, which differs in that in the von Neumann neighborhood, only 4 cells are considered to be adjacent vertically and horizontally, in the Moore neighborhood – all 8 cells, including the diagonal ones.
When the conditions of passability are met and it does not belong to the cells previously marked in the path, a number equal to the number of steps from the starting cell is written into the cell attribute, from the starting cell at the first step it will be 1. Each cell marked with the number of steps from the starting cell, becomes the starting one and next steps to adjacent cells are generated from it. Obviously, such an enumeration will find a path from the initial cell to the final one, or the next step from any cell generated in the path will be impossible.
The shortest path is restored in the opposite direction: when selecting a cell from the finishing cell to the starting cell, at each step, a cell is selected that has an attribute of distance from the starting cell one less than the current cell. Obviously, this is the way to find the shortest path between a pair of given cells. There may be several routes with the minimum numerical path length, both when searching for a path in the vicinity of Moore and von Neumann. The choice of the final path in applications is dictated by other considerations outside this algorithm. For example, when routing printed circuit boards – the minimum linear length of the laid conductor.
Figures 2 – 3 show the steps of the wave algorithm on a graph.
Figure 2 – An example of using the algorithm
Figure 3 – An example of using the algorithm
2.3 Graphics engine
The graphics engine is responsible for the graphics in the game engine. The best definition of a graphics engine is found on wikipedia: A graphics engine is a middleware, a software engine whose main task is to render (render) 2D or 3D computer graphics [3].
Often the graphics engine is the most complex component of the game engine, so it quite claims to be the main component of the game engine. For this reason, graphics engines are rarely distributed separately on their own and are often included in some other product (game engine in particular). However, this rule does not apply to free software, created by enthusiasts who create free graphics engines, which can then be plugged as a module into your project like the rest of the components included in the game engine.
References
- Википедия. Компьютерная игра [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Компьютерная_игра
- Неигровой персонаж [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Неигровой_персонажа
- Википедия. Графический движок [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/...