Рубрика «логические игры» - 10

В этом посте описывается генератор уровней для моей игры-головоломки Linjat. Пост можно читать и без подготовки, но он легче усвоится, если сыграть в несколько уровней. Исходный код я выложил на github; всё обсуждаемое в статье находится в файле src/main.cc.

Примерный план поста:

• Linjat — это логическая игра, в которой нужно закрыть все числа и точки в сетке линиями.
• Головоломки процедурно генерируются при помощи комбинации из солвера, генератора и оптимизатора.
• Солвер пытается решить головоломки так, как это делал бы человек, и присваивает каждой головоломке оценку интересности.
• Генератор головоломок создан таким образом, чтобы можно было с лёгкостью менять одну часть головоломки (числа) и при этом все остальные части (точки) менялись таким образом, чтобы головоломка оставалась решаемой.
• Оптимизатор головоломок многократно решает уровни и генерирует новые вариации из наиболее интересных, найденных на текущий момент.

Правила

Чтобы понять, как работает генератор уровней, нужно, к сожалению, разобраться с правилами игры. К счастью, они очень просты. Головоломка состоит из сетки, содержащей пустые квадраты, числа и точки. Пример:

Цель игрока — прочертить вертикальную или горизонтальную линию через каждое из чисел при соблюдении трёх условий:

• Линия, идущая через число, должна иметь ту же длину, что и число.
• Линии не могут пересекаться.
• Все точки необходимо закрыть линиями.

Пример решения:

Ура! Дизайн игры готов, UI реализован, и теперь единственное, что осталось — найти несколько сотен хороших головоломок. А для подобных игр обычно не имеет смысла пытаться создавать такие головоломки вручную. Это работа для компьютера.
Читать полностью »