-Increasing the level of playability in games depends on the engine's operation. The more accurate and predictable the game is, the greater the difficulty level will be. However, the level of playability may decrease due to the player's interest. To prevent this, we propose a combination of different techniques for universal operation on various two-dimensional games. The used methods have been modified in such a way to show that hybrid forms can be much more advantageous. The proposition has been tested on selected games, and the obtained results were analyzed and discussed depending on the introduced modifications. The aim of the discussion was to indicate the various advantages and disadvantages of these techniques to increase the playability.
The game development is dependent on graphics card producers and player requirements. The more efficient the equipment will be available on the market, the more real and complicated games should be. Particularly the second aspect is important, because even the simplest game can attract human attention. The problem is the lack of holding this attention. To remedy this, games use more and more new algorithms that allow a computer counterattack during the game. However, the perfect operation of the algorithm can cause the player will not have the slightest chance of winning, which will cause the game to quickly be forgotten. This lack of interest should be prevented by the addition of a certain, preferably controlled randomness in his movements.
Particularly the development of artificial intelligence
techniques finds its applications in the various aspects of our
lives, not only in entertainment, which games are an example.
Decision support systems are the most known application
of these techniques. One such example is medicine, where
computer can confirm or even detect some diseases based on
a given samples of X-RAY or CT images. Selected tools for
that problems can be heuristic algorithms, what is presented
in [
Entertainment forces a rapid pace of development, which
can be seen after indicating new trends such as extended,
virtual or mixed realities. In [
In this paper, we propose a hybrid solution connected with the classic techniques like q-learning, a* and tabu search. Our technique is based on the fitness function which depends on the selection of a specific metric.
Proposed algorithm is based on path search algorithms. However it does not check whole path to the target, but only the value of points, which are the neighbours of chasing player (or enemy, depending on the point of view). Firstly, it needs to find all possible fields on the board that can be visited. After this action, it is necessary to compute the value of each field ( ). The evaluation is made according to the following formula (A; B) = d(A; B) + wij ; (1) where A and B are the points in two-dimensional space understood as (xA; yA) and (xB; yB). First point is the possible next field of chasing player and the second one is the localization of target. Function ( ) is the sum of two components, the value of the field calculated as a specific metric and the weight wij , where i and j are given positions on the board. The weight is selected in random way in the range [ 1; 1]. Let us assume that d is such a function that d : X
X ! [0; 1]; (2) (a) The pacman game (b) A console game where X is non-empty set. d is called a metric. For any two points A; B 2 X, the function must satisfy the following properties: 1) distance between two points is equal to 0 if and only if points have the same coordinates d(A; B) = 0 ()
A = B; d(A; B) = d(B; A); (3) (4) 2) symmetry rule a distance between A and B is the same like a distance between B and A 3) triangle inequality a distance between A and B is less or equal the sum of distances between A and C (C is an intermediate point) and between C and B d(A; B) d(A; C) + d(C; B): (5) assigned to each empty field at the position (i; j). Additionally, player will be marked as 10 and the enemies (moved by the computer) as 20. Visualization of such a board is shown on Fig. 1.
The player moves towards the user by selecting the field, in which a value of the fitness function described by Eq. (1) is the smallest. However, it is possible a situation where the algorithm gets stuck. An example of such a setting is a corner, where a character on three sides has a wall (further walk is prevented). Starting from this position, there is a very high probability of returning to the same field. In order to avoid described situation, we introduce a tabu table, where movements that were made and did not bring any benefits (i.e. preventing further walk in the direction of a user) are saved. The proposed algorithm is presented in Alg. 1.
The most known metric is the Euclidean one defined as:
The proposed solution has been implemented in C# and vu n tested in terms of the number of won games, the number dE (A; B) = tuX(xi yi)2; (6) of necessary moves that the algorithm needs to caught the i=1 player, and various metrics which have been described earlier. where n is the number of coordinates of points. Another In addition, all tests were carried out depending on the number example is the taxicab metric (called also the Manhattan of fields on the board, the amount of obstacles or even the metric), defined as follows: points which must be collected by the player. As points, we mean in the case of the console the symbols ’#’, and in the dM (A; B) = i=m1;a::x:;n jxi yij: (7) case of pacman – dots.
In Fig. 2 is shown how the average number of moves The last presented case is the jungle river metric understood performed by the algorithm increases depending on the size as of the board. The initial size of board was 400 and during dR(A; B) = dE (A; C1) + dE (C1; C2) + dE (C2; B); (8) subsequent steps 20 fields were added (up to 760). In each case the growth of moves was linear (what is shown thanks to where C1 and C2 are orthogonal projections of A and B, linear regression). However, the slope of the line is relatively respectively, on the line r (r is called a river). small, which indicates the advantage of the proposed solution.
Each game takes place in a certain area or board. Let us Even in case of a large board, presented method was effective. assume that the board size is w h. In the case when all In addition, almost perfect linear growth in the average number fields are empty, and the computer players are approaching of movements was obtained for the jungle river metric. A to the user, the game would be too simple. It is necessary to bit worse results were achieved for the Manhattan metric put some obstacles on the board, what will be marked as a and the worst metric was the Euclidean one. This is caused large number, for example 100. A random value wij will be by randomly located obstacles at the game board. Again in
Fig. 3, the average number of wins during 100 experiments is presented. The most effective was the proposed algorithm with the jungle river metric. This combination was the most succesful during 32% out of the total number of games. The Manhattan metric was slightly less effective (the winner of 26% games). What is interesting, the weakest results out of presented metrics were achieved by the Euclidean one (24 %).
The smallest number of victories had a player – only 18%. It can be concluded that beating the algorithm was not easy but still possible.
The number of calculations is small in comparison to other graphic algorithms which have to search the entire board.
Only the position of the player is the necessary knowledge for applying of this technique. The path to the given object is determined by a dedicated function. In addition, various metrics have different effectiveness, so it allows us to propose a game with varied difficulty level by application of a specific metric. This type of distinction not only diversifies the game, but also does not allow the player to adapt to one level of computer intelligence.
A hybrid solution based on known algorithms has been shown in this paper. Three different metrics were selected: the jungle river, the Manhattan and the Euclidean, which were used interchangeably in the assessment of possible movements to be performed by a computer-controlled player. The obtained results showed that this type of solution has the right to be used as a computational intelligence. Especially, if the difficulty level of the game would be understood as applying a different metric. Measurements for each of presented metrics showed that the method’s effectiveness depends on the right choice of them. In addition, they are stable in terms of growth of the calculation, which increases slightly when the size of the board grows.
During further research it is possible to apply other, less known metrics or use described model in other, a bit more complicated games and check efficiency of the method. Measurements prove that such approach can be successfully implemented in similar types of games.
The algorithm can be used in different games when player need to catch moving element in the game, which doesn’t need to be player. This model of playing can be applied in most arcade games and many another ones. Presented ideas has a wide range of applications in this brand of science.