9.9 KiB
Гонки на бумаге - Алгоритм A* с эвристикой
🆕 Импорт карт из JSON
Программа теперь поддерживает загрузку пользовательских карт из JSON-файлов!
Быстрый старт
# Запуск со встроенной картой
dotnet run --project racing-astar.csproj
# Загрузка карты из файла
dotnet run --project racing-astar.csproj maps/your-map.json
# Пример с готовой картой
dotnet run --project racing-astar.csproj maps/open-field.json
# Экспорт решения в JSON файл
dotnet run --project racing-astar.csproj maps/your-map.json --output solution.json
# или короткая версия:
dotnet run --project racing-astar.csproj maps/your-map.json -o solution.json
Формат карты
Типы ячеек:
0- Дорога (первая ячейка становится стартом)1- Камень (препятствие)2- Снег (пока как дорога)3- Лед (пока как дорога)4- Чекпоинт
Подробная документация: см. MAP-FORMAT.md
Формат экспортированного решения
При использовании опции --output программа сохраняет найденное решение в JSON файл с векторами ускорения для каждого шага:
{
"solution": [
[0, 0],
[1, 2],
[-1, -1],
[2, 1]
]
}
Где каждый элемент массива [ax, ay] представляет собой:
ax- ускорение по оси X (от -2 до +2)ay- ускорение по оси Y (от -2 до +2)
Первый элемент всегда [0, 0] (стартовая позиция без ускорения).
Этот формат можно использовать для:
- Воспроизведения решения в редакторе карт
- Анализа найденного пути
- Сравнения разных решений
Примеры карт
maps/open-field.json- Простая открытая карта (3 чекпоинта)maps/racing-map-42x42.json- Сложная карта (59 чекпоинтов, 141 препятствие)
Сравнение алгоритмов
BFS (Breadth-First Search)
- Файл:
Program.cs - Алгоритм: Поиск в ширину
- Гарантия: Находит оптимальное решение (минимальное количество ходов)
- Производительность: Исследует все состояния на каждом уровне глубины
- Память: O(b^d), где b - коэффициент ветвления, d - глубина решения
A* (A-Star)
- Файл:
ProgramAStar.cs - Алгоритм: Поиск с эвристикой
- Гарантия: Находит оптимальное решение при допустимой эвристике
- Производительность: Направленный поиск к цели
- Память: Значительно меньше, чем BFS для больших задач
Эвристическая функция
Компоненты эвристики:
-
Для одного чекпоинта:
h = EstimateStepsToReach(distance, currentSpeed, maxAcceleration)- Учитывает текущую скорость
- Моделирует физику ускорения и торможения
- Решает квадратное уравнение движения: s = v₀t + ½at²
-
Для нескольких чекпоинтов:
h = ∑(steps to nearest unvisited checkpoint)- Жадный алгоритм TSP (задача коммивояжера)
- Последовательно выбирает ближайший непосещенный чекпоинт
- Оценивает расстояние с учетом физики движения
Свойства эвристики:
- Допустимая (admissible): Никогда не переоценивает реальную стоимость
- Согласованная (consistent): h(n) ≤ cost(n, n') + h(n')
- Информированная: Учитывает физику игры (скорость, ускорение)
Результаты
Пример задачи (4 чекпоинта, 42×42 поле):
| Метрика | BFS | A* |
|---|---|---|
| Итераций | ~100,000+ | 20,301 |
| Время | >10 сек | 1.02 сек |
| Память (макс. открытых узлов) | ~50,000+ | 10,980 |
| Решение (ходов) | Оптимальное | 27 (оптимальное) |
Преимущества A*:
✅ В 5-10 раз быстрее BFS на больших картах
✅ Значительно меньше памяти - исследует только перспективные пути
✅ Масштабируемость - может решать задачи с большим количеством чекпоинтов
✅ Адаптивность - эвристика учитывает физику игры
Запуск
BFS версия (оригинальная):
dotnet run --project racing.csproj
A* версия (оптимизированная):
dotnet run --project racing-astar.csproj
Настройка эвристики
Для более сложных карт можно настроить параметры в методе CalculateHeuristic:
// Агрессивная эвристика (быстрее, но может пропустить оптимум)
speed = 4.0; // Предполагаем более высокую среднюю скорость
// Консервативная эвристика (медленнее, но гарантирует оптимум)
speed = 2.0; // Предполагаем более низкую среднюю скорость
Формула стоимости A*
f(n) = g(n) + h(n)
где:
- f(n) = полная оценочная стоимость пути через узел n
- g(n) = фактическая стоимость пути от старта до n (количество ходов)
- h(n) = эвристическая оценка стоимости от n до цели
Детали реализации
Структура состояния:
public class GameState
{
Point Position; // Текущая позиция
Point Velocity; // Текущая скорость (с инерцией)
HashSet<int> Visited; // Посещенные чекпоинты
int GCost; // Фактические шаги
double HCost; // Эвристическая оценка
double FCost => GCost + HCost;
}
Очередь с приоритетом:
var openSet = new SortedSet<GameState>(new GameStateComparer());
Автоматически сортирует состояния по FCost, всегда извлекая самое перспективное.
Проверка дубликатов:
string key = $"{pos.X},{pos.Y}|{vel.X},{vel.Y}|{checkpointsMask}";
Уникальный ключ учитывает позицию, скорость и собранные чекпоинты.
Визуализация работы
При запуске A* показывает прогресс каждые 10,000 итераций:
Итерация 10000: OpenSet=7131, FCost=26.78, GCost=12, Посещено=1/4
Где:
- OpenSet - количество состояний в рассмотрении
- FCost - текущая минимальная оценочная стоимость
- GCost - количество фактических шагов
- Посещено - собрано чекпоинтов из общего количества
Оптимизация для больших карт
Для карт >50×50 или >5 чекпоинтов рекомендуется:
-
Увеличить maxIterations:
const int maxIterations = 5000000; -
Использовать более агрессивную эвристику:
return totalCost * 0.9; // Множитель < 1 для ускорения -
Ограничить максимальную скорость:
if (Math.Abs(newVelocity.X) > 5 || Math.Abs(newVelocity.Y) > 5) continue;
Теоретические основы
Временная сложность:
- Лучший случай: O(d), где d - глубина решения
- Средний случай: O(b^d), где b - эффективный коэффициент ветвления
- Худший случай: O(b^d) - вырождается в BFS
Пространственная сложность:
- O(b^d) для хранения открытого и закрытого множеств
- В практике значительно меньше благодаря эвристике
Условия оптимальности:
A* гарантирует оптимальное решение, если:
- h(n) ≤ h*(n) (допустимость) - эвристика не переоценивает
- h(n) ≤ c(n,n') + h(n') (согласованность) - монотонность
Наша эвристика удовлетворяет обоим условиям:
- Использует оптимистичную оценку времени (без учета препятствий)
- Монотонна относительно расстояния