Графы – Волновой алгоритм

Занимался я тут на днях знакомством с графами. Нет, те графы, которые титул, а другие. Попался мне пример, в котором нужно было реализовать распространение огня применив волновой алгоритм. И я подумал, а почему бы мне не сделать это в юнити. Во-первых, работа алгоритма будет более наглядна, чем в консоли. Во-вторых, лишней практика использования юнити не будет. И в-третьих, получится подходящий материал для статьи на сайт. Трех зайцев так сказать… Ну и вот я пишу статью.

Задача.

Задача будет следующей. У нас имеется некоторое поле, клетки которого могут быть трех типов: воспламеняемыми; невоспламеняемыми и горящими. Если мы кликаем по воспламеняемой клетке, она загорается (меняет состояние на «горящая»), и перебрасывает пламя на соседние воспламеняемые клетки, а те в свою очередь перекидывают огонь на своих воспламеняемых соседей. Невоспламеняемые клетки, как понятно не горят и огонь не передают.

Подготавливаем проект.

Роль клеток у нас будут играть обычные примитивы кубы, совокупность которых будет составлять поле. Для визуального отображения состояния клетки нам понадобятся материалы. Создаем папку Mats и в ней три материала: Grey, Green, Red (с соответствующими цветами) для состояний «воспламеняемый», «невоспламеняемый» и «горящий» соответственно. Так же создадим папки «Scripts» и «Prefabs». Сразу заготовим префаб клетки: создадим скрипт CubeScript; создаем куб и вешаем на него скрипт. После нескольких экспериментов, я пришел к выводу, что в данном конкретном примере, удобнее всего будет хранить ссылки на материалы именно в кубе. Поэтому в скрипте CubeScript добавим поле:

public Material[] Materials;

И в инспекторе прилинкуем к нему ранее подготовленные материалы. Важно, я их прилинковал в таком порядке сверху вниз: Grey, Green, Red т.ч. если у вас в конце цвета будут отображаться некорректно, возможно вы ошиблись с порядком. Можно конечно заморочиться и реализовать произвольный порядок, но в данном примере оно того не стоит. Ладно-ладно, мне лениво. :-) Сохраняем префаб и удаляем из сцены, он нам больше не понадобится.

Интерфейс взаимодействия с графом.

Сразу скажу, что первый рабочий пример был без лишних заморочек в том числе и интерфейсов. Но чтоб не растягивать статью, и не напрягать читателя рефакторингом, давайте сразу создадим интерфейс. Он необходим хотя бы ради того, чтоб упростить код класса графа. А во-вторых, сделать его более независимым от «горящих» объектов т.е. благодаря интерфейсу, мы сможем поджигать любой объект реализующий интерфейс.

Интерфейс я назвал ICombustible, в нем 2 свойства только на чтение и метод. Вот его код:

public interface ICombustible
{
    bool IsCombustible { get; } //Воспламеняемый ли объект
    bool IsBurnt { get; }       //Горит ли объект в данный момент
    void SetFire(int serialBurn); //Поджечь объект
}

В скрипте CubeScript унаследуемся от него:

public class CubeScript : MonoBehaviour, ICombustible

Чтобы не было ошибок, сразу реализуем интерфейс:

public bool IsCombustible
{
    get { return _isCombustible; }
}
 
public bool IsBurnt
{
    get { return _isBurnt; }
}
 
public void SetFire(int serialBurn)
{
    //Временная заглушка
    throw new System.NotImplementedException();
}
 
private bool _isBurnt;
private bool _isCombustible;

Метод SetFire() реализуем позже.

Инициализируем поле.

Теперь мы можем создать поле. Создаваться от будет программно, и заниматься этим будет скрипт InitScript. Создадим его и повесим на камеру. Для начала нам понадобятся три поля:

public int Size;
public GameObject Cube;
private ICombustible[,] _field;

В первом, мы через инспектор будем создавать длину стороны поля в клетках (для простоты, у нас будет квадратное поле). Во втором, мы прилинкуем ранее созданный префаб клетки. Ну и третье поле олицетворяет наше «реальное поле» в коде, это двумерный массив объектов ICombustible.

Теперь напишем метод инициализирующий наше поле:

void Start()
{
    if (Size > 0)
    {
        _field = new ICombustible[Size, Size];
        for (int y = 0; y < Size; y++)
        {
            for (int x = 0; x < Size; x++)
            {
                GameObject newGameObject = Instantiate(Cube);
                newGameObject.transform.position = new Vector3(x, y);
                _field[x, y] = newGameObject.GetComponent<CubeScript>();
            }
        }
    }
}

Думаю, код не нуждается в объяснении, мы просто в цикле инстанцируем кубики по координатам, соответствующим их индексам в массиве, и помещаем в массив ссылку на объект (тут стоит отметить что, хотя мы и помещаем в массив ссылку на компонент CubeScript, но он автоматически приводится к типу массива т.е. ICombustible).

