Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

View RSS Feed

helloworld922

Preview: 2D Grid Accelerator Structure

Rate this Entry
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();
}

Updated April 8th, 2012 at 10:59 PM by helloworld922

Categories
Uncategorized

Comments

  1. copeg's Avatar
    permalink
    A space partitioning tree might be an alternative to look into. Partition the space in some manner (say by halves) and represent each space as a node (children of a node are subsets of that space). The partitioning stops for a given node when the space it represents contains a single object (thus, each leaf represents a given space with one object - no need for determining how small to partition as you terminate when each partition contains a single element, and it avoids unnecessary partitioning). When an object moves, get the leaf node that represents its surrounding space, update the tree by ascending up to the parent(s) and relocating the node in the tree appropriately - collisions can be checked when you update the tree and find the node you are repositioning to 'collide' with another leaf node (you can do precise collision checking at this point). Then re-partition the tree (if no collisions exist) or update the two objects position based upon the collision as appropriate and recursively reposition the nodes within the tree.
  2. helloworld922's Avatar
    permalink
    Quote Originally Posted by copeg
    A space partitioning tree might be an alternative to look into. Partition the space in some manner (say by halves) and represent each space as a node (children of a node are subsets of that space). The partitioning stops for a given node when the space it represents contains a single object (thus, each leaf represents a given space with one object - no need for determining how small to partition as you terminate when each partition contains a single element, and it avoids unnecessary partitioning). When an object moves, get the leaf node that represents its surrounding space, update the tree by ascending up to the parent(s) and relocating the node in the tree appropriately - collisions can be checked when you update the tree and find the node you are repositioning to 'collide' with another leaf node (you can do precise collision checking at this point). Then re-partition the tree (if no collisions exist) or update the two objects position based upon the collision as appropriate and recursively reposition the nodes within the tree.
    I have given quad-trees a try before, but I found that their performance over a 2D grid with a moderate number of objects isn't that great. It may have been the implementation I chose, though. Perhaps a k-d tree would work better... in any case, this grid mechanism works extremely well for a medium number of objects with larger objects tending to be stationary and smaller ones doing the moving. I think I should save the data in each grid as a set, though... the current 2-D arraylist implementation works but is very inefficient