paper-racing-gpi/README.md

Гонки на бумаге (Paper Racing / Vector Racing)

🏁 Описание задачи

Классическая игра "гонки на бумаге" - это задача поиска оптимального пути на декартовом поле.

🚀 Две реализации

Проект содержит две версии алгоритма решения:

1. BFS (Program.cs) - Поиск в ширину, гарантирует оптимальное решение
2. A* (ProgramAStar.cs) - Эвристический поиск, в 5-10 раз быстрее на больших картах

Правила:

1. Поле: Квадратное декартово поле с координатами
2. Цель: Пройти через все чекпоинты за минимальное количество ходов (в любом порядке)
3. Движение: На каждом шаге указывается вектор ускорения (целочисленный)
   • Можно изменить скорость на -1, 0 или +1 по каждой оси (X и Y)
   • Новая позиция = текущая позиция + скорость
4. Препятствия: Есть препятствия, через которые нельзя проезжать
5. Физика: Автомобиль имеет инерцию - скорость сохраняется между ходами

Пример физики движения:

Шаг 0: Позиция=(1,1), Скорость=(0,0), Ускорение=(0,0)
Шаг 1: Позиция=(2,2), Скорость=(1,1), Ускорение=(1,1)
Шаг 2: Позиция=(4,4), Скорость=(2,2), Ускорение=(1,1)
Шаг 3: Позиция=(6,5), Скорость=(2,1), Ускорение=(0,-1)

Реализация

Программа использует алгоритм BFS (Breadth-First Search) для поиска оптимального решения.

Ключевые компоненты:

1. Point - представляет координаты на поле
2. GameState - состояние игры (позиция, скорость, посещенные чекпоинты)
3. RaceTrack - игровое поле с логикой поиска решения
4. Алгоритм Брезенхема - для проверки пересечения с препятствиями

📦 Быстрый старт

Использование интерактивного скрипта:

./run.sh

Или напрямую:

BFS версия:

dotnet run --project racing.csproj

A версия (рекомендуется для больших карт):*

dotnet run --project racing-astar.csproj

🗺️ Редактор карт

Для создания своих карт используйте веб-редактор в папке map-editor/:

cd map-editor
./open-editor.sh  # или просто откройте index.html в браузере

Возможности редактора:

• ✅ Визуально создавать карты любого размера (5×5 до 100×100)
• ✅ 6 типов ячеек: дорога, камень, снег, лёд, чекпоинт, старт
• ✅ Экспортировать/импортировать карты в формате JSON
• ✅ Пошаговая визуализация решений
• ✅ Анимация движения с векторами скорости
• ✅ Регулируемая скорость воспроизведения (1x - 10x)
• ✅ Управление: Play, Pause, Reset, Step

Формат решения для визуализации:

{
  "solution": [
    [1, 1],   // векторы ускорения [ax, ay]
    [1, 0],
    [0, 1]
  ]
}

Подробнее: map-editor/README.md | Быстрый старт: map-editor/QUICKSTART.md

Модификация задачи

Вы можете изменить параметры в Program.cs:

// Размер поля
int width = 15;
int height = 15;

// Стартовая позиция
var start = new Point(1, 1);

// Чекпоинты
var checkpoints = new Dictionary<int, Point>
{
    { 1, new Point(5, 5) },
    { 2, new Point(10, 10) },
    { 3, new Point(12, 3) }
};

// Добавить препятствия
obstacles.Add(new Point(x, y));

Визуализация

S - старт
1, 2, 3 - чекпоинты
# - препятствия
. - пройденный путь

⚡ Сравнение производительности

Характеристика	BFS	A*
Скорость	Базовая	5-10x быстрее
Память	Высокая	Оптимизированная
Оптимальность	Гарантирована	Гарантирована*
Карты 15×15	Быстро	Очень быстро
Карты 42×42	Медленно	Быстро
5+ чекпоинтов	Очень медленно	Приемлемо

*При допустимой эвристике

Рекомендации:

• Для карт ≤20×20 и ≤3 чекпоинтов: любой алгоритм
• Для карт >20×20 или >3 чекпоинтов: используйте A*
• Для экспериментов и обучения: BFS проще для понимания

Подробнее см. ASTAR-README.md

🧮 Сложность

BFS

• Время: O(b^d), где b - коэффициент ветвления (~9 направлений), d - глубина
• Память: O(b^d)
• Пространство состояний: O(W × H × V² × 2^C), где:
  • W, H - размеры поля
  • V - максимальная скорость
  • C - количество чекпоинтов

A*

• Время: O(b^d) худший случай, но на практике значительно лучше
• Память: Меньше благодаря направленному поиску
• Эффективность: Зависит от качества эвристики