Avia corporation. Алгоритм Флойда - Уоршелла

Это игра экономическая стратегия в которой вам необходимо распределять и оптимизировать управление пассажиропотоком построив свою успешную авиакомпанию. Игра не осложнена ненужными элементами:

контролем выбросов в окружающую среду;
установкой количества мест бизнес или эконом класса;
управлением расписанием самолетов; и др.

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

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

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

Из-за создания маршрутов в любом порядке это могло привести к хаосу и неопределенности в передвижении пассажиров. Стал вопрос в динамическом создании пути.

Поэтому мне необходимо было искать кратчайший путь после того как игрок создаст маршрут.

Для решения этой задачи я воспользовался алгоритмом Флойда — Уоршелла Википедия. Алгоритм работает пошагово, он перебирает все вершины и проверяет возможность пройти от одной к другой через текущую вершину. Алгоритм выполняется до тех пор, пока все возможные пути не будут найдены.

К примеру.

У нас есть точки и расстояния между ними. Чтобы узнать кратчайший путь нам необходимо создать матрицу расстояний. Игра разрабатывается на Unity Engine поэтому код будет на C#. Создаем двумерный массив, где 999 - это бесконечность когда точки не объединены между собой, а другие цифры это дистанция между объединенными точками.

int[,] graph = new int[6, 6] { { 999, 1, 999, 999, 999, 999}, { 1, 999, 2, 4, 4, 999}, { 999, 2, 999, 999, 999, 999}, { 999, 4, 999, 999, 2, 999}, { 999, 4, 999, 2, 999, 3}, { 999, 999, 999, 999, 3, 999}, };

Сам алгоритм поиска выглядит вот так:

int[,] distance = new int[graph.GetLength(0), graph.GetLength(1)]; int[,] finishMatrix = new int[graph.GetLength(0), graph.GetLength(1)]; for (int i = 0; i < graph.GetLength(0); ++i) { for (int j = 0; j < graph.GetLength(1); ++j) { distance[i , j] = graph[i , j]; finishMatrix[i , j] = j; } } for (int k = 0; k < graph.GetLength(0); ++k) { for (int i = 0; i < graph.GetLength(0); ++i) { if (distance[i , k] != 999) { for (int j = 0; j < graph.GetLength(1); ++j) { if (distance[i , j] > distance[i , k] + distance[k , j]) { distance[i , j] = distance[i , k] + distance[k , j]; finishMatrix[i , j] = finishMatrix[i , k]; } } } } }

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

Наконец мы его запускаем и видим результат

Мы получили финальную матрицу, и на первый взгляд не видно самого пути. Здесь уже все гораздо проще. Для поиска пути мы берем номер финишной точки к примеру это 3. Номер 3 будет столбцом, а строкой цифра 0 - это стартовая точка.

Как видно мы нашли путь от 0 до 3, но этот путь довольно легкий. Возьмем финишную точку 5

Есть два пути, но очевидно что 0,1,4,5 будет лучшим. Это просто для человека, но как это поймет программа?

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

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

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