Проход сквозь стены, коллизии, видимость целей, pathfinding, wmo

[DeusModus]

Внимание!
Орфография, пунктуация и терминология не сохранены! Я взял на себя смелость употреблять такие понятия как tile, pathfinding, waypoint в их первозданно-английском варианте, а не жутком транслите. Надеюсь, авторы не забросают за это помидорами.



mentat:
Неплохо бы со временем начать работать с WMO.
На WoWDev.org проводилось исследование этого формата, но сейчас это проект временно (или постоянно) сдох. Однако, удалось вырвать из кэша Google информацию с него по используемым форматам.

SLOM:
Сейчас в любом движке игры есть такое понятие как твердые тела.
Обьясню на примере Cosmos Creator который является движком 3d миров и игр на его основе:

• Создаем плоскость и создаем над ней кубик.
• Созаем гравитацию и нажимаем включение просчета, кубик тупо проходит сквозь плоскость.
• Так же поступают наши боты.
• Выделяем плоскость включам опцию земля.
• Выделяем кубик вкл опцию твердое тело опред его как кубик(можно еще как сфера или меш но сфера он будет неправильно себя вести а меш напряжет процес).
• Включаем и кубик падает на плоскость и ост на ней !

Так работает на официальном сервере.
Чтобы кубик обходил препятствие можно делать опережение расчета, то есть траектория падения (движение просчитывается далеко вперед ) и если есть препятствии- ищется кротчайший обход.
Тут есть проблемы. Как определить где проходимо а где нет ? И не будет ли это нагружать сервер частыми проверками на то есть впереди препятствие?
Гораздо легче и быстрей определить это по готовым точкам.

Deamon:
А если так. Понатыкать в вершины полигонов wmo waypoint`ов . На каждый такой waypoint вешать маршрут, типа куда из этой точки может попасть моб(в какой из соседних waypoints). Решается проблема прохода мобов через стены. Сразу же решается проблема проваливающихся мобов. Потому что z координату можно будет считать как разность z координат waypoint'ов. Пример такого провала можно наблюдать в Stormwind, при выходе из города. Там pet чуть-чуть уходит под гравий. Вариант получается и вашим и нашим.

Для упрощения можно брать не каждый полигон, а уменьшить полигонную сетку вдвое. Может что-то даст.

Наверняка есть проблемы с определением вертикальной стены и горизонтального пола. Как вариант можно модифицировать какой-нить viewer wmo файлов и в нем руками удалять неверно взятые полигоны, которые на самом деле относятся к стене или потолку

Правда с таким подходом остается непонятным, каким образом сервер выдает клиенту, что персонаж не видит напрямую врага, и поэтому не может его атаковать.

SLOM:
Отличный ресурс, сегодня нашел там _http://xgm.ru/forum/forumdisplay.php?f=47
Программа позволяет редактировать файлы m2 (модели в WoW и их анимации).
И ваш любимый wmo
Цитата:

.:munche:. :
Нету в wmo waypoint`ов, мы(WoWcore) тоже долго ковыряли данные по m2 и wmo.
Обсчет этих данных будет дико убивать проц - 120%
Вот количество m2 которые нужно обсчитывать - те с которыми происходят коллизии:
73383 M2 на карте 0
100433 M2 на карте 1
Это без учёта, что в wmo тоже содержатся m2 объекты
Я уже молчу по instance которые целиком состоят из wmo... Здесь реально только обсчитывать m2 по сильно упрощенной модели и описать поверхности wmo системой waypoint`ов

SABROG:
Сколько ячеек на всей карте ? Сколько grid`ов в нее может уместиться ?

Не достаточно просто сделать waypoint'ы, монстры прекрасно определяют видимость целы. Т.е. ты не сможешь попасть spell`ом по монстру, если он за угол дома встанет. Да и потом все это упрощается. У нас ведь есть . Значит нам достаточно просчитывать только те M2 которые находятся в grid`е. Но и это ведь не все. Зачем просчитывать M2 с которыми не предполагается взаимодействие ? У каждого игрока и монстра есть область видимости. А также у нас есть траектория движения монстра, т.е. координата цели. Проведя мысленный луч к цели мы получить все координаты от монстра до игрока. Их будет не много, т.к. есть расстояние видимости, когда монстр должен будет оставить преследование. Значит проведя луч к цели мы ищем по каждой этой координате объект, который должен находится в этом месте. Список будет небольшим, т.к. у нас уже заранее будут загружены только те объекты, которые относятся к текущему и последующему grid`у, если идет "перевал" через границу. Остается только с определенным промежутком проводить подобную операцию, чтобы корректировать направление монстра. Т.е. если текущий заданный путь до цели короче, чем просчитали только что, то ничего не делать, если уже длиннее, то пересчитываем новый путь.

