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.
Help with shadow casting algorithm
Moderators: Bob the Hamster, marionline, SDHawk
- 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
⊕ 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
â� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
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:
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).
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.
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:
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).
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.
- sheamkennedy
- Liquid Metal Slime
- Posts: 1110
- Joined: Mon Sep 16, 2013 9:29 pm
- Location: Tama-shi, Tokyo, Japan
- Contact:
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
â� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
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.
But I plan to finish it over the next couple of weeks, as I have time, and release it for anyone to use.
- sheamkennedy
- Liquid Metal Slime
- Posts: 1110
- Joined: Mon Sep 16, 2013 9:29 pm
- Location: Tama-shi, Tokyo, Japan
- Contact:
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.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.
⊕ 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
â� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
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:
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.
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.
- sheamkennedy
- Liquid Metal Slime
- Posts: 1110
- Joined: Mon Sep 16, 2013 9:29 pm
- Location: Tama-shi, Tokyo, Japan
- Contact:
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.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:
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.
⊕ 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
â� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases