5dplomacy/MultiversalDiplomacy/Adjudicate/PathFinder.cs

167 lines
7.2 KiB
C#

using MultiversalDiplomacy.Model;
using MultiversalDiplomacy.Orders;
namespace MultiversalDiplomacy.Adjudicate;
/// <summary>
/// Helper class encapsulating the convoy pathfindind code.
/// </summary>
public static class PathFinder
{
/// <summary>
/// Determines if a convoy path exists for a move in a convoy order.
/// </summary>
public static bool ConvoyPathExists(World world, ConvoyOrder order)
=> ConvoyPathExists(world, world.Map.GetLocation(order.Target), order.Location, order.Season);
/// <summary>
/// Determines if a convoy path exists for a move order.
/// </summary>
public static bool ConvoyPathExists(World world, MoveOrder order)
=> ConvoyPathExists(
world,
world.Map.GetLocation(order.Unit),
world.Map.GetLocation(order.Location),
order.Season);
private static bool ConvoyPathExists(
World world,
Location unitLocation,
Location destLocation,
Season destSeason)
{
// A convoy path exists between two locations if both are land locations in provinces that
// also have coasts, and between those coasts there is a path of adjacent sea provinces
// (not coastal) that are occupied by fleets. The move order is valid even if the fleets
// belong to another power or were not given convoy orders; it will simply fail.
IDictionary<(string location, Season season), Unit> fleets = world.Units
.Where(unit => unit.Type == UnitType.Fleet)
.ToDictionary(unit => (unit.Location, unit.Season));
// Verify that the origin is a coastal province.
if (unitLocation.Type != LocationType.Land) return false;
IEnumerable<Location> originCoasts = unitLocation.Province.Locations
.Where(location => location.Type == LocationType.Water);
if (!originCoasts.Any()) return false;
// Verify that the destination is a coastal province.
if (destLocation.Type != LocationType.Land) return false;
IEnumerable<Location> destCoasts = destLocation.Province.Locations
.Where(location => location.Type == LocationType.Water);
if (!destCoasts.Any()) return false;
// Seed the to-visit set with the origin coasts. Coastal locations will be filtered out of
// locations added to the to-visit set, but the logic will still work with these as
// starting points.
Queue<(Location location, Season season)> toVisit = new(
originCoasts.Select(location => (location, destSeason)));
HashSet<(Location, Season)> visited = new();
// Begin pathfinding.
while (toVisit.Any())
{
// Visit the next point in the queue.
(Location currentLocation, Season currentSeason) = toVisit.Dequeue();
visited.Add((currentLocation, currentSeason));
var adjacents = GetAdjacentPoints(world, currentLocation, currentSeason);
foreach ((Location adjLocation, Season adjSeason) in adjacents)
{
// If the destination is adjacent, then a path exists.
if (destCoasts.Contains(adjLocation) && destSeason == adjSeason) return true;
// If not, add this location to the to-visit set if it isn't a coast, has a fleet,
// and hasn't already been visited.
if (!adjLocation.Province.Locations.Any(l => l.Type == LocationType.Land)
&& fleets.ContainsKey((adjLocation.Key, adjSeason))
&& !visited.Contains((adjLocation, adjSeason)))
{
toVisit.Enqueue((adjLocation, adjSeason));
}
}
}
// If the destination was never reached, then no path exists.
return false;
}
private static List<(Location, Season)> GetAdjacentPoints(World world, Location location, Season season)
{
List<(Location, Season)> adjacentPoints = [];
List<Location> adjacentLocations = location.Adjacents.ToList();
List<Season> adjacentSeasons = GetAdjacentSeasons(world, season).ToList();
foreach (Location adjacentLocation in adjacentLocations)
{
adjacentPoints.Add((adjacentLocation, season));
}
foreach (Season adjacentSeason in adjacentSeasons)
{
adjacentPoints.Add((location, adjacentSeason));
}
foreach (Location adjacentLocation in adjacentLocations)
{
foreach (Season adjacentSeason in adjacentSeasons)
{
adjacentPoints.Add((adjacentLocation, adjacentSeason));
}
}
return adjacentPoints;
}
/// <summary>
/// Returns all seasons that are adjacent to a season.
/// </summary>
public static IEnumerable<Season> GetAdjacentSeasons(World world, Season season)
{
var pasts = world.Timelines.Pasts;
List<Season> adjacents = [];
// The immediate past and all immediate futures are adjacent.
if (pasts[season.Key] is Season immediatePast) adjacents.Add(immediatePast);
adjacents.AddRange(world.Timelines.GetFutures(season));
// Find all adjacent timelines by finding all timelines that branched off of this season's
// timeline, i.e. all futures of this season's past that have different timelines. Also
// include any timelines that branched off of the timeline this timeline branched off from.
List<Season> adjacentTimelineRoots = [];
Season? current = season;
for (;
pasts[current?.Key!] is Season currentPast && currentPast.Timeline == current?.Timeline;
current = pasts[current?.Key!])
{
adjacentTimelineRoots.AddRange(
world.Timelines.GetFutures(current.Value).Where(s => s.Timeline != current?.Timeline));
}
// At the end of the for loop, if this season is part of the first timeline, then current
// is the root season (current.past == null); if this season is in a branched timeline,
// then current is the branch timeline's root season (current.past.timeline !=
// current.timeline). Check for co-branches if this season is in a branched timeline, since
// the first timeline by definition cannot have co-branches.
if (pasts[current?.Key!] is Season rootPast)
{
IEnumerable<Season> cobranchRoots = world.Timelines
.GetFutures(rootPast)
.Where(s => s.Timeline != current?.Timeline && s.Timeline != rootPast.Timeline);
adjacentTimelineRoots.AddRange(cobranchRoots);
}
// Walk up all alternate timelines to find seasons within one turn of this season.
foreach (Season timelineRoot in adjacentTimelineRoots)
{
for (Season? branchSeason = timelineRoot;
branchSeason is Season branch && branch.Turn <= season.Turn + 1;
branchSeason = world.Timelines
.GetFutures(branchSeason!.Value)
.Cast<Season?>()
.FirstOrDefault(s => s?.Timeline == branchSeason?.Timeline, null))
{
if (branchSeason?.Turn >= season.Turn - 1) adjacents.Add(branchSeason.Value);
}
}
return adjacents;
}
}