Using external dlls for dynamic lighting

ID:116665
 
Aug 2 2011, 6:03 am
A few friends of mine have gotten me to do some kind of blagathon challenge thing where I'm apparently supposed to write five blog posts a week with them. This ties in quite nicely with something I've been doing over the last few days, where I try to do some hobbyist programming every day, and email myself (using the quite handy plus addressing feature of gmail) about what I've done to try and reinforce the habit.

So with intent to start playing this game, here's what I've been working on tonight:
A terribly impressive demonstration of dynamic lighting in DM

The idea is to use an external DLL to generate a per-client lighting mask that can just be rendered as a single client.screen obj over the top of everything, so we get nice pixel-by-pixel lighting. The current implementation is only a few hours old, so it doesn't do a lot yet - doesn't really work in circumstances where the client eye shifts around (readily fixable), probably not really fast enough for proper realtime use (less fixable), doesn't have any kind of concept of opacity (potentially fixable - need to think about that a bit), but it basically functions. Source is available here. The DLL is written in C++ using the Qt framework. And, as is my usual wont, it's not exactly documented.

If this intrigues and interests you, DarkCampainger has done some similar, very clever things.

Extensions, and Places Where This Could Go:
  • Isometric mode, not just topdown mode (Would just require some maths to do the lighting in the right coordinate system)
  • Coloured lights (Should actually be pretty easy)
  • Just how fast can this be done? (Almost certainly much faster than I'm currently doing it, but the call from DM to the DLL is likely going to always be the bottleneck)
  • Opacity. (Problems here include: How much precision do you want with the opaqueness? How do you light the tops of walls? How do you pass the information about location of opaque things to the DLL?)


EDIT: Added a DLL to the zip file. It's build for Windows, 32-bit, and does still require the Qt libraries, so I'm afraid running this will require a little work. Maybe I should host it...
Aug 2 2011, 7:25 am
The server is doing all of the work? it doesn't sound like it'd scale if each client has to download a screen-sized image every time the lighting changes.
Aug 2 2011, 9:19 am (Edited on Aug 2 2011, 11:24 am)
Forum_account wrote:
The server is doing all of the work? it doesn't sound like it'd scale if each client has to download a screen-sized image every time the lighting changes.

Not to mention these are client.screen objects, so the client has to download a screen-sized image whenever the mob moves as well.

I've found that a lighting system needs to take less than 0.01 seconds per light source update to not have an overwhelming effect upon the game's performance.

DarkCampainger's version takes something like 10 seconds to render lighting for a scene, and it sounds like you were planning to work towards a system that has similar functionality to his.

I don't think this is a feasible approach to dynamic lighting.
Aug 2 2011, 11:03 am
Not to mention these are client.screen objects, so the client has to download a screen-sized image whenever the mob moves as well.

that's true. it also wouldn't look right as the screen is scrolling. I don't think this is even a practical approach for static lighting.
Aug 2 2011, 12:04 pm
Isometric mode, not just topdown mode (Would just require some maths to do the lighting in the right coordinate system)

That's not the only problem with isometric mode. These simple effects tend to only look right with a top-down perspective. When you have an isometric or 2.5D view it quickly becomes apparent that shadows and lighting aren't correct. With shadows, you'd have many situations where the mob's body would be split across the boundary of a shadow producing an unrealistic shadow on the mob's icon (because the mob would either be standing completely in the light or completely in the shadow, but their icon will be split across the boundary regardless).
Aug 2 2011, 6:52 pm
Very nice. What formula did you use for the attenuation?

A while back (pre-4.0) someone released a client-side dll for playing games in full-screen. Since the client knows the opacity data, I wonder if it would be possible to hijack the map and overlay a lighting render. It would be an interesting hack...
Aug 3 2011, 1:13 am
Neblim:
The source is available and compilable, and Qt is cross-platform. It's quite usable under Linux.

D4RK3/Forum_account on speed + scalability:
It's all done serverside. I agree that this likely wouldn't work too well for a multiplayer, real-time game. The lighting images are ~20 kb - that's 0.15 seconds transfer time alone at 1 mbps.

I wouldn't rule out singleplayer realtime. On the (admittedly fast) computer I was developing it on, lighting was being finished and updated before the movement animation finished (which leads to some interesting results when the mob isn't keeping up with its own lights...). With some polish and care, I think it /could/ work.

Anything where light sources or eyes aren't moving around realtime - like, say, a roguelike - the idea works fine.

Plus, it doesn't have to be incredibly useful, as such - the idea of having an external DLL do some rendering and then plop the end result onto the screen has been around since BYOND has had external DLLs. This is just a demonstration that that idea can kinda sorta maybe work.

Forum_account, on isometricity:
You're right. I hadn't thought much about isometrics when I originally made the post. Isometric lighting is definitely in the nontrivial basket.

DarkCampainger:
I'm creating a shadowmap by starting with a all-black, max-opaque image, and then for every pixel the alpha is set to 255 - sum(contributions from all lights to that pixel). Lights have intensity, position, and a falloff factor. Contribution to any given pixel by a light is (intensity / (1 + (distance**2 / falloff_factor)).

If the sum of the contribution from all the lights > 255, that pixel becomes rgba(255, 255, 255, light - 255) (that is, lots of light makes things washed out and white).

So absolutely no concept of opacity, and not really doing the same thing as your lightmaps. But also damned close to realtime.

