Пишу игрушку сыну, на 1С
(хотя платформа не принципиальна). Моделируется игра "Лабиринт" - компьютер в роли ведущего задает карту: прямоугольник из заранее известного количества клеток по ширине и высоте, в каждой клетке может быть один из заранее известного класса объектов. Некоторые классы - ямы: пара клеток любого взаимного расположения, при попадании в одну оказываешься в другой, реки: n клеток последовательно соприкасающихся сторонами, при попадании в любую часть оказываешься в конце и т.д. Игрок не знает карту, можно навешивать любые миссии, но суть в том чтобы разгадать карту и ходить осознанно. Игрок делает ход - вправо, влево, вверх или вниз - ведущий (компьютер) отвечает - пусто, яма 3, река и т.п.
Я запрограммировал процесс генерации карты, интерфейс и отработка ходов не вызывают сложностей. Но в процессе генерации порой получаются такие карты, которые нельзя пройти - то есть, или попадая в определенную точку нельзя из нее выйти (например, река стеклась в центр по спирали, или 2 реки так взаимно переплелись), или просто есть недоступные области. Собственно, возник вопрос - есть ли какой-нибудь алгоритм или метод, который позволяет проверять полученную карту на "проходимость" - то есть на отсутствие мертвых зон и недоступных областей? Другими словами, чтобы из любой исходной точки можно было попасть в любую другую. Предполагаемое количество клеток в длине/ширине карты - порядка 5-10.
12.12.2012, 18:34 
