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

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 2

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 3

Показать

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

Показать

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

nazarpunk 2 года · Answer 4

Показать

nazarpunk 2 года

Показать

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

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

Показать

Jack-of-shadow 2 года

Показать

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

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

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

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

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

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

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

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

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

Показать

Vlod 2 года

Показать

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

nazarpunk 2 года · Answer 9

Показать

nazarpunk 2 года

Показать

Vlod:

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

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

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

Показать

Vlod 2 года
Ред. Vlod

Показать

nazarpunk:

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

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

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

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

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

Вход

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

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

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

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

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