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:
Post a Comment