Monday, November 3, 2008

Do Not Want!

I promised an in-depth explanation of how bots in BrainWorks perform dodging. But sometimes a picture provides the perfect overview:

That's the core of the algorithm. For whatever reason, this dog has decided he absolutely does not want to catch the ball someone threw at him, and the only thing his mind is thinking about is how he can safely get away.

When a bot needs to dodge a missile, the bot considers the eight possible directions it can move in (forward, backward, left, right, and each diagonal), plus the "dodge" of standing still. Any movement direction that collides with an incoming missile is considered completely off limits. Yes, it's bad to get "herded" where the enemy wants you to go, but that's a situation the bot can deal with later. There's no sense in eating a rocket now so that the bot might not take other damage later. Priority number one is always avoiding incoming damage.

So for each of the nine total dodge options, the bot computes what would happen if it moved in that direction for around a second. If a missile would hit the bot, it flat out ignores the option. It also has to check for some other problems. Obviously "dodging" into a wall isn't much of a dodge at all, so bots only dodge in directions with enough open space to move. And if the dodge is off a ledge, into a pit, then the bot also ignores that option. Those are the three reasons a bot will automatically disqualify a potential dodge direction:
  • Would hit a missile
  • Would hit a wall
  • Would fall down a pit
The bot might then dodge in any of the remaining dodge directions. There are two obvious and wrong ways the bot can choose which direction to move in.

Option 1: Move in the direction that gets the bot closest to its intended destination

The problem here is that the bot is very predictable. If you know where the bot wants to go and what route a missile shot cuts off, you know exactly where it will head next That makes it trivial to hit the bot in your next shot, and being predictable is not a luxury the bot has.

Option 2: Choose one of the remaining directions at random

This solves the predictability problem. But when you pick the remaining directions at random with equal probability, the bot's natural movement will be away from the missiles, without any regard for where the bot wants to end up. This random selection lets the attacker control the general direction the bot will move on, possibly keeping the bot from its destination indefinitely. In this situation, it's easy for the attacker to route the bot into a corner and finish it off.

The solution is to combine these two strategies:

Solution: Select at random, preferring directions that move towards the intended destination

Rather than assigned an equal chance of dodging in any direction, the bot analyzes all options and rates how well they help the bot reach its goal. The more helpful an option is, the higher the probability it will take it. However, any option could be taken. Over time, there is a high probability the bot will reach its goal, but its actual dodge direction is not predictable.

For example, suppose there is an incoming missile on the bot's east side, so it's unsafe to dodge east, northeast, or southeast. And suppose the bot would prefer to move northeast were the missile not in the way. The bot's dodge probability table might look like this:
  • North: 40%
  • Northeast: 0% (Ideal)
  • East: 0%
  • Southeast: 0%
  • South: 15%
  • Southwest: 5%
  • West: 15%
  • Northwest: 20%
  • Stationary: 5%
Once the bot knows where it wants to move, it keeps dodging in that direction for anywhere between three quarters of a second and a second and a half, at which point it chooses another direction (or possibly keeps going the same way). The result? A simple weighted probability function prevents the bot from running into missiles, being predictable, and being routed away from their goals.

No comments: