Probably the best and most famous grid traversal algorithm uses a simple loop that for each iteration takes one more step in the grid. It works in both 2D and 3D.
Java code:
public boolean isFreePath(float startX, float startZ, float endX, float endZ) { // calculate the direction of the ray (linear algebra) dirX = (endX - startX); dirY = (endZ - startZ); float length = (float) Math.sqrt(dirX * dirX + dirY * dirY); dirX /= length; // normalize the direction vector dirY /= length; tDeltaX = MAP_RESOLUTION / Math.abs(dirX); // how far we must move in the ray direction before we encounter a new voxel in x-direction tDeltaY = MAP_RESOLUTION / Math.abs(dirY); // same but y-direction // start voxel coordinates x = (int) (worldCoordToMapCoord(startX)); // use your transformer function here y = (int) (worldCoordToMapCoord(startZ)); // end voxel coordinates endX1 = (int) (worldCoordToMapCoord(endX)); endY1 = (int) (worldCoordToMapCoord(endZ)); // decide which direction to start walking in stepX = (int) Math.signum(dirX); stepY = (int) Math.signum(dirY); float tMaxX, tMaxY; // calculate distance to first intersection in the voxel we start from if(dirX < 0) { tMaxX = (mapToWorld(x)-startX) / dirX; }else { tMaxX = (mapToWorld(x+1)-startX) / dirX; } if(dirY < 0) { tMaxY = (mapToWorld(y)-startY) / dirY; }else { tMaxY = (mapToWorld(y+1)-startY) / dirY; } // check if first is occupied if (isMapPositionOccupied(x, y)) // use your function here return false; boolean reachedX = false, reachedY = false; while (true) { if (tMaxX < tMaxY) { tMaxX += tDeltaX; x += stepX; } else { tMaxY += tDeltaY; y += stepY; } if (stepX > 0.0f) { if (x >= endX1) { reachedX = true; } } else if (x <= endX1) { reachedX = true; } if (stepY > 0.0f) { if (y >= endY1) { reachedY = true; } } else if (y <= endY1) { reachedY = true; } if (isMapPositionOccupied(x, y)) { return false; } if (reachedX && reachedY) { break; } } return true; } |
Here’s an applet showing it in action.
The white tiles are free, the gray tiles are blocking. The ray starts at the green dot and ends at the red dot. The gray spheres are the visited grid sections. Use leftclick to position the green dot and the right button to position the red dot.
Link to paper:
http://www.flipcode.com/archives/A%20faster%20voxel%20traversal%20algorithm%20for%20ray%20tracing.pdf
Some discussion on GameDev:
http://www.gamedev.net/community/forums/topic.asp?topic_id=385303
Implementations:
http://www.clockworkcoders.com/oglsl/rt/gpurt3.htm
http://www.devmaster.net/articles/raytracing_series/part4.php
Full source of the applet:



Awesome. I saw the paper but couldn’t quite make it work. This helps.
But I notice that the code you gave doesn’t work when I try to implement it (slight inaccuracies in the line: moves down/up too early/late). Maybe you could release the full applet source code, or at least have more code to work from. I might be able to make it work on my own, but I’ll be looking at this page for updates.
I just fixed it by myself. First I tried to decompile your code then compile it again to see how it worked, but somehow that didn’t work. Finally I just figured out what I did wrong and did it right.
If you want to see my full applet code, go ahead here to pick up the source: . It may not be the prettiest, but I think it’s better to see how to implement this function and make it work rather than see the program around it.
Hope someone besides me finds this useful.
It appears my url got swallowed by the blog software, here it is again:
http://snipt.org/moY
Sorry for responding so late. But I’ve uploaded the code now. I hope someone finds good use in it!