Pacman Game (Pygame)

Классическая аркадная игра Pacman, написанная на Python с использованием библиотеки Pygame. Этот проект реализует все основные механики оригинальной игры, где поведение привидений основано на фундаментальных алгоритмах поиска пути в графах:

• DFS с ограничением глубины + Жадный алгоритм - для локального поиска вблизи Pacman
• BFS - гарантирует нахождение кратчайшего пути в невзвешенном графе лабиринта
• Алгоритм Дейкстры - учитывает "опасные" зоны (веса вершин)
• A* с эвристикой Манхэттенского расстояния для оптимизированного поиска

🔍 Особенности

• Кастомизированная карта с использованием спрайтов в стиле оригинальной игры
• Управление с помощью стрелок
• Система подсчёта очков
• Четыре типа привидений с уникальным поведением (см. раздел Поведение привидений)

👻 Поведение привидений

Каждое привидение реализует уникальный алгоритм поиска пути:

1. Inky (Голубой) - Гибридный алгоритм (DFS + жадный поиск)

   • Использует жадный алгоритм при большом расстоянии до Pacman
   • Переключается на ограниченный по глубине DFS при приближении
   • Эффективен для быстрого преследования на коротких дистанциях

2. Pinky (Розовый) - BFS

   • Всегда находит кратчайший путь

3. Clyde (Оранжевый) - Модифицированный алгоритм Дейкстры

   • Учитывает веса разных типов клеток:
     • Обычный коридор: вес 1
     • Перекресток: вес 2
     • Опасная зона (рядом другие привидения): вес 5
   • Оптимален для стратегического перехвата

4. Blinky (Красный) - Алгоритм A*

   • Использует эвристику Манхэттенского (на Больших расстояних лучше использовать ) расстояния
   • Динамически меняет поведение в зависимости от состояния Pacman

📊 Сравнение алгоритмов поиска пути

Алгоритм	Сложность	Практическая скорость & Память	Лучший кейс применения	Особенности реализации
DFS+Жадный	O(bᵈ)	0.08-0.12 мс/шаг (≈120K операций при d=5) & >5 КБ (стек глубины)	Короткие дистанции	Глубина поиска ограничена (d=5), жадный выбор на больших расстояниях
BFS	O(V+E)	1.2-1.8 мс/шаг (≈2.3K посещений вершин) & 25-30 КБ (очередь + visited)	Кратчайший путь в невзвешенном графе	Использует двунаправленную очередь (deque), кэширование путей
Дейкстра	O(E+V*log V)	3.5-5.2 мс/шаг (≈5.7K операций с кучей) & 35-40 КБ (dist + prev)	Взвешенные графы	Приоритетная куча (heapq), динамическое обновление весов
A*	O(E)	0.6-0.9 мс/шаг (≈1.1K оценок эвристики) & 20-25 КБ (open/closed sets)	Большие карты	Эвристика Манхэттенского расстояния, адаптивная стратегия

Методика расчётов (для 34×24 = 816 клеток):

1. DFS+Жадный:

   • Среднее ветвление b ≈ 2.7 (для лабиринта Pacman)
   • Глубина d=5 → 2.7⁵ ≈ 143 операции
   • 100K операций жадного выбора на больших дистанциях

2. BFS:

   • V=816, E≈2200 → 3016 посещений в худшем случае
   • Кэширование сокращает до ≈2.3K операций

3. Дейкстра:

   • 2200 рёбер + 816×log₂816 ≈ 5700 операций
   • Ускорен бинарной кучей

4. A*:

   • Эвристика сокращает E=2200 до ≈1.1K проверок
   • Open-set хранит ~25% вершин

Все алгоритмы оптимизированы для стабильной работы на карте 34×24 с частотой 60 FPS (с учетом отрисовки спрайтов)

Максимальное время выполнения на кадр: 1000 мс / 60 FPS ≈ 16.6 мс

⚙️ Требования

• Python 3.6+
• Pygame

🛠️ Установка

1. Клонируйте репозиторий:

   git clone https://github.com/ваш-username/pacman-pygame.git
   cd pacman-pygame

2. Установите зависимости:

   pip install -r requirements.txt

3. Запустите игру:

   python pacman.py

## В планах
- [ ] Добавить состояние firgtened для Pacman (временная возможность съедать привидения)
- [ ] Добавить больше уровней
- [ ] Реализовать ИИ для привидений
- [ ] Добавить систему рекордов
- [ ] Реализовать мультиплеер