Модификация Wave алгоритма + Tilemap

Идея заключается в следующем, объединить возможности Tilemap Unity и волновой алгоритм. Tilemap позволяет быстро нарисовать карту и в нем уже есть своя сетка, вопрос заключается в том, чтобы совместить «сетку» 2D массива и сетку Tilemap. Кроме этого, у волнового алгоритма, есть недостаток в том, что каждая итерация, это проход всего массива. Поэтому, мы решили модифицировать алгоритм так, чтобы вместо прохода массива, делалась проверка только пограничных элементов. Таким образом, нагрузка на систему будет возрастать не от размера самого массива, а от удаления точки поиска.


В чем отличие нашей версии волнового алгоритма? Возьмем 2D массив 100х100, во время поиска пути, каждая итерация это проверка всех элементов массива, а что будет если у нас двумерный массив размером 1000х1000? Нагрузка на систему в этом случае значительно выше. Наша модификация позволяет проверять пограничные элементы, от точки поиска, без необходимости проверять весь массив. Например, если смотреть на сетку, в центре которой находится искомый объект, то если удалить точку старта на 50 клеток, значит что радиус поиска будет 50х2=100, то есть, даже если сам массив имеет размеры 1000х1000, алгоритм будет ограничен обходом лишь 100 клеток. И это значительно увеличивает поиск в больших массивах. Однако, нужно не забывать, что удаление от точки поиска, будет означать и рост нагрузки на систему.

Подготовка. Добавляем на сцену Tilemap:

Модификация Wave алгоритма + Tilemap

В настройках решетки Grid можно поменять размер клеток под спрайты, другие параметры оставляем как есть, это важно (!) для корректной работы алгоритма.

Далее, вешаем на объект Grid наш скрипт:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
[RequireComponent(typeof(Grid))]
public class Tilemap2DPathfinding : MonoBehaviour {

    [SerializeField] private Grid grid;
    [SerializeField] private int width = 30;
    [SerializeField] private int height = 30;
    [SerializeField] private LayerMask wallMask;
    [SerializeField] private Transform cursor;
    [SerializeField] private Transform player;
    private Node[,] levelMap;
    private List<Node> path;
    private Camera cam;
    private Vector2Int target;
    private Vector3 lastPos;

    struct Node
    {
        public int x;
        public int y;
        public int cost;
    }

    void Initialize()
    {
        player.position = CellPosition(player.position);
        cam = Camera.main;
        levelMap = new Node[width, height];
        GlobalMapRefresh();
    }

    void GlobalMapRefresh() // снимок карты, фиксируем проходимые и не проходимые участки
    {
        float posX = -grid.cellSize.x * width / 2f - grid.cellSize.x / 2f;
        float posY = grid.cellSize.y * height / 2f - grid.cellSize.y / 2f;
        float Xreset = posX;
        
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                posX += grid.cellSize.x;
                levelMap[x, y].cost = -1;
                if (Physics2D.OverlapPoint(new Vector2(posX, posY), wallMask)) levelMap[x,y].cost = -2;
                levelMap[x, y].x = x;
                levelMap[x, y].y = y;
            }

