Oh hey! I am glad that my libs are helping out.
Bresenham is good when you have a grid to "parse cells". I guess you could use bresenham to go pixel-by-pixel, but that would not be very fast.
It is also a "beautiful line drawer". It draws only one-cell lines, even when the line touches several cells. This means that not all the cells touched by the line are actually activated by it (this makes it not ideal for things like line-of-sight or shooting. They appear to "miss cells"). If you want to use it for that, you would have to use a "supercover" version of bresenham (unfortunately bresenham.lua does not have that)
If your objects are bounding boxes, there is a nice algorithm to intersect them with a segment called the
Liang-Barsky algorithm. I happen to have a Lua implementation handy:
Code: Select all
local function getLiangBarskyIndices(l,t,w,h, x1,y1,x2,y2)
local t0, t1 = 0, 1
local dx, dy = x2-x1, y2-y1
local p, q, r
for side = 1,4 do
if side == 1 then p,q = -dx, x1 - l
elseif side == 2 then p,q = dx, l + w - x1
elseif side == 3 then p,q = -dy, y1 - t
else p,q = dy, t + h - y1
end
if p == 0 then
if q < 0 then return nil end
else
r = q / p
if p < 0 then
if r > t1 then return nil
elseif r > t0 then t0 = r
end
else -- p > 0
if r < t0 then return nil
elseif r < t1 then t1 = r
end
end
end
end
return t0, t1
end
The parameters are:
* l,t,w,h: a bounding box (left, top, width, height)
* x1,y1,x2,y2: the starting and ending points of the line that is being tested for collision.
The result is:
* nil if the line does not touch the box
* two numbers (t0,t1) between 0 and 1 indicating the point in the line where the two intersections with the box occur. 0 means the beginning of the line, 1 means the end.
So if you have several objects with properties l,t,w,h, you can get the intersections in order by sorting by t0:
Code: Select all
local function sortByT0(a,b) return a.t0 < b.t0 end
local function getCollisionLine(objects, x1,y1,x2,y2)
local collisions, len = {},0
for i=1, #objects do
local obj = objects[i]
local t0,_ = getLiangBarskyIndices(obj.l, obj.t, obj.w, obj.h, x1,y1,x2,y2)
if t0 then
len = len + 1
collisions[len] = {obj=obj, t0=t0}
end
end
table.sort(collisions, sortByT0)
local result = {}
for i=1,len do result[i] = collisions[i].obj end
return result
end
This function, given a list (array-like table) of objects and a segment, returns the list (array-like) objects that collide with that segment, in order (the ones near to the beginning of the line come first).
I am using something similar in
the new version of bump.lua, which I hope to release very soon.