I remember that fullscreen hack. Not sure if this can be done clientside, because I've not looked into DM clientside hackery. Don't know exactly how much the client knows. If the client knows what is where on screen, it's very possible.
Aug 3 2011, 10:09 am
I'm kind of a fan of the idea of using external libs extensively for BYOND games. I once produced a program which would take a correctly annotated side-effect free piece of BYOND code and produce a C library along with correct linkage for it to be usable under BYOND. The idea was to eventually extend it to allow full integration with BYOND - you'd run your game through the program and it would spit out some garbled DM code (consisting mostly of proc stubs containing call()()s) and an external library containing most of the game logic. Unfortunately I lost the original program a while back and every time I go to reproduce such a program I inevitably get disheartened while trying to efficiently and cleanly parse DM.
Aug 3 2011, 12:14 pm
Client-side DLL/SO is possible (as I was working on the communicator and the support library for it). However, it is currently slow due to using world.Export() along with the fact there were some bugs (bugs I need to fix) during the last testing.

I might introduce the source to the "DM External Library Communicator" and/or the Support Library that works with it in the near future. That way, others can also improve upon the design if one desires an improved design.
Aug 3 2011, 12:22 pm
The operations that you might want to use a .dll for tend to end up in one of these two categories:

1. Integral gameplay features that would be sped up by using a .dll if it weren't for the overhead of constantly calling a dll.

2. Features that BYOND can't perform quickly and would be sped up by a .dll but the reason BYOND can't perform them quickly is because they should really be performed client-side.

In either case the .dll isn't as helpful as you'd hope it to be.

Hazman wrote:
I once produced a program which would take a correctly annotated side-effect free piece of BYOND code and produce a C library along with correct linkage for it to be usable under BYOND. The idea was to eventually extend it to allow full integration with BYOND - you'd run your game through the program and it would spit out some garbled DM code (consisting mostly of proc stubs containing call()()s) and an external library containing most of the game logic.

I'm curious what benefit you hoped to get. It sounds like it'd just make your BYOND game a nightmare to debug.
Aug 6 2011, 9:14 am
The idea would be to do it on sections of your game which were largely stable. Provided that the conversion process did not introduce bugs (which depends primarily on it being correctly annotated), your resultant library would not contain more bugs than the original code.

Handily you could also distribute a non-processed version of the game (or perhaps a version which tried to call the library before falling back to DM code) for those not trusting the external DLL.

In testing I found that most non-trivial operations were miles faster when run via external dll, even when accounting for time taken to convert arguments and results to and from strings.

Don't forget that there are operations which you can perform in external DLLs which BYOND can't perform _at all_ - e.g. threaded operations, high-precision mathematic operations, plus the ability to arbitrarily allocate memory. I'm tempted to start work on a library which takes advantage of this (arbitrary memory access) in order to allow for a much higher (practically unlimited, if datums are also written to the file system) datum limit.
Aug 6 2011, 12:16 pm
Now, that would be a great idea. Have a library that utilizes C++ styled dynamic memory allocation. A great way to utilize it too is store pointer/memory address information inside a DM variable to access it later (using string output/input). That's what I been doing lately while handling dynamic memory allocation inside a DLL.

And yes, DLLs have the advantage of allowing threading (though in later versions of BYOND, you must close the threads before shutting down the server or closing Dream Seeker; you will face crashing that wasn't the case when DLL support was first added). In fact, some tasks need threading to work properly (or you will have a frozen server due to being stuck in a call on a single thread).
Sep 11 2011, 4:21 am (Edited on Sep 11 2011, 4:47 am)
Your algorithm for setting the light value for every pixel is to slow, you may read about SIMD commands, and also SSE to save time. The current algorithm needs O(n^n) cycles. You can go down to at least O(n/4), if you interpret the image as a integer array and (one pixel = 32 bit) and use the right operation on 4 elements (128 bit ) at the same time.
On the newest intel processors you could even use 256 bit registers and go down to O(n/8).
Sep 12 2011, 3:32 am
Amsel wrote:
Your algorithm for setting the light value for every pixel is to slow, you may read about SIMD commands, and also SSE to save time. The current algorithm needs O(n^n) cycles. You can go down to at least O(n/4), if you interpret the image as a integer array and (one pixel = 32 bit) and use the right operation on 4 elements (128 bit ) at the same time.
On the newest intel processors you could even use 256 bit registers and go down to O(n/8).

Don't know what you mean by n**n. Algorithm is O(m * n**2) with m lights and an n*n screen.

I'm aware of SIMD/SSE in a vague sense. Don't exactly see how it's dropping a factor of n from the order of complexity. It probably would be faster - likely significantly so - and multithreading might also make things faster. It'd be tricky to implement though - the dependence on the distance from lights would make it difficult to do with a series of parallel instructions.

But it would also probably not contribute much to making the whole shebang much faster. The principle bottleneck here is always going to be writing the file out and reading it in again.
Sep 12 2011, 3:51 am
the dependence on the distance from lights would make it difficult to do with a series of parallel instructions

As long as lights are positioned at pixels and don't have decimal precision, for every light there are 4 or 8 points equidistant from it that can be computed without much trouble. It wouldn't work if you tried to add anything else (ex: shadows) and it wouldn't make much of a difference anyway, O(m*n*n/4) is still O(m*n*n) (and I doubt it'd be a factor of 1/4 in the first place because you're still loading all n*n values into registers, you're doing 1/4th as many of one operation, not all operations).