[SOLVED] Collision Line (or something similar)

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
CRxTRDude
Prole
Posts: 41
Joined: Sun Dec 15, 2013 3:03 am
Location: Some island in the archipelago

[SOLVED] Collision Line (or something similar)

Post by CRxTRDude »

:shock:

I know you guys are wondering why i'm even posing this, but let me just say it anyway.

I came across this function before in GM (you gyus know what i mean...) called CollisionLine which casts an imaginary line "to check whether any object collides with a given line." I wanted to know how it worked, so i searched the internets for how that is really implemented and found out it's proprietary, however, one of the forumists in GMC said that it might have to do with Line-Line intersection.

I don't know if it's possible for LOVE to have something like this, but it could be beneficial for people using this for platformer enemy LOS (i might be even able to use it for that purpose as well). That's the reason i asked about this, i'm technically not good in math, but i'm good in some logic and also observing other people's work (and code).

EDIT: I already made my own crude LOS with Pythagorean theorem and y checks. Nevertheless, this is still useful to people who wanted to make use of the Liang-Barsky Indeces for a more powerful LOC kick (thanks kikito!). I posted my implementation for my own checks.
Last edited by CRxTRDude on Thu Dec 26, 2013 4:55 am, edited 3 times in total.
~ CRxTRDude || Will be out of touch for a wee longer than expected. Will keep in touch with soon enough. Sorry bout that.
User avatar
veethree
Inner party member
Posts: 877
Joined: Sat Dec 10, 2011 7:18 pm

Re: Collision Line (or something similar)

Post by veethree »

I think you're talking about ray casting. I have no experience with that, So this is about where my input ends.
User avatar
CRxTRDude
Prole
Posts: 41
Joined: Sun Dec 15, 2013 3:03 am
Location: Some island in the archipelago

Re: Collision Line (or something similar)

Post by CRxTRDude »

I think that's what i also saw in some forums and internets searching... Might check them out one by oneand see what works (probably later, it's nighttime from where i'm at, goota get some sleep first)
~ CRxTRDude || Will be out of touch for a wee longer than expected. Will keep in touch with soon enough. Sorry bout that.
bekey
Party member
Posts: 255
Joined: Tue Sep 03, 2013 6:27 pm

[]

Post by bekey »

-snip-
Last edited by bekey on Fri Jan 24, 2014 1:39 am, edited 1 time in total.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Collision Line (or something similar)

Post by Roland_Yonaba »

Love does not have such af functin built-in, but it is very easy to implement.
You can take a look at Kikito's brensenham. It is dead simple, clean and easy to use. I also have an implementation of LOS tight into my pathfinding library.

Added to that, here is a very nice article explaining the logic of bresenham line marching algorithm, and another one which is worth reading as it provide different flavours of raycasting implementations, while plotting their differences. There's is also this paper, entitled: "A fast voxel traversal algorithm for raytracing" that can serve as reference for pseudocode :direct link.

And, just for the record, RogueBasin has the best collection of articles on the topic, in my humble opinion.

Hope this helps.
User avatar
veethree
Inner party member
Posts: 877
Joined: Sat Dec 10, 2011 7:18 pm

Re: Collision Line (or something similar)

Post by veethree »

Roland_Yonaba wrote:You can take a look at Kikito's brensenham. It is dead simple, clean and easy to use.
I can vouch for that. I implemented a very simple LOS based lighting system with that within like 5 minutes of finding out about it. Thanks for that Roland_Yonaba.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Collision Line (or something similar)

Post by Roland_Yonaba »

veethree wrote:
Roland_Yonaba wrote:You can take a look at Kikito's brensenham. It is dead simple, clean and easy to use.
I can vouch for that. I implemented a very simple LOS based lighting system with that within like 5 minutes of finding out about it. Thanks for that Roland_Yonaba.
Awesome. Oh well, Kikito's the only one who should be thanked for that ;)
User avatar
CRxTRDude
Prole
Posts: 41
Joined: Sun Dec 15, 2013 3:03 am
Location: Some island in the archipelago

Re: Collision Line (or something similar)

Post by CRxTRDude »

Roland_Yonaba wrote:You can take a look at Kikito's brensenham. It is dead simple, clean and easy to use.
I didn't know kikito had something like this ... (I use his gamera and anim8 for the platformer the recent time) Thanks for that Yonaba!
Side quote: Taht was the 2nd time you helped so far ;)

EDIT:to veetree, how did you use bresenham for that lighting? I'm curious about that...
~ CRxTRDude || Will be out of touch for a wee longer than expected. Will keep in touch with soon enough. Sorry bout that.
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Collision Line (or something similar)

Post by kikito »

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)

Image

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.
Last edited by kikito on Mon Dec 23, 2013 9:51 am, edited 3 times in total.
When I write def I mean function.
User avatar
CRxTRDude
Prole
Posts: 41
Joined: Sun Dec 15, 2013 3:03 am
Location: Some island in the archipelago

Re: Collision Line (or something similar)

Post by CRxTRDude »

Well, I'm using ATL based solid collision, probably my enemy and player is bounding boxes, i think...
I'll check these out...

Your libs are so helpful for the platformer i'm making... Thanks a bunch!

BTW, how do you implement this for LOS?
~ CRxTRDude || Will be out of touch for a wee longer than expected. Will keep in touch with soon enough. Sorry bout that.
Post Reply

Who is online

Users browsing this forum: Ahrefs [Bot], Bing [Bot] and 3 guests