Теперь если в инспекторе задать значение поля Size, и запустить игру, у нас появится стена из кубиков. Осторожно со значениями, у меня при значении 500 юнити виснет намертво.  :roll: Подберите комфортное число для себя и отпозиционируйте камеру, чтоб вся стена попадала в поле зрения. Я остановился на числе 50.

Делаем поле неоднородным.

Теперь нам нужно задать свойства нашим кубикам-клеточкам, воспламеняемые/невоспламеняемые и цвет. Для этого в скрипте CubeScript пишем метод:

void Start()
{
    int randomNum = Random.Range(1, 9);
    _isCombustible = randomNum % 2 == 0;
    GetComponent<Renderer>().sharedMaterial = IsCombustible ? Materials[1] : Materials[0];
}

Тут мы на основе четности/нечетности случайного числа randomNum, задаем «горибельный» кубик или нет, и назначаем соответствующий материал. Возможно у вас возникнет конфликт неймспейсов из-за класса Random, в этом случае либо удалите неиспользуемые юзинги, либо пропишите в юзингах следующую строку:

using Random = UnityEngine.Random;

Теперь если мы запусти игру, поле уже будет не однородным.

Реализовываем волновой алгоритм.

А теперь собственно то, ради чего всё это затевалось. Создадим класс Graph. Он будет работать с нашим массивом объектов ICombustible. Поэтому создаем 2 поля и конструктор:

private ICombustible[,] _field;
private int _sideCount;

public Graph(ICombustible[,] field)
{
    _sideCount = (int)field.GetLongLength(0);
    _field = field;
}

Далее идет метод запускающий расчет:

public void StartWave(Vector2DInt startPoint)
{
    Queue<Vector2DInt> queue = new Queue<Vector2DInt>();
    queue.Enqueue(new Vector2DInt(startPoint.x, startPoint.y));
    int numWave = 1;
 
    _field[startPoint.x, startPoint.y].SetFire(numWave);
 
    while (queue.Count > 0)
    {
        numWave++;
        for (int i = queue.Count; i > 0; i--)
        {
            _OneWave(queue, queue.Dequeue(), numWave);
        }
    }
}

Метод принимает объект-координату – точка, откуда начинается «возгорание».

Не большое отступление. Класс Vector2DInt – это класс, который я написал, чтобы упростить вид кода. Вместо него можно использовать юнитовский Vector2, например, но он для меня оказался неудобным т.к. координаты в нем хранятся во float, и постоянные приведения к int загромождали код. Этот класс выглядит так:

public class Vector2DInt
{
    public int x;
    public int y;
 
