mrgameeng/tests/MrGameEng.Simulation.Tests/Pathfinding/GridPathfinderTests.cs

using Microsoft.Xna.Framework;
using Xunit;

namespace MrGameEng.Pathfinding.Tests;

public class GridPathfinderTests
{
    private static List<Point> Path(
        IPathGrid grid,
        Point start,
        Point goal,
        PathAlgorithm algorithm = PathAlgorithm.AStar,
        GridConnectivity connectivity = GridConnectivity.Eight
    )
    {
        var pathfinder = new GridPathfinder(grid, connectivity);
        var path = new List<Point>();
        Assert.True(pathfinder.FindPath(start, goal, path, algorithm));
        return path;
    }

    private static void AssertValidPath(IPathGrid grid, List<Point> path, Point start, Point goal)
    {
        Assert.Equal(start, path[0]);
        Assert.Equal(goal, path[^1]);
        for (var i = 0; i < path.Count; i++)
        {
            Assert.True(grid.IsPassable(path[i].X, path[i].Y), $"impassable cell {path[i]}");
            if (i > 0)
            {
                var dx = Math.Abs(path[i].X - path[i - 1].X);
                var dy = Math.Abs(path[i].Y - path[i - 1].Y);
                Assert.True(
                    dx <= 1 && dy <= 1 && dx + dy > 0,
                    $"non-adjacent step {path[i - 1]} -> {path[i]}"
                );
            }
        }
    }

    [Theory]
    [InlineData(PathAlgorithm.AStar)]
    [InlineData(PathAlgorithm.Dijkstra)]
    [InlineData(PathAlgorithm.BreadthFirst)]
    public void FindPath_OpenField_StraightLine(PathAlgorithm algorithm)
    {
        var grid = new TestGrid(".....", ".....", ".....");

        var path = Path(grid, new Point(0, 1), new Point(4, 1), algorithm);

        AssertValidPath(grid, path, new Point(0, 1), new Point(4, 1));
        Assert.Equal(5, path.Count); // прямая, без лишних шагов
    }

    [Theory]
    [InlineData(PathAlgorithm.AStar)]
    [InlineData(PathAlgorithm.Dijkstra)]
    [InlineData(PathAlgorithm.BreadthFirst)]
    public void FindPath_WallsForceDetour(PathAlgorithm algorithm)
    {
        var grid = new TestGrid(".....", "####.", ".....");

        var path = Path(grid, new Point(0, 0), new Point(0, 2), algorithm);

        AssertValidPath(grid, path, new Point(0, 0), new Point(0, 2));
        Assert.Contains(new Point(4, 1), path); // единственный проход
    }

    [Fact]
    public void FindPath_NoRoute_ReturnsFalse()
    {
        var grid = new TestGrid(".#.", ".#.", ".#.");
        var pathfinder = new GridPathfinder(grid);
        var path = new List<Point>();

        Assert.False(pathfinder.FindPath(new Point(0, 0), new Point(2, 0), path));
        Assert.Empty(path);
    }

    [Fact]
    public void FindPath_StartEqualsGoal_SinglePoint()
    {
        var grid = new TestGrid("...");

        var path = Path(grid, new Point(1, 0), new Point(1, 0));

        Assert.Equal([new Point(1, 0)], path);
    }

    [Fact]
    public void FindPath_DiagonalNeverCutsCorners()
    {
        var grid = new TestGrid(".#", "#.");
        var pathfinder = new GridPathfinder(grid, GridConnectivity.Eight);
        var path = new List<Point>();

        // Диагональ (0,0)->(1,1) зажата стенами — пути нет.
        Assert.False(pathfinder.FindPath(new Point(0, 0), new Point(1, 1), path));
    }

    [Fact]
    public void FindPath_FourConnectivity_NoDiagonalSteps()
    {
        var grid = new TestGrid("...", "...", "...");

        var path = Path(
            grid,
            new Point(0, 0),
            new Point(2, 2),
            connectivity: GridConnectivity.Four
        );

        Assert.Equal(5, path.Count); // манхэттен: 4 шага
        for (var i = 1; i < path.Count; i++)
        {
            var dx = Math.Abs(path[i].X - path[i - 1].X);
            var dy = Math.Abs(path[i].Y - path[i - 1].Y);
            Assert.Equal(1, dx + dy);
        }
    }

    [Theory]
    [InlineData(PathAlgorithm.AStar)]
    [InlineData(PathAlgorithm.Dijkstra)]
    public void FindPath_CostAware_AvoidsExpensiveTerrain(PathAlgorithm algorithm)
    {
        // Прямой путь через болото (цена 9) дороже обхода по краю.
        var grid = new TestGrid(".....", ".999.", ".....");

        var path = Path(grid, new Point(0, 1), new Point(4, 1), algorithm);

        Assert.DoesNotContain(path, p => grid.Cost(p.X, p.Y) > 1f);
    }

    [Fact]
    public void FindPath_BreadthFirst_IgnoresCosts()
    {
        var grid = new TestGrid(".....", ".999.", ".....");

        var path = Path(grid, new Point(0, 1), new Point(4, 1), PathAlgorithm.BreadthFirst);

        Assert.Equal(5, path.Count); // идёт напрямик через дорогие клетки
    }

    [Fact]
    public void FindPath_ReusedInstance_GivesCleanResults()
    {
        var grid = new TestGrid(".....", ".###.", ".....");
        var pathfinder = new GridPathfinder(grid);
        var path = new List<Point>();

        Assert.True(pathfinder.FindPath(new Point(0, 0), new Point(4, 2), path));
        var first = path.ToArray();
        Assert.True(pathfinder.FindPath(new Point(0, 0), new Point(4, 2), path));

        Assert.Equal(first, path); // generation-сброс не оставляет мусора между запросами
    }

    [Fact]
    public void FindPath_AStarMatchesDijkstraCost()
    {
        var grid = new TestGrid("..3..", ".#3#.", "..3..", ".###.", ".....");
        var start = new Point(0, 0);
        var goal = new Point(4, 4);

        var aStar = Path(grid, start, goal, PathAlgorithm.AStar);
        var dijkstra = Path(grid, start, goal, PathAlgorithm.Dijkstra);

        Assert.Equal(PathCost(grid, dijkstra), PathCost(grid, aStar), 3);
    }

    private static float PathCost(IPathGrid grid, List<Point> path)
    {
        var total = 0f;
        for (var i = 1; i < path.Count; i++)
        {
            var diagonal = path[i].X != path[i - 1].X && path[i].Y != path[i - 1].Y;
            total += (diagonal ? 1.4142135f : 1f) * grid.Cost(path[i].X, path[i].Y);
        }

        return total;
    }
}