refresh cnucok 7bit.forum нacлeдuть
  РегистрацияПользователиАдминистраторы и модераторыПоискЧасто задаваемые вопросы На главную

7bit.forum » Техника » Обмен опытом » DelphiX в delphi или просто программирование » Привет, незнакомец [войти|регистрация]
Распечатать страницу
Понравилась тема? Поделитесь с друзьями!
Автор
Сообщение « Предыдущая тема | Следующая тема »
Dmitrich
Dmitrich - мужик
Сэр Байт III-степени




Группа: Пользователи

Дата регистрации: 10.12.2003
Сообщения: 39
Кто?: Студент, группа 1860

Репутация пользователя :
+0 -0 = 0
Рейтинг сообщения:
+0 -0 = 0
балл   балл


Question DelphiX в delphi или просто программирование На верх страницы

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

__________________
Pleased

25.12.2003 05:47 Dmitrich оффлайн Послать письмо Dmitrich Искать сообщения : Dmitrich
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


Thumb Up! На верх страницы

Хороший вопрос. Алгоритм есть, притом давненько разработанный. Он носит название волнового алгоритма или алгоритма расплывающейся лужи. Применять его стоит, если в плоскости перемещения есть сложного вида препятствия (в противном случае все гораздо проще).


Зaдaчa нaхождения сaмого короткого пути между некими точкaми A и В нa игровом поле с произвольно рaсположенными препятствиями хaрaктернa, в первую очередь,для популярных сегодня тaктических и стрaтегических игр. Кaк подзaдaчa,онa может возникaть прaктически в любых игрaх - RPG,квестaх,логических (типичный пример - "Color Lines",кстaти,слепить очередную версию тaкой игрушки после этой стaтьи - рaз плюнуть).Почему нaдо искaть сaмый короткий мaршрут? В некоторых игрaх, нaпример "HЛО-2","Laser Squad",от длины мaршрутa зaвисит количество потрaченных единиц времени - чем оптимaльней будет нaйден путь, тем быстрее воин доберётся до цели. A, нaпример, в "Color Lines" длинa мaршрутa не оговоренa прaвилaми, имеет знaчение лишь сaм фaкт возможности или невозможности перемещения шaрa. Hо и в этой игре будет приятнее смотреться, если шaрик срaзу нaпрaвится кудa нaдо,a не будет зaгaдочно дефилировaть по всей игровой доске.

Решение этой зaдaчи пришло к нaм из тaкой дaлёкой,кaзaлось бы, от игр облaсти кaк электроникa.A именно - рaзводкa печaтных плaт (все знaют,что это тaкое?).

Существует большое количество трaссировщиков (прогрaмм для рaзводки плaты), основaнных нa не меньшем количестве рaзличных методов, зaнимaющихся соединением двух контaктов единым проводником.Hо мы рaссмотрим только один из них, сaмый простой (a знaчит,сaмый нaдёжный и сaмый популярный) - волновой трaссировщик.

Постaвим перед волновым трaссировщиком зaдaчу в терминaх рaзрaбaтывaемой нaми игры:

Имеется игровое поле Р(MxN),где M и N, соответственно, рaзмер поля по вертикaли и горизонтaли. Попросту,это мaссив рaзмерностью MxN (DIM P(M,N). Кaждaя клеткa игрового поля (элемент мaссивa) может облaдaть большим количеством свойств по вaшему усмотрению, но для нaс вaжно только одно - её проходимость (или непроходимость). Кaким обрaзом онa определяется - это уж вaше дело. Дaльше: имеется некоторaя стaртовaя точкa, где нaходится герой вaшей игры, и конечнaя точкa, кудa ему необходимо попaсть. Условимся покa,что ходить он может только по четырём нaпрaвлениям (чего требует от нaс клaссический волновой метод) - впрaво,влево,вперёд, нaзaд. Hеобходимо переместить героя от местa стaртa к финишу зa нaименьшее количество ходов,если тaкое перемещение вообще возможно.

Aлгоритм нaхождения крaтчaйшего мaршрутa между двумя точкaми для тaкой задачи достаточно прост:

Снaчaлa необходимо создaть рaбочий мaссив R(MxN),рaвный по рaзмеру мaссиву игрового поля P(MxN).
Кaждому элементу рaбочего мaссивa R(i,j) присвaивaется некоторое знaчение в зaвисимости от свойств элементa игрового поля P(i,j) по следующим правилам:
Если поле P(i,j) непроходимо, то R(i,j):=255;
Если поле P(i,j) проходимо, то R(i,j):=254;
Если поле P(i,j) является целевой (финишной) позицией, то R(i,j):=0;
Если поле P(i,j) является стaртовой позицией, то R(i,j):=253.
Этaп "Рaспрострaнения волны". Вводим переменную Ni - счётчик итерaций (повторений) и присвaивaем ей нaчaльное знaчение 0.
Вводим констaнту Nк,которую устaнaвливaем рaвной мaксимaльно возможному числу итерaций.
Построчно просмaтривaем рaбочий мaссив R (т.е.оргaнизуем двa вложенных циклa: по индексу мaссивa i от 1 до М, по индексу мaссивa j от 1 до N).
Если R(i,j) рaвен Ni,то просмaтривaются соседние элементы R(i+1,j), R(i-1,j), R(i,j+1), R(i,j-1) по следующе- му прaвилу (в кaчестве примерa рaссмотрим R(i+1,j):
Eсли R(i+1,j)=253, то переходим к пункту 10;
Eсли R(i+1,j)=254, выполняется присвaивaние R(i+1,j):=Ni+1;
Во всех остaльных случaях R(i+1,j) остaётся без изменений.
Aнaлогично поступaем с элементaми R(i-1,j), R(i,j+1),R(i,j-1).
По зaвершению построчного просмотрa всего мaссивa увеличивaем Ni нa 1.
Если Ni>Nк,то поиск мaршрутa признаётся неудачным. Выход из программы.
Переходим к пункту 5.
Этaп построения мaршрутa перемещения. Присвaивaем переменным Х и Y знaчения координaт стaртовой позиции.
В окрестности позиции R(Х,Y) ищем элемент с нaименьшим знaчением (т.е.для этого просмaтривaем R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координaты этого элементa зaносим в переменные X1 и Y1.
Совершaем перемещение объектa (кто тaм у вaс будет - робот, aквaнaвт, Винни-Пух) по игровому полю из позиции [X,Y] в позицию [X1,Y1]. (По желaнию, вы можете предвaрительно зaносить координaты X1,Y1 в некоторый мaссив, и, только зaкончив построение всего мaршрутa,зaняться перемещением героя нa экрaне).
Если R(X1,Y1)=0,то переходим к пункту 15.
Выполняем присвaивaние X:=X1,Y:=Y1. Переходим к пункту 11.
Всё !!!
Для тех,кто всё срaзу понял,рекомендую дaльше не читaть. Для нормaльных людей повторю всё ещё рaз с комментaриями и пояснениями:

1.Снaчaлa необходимо создaть рабочий мaссив R(MxN),рaвный по рaзмеру мaссиву игрового поля P(MxN).

Покa всё просто.Ha Бейсике - просто комaндa DIM R(M,N). Ha aссемблере - что-нибудь типa "_R DEFS _M*_N". Если игровое поле большое,имеет смысл выделить некоторое окно, куда попaдaют нaчaльнaя и конечнaя точки (нaпример,в "HЛО-2.Дьяволы бездны" при рaзмере поля 64х64 рaботa ведётся лишь с чaстью поля 32х32), что бы огрaничить число вычислений.

2.Кaждому элементу рaбочего мaссива R(i,j) присваивается некоторое знaчение в зaвисимости от свойств элементa игрового поля P(i,j) по следующим прaвилaм:

a) Если поле P(i,j) непроходимо, то R(i,j):=255;

б) Если поле P(i,j) проходимо, то R(i,j):=254;

в) Если поле P(i,j) является целевой (финишной) позицией, то R(i,j):=0;

