Collision detection in grid map?

Question

There is a grid map (tile map). Among all the tiles, some are free (empty) and some are obstacles. Now if I randomly pick to empty tiles (tile A and tile B) and draw a line segment across them. What is the fastest algorithm to tell whether this line segment is collision free to any obstacles or not? (In the figure below: Red tiles are obstacles, Line_2 is collision free, Line_1 is not)

Currently, what I am doing is to do a voxel traversal from A to B and check the traversed tiles whether it contains an obstacle or not?

But is there better solution?

Answer 1

I believe, the speed of algorithm depends of the size of the field and the amount of obstacles. Your way is excellent if the field is full of obstacles.

Another way is finding the points of intersection of the ray and each side of the tile.

I think this way is excellent if you have a few tiles and a lot of free space.

UPD: This method should be optimized by exclusion calculations for the "back sides" of tiles for all the set. It will decrease amount of calculations and speed up the routine.

Finally, I believe, you can use both algorithms in your code. You can select a method by approximation the "density" of the map.