Potential Fields AI, 2/3: RTS bot implementation.

Categories ai, code

This is part 2 of Potential Fields AI article. In part 1 I presented you basic example of my Potential Fields AS3 library. Today we’re going to implement a game with RTS bots fighting against enemies. In part 3 I’ll describe AI details from my upcoming game.

RTS bots fighting.

Above image presents what we’re going to implement: two teams of bots fighting each other with guns. Each bot shots bullets of its own color. Bot’s AI is described with four simple rules:

  • bot marks nearest enemy as its target;
  • then bot follows the enemy to reach “shot distance”;
  • when “shot distance” is reached, bot attacks;
  • if there’s no more enemies, bot stops.

Second rule is where PFlib will help us – It will drive all bots movements. Searching for target and shoting are additional features that we need to implement. Before we start, let’s discuss an important element of my library – potential maps.

Static vs. dynamic potential map.

Do you remember that agent moves on map? You can register more than one map for an agent. My library implements two types of maps: PFDynamicPotentialsMap and PFStaticPotentialsMap. They are designed for different use cases. Major difference lays in memory usage and speed of main operations: adding/updating/removing potential field and getting cell’s potential value. Understanding of this two kinds of maps is crucial for saving resources and keeping good performance in your game.

PFStaticPotentialsMap:

  • this map is implemented as a matrix (Vector.<Vector<int>>);
  • getPotential(x:int, y:int):int call executes very fast – o(1) – as it just reads the value from the matrix;
  • addPotentialField(field:PFPotentialField):void call is very slow because it iterates through all field’s cells;
  • removePotentialField(field:PFPotentialField):void call is very slow for the same reasons;
  • updating field position is impossible – you have to remove the field, update its position and add it again;
  • big memory usage in comparsion to dynamic map – at least width * height * 4bytes;
  • it is designed to store constant potentials informations, like terrain potentials or environment obstacles, e.g. water;

PFDynamicPotentialsMap:

  • this map stores potential fields on linked list;
  • getPotential(x:int, y:int):int call executes slow – o(N), where N is number of fields added – it needs to iterate through all fields on the list and sum their potentials in given point;
  • addPotentialField(field:PFPotentialField):void call is very fast as it just adds element to the list;
  • removePotentialField(field:PFPotentialField):void call is very fast for the same reasons;
  • updating field position is extremely fast – it just modifies values in field object;
  • uses very small amount of memory – it just stores light data structures on list;
  • it is designed for frequently changing potentials: units, moveable obstacles, bullets, etc.
NOTICE: I need to underline it twice: updating field position on static map is impossible – you have to remove the field, update its position and add it again. In some scenarios, this makes field object useless after addPotentialField() is executed. Terrain map is a good example here. You would probably create your terrain static potential map once and never update its potential so all fields’ objects could be freed from memory. However, it has one usefull advantage: you can use one field object to generate whole terrain map – just update it’s values between addPotentialField()  calls.

In Hello Potentials demo from part 1 we used only one dynamic map. Also in this, part 2 we won’t use any static map. However you can find it in Basic Behaviors demo (online swf / source code) where static obstacles are implemented.

Now let’s see what agent can do with potential maps.

Agent’s resultant map.

PFAgent public interface provides two sets of methods for map operations:

// PFStaticPotentialsMap operations:
public function addStaticPotentialsMap(value:PFStaticPotentialsMap):void
public function removeAllStaticPotentialsMaps():void
public function get staticPotentialsMaps():Vector.
public function enableStaticPotentialMap(map_index:int, enabled:Boolean):void
public function isStaticPotentialMapEnabled(map_index:int):Boolean

// PFDynamicPotentialsMap operations:
public function addDynamicPotentialsMap(value:PFDynamicPotentialsMap):void
public function removeAllDynamicPotentialsMaps():void
public function get dynamicPotentialsMaps():Vector.
public function enableDynamicPotentialMap(map_index:int, enabled:Boolean):void
public function isDynamicPotentialMapEnabled(map_index:int):Boolean

There’s no method for removing single map, but you can remove all maps of the same type. Instead, you should enable/disable map of given index. It’s much faster than removing, because maps are stored in array. You have to maintain  map_index by yourself. Map index is determined by adding order and is separate for both map types.

