6 ms·

>The problem “how to find the closest 3 light sources and to calculate the distance and an angle was solved with a script running in the Update() loop. > > Yes,

by clarry 8y ago

>The problem “how to find the closest 3 light sources and to calculate the distance and an angle was solved with a script running in the Update() loop. > > Yes, it’s not the quickest way considering how much math is involved. If I programmed it today, I would use that modern Unity Jobs System. But when I did it there was no such thing so I had to optimize regular scripts we had. I wish they'd let you in on a little more. Because my numb mind says this isn't something you should ever need to optimize. How many light sources do they have, dozens at most? And how many sprites? Dozens/hundreds? That is nothing.. what is this heavy math? I figured all they'd need is a vector from light source to object, and the vector's magnitude.

mmastrac 8y ago
This could _possibly_ be because Unity's scripting engine is Mono/C# which might not be optimal for doing large amounts of math in tight loops in this particular case. 100% supposition.
- clarry 8y ago
  I mean, my point was that a few dozen light sources times a few hundred sprites isn't large amounts of math, unless they're doing something really fancy with each pair. Language speed definitely isn't key here. It's got to be something else.
  - beetwenty 8y ago
    Finding the nearest three light sources is the main bottleneck, and in scenarios with many lights, is highly dependent on having a broadphase algorithm to filter them out early. If they did it the naive way, the algorithm becomes O(number of sources * number of lit objects). But that doesn't seem to be their concern here, either. Optimizing broadphase collision is a well-understood problem, and the scenario of finding the nearest is only slightly different from that.
- pjmlp 8y ago
  In more recent versions it is actually IL2CPP for most targets, and with the addition of former Insomiac devs, their C# subset (HPC#) has been taking a greater role on the engine.
BugsJustFindMe 8y ago
Indeed. And you don't even need square roots for identifying the three closest, since squared distances are just as good for that. So it's, what, a few instances of very basic arithmetic and then three roots? I don't see the complication either. It would be nice to know which part of their process introduced the difficulty. Was it the update frequency?
- simcop2387 8y ago
  I might even avoid the squares and use a manhattan distance metric instead. No multiplication at all, just absolute value and addition.
- viggity 8y ago
  finding an approximate root for these purposes can be really quite fast, as was demonstrated in Quake III. https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root
IkmoIkmo 8y ago
Agreed. I've written a lighting system exactly like this one (it's a very common 2d lighting concept, basically any sprite-based game with dynamic lightning will use exactly this). The only difference was that I used 24 light-direction frames instead of 4 frames because I was pre-rendering 3d models to 2d sprites, so I didn't have to have an artist draw each frame but could just export any level of precision, limited not by the artist but by filesize/memory. The calculations he's talking about are as simple as it gets and were never really a problem for me even on low-end machines. (I was building a top-down space rpg, basically any of the 100 plasma discharges, engine exhausts, particles etc was a dynamic source of light)
thrower123 8y ago
I would hope that they aren't doing that calculation for every sprite every frame. It strikes me that most of the sprites and probably most of the light sources are static, so most of the information could be precalculated and cached, which would leave just the moving sprites and lights. I would probably look at some kind of spatial partioning and marking sections dirty to prune things further. If it turned out to be significant enough that it was hurting framerate, anyway.
OskarS 8y ago
Doing it the "naive" way would be: for every object that needs to be rendered like this, loop through all the lights and find the closest 3 of them. That would be O(n * m) where n is the number of lights and m is the number of objects. If you have hundreds of lights and thousands of objects, it's not insignificant, especially since you're doing it on the main thread. I had to do this for a Unity game which had a similar "custom" light solution, and on lower end devices it was a problem. It was easily solved using a simple spacial data structure, but doing it the naive way did present some issues.

by clarry 8y ago

mmastrac 8y ago

This could _possibly_ be because Unity's scripting engine is Mono/C# which might not be optimal for doing large amounts of math in tight loops in this particular case. 100% supposition.

clarry 8y ago
I mean, my point was that a few dozen light sources times a few hundred sprites isn't large amounts of math, unless they're doing something really fancy with each pair. Language speed definitely isn't key here. It's got to be something else.
- beetwenty 8y ago
  Finding the nearest three light sources is the main bottleneck, and in scenarios with many lights, is highly dependent on having a broadphase algorithm to filter them out early. If they did it the naive way, the algorithm becomes O(number of sources * number of lit objects). But that doesn't seem to be their concern here, either. Optimizing broadphase collision is a well-understood problem, and the scenario of finding the nearest is only slightly different from that.
pjmlp 8y ago
In more recent versions it is actually IL2CPP for most targets, and with the addition of former Insomiac devs, their C# subset (HPC#) has been taking a greater role on the engine.

BugsJustFindMe 8y ago

Indeed. And you don't even need square roots for identifying the three closest, since squared distances are just as good for that. So it's, what, a few instances of very basic arithmetic and then three roots? I don't see the complication either. It would be nice to know which part of their process introduced the difficulty. Was it the update frequency?

simcop2387 8y ago
I might even avoid the squares and use a manhattan distance metric instead. No multiplication at all, just absolute value and addition.
viggity 8y ago
finding an approximate root for these purposes can be really quite fast, as was demonstrated in Quake III. https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root

IkmoIkmo 8y ago

Agreed. I've written a lighting system exactly like this one (it's a very common 2d lighting concept, basically any sprite-based game with dynamic lightning will use exactly this). The only difference was that I used 24 light-direction frames instead of 4 frames because I was pre-rendering 3d models to 2d sprites, so I didn't have to have an artist draw each frame but could just export any level of precision, limited not by the artist but by filesize/memory. The calculations he's talking about are as simple as it gets and were never really a problem for me even on low-end machines. (I was building a top-down space rpg, basically any of the 100 plasma discharges, engine exhausts, particles etc was a dynamic source of light)

thrower123 8y ago

I would hope that they aren't doing that calculation for every sprite every frame. It strikes me that most of the sprites and probably most of the light sources are static, so most of the information could be precalculated and cached, which would leave just the moving sprites and lights. I would probably look at some kind of spatial partioning and marking sections dirty to prune things further. If it turned out to be significant enough that it was hurting framerate, anyway.

OskarS 8y ago

Doing it the "naive" way would be: for every object that needs to be rendered like this, loop through all the lights and find the closest 3 of them. That would be O(n * m) where n is the number of lights and m is the number of objects. If you have hundreds of lights and thousands of objects, it's not insignificant, especially since you're doing it on the main thread. I had to do this for a Unity game which had a similar "custom" light solution, and on lower end devices it was a problem. It was easily solved using a simple spacial data structure, but doing it the naive way did present some issues.