Процедурная генерация уровня для небольшого пазла

На новогодних каникулах в качестве домашнего проекта сделал небольшой классический пазл с шариками для маленькой консоли Playdate.

Больше всего времени у меня заняла задача генерации уровней на ходу.

Я решил обрисовать алгоритм и показать некоторые идеи, которые могут пригодиться для генерации уровней в похожих ситуациях.

Геймплей

У нас есть прямоугольное поле с шарами. Несколько белых и один черный. Мы управляем черным шаром. Стрелками мы можем толкнуть черный шар в одном из четырех направлений. Тот покатится и, если встретит на своем пути шар, толкнет его, а сам остановится. В свою очередь, белый шар может толкнуть на своем пути другой шар.

Если черный шар выкатится за края поля, мы проиграем. Задача: столкнуть с поля все белые шары.

Уровни генерируются на ходу по последней позиции черного шара.

Задача

Зная начальную позицию черного шара, расставить N белых шаров на поле, так чтобы уровень был проходимым и интересным.

Решение

Будем строить уровень в том же порядке, как мы будем его проходить.

Возьмем позицию черного шара и выберем случайное направление.

Затем выберем на сколько клеток он должен будет сдвинуться при первом ходе. Причем сдвиг может быть даже нулевой, так как черный шар при ходе может остаться на той же самой клетке.

Разместим рядом с новой позицией черного шара наш первый белый шар, причем по направлению движения.

Запомним историю случившегося хода:

1-й ход: Герой двигался по таким-то клеткам. Белые шары двигались по таким-то клеткам.

Выбираем следующую позицию черного шара аналогичным образом: выбираем случайное направление и смещение.

Однако теперь при выборе появляется ограничение. Новый белый шар не должен попасть на уже посещенные черным шаром клетки.

Например, мы не можем установить второй белый шар сюда. Потому что по этим клеткам уже ходил черный шар в первом ходу — будет противоречие.

А можно ли поставить новые шары на клетки, по которым уже летали другие белые шары? Например, здесь:

Можно, но не везде.

Рассмотрим первый вариант:

Мы генерируем шар уже для второго хода, то есть позицию белого шара на момент второго хода. Но по центральной линии уже пролетал первый белый шар.

Давайте восстановим начальную картину уровня, чтобы мы оказались ко второму ходу в такой ситуации, как на картинке выше.

Исходный уровень должен быть таким:

То есть в начальной позиции уровня мы поставили шар на одну клетку правее.

У края поля: Мы не можем на втором ходу ожидать белый шар у края поля. Потому что это значит, что в изначальном положении уровня он должен находиться за пределами поля.

По ходу расстановки новых шаров уровень обрастет историей ходов в виде различных стрелочек на поле с их нумерацией.

Каждый раз, когда мы будем вычислять начальную позицию новых белых шаров на поле, мы должны:

• Смещать их по соответствующим стрелочкам истории белых шаров, если они на них попадают.
• И проверять, что белые шары не мешают перемещениям черного шара в соответствующий момент истории ходов. То есть сместили шар — проверили историю перемещений, могло ли быть пересечение с черным шаром в определенных ходах. Если могло, то значит вариант расстановки белого шара не подходит.

Здесь, главное не запутаться и хорошо понимать историю перемещений шаров.

То есть вы должны, как бы, восстанавливать историю позиций шаров в истории до определенного хода и делать соответствующие проверки на конфликты.

Кусочек кода с проверкой истории в момент нахождения позиции белого шара:

-- ballsMovesTable - таблица с историей перемещения белых шаров
-- heroMovesTable - таблица с перемещением черного шара

newBallPosition = {x = newHeroPosition.x + direction.x,
                   y = newHeroPosition.y + direction.y}

-- Если позиция будет за пределами карты, то установка шара невозможна
if not pointInBounds(newBallPosition, bounds) then
   return false
end

h = #ballsMovesTable -- Количество совершенных ходов в истории

-- Идем по ходам в истории в обратную сторону
for i = #ballsMovesTable, 1, -1 do
   ballsMove = ballsMovesTable[i]
      
   -- Если попали на стрелку предыдущего белого шара
   if ballsMove[newBallPosition.x][newBallPosition.y] ~= nil then
      
      -- Проверяем перед смещением, что мы не пересекаемся с черным шаром
      -- по истории после этого момента
      for j = i + 1, h do
         if heroMovesTable[j][newBallPosition.x][newBallPosition.y] then
            return false
         end
      end
         
      -- Смещаем шар по стрелке из истории хода
      offsetX = ballsMove[newBallPosition.x][newBallPosition.y].x
      offsetY = ballsMove[newBallPosition.x][newBallPosition.y].y
      newBallPosition = {x = newBallPosition.x + offsetX,
                         y = newBallPosition.y + offsetY}
      if not pointInBounds(newBallPosition, bounds) then
         return false
      end
      h = i
         
   end
end

-- Проверяем финальную позицию белого шара на пересечении
-- с начальной историей черного шара
for j = h, 1, -1 do
   if heroMovesTable[j][newBallPosition.x][newBallPosition.y] then
      return false
   end
end

return true

Развесовка алгоритма

Я еще улучшил алгоритм небольшой развесовкой решений в момент выбора на сколько клеток мы смещаем черный шар при ходе и отдал приоритет большим смещениям. Чтобы уровень был интереснее. Так как, чем длиннее перемещения черного шара, тем интереснее создаются ситуации.

В итоге у меня получилась такая генерация уровней. Кстати, очень залипательная игра получилась.