Using AI and Utilities when Developing Tower Defense Games
This article continues the theme of the application of mathematical modeling in the development of games in the genre TD. In the previous articles , the basic parameters of the main objects of the game — creeps and towers — were considered, and their dependence on the round time and the size of the map, as well as the principles of constructing an in-game economy that would not introduce imbalances at certain stages of the game.
Further development of this topic suggests itself: if the basic algorithms are known that allow you to set the boundary limits of the game parameters, then the same algorithms can be used to create an AI that would allow at least partially replace the player and check the gameplay "live".
The topic of creating player-imitation bots for single-player games has repeatedly surfaced on Habré, but, as a rule, they were created either for "sports interest" or for the purpose of "spinning" parameters in those games where monotonous actions are required. However, AI can be useful in the development of the game, which will be the first part of this article.
')
To begin with, we will decide what the AI ​​might be needed for in the Tower Defense (TD) genre game.
First of all, the bot was necessary for superficial assessment of levels, especially for checking geometry. Since we have a free field in the game (free building), then with the help of a bot it was possible to quickly check how the graph of enemy paths would change with different types of building.
Secondly, in the process of creating a bot, a very useful function was introduced into the game (its debug version) - the fastest possible “acceleration” of the creep wave run, without drawing graphics, only with the game mechanics. This allowed us to quickly check the work of the bot, as well as to debug the balance of individual waves for each of the field configurations (and for different methods of placing the towers on the field). This method was necessary to test "in practice" the applicability of towers of various kinds in different situations. It allows you to “lose” a lot of different cards in a short time, which makes it possible to collect statistics that will show how mathematically verified the data coincide with the real state of affairs.
If we talk about the principle of the bot, it had the following algorithm (the items also show the evolution of the creation of the bot, its different iterations):
1. The bot is constantly running and can perform an action at any time - both in anticipation of a wave of enemies, and when enemies move across the field.
2. Each time the paths of all creep waves are calculated. Note that in the same wave there can be several groups of enemies leaving different points.
3. Each cell of the field is assigned its own "weight" depending on how many creep teams passes through it. It is understood that the bot counts 1 wave ahead, and knows from what points the creeps will go.
4. Also, a bot can be made more “smart” by adding knowledge of how many and what creeps will come from which point, at what interval, etc., that is, data on the “power” of each of the following waves / subwaves.
5. The "weight" of each of the subsequent waves was calculated based on how soon it will begin. That is, the bot could easily look as rude at "1 step forward", and immediately act "strategically". The sum of the values ​​for each cell for each of the waves was added, so in the end it turned out that each cell of the field has one value - its “weight”. Of course, this matrix of coefficients changes depending on the number of remaining waves: the waves that have already passed (the paths of their creeps) are no longer taken into account in the "weights map".
6. Depending on which cell has the greatest “weight”, a tower is placed at this point.
7. In the first iteration, the logic of the bot on the profile of the economy was the simplest: as soon as there is enough money for the tower, it is bought. At first, only 1 tower was used, since the main task was to check the level geometry during development.
8. Since the installation of the tower in some tiles can change the trajectory of the creeps, in the second iteration a miscalculation of the field and the behavior of opponents was added 1 turn ahead. Thus, for each of the places, it was checked what would happen if you put a tower at this point, if the trajectory of the enemy's movement changed, and if so, how much damage would they all previously installed towers (and not just the tower put up last). Without this opportunity, it has repeatedly happened that installing a tower in a seemingly perfect place makes the other towers useless, as the creeps begin to move around the rest of the artillery.
9. Further development of the bot - use the upgrade tower. Again, it looks for 1 move ahead, which will be more profitable - upgrade one of the towers (first choose the tower that deals the most damage, in the second iteration all towers began to move, as the radius of the tower increased with the upgrade, which means damage could change nonlinearly), or put another one. Of course, the difference in damage was normalized to the price of the action.
10. Next, you need to teach the bot to sell unused towers. This was applied if the bot “knew” that the tower in place X on the next wave would not be involved. This was calculated similarly to the principle of choosing the place of construction of the tower, only with the opposite sign. It is important to bear in mind that the sale of the tower returned only 50% of its value. Therefore, it is worth selling the tower if there is a place on the map where the installed tower will cause 2 times more damage than the tower in the current place (to compensate for the losses on sale).
However, the further development of the bot (so that it could use other towers, bonuses, competently counteract opponents with unique abilities) was considered impractical, but some parts of this utility found their application in a completely different field: recording and viewing game replays.
Moreover, as a result of comparing the logic of a bot and a person on the same cards, it turned out that the bot shows itself well where it comes to geometry, but the actions associated with upgrading and selling towers are usually better done by humans. Based on this, the following items were derived, in which AI showed itself very well:
1. Check how easy the level we pass exclusively base towers.
2. Check whether the geometry is correct, whether there is an imbalance in building on one of the waves - in fact, it was checked how much at the level of convenient points for placing towers, whether the player’s choice of places to build towers remains at least towards the middle of the level.
3. To check whether we are passing the level at all on the first waves, thanks to the bot, it was possible to calculate an adequate balance of starting funds.
In fact, AI fulfilled its mission: it helped filter out failed cards, thereby making it clear to the game designer what types of level geometry can be acceptable with this balance of towers and opponents.
However, the use of the AI ​​module was relevant in the future, namely: for the part of the code that would allow to imitate the player’s single actions - building towers, upgrading, selling, speeding up playing time, etc.
All this was useful for recording (and further viewing) replays from other testers, when the design vector itself was selected and required tuning of the difficulty and interestingness of the levels conducted on live players. In fact, the source that gives solutions has simply changed - AI used to do this before, but now the entire sequence of actions was read from the log file.
Logging and viewing logs
In each game session, the following actions were recorded:
1. Start / end of the game session,
2. Turn on / off pause,
3. Change the speed of the game,
4. Early wave call
5. Installing tower X in the coordinates of the battery,
6. Upgrade of the tower in place X,
7. Sale of the tower in place X,
8. To control - loss of life cup,
9. To control - win / lose level,
10. To control - the fact of the killing of the last creep in the wave (the creep coordinates are written).
Example log
level3.lvl start; 03/22/2012 19:39:12;
level3.lvl; 6.41; build; active_tower; 5.1; 250;
level3.lvl; 10.25; build; active_tower; 9.1; 190;
level3.lvl; 12.16; upgrade; 5.1; 130;
level3.lvl; 13.86; upgrade; 9.1; 80;
level3.lvl; 35.68; killlast; wave1; 7.0; 6;
level3.lvl; 60.76; killlast; wave2; 7.0; ten;
level3.lvl; 85.97; build; splash_tower; 11.0; 190;
level3.lvl; 88.44; lifelose; wave3; 56;
level3.lvl; 88.98; lifelose; wave3; 56;
level3.lvl; 99.08; killlast; wave3; 7.0; 6;
For each event, the game time is written, the time does not depend on the speed of the game, that is, it may differ from the real one.
Thus, it is possible to view both the actions of the player and the state of the game. This can be important for “synchronizing” gameplay when launching a replay.
For example, if in the replay the last wave creep was not killed, and in the logs it is marked that he died, then to save synchronization it is better to destroy this creep artificially.
Recording game time allows you to calculate how quickly a player reacts to the appearance of a “stimulus” (a new wave of enemies).
The replay files were automatically recorded in the file system of the phone, then removed and played in the desktop version of the game. The game is written in Unity, so the game could be launched in the editor in the same way as on a mobile device. Of course, we took advantage of this when playing replays.
Also on the actions of the player, you can see where the game has a "sagging" action-component.
This “map” allows you to identify the weak points of the level without having to analyze a lot of individual replays, and a visual display allows you to better “superimpose” the log data on the game level itself.
Thus, this technique was useful at different stages of the project: both in playtest, where it is important to see the behavior of each of the testers, including the player’s “evolution” during the course of the game, and at a later stage, when it was necessary to analyze many passages.
Further development of this topic suggests itself: if the basic algorithms are known that allow you to set the boundary limits of the game parameters, then the same algorithms can be used to create an AI that would allow at least partially replace the player and check the gameplay "live".
The topic of creating player-imitation bots for single-player games has repeatedly surfaced on Habré, but, as a rule, they were created either for "sports interest" or for the purpose of "spinning" parameters in those games where monotonous actions are required. However, AI can be useful in the development of the game, which will be the first part of this article.
')
To begin with, we will decide what the AI ​​might be needed for in the Tower Defense (TD) genre game.
First of all, the bot was necessary for superficial assessment of levels, especially for checking geometry. Since we have a free field in the game (free building), then with the help of a bot it was possible to quickly check how the graph of enemy paths would change with different types of building.
Secondly, in the process of creating a bot, a very useful function was introduced into the game (its debug version) - the fastest possible “acceleration” of the creep wave run, without drawing graphics, only with the game mechanics. This allowed us to quickly check the work of the bot, as well as to debug the balance of individual waves for each of the field configurations (and for different methods of placing the towers on the field). This method was necessary to test "in practice" the applicability of towers of various kinds in different situations. It allows you to “lose” a lot of different cards in a short time, which makes it possible to collect statistics that will show how mathematically verified the data coincide with the real state of affairs.
If we talk about the principle of the bot, it had the following algorithm (the items also show the evolution of the creation of the bot, its different iterations):
1. The bot is constantly running and can perform an action at any time - both in anticipation of a wave of enemies, and when enemies move across the field.
2. Each time the paths of all creep waves are calculated. Note that in the same wave there can be several groups of enemies leaving different points.
3. Each cell of the field is assigned its own "weight" depending on how many creep teams passes through it. It is understood that the bot counts 1 wave ahead, and knows from what points the creeps will go.
4. Also, a bot can be made more “smart” by adding knowledge of how many and what creeps will come from which point, at what interval, etc., that is, data on the “power” of each of the following waves / subwaves.
5. The "weight" of each of the subsequent waves was calculated based on how soon it will begin. That is, the bot could easily look as rude at "1 step forward", and immediately act "strategically". The sum of the values ​​for each cell for each of the waves was added, so in the end it turned out that each cell of the field has one value - its “weight”. Of course, this matrix of coefficients changes depending on the number of remaining waves: the waves that have already passed (the paths of their creeps) are no longer taken into account in the "weights map".
6. Depending on which cell has the greatest “weight”, a tower is placed at this point.
7. In the first iteration, the logic of the bot on the profile of the economy was the simplest: as soon as there is enough money for the tower, it is bought. At first, only 1 tower was used, since the main task was to check the level geometry during development.
8. Since the installation of the tower in some tiles can change the trajectory of the creeps, in the second iteration a miscalculation of the field and the behavior of opponents was added 1 turn ahead. Thus, for each of the places, it was checked what would happen if you put a tower at this point, if the trajectory of the enemy's movement changed, and if so, how much damage would they all previously installed towers (and not just the tower put up last). Without this opportunity, it has repeatedly happened that installing a tower in a seemingly perfect place makes the other towers useless, as the creeps begin to move around the rest of the artillery.
9. Further development of the bot - use the upgrade tower. Again, it looks for 1 move ahead, which will be more profitable - upgrade one of the towers (first choose the tower that deals the most damage, in the second iteration all towers began to move, as the radius of the tower increased with the upgrade, which means damage could change nonlinearly), or put another one. Of course, the difference in damage was normalized to the price of the action.
10. Next, you need to teach the bot to sell unused towers. This was applied if the bot “knew” that the tower in place X on the next wave would not be involved. This was calculated similarly to the principle of choosing the place of construction of the tower, only with the opposite sign. It is important to bear in mind that the sale of the tower returned only 50% of its value. Therefore, it is worth selling the tower if there is a place on the map where the installed tower will cause 2 times more damage than the tower in the current place (to compensate for the losses on sale).
However, the further development of the bot (so that it could use other towers, bonuses, competently counteract opponents with unique abilities) was considered impractical, but some parts of this utility found their application in a completely different field: recording and viewing game replays.
Moreover, as a result of comparing the logic of a bot and a person on the same cards, it turned out that the bot shows itself well where it comes to geometry, but the actions associated with upgrading and selling towers are usually better done by humans. Based on this, the following items were derived, in which AI showed itself very well:
1. Check how easy the level we pass exclusively base towers.
2. Check whether the geometry is correct, whether there is an imbalance in building on one of the waves - in fact, it was checked how much at the level of convenient points for placing towers, whether the player’s choice of places to build towers remains at least towards the middle of the level.
3. To check whether we are passing the level at all on the first waves, thanks to the bot, it was possible to calculate an adequate balance of starting funds.
In fact, AI fulfilled its mission: it helped filter out failed cards, thereby making it clear to the game designer what types of level geometry can be acceptable with this balance of towers and opponents.
However, the use of the AI ​​module was relevant in the future, namely: for the part of the code that would allow to imitate the player’s single actions - building towers, upgrading, selling, speeding up playing time, etc.
All this was useful for recording (and further viewing) replays from other testers, when the design vector itself was selected and required tuning of the difficulty and interestingness of the levels conducted on live players. In fact, the source that gives solutions has simply changed - AI used to do this before, but now the entire sequence of actions was read from the log file.
Logging and viewing logs
In each game session, the following actions were recorded:
1. Start / end of the game session,
2. Turn on / off pause,
3. Change the speed of the game,
4. Early wave call
5. Installing tower X in the coordinates of the battery,
6. Upgrade of the tower in place X,
7. Sale of the tower in place X,
8. To control - loss of life cup,
9. To control - win / lose level,
10. To control - the fact of the killing of the last creep in the wave (the creep coordinates are written).
Example log
level3.lvl start; 03/22/2012 19:39:12;
level3.lvl; 6.41; build; active_tower; 5.1; 250;
level3.lvl; 10.25; build; active_tower; 9.1; 190;
level3.lvl; 12.16; upgrade; 5.1; 130;
level3.lvl; 13.86; upgrade; 9.1; 80;
level3.lvl; 35.68; killlast; wave1; 7.0; 6;
level3.lvl; 60.76; killlast; wave2; 7.0; ten;
level3.lvl; 85.97; build; splash_tower; 11.0; 190;
level3.lvl; 88.44; lifelose; wave3; 56;
level3.lvl; 88.98; lifelose; wave3; 56;
level3.lvl; 99.08; killlast; wave3; 7.0; 6;
For each event, the game time is written, the time does not depend on the speed of the game, that is, it may differ from the real one.
Thus, it is possible to view both the actions of the player and the state of the game. This can be important for “synchronizing” gameplay when launching a replay.
For example, if in the replay the last wave creep was not killed, and in the logs it is marked that he died, then to save synchronization it is better to destroy this creep artificially.
Recording game time allows you to calculate how quickly a player reacts to the appearance of a “stimulus” (a new wave of enemies).
The replay files were automatically recorded in the file system of the phone, then removed and played in the desktop version of the game. The game is written in Unity, so the game could be launched in the editor in the same way as on a mobile device. Of course, we took advantage of this when playing replays.
Also on the actions of the player, you can see where the game has a "sagging" action-component.
This “map” allows you to identify the weak points of the level without having to analyze a lot of individual replays, and a visual display allows you to better “superimpose” the log data on the game level itself.
Thus, this technique was useful at different stages of the project: both in playtest, where it is important to see the behavior of each of the testers, including the player’s “evolution” during the course of the game, and at a later stage, when it was necessary to analyze many passages.
Source: https://habr.com/ru/post/189198/
All Articles