Алгоритм. разработка программы нахождения пути.

Привет!..прошу помощи в разработке программы нахождения пути из точки А в точку В на карте..Необходимо задать игровое поле,которое должно быть во-первых, дискретным (разбитым на секторы), и во-вторых, каждая
ячейка поля может быть как доступной для перехода, так и быть
препятствием.
надо пройти от A до B. Нам необходим массив направлений
такого же размера что и карта с ландшафтом. Так же необходимо иметь два
списка с координатами (X,Y) свободных секций карты. Количество
элементов в них зависит от размера карты.


заранее спасибо за рассмотрение))

0

Будем рассматривать случай, когда поле (карта) конечна и каждая ячейка характеризуется только статусом «Доступна» или «Заблокирована», который не зависит ни от каких параметров (в т.ч. положении человека на этом поле) и задается изначально. Если поле разбито на ячейки в виде сетки, то каждая ячейка задается двумя координатами (i,j), где 0<i<n+1 и 0<j<m+1, (n,m) — размеры карты. Тогда статум ячейки будет будем считать функцией двух аргументов A[i,j] :: {True, False}

При таком построении человек по карте может перейти из (i,j) только в (i+1,j), (i,j+1), (i,j-1) и (i-1, j) и никуда более. Пусть изначально человек стоял на позиции (x, y). Очевидно, что в таком случае все поля, не занятые преградами, то есть те, где A принимает True, делятся на две группы: доступные (те, куда из (x, y) можно дойти) и недоступные (например, изолированные камеры). Обозничим через P[i,j] :: {none, left, right, top, bottom} доступность ячейки (i, j): none, если ячейка изолирована или ещё не определена, left, если в неё можно прити слева, right — если справа и т.д.
Очевидно, что если нас интересует путь от (x, y) в (r, t) и P полностью построена, то в случае P[r,t]=none пути нет, в противном случае путь от (x,y) в (r,t) == путь от (x,y) в (r',t') ++ переход от (r', t') в (r,t), где (r',t') — ячейка, из которой можно прийти в (r,t), она определяется непосредственно P[r,t]. Это называется обратным ходом.

Осталось последнее: сформировать P. Для этого положим P[_,_]==none. Установим P[x+1,y]=left, P[x-1,y]=right, P[x,y+1]=bottom, P[x,y-1]=top, исключая поля, где A=False (иными словами, из 4 полей, окружающих стартовую позицию, доступны те, в которых нет препятствий). Инициализируем массив-список C[s], который хранит координаты точек, только что рассмотренных. Суть в том, что если мы какую-то ячейку рассмотрели на возможность перехода от неё к соседям (на первом шаге — это (x,y)), эта ячейка больше не будет в рассуждениях фигурировать, так как, очевидно, путь не должен проходить через одну ячейку дважды (это как минимум, глупо, также невыгодно для путишественника и сложно для нас, программистов). А те ячейки, которые мы только-только рассмотрели (упомянули) в контексте «в неё можно прийти», становятся подозрительными, потому что они, быть может, являются звеньями в пути. Поэтому мы на каждом этапе будем запоминать все подозрительные ячейки в списке C и на следующем этапе мы будем оперировать только с ячейками из этого списка. Идея, думаю, ясна.
Эта часть завершается тогда, когда список C становится пустым (т.е. все ячейки, в которые можно прийти, уже рассмотрены).

Первый этап описан (см. выше), точки (x+1,y), (x-1,y), (x,y+1), (x,y-1) должны быть занесены в список C.

Описание общего этапа (второй, третий, ...):
1. Онуляем список C' (аналог C, только для нового этапа)
2. Для каждой точки (x,y) из списка рассматриваем (x+1,y), (x-1,y), (x,y+1), (x,y-1) на предмет доступности (функция A) и, если какие-то ячейки физически доступны, устанавливаем для них P соотв. значение (P[x+1,y]=left, P[x-1,y]=right, P[x,y+1]=bottom, P[x,y-1]=top); добавляем эти ячейки в список C'.
3. Этап завершен. Если C' непуст, запускаем навый этап уже со списком C' (т.е. C:=C'). В противном случае перебраны все варианты и программе больше нечего делать. [Также можно делать выход тогда, когда в C' есть конечная ячейка (r,t), что означает, что мы уже способны указать путь к ней.]

Примечание по реализации подобного алгоритма на языках типа C/C++/Pascal/Delphi/Fortran/...
• A и P лучше делать двумерными массивами [0..n+1, 0..m+1], в крайних строчках/столбцах хранить False и none, как маркер границы карты.
• C — массив [1,nm/2], элементы которого имеют структурный тип {X:1..n, Y:1..m}. Также лучше использовать "указатель" на голову массива (т.е. ввести переменную, в которой содержится информация о количестве элементов в C)
• Можно вместо C и C' использовать один список и работать с ним, как со стеком. Не советую. Как минимум, потому что нет никаких гарантий того, что полученный путь самый краткий.

Оценка сложности: ~nm.

1

идея ясна,большое спасибо...но мне бы сам код программы,реализация....желательно на Delphi или С++

0

А алгоритм Дийкстры не подойдет ? Похоже, он один из самых эффективных и в программировании не сложен. И гуглом его можно найти

1

Алгоритм Дейкстры, используемый для нахождения минимального пути на графе со взвешенными вершинами, тут будет несколько странным хотя бы потому, что на каждом этапе этот алгоритм определяет, к какой точке есть ближайший маршрут из ещё нерассмотренных точек. Вообще говоря, грубый поиск в ширину тут скорее даст большую эффектность (хотя в данном случае у них суть похожая).
А вообще, Just Google It:
• Алгоритм Дейкстры
• Поиск в ширину

0

Алгоритм Дейкстры - не самая быстрая вещь. Мне кажется его разумно использовать для сложных, запутанных графов с циклами.
А здесь и впрямь лучше попробовать поиском в ширину.

0