Monday, April 2, 2012

Turn Based Strategy Game AI part 3








Continued from part 2

This week I would like to introduce you to Carl.  This AI player shares almost the same code as Brutus from last week, but with one very important difference.  Carl generates an Influence Map to determine the relative strengths of each player at each space on the map. 

The influence map is generated by seeding a representation of the game map with each unit's strength, and then using an algorithm known as Chamfering or Grassfire to propagate these influence values across the map.  The advantage of this algorithm is that it is relatively quick, requiring only 2 passes over the map (3 if one includes the initial seeding of values).

I am currently computing the influence value of a unit equal to its Attack value multiplied by the sum of its movement rate and attack range.  This value then falls off at a rate of 1 per space distant from the source.  I then record the highest influence at each space.

I am also keeping track of each player's influence separately as I hope to generate additional types of influence maps in the weeks to come.  Here is the code I am currently using to generate the influence map.

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;

namespace ShatteredThrone
{
    class InfluenceMap
    {
        class InfluenceKey
        {
            // player
            float[] _influences;

            public InfluenceKey() : this(0f, 0f) { }

            public InfluenceKey(float p1, float p2)
            {
                _influences = new float[2];
                _influences[0] = p1;
                _influences[1] = p2;
            }

            public float GetInfluenceByPlayer(int who)
            {
                return _influences[who];
            }

            public float GetTotalInfluence()
            {
                return GetInfluenceByPlayer(0) - GetInfluenceByPlayer(1);
            }

            public void SetInfluenceForPlayer(int who, float v)
            {
                _influences[who] = Math.Max( v, _influences[who]);
            }
        }

        float _minInfluence;
        float _maxInfluence;
        int _width;
        int _height;
        List _influenceMapping;

        public InfluenceMap(float maxInfluenceValue)
        {
            _minInfluence = -maxInfluenceValue;
            _maxInfluence = maxInfluenceValue;
            _influenceMapping = new List();
        }

        public float GetTotalInfluenceAt(int x, int y)
        {
            float ret = 0f;

            if (x >= 0 && x < _width &&
                y >= 0 && y < _height)
                ret = _influenceMapping[y * _width + x].GetTotalInfluence();

            return MathHelper.Clamp(ret, _minInfluence, _maxInfluence);
        }

        public float GetTotalInfluencePercentAt(int x, int y)
        {
            // returns value between -1 and 1
            return GetTotalInfluenceAt(x, y) / _maxInfluence;
        }

        private float GetInfluenceByPlayerAt(int who, int x, int y)
        {
            float ret = 0f;

            if (x >= 0 && x < _width &&
                y >= 0 && y < _height)
                ret = _influenceMapping[y * _width + x].GetInfluenceByPlayer(who);

            return ret;
        }

        private void SetInfluenceForPlayerAt(int who, int x, int y, float v)
        {
            if (x >= 0 && x < _width &&
                y >= 0 && y < _height)
                _influenceMapping[y * _width + x].SetInfluenceForPlayer(who, v);
        }

        float _upDownValue;
        float _leftRightValue;
        float _bestValue;

        private float CalculateInfluenceForPlayerAt(int who, int x, int y, int dir)
        {
            _upDownValue = GetInfluenceByPlayerAt(who, x, y + dir); // north/south
            _leftRightValue = GetInfluenceByPlayerAt(who, x + dir, y); // west/east

            // subtract 1 from the value of our highest neighbor
            _bestValue = Math.Max(_upDownValue, _leftRightValue) - 1;

            // all values should be positive
            return (_bestValue > 0f) ? _bestValue : 0f;
        }

        private float GetInfluenceForUnitType(UnitStatus u)
        {
            return (u.Move + u.Range) * u.Attack;
        }

        // based on Chamfering/grassfire algorithm
        public void CreateMap(GameMap m, GameState gs)
        {
            int x, y;

            // rebuild map and working arrays
            _width = m.Width;
            _height = m.Height;

            // rebuild our array only if necessary
            if (_influenceMapping.Count != (_width * _height))
            {
                _influenceMapping.Clear();
                // zero out arrays
                for (x = 0; x < _width; x++)
                {
                    for (y = 0; y < _height; y++)
                    {
                        _influenceMapping.Add(new InfluenceKey());
                    }
                }
            }
            else
            {   // reset all existing influence values to 0
                for (x = 0; x < _width; x++)
                {
                    for (y = 0; y < _height; y++)
                    {
                        SetInfluenceForPlayerAt(0, x, y, 0f);
                        SetInfluenceForPlayerAt(1, x, y, 0f);
                    }
                }
            }
            // seed initial values based on units
            foreach (UnitStatus u in gs.Units)
            {
                if (u.IsAlive)
                {
                    SetInfluenceForPlayerAt((u.Owner == Globals.PLAYER_ONE) ? 0 : 1, u.X, u.Y, GetInfluenceForUnitType(u));
                }
            }
            
            // perform pass 1 (calculates based on North/West neighbors)
            for (y = 0; y < _height; y++)
            {
                for (x = 0; x < _width; x++)
                {
                    SetInfluenceForPlayerAt(0, x, y, CalculateInfluenceForPlayerAt(0, x, y, -1));
                    SetInfluenceForPlayerAt(1, x, y, CalculateInfluenceForPlayerAt(1, x, y, -1));
                }
            }

            // perform pass 2 (calculates based on South/East neighbors)
            for (y = (_height - 1); y >= 0; y--)
            {
                for (x = (_width - 1); x >= 0; x--)
                {
                    SetInfluenceForPlayerAt(0, x, y, CalculateInfluenceForPlayerAt(0, x, y, 1));
                    SetInfluenceForPlayerAt(1, x, y, CalculateInfluenceForPlayerAt(1, x, y, 1));
                }
            }
        }
    }
}

