A use case: soldiers attacking the player (iteration)

Okay, so with all this in place we can simulate an iteration. We start with updating the player's and the NPCs' positions. At first, the player is outside room and the NPCs are at their initial positions. So, assuming that there are game objects modelling the player and the NPCs, and that these objects implement GAI traits for creating, setting, and collecting data from cells, it should look like this:

GAI.cells.create(npc_1)
GAI.cells.create(npc_2)
if (player_entered_the_room) GAI.cells.create(player)
  // player_entered_the_room is a flag set externally - it's not used by GAI

Then we run GAI, just once:

GAI.run()

And then we collect the results and destroy the cells:

GAI.cells.get(npc_1)
GAI.cells.remove(npc_1)
GAI.cells.get(npc_2)
GAI.cells.remove(npc_2)
if (player_entered_the_room) {
  GAI.cells.get(player)
  GAI.cells.remove(player)
}

During the iteration functions "move_towards", "turn_towards", and "shoot" are called in parallel for each cell. Functions calculating lazy vals are called by them when needed. Note that it means some of the lazy vals might be calculated twice if two main functions call them in the same time. This is ok: we waste a bit of CPU time, but there is no race condition, and the results of both calls will be the same. Eventually the lazy vals could be synchronized: If one thread calculated the lazy val, the other waits for the result instead of doing the same.

If the player is not in the room, the NPCs will just stay at their initial positions. Lazy vals are not calculated and the iteration ends. The things start to get interesting when we add the player.

The player appears at the node_1 (Point2D(3,1)). The NPCs know she's there, but they don't see her, so they calculate the node where they have to go to be able to see her and shoot at her: node_2. They both want to tag it, calculate the path to it, and move towards the first node on the path. The problem is, they both chose the same node. Technically it's possible. They can both go there, stay next to each other (the game engine should prevent them from bumping into each other) and shoot. But we don't want that. If the player has a grenade, she could kill them both at once. Instead, we want only one of them to go to node 2, and the other to stay away.

The solution is simple: we rely on the fact that we process the cells sequentially, even if we don't care about the order (it's a bit different in the CUDA approach). Let's say npc_1 is processed first. It tags node 2 and moves towards it. When GAI later processes npc_2, it discovers that node_2 is already tagged. And it's the only valid node which it can fire at the player from, so withoutany other valid node, it just stays where it is.

But let's say in the next few seconds the player moves from node_1 to node_2. What happens then? At the beginnning of the iteration after it happened the position graph is updated: the player reference is moved to node_2, and then npc_1 is processed. It learns that the position of the player changed and node_2 is no longer available - we don't want the NPC to run into the player. But node_2 is unique in that it has three valid closest nodes: 1, 3, and 7. node_3 is now the closest valid node for npc_1. npc_1 removes its tag from node_2, tags node_3, recalculates the path and moves in that direction (it already started moving in that direction before, because node_3 lies on the path to node_2, so we can assume it's pretty close now). What's more, npc_2 discovers that now there is an untagged valid node where it can move: node_7. So it tags it and moves there. Ina few more seconds both npc_1 and npc_2 go around the wall, see the player, turn towards it, even though they're still moving towards their tagged positions, and start shooting.

Note that even if npc_2 initial position was next to npc_1, it wouldn't change its decision to move to node_7. If npc_1 is processed first, it will have a priority in tagging nodes, so first npc_2 will just have nothing to go, and then it will have to choose between node_1 and node_7, just as in our scenario. It might eventually choose node_1 - the programmer may either prevent it, by filtering out this node (or by adding a rule that passing the node with the player is forbidden), or let the NPC do it. I would let it as it is.

When the NPCs go around the wall (as drawn here), the player is able to shoot at them too. The player is probably much stronger than NPCs. They will start losing health quickly. When one of them is seriously wounded (health going below 50%) it will retreat to the nearest point where it is invisible to the player. It seems reasonable, since there is another NPC engaging the player, so she probably won't follow the wounded one. If the game allows NPCs to regain health it means that the wounded NPC will have some time to do it and then, when its health goes back above 50%, it will again decide to attack. If not, it will just wait behind the wall. If the player follows it, it will shoot at her the moment she is visible, and in the same time it will recalculate the next retreat node(again, a rule about not crossing the node with the player might help to make more natural decisions). Basically it means that the NPC will try to hide behind the wall and while doing it, it will constantly shoot at the player. Only when it runs out of ammo, the NPC will turn around and run.

Sounds pretty reasonable, right? ;) And all this is coded with just a handful of pretty simple functions described above. Some of them are generic enough that they can be put in a utility library and simply used by the programmer from there - they don't have to be written by hand every time. Also, if you make a game with more rooms and more NPCs, you can very easily reuse the functions you've written for this one scenario.