MF
Что-то вокруг не так
  offline
Опыт:
26,594Активность: |
Path Finding
Возник такой, скорее теоритический, вопрос. Возможно ли (при наличае базы коэфициентов проходимости всех тайлов вара) реализовать прохождение юнитом пути от точки до точки так чтоб сумма коэфициентов тайлов пройденных юнитом была наименьшей? (желательно с идеей, выраженной в словах (в код я перевести сумею), с тем что это алгоритм поиска на графе с различными весами вершин я знаком, но те методы поиска кратчайшего пути которые мне известны не обеспечат нужной скорости) Отредактировано MF_Andreich, 19.01.2009 в 12:27. |
19.01.2009, 12:19
|
|
alexkill
 offline
Опыт:
18,872Активность: |
Можно. Теорию графов вспомни. |
|
19.01.2009, 12:46
|
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
Я ее и не забывал... такое разве забудешь? только от одного воспомианая про третий курс и экзамен по теориям алгоритмов мороз по коже... А уж про реализацию алгоритма Дейкстры лучше не вспоминать вовсе... ибо не подойдут они скорее всего... долго. |
|
19.01.2009, 12:48
|
ScorpioT1000
Работаем
  offline
Опыт: отключен
|
а где трабла? проверка на проходмость есть, ордеры есть |
|
19.01.2009, 14:25
|
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
в том то и дело... допустим. на снежной карте есть каменная дорожка. и не одного припятствия. (но!) предположим у нас есть так же база в которой снег имеет проходимость 2. то есть увязает в нем герой по колено, а по камню он бегает махом коэффициент 1. нужно чтоб герой при отдачи приказа бежать, бежал не напрямую (как скажет ему вар3) а по возможности по дороге, но так чтоб сумма коэфициентов при этом не превышала бы ту сумму что была бы при проходе напрямую...
Алгоритмом Дейкстры пахнет очень сильно, но не хочеться его реализовывать. Вот и спрашиваю, может есть какие другие идеи? |
|
19.01.2009, 14:33
|
|
NETRAT
 offline
Опыт:
83,712Активность: |
проблема в том что это в любом случае
|
|
19.01.2009, 14:33
|
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
Вот. Уже то что надо. одно мнение против. |
|
19.01.2009, 14:34
|
|
NETRAT
offline
Опыт:
83,712Активность: |
такие вещи оптимизируются выбором ключевых точек и определением заранее выгодных маршрутов - то есть в твоем случае дорожка - в любом случае выгодный маршрут, ключевыми точками выбираются ее начало и ее конец и ее вес считается 0 - то есть точка ее начала [кагбе] совмещается с точкой конца.
Забудь про графы на jass NETRAT добавил: ну и, красиво внедриться в движок, управляющий приказами юнитов все равно не получится, это уже 3 причина забить |
|
19.01.2009, 14:39
|
|
ScorpioT1000
Работаем
offline
Опыт: отключен
|
а я разве говорил что я бы стал? нет конечно, там даже на ихних cpp финдингах утечки
ну нет, попробовать то можно, просто стоит-ли оно того? можно напр. заюзать стандартный финдинг в комбо с дамми |
|
19.01.2009, 14:41
|
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
как это делаеться если заранее известен граф (в данном случае карта) я знаю. Математик все таки. Интересно было бы увидеть решение в общем случае. Но как и подозревал лаги будут дикие... придеться отказаться от идеи... |
|
19.01.2009, 14:41
|
|
NETRAT
offline
Опыт:
83,712Активность: |
ScorpioT1000 ты меня что ли спрашиваешь?
Брр, читать в направлении графов... Имеется карта проходимости Warcraft Pathing Map (.wpm) которая генерится редактором, во время загрузки эта карта анализируется, строится тот же граф (в случае сетки граф строить даже не нужно). А дальше... В играх, в основном используется http://www.google.ru/search?hl=ru&q=A+Star+pathfinding http://ru.wikipedia.org/wiki/Алгоритм_поиска_A* http://en.wikipedia.org/wiki/A*_search_algorithm (здесь, как всегда, больше и интересней чем на русском) http://www.firststeps.ru/theory/karta.html |
|
19.01.2009, 14:54
|
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
Спасибо NETRAT буду читать. Если идея выгорит, ждите что-то, по крайней мере, интересное.
MF_Andreich добавил: и еще вопрос в пределах этой темы. Можно ли проверить проходим ли весь квадрат 128*128? а не точка. |
|
19.01.2009, 15:06
|
|
PlayerDark
Coraline
 offline
Опыт:
10,569Активность: |
а чем обычный волновой алгоритм не проходит ? |
|
19.01.2009, 15:12
|
|
NETRAT
offline
Опыт:
83,712Активность: |
что значит "проходим ли весь квадрат"? |
|
19.01.2009, 15:19
|
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
PlayerDark
Хотя бы ссылочку на описание. А то нас только "умным" алгоритмам учат, а не оптимальным. NETRAT Ну грубо говоря есть квадрат 128*128 (его координаты все мы знаем) как проверить сможет ли в нем стоять юнит с картой пути 128*128 (ничего кроме как попробовать создать в нем юнита с такой картой пути и затем сравнить его координаты с центром мне в голову не пришло) |
|
19.01.2009, 15:19
|
|
NETRAT
offline
Опыт:
83,712Активность: |
PlayerDark читай внимательно - волновой ищет без предположений об оптимальном пути - то есть по всем направлениям сразу. A* ищет в направлении оптимального пути - то есть, как правило, в направлении целевой точки, поэтому он почти всегда, быстрее.
NETRAT добавил: MF_Andreich волновой указан в последней ссылке |
|
19.01.2009, 15:21
|
|
adic3x
offline
Опыт:
108,439Активность: |
Цитата:
мувнуть юнита и посмотреть потом его координаты? |
|
|
19.01.2009, 15:22
|
|
NETRAT
offline
Опыт:
83,712Активность: |
это как-то wierd приложить одну карту пути ко второй и посмотреть совпадают ли они |
|
19.01.2009, 15:23
|
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
ADOLF
да... мне только это в голову и пришло. NETRAT Это реализуемо? (я очень давно занимался ВЕ, когда о жассе еще никто не знал, и сделать квест в журнале считалось круто, с тех пор многое изменилось => я многого не знаю) |
|
19.01.2009, 15:24
|
|
adic3x
offline
Опыт:
108,439Активность: |
Цитата:
ну как вариант посмотреть, карта путей рисуется с точностью до 32, т.е. 128*128 это 4*4 по 32*32, т.е. 16 проверок, но карта путей же не дает инфы о деструбах/юнитах ? ADOLF добавил: + хз, будет ли 16 проверок быстрее мова юнита... имхо мб и будет быстрее... |
|
|
19.01.2009, 15:30
|