    public Vector2DInt(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
 
    public static Vector2DInt operator +(Vector2DInt a, Vector2DInt b)
    {
        return new Vector2DInt(a.x + b.x, a.y + b.y);
    }
 
    public static Vector2DInt operator -(Vector2DInt a, Vector2DInt b)
    {
        return new Vector2DInt(a.x - b.x, a.y - b.y);
    }
}

Как видите он поддерживает сложение и вычитание координат, и этого пока достаточно.

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

Далее мы поджигаем кубик с координатами стартовой точки, вызывая метод SetFire(). В метод мы передаем номер волны.

На каждом проходе цикла while увеличиваем номер волны. Извлекаем из очереди одну точку и добавляем соседние ей точки (не все, конкретнее смотрите метод _OneWave()). И так до тех пор, пока в очереди не кончатся точки. Цикл for нужен для отделения одной волны от другой.

private void _OneWave(Queue<Vector2DInt> queue, Vector2DInt point, int numWave)
{
    foreach (Vector2DInt offset in _offsets)
    {
        Vector2DInt newPoint = point + offset;
 
        if (_IsValid(newPoint)
            && _field[newPoint.x, newPoint.y].IsCombustible
            && !_field[newPoint.x, newPoint.y].IsBurnt)
        {
            _field[newPoint.x, newPoint.y].SetFire(numWave);
            queue.Enqueue(new Vector2DInt(newPoint.x, newPoint.y));
        }
    }
}

Метод _OneWave() принимает в качестве параметров очередь с которой мы работаем и точку, соседей которой мы проверяем. Т.е. нам нужно проверить 8 точек: клеточка (x, y+1); клеточка (x+1, y+1); и т.д. по часовой стрелке (или против, это не важно). Чтобы такое можно было проделать в цикле, добавим в класс массив смещений _offsets:

private readonly Vector2DInt[] _offsets =
{
    new Vector2DInt(0, 1),
    new Vector2DInt(1, 1),
    new Vector2DInt(1, 0),
    new Vector2DInt(1, -1),
    new Vector2DInt(0, -1),
    new Vector2DInt(-1, -1),
    new Vector2DInt(-1, 0),
    new Vector2DInt(-1, 1)
};

Ну и далее в цикле создаем смещенную точку и проверяем не выходит ли она за пределы поля (_IsValid()), может ли она гореть, не сгорела ли она ранее. Если все проверки проходят, поджигаем ее и добавляем ее координаты в очередь.

Метод проверки, не выходит ли точка за пределы массива выглядит так:

private bool _IsValid(Vector2DInt point)
{
    return (point.x > -1 && point.y > -1 && point.x < _sideCount && point.y < _sideCount);
}

Запуск расчета.

Поджигать кубики мы планировали по клику. Реализовать это можно по-разному, но я остановился на способе через события. При клике на кубике, оно будет генерировать событие со ссылкой на себя, а InitScript будет его ловить и обрабатывать. Для этого в CubeScript добавим два поля:

void OnMouseDown()
{
    if (CubeClickEvent != null && IsCombustible && !IsBurnt)
    {
        CubeClickEvent.Invoke(this);
    }
}

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

В InitScript нам нужно подписаться на событие и обработать его. Добавим поле:

private Graph _graph;

И в методе Start(), после инициализации массива _field, создаем объект графа и подписываемся на событие:

_graph = new Graph(_field);
CubeScript.CubeClickEvent += OnCubeClick;

Если вам не понятно, как работают события в C#, могу порекомендовать эту статью – https://habrahabr.ru/post/213809/

Теперь реализуем обработчик:

private void OnCubeClick(CubeScript sender)
{
    _graph.StartWave(new Vector2DInt((int)sender.transform.position.x, (int)sender.transform.position.y));
}

Если сейчас запустить игру, она зациклится и зависнет т.к. состояние кубиков не меняется, и они будут вечно попадать в очередь. Чтобы этого не было, необходимо реализовать метод SetFire()

public void SetFire(int serialBurn)
{
    if (!IsCombustible || IsBurnt)
        return;
 
    _serialBurn = serialBurn;
    _isBurnt = true;
    GetComponent<Renderer>().sharedMaterial = Materials[2];
}

Так же в класс CubeScript, нужно добавить поле и свойство:

public int Serial
{
    get { return _serialBurn; }
}
 
private int _serialBurn;

Они нужны чтобы пометить к какой волне относится куб. В методе SetFire() мы проверяем сгораемый ли кубик и не сгоревший ли он уже. Далее отмечаем кубик как сгоревший и задаем номер волны. Последняя строка, меняющая материал кубика добавлена для теста, чтоб мы уже могли заценить, как всё работает и работает ли.

Если вы все правильно сделали, то теперь запустив игру и кликнув на любом зеленом кубике, вся область, связанная с ним, окрасится в красный. Правда произойдет это моментально, не похоже на распространение огня, больше похоже на заливку цветом, определённой цветовой области. Для этого нам и понадобится номер волны.

Пускаем волны.

Нам снова понадобится очередь. Добавим в класс CubeScript поле:

public static Queue<CubeScript> BurnQueue;

И проинициализируем его в методе Start() таким образом:

if (BurnQueue == null)
        BurnQueue = new Queue<CubeScript>();

Теперь вынесем строку с переменой материала из метода SetFire() в отдельный метод:

public void StartBurn()
{
    GetComponent<Renderer>().sharedMaterial = Materials[2];
}

А в место нее, в метод SetFire() добавим строку:

BurnQueue.Enqueue(this);

Как вы, наверное, уже поняли, мы забиваем очередь кубиками в порядке возрастания волны, во время работы графа. Теперь нам нужно лишь написать метод, который будет последовательно окрашивать волну за волной. Но сначала нам нужно как-то узнать, что граф окончил расчет. Воспользуемся опять событийной системой. В класс Graph добавим 2 поля:

public delegate void EndWave();
public event EndWave EndWaveEvent;

И в методе StartWave() генерируем событие:

if (EndWaveEvent != null)
     EndWaveEvent.Invoke();

Я поместил вызов в конец метода, но в принципе, можно поместить и в конец цикла while, тогда событие будет генерироваться после каждой волны. Но такое решение потребует другой реализации обработчика. Это уже можете потом сами поэкспериментировать, пока сделаем, по-моему.

В скрипте InitScript подпишемся на событие, в методе старт, после инициализации графа:

_graph.EndWaveEvent += OnEndWave;

И напишем обработчик:

private void OnEndWave()
{
    StartCoroutine(_BurnQueue());
}

Здесь мы в корутине запускаем метод, который перекрашивает кубики в очереди с паузами между волнами:

private IEnumerator _BurnQueue()
{
    int numWave = 1;
    while (CubeScript.BurnQueue.Count > 0)
    {
        CubeScript cube = CubeScript.BurnQueue.Dequeue();
 
        if (cube.Serial > numWave)
        {  //Если пошла другая волна, делаем паузу и увеличиваем счетчик волн
            yield return new WaitForSeconds(SpeedWave);
            numWave++;
        }
 
        cube.StartBurn();
    }
}

Переменная SpeedWave, это поле, которое я добавил, чтоб иметь возможность задавать скорость распространения волны в секундах, из инспектора.

public float SpeedWave;

Вот теперь, все работает, как и задумывалось.

Спасибо за внимание.

Проект на гитхабе – https://github.com/LonelyWolf2000/freedevgame.ru-Unity-WaveAlg

Добавить комментарий