Our RTS bot will be an agent (PFAgent). This agent will use two maps for its AI:

  • dynamic map of avoidance potentials (one map instance shared by all bots);
  • dynamic map of bot’s command potentials (individual map instance for each bot).

PotentialsStack

Above image presents a snapshot from the game that we’re going to create in this tutorial. There are 2 red and 2 blue bots on the stage. This two bots attack each other (BOT1 is BOT2’s target and vice versa).

Look at the two stacks, they illustrate maps collections for higlighted bots. All 4 bots emit repelling potential on avoidance map (they are agents, so they are potential fields, so they can emit). There is only one instance of avoidance map in the game. This instance is added to all bots. However, each bot creates its own instance of commands map. Commands map will store two potential fields:

  • follow target” – wide potential, attracting bot to it’s target (green potetnail on command maps above);
  • keep distance” – small potential, repelling bot from it’s target (illustrated as almost red area).

Those fields will be updated with enemy bot position in every game loop cycle. In result, our bot will follow the target :).

Resultant potential of “follow target” and “keep distance” potentials will attract bot to the target and keep it at appropriate distance (e.g. maximum shoting range of its gun).

Resultant map of avoidance map and commands map will attract bot to the target, keep it at appropriate distance and prevent from colliding with other bots.

In fact, “resultant map” is only an abstraction. Agents don’t need to know whole map. They are interested in 8 potential values surrounding their position. This values are calculated when nextPosition() is called.

Have you noticed, that bot’s repelling potential is not reflected on resultant map? PFAgent class provides one important property:

public var subtractSelfPotentialFromDynamicsMapSum:Boolean;

It’s set to true by default. It substracts agent’s potential when calculating resultant map.

Armed with this knowledge we’re ready to implement our game!

RTS bot implementation.

We’ll start with two bots moving toward target (other bot). Red and blue circle will be used to visualise bots on the stage. Bot will contain PFAgent object for its AI. “Follow target” and “keep distance” potentials also have to be stored in bot’s object. We will add bots to a linked list and update them in game loop.

Having said that, we can design bot’s class:

package {
    import com.ncreated.ai.potentialfields.PFAgent;
    import com.ncreated.ai.potentialfields.PFRadialPotentialField;
    import com.ncreated.lists.BasicLinkedListNode;

    import flash.display.Sprite;

    public class Bot extends BasicLinkedListNode {

        public static const TEAM_RED:int = 0;
        public static const TEAM_BLUE:int = 1;
        public static const RADIUS:Number = 3;// radius of circle representing bot

        public var team:int;
        public var sprite:Sprite;

        public var target:Bot;

        public var agent:PFAgent;
        public var followTargetPotential:PFRadialPotentialField;
        public var keepDistancePotential:PFRadialPotentialField;

        public function Bot() {
        }

        public function update():void {
        }
    }
}

BasicLinkedListNode comes with PFLib, so it should be it in your classpath. It’s just a ligh implementation of linked list node.

Great! Now let’s create our game class template:

package {

    import flash.events.Event;
    import flash.events.MouseEvent;

    [SWF(width='300', height='200', backgroundColor='#eeeeee', frameRate='30')]
    public class FightingBots extends Sprite {

        public function FightingBots() {
            addEventListener(Event.ADDED_TO_STAGE, init, false, 0, true);
        }

        private function init(event:Event):void {
            stage.addEventListener(Event.ENTER_FRAME, onEnterFrame, false, 0, true);
            stage.addEventListener(MouseEvent.CLICK, onClick, false, 0, true);

            // initialize game here
        }

        private function onEnterFrame(event:Event):void {
            // game loop
        }

        private function onClick(event:MouseEvent):void {
            // reset game
        }
    }
}

It’s just a common template which I’m using for simple demos. It has clear initialization point, game loop and resets on mouse click. Let’s fill it with some code:

package {

    import com.ncreated.ai.potentialfields.PFDynamicPotentialsMap;
    import com.ncreated.lists.BasicLinkedList;

    import flash.display.Bitmap;
    import flash.display.BitmapData;

    import flash.display.Sprite;
    import flash.events.Event;
    import flash.events.MouseEvent;

    [SWF(width='300', height='200', backgroundColor='#eeeeee', frameRate='30')]
    public class FightingBots extends Sprite {

        public static const TILE_SIZE:int = 4;

        private var _botsAvoidanceMap:PFDynamicPotentialsMap;
        private var _botsList:BasicLinkedList;

        private var _debugBitmap:Bitmap;

        public function FightingBots() {
            addEventListener(Event.ADDED_TO_STAGE, init, false, 0, true);
        }

        private function get mapWidth():int {return stage.stageWidth / TILE_SIZE;}
        private function get mapHeight():int {return stage.stageHeight/ TILE_SIZE;}

        private function init(event:Event):void {
            stage.addEventListener(Event.ENTER_FRAME, onEnterFrame, false, 0, true);
            stage.addEventListener(MouseEvent.CLICK, onClick, false, 0, true);

            _botsAvoidanceMap = new PFDynamicPotentialsMap(mapWidth, mapHeight);
            _botsList = new BasicLinkedList();

            respawnBots();

            // Just for debug purposes:
            _debugBitmap = new Bitmap(new BitmapData(mapWidth, mapHeight));
            _debugBitmap.scaleX = stage.stageWidth / mapWidth;
            _debugBitmap.scaleY = stage.stageHeight/ mapHeight;
            addChildAt(_debugBitmap, 0);
        }

        private function respawnBots():void {
            // ...
        }

        private function createBot(team:int, x:int, y:int):Bot {
            var bot:Bot = new Bot();
            // ...
            return bot;
        }

        private function destroyBot(bot:Bot):void {
            // ...
        }

        private function onEnterFrame(event:Event):void {
            updateBots();
            debugDraw();
        }

        private function updateBots():void {
            // ...
        }

        private function debugDraw():void {
            // ...
        }

        private function onClick(event:MouseEvent):void {
            while (_botsList.length > 0) destroyBot(_botsList.tail as Bot);
            respawnBots();
            updateBots();
            debugDraw();
        }
    }
}

At this point, the code should be easy to understand, but here are some comments:

  • Line 16: define cell size (4 pixels) for our potential map. It gives us 75×50 tiles on our 300x200px stage (lines 27 and 28). You can reduce it for better precision.
  • Line 34: create avoidance map covering whole stage.
  • Line 46: respawnBots() method will create bunch of bots.
  • Line 69: we’re going to draw commands map for one bot.

Now, some important part – bot setup in createBot() method:

private function createBot(team:int, x:int, y:int):Bot {
    var bot:Bot = new Bot();
    bot.team = team;

    /* Create an agent that will controll this bot movement. */
    bot.agent = new PFAgent();
    bot.agent.type = PFPotentialField.PF_TYPE_REPEL;
    bot.agent.potential = 200;
    bot.agent.gradation = 20;
    bot.agent.position.setTo(x, y);

    /* Add this agent to common avoidance map. */
    _botsAvoidanceMap.addPotentialField(bot.agent);

    /* Register avoidance map for this bot. */
    bot.agent.addDynamicPotentialsMap(_botsAvoidanceMap);

    /* Create "follow target" potential field that will attract this bot to enemy bot. */
    bot.followTargetPotential = new PFRadialPotentialField();
    bot.followTargetPotential.type = PFPotentialField.PF_TYPE_ATTRACT;
    bot.followTargetPotential.potential = 1.42 * Math.max(mapWidth, mapHeight);// make sure that potential covers whole map
    bot.followTargetPotential.gradation = 1;
    bot.followTargetPotential.position.setTo(x, y);

    /* Create "keep distance" potential field which will prevent this bot from getting too close to its target (enemy bot). */
    bot.keepDistancePotential = new PFRadialPotentialField();
    bot.keepDistancePotential.type = PFPotentialField.PF_TYPE_REPEL;
    bot.keepDistancePotential.potential = 250
    bot.keepDistancePotential.gradation = 15;
    bot.keepDistancePotential.position.setTo(x, y);

    /* Register commands map for this bot. */
    bot.agent.addDynamicPotentialsMap(new PFDynamicPotentialsMap(mapWidth, mapHeight));

    /* Add "follow target" and "keep distance" potentials to commands map. */
    bot.agent.dynamicPotentialsMaps[1].addPotentialField(bot.followTargetPotential);
    bot.agent.dynamicPotentialsMaps[1].addPotentialField(bot.keepDistancePotential);

    /* Create bot sprite. */
    bot.sprite = new Sprite();
    bot.sprite.graphics.beginFill(team == Bot.TEAM_RED ? 0xFF0000 : 0x0000FF);
    bot.sprite.graphics.drawCircle(0, 0, Bot.RADIUS);
    bot.sprite.graphics.endFill();
    bot.sprite.cacheAsBitmap = true;
    addChild(bot.sprite);
    return bot;
}
  • Line 3: assign bot to the team (red or blue).
  • Lines 6-10: create PFAgent for bot’s AI. Potential value and gradation size is always difficult to guess and balance (I’ll write more about balancing in part 3). It’s often a result of trials and errors. After spending some time with potential fields AI you gain some intuition with those numbers :).
  • Lines 19-23: an important requirement for “follow target” potential is that it must cover whole stage. Imagine that our bot stands on top-left corner of the stage and it’s target stands on bottom-right. The field needs be big enough that bot can “feel” it.
  • Lines 26-30: potential 250 and gradation 15 gives us 250/15 = 16 cells-wide “keep distance” potential. Cell’s size is 4 pixels, so our bot should keep about 64px distance from it’s target. Nice!
  • Lines 40-45: draw some circle to represent bot on the stage. It immediately adds the sprite to the stage.

