Всем привет. 
Нужно алгоритм поиск пути в двовхмерном массыве(игровое поле). Вот игровое поле:


playfield[10][10] - структура, где есть поле TYPE.
В этом поле содержиться инфа о даной клетке:
RECT_NONE - невидимая клетка. неиспользуется в игре 
RECT_EMPTY - пустая клетка. 
RECT_BALL - занятая клетка. находиться какой-то объэкт

Интерфейс функции:

Помогите плз написать алгоритм поиска пути на С/С++. Прочитал алгоритмы здесь: http://pmg.org.ru/ai/stout.htm мало что понял  
Заранее спасибо.



Это сообщение отредактировал(а) Sergio - 7.12.2008, 16:19

алгоритм поиска в ширину можно представить так:
вместо того, чтобы находить сразу все доступные точки, найти сначала точки, в которые можно добраться за 0 шагов, потом за 1 шаг, потом за 2, потом за 3 и т.д.
если до точки можно добраться, значит рано или поздно мы её встретим

за 0 шагов, естественно, можно добраться только в стартовую точку
за 1 - во всех её соседей (кроме тех, через которые нельзя ходить)
чтобы найти все точки, доступные за 2 шага, пробегаемся по точкам, доступным за 1 шаг и помечаем всех её соседей (кроме тех, по которым нельзя ходить), как доступные за 2 шага
и так продолжаем, пока не встретим искомую точку

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

конечно же, возможна целая куча оптимизаций, но для понимания можно начать с самой простой версии

Это сообщение отредактировал(а) maxim1000 - 7.12.2008, 19:05

Мм, может я не в тему, но разве элементарный алгоритм волны не подойдет?
Вроде он ищет оптимальнейший путь и только надо обработать случай, когда до клетки не добраться.

честно говоря, в своём владении терминологией не уверен, но, по-моему, в данном случае (т.е. невзвешенном графе) волнойов лагоритм, поиск в ширину и алгоритм Дейкстры совпадают

Я так понял что алгоритм поиска в ширину реализуется с помощью рекурсии.. 
Вот что примерно такого(поправьте если неправильно)
По диагонали проходить путь нельзя:

спасибо.

Sergio, И что, он даже не циклится? 

ksnk, а какправильно? помоги плз с реализацией

Перебор в ширину:

Перед расчетом заводим новый массив 10x10. Прочищаем его нулями.
Занятые и невидимые точки заполняем -1.
Начало помечаем 1
Конец = 1000.

Цикл по N++, от 1-го. {
  Для каждой точки, помеченной N проверяем соседей. {
    Если сосед ==1000 - Нашли.
    Если сосед ==0 - помечаем его N+1
  }
}
Все. В результате 

Можно составлять список из N+1-х элементов для пущей оптимальности. 

Это сообщение отредактировал(а) ksnk - 8.12.2008, 00:53

ksnk, а можно побробней что это значит?

Вот что у меня пока вышло:

Не очень понимаю как это всё должно работать.

Это сообщение отредактировал(а) Sergio - 8.12.2008, 17:32

имя TYPE здесь не стоит использовать
лучше что-то типа distance - чтобы понятнее было

я бы посоветовал нарисовать на бумаге в клеточку какое-то поле (с препятствиями) и последовательно найти точки, до которых можно добраться за 1, 2, 3 и т.д. шагов

maxim1000, хорошо учту.

Чего-то типа такого. На С писал давненько, проверить не на чем, может и ашипка-другая попасть...
Чтобы не сочинять массив, можно добавить в основной массив поле TMP, в котором и будем уже рисоваться...



Неоптимально, понятно, но зато должно работать 
Чтобы сэкономить на многократном просмотре поля - можно сочинять список клеток, которые помечены N+1 и просматривать уже только его.  

Это сообщение отредактировал(а) ksnk - 8.12.2008, 19:59

А зачем вам собственно он нужен, что вы уже задумали?