First, some definitions for others reading this
- Euclidean – This is the pathfinding method we’re currently using in the course. It assumes that a diagonal move is equivalent to 1.4 units of measurement. Cardinal movements are 1 unit each square. The Euclidean cost of X+1, Z+1 is 1.4
- Manhattan (or Taxi) – This is pathfinding assuming that you cannot move diagonally, much like a Taxi in Manhattan, to get to X+1, Z+1, you have to go to X+1, Z then X+1,Z+1, so the Manhatten cost for X+1,Z+1 is 2.
- Kings – In Chess a King may move one space in any Cardinal or Diagonal direction. King’s Cost is how many moves a Chess King would take to get to the space. The Kings Cost of X+1, Z+1 is 1.
One thing that I’ve added to my own personal project is a Distance function in the GridPosition. My Turn based game uses the Manhattan cost, this is my GridPostion.Distance(GridPosition other) method
public int Distance(GridPosition other)
{
int deltaX = Mathf.Abs(x-other.x);
int deltaZ = Mathf.Abs(z-other.z);
return (deltaX+deltaZ) * 10;
}
I multiply by 10 just to match up with the HCost setup in Pathfinding, and test against Distance/10 in the Actions.
So I think a starting point would be to make the three movement costs Distance function setup in GridPosition. This will be worth it
/// <summary>
/// Returns the pathfinding HCost based on Euclidean distance. (Cardinal moves *10, Diagonal Moves * 14)
/// Physical distance is scaled in units of 10 to conform to our pathfinding system.
/// </summary>
/// <param name="other"></param>
/// <returns></returns>
public int EuclideanDistance(GridPosition other)
{
int deltaX = Mathf.Abs(x - other.x);
int deltaZ = Mathf.Abs(z - other.z);
if (deltaX > deltaZ)
{
(deltaX, deltaZ) = (deltaZ, deltaX);
}
int cardinal = deltaZ - deltaX;
//At this point, deltaX now represents the number of diagonal squares. cardinal is the remainder of squares travelled diagonally
return cardinal * 10 + deltaX * 14;
}
/// <summary>
/// Returns the pathfinding HCost based on Manhattan distance (Only Cardinal moves allowed -- Cardinal moves * 10)
/// Physical distance is scaled in units of 10 to conform to our pathfinding system.
/// </summary>
/// <param name="other"></param>
/// <returns></returns>
public int ManhattanDistance(GridPosition other)
{
int deltaX = Mathf.Abs(x - other.x);
int deltaZ = Mathf.Abs(z - other.z);
return (deltaX + deltaZ) * 10;
}
/// <summary>
/// Returns the pathfinding HCost based on Kings distance (Cardinal and Diagonal moves are all * 10)
/// Physical distance is scaled in units of 10 to conform to our pathfinding system.
/// </summary>
/// <param name="other"></param>
/// <returns></returns>
public int KingsDistance(GridPosition other)
{
int deltaX = Mathf.Abs(x - other.x);
int deltaZ = Mathf.Abs(z - other.z);
//Because diagonal and cardinal moves are all the same cost, the greater of deltaX,deltaZ is the HCost
return Mathf.Max(deltaX, deltaZ) * 10;
}
In terms of an IEnumerable vs a List, there’s not a terribly great amount of difference, but you’re going to need some extra code to determine if the GridPosition is contained in the results…
Let’s write a couple of the IEnumerables to get started.
First, in BaseAction, you’re going to need the abstract reference:
public abstract IEnumerable<GridPosition> GetValidActionGridPositions();
I’m also going to add some helper IEnumerables to get an IEnumerable of all of the valid tiles within range, depending on the distance model:
protected IEnumerable<GridPosition> GetEuclideanTilesInRange(int range)
{
for(int x=-range; x<range+1; x++)
{
for (int z = -range; z < range + 1; z++)
{
GridPosition unitGridPosition = unit.GetGridPosition();
GridPosition testPosition = unitGridPosition + new GridPosition(x, z);
if (unitGridPosition.EuclideanDistance(testPosition) > range * 10) continue;
if (!LevelGrid.Instance.IsValidGridPosition(testPosition)) continue;
yield return testPosition;
}
}
}
protected IEnumerable<GridPosition> GetManhattanTilesInRange(int range)
{
for(int x=-range; x<range+1; x++)
{
for (int z = -range; z < range + 1; z++)
{
GridPosition unitGridPosition = unit.GetGridPosition();
GridPosition testPosition = unitGridPosition + new GridPosition(x, z);
if (unitGridPosition.ManhattanDistance(testPosition) > range * 10) continue;
if (!LevelGrid.Instance.IsValidGridPosition(testPosition)) continue;
yield return testPosition;
}
}
}
protected IEnumerable<GridPosition> GetKingTilesInRange(int range)
{
for(int x=-range; x<range+1; x++)
{
for (int z = -range; z < range + 1; z++)
{
GridPosition unitGridPosition = unit.GetGridPosition();
GridPosition testPosition = unitGridPosition + new GridPosition(x, z);
if (unitGridPosition.KingsDistance(testPosition) > range * 10) continue;
if (!LevelGrid.Instance.IsValidGridPosition(testPosition)) continue;
yield return testPosition;
}
}
}
Now in each of our Actions, we’ll need to override the GetValidActionGridPositions IEnumerable.
Here’s ShootAction.GetValidActionGridPositions()
public override IEnumerable<GridPosition> GetValidActionGridPositions()
{
GridPosition unitGridPosition = unit.GetGridPosition();
foreach (GridPosition testGridPosition in GetEuclideanTilesInRange(maxShootDistance))
{
if (!LevelGrid.Instance.HasAnyUnitOnGridPosition(testGridPosition))
{
// Grid Position is empty, no Unit
continue;
}
Unit targetUnit = LevelGrid.Instance.GetUnitAtGridPosition(testGridPosition);
if (targetUnit.IsEnemy() == unit.IsEnemy())
{
// Both Units on same 'team'
continue;
}
yield return testGridPosition;
}
}
For ShootAction, you want Euclidean distance because this is the closest you’ll get to an area like a circle around the unit (the larger the shoot distance, the more the shape will resemble a circle). By using the helper IEnumerables, we’ve cut the amount of code required dramaticallly, because the helper method has already validated the distance in Euclidean distance, and has verified it’s a valid grid position. All we need to do is rule out our own tile and return the rest.
Now if you decide later to change this to Kings or Manhattan, all you’ll need to do is change which Helper method you are using.
If you’re a SQL programmer, you could consolidate much of this logic into a literal query using System.Linq
public override IEnumerable<GridPosition> GetValidActionGridPositions()
{
GridPosition unitGridPosition = unit.GetGridPosition();
foreach (var testGridPosition in from testGridPosition
in GetEuclideanTilesInRange(maxShootDistance)
where LevelGrid.Instance.HasAnyUnitOnGridPosition(testGridPosition)
let targetUnit = LevelGrid.Instance.GetUnitAtGridPosition(testGridPosition)
where targetUnit.IsEnemy() != unit.IsEnemy()
select testGridPosition)
{
yield return testGridPosition;
}
}
But lets say for SwordAction, you only want to hit targets in Cardinal directions, no hitting those corners, then you would use
public override IEnumerable<GridPosition> GetValidActionGridPositions()
{
GridPosition unitGridPosition = unit.GetGridPosition();
foreach (GridPosition testGridPosition in GetManhattanTilesInRange(maxSwordDistance))
{
if (!LevelGrid.Instance.HasAnyUnitOnGridPosition(testGridPosition))
{
// Grid Position is empty, no Unit
continue;
}
Unit targetUnit = LevelGrid.Instance.GetUnitAtGridPosition(testGridPosition);
if (targetUnit.IsEnemy() == unit.IsEnemy())
{
// Both Units on same 'team'
continue;
}
yield return testGridPosition;
}
}
In this case, I’ve set the check to Manhattan distance, meaning that you can only move in Cardinal directions. You’ll note that the method is very similar to ShootAction, just substituting the helper method.
You’ll need to make similar IEnumerables for each Action.
Now for the fun part… You’ve got the IEnumerable, but you want to verify if a given tile is in the list
Our old code for this is:
public virtual bool IsValidActionGridPosition(GridPosition gridPosition)
{
List<GridPosition> validGridPositionList = GetValidActionGridPositionList();
return validGridPositionList.Contains(gridPosition);
}
Here is how you would normally need to do this with an IEnumerable
public virtual bool IsValidactionGridPositionTheHardWay(GridPosition gridPosition)
{
foreach (GridPosition position in GetValidActionGridPositions())
{
if (position == gridPosition) return true;
}
return false;
}
or, by adding using System.Linq; to our Usings clauses, you could do the whole thing in one line:
public virtual bool IsValidActionGridPosition(GridPosition gridPosition)
{
return GetValidActionGridPositions().Contains(gridPosition);
}
This is far from complete, but it should be a good enough start to get you up and running.
