Как можно оптимизировать этот код с 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

464

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

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

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

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

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

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

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

Ну кстати да. Посмотрел. Все фреймы обрабатываются одновременно. периодиком в 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 3

Показать

Vlod 2 года

Показать

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

nazarpunk 2 года · Answer 4

Показать

nazarpunk 2 года

Показать

Vlod:

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

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

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

Показать

Vlod 2 года
Ред. Vlod

Показать

nazarpunk:

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

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

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

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

nazarpunk 2 года · Answer 7

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

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

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

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

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

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

Еще кучу ифов в 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 9

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 10

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 понимает), но не суть, на обычном джасс +- тоже самое можно сделать.

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

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

а как передать переменные внутрь ForGroup? а потом еще и вернуть результат? она же вызывается с takes nothing returns nothing
для этого создавать новый вопрос с тестовым мини кодом?
делать на глобалках? или на той же ht? а они разве не перезапишутся, если несколько ForGroup будут выполняться в разных тредах и перезаписывать результат в одну свою глобалку на true/false условно хаотично
или если ты в 3 глобалки (или в 3 значения в ht) записываешь входящие i , x , y - то они тоже будут прыгать при вызове MushroomMoving_CollisionCheck\ForGroup несколько раз т.к. идёт перезапись входящих общих переменных i x y при каждом их вызове

Открыть код

function UnitIndex takes unit u returns integer
	local integer i=1
	loop
		exitwhen i>PLAYER_MAXINUM+Stage_BoxsCount
		if u==OrangeMushroom[i] then
			set u=null
			return i
		endif
		set i=i+1
	endloop
	set u=null
	return 0
endfunction

function MushroomMoving_CollisionCheck_ForGroup takes nothing returns nothing
	local unit u=null
	local integer j=0
	local real otherx
	local real othery
	set u = GetEnumUnit()
	if u!=OrangeMushroom[i] then
		set j=UnitIndex(u)
		if (GetPlayerSlotState(GetOwningPlayer(OrangeMushroom[j]))==PLAYER_SLOT_STATE_PLAYING or j>PLAYER_MAXINUM) and LevelClearState[j]==false then
			if MB_Frame_On==1 then
				set MB_CollisionY = MB_CollisionY+1
			endif
			set otherx=GetUnitX(OrangeMushroom[j])
			set othery=GetUnitY(OrangeMushroom[j])
			if ContainsCoords(otherx-64,othery-64,otherx+64,othery+64,x,y)==true then
				if PropellyCondition==true then
					if GetUnitTypeId(OrangeMushroom[j])!='orai' then
						set u=null
						set Frame_MainPlayerY=j
						return false
					endif
				else
					set u=null
					set Frame_MainPlayerY=j
					return false
				endif
			endif
		endif
	endif
	set u=null
	return true
endfunction

function MushroomMoving_CollisionCheck takes integer i,real x,real y returns boolean
	local group G = CreateGroup()
	call GroupEnumUnitsInRange(G, x,y, 128, null)
	call ForGroup(G,function MushroomMoving_CollisionCheck_ForGroup)
	call DestroyGroup(G)
	set G=null
endfunction

Jack-of-shadow: попробуй что то типо того:

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

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

Вход

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

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

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

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

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