Monocle: Monaco-style line of sight engine

[Gravy]

Hi all,

Attached is my implementation of Monaco's vector line of sight algorithm, as described here: https://www.facebook.com/notes/monaco/l ... 1301481995

The demo doesn't work perfectly, as there is still a bug or two. Specifically, the line of sight will mess up or sometimes crash when the player's x or y value is an integer. There are also lots of optimizations I could do to speed up the algorithm, such as those described in the link. And my code is kind of a mess.

I tried to write this to be nearly plug and play with any tile-based game. It requires an X and Y value, and a two-dimensional array filled with tables that have a 'solid' attribute that is true or false (All the border tiles must be solid).

This is still a long way from perfection, but I welcome any feedback/suggestions!

EDIT: Also be sure to turn off Monocle and turn on debug mode to see how it works.

[micha]

Looks great. I might use this in my project.

[Germanunkol]

I fiddled with your code a little.

First of all: Well done!
I thought that because you use triangles I might get "overlapping problems" when I draw the shadows transparent, but it works like a charm so far!

I've had Problems using multiple light sources.
I did the following:

Code: Select all

lights = require('monocle')
lights2 = require('monocle')

And then later called the draw function for both lights, with different places. Sometimes (when I move the player around) it crashes saying:

Code: Select all

Error: monocle.lua:227: bad argument #1 to 'unpack' (table expected, got boolean)
stack traceback:
	[C]: in function 'unpack'
	monocle.lua:227: in function 'draw_triangles'
	monocle.lua:25: in function 'draw'
	main.lua:45: in function 'draw'
	[string "boot.lua"]:410: in function <[string "boot.lua"]:373>
	[C]: in function 'xpcall'

Also, I've managed to make it work easily without canvases... why the trouble?

[Gravy]

I think the crash you're getting is the issue with integer-valued player coordinates. Basically, when the cast rays hit another edge, that edge is split into two. When the point it hits on the edge is an endpoint, it messes up. This is something I can (and will) fix with some additional logic, but a work-around is to prevent the player's coordinates from ever being exactly integer-valued.

I updated the demo above. Can you try to crash it? I haven't been able to. Note that it will crash or mess up right away if you start the player at integer-valued coordinates. If this fix doesn't work, then there is another bug. This thing is sort of a beast, so I won't be surprised if there are more pesky edge cases

[Germanunkol]

Hm, almost there. That tipp with the non-integer values was great, it works. But I'm still getting some issues around the edges. For example,rendering a light at (6.999999996, 11.940000005) crashes. (Can you confirm?) The x value is probably too close to 7, so there's some rounding issues?

I think the lib should internally modify the coordinates it gets so that it doesn't crash. Doing it externally really spoils the code.

It's looking great with 4 lights rendered close to each other Very nice!

I removed the need for canvases for the lights altogether... So this can easily be used without shader support.

[Gravy]

I think I figured out how to fix this without needing to change the x and y values manually. Basically, the projected ray should ignore edges it hits when the intersection point is the clockwise edge, and when it hits the counterclockwise edge, it should just set that edge as the next instead of splitting it. I'll post a new version with the fix in the next couple of days.

[Ranguna259]

WOW, if you put this into a lib I'm totally gonna use it

Stuff like:

Code: Select all

updateShadows()

or something alike

Keep up the good work

[clofresh]

Wow, that's pretty awesome! Depending on your perspective, you could make the projections look like shadows or really tall buildings.

[Gravy]

I tried implementing my fix for the integer-valued coordinates, but it ended up being more trouble than it's worth, so I just put the rounding logic into the Monocle module. However, I'm still getting random crashes once in a while and am having trouble reproducing it.

Attached is the latest version. If anyone figures out how to reproduce the crash, let me know and I will fix. Aside from that, the only changes I want to make are the optimizations mentioned in the link above.

Does anyone know how to do a simple Gaussian blur on the Monocle canvas? I think that will make the shadows look much better.

EDIT: I think I figured out the problem. Whenever a ray cast from the player hits a corner precisely, it messes up a bit. I have some logic to deal with this, but because of floating-point weirdness, it's not working.

[Germanunkol]

Do you have a github account, Gravy?
Would you mind making a github repository out of this? It would be easier to get the code and add to it... And I'd like to make a branch which does not use canvases, which I could then simply add to your repository.