5 игр, чтобы лучше понять алгоритмы, графы и логику
Подборка, с одной стороны, таймкиллеров, с другой — «проводников» в основы компьютерных наук. Тут вы буквально играете алгоритмом: оптимизируете дерево решений, балансируете граф маршрутов. В общем, база базовая.
Собрали вместе с Ольгой Максименковой — зам. руководителя департамента программной инженерии и доцентом факультета компьютерных наук НИУ ВШЭ, руководителем проектной группы «Программная инженерия компьютерных игр — ПИКИ».
Mini Metro — балансировка транспортного графа
Вам нужно построить схему метро, где станции и линии — вершины и ребра графа. Главная задача — оптимизировать поток пассажиров и не допустить перегрузки. Похоже на решение задач о кратчайших путях, потоках в сети, алгоритмах распределения.
Что полезного:
- Динамическое обновление графа с ростом нагрузки
- Оптимизация маршрутов и распределения ресурсов (поездов)
- Игра требует понимания центров и удаленных узлов — анализ графа
TIS-100 или Shenzhen I/O — реальное программирование
Здесь надо буквально писать код, чтобы решить задачи оптимизации. В TIS-100 вы работаете с ассемблероподобным языком и решаете задачи на передачу данных, синхронизацию и распределение.
Что полезного:
- Задачи формализуются как графы передачи данных
- Требуется минимизация по памяти и количеству операций
Human Resource Machine — алгоритмы через визуальную метафору
Вы управляете офисным работником с помощью базовых команд: взять, положить, прыгнуть, сравнить. Каждая задача — это классический алгоритм: сортировка, фильтрация, подсчет, аккумуляция.
Что полезного:
- Простая модель регистров и памяти
- Задачи как реализация алгоритмов в условиях ограничения
- Минимизация по строкам и циклам
SpaceChem — пространственная оптимизация и граф операций
Тут надо конструировать машины, выполняющие химические (и логические) процессы. Эти машины — не что иное, как графы взаимодействующих узлов.
Что полезного:
- Каждая операция — узел, действия — ребра
- Вызов: минимизация по циклам, пространству, времени
- Результаты можно анимировать, анализировать и сравнивать с другими игроками
Аналог игры по полезным изучаемым функциям:
The Signal State — логика и релейные схемы
Пазл с интерфейсом логического программирования: переключатели, входы, И/ИЛИ/НЕ-операторы. Цель — преобразовать сигналы в нужную форму.
Что полезного:
- Булевы функции, построение схем
- Временные зависимости, синхронизация
- Минимизация по компонентам и времени сигнала