.:munche:. :
Я не знаю размеры ячеек на MaNGOS. Размеры в клиенте соответственно:
64х64 tile`ов максимально.
Сколько их реально прописано в соответствующем файле.
Размер tile 533.3(3).

Еще естественное замечание:
m2 на карте может стоять так, что будет находится на 4-х chunk`ах сразу - т.е. на границе, соответственно привязку к grid`ам,сеткам и прочим квадратам сделать без разбиения m2 на куски не получится... Либо делать для хранения такой информации простой массив с привязкой только к tile.

Спасибо Lelox за материалы.

продолжение следует...

[MaxXx2021]

вроде же идут работы над MoveMaps, на getmangos.com?

[DeusModus]

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

Это всё? Как жаль ( Надеюсь авторы вернутся и продолжат дискуссию, было очень интересно Да и за это время наверняка многое уже изменилось

[DeusModus]

Сообщение от GriffonHeart

Это всё? Как жаль ( Надеюсь авторы вернутся и продолжат дискуссию, было очень интересно Да и за это время наверняка многое уже изменилось

У меня все страницы. Просто я не копирастю, а обрабатываю.
Многое изменилось, но то что там было всё равно интересно.

[MaxXx2021]

Сообщение от DeusModus

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

Я не такой задр чтоб перед сном читать темы. Тем более выяснили же уже что в WMO формате уже есть все для реализации.

[DeusModus]

Сообщение от MaxXx2021

Я не такой задр чтоб перед сном читать темы. Тем более выяснили же уже что в WMO формате уже есть все для реализации.

Терминология у вас гадкая.

[Deamon]

Последние 2 года был только флуд. Дело двигалось вперед, когда andstan поддерживал VMap.

Кстати, чисто по секрету, VMap сейчас для больших городов делает девятикратную работу по просчету видимости. А все почему?

Имеем сетку
-----------
| 1 | 2 | 3 |
-----------
| 4 | 5 | 6 |
-----------
| 7 | 8 | 9 |
-----------

Формат карт у blizz'ов устроен таким образом, что если в ADT файле номер 5 имеется объект достаточно большой величины, то ссылка на него вместе с координатами будет хранится и в прилегающих к нему ADT файлах. Устраняется это дело легко. В MODF чанке есть UniqueID, устанавливающее номер инстанции WMO объекта. Тоже самое применимо и к M2 и MDDF чанку. Это так, чисто на заметку.

[user456]

Ну если Мангос уже сделал реализацию - так и говорить не о чем. А так я делал просчеты вплоть до z для каждой торчащей палки или z на каждой точке лежащего дерева или земли (для wmo тоже, даже мобов пускал по пещере бродить по этим расчетам, но тут не очень гладко выходило) и попадания в баунд радиусы каждой сосны. При одном плеере на рилме и куче бродящих рядом мобов съедало 5% ЦПУ, что не есть хорошо.
Посмотрел что Близзы делают - у них предпросчитана сетка. Если чар далеко - моб бежит по сетке и уже с какого-то радиуса по прямой. В яслях дворфов-гномов ясно все видно: тролли не забегают в свои шатры если там чар, на входе в пещеру тролль преодолевает вмо-терран по одной из 2-х возможных точек и т.п.
Считается все, кроме вмо, довольно просто. Правда код если и спрашивали то вовкоры, и то похоже мало поняли в том что я написал (ну малость было оптимизировано) Если надо - могу закинуть "as is"

[Konctantin]

Выкладывайте, интересно посмотреть, это ж все таки обучающий форум.

[user456]

Вводная: имеем карту типа Azeroth, где позиция xy = 0:0 посредине. В итоге координаты от -HALF_MAP до +HALF_MAP. 64х64 тайла которые в wdt карты помечены как отсутствующие или в наличии. В тайле 16х16 чанков, каждый делится на сабчанки, где собственно уже есть реальные координаты. Вкратце константы.

     
     TILE_SIZE            = 533.33333;
     TILES_COUNT          = 64;
     MAX_TILE             = 63;
     HALF_MAP             = 32*TILE_SIZE;
     INSTANCE_QUARTER_MAP = 8*TILE_SIZE;
     CHUNK_COUNT          = 16;
     TILE_CHUNK_COUNT     = 256;
     MAX_CHUNK            = 255;
     CHUNK_SIZE           = TILE_SIZE / CHUNK_COUNT;
     DCHUNK_SIZE          = CHUNK_SIZE*2;
     SUB_CHUNK_FULL_COUNT = 17;
     SUB_CHUNK_LINE_COUNT = 8;
     SUB_CHUNK_POINT_COUNT = 9;
     SUB_CHUNK_SIZE  = CHUNK_SIZE / SUB_CHUNK_LINE_COUNT;
     HALF_SUB_CHUNK_SIZE  = SUB_CHUNK_SIZE/2;

Сначала находим в каком тайле и чанке x и y и выходим если координаты хзгде. Абсолютная позиция от края карты.

  absX := HALF_MAP - objPos.pos.x;absY := HALF_MAP - objPos.pos.y;
  tileX := trunc(absX / TILE_SIZE);diffX := absX - tileX * TILE_SIZE;
  tileY := trunc(absY / TILE_SIZE);diffY := absY - tileY * TILE_SIZE;

  chunkX := trunc(diffX / CHUNK_SIZE);chunkDiffX := diffX - chunkX * CHUNK_SIZE;
  chunkY := trunc(diffY / CHUNK_SIZE);chunkDiffY := diffY - chunkY * CHUNK_SIZE;

  if OrdinalMapsArray[objPos.mapId, tileY, tileX] = nil then
    exit;

Далее смотрим не попали ли в воду, м2, вмо и т.п., в конце-концов определились что все-таки на карте. Имеем в каждом сабчанке 9х9 точек, что дает нам кучу квадратов. Благодаря второй сетке 8х8 каждый квадрат получает точку в центре и мы имеем уже 4 полигона, что ближе к тригонометрии. Делением получаем тангенс угла, по которому сразу понятно в какой из 4-х полигонов попали. А там уже дело техники: точка сопряжения прямой с полигоном, откуда и имеем Z.

  { chunk }
  tan1 := subChunkDiffY / subChunkDiffX;
  tan2 := subChunkDiffY / (SUB_CHUNK_SIZE - subChunkDiffX);


  v3.x := HALF_SUB_CHUNK_SIZE;  v3.y := HALF_SUB_CHUNK_SIZE;
  v3.z := lpChunkMap.Z[subChunkX + subChunkY * SUB_CHUNK_FULL_COUNT + SUB_CHUNK_POINT_COUNT];
  p1.x := subChunkDiffY;     p1.y := subChunkDiffX;      p1.z := 0;
  p2.x := subChunkDiffY;     p2.y := subChunkDiffX;      p2.z := 100;
  if tan2 >= 1 then begin
    if tan1 >= 1 then begin //right
      v1.x := SUB_CHUNK_SIZE;    v1.y := 0;
      v2.x := SUB_CHUNK_SIZE;    v2.y := SUB_CHUNK_SIZE;
      v1.z := lpChunkMap.Z[(subChunkX + 1) + subChunkY * SUB_CHUNK_FULL_COUNT];
      v2.z := lpChunkMap.Z[(subChunkX + 1) + (subChunkY + 1) * SUB_CHUNK_FULL_COUNT];
      norm := Normal([v1, v2, v3]);
      mapPositionResult.tilt := abs(Normalize(norm).z);
      dV := IntersectionPoint(p1, p2, norm, PlaneDistance(norm, v3));
      result := baseZ + dV.z;
    end
    else begin //bottom
      v1.x := SUB_CHUNK_SIZE;    v1.y := SUB_CHUNK_SIZE;
      v2.x := 0;                 v2.y := SUB_CHUNK_SIZE;
      v1.z := lpChunkMap.Z[(subChunkX + 1) + (subChunkY + 1) * SUB_CHUNK_FULL_COUNT];
      v2.z := lpChunkMap.Z[subChunkX + (subChunkY + 1) * SUB_CHUNK_FULL_COUNT];
      norm := Normal([v1, v2, v3]);
      mapPositionResult.tilt := abs(Normalize(norm).z);
      dV := IntersectionPoint(p1, p2, norm, PlaneDistance(norm, v3));
      result := baseZ + dV.z;
    end;
  end
  else
  if tan1 >= 1 then begin //top
    v1.x := 0;                 v1.y := 0;
    v2.x := SUB_CHUNK_SIZE;    v2.y := 0;
    v1.z := lpChunkMap.Z[subChunkX + subChunkY * SUB_CHUNK_FULL_COUNT];
    v2.z := lpChunkMap.Z[(subChunkX + 1) + subChunkY * SUB_CHUNK_FULL_COUNT];
    norm := Normal([v1, v2, v3]);
    mapPositionResult.tilt := abs(Normalize(norm).z);
    dV := IntersectionPoint(p1, p2, norm, PlaneDistance(norm, v1));
    result := baseZ + dV.z;
  end
  else begin //left
    v1.x := 0;                 v1.y := SUB_CHUNK_SIZE;
    v2.x := 0;                 v2.y := 0;
    v1.z := lpChunkMap.Z[subChunkX + (subChunkY + 1) * SUB_CHUNK_FULL_COUNT];
    v2.z := lpChunkMap.Z[subChunkX + subChunkY * SUB_CHUNK_FULL_COUNT];
    norm := Normal([v1, v2, v3]);
    mapPositionResult.tilt := abs(Normalize(norm).z);
    dV := IntersectionPoint(p1, p2, norm, PlaneDistance(norm, v2));
    result := baseZ + dV.z;
  end

Код собственно не трогал со времен 1.хх. Не думаю что сильно поменялось. (Edit: эта часть не поменялась и z считается быстро, если не делать для всех мобов одновременно динамически вычисляя передвижения каждые 0.2 ярда как я когда-то делал)

Вов, у меня остались гдето еще твои исходники которые карты рисуют красивые.
Могу тебе переслать если надо

[user456]

Да есть они у меня
Вот сидел искал в своем мусорнике что чего делало (я ж забыл уже). А то что что-то делало переводил к wotlk данным. Штуки 3 вроде адаптировал (рисовалку м2, вмо и вмо на мапе). Можно выложить "as is", куда только?

Ромке скинь, он на сайте у нас выложит на аплоаде

[tempura]

А здесь в форум не лезет? Куда угодно выложи, я в архив форумный перекину.

[user456]

http://filebeam.com/efde5642179e7b6f50b40a96237d22f7

2 примера с сорсами (для особо ленивых еще 2 экзешника и StormLib.dll)

wmo: рисует скелет wmo (откуда берутся пути к wmo типа "World\wmo\Azeroth\buildings\stranglethorn_bootyba y\bootybay" большущий секрет, "Total Commander" и WowMpq к примеру). Несколько путей к wmo для примера сидят в сорсе.

Mwmo_terrain_m2: рисует карту 3х3 тайла, на которой показаны баунды привязанных к ним m2 и скелеты wmo.

Папки с mpq определяются по ключу в реестре, так что какой клиент последним запускали - от того и возьмет.

PS: подкорректировал под WotLK, в остальном никаких умных доводок до ума за последние года 3.
Update: http://filebeam.com/84c3fdab81177a57a2692023fe36d917 добавлена обработка path3, lichking и expansion mpq.

Народ на счет столкновений.
Разве не проще сделать для каждого загружаемого в мир нпц свою сетку в которой он может перемещаться(полигонами) чем просчитывать столкновения каждый раз при его перемещении?

И еще вопрос не могли бы вы скинуть сцыль на описание формата wmo

Премного благодарен

[Konctantin]

Посмотрите тут: http://www.madx.dk/wowdev/wiki/index.php?title=WMO

[Chestarfild]

Разве не проще сделать для каждого загружаемого в мир нпц свою сетку в которой он может перемещаться(полигонами) чем просчитывать столкновения каждый раз при его перемещении?

Этож представьте какая сетка должна быть. Помоему вариант с столкновениями намного проще, и менее нагружает систему.