AI monsters and finding the way with heatmaps

Suppose we have a flat map consisting of tiles. On some tiles there are monsters, and on some others - all sorts of things that monsters are interested in: a player, weapons, potions, ammunition, etc. in the same spirit. The task is to explain the monsters, to what things they go and how. The path should be close to optimal, and the computation time as short as possible. One of the easiest ways is to use a heat map of distances to a specific goal or targets.

Disclaimer

I will say right away that this is a fairly well-known method: it was used for AI opponents in games (for example, brogue ), for RTS bots and for the movement of particles , and much more. Below I will discuss the bagel, that is, I admit that the world consists of discrete square tiles and each object is located at least on one of them, [although in principle the same can be done with any topology of the world that is isomorphic to a (connected) graph. Images borrowed from this article on roguebasin.com

Zombie

To explain how heat maps work, I will first create the simplest possible monster - a zombie. He should just chase the player, not being distracted by the rest of the world, and being close by - throwing melee. Life will also be simplified for us by the fact that in roguelikas the melee attack and movement are traditionally performed by one team, so in fact the zombie does exactly one thing: rushing along the shortest path towards the player. All AI, respectively, comes down to finding this very shortcut.

To find the path, we need a two-dimensional array the size of a map, each cell of which contains the distance from this tile to the player. Let the value in the tile in which the player is located is zero; in adjacent tiles it is equal to one, in the next row of two, and so on. In general, the value of a tile is one greater than the smallest value among its neighbors. Impassable tiles are ignored, that is, None or any prohibitively large number is put there. It should look like this:
')

Now, a zombie is enough to find out the values ​​of neighboring tiles on each turn, choose the smallest of them and step in the appropriate direction. If another zombie is already standing there or something else is stopping you from entering, take the option a little worse and so on, as long as there are tiles with a value no greater than the current one. If there are several equally good options, choose randomly. In general, everything. Zombies are confidently moving towards the player, undermining on mines and substituting under fire, as they should according to the laws of the genre. Here , by the way, is an interactive demo on HaxeFlixel.


The first advantage of this method is obvious: it is fast. When going around wide, the complexity of conversion is at best linear with the map area. In practice, most of the player’s moves either do not change the card at all (if it stands in one place), or only affects the adjacent cells. The time that the zombies themselves spend on choosing a move is negligible. From this, by the way, the second advantage follows: as many zombies can use the same card, that is, increasing the number of monsters almost does not increase the time spent on the move. No matter, one zombie on the screen or a thousand - they will still navigate for about the same time.

Multiple attractors

To demonstrate a little more complex behavior, you can create a goblin. He has two goals in life: to attack a player, like a zombie, and collect gold. Accordingly, at the beginning of the calculation of the card, we not only put a zero under the player, but also indicate some value under each tile on which at least one coin lies. Distances are calculated in the same way as in the previous example. The picture below shows the value -4 for gold, that is, the goblin is ready to go for gold a little further than the chance to turn into ten units of exp.


An obvious problem arises: what if you add both zombies and goblins to one game? They have different behaviors and can no longer use the same card. And if you have a heat map for each type of AI, the speed advantage can quickly disappear. The solution is to create a map for each type of attractor . Each AI will then take values ​​from all its cards of interest and choose the next step based on the weighted amount. How are “Player Card”, “Card with Gold” and “Card with Arrows” faster than “Map for Zombies”, “Map for Goblins” and “Map for Centaurs”? It's all about the frequency of calculation. The map needs to be updated only when its attractors change. As a rule, the player either moves, or picks up gold from the floor, or shoots a monster, but not all at the same time. That is, only one card is usually updated per turn, and in the case of separate cards with AI, you would have to recount everything at once.

Expanding AI

The goblin needs to think about another problem that the zombies didn't care about. The implication is that he wants to collect gold, but the heat map can only order him to approach him. Fortunately, artificial intelligence is not limited to just one card. Checking the direction of movement occurs after the monster has found out that in the current location, he actually has nothing to do. You can increase the speed by checking the possibility of other actions only in the local minima of the map, but this is usually premature optimization: many cells on which the monster actually has something to do with are not local minima.

Another disadvantage of the implementation described is that the zombie will beat against the player, even if he has 1 HP left, and the goblin dying of hunger will not stop collecting gold. Okay, for these two creatures, this is most likely the norm, but generally the monster should have several types of behavior depending on the circumstances. As usual, the state machine will help us here. The feature in the case of heatmaps is only in the fact that for each state of the automaton a different weight vector of the maps is set. A heavily wounded opponent will most likely retreat from the player, that is, multiply the value from the corresponding card by something negative, but run off to the nearest healer, giving great weight to the value from the potions card. A hungry person will in the same way strive for food, try not to be caught by the player and completely ignore the ammunition lying on the floor.

Underwater rocks

I personally found three of them. First, there may be more than one path from point A to point B. For AI, this is not a problem: monsters reaching the player in different ways, poke a little less into the eyes of the determinism of their behavior and even look a little smarter than they really are. But the article on roguebasin suggests using the same maps to show the path from the player to the cursor when navigating with the mouse or shooting. This is a very bad idea: the path that is thus displayed on the screen may be optimal, but it does not have to coincide with the path that the character goes to the same point. For shooting or spells, this problem is even more serious, because maps do not prohibit bypassing corners and moving along a curve (if the topology of the map allows). And only a mortar from a famous anecdote should fire around the corner.

Secondly, this method ignores the field of view of monsters. A zombie is fully capable of chasing a player through half cards, even if he has never seen him and should not even be aware of his existence. It can be assumed that if a player sees a monster, then the monster sees him too (adjusted for secrecy). Then the heat map is updated only within the field of view of the player and tiles outside of its limits are ignored just as impassable. This is a crutch, but, alas, an honest field of view for all the NPCs on the knee is not short.

Thirdly, each opponent acts on its own. By creating a map with monsters as attractors, you can set behaviors like “Get together” or “Follow the leader”, but the complex tactical interaction of monsters also requires more serious work on artificial intelligence.

Conclusion

So from the matches and acorns you can collect a good artificial intelligence. It will not be brilliant, but with a successful balancing of the scales of the cards and a well-tuned state machine, the opponents look much smarter than they really are.

PS: This method turns out to be called a Lee algorithm. Thank you Shtucer for the amendment.