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

476

goodlyhero 2 года · Answer 1

Показать

goodlyhero 2 года

Показать

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

nazarpunk 2 года · Answer 2

Показать

nazarpunk 2 года

Показать

Что такое CPS?

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

Ковыряться в чужом коде после грязного жасса? Извольте.

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

goodlyhero: Попробуйте проверять на коллизию не всех юнитов на карте а только ближайших, например через поиск их в ректе.

а разве именно это не делает эта имеющаяся строка в коде?:

if ContainsCoords(otherx-64,othery-64,otherx+64,othery+64,x,y)==true then

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

nazarpunk: Что такое CPS?

счётчик количества отработки функции MushroomMoving_CollisionCheck
варик начинают загружать именно эти две строки:

set otherx=GetUnitX(OrangeMushroom[j])
set othery=GetUnitY(OrangeMushroom[j])

а счётчик считает сколько раз было обращение к этим строкам

nazarpunk 2 года · Answer 4

host_pi:

а разве именно это не делает эта имеющаяся строка в коде?

Нет, она уже сверяет координаты. Если сверять всех со всеми, то это будет O(n*n). А имелось в виду сверять только ближайшие координаты, чтоб хоть как-то понизить сложность.

host_pi:

варик начинают загружать именно эти две строки:

Зачем получать координаты из игры, если стандартная система перемещений отключена? Почему не хранить их в массиве не пользоваться только Set?

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

host_pi:

варик начинают загружать именно эти две строки:

Варкрафт загружает то, что у вас происходит полный перебор всех пар юнитов.

Стандартные варкрафтовские функции в этом плане работают намного умнее и количество юнитов почти не влияет на скорость. Соответственно функция GroupEnumUnitsInRect Вернет вам всех юнитов в квадрате за время. которое не зависит от количества юнитов на карте примерно никак. И это буде примерно бесконечно быстрее на значителньных количествах юнитов.

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

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

какой нативкой можно сверять ближайшие координаты у других юнитов рядом с заданным?

nazarpunk: Зачем получать координаты из игры, если стандартная система перемещений отключена? Почему не хранить их в массиве не пользоваться только Set?

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

goodlyhero: EnumUnitsInRect

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

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

Показать

goodlyhero 2 года
Ред. goodlyhero

Показать

host_pi:

какой нативкой можно сверять ближайшие координаты у других юнитов рядом с заданными?

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

nazarpunk 2 года · Answer 8

Показать

nazarpunk 2 года

Показать

goodlyhero:

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

Они разве не O(n)?

Daro 2 года Ред. Daro · Answer 9

Видел, что для большей производительности юзали через костыль трек события TriggerRegisterUnitInRange(trig, whichUnit, range, null), это по сути и есть готовая псевдоколлизия между юнитами, но для неё нужно накостыли эвент на выход из зоны и свойство на получения текущего статуса для проверки MushroomMoving_CollisionCheck, можно все коллизии у юнита сохранять в хеш по идишнику и динамический обновлять бд. Но это, как говориться, решение, которое нужно было реализовывать ещё при начале разработки

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

в карте у всех юнитов стоит abiList:
Aloc - москиты locust - что делает юнита некликабельным и не показывает тултип
Avul - неуязвимый invulnerable - что убирает показывание полоски жизни
GroupEnumUnitsInRect и GroupEnumUnitsInRange - не работает с москитами, т.е. юнита с такой абилкой - не добавляет в группу

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

после редактирования карты и убирания москитов с коробок такие результаты:

-bridge 12 в новом коде выдает 19200 коллизий против 79200 коллизий в прошлом
варик без пробуксовывания может обрабатывать максимум уже не -bridge 12 а -bridge 18 - 28600 коллизий

-ladder2 10 в новом коде выдает 26300 коллизий против 82000 коллизий в прошлом
варик без пробуксовывания может обрабатывать максимум уже не -ladder2 10 а -ladder2 12 - 32200 коллизий

вот получившийся код через GroupEnumUnitsInRange 200
пока через радиус, с ректом не морочился

код GroupEnumUnitsInRange 200

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 takes integer i,real x,real y returns boolean
	local integer j=1
	local real otherx
	local real othery
	local group G = CreateGroup()
	local unit u=null
	if LevelClearState[i]==false then
		call GroupEnumUnitsInRange(G, x,y, 200, null)
		loop
			set u = FirstOfGroup(G)
			exitwhen u==null
			if MB_Frame_On==1 then
				set MB_CollisionY = MB_CollisionY+1
			endif
			if u!=OrangeMushroom[i] then
				set otherx=GetUnitX(u)
				set othery=GetUnitY(u)
				set j=UnitIndex(u)
				if (GetPlayerSlotState(GetOwningPlayer(OrangeMushroom[j]))==PLAYER_SLOT_STATE_PLAYING or j>PLAYER_MAXINUM) then
					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 G=null
								set Frame_MainPlayerY=j
								return false
							endif
						else
							set G=null
							set Frame_MainPlayerY=j
							return false
						endif
					endif
				endif
			endif
			call GroupRemoveUnit(G, u)
		endloop
		set G=null
	endif
	return true
