Line collision on a grid

BlitzMax Forums/BlitzMax Programming/Line collision on a grid

Drakim(Posted 2009) [#1]


I think the image speaks for itself, but, how do I test if a line going from location A to location B collides with any squares that are marked as solid?


matibee(Posted 2009) [#2]
First option looking at your sketch...

Look up djekstra's (sp?) line drawing algorithm. And plot the line pixel by pixel until it reaches the target point (success) or passes into a cell with a solid tile in it (fail).


jkrankie(Posted 2009) [#3]
there is an example of a* pathfinding in the samples, which looks like it might be what you are after.

Cheers
Charlie


Arowx(Posted 2009) [#4]
Matibee's suggestion of using I think means using a line drawing algorith to trace the line on the grid and check for hits.

This will work very well for fixed square by square movement test or as a quick test before you do a lower level collision test.

But the core question is in what context are you using it, collision (e.g.) bullets, line of sight, lighting shadow-casting, pathfinding?

For instance you could want line of sight information, and because your gamespace is grid based and levels are fixed then you could precalculate the visibility of each square from every another.

Or alternatly you can do somthing similar for pathfinding on fixed levels, where you store the path from every grid square to every other in a lookup table (again best for smaller level designs).


Drakim(Posted 2009) [#5]
Thanks for the replies. The thing I have in mind is indeed stuff like bullets, line of slight and lighting shadow casting. However, not path finding (for this I'd use a* pathfinding, which does as far as I know have no relation to a direct line like this at all. It's more step based)

Matibee's suggestion would perhaps work, but I still feel it's not what I'm looking for. It seems to be made more for drawing the actual line instead of checking a clear path. Sure, I could check the location of every single pixel as I draw the line, but still, that feels like the wrong way of doing it, unless I've missed something.


Arowx(Posted 2009) [#6]
It depends if your game uses a fixed square grid with integer based movement then that appoach is ideal.

Lighting and shadow casting is quite expensive although I have come acorss a raster based approach at gamedev.net.

I've had a play with it so could dig out the code if your looking for something similar?

For bullets probably best to use a simple sphere test as a first pass then go to a more detailed rectangle test or pixel based collision detection, both of which BlitzMax provides as CollideImage and CollideRect commands.

Also this is a good general games programming site


matibee(Posted 2009) [#7]
Ack! Djekstra = pathfinding, Bresenham = line drawing :) It's been a while.

Another option;

Compute the angle between the player (in the red square) and his target point. Take every external corner of the black object, and compute their angles to the player. If the target angle lies inside the range of object angles it doesn't clear it.

This method (like many others) will require some spacial division to save you from having to check every single object in the scene every time. The line drawing doesn't.

There's a condition that may cause you problems though...

If you moved the bottom black object one cell across, a line at 45 degrees would still pass between the two objects.


Dabhand(Posted 2009) [#8]
http://www.foppygames.nl/Downloads/line_of_sight.zip

Auld stylee BlitzBasic, but the meat is there and just what your after me thinks.

Dabz


Kistjes(Posted 2009) [#9]
Hi,
A while ago I made a 2D version of Portal (tiled bird-eye view).
I had to come up with a solution for exactly the same problem you describe.
My solution was:
1) Describe the contour of the wall-squares as lines and
2) Do a GetInsertionPoint() of the line with all the walls.
Works perfectly in huge maps with lot's of walls.

This method (within a TLine type) checks for insertionpoints between two lines:



I can send you my Portal code if you want...