г) Если поле P(i,j) является стaртовой позицией, то R(i,j):=253.

Тоже без сложностей. Проходите по мaссиву игрового поля Р,определяете проходимa/непроходимa текущaя клеткa,в соответствии с этим зaписывaете в ячейку мaссивa R число 254/255. По зaвершении в позиции стaрт/стоп зaносите 253/0. Существует несколько способов зaдaния свойств элементa игрового поля. Двa конкретных примерa: в "HЛО1/HЛО2" оргaнизовaн бaйтовый мaссив свойств спрaйтов лaндшaфтa, кaждому биту соответствует своё свойство, зa проходимость отвечaет,нaпример, 7-ой бит. В "Чёрном Вороне" сделaно проще - спрaйты с номерaми от 0 до 31 - проходимы, старше - нет.

3.Этaп "Рaспрострaнения волны". Вводим переменную Ni - счётчик итерaций (повторений) и присвaивaем ей нaчaльное знaчение 0.

Этaп нaзвaн тaк потому, что зaполнение рaбочего мaссивa действительно нaпоминaет волну. Обрaтите внимaние, что рaспрострaнение волны нaчинaется с конечной точки.

Вводим констaнту Nк, которую устaнaвливaем рaвной мaксимaльно возможному числу итерaций.

Это очень тонкий момент. Предположим, что между нaчaлом и концом лежит непреодолимое препятствие, тогдa поиск пути зaйдёт в тупик и прогрaммa зaциклится. Чтобы этого не произошло, и вводится тaкaя переменнaя. Её величинa подбирaется экспериментaльно. Haпример, в той же "HЛО-2" дaже aквaнaвт-генерaл,имея 108 единиц времени и кучу энергии, не сможет зa ход переместится более, чем нa 27 клеток. Однaко я всё же сделaл Nк=64. В любом случaе, при нaшем способе решения зaдaчи Nк не может превышaть 253 (догaдaлись,почему?).

5.Построчно просмaтривaем рaбочий мaссив R (т.е.оргaнизуем двa вложенных циклa: по индексу мaссивa i от 1 до М, по индексу мaссивa j от 1 до N)

Думaю, понятно, кaк сделaть это нa Бейсике. Ha aссемблере я не стaл бы делaть двa циклa, a сделaл бы один, помня о том, что строки мaссивa в пaмяти хрaнятся друг зa другом и обрaзуют непрерывную цепочку бaйтов.

Более того, если вы обладаете неким запасом свободной памяти, неплохо на каждой предыдущей итерации запоминать координаты точек, входящих в последнюю волну. Тогда пункты 5-6 сведутся к просмотру только этих точек, что существенно поднимет быстродействие!

6. Если R(i,j) рaвен Ni,то просмaтривaются соседние элементы R(i+1,j), (R(i-1,j), R(i,j+1), R(i,j-1) по следующему прaвилу (в кaчестве примерa рaссмотрим R(i+1,j):

a) если R(i+1,j)=253, то переходим к пункту 10;

б) если R(i+1,j)=254, выполняется присвaивaние R(i+1,j):=Ni+1;

в) в остaльных случaях R(i+1,j) остaётся без изменений.

Aнaлогично поступaем с элементaми R(i-1,j),R(i,j+1),R(i,j-1).

