Grid Traversal

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.
 


Hi There


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:

import java.awt.*;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.applet.*;
 
public class GTApplet extends Applet implements MouseListener,
		MouseMotionListener
{
	enum mapNotations
	{
		FREE, OCCUPIED, BOOKED, RESERVED
	};
 
	private static final int GRID_PAINT_SIZE = 50;
 
	private static final int MAP_RESOLUTION = GRID_PAINT_SIZE;
 
	private static final int MAP_SIZE = 4 * 2;
 
	private final mapNotations[][] map = new mapNotations[MAP_SIZE][MAP_SIZE];
 
	private final int[][] markedMap = new int[MAP_SIZE][MAP_SIZE];
 
	// Specify variables that will be needed everywhere, anytime here
	// The font variable
	Font bigFont, smallFont, smallestFont;
 
	Color bgColor;
	Color gridLineColor;
	Color gridOccupiedColor;
	Color startColor;
	Color endColor;
	Color helperLineColor;
	Color markerColor;
	Color textColor;
 
	int startX = 50, startY = 50, endX = 50, endY = 50;
 
	int markerDiameter = 6;
	int mapMarkerDiameter = 26;
 
	boolean isFreePath = false;
 
	public void init()
	{
		// init the map
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++) 			{ 				if (Math.random() > 0.2f)
				{
					map[x][y] = mapNotations.FREE;
				} else
				{
					map[x][y] = mapNotations.OCCUPIED;
				}
			}
		}
 
		bigFont = new Font("Arial", Font.BOLD, 16);
		bigFont = new Font("Arial", Font.BOLD, 12);
		smallestFont = new Font("Calibri", Font.PLAIN, 10);
 
		gridLineColor = Color.DARK_GRAY;
		gridOccupiedColor = Color.LIGHT_GRAY;
		startColor = Color.green;
		endColor = Color.red;
		helperLineColor = Color.black;
		markerColor = Color.gray;
		textColor = Color.DARK_GRAY;
 
		bgColor = new Color(230, 231, 232);
 
		setBackground(bgColor);
 
		addMouseListener(this);
		addMouseMotionListener(this);
 
	}
 
	public void mouseEntered(MouseEvent e)
	{
		// called when the pointer enters the applet's rectangular area
	}
 
	public void mouseExited(MouseEvent e)
	{
		// called when the pointer leaves the applet's rectangular area
	}
 
	public void mouseClicked(MouseEvent e)
	{
		// called after a press and release of a mouse button
		// with no motion in between
		// (If the user presses, drags, and then releases, there will be
		// no click event generated.)
	}
 
	public void mousePressed(MouseEvent e)
	{ // called after a button is pressed down
		if (e.getButton() == MouseEvent.BUTTON1)
		{
			startX = e.getX();
			startY = e.getY();
		} else
		{
			endX = e.getX();
			endY = e.getY();
		}
 
		resetMarkedMap();
		isFreePath = isFreePath(startX, startY, endX, endY);
 
		repaint();
		// "Consume" the event so it won't be processed in the
		// default manner by the source which generated it.
		e.consume();
	}
 
	public void mouseReleased(MouseEvent e)
	{ // called after a button is released
	//        repaint();
		e.consume();
	}
 
	public void mouseMoved(MouseEvent e)
	{ // called during motion when no buttons are down
	//        repaint();
		e.consume();
	}
 
	public void mouseDragged(MouseEvent e)
	{ // called during motion with buttons down
	//        repaint();
		e.consume();
	}
 
	public void stop()
	{
	}
 
	// just some simple and rude drawing
	public void paint(Graphics g)
	{
		g.setColor(gridLineColor);
		for (int x = 0; x < MAP_SIZE + 1; x++)
			g.drawLine(x * GRID_PAINT_SIZE, 0, x * GRID_PAINT_SIZE, MAP_SIZE
					* GRID_PAINT_SIZE);
 
		for (int y = 0; y < MAP_SIZE + 1; y++)
			g.drawLine(0, y * GRID_PAINT_SIZE, MAP_SIZE * GRID_PAINT_SIZE, y
					* GRID_PAINT_SIZE);
 
		g.setColor(gridOccupiedColor);
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++)
			{
				if (map[x][y] == mapNotations.OCCUPIED)
				{
					g.fillRect(x * GRID_PAINT_SIZE + 1,
							y * GRID_PAINT_SIZE + 1, GRID_PAINT_SIZE - 1,
							GRID_PAINT_SIZE - 1);
				}
			}
		}
 
		g.setColor(textColor);
 
		g.setFont(smallestFont);
 
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++)
			{
				g.drawString("(" + x + "," + y + ")", x * GRID_PAINT_SIZE + 2,
						y * GRID_PAINT_SIZE + 10);
			}
		}
 
		g.setFont(bigFont);
		g.drawString("Start: (" + startX + "," + startY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 30 + 10);
		g.drawString("End: (" + endX + "," + endY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 48 + 10);
		g.drawString("Is free path: " + isFreePath, 16, MAP_SIZE
				* GRID_PAINT_SIZE + 48 + 18 + 10);
		g.setFont(smallFont);
		g.drawString("Start (map coords): (" + sx + "," + sy + ")", 16,
				MAP_SIZE * GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 0 * 14);
		g.drawString("End (map coords): (" + endX1 + "," + endY1 + ")", 16,
				MAP_SIZE * GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 1 * 14);
		g.drawString("Step (map coords): (" + stepX + "," + stepY + ")", 16,
				MAP_SIZE * GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 2 * 14);
		g.drawString("Dir: (" + dirX + "," + dirY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 3 * 14);
		g.drawString("tDelta: (" + tDeltaX + "," + tDeltaY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 4 * 14);
		g.drawString("sTMax: (" + sTMaxX + "," + sTMaxY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 5 * 14);
 
		g.setColor(markerColor);
 
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++)
			{
				if (markedMap[x][y] == 1)
				{
					g.fillOval(x * GRID_PAINT_SIZE - mapMarkerDiameter / 2
							+ GRID_PAINT_SIZE / 2, y * GRID_PAINT_SIZE
							- mapMarkerDiameter / 2 + GRID_PAINT_SIZE / 2,
							mapMarkerDiameter, mapMarkerDiameter);
				}
			}
		}
 
		g.setColor(startColor);
		// draw start and end markers
		g.drawOval(startX - markerDiameter / 2, startY - markerDiameter / 2,
				markerDiameter, markerDiameter);
 
		g.setColor(endColor);
		// draw start and end markers
		g.drawOval(endX - markerDiameter / 2, endY - markerDiameter / 2,
				markerDiameter, markerDiameter);
 
		g.setColor(helperLineColor);
		g.drawLine(startX, startY, endX, endY);
	}
 
	public void resetMarkedMap()
	{
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++)
			{
				markedMap[x][y] = 0;
			}
		}
	}
 
	int sx, sy, x, y, endX1, endY1, stepX, stepY;
	float tDeltaX, tDeltaY;
	float dirX, dirY;
	float sTMaxX, sTMaxY;
 
	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
		sx = (int) (worldCoordToMapCoord(startX));  // use your transformer function here
		sy = (int) (worldCoordToMapCoord(startZ));
 
		// end voxel coordinates
		endX1 = (int) (worldCoordToMapCoord(endX));
		endY1 = (int) (worldCoordToMapCoord(endZ));
 
		x = sx;
		y = sy;
 
		// 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;
		}
 
		sTMaxX = tMaxX;
		sTMaxY = tMaxY;
 
		// 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;
	}
 
	private float mapToWorld(int coord)
	{
		return coord*MAP_RESOLUTION;
	}
 
	private float worldCoordToMapCoord(float coord)
	{
		return coord / MAP_RESOLUTION;
	}
 
	private boolean isMapPositionOccupied(int x, int y)
	{
		if(x < 0 || y < 0)
			return true; 
 
		// save this for debug use
		markedMap[x][y] = 1;
 
		return map[x][y] == mapNotations.OCCUPIED;
	}
}
Be Sociable, Share!

4 thoughts on “Grid Traversal

  1. Durnus

    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.

  2. Durnus

    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.

  3. admin Post author

    Sorry for responding so late. But I’ve uploaded the code now. I hope someone finds good use in it!

Comments are closed.