Lighting Engine!

(EDIT-ALL THE PROBLEMS I WAS HAVING WERE FIXED, SCROLL DOWN FOR WORKING VERSIONS OF THE ENGINE)

So, I’m making a somewhat fancy tile based game engine. I’ve already got basic movement/collision for the player, which is easy. I also made a really quick raycasting function to check for collisions between a line and the level’s walls. The next step is to make lighting.

Here’s a quick example of what it’ll look like, though this version is slow as hell and not quite perfect (note some flickering when you move the flashlight slowly against a block).

WADS to move, mouse to aim the flashlight.

http://www.swfupload.com/view/108949.htm

At this point it’s basing the shape of the light on 40 or so rays cast from the player, which all stop when they hit a wall. It works, but it’s very, very slow.

I’m going to remake it using math, so it’s quicker and more accurate. Here’s the plan:

Consider the flashlight as a triangle. Find all the wall pieces (which are all squares of the same size, aligned to the tile grid) that are touching this triangle. For each square, find the key points that would affect the light beam (the two outermost points, etc). Draw the light beam based on these points.

Here’s the trouble-How do I get the list of walls touching the triangle in the first place?

Dunno how many people can help, but I’m sure someone’s got an idea.

So this is what you spent all last night agonizing over. I must admit, it looks pretty sweet. I felt like Sherlock Holmes.

Try drawing it on paper, if you haven’t done so already. It always helps me when I’m trying to work out some math. Make a list of the coordinates you know, and the angles/rotations that you know. Then see if you can put them together to find the solution.

Good luck.

Maybe this’ll help. In the picture, the triangle is the light. I can use simple raycasting to find all the cells that are touching the edges of the light. These are shown as light gray cells. What I need to find is all of the dark gray cells, that are inside the triangle but not touching an edge.

IMHO I don’t think we have the capacity to do such a thing.

The only thing I could suggest is calculate the grids crossed at the furthest position from the player, and raytrace to those grids. Then again I don’t have any experience in this (I have enough trouble with my own LOS algorithm).

Thats looks pretty good.

I think I’ve come across several ways of doing this sort of thing.

The problem in your case (with the initial method) is the number of rays you’re sending out. I once did something similar but not in actionscript. I seem to remember that I got a big speed-up by working out where the rays diverged, that is where they start hitting different tiles, and only tracking the next ray from that point. This saves a lot of looping and repeating work which is already done. I can’t remember how I did that, now. I could go and chase it up if you can’t figure it out, but that risks getting me interested in it again.

HTH.

What I’m thinking is line intersection… Check for intersections with the triangle edges and the grid (using maths), and do stuff… Keep in mind this probably won’t work well because it seems very random.

Okay here is my annotated diagram:

Let’s use the line going / (the one with the steepest gradient).

It intersects line B at 5.1, and line C at 7, meaning tiles in column 2 (indicated in red) must have a maximum less than or equal to 5.1 and less than or equal to 7. This means all tiles below the line 5.

Now look at the other line.

It intersects line B at 4.5, and line C at 4.9. This implies tiles in column 2 must have a minimum greater than or equal to 4.5 and 4.9. So all tiles above the line 5.

Obviously no tiles fit both these conditions. Hence no tiles in column 2 are highlighted.

Now look at, say, column 4.

The first line intersects D and E at 8.8 and 10.5. Tiles in this column must be below the line 8.

The other line intersects D and E at 5.3 and 5.8. Tiles must be above the line 6.

This gives the two tiles 6-7 and 7-8, as coloured dark grey in the diagram.

If haven’t taken any trig you better just leave it here, because you WILL be lost!

How were you doing it before, without intersecting the edges – walking pixels? If so going to edge intersection should speed it up immediately.

Incidentally, am I right in assuming that you’re creating a mask to show the background, or something like that?

1. Thinking about it, I think you’re right about starting by tracking the edge rays to create a triangle. You may need several similar routines, for different angles – I’m assuming the cone is up and rightwards as you’ve drawn it.
2. The idea is to have a structure which represents visible spans in degrees.
3. Start off at the player with the full range visible – 30 to 60 degrees, say.
4. read in the span, and at that y-coord, work out min and max tiles visible. Skip across these, drawing them or whatever. When you find a row of shadow-casting tiles, either remove or truncate the span, or split it into two.
5. go on to the next row of tiles until you run out of spans, leave the screen or decide you’ve gone far enough.

It may help to do the processing and drawing in separate passes. You could build up a list of angles and y-start coordinates, then somehow render that as a single filled shape – if thats how you want to do it.

