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

nazarpunk 2 года · Answer 1

host_pi:

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

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

host_pi:

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

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

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

host_pi:

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

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

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

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

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

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

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

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

goodlyhero: EnumUnitsInRect

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

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

Показать

goodlyhero 2 года
Ред. goodlyhero

Показать

host_pi:

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

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

nazarpunk 2 года · Answer 5

Показать

nazarpunk 2 года

Показать

goodlyhero:

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

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

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

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

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

в карте у всех юнитов стоит 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 8

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 9

Показать

nazarpunk 2 года

Показать

goodlyhero:

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

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

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

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 11

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

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

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

Вход

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

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

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

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

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