            posY -= grid.cellSize.y;
            posX = Xreset;
        }
    }

    void OnDrawGizmos()
    {
        Gizmos.color = Color.yellow;
        Gizmos.DrawWireCube(transform.position, new Vector3(width * grid.cellSize.x, height * grid.cellSize.y, 1));

        // отрисовка пути в редакторе
        if (path != null && path.Count > 0)
        {
            for (int i = 0; i < path.Count; i++)
            {
                Gizmos.color = new Color(0, 255, 0, .25f);
                Vector2Int pos = ConvertToWorld(path[i]);
                Gizmos.DrawCube(new Vector3(pos.x * grid.cellSize.x + grid.cellSize.x / 2f, pos.y * grid.cellSize.y + grid.cellSize.y / 2f, 0), new Vector3(grid.cellSize.x, grid.cellSize.y, 1));
            }
        }
    }

    void OnValidate()
    {
        grid = GetComponent<Grid>();
        if (player) player.position = CellPosition(player.position);
        width = Mathf.Abs(width);
        height = Mathf.Abs(height);
        width = GetEvenInteger(width);
        height = GetEvenInteger(height);
        transform.position = Vector3.zero;
    }

    int GetEvenInteger(int value) // преобразовать в четное число
    {
        if (value % 2 == 0) return value; else return value - 1;
    }

    void Awake()
    {
        Initialize();
    }

    Vector2Int ConvertToMap(Vector3Int cellPos) // конвертировать позицию клетки в соответствие позиции элементу 2D массива
    {
        return new Vector2Int(cellPos.x + width / 2, (-cellPos.y + height / 2) - 1);
    }

    Vector2Int ConvertToWorld(Node cell) // конвертировать позицию элемента 2D массива в соответствие позиции клетки
    {
        return new Vector2Int(cell.x - width / 2, -(cell.y - height / 2) - 1);
    }

    Vector3 CellPosition(Vector3 position) // получаем позицию клетки решетки Grid
    {
        position.z = 0;
        Vector3Int pos = grid.WorldToCell(position);
        target = ConvertToMap(pos);
        return new Vector3(pos.x * grid.cellSize.x + grid.cellSize.x / 2f, pos.y * grid.cellSize.y + grid.cellSize.y / 2f, 0);
    }

    void MapRefresh() // обновление проходимых участков карты
    {
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                if (levelMap[x, y].cost >= 0) levelMap[x, y].cost = -1;
            }
        }
    }

    void LateUpdate()
    {
        Vector3 cursorPosition = CellPosition(cam.ScreenToWorldPoint(Input.mousePosition));

        if (target.x >= 0 && target.x < width && target.y >= 0 && target.y < height)
        {
            cursor.position = cursorPosition;

            if (cursor.position != lastPos)
            {
                MapRefresh();
                path = FindPath(ConvertToMap(grid.WorldToCell(player.position)), target, levelMap, width, height, true);  
            }

            lastPos = cursor.position;
        }
    }

    List<Node> FindPath(Vector2Int start, Vector2Int end, Node[,] map, int mapWidth, int mapHeight, bool diagonally)
    {
        int x, y, cost = 0, step = 0;

        if (map[end.x, end.y].cost == -2) return null;

        if (start.x - 1 >= 0)
        {
            if (map[start.x - 1, start.y].cost == -2) step++;
        }
        else step++;

        if (start.y - 1 >= 0)
        {
            if (map[start.x, start.y - 1].cost == -2) step++;
        }
        else step++;

        if (start.x + 1 < mapWidth)
        {
            if (map[start.x + 1, start.y].cost == -2) step++;
        }
        else step++;

        if (start.y + 1 < mapHeight)
        {
            if (map[start.x, start.y + 1].cost == -2) step++;
        }
        else step++;

        if (step == 4) return null; else step = 0; // проверка на доступность (например, юнит окружен)
        map[end.x, end.y].cost = 0; // начало поиска с точки назначения
        List<Node> result = new List<Node>(); // массив цикла поиска
        result.Add(map[end.x, end.y]);

        while (true) // цикл поиска
        {
            for (int i = 0; i < result.Count; i++)
            {
                if (map[result[i].x, result[i].y].cost == step) // находим клетку, соответствующую текущему шагу
                {
                    if (result[i].x - 1 >= 0) // если не выходим за границы массива
                        if (map[result[i].x - 1, result[i].y].cost == -1) // если клетка еще не проверялась
                        {
                            cost = step + 1; // сохраняем стоимость клетки
                            map[result[i].x - 1, result[i].y].cost = cost; // назначаем стоимость
                            result.Add(map[result[i].x - 1, result[i].y]); // добавляем эту клетку в цикл поиска
                        }

                    if (result[i].y - 1 >= 0)
                        if (map[result[i].x, result[i].y - 1].cost == -1)
                        {
                            cost = step + 1;
                            map[result[i].x, result[i].y - 1].cost = cost;
                            result.Add(map[result[i].x, result[i].y - 1]);
                        }

                    if (result[i].x + 1 < mapWidth)
                        if (map[result[i].x + 1, result[i].y].cost == -1)
                        {
                            cost = step + 1;
                            map[result[i].x + 1, result[i].y].cost = cost;
                            result.Add(map[result[i].x + 1, result[i].y]);
                        }

                    if (result[i].y + 1 < mapHeight)
                        if (map[result[i].x, result[i].y + 1].cost == -1)
                        {
                            cost = step + 1;
                            map[result[i].x, result[i].y + 1].cost = cost;
                            result.Add(map[result[i].x, result[i].y + 1]);
                        }
                }
            }

            step++;

            if (map[start.x, start.y].cost != -1) break; // если путь найден, выходим из цикла
            if (step != cost || step > mapWidth * mapHeight) return null; // если путь найти невозможно
        }

        result.Clear();

        // начало поиска со старта
        x = start.x;
        y = start.y;

        step = map[x, y].cost; // определяем базовую стоимость
        result.Add(map[x, y]);

        while (x != end.x || y != end.y) // прокладка пути
        {
            if (diagonally) // если разрешен поиск по диагонали
            {
                if (x - 1 >= 0 && y - 1 >= 0) // если не выходим за границы массива
                    if (map[x - 1, y - 1].cost >= 0) // если клетка проходима
                        if (map[x - 1, y - 1].cost < step) // если эта клетка дешевле, базовой стоимости
                        {
                            step = map[x - 1, y - 1].cost; // новая базовая стоимость
                            result.Add(map[x - 1, y - 1]); // добавляем клетку в массив пути
                            x--;
                            y--;
                            continue; // переходим на следующий цикл
                        }

                if (y - 1 >= 0 && x + 1 < mapWidth)
                    if (map[x + 1, y - 1].cost >= 0)
                        if (map[x + 1, y - 1].cost < step)
                        {
                            step = map[x + 1, y - 1].cost;
                            result.Add(map[x + 1, y - 1]);
                            x++;
                            y--;
                            continue;
                        }

                if (y + 1 < mapHeight && x + 1 < mapWidth)
                    if (map[x + 1, y + 1].cost >= 0)
                        if (map[x + 1, y + 1].cost < step)
                        {
                            step = map[x + 1, y + 1].cost;
                            result.Add(map[x + 1, y + 1]);
                            x++;
                            y++;
                            continue;
                        }

                if (y + 1 < mapHeight && x - 1 >= 0)
                    if (map[x - 1, y + 1].cost >= 0)
                        if (map[x - 1, y + 1].cost < step)
                        {
                            step = map[x - 1, y + 1].cost;
                            result.Add(map[x - 1, y + 1]);
                            x--;
                            y++;
                            continue;
                        }
            }

            if (x - 1 >= 0)
                if (map[x - 1, y].cost >= 0)
                    if (map[x - 1, y].cost < step)
                    {
                        step = map[x - 1, y].cost;
                        result.Add(map[x - 1, y]);
                        x--;
                        continue;
                    }

            if (y - 1 >= 0)
                if (map[x, y - 1].cost >= 0)
                    if (map[x, y - 1].cost < step)
                    {
                        step = map[x, y - 1].cost;
                        result.Add(map[x, y - 1]);
                        y--;
                        continue;
                    }

            if (x + 1 < mapWidth)
                if (map[x + 1, y].cost >= 0)
                    if (map[x + 1, y].cost < step)
                    {
                        step = map[x + 1, y].cost;
                        result.Add(map[x + 1, y]);
                        x++;
                        continue;
                    }

            if (y + 1 < mapHeight)
                if (map[x, y + 1].cost >= 0)
                    if (map[x, y + 1].cost < step)
                    {
                        step = map[x, y + 1].cost;
                        result.Add(map[x, y + 1]);
                        y++;
                        continue;
                    }

            return null; // текущая клетка не прошла проверку, ошибка
        }

        return result; // возвращаем найденный маршрут
    }
}
На старте, скрипт делает снимок карты, чтобы определить проходимые и непроходимые участки, поэтому это нужно учитывать во время создания карты. Нужно выделить один Tilemap для рисования непроходимых мест, и повесить на этот тайлмап коллайдер с отдельной маской, ее мы указываем потом в настройках скрипта.

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

Скачать демо проект:

Внимание! Посетители, находящиеся в группе Гости, не могут скачивать файлы.
Тестировалось на: Unity 2018.1.6
Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.
  • Дешевый хостинг
  • Яндекс.Метрика