Monday, April 16, 2012

Turn Based Strategy Game AI part 4

Continued from part 3



This installment has been difficult to put together.  The idea was to add in a Goal based planning element to the AI, and the resulting work quickly became a much larger undertaking than I desired.  My own objective is to only add small incremental changes each week, but this one really got away from me.  Often because I thought I knew what I was doing, when I really did not.

I ended up gutting a lot of the extra details I had been adding to get this back to a reasonable size.  I am glad I did, because the end result ended being less than steller.  Yet, it has a promising framework to work from in the weeks to come.

The basic idea was simple.  The AI would consist of two components, a tactical component will make the individual move decisions, while a new strategic component would parsel out individual goals to our units.  The tactical component will use each units goal in determining the best move.

The tactical component consists of the code I have written up to this point in the series, the only change here will be to give extra weight to the units assigned goal.

I ended up with 3 types of goals at this point.  A KILL goal of which all enemy units represent a single such goal.  A CAPTURE goal, which consists of all Settlements in the game that we do not own, and finally a FORTIFY goal, otherwise known as the default NULL goal where the unit works to maximize its best possible move without a specific target unit or settlement.

The strategic layer executes once at the start of the AI's turn and goes through the following logic:

  • Add each enemy unit as a KILL goal
  • Add each unowned settlement as a CAPTURE goal
  • Prioritize each goal
  • Loop through the goals in order of priority
    • Judge the Suitability of all our units not already assigned a goal for this goal
    • If the goal has enough units (3 for KILL, 1 for CAPTURE)
      • Assign the most suitable units to this goal (top 3 for KILL, just the top for CAPTURE goals)

Then the tactical portion of the AI will weight its potential moves towards its assigned goal target.

That is the simple idea, however a rather large amount of code resulted.  This was not helped by the fact that I also added a new component called a DispositionProfile.  This class holds all numeric constants used during the AI calculations (or at least just the new ones introduced this week so far).  The idea is that different weighting sets can be used based on different situations.  Also, I may try evolving the AI values through a genetic algorithm at some point, and these DispositionProfile objects can be used as the AI's "DNA" in the process.

One of the trickier aspects of the process is judging a Goal's Priority and a unit's Suitability for a goal.  At this point, I based this part of the algorithm on the Influence Map I added last week.  By adding both player's influence together, I generated a Tension map.  The areas of highest Tension values were located along the front where both players have units.  I would give higher priority to targets in these highly contested areas. 

The other major component of determining a goal's priority would be its Vulnerability, which was simply our own influence by itself.  The thinking being that we would give extra priority to the most vulnerable targets.

The idea was based on the following article on influence maps.  And the logic is that we want to target the most vulnerable enemies along the mutual front.  A unit's suitability to a goal is based mostly on its distance to the goal along with the unit's Attack value and current HP.

The results of this addition are a bit of a mixed bag.  The resulting video makes me realize that I still have 2 fundamental issues.  One is that the tactical engine does not maximize the order of its moves.  This has caused one unit type to become nearly unstoppable.  This unit is not particularly strong, but it has a strong defense which nullifies all damage against it when it has no combo points.  And combo points are generated by attacking the same unit with successive moves.

The other issue is that the map is not terribly balanced.  These two elements make it difficult to get an accurate feel for which AI is strongest.  I plan to make addressing these two items my focus for the next installment.

One positive takeaway is that this AI is not leaving units hanging around its staging area as badly as the prior.  Here is the video showing this weeks AI (called "Dave") in Blue against last weeks "Carl".  I have the game engine drawing a line between Dave's units and their assigned goal, along with overlaying the Influence map visually.

Video Here

Here is the new Goal class that keeps track of goals and assigns Priority and Suitability values. (The GoalResource and DispositionProfile classes referenced are simple data classes without any special logic)
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;

namespace ShatteredThrone.AI
{
    public class Goal
    {
        public enum GoalType
        {
            FORTIFY = 0,
            ATTACK = 1,
            CAPTURE = 2
        }

        public GoalType GoalId;
        public Point GoalTarget;
        public float Priority;
        public bool IsActive;
        List PotentialResources;
        public int NeededResources;

        public Goal()
        {
            PotentialResources = new List();
            IsActive = false;
            GoalTarget = new Point(0, 0);
        }

