I have a several 8x8 boxes on the screen.
I have a line from a/b to c/d.

I need to find out the line intersects with the boxes.

How I'm doing that right now is by using some line intersection formula I found to check if the line passes through each segment side of each box. So for each box, checking 4 sides for intersection. This works but I'm finding it's dreadfully inefficient once you get many boxes on the screen.

Hoping someone has a snippet or can at least point me in a direction of what to explore.

I've done a little searching and see something about Bresenham's algorithm but I don't have the brain power to translate it into Pico-8 in a manner that spits out a true/false for a given 8x8 box.

Currently, I'm checking each box, which could be up to 100 or more. I'd like to think there's a way to avoid having to loop through all 100 and compare, but maybe not.

Any help is appreciated.

So I'm blanking on any super efficient way of doing it but at the very least you can partition your space.

If you order your boxes on the x axis then you'll have a set of boxes that are before a and a set of boxes after c that the line cannot possibly intersect with.

Ditto if you maintain a separate ordering of the boxes by y co-ord then you can filter your filtered list across the y axis as well which, assuming a uniform distribution of boxes and shirt line segments would rapidly reduce the number of boxes you need to check.

To be honest I didn't think the Axis Aligned Bounding Box check was that inefficient. So if you could link to to code or formulas that you are using would be good.

I did some more searching here on the forum, this time for "line of sight" and found the cart linked below. It doesn't load in the browser but it seems to work pretty well once I pulled it down. I'm seeing how I can tweak and use it.

https://www.lexaloffle.com/bbs/?tid=2183

@mole5000 - Thanks for the ideas. I'll keep that in mind as other methods keep failing.

Here is the code I was using that I felt became inefficient. I borrowed it from somewhere or possibly transposed it from a JS example.

The intersect_shape is my own method that simply loops through an array of points of a shape (in this case a square). I'm checking the intersection for each side. The ccw and intersect functions are the ones I found elsewhere.

function ccw(l1s,l1e,l2s)
    return (l2s.y-l1s.y) * (l1e.x-l1s.x) > (l1e.y-l1s.y) * (l2s.x-l1s.x)
end

function intersect(l1s,l1e, l2s,l2e) 
    return ccw(l1s,l2s,l2e) != ccw(l1e,l2s,l2e) and ccw(l1s,l1e,l2s) != ccw(l1s,l1e,l2e)
end

function intersect_shape(ls,le, shape)
    local limit=#shape

    for thispt=1,limit do
        local nextpt=thispt+1
        if nextpt>limit then nextpt=1 end

        if intersect(
                {x=ls.x,y=ls.y},{x=le.x,y=le.y}, 
                {x=shape[thispt].x,y=shape[thispt].y},{x=shape[nextpt].x,y=shape[nextpt].y}
        ) then
            return true
        end
    end

    return false
end

And this code does work, returning the results I expect. It just seems to slow things down once I start looping through 100+ squares, each with 4 sides. That's a lot of math happening very quick so it makes sense to me why it could slow things down. So it's not that this code is wrong but I'm clearly using it inefficiently.

You could draw the boxes to screen and then use pget to sample points along the line.

(You could then continue drawing pretty graphics over top.)

It's not as absurd as it seems, but it requires you to do the collision check during your draw loop which is less then ideal.

I haven't had a chance to have a deep think about your code yet but two things stand out.

It looks like you've written a general line polygon intersection test? For an axis aligned box you don't need the full power of a the general case - you are just looking to see if you line crosses the 2 vertical and 2 horizontal lines that make up the box. That is to say you are trying to solve the equation of the line for certain values of x and y when your line crosses the vertical and horizontal lines the define your box.

To go back to basics
The equation is y=mx+c where m is the gradient and c is offset from the origin when x = 0.

So if a 8x8 box is at 12,17 and you have a line of gradient=0.5 and c=1 then you are looking to solve the line equation for x = 12 and 20 and y = 17 and 25

y=12*0.5+1=7
y=20*0.5+1=11

x=(17-1)/0.5=32
x=(25-1)/0.5=48

All you need to do is check if either of the y values are within the vertical bounds of the box or either of the x values are within the horizontal bounds of the box.

In this case all of the intersection points fall outside the bounds of the box. If the gradient of the line was 1 instead then the intersection points would hit the bounds of the box.

y=12*1+1=13
y=20*1+1=21

x=(17-1)/1=16
x=(25-1)/1=24

y: 17<21<25 x: 12<16<20

This should allow you to write a much simpler function

In terms of micro optimizations you code creates loads of tables - in particular the line {x=ls.x,y=ls.y},{x=le.x,y=le.y}, seems to be pointless as you can simply pass in ls and le - same with the next line and the shape points.

Blimey, a diagram would make this much easier to explain.

Thanks for all the code and insight.

I spent most of yesterday getting my head around the algorithm found in the cart linked below. It seems to work very well and doesn't create the slowdown I had with other functions (above).

I'm going to submit a demo cart tonight with how I'm using it.

https://www.lexaloffle.com/bbs/?tid=2183

Line grid intersection demo

Cart File | Forum Post |

	More cartridges by morningtoast

More Cartridges [View All]

 

Line grid intersection demo

by morningtoast

Cart #41652 | 2017-06-16 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

Here is a demo cart of the algorithm I used and is working great. See the link above for the original cart that I borrowed it from. I tried to simply the implementation so others can take it and integrate with their game easily. I don't understand all of it, but it works :)