Лабиринт. Волновой поиск

Склонируем предыдущий урок, но уберем возможности управления клавиатурой. Для этого уберем хендлеры обработки нажатия и поднятия кнопок, а также очистим внутри функцию обновления сцены. Давайте переделаем поведение нашего героя (шарика). Сделаем возможность нажимать мышкой на любую свободную клетку лабиринта, после этого герой должен будет сам автоматически расчитать путь туда и осуществить движение до целевой клетки.

Для поиска пути в лабиринте воспользуемся алгоритмом поиском в ширину (для квадратных сеток его часто называют волновым поиском / алгоритмом)

Объявим новые переменные необходимые для хранения фронта волны и расчитанного пути

int[,] wave = new int[16, 16]; // массив с метками волны
List<Point> path = new List<Point>(); // востановленный путь

Отрисуем путь и курсор

private void Form1_Paint(object? sender, PaintEventArgs e)
{
    var cursor = PointToClient(Cursor.Position);
    var row = (int)(cursor.Y / CellSize);
    var column = (int)(cursor.X / CellSize);

    var gr = e.Graphics;
    gr.Clear(Color.Black);
    gr.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;

    UpdateScene();            

    //draw cursor
    gr.FillRectangle(new SolidBrush(Color.FromArgb(128, Color.Green)), column * CellSize, row * CellSize, CellSize, CellSize);
    DrawPath(gr);

    //draw scene
    DrawMap(gr);
    DrawHero(gr);
}

// отрисовка пути
private void DrawPath(Graphics gr)
{
    foreach (var item in path)
    {
        gr.FillRectangle(new SolidBrush(Color.FromArgb(128, Color.Blue)), item.X * CellSize, item.Y * CellSize, CellSize, CellSize);
    }
}

Подпишемся на событие MouseUp и будем расчитывать координаты клетки на которую нажали.

private void Form1_MouseUp(object? sender, MouseEventArgs e)
{
    var cursor = PointToClient(Cursor.Position);
    var row = (int)(cursor.Y / CellSize);
    var column = (int)(cursor.X / CellSize);

    if (map[column, row] != 0) // если нажали на стену, то ничего не делаем
        return;

    BuildWave(); // строим волну
    BuildPath(column, row); // строим путь
}

Для расчета волны воспользуемся очередью. 

// функция расчета волны
private void BuildWave()
{
    wave = new int[16, 16];
    Queue<(Point, int)> q = new Queue<(Point, int)>();
    q.Enqueue(new(new Point(heroX, heroY), 1));
    while (q.Any())
    {
        var deq = q.Dequeue();
        var p = deq.Item1;

        if (map[p.X, p.Y] != 0)
            continue;

        if (wave[p.X, p.Y] != 0)
            continue;

        int level = deq.Item2;

        wave[p.X, p.Y] = level;

// добавим в очередь фронт волны от текущей позиции в 4 стороны
        q.Enqueue((new Point(p.X + 1, p.Y), level + 1));
        q.Enqueue((new Point(p.X - 1, p.Y), level + 1));
        q.Enqueue((new Point(p.X, p.Y + 1), level + 1));
        q.Enqueue((new Point(p.X, p.Y - 1), level + 1));

    }
}

Теперь построим обратный путь , пройдя от целевой точки до исходной, на каждом шаге будем переходить в клетку с меньшим значением фронта волны.

private void BuildPath(int targetX, int targetY)
{
    // build path
    path = new List<Point>();
    path.Add(new Point(targetX, targetY));
    while (true)
    {
        var point = path.First();
        int level = wave[point.X, point.Y];

        if (point.X == heroX && point.Y == heroY)
            break;

        bool exit = false;
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                if (Math.Abs(i + j) != 1)
                    continue;
                if (wave[point.X + i, point.Y + j] == level - 1)
                {
                    path.Insert(0, new Point(point.X + i, point.Y + j));
                    exit = true;
                    break;
                }

            }
            if (exit)
                break;
        }
        if (!exit) //path not found
        {
            path.Clear();
            break;
        }
    }
}

Попробуем вывести лабиринт с метками пути, чтобы визуально понять как работает волновой поиск. 

Обратите внимание в недостижимых областях все клетки промаркированы нулем, волна туда не проникла.

Теперь сделаем чтобы при обновлении сцены мы передвигались вдоль расчитанного пути

public void UpdateScene()
{            
    if (DateTime.Now.Subtract(lastMove).TotalMilliseconds <= 100)
        return;

    lastMove = DateTime.Now;
    int newHeroX = heroX;
    int newHeroY = heroY;
    if (path.Any())
    {
        var p = path.First();
        path.RemoveAt(0);

        newHeroX = p.X;
        newHeroY = p.Y;
    }

    if (map[newHeroX, newHeroY] == 0)
    {
        heroX = newHeroX;
        heroY = newHeroY;
    }
}

Запустим и проверим:

Полный код примера можно посмотреть здесь