LOS Gadget, v. 0.1

LOS Gadget, v. 0.1

Discuss Lua based Spring scripts (LuaUI widgets, mission scripts, gaia scripts, mod-rules scripts, scripted keybindings, etc...)

Moderator: Moderators

User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

LOS Gadget, v. 0.1

Post by Argh »

I sat down this evening and wrote a LOS Gadget. It's ugly, un-optimized and doesn't do everything I want it to do yet. That said, it's already faster than the current LOS system in Spring, especially for flying aircraft and other fast-moving objects. It might or might not ever be fully workable in Lua, and I'm sure it'd run much faster engine-side, but now that I have access to the LOS states of things, I thought I'd put some of my ideas into a working form and see how it went.

Try it out. Just set some Units' SightDistance to 0 and try a test game with one AI player.

Code: Select all

function gadget:GetInfo()
	return {
		name = "Alternative LOS Handler",
		desc = "Replaces Spring's LOS system with a cell-based handler.",
		author = "Argh",
		date = "December 14th, 2008",
		license = "Public Domain, or the least-restrictive rights of your country of residence",
		layer = 1,
		enabled = true,
	}
end

if (gadgetHandler:IsSyncedCode()) then
--------------------------------------------------------------------------------
--  SYNCED
--------------------------------------------------------------------------------


---------------------------------------------------------------------------------VARIABLE DECLARATIONS
local LOSTable = {}
local LOSList = {}
local LOS_SectorSize = 1024
local i,j,count = 0,0,0

local teamTable0 = {}
local teamTable1 = {}

local unitID
local MaxSizeX = Game.mapSizeX
local MaxSizeZ = Game.mapSizeZ

local startX = 0 - LOS_SectorSize
local startZ = 0 - LOS_SectorSize

local finishX = MaxSizeX + LOS_SectorSize
local finishZ = MaxSizeZ + LOS_SectorSize

local gaiaTeam = Spring.GetGaiaTeamID()

local unitTable

function gadget:Initialize()

end

function unitCreated(unitID, unitDefID, teamID)
	Spring.SetUnitLosState(unitID, teamID, { los = true})
	Spring.SetUnitLosMask(unitID, teamID, { los = true})
end

function gadget:GameFrame(f)
	if f % 16 < 0.1 then
	for _,unitID in ipairs (Spring.GetAllUnits()) do
		local lengthTable = Spring.GetTeamList()
		local length = # lengthTable
		for i = -1,length,1 do
			--Spring.Echo(i)
			if Spring.GetTeamInfo(i) ~= nil then
				local team = Spring.GetUnitTeam(unitID)
				if team ~= gaiaTeam and team ~= i then
					Spring.SetUnitLosMask(unitID, i, { los =false})
					Spring.SetUnitLosState(unitID, i, { los = false})
				end
				if team == gaiaTeam or team == i then
					Spring.SetUnitLosMask(unitID, i, { los = false})
					Spring.SetUnitLosState(unitID, i, { los = true})
					Spring.SetUnitLosMask(unitID, i, { los = true})
				end
			end
		end
	end
	for squareX = startX,finishX,LOS_SectorSize do
		for squareZ = startX,finishX,LOS_SectorSize do
			count = count + 1
			unitTable = Spring.GetUnitsInRectangle(squareX,squareZ,squareX + LOS_SectorSize, squareZ + LOS_SectorSize)
			if unitTable[1] ~= nil then
				for _,unitID in ipairs (unitTable) do
					local team = Spring.GetUnitTeam(unitID)
					if team == 0 then
						table.insert(teamTable0,{squarex = squareX - 1, squarez = squareZ - 1})  -- UPPER LEFT
						table.insert(teamTable0,{squarex = squareX, squarez = squareZ - 1})  -- UPPER CENTER
						table.insert(teamTable0,{squarex = squareX + 1, squarez = squareZ - 1})  -- UPPER RIGHT
						table.insert(teamTable0,{squarex = squareX - 1, squarez = squareZ})  -- CENTER LEFT
						table.insert(teamTable0,{squarex = squareX, squarez = squareZ}) -- CENTER
						table.insert(teamTable0,{squarex = squareX + 1, squarez = squareZ})  -- CENTER RIGHT
						table.insert(teamTable0,{squarex = squareX - 1, squarez = squareZ + 1})  -- LOWER LEFT
						table.insert(teamTable0,{squarex = squareX, squarez = squareZ + 1})  --  LOWER CENTER
						table.insert(teamTable0,{squarex = squareX + 1, squarez = squareZ + 1})  -- LOWER RIGHT
					end
					if team == 1 then
						table.insert(teamTable1,{squarex = squareX - 1, squarez = squareZ - 1})  -- UPPER LEFT
						table.insert(teamTable1,{squarex = squareX, squarez = squareZ - 1})  -- UPPER CENTER
						table.insert(teamTable1,{squarex = squareX + 1, squarez = squareZ - 1})  -- UPPER RIGHT
						table.insert(teamTable1,{squarex = squareX - 1, squarez = squareZ})  -- CENTER LEFT
						table.insert(teamTable1,{squarex = squareX, squarez = squareZ}) -- CENTER
						table.insert(teamTable1,{squarex = squareX + 1, squarez = squareZ})  -- CENTER RIGHT
						table.insert(teamTable1,{squarex = squareX - 1, squarez = squareZ + 1})  -- LOWER LEFT
						table.insert(teamTable1,{squarex = squareX, squarez = squareZ + 1})  --  LOWER CENTER
						table.insert(teamTable1,{squarex = squareX + 1, squarez = squareZ + 1})  -- LOWER RIGHT
					end
				end
			end
		end
	end


	if # teamTable0 ~= nil then
		for a,b in ipairs (teamTable0) do
			if b.squarex ~= nil then
				--Spring.Echo("found")
				local sightTable = Spring.GetUnitsInRectangle(b.squarex,b.squarez, b.squarex + LOS_SectorSize, b.squarez + LOS_SectorSize)
				for _,unitID in ipairs (sightTable) do
					local team = Spring.GetUnitTeam(unitID)
					if Spring.GetUnitIsCloaked(unitID) == false and team ~= 0 and team ~= gaiaTeam then
						Spring.SetUnitLosState(unitID, 0, { los = true})	
						Spring.SetUnitLosMask(unitID, 0, { los = true})				
					end
					
				end
			end
			table.remove(teamTable0,a)
		end
	end

	if # teamTable1 ~= nil then
		for a,b in ipairs (teamTable1) do
			if b.squarex ~= nil then
				--Spring.Echo("found")
				local sightTable = Spring.GetUnitsInRectangle(b.squarex,b.squarez, b.squarex + LOS_SectorSize, b.squarez + LOS_SectorSize)
				for _,unitID in ipairs (sightTable) do
					local team = Spring.GetUnitTeam(unitID)
					if Spring.GetUnitIsCloaked(unitID) == false and team ~= 1 and team ~= gaiaTeam then
						Spring.SetUnitLosState(unitID, 1, { los = true})	
						Spring.SetUnitLosMask(unitID, 1, { los = true})				
					end
					
				end
			end
			table.remove(teamTable1,a)
		end
	end

	end
end
-------------------------------------------------------------------------------------------END SYNC
end
What this code does is to divide the map into LOS "sectors". Each sector is 1024 map-units on a side.

Then it's searching for any units on a given Team inhabiting that sector. If it finds any, it stores that information in a table, and then "populates" the surrounding sectors.

If a given Team returns a list of valid sectors, then a search is performed, on a per-sector basis, searching for Units and changing their state. If a given Unit is not currently visible, then they become visible.

All of that works. Gaia stuff remains visible. It's fast, and not frame-bound like the current LOS system. It uses a cell-based system, instead a unit-bound system- what counts is not unit positions, or terrain, but whether a given cell is inhabited.