        public void CreateGoal(GoalType gt, int tx, int ty, GameState gs, DispositionProfile aiDisposition, InfluenceMap im)
        {
            // set basic goal properties
            GoalId = gt;
            GoalTarget.X = tx;
            GoalTarget.Y = ty;
            IsActive = false;
            PotentialResources.Clear();
            
            // Determine Goal Priority based on goal type
            switch (GoalId)
            {
                case GoalType.ATTACK:
                    SetAttackPriority(gs, aiDisposition, im);
                    NeededResources = 3;
                    break;
                case GoalType.CAPTURE:
                    SetCapturePriority(gs, aiDisposition, im);
                    NeededResources = 1;
                    break;
                case GoalType.FORTIFY:
                    Priority = 0f;
                    break;
            }
        }

        public bool HasSufficientResources
        {
            get
            {
                return (PotentialResources.Count >= NeededResources);
            }
        }

        public void AssignGoalResources(GameState gs)
        {
            // order our potential resources by suitability
            var resourcesBySuitability = from pr in PotentialResources
                                         orderby pr.Suitability descending
                                         select pr;

            // assign a number of resources equal to what we need
            int assignCount = 0;
            foreach(GoalResource gr in resourcesBySuitability)
            {
                // get unit representing this resource
                UnitStatus u = gs.GetUnitAtLocation(gr.SourceLocation);
                // double check that we got a valid unit
                if (u != null)
                {
                    // set goal for unit and bump count
                    u.SetAiGoal(GoalId, GoalTarget);
                    assignCount++;
                    // if we have assigned enough units, break out of loop
                    if (assignCount >= NeededResources) break;
                }
            }
        }

        public void AssignUnitResourceSuitability(UnitStatus u, GameState gs, DispositionProfile dp)
        {
            switch (GoalId)
            {
                case GoalType.ATTACK:
                    GetBaseUnitSuitabilityForAttackGoal(u, gs, dp);
                    break;
                case GoalType.CAPTURE:
                    GetBaseUnitSuitabilityForCaptureGoal(u, gs, dp);
                    break;
            }
        }

        private void SetAttackPriority(GameState gs, DispositionProfile dp, InfluenceMap im)
        {
            Priority = im.GetTensionPercentAt(GoalTarget.X, GoalTarget.Y) * dp.AttackGoal.TensionFactor;
            Priority += im.GetVulnerabilityPercentByPlayerAt(gs.CurrentPlayer, GoalTarget.X, GoalTarget.Y) * dp.AttackGoal.VulnerabiltiyFactor;
        }

        private void SetCapturePriority(GameState gs, DispositionProfile dp, InfluenceMap im)
        {
            Priority = im.GetTensionPercentAt(GoalTarget.X, GoalTarget.Y) * dp.CaptureGoal.TensionFactor;
            Priority += im.GetVulnerabilityPercentByPlayerAt(gs.CurrentPlayer, GoalTarget.X, GoalTarget.Y) * dp.CaptureGoal.VulnerabiltiyFactor;
        }

        private void AddPotentialUnitResource(UnitStatus u, float suitability)
        {
            GoalResource gr = new GoalResource();
            gr.SourceLocation.X = u.X;
            gr.SourceLocation.Y = u.Y;
            gr.Suitability = suitability;

            PotentialResources.Add(gr);
        }

        private float GetBaseDistanceFactor(int sx, int sy, int tx, int ty, float range)
        {
            float ret = (range > 0) ? (float)Globals.GetDistance(sx, sy, tx, ty) / range : 5f;
            return 4f - ret;
        }

        private void GetBaseUnitSuitabilityForAttackGoal(UnitStatus u, GameState gs, DispositionProfile dp)
        {
            float suitability;

            // get base distance rating
            suitability = GetBaseDistanceFactor(u.X, u.Y, GoalTarget.X, GoalTarget.Y, u.Move + u.Range) * dp.AttackGoal.SourceDistanceFactor;
            // add current hp rating
            suitability += (float)u.CurrentHP * dp.AttackGoal.SourceHpFactor;
            // add attack rating
            suitability += (float)u.Attack * dp.AttackGoal.SourceAttackFactor;

            AddPotentialUnitResource(u, suitability);
        }

        private void GetBaseUnitSuitabilityForCaptureGoal(UnitStatus u, GameState gs, DispositionProfile dp)
        {
            float suitability;

            // get base distance rating
            suitability = GetBaseDistanceFactor(u.X, u.Y, GoalTarget.X, GoalTarget.Y, u.Move) * dp.CaptureGoal.SourceDistanceFactor;

            AddPotentialUnitResource(u, suitability);
        }

    }
}

