helloworld922

This is a short preview of 2D grid accelerator structure. It's primary use is for speeding up collision detection.

The general concept is this:

The full 2D space is partitioned into individual grid (the black lines). Each shape added to the grid has some minimal aligned bounding box (pictured as green outlines). Every grid square which overlaps this bounding box has the shape's reference added to it's list of shapes (red background). Now to check for collisions, you just take one object, find all objects which are in the same grids it is, and then perform the collision detection.

grid.jpg

There are a few issues with this method:

If there are lots of objects of very different sizes, it's impossible to choose a reasonable grid size. Too large a grid size, then their will be a lot of small objects in each grid. Too small a grid size and the large object gets added to too many grids. Either way the time it takes to check for a collision and modifying the location of shapes increases. The solution is to use a hierarchical grid, but for the applications I had in mind it's not a big issue.

Another issue is moving the shapes. There are two solutions: Before moving a shape, remove it from the structure, move it, then re-add it. Another solution is to rebuild the whole structure after moving shapes. Both of these methods have their pros and cons. If there are a lot of moving objects, the second method is beneficial. Otherwise it's better to use the first. However, in addition to performance, there is the usability factor. For both of these methods it's easy to forget to both rebuild or remove/re-add shapes. Any suggestions on how to remedy this are welcome.

Here's the current code:

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
 
/**
 * A simple 2D grid accelerator structure
 * 
 */
public class Grid
{
	private double tile_width;
	private double tile_height;
	private ArrayList<ArrayList<BoundedShape>> data;
 
	private int x_tiles;
	private int y_tiles;
 
	public Grid(int x_tiles, int y_tiles, double tile_width, double tile_height)
	{
		setX_tiles(x_tiles);
		setY_tiles(y_tiles);
		setTile_height(tile_height);
		setTile_width(tile_width);
		data = new ArrayList<ArrayList<BoundedShape>>();
		for (int i = 0; i < x_tiles; ++i)
		{
			for (int j = 0; j < y_tiles; ++j)
			{
				data.add(new ArrayList<BoundedShape>());
			}
		}
	}
 
	/**
	 * @return the tile_width
	 */
	public double getTile_width()
	{
		return tile_width;
	}
 
	public double getWidth()
	{
		return tile_width * x_tiles;
	}
 
	public double getHeight()
	{
		return tile_height * y_tiles;
	}
 
	/**
	 * @param tile_width
	 *            the tile_width to set
	 */
	private void setTile_width(double tile_width)
	{
		this.tile_width = tile_width;
	}
 
	/**
	 * @return the tile_height
	 */
	public double getTile_height()
	{
		return tile_height;
	}
 
	/**
	 * @param tile_height
	 *            the tile_height to set
	 */
	private void setTile_height(double tile_height)
	{
		this.tile_height = tile_height;
	}
 
	/**
	 * @return the width
	 */
	public int getX_tiles()
	{
		return x_tiles;
	}
 
	/**
	 * @param width
	 *            the width to set
	 */
	private void setX_tiles(int width)
	{
		x_tiles = width;
	}
 
	/**
	 * @return the height
	 */
	public int getY_tiles()
	{
		return y_tiles;
	}
 
	/**
	 * @param height
	 *            the height to set
	 */
	private void setY_tiles(int height)
	{
		y_tiles = height;
	}
 
	private ArrayList<BoundedShape> getTile(int x, int y)
	{
		if (x < 0)
		{
			x = 0;
		}
		else if (x > x_tiles)
		{
			x = x_tiles;
		}
		if (y < 0)
		{
			y = 0;
		}
		else if (y > y_tiles)
		{
			y = y_tiles;
		}
		return data.get(x + y * x_tiles);
	}
 
	private ArrayList<ArrayList<BoundedShape>> getTiles(BoundedShape s)
	{
		ArrayList<ArrayList<BoundedShape>> tiles = new ArrayList<ArrayList<BoundedShape>>();
		Rectangle2D.Double bounds = s.getBounds();
		for (int x = (int) (bounds.x / tile_width); x <= (int) ((bounds.x + bounds.width) / tile_width); ++x)
		{
			for (int y = (int) (bounds.y / tile_height); y <= (int) ((bounds.y + bounds.height) / tile_height); ++y)
			{
 
				tiles.add(getTile(x, y));
			}
		}
		return tiles;
	}
 
	public void addBoundedShape(BoundedShape s)
	{
		ArrayList<ArrayList<BoundedShape>> tiles = getTiles(s);
		for (ArrayList<BoundedShape> tile : tiles)
		{
			if (!tile.contains(s))
			{
				tile.add(s);
			}
		}
	}
 
	public void removeBoundedShape(BoundedShape s)
	{
		ArrayList<ArrayList<BoundedShape>> tiles = getTiles(s);
		for (ArrayList<BoundedShape> tile : tiles)
		{
			tile.remove(s);
		}
	}
 
	public void paint(Graphics2D g)
	{
		g.setColor(Color.black);
		for (int x = 0; x <= x_tiles; ++x)
		{
			g.drawLine((int) (x * tile_width), 0, (int) (x * tile_width),
					(int) (tile_height * y_tiles));
		}
		for (int y = 0; y <= y_tiles; ++y)
		{
			g.drawLine(0, (int) (y * tile_height), (int) (tile_width * x_tiles),
					(int) (y * tile_height));
		}
		for (int x = 0; x < x_tiles; ++x)
		{
			for (int y = 0; y < y_tiles; ++y)
			{
				ArrayList<?> tile = getTile(x, y);
				if (tile.size() > 0)
				{
					g.setColor(new Color(0xFF, 0, 0, 0x80));
					g.fillRect((int) (x * tile_width), (int) (y * tile_height), (int) tile_width,
							(int) tile_height);
				}
			}
		}
	}
}
 
import java.awt.geom.Rectangle2D;
 
public interface BoundedShape
{
	public Rectangle2D.Double getBounds();
}