To make it really worth using, though, a lot of suck needs to get removed, and I'm posting this up in case anybody is interested in this topic and would like to help make it run better.

1. I've eliminated overlapping searches, which are obviously very costly, but now I have to do a bunch of smaller searches, which is not efficient, especially in Lua. I'd like to know if there's a way to convert the grid into a smaller number of efficient search zones, to reduce the number of searches as much as possible.

2. There are all kinds of glitchy behaviors that occur if I set the LOS Mask / State like this. CEGs become invisible, because AirLOS expects LOS entries in the LOS Handler, and if there aren't any, it can't get the job done.

However, the fact that I can see a few CEGs almost makes it look like there's some minimal presence in the LOS Handler, which doesn't make any sense at all.

I'm not sure how to deal with this. We can't modify the state of CEGs, get their existence, turn their visibility on / off, etc., so I'm kinda stuck on that one at the moment.

Lastly, the current LOSHandler keeps trying to change the LOS status of Units, unless the Mask is set. I'd like a way to turn the LOSHandler completely off, or just restrict it to CEGs, it's very annoying to have to set the masks to keep my Units from blinking out constantly.

3. There's the obvious accuracy discrepancy between zones based on their size- i.e., the farther the Unit gets from the center of a zone, the more obvious it is that the LOS is not bound to the Unit at all. Until I have a fast method of consolidating searches into the lowest-possible number of areas, it's not very practical to think about making the zones smaller to avoid this.

All of these errors / issues aside, this is a really different approach to LOS for this engine, and one that I think is worth exploring further, as it's already quite fast and ignores terrain. If anybody has some practical ideas to address these issues, your opinion is welcome, or you can take the code as-is.
User avatar
aegis
Posts: 2456
Joined: 11 Jul 2007, 17:47

Re: LOS Gadget, v. 0.1

Post by aegis »

Argh wrote:Until I have a fast method of consolidating searches into the lowest-possible number of areas, it's not very practical to think about making the zones smaller to avoid this.
search areas?
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: LOS Gadget, v. 0.1

Post by Argh »

search areas?
Yeah, basically. I need a smart algorithm that will reduce the number of searches down, where appropriate. If the algorithm's faster, on average, than doing the smaller search zones, then it would help a bit speedwise.

For example, if two squares are side-by-side, it needs to treat them like a rectangle. This would result in much faster search times. It's a fairly non-trivial problem, though, finding the optimal combination of searches, and it's not something I'm familiar with.

For example... let's say that the occupied-squares table comes out like this:
Image
This is quite a few searches. Keep in mind, while the speed of actual result from Spring can be assumed to be a n^2 problem, it's the Lua portion where it's having to evaluate the results that worries me.

I'd like to reduce it to three searches, like this:
Image

I know there must be ways to do this, but as I said, this isn't something I'm familiar with.

P.S.: I just tried setting airSightDistance, which looks like it should work, even if sightDistance == 0, but it doesn't work for showing CEGs that are supposedly using AirLOS, i.e., CEG setting useAirLOS=1;

I don't see anything in the LOS code that suggests AirLOS is disabled, so I'm kinda confused why that's not working as intended.
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: LOS Gadget, v. 0.1

Post by lurker »

Spring also has a cell-based search; the cells are just normally set to be really small. This does look useful, but what's different from it and ALOS at mip level 7 with all units at 750 los?
Last edited by lurker on 15 Dec 2008, 04:31, edited 2 times in total.
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: LOS Gadget, v. 0.1

Post by Argh »

Spring also has a cell-based search; The cells are just normally set to be really small. This does look useful, but what's different from it and ALOS at mip level 7 if it was rectangular?
Well, what's mainly different, based on what I've read from the LOSHandler source, is a few important things:

1. It's not doing per-Unit checks for terrain blocking, which saves a lot of time.

2. It's using square search areas, instead of a complex mip-based solution. In that sense, it's basically mip level 7, but not really, because I don't think that you ever end up with true squares even at that mip level, dunno, I'll have to look at that.

