Calculating Line Intersections without looping

Game Mechanics
#1

I’ve got a game I’m working on that’s tile based. I have a bunch of tiles on the map and a line and I’m trying to figure out how to determine what tiles the line is passing through without looping through all tiles or all of the points on the line. I’m sure there’s a way to do with just using math - but I haven’t figured it out.

I know the starting point of the line and the ending point of the line so I also know the slope, and I know the size of each tile. The tiles are stored in a 2D array that corresponds with their x/y position in the map.

Does anybody have any suggestions on how I might figure this out using math?

#2

Do you mean something like Bresenham’s line algorithm which is commonly used in graphics to draw lines? LibGDX has a Bresenham2 implementation here and I think the concept should stay the same even if you’re not using the engine.

#3

Thank you, this is exactly what I meant.

#4

You were looking for a line drawing algorithm?

#5

I guess I was, I was trying to figure out what tiles the line was passing through and prevent it from passing through certain ones. I didn’t know how to label what I was looking for though.

#6

Bresenham’s does not give you ALL the tiles the line intersects. It’s actually quite a challenge. I solved it with a neat and fast algorithm some years ago, posted it on JGO, you might be able to find it - I’m in my phone, so you have to do the digging yourself :slight_smile:

#7