DanFi
offline
Опыт:
7,220Активность: |
Алгоритм нахождения пути. VB.
Добрый вечер!
Начал я тут недавно создавать (опять) игру свою (2D, с видом сверху, стрелялка). Работает всё отлично. Присутствует редактор карт, ГГ уже и анимирован, и стрелять умеет, и ходить… НО! Столкнулся с большой проблемой! Забыл про AI… когда начал программировать, столкнулся с большой проблемой… противники не могут найти и дойти до ГГ! Была ошибка в алгоритме нахождения пути. Противники, то тупо останавливались, то упирались в стены. Мучился долго. Потом со злости, что ничего не получилось, снёс ИИ к чёрту, а в мести и с ИИ пол кода программы (не заметил…немного…). Теперь восстанавливаю. Помогите, кто может! Я, конечно, понимаю, что это сложнейший алгоритм, но хотя бы подтолкните меня на это, пожалуйста! SWF- ролик. Описание:
Белый квадрат – пусто (Значение 0) Коричневый квадрат – стена (Значение 1) Зелёный – враг (Значение 4) Жёлтый – ГГ (значение 10) Зелёная линия – правильный путь противника Коричневый – неправильный Заранее благодарю! |
21.12.2006, 21:57 | #1
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
DanFi
offline
Опыт:
7,220Активность: |
ComotozNick, ты какие языки программирования знаешь?
|
21.12.2006, 22:55 | #2
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
ComotozNick
Активность: 666
offline
Опыт:
26,206Активность: |
C++, Perl |
21.12.2006, 23:05 | #3
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
DanFi
offline
Опыт:
7,220Активность: |
Посмотрел? Есть идеи, как это реализовать? Я даже не знаю с чего отталкиваться... Хотя нет, я думаю, можно реализовать с помощью ОЧЕНЬ большого количества If. |
21.12.2006, 23:08 | #4
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
ComotozNick
Активность: 666
offline
Опыт:
26,206Активность: |
DanFi я подумаю в течение сегодня-завтра, потом выложу.
Самый простой (и нудный в реализации) вариант - тупой перебор всех полей, потом находить все возможные варианты как проити и из них выбирать самый короткий, но это реализовать просто задолбаешься. |
21.12.2006, 23:11 | #5
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
DanFi
offline
Опыт:
7,220Активность: |
Ну вот я о том же... Хотя можно с помошью For... |
22.12.2006, 08:23 | #6
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
DanFi
offline
Опыт:
7,220Активность: |
С помощь IF у меня ни чё не получилось! |
22.12.2006, 19:02 | #7
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
nic666
offline
Опыт:
5,612Активность: |
Вообще алгоритм нахождения кратчайшего пути базируется на том, что нужен двумерный массив и в первую клетку заносится 1, затем а каждую точку рядом с начальной заносится 2, кроме той, что содержит 1, затем в следующие рядом с теми что содеражат 2, заносится 3, но при условии что там 0, но не 1 или 2 и .т.д. И так до тех пор пока не дойдешь до конечной точки. А тогда остается лишь пройтись по точкам со значениями 1,2,3,4,N и вот тебе кратчайший путь... |
22.12.2006, 21:05 | #8
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
DanFi
offline
Опыт:
7,220Активность: |
Да ты гений! Только я немного не понял. сейчас вникну.
DanFi добавил: Я и использую двухмерный массив. DanFi добавил: А как быть, если присутствуют стены? |
22.12.2006, 21:55 | #9
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
nic666
offline
Опыт:
5,612Активность: |
Имеется ввиду ставить числа в клетки связанные с текущей. Сначала ставишь единицу (она всего одна в начальной клетке), потом просматриваешь 8 клеток вокруг и ставишь 2 в те с которымы есть связь (может и 4 а не 8, смотря какой у тебя лабиринт), там где стены - там не надо ставить ничего (должен 0 остаться)... потом просматриваешь двойки и ставишь 3 в те клетки с которыми связь есть, но там не туда где 1 или 2 и т.д. Этот алгоритм придумали в 198х затертом году он называется "волновой алгоритм поиска пути", и дает 100% результат, если конечно вообще путь есть... |
22.12.2006, 22:19 | #10
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
ComotozNick
Активность: 666
offline
Опыт:
26,206Активность: |
nic666 говорит толковую идею. У меня была подобная идея, но там были недочеты и я ее откинул... как получается зря.
|
22.12.2006, 23:23 | #11
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Mefist
Is it cocktail hour yet?
offline
Опыт:
98,240Активность: |
а может кто-нибудь на словах объяснить как вообще работает такой алгоритм? и лично ничего придумать не могу =\ |
22.12.2006, 23:52 | #12
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
ComotozNick
Активность: 666
offline
Опыт:
26,206Активность: |
% щас попытаюсь тебе накатать рисунок, чтобы ты понял суть идеи..
|
23.12.2006, 00:09 | #13
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Алгоритм нахождения кратчайшего пути - построение дерева достижимости. Да, млин, по этой теме материалов - хоть залейся. Суть в том что находятся все кратчайшие пути от начальной, до каждой точки карты, итерационно, пока не встречаем нашу конечную точку, когда встречаем, просто формируем путь, по которому мы в нее пришли. Помогает литература по теории алгоритмов, и почти уверен что статьи по этой теме есть на геймдеве |
23.12.2006, 16:52 | #14
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
zibada
offline
Опыт: отключен
|
|
23.12.2006, 17:14 | #15
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Mefist
Is it cocktail hour yet?
offline
Опыт:
98,240Активность: |
спасиб .. почитаю |
24.12.2006, 17:37 | #16
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
exploder
iOS zealot
offline
Опыт:
19,394Активность: |
|
25.12.2006, 14:38 | #17
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Sir Lothar
offline
Опыт:
5,740Активность: |
Цитата:
Сомневаюсь ) Точно такое же было написано в одной из статей журнала "Игромания" (цикл по програмированию в GLScene). |
|
25.12.2006, 15:03 | #18
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
DanFi
offline
Опыт:
7,220Активность: |
Дай ссылку на статью |
25.12.2006, 17:12 | #19
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
nic666
offline
Опыт:
5,612Активность: |
А в чем проблема? Я же в принципе описал как делать.
Единствено забыл указать ньанс:
|
26.12.2006, 09:50 | #20
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|