| Тема: Алгоритм обхода припятствий? Страниц: 1 | Прочитано 4979 раз |
derick
[НефтеКачок-Derrick]
Неназываемый
Я люблю этот Форум!
Пол: 
Репутация: +3
|
 |
Алгоритм обхода припятствий?
« от 22.04.2005 в 08:17:45 » |
|
Кто знает?
|
|
 Зарегистрирован |
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
 
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #1 от 22.04.2005 в 19:18:59 » |
|
А чего тут знать, в JA используется стандартный A*
|
|
Зарегистрирован |
|
|
|
Ломолом
[словоплут]
забанен
Был бы умным - репа была бы 400!!!
Пол: 
Репутация: +224
|
|
Re: Алгоритм обхода припятствий?
« Ответ #2 от 22.04.2005 в 20:02:38 » |
|
2Force_Majeure:
Хороший ответ!
|
|
Зарегистрирован |
Многие меня поносят
И теперь, пожалуй, спросят:
Глупо так зачем шучу?
Что за дело им? Хочу. (А.С. Пушкин)
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #3 от 23.04.2005 в 05:38:06 » |
|
2Ломолом:
Quote:2Force_Majeure:
Хороший ответ! |
|
Каков вопрос 
|
|
Зарегистрирован |
|
|
|
derick
[НефтеКачок-Derrick]
Неназываемый
Я люблю этот Форум!
Пол:
Репутация: +3
|
|
Re: Алгоритм обхода припятствий?
« Ответ #4 от 03.05.2005 в 19:49:57 » |
|
так чем не понятен вопрос?? я имею в виду как персонаж выбюирает пусть обхода препятвия
|
|
Зарегистрирован |
|
|
|
derick
[НефтеКачок-Derrick]
Неназываемый
Я люблю этот Форум!
Пол:
Репутация: +3
|
|
Re: Алгоритм обхода припятствий?
« Ответ #5 от 03.05.2005 в 19:50:53 » |
|
т.е. щелкаешь, а он же идет не напрямик, а обходит деревья и т.д.
|
|
Зарегистрирован |
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #6 от 04.05.2005 в 07:50:56 » |
|
т.е. тебе изложить сам алгоритм?
В кратце принцип такой: известны координаты (в двумерной плоскости карты) точки А, где стоит человек и В, куда ему нужно переместиться. По ним находится длина L прямой между этими точками. Карта делится на клетки (массив) заполненные 0, значит свободно, и 1, там где есть препятствие. Из точки А делается "ход" персонажа на одну клетку карты по всем 8 направлениям (самоадресуемый список). Длину каждого из 8 маршрутов считают исходя из того, что двинуться на соседнюю клетку напрямую стоит 2 ед., а по диагонали 3. При движении, ессно, берем только теварианты, где "свободно". Все 8 вариантов кладутся в массив Р. Все имеющиеся арианты сравниваются с L и выбирается наиболее близкий. далее обсчитываем его по томуже принципу, а 7 ост. вариантов сбрасываются в др. масств Р1, их нельзя выбрасывать т.к. в последствии они могут оказаться более выгодными, чем идти напрямую (например, если прямой путь заведет внутрь препятствия, по форме буквы "П"), тогда из Р1 достается наиболее выгодный вариант и все продолжается уже с ним.
|
|
Зарегистрирован |
|
|
|
Mr Evil
[С бобровой тушкой :)]
Иван
Я страшный, но общительный.
Пол:
Репутация: +114
|
|
Re: Алгоритм обхода припятствий?
« Ответ #7 от 11.06.2005 в 11:47:57 » |
|
Даже не знаю в какую тему вопрос написать.
Вопрос такой: Каким образом можно транспорту прописать хождение по водной глади на тактической карте? (По принципу Хамера на дорогах).
Я понял, что нужно прописать сектора, по которым транспортное средство может передвигаться. Я прв или нет?
|
| « Изменён в : 11.06.2005 в 11:48:21 пользователем: Де Магог » |
Зарегистрирован |
"Если земляне не будут постоянно
тренировать губы, у них начнут работать мозги."
Дуглас Адамс
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #8 от 11.06.2005 в 12:21:46 » |
|
2Mr Evil:
Как хаммер ездит по дорогам в JA?
Классический случай применения Астар.
Quote:| понял, что нужно прописать сектора, по которым транспортное средство может передвигаться. Я прв или нет? |
|
Простой думерный массив с 0 и 1. 0 - сектор с водой, 1 - там где ехать нельзя (суша).
|
|
Зарегистрирован |
|
|
|
Mr Evil
[С бобровой тушкой :)]
Иван
Я страшный, но общительный.
Пол:
Репутация: +114
|
|
Re: Алгоритм обхода припятствий?
« Ответ #9 от 11.06.2005 в 13:44:35 » |
|
2Force_Majeure: Хм... Довольно просто. Спасибо. 
|
|
Зарегистрирован |
"Если земляне не будут постоянно
тренировать губы, у них начнут работать мозги."
Дуглас Адамс
|
|
|
Ghaydn
[Гомпозитор]
Прирожденный Джаец
Рисую карты в блокноте. Ищу кнопку сохранения.
Пол:
Репутация: +203
|
|
Re: Алгоритм обхода припятствий?
« Ответ #10 от 13.08.2006 в 21:44:01 » |
|
Крайне странно смотрится в свете описанного выше алгоритма обхода препятствий. В бою такой путь может оказаться фатальным. За врагами и ополченцами такого я не замечал, так как AI несколько шире возможности управления. В частности враги могут замирать на бегу каждую клетку аналогично нажатию ESC, но не останавливаясь, что бы привело к лишней трате очков за повторное начало бега.
Просто к слову пришлось.
|
|
Зарегистрирован |
— Доктор, меня не понимают...
— вРН БШ ЯЙЮГЮКХ?
|
|
|
Чертовска Вражiна
[Serj_PSG]
Прирожденный Джаец
Когда-то я любил сей форум
Репутация: +612
|
|
Re: Алгоритм обхода припятствий?
« Ответ #11 от 14.08.2006 в 02:10:13 » |
|
Ghaydn:
В СквадЛидере м.б. путь по клеткам отметить: часть пути которая тебя устраивает в конце помечается 1 кликом, а далее м. другой маршрут избирать и помечать его. Когда весь путь отметил -- двойной клик и происходит движение. Но это только к багмонстру -- если сможет расковырять и переделать данный алгоритм.
|
|
Зарегистрирован |
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #12 от 15.08.2006 в 13:21:04 » |
|
2Ghaydn:
А что странного? Если бы дерева не было, он шел бы по диагонали (на рисунке вниз) до конца, а потом повернул направо. А так, он дошел до дерева, обогнул его и дальше продолжил обычный путь. А опасности боя классический А-стар не учитывает, для этого нужно какие-то модификации.
|
|
Зарегистрирован |
|
|
|
Ghaydn
[Гомпозитор]
Прирожденный Джаец
Рисую карты в блокноте. Ищу кнопку сохранения.
Пол:
Репутация: +203
|
|
Re: Алгоритм обхода припятствий?
« Ответ #13 от 19.08.2006 в 21:44:00 » |
|
2Force_Majeure: Обогнуть дерево можно двумя путями. Но он почему-то упорно выбирает именно тот, что длиннее. И дело даже не только и не столько в опасности боя, сколько в элементарном просчёте: проход слева длиннее, чем справа. Значит, при сравнении длины путей правый не просчитывается совсем. Значит, алгоритм неполный/несовершенный. Значит, его надо доработать.
|
|
Зарегистрирован |
— Доктор, меня не понимают...
— вРН БШ ЯЙЮГЮКХ?
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #14 от 20.08.2006 в 06:10:10 » |
|
2Ghaydn:
Quote:| Обогнуть дерево можно двумя путями. Но он почему-то упорно выбирает именно тот, что длиннее. |
|
Огибать дерево с разных сторон - стоит равнозначно, если я не ошибаюсь в подсчетах, красный и синий пути займут одинаковое кол-во ОД.
|
|
Зарегистрирован |
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #15 от 21.08.2006 в 10:18:17 » |
|
2Force_Majeure:
вообщето 4 против 3
|
|
Зарегистрирован |
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #16 от 21.08.2006 в 13:33:03 » |
|
2Strax5:
Может я где то ошибаюсь? Первые три клетки абсолютно одинаковы, так? Остается или две клетки по красному пути 2+2=4 очка или одна клетка по синему плюс поворот 3+1=4 очка.
|
|
Зарегистрирован |
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #17 от 23.08.2006 в 13:01:23 » |
|
2Force_Majeure:
0.5 + 3 + 0.5 = 4 полных (всего 5 клеток)
0.5 + 2 + 0.5 = 3 полных (всего 4 клетки)
А поворот отдельно считается?
|
| « Изменён в : 23.08.2006 в 13:02:11 пользователем: Strax5 » |
Зарегистрирован |
|
|
|
Ghaydn
[Гомпозитор]
Прирожденный Джаец
Рисую карты в блокноте. Ищу кнопку сохранения.
Пол:
Репутация: +203
|
|
Re: Алгоритм обхода припятствий?
« Ответ #18 от 23.08.2006 в 20:21:43 » |
|
Вообще если быть совсем точным, то сама система траты очков в игре меня смущает. Тайл ведь при взгляде сверху (а не в проекции) имеет форму квадрата. Значит, примем его сторону за 1. Тогда диагональ будет равна корню из двух, то есть примерно 1.4. Приравнять 1.4 к двум совсем уж не получается (приравняем к 1.5 ). Теперь подсчитаем путь Карлоса с имеющимися данными. Получается синий 6, а красный 7. В жизни путь получился бы длиннее на целую единицу.
|
|
Зарегистрирован |
— Доктор, меня не понимают...
— вРН БШ ЯЙЮГЮКХ?
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #19 от 24.08.2006 в 08:30:20 » |
|
2Strax5:
В классическом а-старе нет, но в Джа ведь считаются. Никак не пойму, как ты счиатешь, но кажется догнал, в чем моя ошибка, не считал одного поворота на красном пути, действительно получается красный на единицу длиннее.
2Ghaydn:
В а-старе обычно прямой переход берут за 2 а диагональный за 3.
|
|
Зарегистрирован |
|
|
|
Ghaydn
[Гомпозитор]
Прирожденный Джаец
Рисую карты в блокноте. Ищу кнопку сохранения.
Пол:
Репутация: +203
|
|
Re: Алгоритм обхода припятствий?
« Ответ #21 от 24.08.2006 в 12:15:33 » |
|
2lalien: Не считаются ни при ходьбе, ни при любом другом движении.
|
|
Зарегистрирован |
— Доктор, меня не понимают...
— вРН БШ ЯЙЮГЮКХ?
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #22 от 25.08.2006 в 08:00:14 » |
|
Хм, действительно, повороты не считаются. Вот что значит давно в Джа не играл
Тогда и вправду, путь предложенный алгоритмом длиннее, с чем это связано не знаю 
|
|
Зарегистрирован |
|
|
|
GreenEyeMan
[Добрый волшебник]
Псих
Истина как-то тут, а я ее где-то там.
Пол:
Репутация: +274
|
|
Re: Алгоритм обхода припятствий?
« Ответ #23 от 23.09.2006 в 04:47:35 » |
|
Надеюсь в правильную ветку задал вопрос. Можно ли (если можно то где) изменить скорость передвижения персов\вражин\монстров? Запретить бег для врагов?
|
|
Зарегистрирован |
Я счастлив, а остальное побоку.
|
|
|
bugmonster
[Баги! Баги везде!]
Source
ПРОГРАММИРЫ НЕ УЧИТЫВАЛИ ЭТУ СИТУАЦИЮ
Пол:
Репутация: +1337
|
|
Re: Алгоритм обхода припятствий?
« Ответ #24 от 26.09.2006 в 15:30:44 » |
|
2GreenEyeMan:
Quote:| Надеюсь в правильную ветку задал вопрос |
|
И не надейся, но модеры разберутся, если что
Quote:| Можно ли (если можно то где) изменить скорость передвижения персов\вражин\монстров? |
|
Что ты подразумеваешь под "скоростью передвижения"? Если скорость анимации, то в JA2CW это сделано.
Quote:| Запретить бег для врагов? |
|
Можно. Если сильно надо, могу поискать где и что менять.
|
|
Зарегистрирован |
Восславим же радость и мужество,
Труда и науки содружество
Восславим мудрую партию,
Помолимся за неё.
А Пентагон в свои руки поганые,
Пусть возьмёт свои доллары сраные
И в ж... себе затолкает
|
|
|
GreenEyeMan
[Добрый волшебник]
Псих
Истина как-то тут, а я ее где-то там.
Пол:
Репутация: +274
|
|
Re: Алгоритм обхода припятствий?
« Ответ #25 от 26.09.2006 в 19:18:49 » |
|
2bugmonster: "Если сильно надо, могу поискать где и что менять." - ну, если не в лом.  А если еще в своу ПдМ такую возможность встроешь, вообще здоровски будет.
"скорость анимации" - ну да, но только не для всех, а для отдельных "особей".
|
|
Зарегистрирован |
Я счастлив, а остальное побоку.
|
|
|
bugmonster
[Баги! Баги везде!]
Source
ПРОГРАММИРЫ НЕ УЧИТЫВАЛИ ЭТУ СИТУАЦИЮ
Пол:
Репутация: +1337
|
|
Re: Алгоритм обхода припятствий?
« Ответ #26 от 02.10.2006 в 12:54:53 » |
|
2GreenEyeMan: Вообще скорость анимации движения в Джа и так рассчитывается "на лету" в зависимости от многих праметров: пошаговка/реалтайм, бодитайп, физ. параметры, усталость, здоровье. Поэтому уточни: что требуется по задумке?
|
|
Зарегистрирован |
Восславим же радость и мужество,
Труда и науки содружество
Восславим мудрую партию,
Помолимся за неё.
А Пентагон в свои руки поганые,
Пусть возьмёт свои доллары сраные
И в ж... себе затолкает
|
|
|
GreenEyeMan
[Добрый волшебник]
Псих
Истина как-то тут, а я ее где-то там.
Пол:
Репутация: +274
|
|
Re: Алгоритм обхода припятствий?
« Ответ #27 от 04.10.2006 в 19:01:32 » |
|
2bugmonster: В принципе, хочеться отключить бег и снизить в два раза скорость передвижения пешком у определенного перса (допустип - качок). Можно сказать, это ради эксперемента толлько: можно или нельзя.
|
|
Зарегистрирован |
Я счастлив, а остальное побоку.
|
|
|
VM
[Генеральный застройщик пустоши]
Прирожденный Джаец
Советские часы - самые быстрые в мире!
Пол:
Репутация: +969
|
|
Re: Алгоритм обхода припятствий?
« Ответ #28 от 04.10.2006 в 19:30:16 » |
|
2GreenEyeMan: Скорость передвижения напрямую зависит от подвижности перса. Уменьши ее в его профиле и получишь медленного качка.
|
|
Зарегистрирован |
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #29 от 02.11.2006 в 12:56:12 » |
|
А как вам такой обход? 
|
|
Зарегистрирован |
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #30 от 16.02.2007 в 20:10:52 » |
|
Вот такой еще обход препятсвия. Если курсор поставть на одну клетку выше - обход будет с другой стороны.
|
|
Зарегистрирован |
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #31 от 02.04.2008 в 09:13:47 » |
|
Вот еще глючные обходы.
При этом если сделать пару шагов по этому пути, Барри автоматически получает стакон дроби в голову.
|
|
Зарегистрирован |
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #32 от 02.04.2008 в 09:16:42 » |
|
Самый нелогочный на мой взгляд.
|
|
Зарегистрирован |
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #33 от 02.04.2008 в 09:16:59 » |
|
Еще один
|
|
Зарегистрирован |
|
|
|
pipetz
[пипец всему!]
Прирожденный Джаец
Я очень люблю этот Форум!
Пол:
Репутация: +303
|
|
Re: Алгоритм обхода припятствий?
« Ответ #34 от 02.04.2008 в 09:40:28 » |
|
В 2, 3 такое ощущение что такой путь игра считает более безопасным.
Вообще алгоритм обхода, кажется, отличается в скрытном режиме.
Но у тебя тут везде не скрытный режим. Почему так ныкаются непонятно.
|
|
Зарегистрирован |
- Джаец?
- Джаиц, джаиц.
- Ну, джаец, ну погоди!
https://github.com/egorovav/Ja2Project/releases
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #35 от 05.05.2008 в 13:15:14 » |
|
Вот еще глюк с передвижением мне абсолютно не понятный.
Если Стефен бежит прямо - 7 АР, если сворачивает направо сразу после входа - 8.
А если налево - 10.
|
|
Зарегистрирован |
|
|
|
Strax5
[Пятижды пуганый]
Прирожденный Джаец
Дорогу осилит бегущий
Пол:
Репутация: +647
|
|
Re: Алгоритм обхода припятствий?
« Ответ #36 от 05.05.2008 в 13:15:34 » |
|
Вот так.
|
|
Зарегистрирован |
|
|
|
pipetz
[пипец всему!]
Прирожденный Джаец
Я очень люблю этот Форум!
Пол:
Репутация: +303
|
|
Re: Алгоритм обхода припятствий?
« Ответ #37 от 14.08.2009 в 05:27:46 » |
|
Ну, вот я и досюда добрался.
2Force_Majeure: 22.04.2005 в 19:18:59, Force_Majeure писал(a):| А чего тут знать, в JA используется стандартный A* |
|
Откуда такая информация? Неужели из исходников? 
Я спрашиваю потому что сам в них нефига не разобрался.
Там активно используется оператор "goto". Я как увидел чуть в обморок не упал.
Вот в 1.13 точно A* по крайней мере судя по названиям классов и функций.
Если кто интересуется алгоритмом А* вот небольшая прога с исходниками на C#.
По моему очень наглядно. Автор некий Карлос Барбоса.
Я правда немного подправил, у него там не A* было, а какой-то A+.
|
|
Зарегистрирован |
- Джаец?
- Джаиц, джаиц.
- Ну, джаец, ну погоди!
https://github.com/egorovav/Ja2Project/releases
|
|
|
Force_Majeure
[Непреодолимая сила]
Прирожденный Джаец
Ах, было б только с кем поговорить ...
Пол:
Репутация: +526
|
|
Re: Алгоритм обхода припятствий?
« Ответ #38 от 14.08.2009 в 06:52:24 » |
|
2pipetz:
2005 год... тогда исходники еще не копали А писал я это судя просто по тому, как осуществляется обход мерками препятствий. Естественно, мог и ошибаться, но скорее всего там все-таки она родимая А-звездочка.
|
|
Зарегистрирован |
|
|
|
pipetz
[пипец всему!]
Прирожденный Джаец
Я очень люблю этот Форум!
Пол:
Репутация: +303
|
|
Re: Алгоритм обхода припятствий?
« Ответ #39 от 14.08.2009 в 07:16:59 » |
|
14.08.2009 в 06:52:24, Force_Majeure писал(a):| Естественно, мог и ошибаться, но скорее всего там все-таки она родимая А-звездочка. |
|
Да вот ХЗ. Она или не она. Зачем тогда создатели 1.13 переписали этот код именно под A*?
Ежели он уже был A*. Возможно, конечно, просто чтобы отрефакторить , в смысле "причесать".
Дело тёмное. Надо медведей трясти.
|
|
Зарегистрирован |
- Джаец?
- Джаиц, джаиц.
- Ну, джаец, ну погоди!
https://github.com/egorovav/Ja2Project/releases
|
|
|
|
Главная
Помощь
Поиск
Участники
Вход
Регистрация
algoritm.jpg
Noch_ein_Umweg.bmp-1.jpg
A_kak_vam_eto.jpg
Obxod.jpg
Samy_korotkiy_put.jpg
AP_Gluck_8.jpg
AP_Gluck_10.jpg
cbastar.zip
Послать Тему
Печатать