Лекция #12. AI. Подходы, тимплей, взаимодействие с миром, оптимизации для большого мира. [Лектор - roman_p] (4 стр)
Автор: Арсений Капулкин
[01:15] <_ShaMan_> а какие алгоритмы применяются для поиска пути в шутерах?
[01:15] <_ShaMan_> со стратегиями понятно. Обычно A*
[01:15] <roman_p> лучше всего - A*
[01:15] <roman_p> есть вариации на тему - левой и правой руки и т.д.
[01:16] <_ShaMan_> или тот же A* но с навигации по опорным точкам?
[01:16] <roman_p> A* - может быть: 1-по клеткам. 2-по нодам. 3-по фаскам.
[01:16] <_ShaMan_> waypoints
[01:16] <roman_p> 2- и есть waypoints ;)
[01:16] <_ShaMan_> эээ. Что значит по "фаскам"?
[01:16] <roman_p> можно сразу по фаскам ходить. navmesh называется.
[01:17] <roman_p> 3 фасок - тройная связанность.
[01:17] <_ShaMan_> а он как по скорости?
[01:17] <roman_p> у waypoint - любая связанность.
[01:17] <roman_p> у клеток - 4 или 8.
[01:18] <roman_p> все это быстрые алгоритмы.
[01:18] <kas> чисто а* видимо нигде не юзаеца
[01:18] <roman_p> в магии крови - двухнаправленная A*
[01:18] <kas> он медленный
[01:18] <roman_p> kas - перепеши.
[01:19] <roman_p> kas - а также покажи что он тормозит. строчками из профайлера.
[01:19] <_ShaMan_> а в играх типа Квака или УТ, я так понимаю при постройке карты сразу просчитываются ноды?
[01:19] <_ShaMan_> не будут же они это в реалтайме :)
[01:20] <roman_p> SM: да. есть такая утилита aas. она строит .aas файл. в q3 там waypoints храняться.
[01:20] <kas> вот, ты поищи путь с одного конца карты на другой
[01:20] <kas> свёсдочкой
[01:20] <kas> чистой
[01:20] <kas> получишь пару милисекунд на перса и задумаешься
[01:20] <roman_p> kas: карта 512x512, путь примерно в 640 клеток, A*, на p4-2.0 ~10msec.
[01:20] <kas> 10 милисекунд ето уже 100 фпс
[01:21] <kas> а ещё графика
[01:21] <kas> а ещё дофига всего
[01:21] <kas> 10 мск один перс?
[01:21] <roman_p> kas : 1 вызов. 1 перс.
[01:21] <roman_p> kas - просто нефига кучу персов пускать на длинные расстояния.
[01:21] <kas> может, ваще запретить ходить? :)
[01:21] <kas> нефик пасфайндер напрягать.
[01:21] <roman_p> kas - можно сделать pathfinder LOD. но до него руки не доходили ;)
[01:22] <kas> у меня было 70 перцев, карта 512х512
[01:22] <kas> фпс просаживался на 1
[01:22] <kas> с 67 до 66
[01:22] <roman_p> все 70 ходили на 640 клеток постоянно меняя маршрут? ;)
[01:22] <kas> ходили на полкарты
[01:23] <roman_p> постоянно меняя конечную точку назначения?
[01:23] <roman_p> и что за алгоритм был то?
[01:23] <kas> та хоть как, пасфайндер каждый кадр искал
[01:23] <kas> звёсдочка, но модифицированная
[01:23] <kas> сильно модифицированная
[01:24] <kas> Near Optimal Hierarchical Pathfinding
[01:24] <roman_p> lod на карту непроходимости?
[01:24] <kas> не совсем
[01:24] <roman_p> ну, перепеши в МК на нее ;)
[01:24] <roman_p> mipmap на карте непроходимости.
[01:25] <kas> не мипмапы
[01:25] <kas> грид регионов
[01:25] <kas> внутри которых звёсдочка
[01:25] <kas> а регионы маленькие
[01:25] <kas> на которых звёсдочка реактивна
[01:25] <roman_p> ага. 2-х уровневый mipmap ;)
[01:26] <kas> единственная трудность - граф перестраивать
[01:26] <roman_p> можно сделать N-уровневый mipmap - будет еще реактивнее.
[01:26] <kas> не, реактивнее уже не будет
[01:26] <kas> оно компенсируется сложностью
[01:26] <kas> перестроения графа
[01:26] <roman_p> представь - что у тебя регион - 2 клетки.
[01:26] <kas> представь сколько регионов будет
[01:26] <roman_p> путь ты ищешь - только на карте 2 на 2.
[01:27] <roman_p> куча регионов.
[01:27] <kas> и насколько неоптимальным
[01:27] <kas> будет путь
[01:27] <roman_p> и никакой перестройки графа.
[01:27] <roman_p> тебе быстро или оптимально? ;))
[01:27] <kas> дайте две!
[01:27] <roman_p> mipmap pathfinder - вообще не будет ресурсов жрать ;)
[01:28] <kas> про поиск пути надо земедельца мучить :)
[01:29] <kas> на самом деле там же не только тупой поиск, тамже критериев много всяких исчо
[01:29] <kas> например в стратежки - искать путь для толстых юнитов
[01:29] <kas> искать для отрядов
[01:29] <roman_p> МК делает поиск пути исходя из толщины тела.
[01:30] <roman_p> всего 4 набора толщины тела есть.
[01:33] <roman_p> вообще - правильный pathfinder - это роскошь ;)
[01:33] <roman_p> вот, в gta:sa его нет. и что? ;)
[01:33] <roman_p> там все умеют ходит либо по прямой, либо по скриптовому маршруту ;)
[01:33] <kas> а нафега он там? :)
[01:34] <roman_p> а нафига в МК - в одном из скриптов, 3 чувака отправляются на 1200 клеток сразу в одну и туже точку? ;))
[01:37] <roman_p> для RPG - вполне хватит pathfinder-а на 64 метра максимум. вполне.
[01:40] <_TwilighT_> в Baldur's Gate суперотстойный pathfinder например
[01:40] <kas> да, говорят он весде такой :)
[01:40] <kas> на самом деле
[01:40] <kas> в стратежках зажигает более менее, а рпг все забивают
[01:42] <roman_p> в стратегиях - нет такой плотной непроходимости.
[01:42] <kas> ну, нискажи
[01:42] <Rageous> в стратегиях зато тучи юнитов бывают
[01:42] <kas> дада
[01:42] <Rageous> у нас это одна из самых больших проблем в варфаре
[01:43] <roman_p> если ты кликаешь в MK - в перс там не идет, не идет через узкий проход - значит там на самом деле нельзя пройти. такие кол. меши.
[01:43] <roman_p> т.е. как с таким бороться с програмной точки зрения - я не знаю ;)
[01:43] <roman_p> можно выдрачивать - кол. меши, делать их разумными, а не огромными и больше визуальных. но дизайнеры на это забили ;)
[01:47] <_ShaMan_> про взаимодействие с миром вроде как не было
[01:47] <_ShaMan_> только в вопросах
[01:52] <roman_p> могу рассказать про взаимодействие с миром.
[01:52] <roman_p> хотя я это уже рассказывал.
[01:52] <_ShaMan_> про стол?
[01:52] <roman_p> взаимодействие с миром - это teamplay и perception.
[01:46] <_TwilighT_> типа про оптимизация для большого мира будет или нет? :)
[01:53] <roman_p> а оптимизация - она вообще для всего одна и та же.
[01:53] <roman_p> profile, profile, profile.
[01:53] <roman_p> batch, batch, batch.
[01:53] <roman_p> lod, lod, lod.
[01:54] <roman_p> а потом уже - оптимизация _рабочего_ алгоритма.
[01:54] <roman_p> ну и в самом конце - asm и настройки intel compiler-а ;)
[02:06] <DobroKOT> вот у меня была конретная задача по AI, я её не успел сделать до ухода...
[02:06] <DobroKOT> Был такой зверь - Гиппозавр.
[02:07] <DobroKOT> collision form которого был, грубо говоря, параллепипед.
[02:08] <DobroKOT> он прижимался боком к стенке... И больше не мог ходить. Так как при любой попытке поворота физика его останавливала.
[02:08] <DobroKOT> И как такое детектить в тот момент мне было не очень понятно.
[02:08] <DobroKOT> Да пофиг на чём... проблема была в Гиппозавре, а не в скриптовом языке.
[02:09] <roman_p> D: если прижимается NPC к стенке - он у вас не поворачивался?
[02:09] <DobroKOT> да.
[02:09] <roman_p> D: imho, это бага colsolver-а.
[02:09] <DobroKOT> не, это не бага. К сожалению, это его правильная работа.
[02:10] <DobroKOT> просто не очень понятно, когда надо стрейфится и куда, если вокруг тебя polygon soup.
[02:10] <roman_p> D: при таком colsolver-а NPC надо сделать круглыми ;)
[02:11] <DobroKOT> roman_p, косолвер реальный.
[02:11] <DobroKOT> ну, не polygon суп, а collision forms суп, конечно...
[02:11] <roman_p> D: проблема в colsolver-е. надо его учить поворачивать прямоугольник рядом с линией.
5 февраля 2006