Это игра экономическая стратегия в которой вам необходимо распределять и оптимизировать управление пассажиропотоком построив свою успешную авиакомпанию. Игра не осложнена ненужными элементами:
- контролем выбросов в окружающую среду;
- установкой количества мест бизнес или эконом класса;
- управлением расписанием самолетов; и др.
В этой статье я расскажу, об основной игровой механике, без которой не было бы этой игры. Речь пойдет о системе пересадки пассажиров.
Посчитав максимальное количество потенциальных маршрутов, оно составило бы 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 будет лучшим. Это просто для человека, но как это поймет программа?
Отлично, мы нашли путь по нашей предварительно подготовленной матрице. Как я писал выше, вариант с просчетом путей заранее не подходит, следовательно я написал свой довольно сложный алгоритм по созданию матрицы дистанций.
Кстати можете сами поискать путь из других точек, стартовая и конечная может быть любая.
Теперь наши пассажиры могут спокойно добраться до пункта назначения если даже туда нет прямого рейса.
Игра выйдет 9 июня 2023 в Стим, Nintendo eShop, IOS, Android
Добавляйте в вишлисты