3. It's not framebound, movement bound, etc. So it can be run faster or slower, to adjust the rate if it's going to have smoother results. So, if you just want one update per second, it's very simple to change that. Or go even slower, but use larger squares... you can make that tradeoff, whereas you can't really do any of that with the current system.

All of that said, I regard this as a rough prototype only. I'm just playing around with all of this, basically, trying to see whether a better model can be found. You know I've whined and moaned about the slow performance of the LOSHandler more than once, so I figure that instead of just pontificating, I'd try and actually build a working model.

One thought just occurred to me... if I could manipulate the LOS squares, instead of the LOS status / flags, this would have all of its current advantages, and very few disadvantages.
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: LOS Gadget, v. 0.1

Post by lurker »

ALOS doesn't use terrain, and it's trivial to add a circular mode for normal LOS. Always using a square will only be slightly faster with cells that large; setting the array is almost none of the calculation load. And 'not frame-bound' strikes me as a very odd term to mean 'changable update frequency'.
Argh wrote:One thought just occurred to me... if I could manipulate the LOS squares, instead of the LOS status / flags, this would have all of its current advantages, and very few disadvantages.
What advantages? Just changing the map update frequency?
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: LOS Gadget, v. 0.1

Post by Argh »

ALOS doesn't use terrain
But a Unit cannot use ALOS to actually see other Units... and, as I noted above, if sightDistance < airSightDistance, then the Unit can't see CEGs, which means that something is really 'orribly borked. I just looked at the code, and it assumes that airLOS == -1 unless set otherwise, and there's a commented-out line in LOSHandler that suggests that ALOS isn't actually getting calculated at all- it's just using standard LOS. IDK for certain, by any means- what I do know is that if I have this running for Units with SightDistance=0, then my Units can see other Units, but can't see Projectiles or CEGs properly, which sucks.

Trust me, if I had a LOS that didn't take terrain into account and worked right with CEGs, I'd just use that. I seriously doubt that anything I could write in Lua would be faster, if for no other reason than language speeds.
What advantages? Just changing the map update frequency?
Yeah, among other things it could reduce the update frequency or decrease the granularity based on the number of non-Gaia Units, or both, to keep this from being one of the killer chokepoints for this engine, among other things. I can't imagine that doing the actual area-search and the table matchups in Lua is fast, it's probably horribly slow compared to C++.
Last edited by Argh on 15 Dec 2008, 04:50, edited 1 time in total.
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: LOS Gadget, v. 0.1

Post by lurker »

You probably could have written the code for circular normal los in less time than writing this lua. :roll: I think you're missing the point of me mentioning alos. You use the SAME CODE for normal los.
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: LOS Gadget, v. 0.1

Post by Argh »

Maybe, but then I'd have to argue for inclusion... with the same people who have repeatedly refused to implement it, citing various reasons that I've just disproved.

It really is a lot faster to ignore terrain, use slower updates, and not pay any attention to movement, and this makes it obvious. It's doing 3*1024^2 per Unit, or a greater LOS area than any one unit is allowed to have for Spring, and it's still faster.
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: LOS Gadget, v. 0.1

Post by lurker »

I have commit access, just do it right and give it to me, or flip a coin to see if I'll code it myself soon.
Warlord Zsinj
Imperial Winter Developer
Posts: 3742
Joined: 24 Aug 2004, 08:59

Re: LOS Gadget, v. 0.1

Post by Warlord Zsinj »

I came up tails
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: LOS Gadget, v. 0.1

Post by Argh »

I got a bit distracted there for a minute. Look, I'd love to write you a patch, but:

A. If I'm going to bother, I'd gut it and do it closer to this.

B. Instead of bothering, I think it'd be better to fix ALOS, and then I could just use this and ALOS, and if anybody gets around to making something like this as an alternative sometime, great, if not, oh well, I still have faster code.

But LOSHandler and ALOS are basically not working as they should be. Here, try this, with the Gadget installed. Change a Unit's FBI tags thusly:

SightDistance=1;
airSightDistance=1024;

