Help with shadow casting algorithm

Make games! Discuss those games here.

Moderators: Bob the Hamster, marionline, SDHawk

Post Reply
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Help with shadow casting algorithm

Post by sheamkennedy »

I have just recently stumbled upon some algorithms for shadow casting in some other programming languages. I'm struggling to grasp how this would be coded or what exactly the algorithm is doing.

If you're wondering what shadow casting is see this video:
http://www.youtube.com/watch?v=kw47JxfMlzs

If you want to see some basic algorithm codes:
http://roguebasin.roguelikedevelopment. ... _Algorithm

If anyone knows how to do something like this please share. It would be awesome to if an algorithm could be made for pixel-by-pixel shadowcasting like in the video but even a tile-by-tile shadow casting would be great and probably easier to implement.

Or if anyone can explain the algorithm that might be just as useful.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

Line of sight and shadow casting aka field of view are two different things. LoS determines whether two points (eg the player and a guard) can see each other. FoV determines which points/tiles are visible from a single point. LoS and FoV may also take into account the direction you're facing. If you want a tile-based FoV you could use a LoS algorithm to calculate a FoV by just running it repeatedly for every tile on the screen, but that's really inefficient, and the OHR's script interpreter is far too slow for it to be feasible. Still, the two are very closely related, and if you create a game that uses separate LoS and FoV algorithms you want to try and ensure that they agree on visibility.

Also, there are FoV algorithms (prehaps they should be called something else; I'll call it "light casting") which try to determine lit squares rather than visible squares. Then you place a light source at the player, maybe more throughout the level, and possibly allow light to bounce around corners. In fact you may just ignore walls and get something very simple.

Breshenham's Line algorithm is for drawing lines, and is one of those things that's so obvious once you understand it that you wonder why it's named after someone. I would avoid the Wikipedia article, instead look at this figure from it:

Image

Naturally, drawing a straight line is pretty easy, just involving some simple math. Anyway Breshenham's algorithm is used for LoS by tracing a line from one point to the other and checking whether each tile on the line contains an obstruction. Notice that it allows sight past two obstructions that are diagonally adjacent. This is fine if your obstacles are barrels and you're meant to be able to see diagonally past them, but not if they're cubes of concrete. Also, it isn't relevant for non-tile based LoS at all, such as in that video you posted.

Although you are looking for FoV and not LoS, an full-featured implementation of Bresenham's is available at http://rpg.hamsterrepublic.com/ohrrpgce ... e_of_sight which also links to a less scary simplified version.


Drawing pixel-based shadow casting is possible in theory in the OHR using slices, but again the script interpreter is far far too slow for it to be practical. However you could draw larger chunks, like quarter tile 10x10 black squares. That could be fast enough, and you can use a tile layer for it rather than slices.

Also, you could instead use Cyberdogs/C-Dogs-style shadow casting, which draws shadows only at 45 degree angles, and is very fast to calculate. In the following screenshot you can see the shadows are blocky because they're tile based, but it would be easy to draw sharp diagonal shadow edges instead. I've always wanted to make an OHR game which does this, or even a full Cyberdogs clone (they're both great games).

Image

There are a couple OHR games that do some kind of (tile-based) "light casting". The earliest that I know of is Project `C'. In that case you can see through walls. Ortega Colonies did something where light originates from the player and other sources and can flow around corners. Scripts for that are available. The Dungeons of Koh-Lah'B is another example. I know there was at least one more. However I don't think I've ever seen an OHR game with real FoV; Ortega Colonies is the only one I know of that even takes walls into account.
(On the other hand there are quite a few OHR games that do LoS.)

The Roguebasin article on FoV has a bunch of different algorithms of course, but translating other languages to Hamsterspeak can be surprisingly difficult.
Last edited by TMC on Sun Dec 22, 2013 6:12 am, edited 1 time in total.
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

Thanks, that should be enough resources to help me out for now. I'll take a better look at them after Christmas and follow up with any further inquiries.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

After writing that post here, I decided to actually implement the shadow casting algorithm inspired by Cyberdogs which I mentioned. I had wanted to put together a (mere tech) demo to join in with the spirit of the impressive games released for Christmas. Well, that didn't work out. It turned out to be more difficult than I thought (it took me hours to work out all the details on paper; it's not so simple if you're looking at it the wrong way). I've since been distracted working on the engine.

But I plan to finish it over the next couple of weeks, as I have time, and release it for anyone to use.
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

TMC wrote:After writing that post here, I decided to actually implement the shadow casting algorithm inspired by Cyberdogs which I mentioned. I had wanted to put together a (mere tech) demo to join in with the spirit of the impressive games released for Christmas. Well, that didn't work out. It turned out to be more difficult than I thought (it took me hours to work out all the details on paper; it's not so simple if you're looking at it the wrong way). I've since been distracted working on the engine.

But I plan to finish it over the next couple of weeks, as I have time, and release it for anyone to use.
That would be awesome. Figuring this out is actually quite a struggle. Specifically working out how to cast shadows on curved objects (cylinder pillars) separately from ridged edged objects (square boxes) is really inhibiting me.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

Well, I wasn't planning on supporting round columns at first, but since you've got them, I guess I should; I think it won't be more complex, just more shadow tiles and drawing patterns. But really it's only a difference of a few pixels for the position of the shadow, assuming the columns are 20 pixels wide and drawn in this sort of perspective:

Image

Top: 45 and 27 degree shadows for a square column.
Bottom left & centre: shadows on a round column.
Bottom right: shadows shifted to match the round column.
Last edited by TMC on Thu Jan 02, 2014 10:08 am, edited 3 times in total.
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

TMC wrote:Well, I wasn't planning on supporting round columns at first, but since you've got them, I guess I should; I think it won't be more complex, just more shadow tiles and drawing patterns. But really it's only a difference of a few pixels for the position of the shadow, assuming the columns are 20 pixels wide and drawn in this sort of perspective:

Image

Top: 45 and 27 degree shadows for a square column.
Bottom left & centre: shadows on a round column.
Bottom right: shadows shifted to match the round column.
Oh of course, that shouldn't have been so difficult to grasp. Guess thats what happens when I spend too much time thinking about something in my head rather than drawing it out on paper.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

Heh. In my case the boundary to understanding it was actually too much focus on drawing out what the results should be on paper.
Post Reply