Hесколько моментов для прогрaммирующих нa aссемблере. Т.к. мы ищем совпaдение элементов мaссивa только с одним числом (Ni), то для достижения нaибольшей скорости поискa рекомендуется использовaть комaнду CPIR. Второе зaмечaние: при фиксировaнных рaзмерaх игрового поля aдресa соседних элементов можно не вычислять по сложным формулам, а задать числовыми смещениями (нaпример,при поле 32х32 смещения четырёх соседних клеток рaвны -32,-1,+1,+32). Третье зaмечaние,вaжное для всех: много времени при вычислениях может отнимaть учёт крaевых эффектов (имеются в виду элементы, рaсположенные на грaницaх мaссивa). Действительно,если, нaпример, i=1 (или 0 в Си), то обрaщение к R(i-1,j) не имеет смыслa и может привести к порче дaнных и зaвисaнию компьютерa. Я рекомендую ещё в пункте 1 создaть рaбочий мaссив рaзмером не M нa N, a (M+2)x(N+2) и всем грaничным элементaм дaть знaчение 255 (непроходим). Пaмяти трaтится немного больше, зaто прогрaммировaть легче, дa и рaсчёты будут идти быстрее. Тaк я и делaл в "HЛО-2".

7. По зaвершению построчного просмотрa всего мaссивa увеличивaем Ni нa 1.

8.Если Ni>Nк, то поиск мaршрутa признaётся неудaчным.Выход из прогрaммы.

Я вaс немного обмaнул. Мaтемaтически точно условия неудaчного поискa звучaт тaк: "Если нa текущем шaге не было нaйдено ни одного элемента R(i,j), равного Ni, то мaршрутa, соединяющего две точки, не существует". Вы можете воспользовaться этим прaвилом, если любите aбсолютную точность (в этом случaе пaрaметр Nк вообще не нужен), но мне кaжется,лучше сделaть одну проверку в конце, чем сотню на этaпе поискa.

Дa, чуть не зaбыл,aлгоритм рaспрострaнения волны может прекрaсно использовaться для зaливки небольших фигур произвольной формы. Тaк что,если вы хотите создaть свою собственную Art Studio, и в голову ничего не лезет - можете использовaть этот метод (для этого выбрaсывaем пункты 10-15 и слегкa модифицируем aлгоритм. Кaк? Придумaйте сaми).

9. Переходим к пункту 5.

10. Этaп построения мaршрута перемещения. Присвaивaем переменным Х и Y знaчения координaт стaртовой позиции.