I’d just like to say that this is AWESOME. It didn’t seem slow to me at all.

Yeah, alex, although it runs okay now, there’s no game running, and little to no graphics. It’s programmer graphics for now.

(haha, Wan2Play, of course I’ve taken trig…I’d have gotten lost way before this point if I hadn’t)

And Lysis, that’s helpful, and it’s more or less what I’m doing. Obviously the current “bruteforce” method is a problem; that’s why I’m remaking it in the first place. :P As far as the raytracing itself, it uses some basic linear algebra (dot products in this case) to find all the points where the line switches cells, and records all the cells that it hits. No pixel walking is used-that’s way too slow. It’s basically doing cell walking-same concept as pixel walking, but with some math added in to speed up the process exponentially.

To get the final light effect working, I have a good image of how the program flow will work, and that’s not the problem. All I’m looking for is advice on one part of it, which is just the collection of contained cells.

Actually, I’d need another thing, too. Once i’ve found all the critical points to draw to in order to form the light shape, it needs to sort them in clockwise order. I can easily get the angles to each point, since they’re used in part of the calculation anyway. Anyone know a good sorting algorithm to use here?

Alright, I got it working. Here’s the list of improvements.

1) SPEED
2) Accuracy
3) No more flickering
4) Beam fades out as it gets farther away
5) Now the light is blurred because I can, and not because I have to in order to hide the crap

CLICK ME FOR THE SEX

Wow, that is Teh Smexiness. Although something i don’t like was not seeing character. It really threw me off sometimes.

Edit:Found a tiny little glitch. In the top part of box in bottom right corner there is a little line the light gets through. Might wanna fix it might not.

Very nice indeed! Wanna Share? ^^

Here’s another build. This time there’s partial lighting for the whole map so you can see where the hell you’re going, but also to show that the lighting still works in these conditions. Also notice the slick little effect on the light beam-it starts sharp and gets more blurred as it goes. Dayum.

More fun if you click here

You should make a little bit of light reflect off the walls, to make it more realistic.

Your welcome for making it twice as complicated.

If you work from the centre (player) outwards, and always scan the row in clockwise order (left to right, for facing up), won’t the points be in clockwise order automatically? I was going with your idea of only casting the two edge rays, and then walking from one side to the other for each row. That’ll find all the contained cells, surely? I feel I must have misunderstood your question about contained cells now. I also note that your first post mentions what I covered – you’re very diplomatic. But I’m still confused as to the actual problem. I think you need 4 special-case routines, for each of the four compass points and the 45 degree surround, then you can just scan rows or columns of your map to find the walls. OK, maybe it would be easier with 8 routines…

Your last build looks bloody cool.

While I wouldn’t go as far as to back Ninjacow’s request for reflections, I think it would look better if you could light the actual wall pixels up.

Have you considered increasing your tile size as an optimisation? I know its a last resort.

Naw, I’ve got other things that I can legitimately optimize, instead of making everything even bigger than it already is…that would be cheating.

very cool 2D. can we take this as foreshadowing of a future game?

2D, I just wanted to let you know that I am in complete awe of you and wish to have your little programming babies. Also, you are all too damn smart for me. Seriously. Who knew there was a fun use for trig? NOT ME!

For the ones who wanted to know, here’s a little explanation of the concept. I left out all the heavy stuff like raycasting and all the math being used, because I don’t care and neither do you.

2D, you are my hero. This started out as your request for help, and it ends up with you teaching everyone a lesson about lighting.

Wow this is cool. I’d be interested to see if you could somehow replace the raycasting parts with vectors or similar. That would defiantly speed things up. :P

@TastyLamp: Raycasting is a highly optimised technique, how is replacing the rays with vectors going to speed it up?

It is so optimised that everything in this demo is laid out in a grid. And in games like Doom all the walls are perfectly vertical.

How hard would it be to generalize the algorithm for a non-grid based tile system with shapes other than squares? Even just having basic convex shapes in a grid-based system would add a lot of flavor to the environment.

DAMN! 2D, Great is your flash kungfu.

So many questions.. Ok.. So in your diagram, the Second wall, How do you determine to not check the Bottom left corner? Do you start at the closest wall and move out ignoring any corners already ‘darkened’ by previous walls? Or do you still check that corner, but effectively nothing is done?

I think I get how you did this.. But, is the light in the end your fully lit triangle with a dynamically created ‘light’ polygon mask? That is actually something I wanted to know because I was wondering if it is possible to dynamically create a mask polygon.

(I am thinking about creating a platform game where There is a background, action layer, and foreground layer, and I mask out the forground dynamically as the character moves behind the objects..)