Shadowcasting (sorta like raycasting but better!)

[Codex]

Hi guys!

The past few days I've been trying to code my own shadowcasting function using this as my guide - RogueBasin Shadowcasting. I wasn't having much luck, so I just went ahead and ported it from the Ruby Version. (which was ported from a python version)

So you might ask, "What is shadowcasting and how is it different from raycasting?" Instead of typing up my own response, I think the explanation on the RogueBasin article is more than sufficient.

Raycasting - The simplest approach is to trace lines from the center out to all of the mapcells at the edge of the radius and stopping when a mapcell is blocking line of sight. The problem with this approach is that many mapcells are visited several times, most often near the starting point and more seldom at the edges.

Shadowcasting - Shadowcasting divides the Field of View calculations into eight octants and visits the mapcells in a totally different way than normal raycasting, described above. Instead of tracing lines from the center out to the edges, shadowcasting visits mapcells row by row or column by column, starting with the nearest row or column and working it's way outward.

Also there was this study done showing the different methods to light a 2D grid. (raycasting, shadowcasting, digital, permissive) It's worth a read if you've got the time!

Controls:
wasd - to move
qe - to rotate Field of View
up, down - changes the angle of vision against walls
1-8 - turns the octants on/off (works only for old version)
enter - switches explored_area mode on/off

[Inny]

It's hard to tell if the technique works with the demo, since the play field is so small. Try making the visible area larger, and the terrain more regular (solid walls and angles), so that the effect is more apparent.

[Codex]

Done.

Controls:
wasd - to move
up, down - changes the angle of vision against walls
1-8 - turns the octants on/off
enter - switches explored_area mode on/off

Would love to see someone compare some of the other LOVE raycasting methods with this. Also need to make this into a module, but probably won't attempt this until I become more proficient in using them.

Anyway, enjoy!

(ps - you will also notice that this method is more efficient in closed areas/rooms/dungeons than in large open areas.)

[Inny]

I've done a similiar one myself. I don't have a demo on hand, but the technique I used was a combination of techniques explained in this series of articles: Crafting a Vintage RPG. The idea was to iterate through every potentially visible tile to mark them as having a pending visibility (so neither hidden or shown), and then iterate across each tile again. If something was pending, then it's considered visible if the two neighboring tiles that lead to the player are visible and not opaque. So, it recursively travels down to the player. One follows the diagonal down to the axis the player is on, and the second follows its own axis down to the diagonal that the player is on.

What's cool about my implementation is that tiles could have a level of "opaqueness", so that you can see through a forest tile, but you couldn't see through multiple forest tiles. It had the effect of pulling down the viewport to a smaller area, without pulling it all the way down to just the immediate tiles next to the player.

Here's the meat of that algorithm:

Code: Select all

-- cx and cy correspond to the center, typically where the player is standing.
function TileLayer:calcVisi( cx, cy )
  local left, top, right, bottom = self:getDrawingParameters()
  for y = top, bottom do
    for x = left, right do
      self:setVisi( x, y, "dummy" )
    end
  end
  self:setVisi( cx, cy, 100 )
  for y = top, bottom do
    for x = left, right do
      self:visiCalcR( x, y, cx, cy )
    end
  end
end

function TileLayer:visiCalcR( x, y, cx, cy )
  local visi = self:getVisi( x, y )
  if visi == "dummy" then
    local nx1 = x + ((x==cx) and 0 or ((x < cx) and 1 or -1))
    local ny1 = y + ((y==cy) and 0 or ((y < cy) and 1 or -1))
    local nx2, ny2
    if (x~=cx) or (y~=cy) then
      local ax, ay = math.abs(cx - x), math.abs(cy - y)
      if ax > ay then
        nx2, ny2 = x + ((x<cx) and 1 or -1), y
      elseif ax < ay then
        nx2, ny2 = x, y + ((y<cy) and 1 or -1)
      end
    end
    if (nx1 == cx and ny1 == cy) or (nx2 == cx and ny2 == cy) then
      visi = 100
    else
      local visi1 = self:visiCalcR(nx1, ny1, cx, cy)
      local visi2 = (nx2) and self:visiCalcR(nx2, ny2, cx, cy) or 0
      visi = math.max( visi1, visi2 )
    end
    self:setVisi( x, y, visi )
  end
  return math.max(0, visi-self:getTile(x, y):opaqueness())
end

-- rest of the class omitted

I hope this gives you some neat ideas. Shadowcasting is a neat technique, and maybe you can get it performing well and doing interesting things.

[Codex]

said... >snip<

So if I understand correctly from the method you describe, it sounds like your playing connect the dots.

Also your explanation about opaqueness just gave me a great idea involving raycasting. Normal methods do something along the lines of,

------->[wall]

once ray hits wall it ends.

possibly make it so that opaque objects/walls decrease the range of raycasting like so,

-------[window]-->

You would need to give a value to walls/objects. Solid walls would get a 999999 opaque block property, vs glass window - 5 opaque property. The ray would have a range of say 50? and then just do simple math. Another way possibly, is to just make solid objects opaque property nil or false and cancel out the ray when it hits the object.

I don't think I can do something like that with shadowca- Oh wait, maybe I could! Hmmm... Might need to play with some properties though and I don't think it will work as well as raycasting for opacqueness. I won't have anything made anytime soon, but a month or two down the road maybe...

[Codex]

Uploaded two new demos with Line of sight.

Both Modes work correctly, except Mode 2 has a small problem. It has to do with love.keypressed.

So it goes like this,

Code: Select all

function love.keypressed(key)
  if key == q -- our key to rotate our FoV
    <stuff that changes the map>
    rotate_left = true  -- This causes our love.update(dt) to update the rotation

    -- These things below need to be DELAYED until our rotation is finished...  Not sure how to do that?
    octant_switch(player.dir, player.octant)
    remove_light()	
    do_fov(player.x_pos, player.y_pos, radius)	

If someone could point out how to delay something until love.update finishes what it's doing that would be awesome! I have almost nil experience in using love.update so.... not sure where to start?

(EDIT - also some feedback on the line of sight for mode 1 would be appreciated! Just say if it feels right, that's all I need to know. You won't fully understand what I'm trying to do with mode 2 until I get that problem fixed. The rotation is important so that the player realizes what's happening. )
(edit2 - forgot to mention new controls, wasd to move, qe to rotate field of view, up & down arrow keys change angle of vision against walls)

[Inny]

All of the handlers go in sequence, so if love.update is doing something, it'll finish it before love.keypressed goes. (Actually, love.keypressed goes before love.update, see: https://love2d.org/wiki/love.run ). If you want something to happen at some particular moment in love.update, and not outside of it in another handler like love.keypressed, what you can do is mark a flag, like so:

Code: Select all

function love.keypressed(k)
  if k == "q" then
    pressedQ = true
  end
end

function love.update(dt)
  -- a bunch of stuff happens
  if pressedQ then
    pressedQ = false
    -- do the stuff here that we want
  end
  -- then do all the other things
end

[wssmith04]

Awesome!