Вы все про пиво, да про пиво. А помочь не хотите?

← →
VictorT (2002-02-11 18:28) [6]

Описываю "волновой алгоритм". Пусть твой лабиринт описывается двухмерным числовым масивом, в котором запрещённые зоны (стены), обозначены например 0, а разрешённые - например 1. Дальше в точке, в которую надо попасть, возбуждается волна. Делается это так: в данный элемент массива ставится 2 (т. к. 0 и 1 используются как идентификаторы). Дальше по всему массиву ищутся 2 и если рядом с ними есть 1, то они заменяются на 3. После соответственно ищутся 3 и примыкающие к ним 1 на 4 и т. д. (цыкл). Условие выхода из цыкла - когда нечего заменять. Теперь, находясь в любой точке лабиринта, можно определить, в каком направлении нужно шагнуть, чтобы придерживаться кратчайшего пути к точке назначения - для этого нужно выбрать из примыкающих к данному елементу массива тот, который меньше данного. Вроде всё. Объяснение получилось сумбурное, если непонятно, спрашивай.

Вы все про пиво, да про пиво. А помочь не хотите? Найти похожие ветки