Without other Units around, do something that creates a CEG event.

Now, according to everything up until it gets to the actual LOSHandler code, that should allow CEGs to be seen. SightDistance is 1 because one of the loops won't even run if <= 0.

It doesn't work. Why it doesn't work, I'm not entirely sure.

Next, I disabled the Gadget, and used those same settings. I was thinking, "hey, my Gadget's doing all sorts of funny stuff, maybe that's what's wrong". Nope. ALOS does not actually obey the variable that it's supposed to. It appears to only obey SightDistance.

While I'm on that topic, all CEGs have useAirLos forced to TRUE, even though that should not be done. By default, they should use normal LOS, setting useAirLos in the CEG should override that default.

Basically, to get anywhere with this, a change in the engine making ALOS actually work like it's supposed to is the place to start. Problem is, I'm not really sure how to do that. In the LOShandler, There's a disabled line:

//airAlgo(int2(airSizeX, airSizeY), -1e6f, 15, readmap->mipHeightmap[airMipLevel])

And it appears to me that somebody basically gutted ALOS some time ago, in favor of just having everything use LOS. I dunno where to start with that, given what I'm reading there. Hell, I'll be the first to say that I don't understand at least of half of that code. For example, it's storing a hash value... why, when you can do it like I did, with a 2D array for occupied cells? I assume there's a good reason for that, but I dunno what it is. Is it storing a unique LOSMap for a given Unit, maybe? If so, that's one reason why it's so slow, and why it seems to get slower faster with large areas. It's not the raw search for Units, people. The code I posted here shows that it's not that, and the slightly-more-optimized version I have over here is definitely not choking due to the searches- I did things that normally make Spring come to a screeching halt, like fly 80 planes around on patrol paths that would ensure a lot of the entire map was being searched, and it was performing very reasonably.

And of course, it's doing the non-cheap height vs. mipmap stuff, which, btw, doesn't seem to return valid results a lot of the time. I've seen situation after situation where a Unit's standing next to a hill, and can't see the LOS squares up the side of the hill, or below in a valley, if you turn the mip levels higher than 1. At 6, it should be practically ignoring height entirely, but it doesn't seem to work correctly at all.

So, this is pretty much stuck in limbo, until I either sit down and figure out how to recode what I've done here in C++ that will get along with Spring, and then have it available via a mod-side tag, I think (unless somebody sees that "quick fix" lurker mentioned, because I sure don't). Better to just have an entirely different mode than to try and kludge new behavior into what we have.

Lastly, I just did a performance test that was pretty convincing about the whole worth of the thing as an idea. I just tested 1024 sightDistance Units vs. Units that could only use this, and did a pretty standard stress-test for LOS.

For the test, I placed members of one team all over the map, pretty much giving them complete coverage. Then I placed groups of 40 for the other team until the game reached an unplayable FPS (i.e., anything under 15). Then I repeated the procedure, but used fewer groups of 40- then gave those groups Patrol orders, to simulate the real-world impact of heavy games with a lot of units.

When nothing was moving, Spring's LOSHandler won, barely. I was a bit surprised, but I guess it's the sheer speed difference in the code, and the fact that mine has to update whether or not things have moved.

When stuff started moving, though... whee, what a difference. The code above, as ugly and undoubtably poorly designed as it is, won hands down over Spring's current LOSHandler, with mipmap settings of 6. It was nearly twice as fast. Oh, and it was covering 1024*3 ^2 in area, too, vs. a radius of 1024 for Spring's LosHandler, so > 50% more surface area.

Look, I know people are going to want to argue various aspects of all of this. First thing I have to say is that you should test it first, and see the difference in behavior. Remember, it's doing 1024*3^2, so jack up the sightDistance to at least 1024 for a fair test. I think that my version will crush LOSHandler at 2048 vs. 2048, but that's always been seen as the absolute high end for LOS in this engine anyhow, and that's a damn long distance in most game scales anyhow.