endfunction

перехожу к тестам второго способа через глобалки

goodlyhero 2 года · Answer 11

host_pi:

код GroupEnumUnitsInRange 200

Я просмотрел код.

Из замеченного:

У вас есть вторая функция которая делает также: MushroomMoving_Collision
До возврата через return нужно уничтожать группу через DestroyGroup и потом обнулять группу и юнита.
В целом, вместо ренжа 200 вам хватит и 128
В этот ренж попадает и сам юнит, чего вероятно вам не нужно. Нужно его пропустить, например банальной проверкой:

if(u==<ваш юнит>) then
	call GroupRemoveUnit(G,u)
	set u = FirstOfGroup(G)
endif

nazarpunk 2 года · Answer 12

Показать

nazarpunk 2 года

Показать

goodlyhero:

До возврата через return нужно уничтожать группу через DestroyGroup и потом обнулять группу и юнита.

Или использовать глобалки и не мастурбировать созданием/удалением.

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

goodlyhero: 1. У вас есть вторая функция которая делает также: MushroomMoving_Collision

она для движений по X, и совсем не нагружает код, по сравнению с MushroomMoving_CollisionCheck
на скрине она в текущем фрейме просчитывается по X 0 раз, а по Y 111 раз
поэтому с её переделкой я даже не заморачивался

goodlyhero: 2. нужно уничтожать группу через DestroyGroup

хорошее замечание

goodlyhero: 2. и потом обнулять группу и юнита.

я проводил тесты, да и в том цикле есть условие по exitwhen u==null
разве когда берётся юнит из пустой группы - call GroupEnumUnitsInRange(G, x,y, 200, null) - то переменная u не обнуляется?
чем отличается u=null после выборки из пустой группы и ручное set u=null ?
у меня сначала были строки set u=null, но потом я решил что все равно u обнуляется перебором юнитов в группе и такие строки будут излишни

goodlyhero: 4. В этот ренж попадает и сам юнит, Нужно его пропустить, например банальной проверкой

там же стоит именно такая проверка -- if u != OrangeMushroom[i] then

goodlyhero 2 года · Answer 14

host_pi:

она для движений по X, и совсем не нагружает код, по сравнению с MushroomMoving_CollisionCheck
на скрине она в текущем фрейме просчитывается по X 0 раз, а по Y 111 раз
поэтому с её переделкой я даже не заморачивался

Она отрезается условием, но полный перебор с проверкой этой штуки все равно происходит. Строго говоря не знаю, насколько оно значительно, тем не менее.
host_pi:

я проводил тесты, да и в том цикле есть условие по exitwhen u==null
разве когда берётся юнит из пустой группы - call GroupEnumUnitsInRange(G, x,y, 200, null) - то переменная u не обнуляется?
чем отличается u=null после выборки из пустой группы и ручное set u=null ?
у меня сначала были строки set u=null, но потом я решил что все равно u обнуляется перебором юнитов в группе и такие строки будут излишни

У вас есть вот такая конструкция:

	set G=null
	set Frame_MainPlayerY=j
	return false

Там юнит не обнуленный.
host_pi:

там же стоит именно такая проверка -- if u != OrangeMushroom[i] then

Был невнимателен.

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

goodlyhero: У вас есть вот такая конструкция: Там юнит не обнуленный.

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

nazarpunk: Или использовать глобалки

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

goodlyhero: В целом, вместо ренжа 200 вам хватит и 128

перепроверил с радиусом 128, а также выключил -pro режим, который был включен при первом (с радиусом 200) тесте и съедал фпс на себя
итоговые результаты поразительны - количество коллизий уменьшилось в 3 раза, а максимальное количество коробок стало в 2 раза выше
и если в оригинальном виде - было под 80000 просчётов коллизий и максимум 8 объектов (не путать с 1ым графиком, там чуть щадящая система оценки была и можно сдвинуть на 1 влево)
то в enum128 варианте - происходит только 35000 просчетов коллизий, и макс 15 объектов, что уже ощутимо вырывается по отличиям
мало того, эта система еще и гибкая - т.е. в реальных игровых условиях результаты будут еще чуть лучше, потому что многие объекты стоят отдельно на уровне а не в единой цепочке с остальными

с имеющимся кодом и лимитами варика - думаю осталось два путя:
1 - оптимизировать MushroomMoving_RectCondition, там по 3 раза вызывается MushroomMoving_CollisionCheck на каждый чих а не по 1 и есть шанс еще в 3 раза повысить производительность без потери текущей физики
2 - как предложил Daro делать на триггерах вхождения юнитом в регион (на карте подобная система уже присутствует при нырянии в воду)
возможно есть и другие методы, а также те люди, кто в будущем захочет этим заняться и довести максимальное количество объектов до 50, как и задумано в карте с лабораторией - заспавнить 50 коробок