We can create a bot now. Let’s respawn two of them on random positions:

private function respawnBots():void {
    var red:Bot = createBot(Bot.TEAM_RED, Math.random() * mapWidth, Math.random() * mapHeight);
    var blue:Bot = createBot(Bot.TEAM_BLUE, Math.random() * mapWidth, Math.random() * mapHeight);

    _botsList.appendNode(red);
    _botsList.appendNode(blue);

    red.target = blue;
    blue.target = red;
}
  • Lines 8-9: manualy set target for each bot. We’ll implement “look for target” logic later.

Final code.

Our game class stil lacks game loop methods implementation. Here’s completed game class code:

package {

    import com.ncreated.ai.potentialfields.PFAgent;
    import com.ncreated.ai.potentialfields.PFDynamicPotentialsMap;
    import com.ncreated.ai.potentialfields.PFPotentialField;
    import com.ncreated.ai.potentialfields.PFRadialPotentialField;
    import com.ncreated.lists.BasicLinkedList;
    import com.ncreated.lists.BasicLinkedListNode;

    import flash.display.Bitmap;
    import flash.display.BitmapData;

    import flash.display.Sprite;
    import flash.events.Event;
    import flash.events.MouseEvent;

    [SWF(width='300', height='200', backgroundColor='#eeeeee', frameRate='30')]
    public class FightingBots extends Sprite {

        public static const TILE_SIZE:int = 4;

        private var _botsAvoidanceMap:PFDynamicPotentialsMap;
        private var _botsList:BasicLinkedList;

        private var _debugBitmap:Bitmap;

        public function FightingBots() {
            addEventListener(Event.ADDED_TO_STAGE, init, false, 0, true);
        }

        private function get mapWidth():int {return stage.stageWidth / TILE_SIZE;}
        private function get mapHeight():int {return stage.stageHeight/ TILE_SIZE;}

        private function init(event:Event):void {
            stage.addEventListener(Event.ENTER_FRAME, onEnterFrame, false, 0, true);
            stage.addEventListener(MouseEvent.CLICK, onClick, false, 0, true);

            _botsAvoidanceMap = new PFDynamicPotentialsMap(mapWidth, mapHeight);
            _botsList = new BasicLinkedList();

            respawnBots();

            // Just for debug purposes:
            _debugBitmap = new Bitmap(new BitmapData(mapWidth, mapHeight));
            _debugBitmap.scaleX = stage.stageWidth / mapWidth;
            _debugBitmap.scaleY = stage.stageHeight/ mapHeight;
            addChildAt(_debugBitmap, 0);
        }

        private function respawnBots():void {
            var red:Bot = createBot(Bot.TEAM_RED, Math.random() * mapWidth, Math.random() * mapHeight);
            var blue:Bot = createBot(Bot.TEAM_BLUE, Math.random() * mapWidth, Math.random() * mapHeight);

            _botsList.appendNode(red);
            _botsList.appendNode(blue);

            red.target = blue;
            blue.target = red;
        }

        private function createBot(team:int, x:int, y:int):Bot {
            var bot:Bot = new Bot();
            bot.team = team;

            /* Create an agent that will controll this bot movement. */
            bot.agent = new PFAgent();
            bot.agent.type = PFPotentialField.PF_TYPE_REPEL;
            bot.agent.potential = 200;
            bot.agent.gradation = 20;
            bot.agent.position.setTo(x, y);

            /* Add this agent to common avoidance map. */
            _botsAvoidanceMap.addPotentialField(bot.agent);

            /* Register avoidance map for this bot. */
            bot.agent.addDynamicPotentialsMap(_botsAvoidanceMap);

            /* Create "follow target" potential field that will attract this bot to enemy bot. */
            bot.followTargetPotential = new PFRadialPotentialField();
            bot.followTargetPotential.type = PFPotentialField.PF_TYPE_ATTRACT;
            bot.followTargetPotential.potential = 1.42 * Math.max(mapWidth, mapHeight);// make sure that potential covers whole map
            bot.followTargetPotential.gradation = 1;
            bot.followTargetPotential.position.setTo(x, y);

            /* Create "keep distance" potential field which will prevent this bot from getting too close to its target (enemy bot). */
            bot.keepDistancePotential = new PFRadialPotentialField();
            bot.keepDistancePotential.type = PFPotentialField.PF_TYPE_REPEL;
            bot.keepDistancePotential.potential = 250
            bot.keepDistancePotential.gradation = 15;
            bot.keepDistancePotential.position.setTo(x, y);

            /* Register commands map for this bot. */
            bot.agent.addDynamicPotentialsMap(new PFDynamicPotentialsMap(mapWidth, mapHeight));

            /* Add "follow target" and "keep distance" potentials to commands map. */
            bot.agent.dynamicPotentialsMaps[1].addPotentialField(bot.followTargetPotential);
            bot.agent.dynamicPotentialsMaps[1].addPotentialField(bot.keepDistancePotential);

            /* Create bot sprite. */
            bot.sprite = new Sprite();
            bot.sprite.graphics.beginFill(team == Bot.TEAM_RED ? 0xFF0000 : 0x0000FF);
            bot.sprite.graphics.drawCircle(0, 0, Bot.RADIUS);
            bot.sprite.graphics.endFill();
            bot.sprite.cacheAsBitmap = true;
            addChild(bot.sprite);
            return bot;
        }

        private function destroyBot(bot:Bot):void {
            removeChild(bot.sprite);
            _botsAvoidanceMap.removePotentialField(bot.agent);
            _botsList.removeNode(bot);
        }

        private function onEnterFrame(event:Event):void {
            updateBots();
            debugDraw();
        }

        private function updateBots():void {
            var iterator:BasicLinkedListNode = _botsList.head;
            while (iterator) {
                var bot:Bot = iterator as Bot;
                bot.update();

                iterator = iterator.next;
            }
        }

        private function debugDraw():void {
            /* Clear debug drawing. */
            _debugBitmap.bitmapData.fillRect(_debugBitmap.bitmapData.rect, 0xEEEEEE);

            /* Draw RED bot commands map. */
            if (_botsList.head) {
                var bot:Bot = _botsList.head as Bot;
                bot.agent.dynamicPotentialsMaps[1].debugDrawPotentials(_debugBitmap.bitmapData);
            }
        }

        private function onClick(event:MouseEvent):void {
            while (_botsList.length > 0) destroyBot(_botsList.tail as Bot);
            respawnBots();
            updateBots();
            debugDraw();
        }
    }
}

