=Paper= {{Paper |id=Vol-2147/p05 |storemode=property |title=Weight Based Algorithms to Increase the Playability in 2D Games |pdfUrl=https://ceur-ws.org/Vol-2147/p05.pdf |volume=Vol-2147 |authors=Alicja Winnicka,Karolina Kęsik,Kalina Serwat,Kamil Książek |dblpUrl=https://dblp.org/rec/conf/system/WinnickaKSK18 }} ==Weight Based Algorithms to Increase the Playability in 2D Games== https://ceur-ws.org/Vol-2147/p05.pdf

Weight Based Algorithms to Increase
the Playability in 2D Games
Alicja Winnicka, Karolina K˛esik,
Kalina Serwata and Kamil Ksia˛żek
Institute of Mathematics
Silesian University of Technology
Kaszubska 23, 44-100 Gliwice, Poland
Email: winnicka.alicja@10g.pl, karola.ksk@gmail.com
kalarcika@gmail.com, kamilksiazek95@gmail.com

Abstract—Increasing the level of playability in games depends are performed [8]. Subsequently, authorization of these data
on the engine’s operation. The more accurate and predictable is important, as can be seen from the number of publications
the game is, the greater the difficulty level will be. However, the and scientific papers in the field of biometrics [5], [11].
level of playability may decrease due to the player’s interest. To
prevent this, we propose a combination of different techniques Entertainment forces a rapid pace of development, which
for universal operation on various two-dimensional games. The can be seen after indicating new trends such as extended,
used methods have been modified in such a way to show that virtual or mixed realities. In [9], [13], the current open
hybrid forms can be much more advantageous. challenge in the field of games are described. In [4], monte
The proposition has been tested on selected games, and the
carlo tree search method with learning mechanism for video
obtained results were analyzed and discussed depending on
the introduced modifications. The aim of the discussion was game is presented. Authors of [14] discuss about the idea
to indicate the various advantages and disadvantages of these of reinforcement learning method for the use in multiplayer
techniques to increase the playability. nonzerosum games. Again in [7], some smart technique for
agents in game is described. Important part of artificial intelli-
I. I NTRODUCTION gence are neural networks, which also have found their place
The game development is dependent on graphics card in games [3].
producers and player requirements. The more efficient the In this paper, we propose a hybrid solution connected with
equipment will be available on the market, the more real and the classic techniques like q-learning, a* and tabu search. Our
complicated games should be. Particularly the second aspect is technique is based on the fitness function which depends on
important, because even the simplest game can attract human the selection of a specific metric.
attention. The problem is the lack of holding this attention. To
remedy this, games use more and more new algorithms that II. S IMPLIFIED A* WITH TABU TABLE
allow a computer counterattack during the game. However, the
perfect operation of the algorithm can cause the player will Proposed algorithm is based on path search algorithms.
not have the slightest chance of winning, which will cause the However it does not check whole path to the target, but only
game to quickly be forgotten. This lack of interest should be the value of points, which are the neighbours of chasing player
prevented by the addition of a certain, preferably controlled (or enemy, depending on the point of view). Firstly, it needs
randomness in his movements. to find all possible fields on the board that can be visited.
Particularly the development of artificial intelligence tech- After this action, it is necessary to compute the value of each
niques finds its applications in the various aspects of our field Θ(·). The evaluation is made according to the following
lives, not only in entertainment, which games are an example. formula
Decision support systems are the most known application Θ(A, B) = d(A, B) + wij , (1)
of these techniques. One such example is medicine, where
computer can confirm or even detect some diseases based on where A and B are the points in two-dimensional space under-
a given samples of X-RAY or CT images. Selected tools for stood as (xA , yA ) and (xB , yB ). First point is the possible next
that problems can be heuristic algorithms, what is presented field of chasing player and the second one is the localization of
in [15]. Another example are energy networks [1], [2], [10]. target. Function Θ(·) is the sum of two components, the value
Along with the rapid development of artificial intelligence, of the field calculated as a specific metric and the weight wij ,
other branches also sharply advance. This is especially vis- where i and j are given positions on the board. The weight is
ible in databases and warehousing because more and more selected in random way in the range [−1, 1]. Let us assume
information needs to be stored, where specific queries or sorts that d is such a function that

25
(c) A table which was used to create two
(a) The pacman game simple games.
(b) A console game
Figure 1: Visualisation of the game areas.

where X is non-empty set. d is called a metric. For any two assigned to each empty field at the position (i, j). Additionally,
points A, B ∈ X, the function must satisfy the following player will be marked as 10 and the enemies (moved by the
properties: computer) as 20. Visualization of such a board is shown on
1) distance between two points is equal to 0 if and only if Fig. 1.
points have the same coordinates The player moves towards the user by selecting the field,
in which a value of the fitness function Θ described by Eq.
d(A, B) = 0 ⇐⇒ A = B, (3) (1) is the smallest. However, it is possible a situation where
2) symmetry rule − a distance between A and B is the the algorithm gets stuck. An example of such a setting is a
same like a distance between B and A corner, where a character on three sides has a wall (further
walk is prevented). Starting from this position, there is a very
d(A, B) = d(B, A), (4) high probability of returning to the same field. In order to
avoid described situation, we introduce a tabu table, where
3) triangle inequality − a distance between A and B is less
movements that were made and did not bring any benefits
or equal the sum of distances between A and C (C is
(i.e. preventing further walk in the direction of a user) are
an intermediate point) and between C and B
saved. The proposed algorithm is presented in Alg. 1.
d(A, B) ≤ d(A, C) + d(C, B). (5)
III. E XPERIMENTS
The most known metric is the Euclidean one defined as: The proposed solution has been implemented in C# and
v
u n
uX tested in terms of the number of won games, the number
dE (A, B) = t (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.
In addition, all tests were carried out depending on the number
where n is the number of coordinates of points. Another
of fields on the board, the amount of obstacles or even the
example is the taxicab metric (called also the Manhattan
points which must be collected by the player. As points, we
metric), defined as follows:
mean in the case of the console the symbols ’#’, and in the
dM (A, B) = max |xi − yi |. (7) case of pacman – dots.
i=1,...,n
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
subsequent steps 20 fields were added (up to 760). In each
dR (A, B) = dE (A, C1 ) + dE (C1 , C2 ) + dE (C2 , B), (8)
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

26
Figure 2: Graph of the average number of moves needed by the algorithm to catch a player on a board of 400 + 20 · n fields
(where n is the value on the X-axis).

Algorithm 1 Weight-based algorithm for choosing the next
movement.
1: Start.
2: Define all the possible movements in dependence of
player’s position.
3: Select randomly one direction.
4: Calculate a value of the fitness function for selected
direction by using Eq. (1) and mark this value as α.
5: Create empty tabu table.
6: for each possible movements do
7: Calculate a value of the fitness function f according to
Eq. (1).
8: if f < α then
9: if move is not in tabu table then
10: Change the direction.
11: α = f.
12: end if
13: k = 0.
14: for each neighbour do
15: if a movement in the direction of this neighbour is Figure 3: Percentage variety of wins in 100 games played on
forbidden then the board with 400 fields and 50 randomly located points to
16: k + +. gain.
17: end if
18: end for
19: if k = 3 then Fig. 3, the average number of wins during 100 experiments
20: Add this movement to tabu table. is presented. The most effective was the proposed algorithm
21: end if with the jungle river metric. This combination was the most
22: end if succesful during 32% out of the total number of games. The
23: end for Manhattan metric was slightly less effective (the winner of
24: Return the best movement in the indicated direction. 26% games). What is interesting, the weakest results out of
25: Stop. 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.

27
Figure 4: Example of player movements – the green line is a trace of movements made by the user, and the red one – by the
proposed algorithm by using the Euclidean metric.

28
The number of calculations is small in comparison to other [8] Z. Marszałek. Performance tests on merge sort and recursive merge sort
graphic algorithms which have to search the entire board. for big data processing. Technical Sciences, 21(1):19–35, 2018.
[9] F. Milani, A. C. B. De Marchi, and R. Rieder. Usability guidelines to
Only the position of the player is the necessary knowledge develop gesture-based serious games for health: A systematic review. In
for applying of this technique. The path to the given object Virtual and Augmented Reality (SVR), 2017 19th Symposium on, pages
is determined by a dedicated function. In addition, various 188–194. IEEE, 2017.
[10] E. Okewu, S. Misra, R. Maskeliūnas, R. Damaševičius, and
metrics have different effectiveness, so it allows us to propose L. Fernandez-Sanz. Optimizing green computing awareness for environ-
a game with varied difficulty level by application of a specific mental sustainability and economic security as a stochastic optimization
metric. This type of distinction not only diversifies the game, problem. Sustainability, 9(10):1857, 2017.
[11] D. Połap. Extraction of specific data from a sound sample by removing
but also does not allow the player to adapt to one level of additional distortion. In Computer Science and Information Systems
computer intelligence. (FedCSIS), 2017 Federated Conference on, pages 353–356. IEEE, 2017.
[12] D. Połap, M. Woźniak, C. Napoli, and E. Tramontana. Real-time cloud-
IV. C ONCLUSIONS based game management system via cuckoo search algorithm. Interna-
tional Journal of Electronics and Telecommunications, 61(4):333–338,
A hybrid solution based on known algorithms has been 2015.
shown in this paper. Three different metrics were selected: [13] S. Risi and J. Togelius. Neuroevolution in games: State of the art and
the jungle river, the Manhattan and the Euclidean, which were open challenges. IEEE Transactions on Computational Intelligence and
AI in Games, 9(1):25–41, 2017.
used interchangeably in the assessment of possible movements [14] R. Song, F. L. Lewis, and Q. Wei. Off-policy integral reinforcement
to be performed by a computer-controlled player. The obtained learning method to solve nonlinear continuous-time multiplayer nonzero-
results showed that this type of solution has the right to be used sum games. IEEE transactions on neural networks and learning systems,
28(3):704–713, 2017.
as a computational intelligence. Especially, if the difficulty [15] M. Woźniak and D. Połap. Bio-inspired methods modeled for respiratory
level of the game would be understood as applying a different disease detection from medical images. Swarm and Evolutionary
metric. Measurements for each of presented metrics showed Computation, 2018.
[16] M. Woźniak, D. Połap, M. Gabryel, R. K. Nowicki, C. Napoli, and
that the method’s effectiveness depends on the right choice E. Tramontana. Can we process 2d images using artificial bee colony? In
of them. In addition, they are stable in terms of growth of International Conference on Artificial Intelligence and Soft Computing,
the calculation, which increases slightly when the size of the pages 660–671. Springer, 2015.
[17] M. Woźniak, D. Połap, C. Napoli, and E. Tramontana. Application
board grows. of bio-inspired methods in distributed gaming systems. Information
During further research it is possible to apply other, less Technology And Control, 46(1):150–164.
known metrics or use described model in other, a bit more [18] M. Wózniak, D. Połap, R. K. Nowicki, C. Napoli, G. Pappalardo, and
E. Tramontana. Novel approach toward medical signals classifier. In
complicated games and check efficiency of the method. Mea- International Joint Conference on Neural Networks (IJCNN), pages 1–
surements prove that such approach can be successfully im- 7. IEEE, 2015.
plemented 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.
R EFERENCES
[1] G. Capizzi, G. L. Sciuto, C. Napoli, and E. Tramontana. Advanced and
adaptive dispatch for smart grids by means of predictive models. IEEE
Transactions on Smart Grid, 2017.
[2] G. Capizzi, G. L. Sciuto, C. Napoli, and E. Tramontana. An advanced
neural network based solution to enforce dispatch continuity in smart
grids. Applied Soft Computing, 62:768–775, 2018.
[3] A. Dobrovsky, C. W. Wilczak, P. Hahn, M. Hofmann, and U. M.
Borghoff. Deep reinforcement learning in serious games: Analysis and
design of deep neural network architectures. In International Conference
on Computer Aided Systems Theory, pages 314–321. Springer, 2017.
[4] E. Ilhan and A. Ş. Etaner-Uyar. Monte carlo tree search with temporal-
difference learning for general video game playing. In Computational
Intelligence and Games (CIG), 2017 IEEE Conference on, pages 317–
324. IEEE, 2017.
[5] J. Kapočiūtė-Dzikienė, A. Venčkauskas, and R. Damaševičius. A com-
parison of authorship attribution approaches applied on the lithuanian
language. In Computer Science and Information Systems (FedCSIS),
2017 Federated Conference on, pages 347–351. IEEE, 2017.
[6] T. Kapuściński, R. K. Nowicki, and C. Napoli. Comparison of effective-
ness of multi-objective genetic algorithms in optimization of invertible
s-boxes. In International Conference on Artificial Intelligence and Soft
Computing, pages 466–476. Springer, 2017.
[7] A. Khalifa, M. Preuss, and J. Togelius. Multi-objective adaptation of
a parameterized gvgai agent towards several games. In International
Conference on Evolutionary Multi-Criterion Optimization, pages 359–
374. Springer, 2017.