пожалуй заберу метод с радиусом как облегчение игрокам с низкими фпс
тем более что картоделы тоже страдают от этого лимита коробок, поэтому на карте больше 7+6=13 объектов обычно не появляется

вот код с глобалками - xgm.guru/files/100/315886/comments/520383/BoxLab_1.1_EN_global.j
вот код с глобалками + енум - xgm.guru/files/100/315886/comments/520383/BoxLab_1.1_EN_global_e...
вот чистый енум:

код GroupEnumUnitsInRange 128

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 takes integer i,real x,real y returns boolean
	local integer j=1
	local real otherx
	local real othery
	local group G = CreateGroup()
	local unit u=null
	if LevelClearState[i]==false then
		call GroupEnumUnitsInRange(G, x,y, 128, null)
		loop
			set u = FirstOfGroup(G)
			exitwhen u==null
			if MB_Frame_On==1 then
				set MB_CollisionY = MB_CollisionY+1
			endif
			if u!=OrangeMushroom[i] then
				set j=UnitIndex(u)
				set otherx=GetUnitX(OrangeMushroom[j])
				set othery=GetUnitY(OrangeMushroom[j])
				if (GetPlayerSlotState(GetOwningPlayer(OrangeMushroom[j]))==PLAYER_SLOT_STATE_PLAYING or j>PLAYER_MAXINUM) then
					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
								call DestroyGroup(G)
								set G=null
								set Frame_MainPlayerY=j
								return false
							endif
						else
							set u=null
							call DestroyGroup(G)
							set G=null
							set Frame_MainPlayerY=j
							return false
						endif
					endif
				endif
			endif
			call GroupRemoveUnit(G, u)
		endloop
		call DestroyGroup(G)
		set G=null
	endif
	return true
endfunction

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

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

goodlyhero: Она отрезается условием, но полный перебор с проверкой этой штуки все равно происходит

добавил группу в расчёт по X, количество коллизий сократилось ещё на треть, фпс остался примерно таким же,
макс количество коробок в -box3 режиме выросло на 10%

конечный код:

Открыть

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_Collision takes integer i,real x,real y returns integer
	local integer j=1
	local real otherx
	local real othery
	local group G = CreateGroup()
	local unit u=null
	call GroupEnumUnitsInRange(G, x,y, 128, null)
	loop
		set u = FirstOfGroup(G)
		exitwhen u==null
		if u!=OrangeMushroom[i] then
			set j=UnitIndex(u)
			if (GetPlayerSlotState(GetOwningPlayer(OrangeMushroom[j]))==PLAYER_SLOT_STATE_PLAYING or j>PLAYER_MAXINUM) and WhetherCollision[j]==0 and LevelClearState[j]==false then
				if MB_Frame_On==1 then
					set MB_CollisionX = MB_CollisionX+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 GetUnitTypeId(OrangeMushroom[i])!='orai' and GetUnitTypeId(OrangeMushroom[j])!='orai' then
						if LeftArrow[Frame_MainPlayer]==true and Acceleration[Frame_MainPlayer]<=0 then
							set WhetherCollision[j]=-1
						elseif RightArrow[Frame_MainPlayer]==true and Acceleration[Frame_MainPlayer]>=0 then
							set WhetherCollision[j]=1
						else
							set WhetherCollision[j]=0
						endif
					endif
					set u=null
					call DestroyGroup(G)
					set G=null
					return j
				endif
			endif
		endif
		call GroupRemoveUnit(G, u)
	endloop
	call DestroyGroup(G)
	set G=null
	return 0
endfunction
function MushroomMoving_CollisionCheck takes integer i,real x,real y returns boolean
	local integer j=1
	local real otherx
	local real othery
	local group G = CreateGroup()
	local unit u=null
	call GroupEnumUnitsInRange(G, x,y, 128, null)
	loop
		set u = FirstOfGroup(G)
		exitwhen u==null
		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
							call DestroyGroup(G)
							set G=null
							set Frame_MainPlayerY=j
							return false
						endif
					else
						set u=null
						call DestroyGroup(G)
						set G=null
						set Frame_MainPlayerY=j
						return false
					endif
				endif
			endif
		endif
		call GroupRemoveUnit(G, u)
	endloop
	call DestroyGroup(G)
	set G=null
	return true
endfunction

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

Показать

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

Показать

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

nazarpunk 2 года · Answer 18

Показать

nazarpunk 2 года

Показать

Jack-of-shadow, и ты отложишь всё на .01 сек. Какая разница?

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

Показать

Jack-of-shadow 2 года

Показать

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

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

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

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

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

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

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

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

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

Показать

Vlod 2 года

Показать

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

nazarpunk 2 года · Answer 23

Показать

nazarpunk 2 года

Показать

Vlod:

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

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

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

Показать

Vlod 2 года
Ред. Vlod

Показать

nazarpunk:

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

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

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

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

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

Вход

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

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

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

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

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