В этом посте описывается генератор уровней для моей игры-головоломки Linjat. Пост можно читать и без подготовки, но он легче усвоится, если сыграть в несколько уровней. Исходный код я выложил на github; всё обсуждаемое в статье находится в файле src/main.cc.
Примерный план поста:
- Linjat — это логическая игра, в которой нужно закрыть все числа и точки в сетке линиями.
- Головоломки процедурно генерируются при помощи комбинации из солвера, генератора и оптимизатора.
- Солвер пытается решить головоломки так, как это делал бы человек, и присваивает каждой головоломке оценку интересности.
- Генератор головоломок создан таким образом, чтобы можно было с лёгкостью менять одну часть головоломки (числа) и при этом все остальные части (точки) менялись таким образом, чтобы головоломка оставалась решаемой.
- Оптимизатор головоломок многократно решает уровни и генерирует новые вариации из наиболее интересных, найденных на текущий момент.
Правила
Чтобы понять, как работает генератор уровней, нужно, к сожалению, разобраться с правилами игры. К счастью, они очень просты. Головоломка состоит из сетки, содержащей пустые квадраты, числа и точки. Пример:
Цель игрока — прочертить вертикальную или горизонтальную линию через каждое из чисел при соблюдении трёх условий:
- Линия, идущая через число, должна иметь ту же длину, что и число.
- Линии не могут пересекаться.
- Все точки необходимо закрыть линиями.
Пример решения:
Ура! Дизайн игры готов, UI реализован, и теперь единственное, что осталось — найти несколько сотен хороших головоломок. А для подобных игр обычно не имеет смысла пытаться создавать такие головоломки вручную. Это работа для компьютера.
Читать полностью »