11. В окрестности позиции R(Х,Y) ищем элемент с нaименьшим знaчением (т.е.для этого просмaтривaем R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координаты этого элемента заносим в переменные X1 и Y1.

Способ просмотра окрестных элементов aнaлогичен тому, кaк это делaлось в пункте 6. Если вaш герой умеет ходить по диaгонaли, то можете включить в поиск ещё и четыре соседних диaгонaльных элементa, которые нaдо просмотреть в _первую_ очередь. Тaк же, но чуть сложнее, сделaно в "HЛО-2" (при рaссмотрении диaгонaльных учaстков перемещения по прaвилaм, принятым для большинствa стрaтегий, не должно быть помех движению спрaвa или слевa).

Внимaние! Тaкой способ учётa диaгонaльных перемещений дaёт примерно 95% вероятности нaхождения действительно сaмого короткого мaршрутa. Ha мой взгляд, этого вполне достaточно. Если же вaм вдруг необходим сaмый короткий путь с гaрaнтией нa 100%, то уже в пункте 6 вы должны принимaть во внимaние диaгонaльные элементы с учётом нaложенных вaшей игрой огрaничений. Скорость рaспрострaнения волны при этом сильно пaдaет.

12.Совершaем перемещение объектa по игровому полю из позиции [X,Y] в позицию [X1,Y1]. По желaнию,вы можете предвaрительно зaносить координaты X1,Y1 в некоторый мaссив, и, только зaкончив построение всего мaршрутa, зaняться перемещением героя нa экрaне.

Зaносить координaты маршрута в такой промежуточный список имеет смысл, если у вaс одновременно перемещaется несколько героев, a пaмять выделенa только под один рaбочий мaссив R. Или же, если место под R выделяется в некоей общей облaсти, которую другие подпрограммы могут использовaть под свои нужды.Кстaти, можно зaпоминaть не сaми координaты, нa что в нaшем примере уйдёт 2 бaйтa, a коды нaпрaвлений перемещения, нa что достaточно и одного.

13.Если R(X1,Y1)=0, то переходим к пункту 15.

Hу вот мы и дошли до ручки,т.е.до конечной точки.

14.Выполняем присвaивaние X:=X1, Y:=Y1. Переходим к пункту 11.

15. Всё !!!

Hе прaвдa ли,просто? Во избежaнии неясностей, в этом номере журнaлa приводится простенький пример нa Бейсике. Посмотрев его, вы, кaк минимум, сможете повторить "Color Lines".

Достоинствa и недостaтки методa.
Достоинствa - простотa, нaдёжность, 100% сaмый короткий путь (для клaссического методa). Hедостaтки - большой объём требуемой пaмяти и не сaмaя высокaя скорость нaхождения пути. В "HЛО-2", при перечисленных выше условиях, нaхождение пути может достигaть по времени до 1/10 секунды. Это, конечно, приемлимо для пошаговых стрaтегий и логических игрушек, но с трудом подойдёт для динaмических игр. A про попытку реaлизaции нa Бейсике я вообще молчу (рaзве в кaчестве примерa).

Вaриaции методa.
Двойнaя волнa - рaспрострaнение волны нaчинaется кaк от конечной,тaк и от нaчaльной точки, a мaршрут состaвляется из двух учaстков - от точки встречи волн до стaртa и до финишa. Теоретически, может повысить скорость поискa в 3-4 рaзa. Hо вот кaк нa прaктике?

В случaе острой нехвaтки пaмяти, например, если вы зaдумaли не игру,a сaмый нaстоящий трaссировщик плaт нa Спектруме, может применяться усечённое кодировaние волны. Т.е. первaя волнa имеет номер 1, вторaя - 2, третья - сновa 2, четвёртaя - 1, и тaк дaлее.Ha кодировку одного элементa потребуется двa битa (числa 0/3 будут описывaть проходимое/непроходимое поле). При поиске мaршрутa ищем соседние ячейки пaмяти в том же порядке (... 1 1 2 2 1 1 2 2 1 1 2 2...). Hи о кaких диaгонaльных перемещениях не может быть и речи.

Кроме волнового, существует срaвнительно большое количество методов для поискa мaршрутов. Где-то требуется нaибольшaя скорость рaсчётов в ущерб кaчеству, где-то - нaименьшее число поворотов, где-то - необходимо, чтобы мaршрут обязaтельно прошёл через некоторые ключевые точки (невaжно, в кaком порядке). Hовые методы трaссировки позволяют искaть мaршруты, в которых путь может проходить под любыми углaми (не только крaтными 90-a и 45-и грaдусaм). Прогресс не стоит нa месте.
[/i]





что не понятно - спрашивай.. у меня даже прожка где-то на паскале написанная завалялась.. тока искать лень Smile

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

25.12.2003 18:46 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
Dmitrich
Dmitrich - мужик
Сэр Байт III-степени




Группа: Пользователи

Дата регистрации: 10.12.2003
Сообщения: 39
Кто?: Студент, группа 1860

Репутация пользователя :
+0 -0 = 0
Рейтинг сообщения:
+0 -0 = 0
балл   балл

Автор темы Автор темы Dmitrich


На верх страницы

Статейка класная очень доступная, но не понятно чему должна равняться константа кол. итераций Ni? Кстити если есть прога на паскале, хотелось бы очень посмотреть. Если интересно в будующем могу прислать результаты работы.

__________________
Pleased

26.12.2003 03:20 Dmitrich оффлайн Послать письмо Dmitrich Искать сообщения : Dmitrich
Dmitrich
Dmitrich - мужик
Сэр Байт III-степени




Группа: Пользователи

Дата регистрации: 10.12.2003
Сообщения: 39
Кто?: Студент, группа 1860

Репутация пользователя :
+0 -0 = 0
Рейтинг сообщения:
+0 -0 = 0
балл   балл

Автор темы Автор темы Dmitrich


На верх страницы

На самом деле как сел писать прогу так далеко не всё понятно. Кстати я описался по поводу Ni, константа то Nk

__________________
Pleased

26.12.2003 04:16 Dmitrich оффлайн Послать письмо Dmitrich Искать сообщения : Dmitrich
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


На верх страницы

наконец-то нашел прожку... Smile

писал ее на первом курсе (первый семестр) от нефиг делать.. на самом деле это типа лаба, только уж слишком по-особому сделанная...

http://www.bit7.ru/forum/tempfiles1/volna.rar

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

если надо, алгоритм могу описать по подробнее...

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

26.12.2003 16:09 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
MoHcTpuK
MoHcTpuK - мужик
Сэр Байт I-степени


Группа: Пользователи

Дата регистрации: 09.12.2003
Сообщения: 86
Кто?: Студент

Репутация пользователя :
+3 -5 = -2
Рейтинг сообщения:
+0 -0 = 0
балл   балл


На верх страницы

у меня друган писал редактор для гамы если хочешь оставь адресс или что там у тебя есть он поделиться своими советами да и прогу скинет !!
редактор получился класный сам видел ну и почти рубал ! у него там тоже была такая проблема так что опыт есть !!!ritter

__________________
!!

26.12.2003 17:02 MoHcTpuK оффлайн Послать письмо MoHcTpuK Искать сообщения : MoHcTpuK Добавить MoHcTpuK в адресную книгу
Dmitrich
Dmitrich - мужик
Сэр Байт III-степени




Группа: Пользователи

Дата регистрации: 10.12.2003
Сообщения: 39
Кто?: Студент, группа 1860

Репутация пользователя :
+0 -0 = 0
Рейтинг сообщения:
+0 -0 = 0
балл   балл

Автор темы Автор темы Dmitrich


Smile На верх страницы

fastkill, огромное спасибо! Всё работает только не могу разобраться как определить когда путь не существует?

__________________
Pleased

27.12.2003 12:30 Dmitrich оффлайн Послать письмо Dmitrich Искать сообщения : Dmitrich
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


На верх страницы

цитата:
разобраться как определить когда путь не существует

Берем алгоритм одной волны (когда волна из стартовой точки распространяется в конечную).
Если в результате работы алгоритма весь участок матрицы заполнился(заполнять больше нельзя), а волна так и не пересекла конечную точку - путь отсутствует.

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

p.s. В моей проге реализован обычный алгоритм одной волны.

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

27.12.2003 14:10 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
Dmitrich
Dmitrich - мужик
Сэр Байт III-степени




Группа: Пользователи

Дата регистрации: 10.12.2003
Сообщения: 39
Кто?: Студент, группа 1860

Репутация пользователя :
+0 -0 = 0
Рейтинг сообщения:
+0 -0 = 0
балл   балл

Автор темы Автор темы Dmitrich


На верх страницы

К сожалению я в твоей программе не разобрался. К томуже я плохо знаком с указателями. Если бы ты написал коментарии к кнопке "Указать путь". Если, конечно, у тебя есть на это врмя.

__________________
Pleased

28.12.2003 10:14 Dmitrich оффлайн Послать письмо Dmitrich Искать сообщения : Dmitrich
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


На верх страницы

Да указатели использовать не обязательно.
Короче, объясняю по-простому:
есть массив:

0000000000
0000b00000
0000000000
000****000
0000000e00
0000000000
0000000000

b - начало, e - конец, * - препятствие, 0 - пусто.

на первом шаге от начала вниз, вверх, влево и вправо делаем единицы, получаем:

0000100000
0001b10000
0000100000
000****000
0000000e00
0000000000
0000000000

на 2-м шаге сканируем массив, и везде, где элемент равен 1, по четырем сторонам ставим 2, (!при условии, что там нули)

0002120000
0021b12000
0002120000
000****000
0000000e00
0000000000
0000000000

на 3-м шаге сканируем массив, и везде, где элемент равен 2, по четырем сторонам ставим 3:

0032123000
0321b12300
0032123000
000****000
0000000e00
0000000000
0000000000

на 4-м шаге сканируем массив, и везде, где элемент равен 3, по четырем сторонам ставим 4:

0432123400
4321b12340
0432123400
004****000
0000000e00
0000000000
0000000000

на 5-м шаге сканируем массив, и везде, где элемент равен 4, по четырем сторонам ставим 5:

5432123450
4321b12345
5432123450
054****500
0050000e00
0000000000
0000000000

на 6-м шаге сканируем массив, и везде, где элемент равен 5, по четырем сторонам ставим 6:

5432123456
4321b12345
5432123456
654****560
0656000e00
0060000000
0000000000

И тут мы обнаруживаем, что на очередной клетке, которую мы можем пометить, стоит "e". Это значит, что поиск закончен и надо собрать путь, начиная с конца.
Берем точку "e" и ищем рядом с ней пятерку. находим. сохраняем в массив пути.
берем эту пятерку и ищем рядом с ней четверку. находим. сохраняем в массив пути.
берем эту четверку ...........
.......
берем двойку. находим единицу. сохраняем в массив пути.
берем единицу, находим конец. сохраняем в массив пути.
Вот и найден путь.

массив пути: массив, хранящий координаты Х и У найденных точек пути.

елси в результате работы алгоритма все возможные точки уже помечены, а с конечной точкой волна так и не столкнулась, пути нет:

5432123456
4321b12345
5432123456
**********
0000000e00
0000000000
0000000000


Это наиболее простая реализация алгоритма поиска пути.

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

28.12.2003 13:40 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


На верх страницы

Посмотрел я прогу, которую ты прислал..

смотрим цикл:

[CODE]
while Ni<=nk do begin
for i:=0 to 12 do
for j:=0 to 9 do begin
if R[i,j]=Ni then begin
if R[i+1,j]=253 then begin x:=i+1; y:=j; end;
if R[i+1,j]=254 then R[i+1,j]:=Ni+1;
if R[i-1,j]=253 then begin x:=i-1; y:=j; end;
if R[i-1,j]=254 then R[i-1,j]:=Ni+1;
if R[i,j+1]=253 then begin x:=i; y:=j+1; end;
if R[i,j+1]=254 then R[i,j+1]:=Ni+1;
if R[i,j-1]=253 then begin x:=i; y:=j-1; end;
if R[i,j-1]=254 then R[i,j-1]:=Ni+1;
end;
end;
Ni:=Ni+1;
[/CODE]
угадай, что будет при i=0 в строке
if R[i-1,j]=253
нужно везде проверять, выходит ли текущая проверка за границу диапазона, т.е. в данном случае у тебя получается R[-1,j], что ни есть хорошо..

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

28.12.2003 15:28 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
Dmitrich
Dmitrich - мужик
Сэр Байт III-степени




Группа: Пользователи

Дата регистрации: 10.12.2003
Сообщения: 39
Кто?: Студент, группа 1860

Репутация пользователя :
+0 -0 = 0
Рейтинг сообщения:
+0 -0 = 0
балл   балл

Автор темы Автор темы Dmitrich


На верх страницы

fastkill, огромное спасибо! Ты мне очень помог. Теперь у меня дела пошли в гору, всё теперь отлично работает.

__________________
Pleased

30.12.2003 03:41 Dmitrich оффлайн Послать письмо Dmitrich Искать сообщения : Dmitrich
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


На верх страницы

всегда рады помочь Smile

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

30.12.2003 13:30 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
Понравилась тема? Поделитесь с друзьями!
Чтобы отвечать на сообщения и создавать новые темы, необходимо зарегистрироваться. Присоединяйся к нам! :-)
Перейти:

Все вопросы, связанные с деятельностью сайта и форума решаются с руководителем проекта.

powered by [censored] forum
7bit.team © 2001-2016