Baby steps to an Artificial Intelligence
8 comments since October 15, 2015
The line between enemy behavior and artificial intelligence is really thin and blurry, so for the sake of the article, lets define what I mean by “artificial intelligence” in the scope of this article.
Enemy behavior is when an enemy act in simple reaction patterns: I see the player, I shoot at him or I see the player and go towards him (no navigation included). Usually, an enemy behavior will have a predefined target, it will only evaluate its immediate surroundings and the target to see if it can react. To summarize; an enemy behavior ask the basic questions: Where’s my target? Can I reach it? Do I react? One question is about a position, the other two are yes or no questions.
In Toto Temple, an artificial intelligence will ask the basic questions: What’s my target? Where is it? Can I reach it? How do I reach it? What do I react to? How to react? Many open ended questions that need context, evaluation and comparing.
It’s dangerous to go alone, take these words.
AI is a rather complicated subject, it’s better to have some bases to begin with. So here are some words I’ll use that may or may not be familiar.
Many AI navigation systems are based on a node system. Nodes are like intersections and corners for roads, connecting to each other, together they create a network. They are used to draw a simple to follow, summarized map of the level for AIs.
A ray, just like a laser, that will return the first thing it hits from a given point to another.
Rendered image of the game, each refresh of the frame take a given time, usually 1/60th of a second, it gives 60 FPS or Frame Per Second. The script may be frame dependent, it means all the timings are done using a number of passing frames instead of fixed times, it is usually not recommended because if you wait for 60 frames, expecting to wait for a second, you may end up waiting for 2 if the game slows down to 30 FPS.
What’s my target? Where is it?
An AI will want to know where to go. To know where to go it needs a purpose. To know its purpose it needs a target. And to know its target it needs to know many things about all the possible targets. First thing to do is determine the absolute interest level of each asset in the level: bronze coins are worth 10 points of interest, silver 50, gold 155, the goat carrier is worth 300. To be sure the powerup is taken at some point, its interest is increased over time.
Of course, when you have the goat, you don’t want the same things as when you don’t have it, first you can’t dash, so you don’t really care about powerups. There are two stats for each thing: interestWithGoat and interestWithoutGoat. The interestWithGoat for every Toto that doesn’t have a goat is -300, which mean the carrier will try to avoid the other totos. Luckily, we only have two contexts: have, or don’t have the goat. If they had health, the interest for health assets would gradually become greater the less I have health, and the system would be way more complicated.
Now that I know the interest of each object, I need distance. The goat may be on the other side of the room, and there are some silver coins near me, so the distance affect the interest the toto-bot has for an asset. As the levels are quite open, a linear distance (without pathfinding) is enough to determine this kind of information.
So the interest modified with the distance, that’s it? Still not yet. Sometimes there are explosions of coins, and while each coin may not sound like much individually, a bunch of them could be worthwhile. Nodes are good for that, so I add the interest of each object to their connected node and distribute a fraction of this “node interest” to neighboring nodes, according to distance between the nodes. I then add the resulting node interest with a weight to each object that connect to the node.
And this is not all! When you are afflicted by the repulsive magnet, it is more intelligent to not get the coins in this context. So the AI know the nature of each asset, it will reduce its interest toward every coin.
Now we are good to go: interest of an object modified with the interest of the zone, the whole modified with the distance then the context, this is all a toto-bot needs to find its ultimate target. An AI like this will completely forget about its surrounding though, work is far from finished.
How do I reach it?
I know where I want to go, how do I get to it now? Nodes are here to help. To trace a path between the AI and the target, I first must connect them to a path. Each asset and AI connect to the nearest node that it can directly reach (with a raycast), making them part of the network.
Now that I have access to the whole path, I need to find it. Now it is time to scan the connections between the nodes, starting with the nearest one. As the levels have very little dead-ends and such, I can use some quirks to make the process faster. What I do is scan each connected node, calculate the angle they are with the current node, and find the node with the angle nearest the target’s. I then add the found node to the path, and scan the new node again, rinse and repeat until you reach the target.
Sometimes a path may loop unto itself or reach a dead-end, this means that the code failed, this happen quite often. So I need a backup plan: When such a thing happen I must review the path, and try to branch to the second best option I had found along the path, I do this with the third and fourth best options too to give me options, no need for a dead-end.
Once I have my 4 (or less) paths, I decide which one I want to take. To do that, I check the length and the added interest of all the nodes in each path. If a path is a little longer, but contain a gold coin, I prefer to go this way and grab the coin on the way.
Also, when the target is a toto, it takes into account the speeds and distance to go before reaching it, this way the bots won’t always follow the carrier, but will try to “anticipate” its movements, intercepting it.
Navigating the path
Now that I have my path, I must navigate it. I could make the bot just follow the path, but they’d look to be on rails and mechanical. Actually, when we first thought about bots, they’d be dummies that follow rails but it would be almost easier to make them feel natural anyway.
What I do is first check with a raycast which is the farthest node on the path that I can directly see, then get the line from that node to the next. I check with raycasts what is the farthest point on the line I can see. I set the point I’ve found with that as my immediate navigation goal, this give me the direction the bot goes right now. However, if it can directly see its target, it will bypass everything and simply go toward the goal.
Can I reach it?
Some assets will not be reachable for the moment for a bot. It happens that a coin find its way outside the level, if the asset can’t connect to a node because it can’t directly reach one, it is simply not part of the network, unreachable. If the asset is chosen as a target, no path will connect to it.
Sometimes, an AI is stuck in a trap, it means it can’t reach much. For that, nodes verify with their connected nodes with a raycast if there is a collision between them. If there is, the path is blocked. If no path connects to the target, you put the wanted target in the “can’t reach” category and try to reach another target the following frame. If no target is available, don’t do navigation but react to immediate environment.
What do I react to?
So I have an “immediate navigation goal”, but life is not always about navigation you know. Sometimes there are immediate threats or bonuses more important than navigating. For instance if there are a couple of coins in the area, maybe I’d want to make a quick turn to get them on the way.
But immediate reactions also mean trying to avoid the other totos when I have the goat. I verify every toto, try to get away from them, if the toto come too close I try to repel it with a shield. I will scan all the immediate assets and decide which one must retain my attention, and react to this asset. The system to go toward or try to avoid something is quite similar to a magnet/anti-magnet.
Changing your mind
Human mind is wonderful, it can create context from present and past to determine future, and you realize how powerful and convenient this all is when you try to make an elaborate enemy behavior or an AI.
Scenario: You need to get the milk, but you got to get around the table before, going left is just as long as going right. The choice is simple: who the hell cares? That’s trivial, just take a path. If you were a simple/bad AI, there are chances you would just be stuck there, as no context is given and you change your mind every frame.
To prevent this kind of thing to happen, we give a context: “You were aiming for that target using this path” every frame. In programming terms, you tell the AI that its current target and path have a bonus in its interest level each time a verification for target and path are made, so a target must be really worth it to make a toto-bot change its mind.
Without some kind of context system, a bot might decide to not block the enemy for whatever reason, but the next frame it completely forgot it decided so and pops the shield anyway. To counter it you could put the likeliness of shielding to very little chance and verify anyway each frame, but it is a pretty unsatisfying and fake approach. I prefer to keep the decision in a variable, and verify if I previously took this decision before trying to take the decision again. Of course the decision will be erased after some time or upon an event. The system really works like cooldowns.
How to react?
I already talked about popping the shield when an enemy is near, but in Toto Temple, you also interact with the temples: you dash into blocks to destroy them, you make lava bubbles burst to propel yourself or others, you travel through portals, and that’s not counting the interactions between players and powerups. Luckily totos don’t have many different “attacks”, so the choices and thus the decisions to make and all the code linked to that is pretty simple, usually it is about reacting or not, that’s it.
To interact with a bloc: if the bot want go toward it, dash into it. It gives some special and unnatural behaviors, but … yeah sorry.
With the lava bubbles, it is similar: when carrying a goat, if it happen to pass by a lava bubble, it will have high chances to pop the shield near it. But as the asset is less intrusive and more “special” than the blocs, and include only the goat carrier that usually want to use the bubbles as much as possible, the result is natural. If the bot want to use a geyser when not carrying a goat, it must dash into it.
For the portal as for the lava bubbles (they act as portals you know), I must do some tweaks to the pathfinding system: when looking for the angle of the nodes, you don’t check the angle between the current node and the node of the entry of the teleport, you check for the exit of the teleport node, and the length of this path segment is calculated as 0 instead of the actual distance between them.
Then there are the Freezer Bomb, the Crystal Cross and the Bomb mode. In order to avoid being hit by a bomb, the bot must be aware of the bomb, its area of effect to be specific. So there is a collider for each node, and a collider for the preview area. When the area touch a node, it adds its interest (-1000) to the node. Doing so right at the beginning of the bomb is unnecessary and make the bots too afraid of the bomb when playing “Bomb mode” so the area is effective only 2 seconds before the explosion, and the bot decide if it is worth it to try to get the bomb or to get away at this point and further on. Then I make spread part of the interest to neighboring nodes, then to their neighbors and so on to make the totos aim for the nodes as far as possible of the bomb and not any node outside the zone.
Now that we have a solid base, we need the bots to mimic what an human would do. Even if dash is not really necessary to navigate for bots, they need to do so to immerse the player as much as possible. To dash, they check the distance and angle between the immediate navigation target and themselves. If the angle is more horizontal, the bot will start horizontally. To start, it will make raycasts in the shape of an L, just like the shape of the movement. If the raycast cannot reach it, try starting vertically, if it does not reach wait, do not dash.
Dashing takes time, much may happen while dashing, so the bot need to still be able to update its trajectory mid dash. If the target has moved, it may change the trajectory of its dash. Also if I had a target, but advancing on the path makes the bot “see” further in the path, it may continue the dash further than it previously wanted.
Human versus machine
Humans aren’t perfect, machines are. They are incredibly dumb but they do exactly what you tell them to. So, without any extra code, if you tell the AI to get the goat, it will get the goat and there’s not stopping it. You fear the “EXTREME” setting in Toto Temple Deluxe? You’ve seen nothing, these cuties are toned down quite much from their initial design. It is actually really hard to make them inefficient. Many tweaks come in the form of sliders: the speed when carrying the goat, the speed when not carrying it, the speed of the dash, AI cooldown range between actions like blocking and dashing, number of consecutive dashes it can do and how much time pass for the bot to realize it missed (and correct its course) when it missed the target with a dash. Implementing some of these has proven to be challenging as they create chaos in the behavior of the bots, we have to control it if we don’t want unbelievable behavior.
For example, if I make an easy bot want to dash more than it does now, it may be stuck in an infinite loop dashing left and right because the other parameters don’t let it dash down quickly enough to dash again in the hole it want to go through. The error still rarely happen with the bots of difficulty normal and under.
Sometimes targets disappear (coin/goat altar gone), or the path become blocked, these are some (of the less weird) scenarios where, because I don’t search for a target/path each frame, I get errors. It tries to get the path to the target, but the target doesn’t exist anymore, or try to reach it, but no path leading to it have been found.
This is where I must do verifications, but instead of cluttering the code with extra verifications everywhere, I do a “try / catch” statement and put all my code inside.
This means that if there is an error in my code, I know it instantly and instead of having a bug, I can manage it. The way I manage it is to quickly and completely reset the bot for a frame, then forbid it to make the same decision for a second, then ask it to make a new decision the next frame when things are settled.
Well that’s about it! In no way the AI in Toto Temple Deluxe is perfect, but it can put up an interesting fight without being too previsible and that was the goal. Thank you to have read this post, and I hope it inspires you to start your own little (or big, who knows!) artificial intelligence!