Last week, when the AI was grading the value of a space to move into, it had the following section to encourage it to move around:

private int ScoreLocationForUnit(Point loc, UnitStatus u, GameDetail gd)
        {
            int ret = 0;

            // prefer to move instead of standing still
            if (loc == u.Location) ret = -1;

For Carl, this is replaced by the following (based on an influence map generated at the start of the Think() call).

private float ScoreLocationForUnit(Point loc, UnitStatus u, GameDetail gd)
        {
            float ret;

            // get location score based on based on influence, (tend towards 0)
            ret = 8f - _influenceMap.GetTotalInfluencePercentAt(loc.X, loc.Y) * 8f;

With this change, Carl now has a preference towards moving areas where the influence is 0, which coincides with the battle front.  Here is a link to a video showing Carl playing Brutus from last week.

I added code to my draw to show the current influence map as well, so we can see the extra information that Carl is using.

I actually expected Carl to play a better game than he does, but it is certainly still a step up from last week, but I still do not have a solid beginner level AI player.  I have gotten some great suggestions that I hope to explore in the weeks to come, but did not yet include them as I want to progress in small bite sized chunks where I can see the level of proficiency of the AI player grow with each change.

Here is the full code listing for Carl:

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;

namespace ShatteredThrone.AI.Brains
{
    class Carl : ComputerBrain
    {
        Random _random;
        Pathfinder _pather;
        CombatEngine _combat;
        InfluenceMap _influenceMap;

        public Carl()
        {
            _random = new Random();
            _pather = new Pathfinder();
            _combat = new CombatEngine();
            _influenceMap = new InfluenceMap(10f);
        }


        private float ScoreLocationForUnit(Point loc, UnitStatus u, GameDetail gd)
        {
            float ret;

            // get location score based on based on influence, (tend towards 0)
            ret = 8f - _influenceMap.GetTotalInfluencePercentAt(loc.X, loc.Y) * 8f;

            // get score based on attack/defense mods for this location
            ret += gd.Map.GetMapSpaceTerrainAttackMod(loc);
            ret += gd.Map.GetMapSpaceTerrainDefenseMod(loc);

            // adjust score by settlements at this location
            Settlement s = gd.CurrentState.GetSettlementAtLocation(loc);
            if (s != null)
            {
                // update by settlement attack/defense mods
                ret += s.DefenseBonus;
                ret += s.AttackBonus;
                if (gd.CurrentState.AreFriendly(s.Owner, u.Owner))
                {
                    // settlement is owned by us, avoid being here if could build here
                    if (s.CanBuildUnits) ret -= 3f;
                    // if current unit is hurt, and the players faction allows units to heal in settlements
                    if (gd.CurrentPlayer.HasPassive(Faction.FactionPassive.HEAL_IN_SETTLEMENTS))
                    {
                        if (u.CurrentDamage > 0) ret += 1f;
                        if (u.CurrentDamage >= (u.MaxHP / 2f)) ret += 2f;
                    }
                    // if this unit generate extra income on settlements, give it more incentive to be here
                    if (s.GoldIncome > 0 && u.HasTrait(UnitTrait.CHARITY)) ret += 2f;
                }
                else
                {
                    // always good to capture settlements
                    ret += 2f;
                    // even better fully capture
                    if (s.Owner == Globals.PLAYER_NONE) ret += 2f;
                }
            }

            // prefer to be next to our own units
            ret += GetAdjacentMovedFriendlyUnits(u.Owner, loc, gd.CurrentState);
            // if this unit has banding, give extra bonus for moving next to units of the same type
            if (u.HasTrait(UnitTrait.BANDING))
            {
                ret += gd.CurrentState.GetBandSize(loc, u.Owner, u.UnitType);
            }

            return ret;
        }

        private float ScoreHealForUnit(Point targetLoc, GameDetail gd)
        {
            float ret = -1f; // doing nothing is better than healing target that does not need it

            // get target unit
            UnitStatus u = gd.CurrentState.GetUnitAtLocation(targetLoc);
            if (u != null)
            {
                // score the heal based on how badly unit requires it
                if (u.CurrentDamage > 0) ret = 1f;
                if (u.CurrentDamage >= 2) ret += 1f;
                if (u.CurrentDamage > (u.MaxHP / 2)) ret += 1f;
                if (u.CurrentDamage > (u.MaxHP / 3)) ret += 1f;
            }

            return ret;
        }

        private float ScoreAttackForUnit(UnitStatus attacker, Point attackLocation, Point targetLocation, GameMap m, GameState gs)
        {
            float ret = 0f;
            UnitStatus target;

            List results = _combat.GetAttackResults(attacker, attackLocation, targetLocation, m, gs);
            // loop through all returned results
            foreach (AttackResult ar in results)
            {
                // subtract damage caused to friends, add damage caused to enemies
                if (gs.AreFriendly(attacker.Owner, ar.TargetOwnerID))
                {
                    // will this kill ourselves?
                    if (!attacker.CanSurviveDamage(ar.Damage))
                    {
                        ret -= 3f + attacker.CurrentHP;
                    }
                    else
                    {
                        ret -= ar.Damage;
                    }
                }
                else
                {
                    // will this kill the target?
                    target = gs.GetUnitAtLocation(ar.TargetLocation);
                    if (target != null)
                    {
                        if (!target.CanSurviveDamage(ar.Damage))
                        {
                            // bonus is 4, + current HP (do not want to reward too much overkill)
                            ret += 4f + target.CurrentHP;
                        }
                        else
                        {
                            ret += ar.Damage;
                            ret += ar.TotalComboPoints;
                        }
                    }
                    else
                    {
                        // could not find target unit for some reason
                        ret += ar.Damage;
                        ret += ar.TotalComboPoints;
                    }
                }
            }

            return ret;
        }


        private float ScoreActionForUnit(Point src, UnitStatus u, CombatAction ca, GameDetail gd)
        {
            float ret = 0f;

            switch (ca.ActionType)
            {
                case CombatActionType.ATTACK:
                    ret = ScoreAttackForUnit(u, src, ca.Location, gd.Map, gd.CurrentState);
                    break;
                case CombatActionType.HELP:
                    ret = ScoreHealForUnit(ca.Location, gd);
                    break;
            }

            return ret;
        }

        private void SubmitBestMoveForUnit(UnitStatus u, GameDetail gd, PlayerController pc)
        {
            float currentBestScore = -10000f; // always want to do something
            Point currentBestMoveLocation = new Point(u.X, u.Y); // by default go nowhere
            CombatAction currentBestCombatAction = new CombatAction(u.X, u.Y, CombatActionType.IDLE); // and do nothing

            // get all possible move locations for this unit
            List moveLocs = _pather.GetValidMoveLocations(u, gd.Map, gd.CurrentState);
            foreach (Point loc in moveLocs)
            {
                // score this move location
                float locScore = ScoreLocationForUnit(loc, u, gd);
                // get all possible actions at this location
                List acts = _combat.GetCombatActionsByUnitAtLocation(u, gd.Map, gd.CurrentState, loc);
                // loop through all possible actions at this location
                foreach (CombatAction ca in acts)
                {
                    // score this action
                    float actionScore = ScoreActionForUnit(loc, u, ca, gd);
                    // is this our best score so far?
                    if ((locScore + actionScore) > currentBestScore)
                    {
                        // set this as our best possible move
                        currentBestScore = locScore + actionScore;
                        currentBestMoveLocation = loc;
                        currentBestCombatAction = ca;
                    }
                }
            }
            // perform the determined best move/action
            // build and submit command to move
            SubmitMove(u, currentBestMoveLocation, pc);
            SubmitAction(currentBestCombatAction, u, currentBestMoveLocation, pc);
        }

        public override void Think(GameDetail gd, PlayerController pc)
        {
            // build influence map
            _influenceMap.CreateMap(gd.Map, gd.CurrentState);
            // get units to move
            List units = GetUnitsLeftToMove(pc.PlayerIndex, gd.CurrentState);

            // do we have any units left to move
            if (units.Count > 0)
            {
                // pick a unit at random
                UnitStatus u = units[_random.Next(units.Count)];
                // do best move for this unit
                SubmitBestMoveForUnit(u, gd, pc);
            }
            else
            {
                // get available settlements to build
                List builders = GetAvailableBuildingSettlements(pc.PlayerIndex, gd.CurrentState);
                PlayerResources pr = gd.CurrentState.GetPlayerResources(pc.PlayerIndex);
                // get list of units we can afford
                List buildableTypes = GetBuildableUnitTypes(gd, pr.Gold, pc.PlayerIndex);

                // do we both have enough money and places to build?
                if (builders.Count > 0 && buildableTypes.Count > 0)
                {
                    // get random settlement to build at
                    Settlement s = builders[_random.Next(builders.Count)];
                    
                    // submit command to build random unit at random location
                    SubmitBuild(buildableTypes[_random.Next(buildableTypes.Count)], s.X, s.Y, pc);
                }
                else
                {
                    // nothing left to do except end our turn
                    SubmitEndTurn(pc);
                }
            }
        }
    }
}

Continued in part 4...

No comments: