Как можно оптимизировать этот код с 2D коллизиями?

Question

Как можно оптимизировать этот код с 2D коллизиями?

Добавлен host_pi

есть одна 2D карта (по зеленой кнопке)

но код для просчёта коллизий может обработать только 11 юнитов
(если играть всемером - то получится, что можно добавить только 4 доп.юнита на карту)
если сделать 12 или 50 юнитов - то варик просто захлёбывается
(в карте есть счетчик обработки коллизий - максимально 80000 операций в секунду)
есть желающие поковыряться в коде и улучшить его, чтобы он смог обрабатывать 50 юнитов?
коллизии - это столкновение. по X это толкание соседних юнитов вправо влево, по Y это носить на голове или стоять сверху на юните

код карты тут:
EN controlc.com/b12ac4e8
RU controlc.com/dcfc0814

цепочка функций по просчёту коллизий:

main - начало карты
Frame__init - инициализация кадра
Frame__Main - просчет одного кадра (частота 0.02)
Frame__PlayersGroup - просчет группы юнитов
Frame__SquaresMoving - движение юнитов
Frame__MovingY [b==false] - движение по Y
if MushroomMoving_RectCondition "UpWidthOM" + "DownWidthOM"  - сравнение ректов
MushroomMoving_CollisionCheck - проверка на коллизии
set otherx=GetUnitX(OrangeMushroom[j]) + set othery=GetUnitY(OrangeMushroom[j]) - считывание координат

графики:

скриншот карты:

Скачать - 11 МБ 42

1

468

Jack-of-shadow 2 года · Answer 1

Показать

Jack-of-shadow 2 года

Показать

nazarpunk, Я просто не видел ещё весь код и предположил что MushroomMoving_CollisionCheck вызывается единовременно (через луп или группу) для каждого юнита на карте. В таком случае можно было бы разбить это со сдвигом во времени.

host_pi 2 года Ред. host_pi · Answer 2

Jack-of-shadow: Как часто вызывается MushroomMoving_CollisionCheck?

счетчика на колво вызовов самой функции нету
но есть счетчик по вызову GetUnitX() GetUnitY() - это цикл внутри MushroomMoving_CollisionCheck
на графиках это CPS
средние цифры - десятки тысяч раз в 1 сек

и счётчик отображается внутри карты тоже через -pro

Jack-of-shadow: В таком случае можно было бы разбить это со сдвигом во времени.

в движке полностью всё с нуля написано, и "время" в том числе
а проблема во вложенных циклах с лупом

Jack-of-shadow 2 года Ред. Jack-of-shadow · Answer 3

Ну кстати да. Посмотрел. Все фреймы обрабатываются одновременно. периодиком в 0.02 сек.
Соответственно все вычисления происходят в одном тике.

вот тут

function Frame__init takes nothing returns nothing
	local trigger t=CreateTrigger()
	call TriggerRegisterTimerEvent(t,0.02,true)

По идее для начала можно разбить Frame__PlayersGroup на 2 части с периодом в 0.01. Это уже должно в два раза облегчить.

например

в Frame__PlayersGroup перебираешь 5 игроков в одном тике, и 5 в следующем.

Соответственно можно при желании еще реже обрабатывать, разбить уже на 5 частей (таймер будет 0.01, а между кадрами будет 0.05).

Я в HoV так аишку оптимизнул. У меня был довольно тяжелый аи с периодом в 2 сек. В итоге сделал таймер 0.01 и теперь от 1 до 200 юнитов обрабатываются с одинаковой скоростью, ибо за один кадр просчитывается только 1 юнит.

У нас в статьях почему то любят пугать что малый период это зло. На деле не важно какой период хоть 0.01 хоть 10 сек. важно сколько действий в нем происходит.
Более того в теории если в карте несколько тяжелых периодиков, то лучше инициализировать их так, что бы они не совпадали по моменту выполнения.

Например

триггер A с периодом 3 сек., триггер B с периодом в 3 сек., и триггер C с периодом 6 сек.
В итоге момент их выполнения совпадает.
Что бы этого избежать лучше инициализировать их не одноверменно, а со сдвигом в сотую.
Я могу быть не прав, тк не проверял тестами. Но по логике получается именно так.

Vlod 2 года · Answer 4

Показать

Vlod 2 года

Показать

nazarpunk, все таки оказывается коллизия это актуальный вопрос, вот люди даже на 10 объектах спотыкаются

nazarpunk 2 года · Answer 5

Показать

nazarpunk 2 года

Показать

Vlod:

все таки оказывается коллизия это актуальный вопрос, вот люди даже на 10 объектах спотыкаются

Не в колизии дело. Здесь самый примитивный случай - прямоугольники ориентированые по осям. Проблема в оптимизации и сравнени всех со всеми. А это квадратичный рост сложности, что не есть хорошо.

Vlod 2 года Ред. Vlod · Answer 6

Показать

Vlod 2 года
Ред. Vlod

Показать

nazarpunk:

и сравнени всех со всеми

Вот вот, это задел на деревья квадрантов и сетки
Смекаешь

goodlyhero 2 года Ред. goodlyhero · Answer 7

Впринципе, период тут можно сильно повысить с 0.02. В этом коде же у вас только просчет коллизий.
Даже если вы будете проверять коллизии с частотой 0.1, то это будет не слишком заметно с учетом ваших скоростей. А производительность поднимется в пять раз. Ну будут у вас грибы чучуть пружинить, может быть, не беда.
Движение-то можно считать с той же частотой 0.02, раз уж оно у вас не вызывает лагов. Так и движение не будет дерганым.

nazarpunk 2 года · Answer 8

Глянул на код. Это просто шикарно. На каждого юнита вызывается UnitIndex. Тоесть лишний цикл на количество игроков. Можно просто каждому грибу записать его индекс через SetUnitUserData. Будет дешевле.

Очищать глобальную группу G дешевле, чем дрочить создание/удаление локалки.

Удаление из группы происходит за O(n), поэтому лучше перебирать группы не через удаление юнита, а через ForGroup. Она к тому же создаёт псевдопоток, что позволяет обойти оплимит.

Этой проверки я так и не понял.

GetUnitTypeId(OrangeMushroom[i])!='orai'

Jack-of-shadow 2 года Ред. Jack-of-shadow · Answer 9

Еще кучу ифов в SetUnitMoveAnimation (к которому Frame__Main каждые 0.02 сек по тыще раз обращается), можно через хеш урезать до одной строки.

cjass

define SaveAnimation (tp,aniName,index) = {SaveInteger(hash,AnimationKey,StringHash(I2S(tp)+aniName),index)}
define LoadAnimation (tp,aniName) = {LoadInteger(hash,AnimationKey,StringHash(I2S(tp)+aniName))}
void AnimationIni(){
SaveAnimation ('uobs',"Walk First",0)
SaveAnimation ('uobs',"Walk Second",1)
SaveAnimation ('ufro',"Walk First",6)
SaveAnimation ('uobs',"Walk Second",7)
//..и все остальные
}
define SetUnitMoveAnimation (u,aniName)={SetUnitAnimationByIndex(u,LoadAnimation(GetUnitTypeId(u)))}

goodlyhero, тут не частоту надо понижать (от этого фриз не исчезнет), а именно разбивать обработку юнитов на разное время. Таймер 0.01 с начало обрабатывает 1-ую часть всех юнитов, потом 2-ую, 3 итд, потом снова первую. Таким образом, если мы разделим всех юнитов например на 5 групп, то то все юниты будут обрабатываться с частотой 0.05 сек.

В Frame__Main/BossMoving тоже что то жеское..

host_pi 2 года Ред. host_pi · Answer 10

goodlyhero: Впринципе, период тут можно сильно повысить с 0.02. Даже если вы будете проверять коллизии с частотой 0.1, производительность поднимется в пять раз.

я уже пробовал менять это значение - ничего не меняется по нагрузке и по фпс
(да и любой из вас его может изменить за пол минуты и чекнуть результат - www.epicwar.com/maps/332635 вот новая версия карты 1.4 с добавленным радиусным ускорением )
это чисто лимит варкрафта на колво вложенных циклов и операций в одном стеке
единственное что из похожего помогает уменьшить тормоза и поднять фпс - это ириновский !actioninterval

nazarpunk: На каждого юнита вызывается UnitIndex. Тоесть лишний цикл на количество игроков. Можно просто каждому грибу записать его индекс через SetUnitUserData. Будет дешевле.
Очищать глобальную группу G дешевле, чем дрочить создание/удаление локалки.

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

nazarpunk: Удаление из группы происходит за O(n), поэтому лучше перебирать группы не через удаление юнита, а через ForGroup. Она к тому же создаёт псевдопоток, что позволяет обойти оплимит.

о, ради такого уже стоит вернуться к коду и протестировать, возможно это и будет тем решением о котором я и писал с самого начала - не изменяя логики кода пустить отдельным потоком просчет коллизий

nazarpunk: Этой проверки я так и не понял.
GetUnitTypeId(OrangeMushroom[i])!='orai'

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

Jack-of-shadow: можно через хеш урезать до одной строки. cjass

это всё хорошо, только war3 не понимает cjass, можно хоть на си шарпе, питоне или джаве писать в пол строки и козырять этим - только компилятор все равно переведёт в обычный многострочный jass, это разве не очевидно?

Jack-of-shadow: В Frame__Main/BossMoving тоже что то жеское

ничего там нету жесткого, там сразу выход из функции по первому условию - if FinalStage==true and BlackBoss !=null

это всё мелочи, обычный код не нагружает варик в щщщи
то есть какой смысл оптимизировать чужой код (который в новых версиях карты вообще обфусцирован) ради наносекунд или уменьшения в каком-то месте с 5 строк до 3, когда уже выявлена реальная причина тормозов - это количество коробок и их обсчёт коллизий
нагружают именно коллизии и как уже выше было сказано - вложенный квадратичный (а теперь уже радиусный) цикл по ним

Jack-of-shadow 2 года Ред. Jack-of-shadow · Answer 11

host_pi,

я уже пробовал менять это значение - ничего не меняется по нагрузке и по фпс

попробуй что то типо того:

globals
 integer playersMax                = 10//кол-во игроков
 integer playersPerFrameProcessed  = 2 //сколько игроков будет обработано за 0.01 сек
 integer playersCurrectFrameOffset = 1 //следующий игрок для обработки коллизий
englobals 

function Frame__PlayersGroup takes nothing returns nothing
	local integer i
		 
		if playersCurrectFrameOffset > PlayersGroupMax {playersCurrectFrameOffset = 0} 
		set i = playersCurrectFrameOffset
		
		loop
	     set playersCurrectFrameOffset = playersCurrectFrameOffset + 1
		 exitwhen i > playersCurrectFrameOffset+playersPerFrameProcessed
	      //тут обрабатываешь игрока

		 set i = i + 1
	    endloop	
        set playersCurrectFrameOffset = i	
endfunction 		


function Frame__PlayersGroupIni takes nothing returns nothing
	local trigger t=CreateTrigger()
	call TriggerRegisterTimerEvent(t,0.01,true)
	TriggerAddAction(t,function Frame__PlayersGroup)
endfunction

я может гденить накосячил но смысл думаю понятен

это всё хорошо, только war3 не понимает cjass

Вобщето с JNGP понимает), но не суть, на обычном джасс +- тоже самое можно сделать.

Как можно оптимизировать этот код с 2D коллизиями?

Вход

Регистрация на сайте

Переместить ресурс

Создание задания

Выбор проекта для репоста

Управление интересами