We still need to implement bot logic in update() method. It updates “follow target” and “keep distance” potentials to enemy position. Then it moves it’s agent to next cell and updates it’s circle sprite position. Here’s the code:

package {
    import com.ncreated.ai.potentialfields.PFAgent;
    import com.ncreated.ai.potentialfields.PFRadialPotentialField;
    import com.ncreated.lists.BasicLinkedListNode;

    import flash.display.Sprite;
    import flash.geom.Point;

    public class Bot extends BasicLinkedListNode {

        public static const TEAM_RED:int = 0;
        public static const TEAM_BLUE:int = 1;
        public static const RADIUS:Number = 3;

        public var team:int;
        public var sprite:Sprite;

        public var target:Bot;

        public var agent:PFAgent;
        public var followTargetPotential:PFRadialPotentialField;
        public var keepDistancePotential:PFRadialPotentialField;

        public function Bot() {
        }

        public function update():void {
            /* Update commands potentials. */
            if (target) {
                var targetPosition:Point = target.agent.position;

                // follow the target
                followTargetPotential.position.setTo(targetPosition.x,  targetPosition.y);
                keepDistancePotential.position.setTo(targetPosition.x,  targetPosition.y);
            }

            /* Move the agent. */
            agent.moveToPositionPoint(agent.nextPosition());

            /* Update sprite position. */
            sprite.x = agent.position.x * FightingBots.TILE_SIZE;
            sprite.y = agent.position.y * FightingBots.TILE_SIZE;
        }
    }
}

Below, there is a result swf. Click to randomize it’s state. I’ve reduced fps to 10 for better perception – things happen slower ;). What you see is that both bots move toward each other and stop on “shot distance”. Remember that we’re drawing only RED bot’s command map. But BLUE bot implements the same logic, so you can easily imagine how its commands map look like ;).

[kml_flashembed publishmethod=”dynamic” fversion=”11.1.0″ movie=”http://www.n-created.com/wp-content/uploads/2013/08/FightingBots_release.swf” width=”300″ height=”200″ targetclass=”flashmovie”]

Get Adobe Flash player

[/kml_flashembed]

Few improvements…

It works as we expected, so we can get rid of debug view. Also respawnBots() method is not so good… It adds two bots and sets it’s targets directly. We want more bots! Here’s new respawnBots() method implementation:

private function respawnBots():void {
    while (_botsList.length < 10) {         _botsList.appendNode(createBot(Bot.TEAM_RED, Math.random() * mapWidth, Math.random() * mapHeight));         _botsList.appendNode(createBot(Bot.TEAM_BLUE, Math.random() * mapWidth, Math.random() * mapHeight));     } } 

It looks much better now. But now bots have to find targets by their own, so add this two methods to Bot class:

 public function findTarget(bots_list:BasicLinkedList):void {     var nearestBotDistance:Number;     var iterator:BasicLinkedListNode = bots_list.head;     while (iterator) {         var bot:Bot = iterator as Bot;         if (bot.team != team) {             if (!target) {                 target = bot;                 nearestBotDistance = distance(bot.sprite.x, bot.sprite.y, sprite.x, sprite.y);             }             else {                 var botDistance:Number = distance(bot.sprite.x, bot.sprite.y, sprite.x, sprite.y);                 if (nearestBotDistance > botDistance) {
                    nearestBotDistance = botDistance;
                    target = bot;
                }
            }
        }

        iterator = iterator.next;
    }
}

private function distance(x1:Number, y1:Number, x2:Number, y2:Number):Number {
    return Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

This new public method takes list of bots in the game and searches for nearest enemy. Then sets it as a new target.

Finally, we need to call findTarget() from game loop:

private function updateBots():void {
    /* Update bots. */
    var iterator:BasicLinkedListNode = _botsList.head;
    while (iterator) {
        var bot:Bot = iterator as Bot;
        bot.update();

        if (!bot.target) {
            // find target
            bot.findTarget(_botsList);
        }

        iterator = iterator.next;
    }
}

Result:

[kml_flashembed publishmethod=”dynamic” fversion=”11.1.0″ movie=”http://www.n-created.com/wp-content/uploads/2013/08/FightingBots_release1.swf” width=”300″ height=”200″ targetclass=”flashmovie”]

Get Adobe Flash player

[/kml_flashembed]

It’s still boring… :(

Fighting Bots demo.

I turned last build into true simulation of fighting bots. Source code of Fighting Bots demo is available on GitHub. I added some bullets and bullet-bot collision detection. Now it looks better (click to reset the state):

[kml_flashembed publishmethod=”dynamic” fversion=”11.1.0″ movie=”http://www.n-created.com/wp-content/uploads/2013/08/FightingBots_release2.swf” width=”600″ height=”400″ targetclass=”flashmovie”]

Get Adobe Flash player

[/kml_flashembed]

This was part 2 of my 3-part Potential Fields AI article. Liked it? Stay tuned for next part!