Задача "о прохождении Лабиринта" распадается на пару других: техническую и логическую. Техническая часть состоит в том, чтобы справиться с управлением своего "героя", избежать столкновений с "противниками" и не попасть в ловушки. Логическая часть – отыскание правильного пути.
Коль скоро задача логическая, то, очевидно, должен существовать алгоритм для ее решения. С точки зрения математики, путь от входа до цели есть топологический инвариант. Проще говоря, это означает: план Лабиринта, нарисованный на куске резины, можно растянуть таким образом, что вход и цель соединятся одним прямым коридором.
Проведя прямую линию по этому коридору, мы получим кратчайший путь до цели. Практически же, если у нас есть план лабиринта, следует заштриховать (завалить) все тупики. Оставшаяся часть - путь (или несколько путей) к цели. В некоторых играх можно видеть весь лабиринт целиком (иногда его план). Но, обычно, в таких играх цель игры не прохождение лабиринта, а собирание предметов (Miss Pocman, Fast Food, CHUCKE и др.). Или же лабиринт снабжен "переключателями" в виде закрывающихся и открывающихся дверей, падающих решеток, разводных мостов и т. д., которые способны изменять конфигурацию лабиринта. Задача - выбрать момент для прохождения, когда "переключатели" в нужном положении (или переключить их самому), чтобы достичь цели.
Итак, если на экране весь лабиринт, то отыскание верного пути не представляет трудностей до тех пор, пока его размер не очень велик. Другое дело, если лабиринт разбит на множество экранов. Тогда, чтобы отыскать таким способом путь, придется составлять план лабиринта.
Лабиринты бывают двух видов: двух или трехмерными, т.е. одно или многоэтажными. При этом двухмерная графика игры не обязательно означает двухмерный лабиринт, и, наоборот, часто трехмерная графика совмещена с двухмерным лабиринтом. При двухмерной графике изображение лабиринта может быть горизонтальным (смотрим сверху) или вертикальным (смотрим сбоку). При трехмерной графике тоже существуют два способа изображения (обычно только части лабиринта): изометрия и фронтальная проекция.
Специалисты различают три конфигурации: лабиринты односвязные, лабиринты многосвязные без "петли" вокруг цели и лабиринты многосвязные с замкнутой "петлей" вокруг цели. Односвязными называются лабиринты, не содержащие замкнутых маршрутов и не имеющие отдельно стоящих стенок. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными. При этом если замкнутый маршрут не проходит вокруг цели, то лабиринт второй конфигурации; если же цель можно обойти по замкнутому маршруту, значит, лабиринт третьей конфигурации.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.