Log In  

Hi,
I wanted to implement line of sight for a roguelike today so I started looking up Bresanham's algorithm and ended up writing a parametric version of it because mixing conditionals and iterators makes me barf. :p

I'm posting the implementation algorithm because I'm not sure if I'm doing things in a way that is blatantly wrong for Lua, or if there's a better way. I'm very new to Lua so, well, I'm kind of clueless about how to write good Lua software. I saw a few implementations around and was wondering what's the best choice for LOS in Lua, also considering that code points are a scarce resource and between them and heat maps I feel somewhat... constrained. So, yes, what's the best line-tracing implementation, given a metric of your choice?

Here's mine. It has as only advantage a clean iterator. :)

function los(x,y,x2,y2)
 local c_x = x -- x position of the cursor along the los
 local c_y = y -- y position of the cursor along the los
 local dx -- the deltas will determine how much to move the cursor along both axes
 local dy
 local i  -- how many real pixels long the line is. Not the diagonal nor the manhattan distance
 if (x == x2) then -- do not divide by 0 ;)
  dx=0
  dy = sgn(y2-y)
  i = abs(y2-y)
 else
  dx = x2-x
  dy = y2-y
  if (abs(dx) > abs(dy)) then
   i  = abs(dx)
   dy = dy/i
   dx = sgn(dx)
  else
   i  = abs(dy)
   dx = dx/i
   dy = sgn(dy)
  end
 end
 i = i-1 -- we only need to check that the intermediate positions are not occluding, not the start nor the end 
 for c=1,i do
  c_x += dx
  c_y += dy
  -- if you want to memoize that this location is visible from x,y, do it right here before the test
  if (obstruction_at(flr(c_x+0.5),flr(c_y+0.5))) then -- there's no round, only zuul
   return false -- no LOS
  end
 end
 return true -- ok LOS
end

I ended up shadowcasting toward each of the border coords in a 11x11 bounding square, with the player in the middle. That's 42 rays. But then some walls that ought to be visible were not, so i cast 38 more rays to the 9x9 bounding box, and everything is ok.

P#20621 2016-05-15 19:00 ( Edited 2016-05-16 09:36)


[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2022-05-23 23:56:41 | 0.004s | Q:5