The goal assignment code run at the start of each AI turn is contained in the following new function:

private void StartOfTurn(GameDetail gd)
        {
            // reset all goals
            _CurrentGoals.Clear();

            // reset our own unit goals from last turn, and create attack goal for enemy units
            foreach (UnitStatus u in gd.CurrentState.Units)
            {
                if (gd.CurrentState.AreFriendly(u.Owner, gd.CurrentState.CurrentPlayer))
                {
                    // friendly unit, reset goal
                    u.ResetAiGoal();
                }
                else
                {
                    // enemy unit, add as goal assuming is alive
                    if (u.IsAlive)
                    {
                        Goal g = new Goal();
                        g.CreateGoal(Goal.GoalType.ATTACK, u.X, u.Y, gd.CurrentState, _disposition, _influenceMap);
                        _CurrentGoals.Add(g);
                    }
                }
            }

            // create capture goal for all unowned settlements
            foreach (Settlement s in gd.CurrentState.Settlements)
            {
                if (s.Owner != gd.CurrentState.CurrentPlayer)
                {
                    Goal g = new Goal();
                    g.CreateGoal(Goal.GoalType.CAPTURE, s.X, s.Y, gd.CurrentState, _disposition, _influenceMap);
                    _CurrentGoals.Add(g);
                }
            }

            // Sort goals in descending order by priority
            var goalsByPriority =   from ug in _CurrentGoals
                                    orderby ug.Priority descending
                                    select ug;
            // add all our units as potential resources for every goal
            foreach (Goal g in goalsByPriority)
            {
                foreach (UnitStatus u in gd.CurrentState.Units)
                {
                    // if unit is living, friendly, and not yet assigned a goal, add it as a potential resource
                    if (u.IsAlive && !u.HasAiGoal && gd.CurrentState.AreFriendly(u.Owner, gd.CurrentState.CurrentPlayer))
                    {
                        g.AssignUnitResourceSuitability(u, gd.CurrentState, _disposition);
                    }
                }
                // Does goal have enough potential resources
                if (g.HasSufficientResources)
                {
                    // Assign resources to goal
                    g.AssignGoalResources(gd.CurrentState);
                }
            }

            // set this as current turn so we only run this routine once per game turn
            _lastTurn = gd.CurrentState.CurrentTurn;
        }

        public override void Think(GameDetail gd, PlayerController pc)
        {
            // build influence map
            _influenceMap.CreateMap(gd.Map, gd.CurrentState);

            // is this the start of the turn?
            if (_lastTurn != gd.CurrentState.CurrentTurn)
            {
                StartOfTurn(gd);
            }


Moves scoring now has additional scoring logic based on a units goal. The scoring for the default FORTIFY goal is the same logic used last time.

        private float GetDistanceToGoalImproval(UnitStatus u, Point newLoc)
        {
            float oldDistance = Globals.GetDistance(u.X, u.Y, u.AiGoalTarget.X, u.AiGoalTarget.Y);
            float newDistance = Globals.GetDistance(newLoc, u.AiGoalTarget);

            // return factor representing improvement in position, protect vs divide by 0
            return (oldDistance > 0) ? (1f - newDistance / oldDistance) : (1f - newDistance);
        }

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

            // score location based on goal
            switch (u.AiGoal)
            {
                case Goal.GoalType.ATTACK:
                    ret = GetDistanceToGoalImproval(u, loc) * _disposition.AttackGoal.TargetDistanceFactor;
                    break;
                case Goal.GoalType.CAPTURE:
                    ret = GetDistanceToGoalImproval(u, loc) * _disposition.CaptureGoal.TargetDistanceFactor;
                    break;
                case Goal.GoalType.FORTIFY:
                default:
                    // get location score based on based on influence, (tend towards 0)
                    ret = 8f - _influenceMap.GetTotalInfluencePercentAt(loc.X, loc.Y) * 8f;
                    break;
            }

And finally, when scoring attack actions, a bonus is applied to the score if the attack action contains the units assigned Attack target (if any).

// if we had an attack goal, boost value of attack if is against our assigned target
            if (attacker.AiGoal == Goal.GoalType.ATTACK && attacker.AiGoalTarget == targetLocation)
            {
                ret += _disposition.AttackGoal.AttackedTargetBonus;
            }

No comments: