Программирование игр и головоломок

Лабиринты являются очень высоко ценимыми головоломками. Почему не использовать компьютер и генератор случайных чисел для построения случайных лабиринтов, которые вы затем будете пытаться пройти? Но мой микрокомпьютер не имеет графических возможностей. К тому же если у вашего такие возможности есть, то я не уверен, что желание нарисовать обычный лабиринт приводит к хорошему упражнению по программированию. Внимание часто в большей мере поглощается графическими задачами, чем более фундаментальной задачей порождения лабиринта. Тем не менее, если вам так подсказывает сердце, не стесняйтесь: , стройте от случая к случаю такой лабиринт, чтобы у него был хотя бы один путь от начала к концу, и играйте с ним.

Чтобы освободиться от графических задач, рассмотрим другую форму лабиринта. Его создание составляет головоломку, а использование — игру. Пусть дана прямоугольная область, образованная n строками с p полями на каждой из них. На моем компьютере, где приходится учитывать формат экрана, числа n = 12 и p = 20 дают хорошие результаты. Занятые места считаются препятствиями (обозначенными здесь 0), пусть как-то помечены свободные места (здесь — точкой), пусть значок * обозначает всадника. Конь перемещается, как конь в шахматах: два шага в одном направлении и еще один шаг перпендикулярно предыдущему направлению. Конь может перемещаться только с одного свободного места на другое, В начальный момент он находится в правом нижнем углу. Он должен попасть в верхний левый угол (который, таким образом, тоже должен быть свободным). Число ходов игры ограничено. На рис. 1 изображен типичный пример лабиринта.

Составьте программу для компьютера для создания этого лабиринта и попытки его пройти. Так как должен существовать какой-то путь, проходящий из правого нижнего угла в правый верхний угол, то я предлагаю вам действовать следующим образом:

— возьмите случайным образом путь, связывающий эти два угла. Это — маленькая головоломка. Может быть, вы знаете задачу Эйлера о шахматном коне: составить такой путь коня по шахматной доске, чтобы он побывал на каждом поле один и только один раз. Но здесь у вас больше свободы. Тем не менее не представляется разумным проходить два раза одно и то же поле (если ваш путь будет содержать круг, то он будет предоставлять возможность для короткого замыкания, т. е. удаления этого круга). Но, может быть, это и не необходимо. Если мы много раз попадаем на одно и то же поле, то мы предоставляем много возможностей выбора, и осложняем задачу воссоздания пути. Не нужно использовать какой-либо систематический алгоритм прохода, иначе ваш лабиринт будет расшифровываться слишком быстро. Следующий за данным полем шаг на нашем пути должен выбираться случайным образом. Как тогда мы сможем быть уверены в попадании в левый верхний угол?

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

дуть будет почти полностью определен (на рисунке препятствия занимают приблизительно 2/3 полей. Это — верхняя грань);

— когда это сделано, вы снимаете обозначения полей выбранного пути, заменяя их точками. Лабиринт готов к показу.

Остается обеспечить движение коня. Вот как действую я. Сначала я подсчитываю число полей на исходном пути, которые были выбраны случайно, и вывожу это число в качестве верхней границы числа ходов. Я свидетельствую, что всегда обнаруживался более короткий путь. Я не пытался объяснить этот экспериментальный факт…

Компьютер сообщает число оставшихся ходов и требует ваших указаний о движении. Ответ дается в виде двух букв: первая из этих букв дает направление, в котором нужно переместиться на два шага, вторая буква дает перпендикулярное предыдущему направление, в котором нужно сделать один шаг: Н — для нижней, В — для верхней, П — для правой, Л — для левой сторон. В случае на рис. 1 первое движение предписывает ЛВ — два шага влево, один вверх.

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

Игра 5. Спящая красавица.

Краткое содержание предыдущих эпизодов. Доктор Жабуэ не убил великолепную Жюли, он только приостановил жизненные процессы. Ее мог бы разбудить надлежащий лицевой массаж, но это его не беспокоит, впереди еще много времени. Из замка вывезено все, что имело хоть какую-то ценность: обстановка, картины, произведения искусства… Молодой повеса обнаруживает пустой замок и находит, что он должен быть замечательным треком для мотогонок…

13-й эпизод.