Как можно оптимизировать этот код с 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: Она отрезается условием, но полный перебор с проверкой этой штуки все равно происходит

добавил группу в расчёт по 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 2

Показать

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

Показать

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

nazarpunk 2 года · Answer 3

Показать

nazarpunk 2 года

Показать

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

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

Показать

Jack-of-shadow 2 года

Показать

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

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

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

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

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

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

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

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

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

Показать

Vlod 2 года

Показать

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

nazarpunk 2 года · Answer 8

Показать

nazarpunk 2 года

Показать

Vlod:

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

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

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

Показать

Vlod 2 года
Ред. Vlod

Показать

nazarpunk:

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

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

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

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

nazarpunk 2 года · Answer 11

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

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

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

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

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

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

Вход

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

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

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

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

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