But there is no free lunch, and I don't honestly have any idea how to do a faster LOS algorithm that takes terrain into account, so adopting this model would have to be optional by all means. Personally, I'd ditch false negative readings, CEGs that are being drawn before the Units they're attached to are officially visible, and all of the other known bugs in a heartbeat for something that's straightforward like this.
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: LOS Gadget, v. 0.1

Post by lurker »

Let's see, one bug report that I'll look at, and:
If two units in the same cell have the same los distance and the same height, they share the math. You can't just use the cell location, so it does a hash.
Tobi
Spring Developer
Posts: 4598
Joined: 01 Jun 2005, 11:36

Re: LOS Gadget, v. 0.1

Post by Tobi »

Argh wrote: Basically, to get anywhere with this, a change in the engine making ALOS actually work like it's supposed to is the place to start. Problem is, I'm not really sure how to do that. In the LOShandler, There's a disabled line:

//airAlgo(int2(airSizeX, airSizeY), -1e6f, 15, readmap->mipHeightmap[airMipLevel])
I just left that line in with the refactoring I did recently as a hint on how to implement terrain based airLos, in case anyone wants to make that.
For example, it's storing a hash value... why, when you can do it like I did, with a 2D array for occupied cells? I assume there's a good reason for that, but I dunno what it is.
LosInstances for units in the same square with the same los radius are shared (multiple units share the same LosInstance then). This (and only this) is done with the hash table in CLosHandler.
Is it storing a unique LOSMap for a given Unit, maybe? If so, that's one reason why it's so slow, and why it seems to get slower faster with large areas.
Yes, and it has to.

LOS is currently still raycasted against terrain (would be very easy to add an option to make it circular after my refactor). Between adding a unit to the LOS map and removing it, the terrain may have changed. In other words, the squares marked for the unit need to be remembered to be able to remove the unit from the los map later on.

As you can see in the code, airLosSquares aren't remembered. That's because the airLos isn't raycasted against terrain but is just a filled circle, which can be erased from the los map entirely deterministically.
It's not the raw search for Units, people.
There isn't even a raw search for Units in current LosHandler :-)
The code I posted here shows that it's not that, and the slightly-more-optimized version I have over here is definitely not choking due to the searches- I did things that normally make Spring come to a screeching halt, like fly 80 planes around on patrol paths that would ensure a lot of the entire map was being searched, and it was performing very reasonably.
Performance drop from 80 planes is barely noticable here... what kind of planes? (losRadius, airLosRadius, radarRadius, etc.)
And of course, it's doing the non-cheap height vs. mipmap stuff, which, btw, doesn't seem to return valid results a lot of the time. I've seen situation after situation where a Unit's standing next to a hill, and can't see the LOS squares up the side of the hill, or below in a valley, if you turn the mip levels higher than 1. At 6, it should be practically ignoring height entirely, but it doesn't seem to work correctly at all.
It never ignores height, it takes average height, ie. from the mipHeightmap. So results with higher losmiplevels depend very much on whether hills lie properly aligned with los square boundaries or not. (If not, the box average throws away a lot of the information present in the original heightmap.)

Realize that you're basically downsampling the heightmap by a huge amount with mip levels higher then 1. At 6, you're sampling a heightmap 64 times smaller in both directions than the raw heightmap as included in the map. (ie. you're taking box average of 64 x 64 heightmap area and using that single value to determine whether a square gets LOS or not.)
But there is no free lunch, and I don't honestly have any idea how to do a faster LOS algorithm that takes terrain into account, so adopting this model would have to be optional by all means. Personally, I'd ditch false negative readings, CEGs that are being drawn before the Units they're attached to are officially visible, and all of the other known bugs in a heartbeat for something that's straightforward like this.
That's exactly the problem, current losHandler is hard to optimize much more because there is the option of it taking terrain into account.

Making it circular however and increasing miplevel would probably boost performance by a huge amount tho.

(It does approx. 100% 'overdraw' though in the terrain raycasting, but even fixing this (which is hard) wouldn't reduce the algorithmic complexity.. TBH I think the only way to do faster terrain based LOS involves very complex data structures based on map heightmap...)
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: LOS Gadget, v. 0.1

Post by Argh »

Performance drop from 80 planes is barely noticable here... what kind of planes? (losRadius, airLosRadius, radarRadius, etc.)
80 aircraft with a LOS of 1024 is a pretty significant performance hit over here, if flying over a bunch of Units that aren't AlwaysVisible and aren't on your team, especially if the terrain causes a lot of complex recalculations.

It's really pretty noticeable(on my hardware) when you have "encounter" situations between fast-movers and large numbers of Units.

Other than that... yes, I'd like to have an option of using circular LOS.

I dunno how to do it, though, otherwise I'd have posted a patch by now. You guys have both said it's simple, but I guess in this case, "simple" is relative- I haven't done any C++ stuff other than read engine code occasionally for quite awhile though :P
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: LOS Gadget, v. 0.1

Post by lurker »

But... those idle units just check the los map; there should be 0 performance change for those checks depending on the units flying above.
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: LOS Gadget, v. 0.1

Post by Argh »

It's not the static guys, it's the mobile guys that do it. They're changing sectors quickly enough, and if they're spread out a lot, they cause a huge hit, because they're all using unique LOS maps.

That part- the unique LOS maps- really, really bothers me, btw. Maybe I just don't understand it's benefits, but from over here, it looks like a massive waste of CPU.

I'm building one LOS map, per Team. Then it's setting the LOS states and masks when it's done building the map.

LOS should always be a Team-based concept, not a Unit-based one, imo.

Why? Well, weapons don't care who has LOS, they just search for valid targets that are visible. Since they don't care, neither should the LOSHandler. I suspect that that part is a leftover from SJ, when he was attempting to build a realistic war sim ;)

Lastly... I think that the word, "search" qualifies here. I'm probably using terminology incorrectly as usual, but I'm meaning "iterative process to determine the state of a thing".

When we get done making a LOS map... we need to iterate through the Units in those sectors, and, if Visible, set their LOS state and mask. That is a "search", to me.

Lastly... Tobi said there's 100% overlap. Did that take into account re-attempts to set the LOS state / mask that update? If not... well, depending on the mip level, you're probably talking about up to 900% overlap for that part. Sure, each pass is fast, you're just checking a bit state and mask. But... get 1000 Units on a map, it gets cumbersome, fast. World Builder is a situation where you're going to see that... a lot.
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: LOS Gadget, v. 0.1

Post by lurker »

Units don't have los maps, they just store a list of what squares they could see the last time they updated.
Argh wrote:When we get done making a LOS map... we need to iterate through the Units in those sectors, and, if Visible, set their LOS state and mask. That is a "search", to me.
This never happens. Spring waits for those units to update by themselves later on.

One thing that can be done for a lot of optimization is, when map damage is off, to only calculate the list of squares for each cell once per height group.
User avatar
Argh
Posts: 10920
Joined: 21 Feb 2005, 03:38

Re: LOS Gadget, v. 0.1

Post by Argh »

Units don't have los maps, they just store a list of what squares they could see the last time they updated.
Ah, ok. So, if they don't update often, then in theory all Units sharing a hash speed up the LOS map process a lot. I get it. That's why it was faster than mine, when nobody's moving.
One thing that can be done for a lot of optimization is, when map damage is off, to only calculate the list of squares for each cell once per height group.
Yeah, that would help a lot, 'specially since most of us have turned map damage off in our games, for most practical purposes. Maybe just have a flag whether damage has occurred anywhere the previous frame?
User avatar
lurker
Posts: 3842
Joined: 08 Jan 2007, 06:13

Re: LOS Gadget, v. 0.1

Post by lurker »

Well, I think the instance-sharing is a rare occurance right now. The units have to have exactly the same radius and hitshape offset; that could be changed to have some flexibility. Not to mention how tiny the cells are normally.
Post Reply

Return to “Lua Scripts”