package com.srbenoit.modeling.grid;
import java.util.logging.Level;
import com.srbenoit.sparsearray.SparseArray;
/**
* A two-dimensional grid that may contain objects . Contained objects must be derived from
* GridMember
. This class provides a fast way to iterate over the set of potential neighbors
* of an object.
*
*
The grid manages a sparse array data structure that assigns each added object an array index * that does not change while the object is part of the grid. Removing objects may open gaps in the * array, which newly added objects will fill first before expanding the array. There are three * parallel arrays, all the same length, and each with the same indices populated with data: * *
GridMember
objectsThe sortedIndices array supports fast access to neighbors lists for a member
* as follows. Each element in this array is an array of integers containing the indices of all
* objects with a particular X address. Within these inner arrays, indices are organized in blocks
* by Y address (all indices with Y address 0 first, all indices with Y address 1 next, and so
* forth). The starting index of each block is stored in the two-dimensional array
* sortedIndexStarts, which is gridWidth x gridHeight in size, and the index after the
* ending index of each block is stored in sortedIndexEnds (meaning that if the
* values in sortedIndexStarts and sortedIndexEnds are equal,
* there are no items in the list for that Y address).
*/
public final class Grid2D extends AbstractGrid2D {
/** the X coordinate of the left edge of the grid */
private final double minX;
/** the Y coordinate of the bottom edge of the grid */
private final double minY;
/** the X coordinate of the right edge of the grid */
private final double maxX;
/** the Y coordinate of the top edge of the grid */
private final double maxY;
/** the width of the grid as a number of grid cells */
private final int gridWidth;
/** the height of the grid as a number of grid cells */
private final int gridHeight;
/** the X address of each object in the grid (size = objects.length) */
private int[] xAddresses;
/** the Y address of each object in the grid (size = objects.length) */
private int[] yAddresses;
/**
* an array of lists of object indices, where [0] holds the list of indices of all objects with
* X address 0, [1] holds the list of indices of all objects with X address [1], and so forth
* (the length of this array is gridWidth). Within each list, indices of all objects with Y
* address 0 appear first, then all with Y address 1, and so forth.
*/
private int[][] sortedIndices;
/**
* the starting index of each block in sortedIndices (this array is gridWidth x gridHeight, and
* the element at [i][j] is the index into the sortedIndices[i] array of the first object whose
* Y address is j)
*/
private final int[][] sortedIndexStarts;
/**
* the ending index of each block in sortedIndices (this array is gridWidth x gridHeightm, and
* the element at [i][j] is the index into the sortedIndices[i] array after the last object
* whose Y address is j - may be equal to array length)
*/
private final int[][] sortedIndexEnds;
/**
* Constructs a new AbstractGrid
.
*
* @param minXCoord the X coordinate of the left edge of the grid
* @param minYCoord the Y coordinate of the bottom edge of the grid
* @param cellSize width and height of the grid cells
* @param width the width of the grid in cells
* @param height the height of the grid in cells
*/
public Grid2D(final double minXCoord, final double minYCoord, final double cellSize,
final int width, final int height) {
super(cellSize);
this.minX = minXCoord;
this.minY = minYCoord;
this.maxX = minXCoord + (width * cellSize);
this.maxY = minYCoord + (height * cellSize);
this.gridWidth = width;
this.gridHeight = height;
this.xAddresses = new int[BLOCK_SIZE];
this.yAddresses = new int[BLOCK_SIZE];
this.sortedIndices = new int[width][BLOCK_SIZE / 4];
this.sortedIndexStarts = new int[width][height];
this.sortedIndexEnds = new int[width][height];
}
/**
* Gets the X coordinate of the left edge of the grid.
*
* @return the minimum X coordinate
*/
public double getMinX() {
return this.minX;
}
/**
* Gets the X coordinate of the left edge of the grid.
*
* @return the minimum X coordinate
*/
public double getMaxX() {
return this.maxX;
}
/**
* Gets the Y coordinate of the bottom edge of the grid.
*
* @return the minimum Y coordinate
*/
public double getMinY() {
return this.minY;
}
/**
* Gets the Y coordinate of the bottom edge of the grid.
*
* @return the minimum Y coordinate
*/
public double getMaxY() {
return this.maxY;
}
/**
* Gets the width of the grid as a number of cells.
*
* @return the width of the grid
*/
public int getGridWidth() {
return this.gridWidth;
}
/**
* Gets the height of the grid as a number of cells.
*
* @return the height of the grid
*/
public int getGridHeight() {
return this.gridHeight;
}
/**
* Called when a member has been added - subclasses should compute grid cells for the object
* and add the object to sorted index arrays
*
* @param index the index of the member that has just been added
*/
protected void memberAdded(final int index) {
GridMember2Int member;
int xAddr;
int yAddr;
member = get(index);
xAddr = coordinateToAddress(member.getPosX(), this.minX, this.gridWidth);
yAddr = coordinateToAddress(member.getPosY(), this.minY, this.gridHeight);
this.xAddresses[index] = xAddr;
this.yAddresses[index] = yAddr;
// Update the sortedIndices arrays to include the new object
addSortedIndex(index);
}
/**
* Gets the X address of the element at a particular index.
*
* @param index the index of the element
* @return the X address of that element
*/
public int getXAddress(final int index) {
return this.xAddresses[index];
}
/**
* Gets the Y address of the element at a particular index.
*
* @param index the index of the element
* @return the Y address of that element
*/
public int getYAddress(final int index) {
return this.yAddresses[index];
}
/**
* Called when a member is about to be removed - subclasses should clean up actions performed
* in memberAdded
. The object still exists in the grid's object array when this
* method is called.
*
* @param index the index of the member that is being removed
*/
protected void memberRemoved(final int index) {
removeSortedIndex(index);
}
/**
* Updates the grid address for a grid member that has moved.
*
* @param index the index of the grid member that moved
* @param newX the grid member's new X coordinate
* @param newY the grid member's new Y coordinate
*/
public void move(final int index, final double newX, final double newY) {
int xAddr;
int yAddr;
xAddr = coordinateToAddress(newX, this.minX, this.gridWidth);
yAddr = coordinateToAddress(newY, this.minY, this.gridHeight);
// Only take action if addresses have changed
if ((xAddr != this.xAddresses[index]) || (yAddr != this.yAddresses[index])) {
removeSortedIndex(index);
this.xAddresses[index] = xAddr;
this.yAddresses[index] = yAddr;
addSortedIndex(index);
}
}
/**
* Identifies the neighboring objects to a specified object, and sets the bits corresponding to
* those potential neighbors in the temp
bit set.
*
* @param member the grid member whose neighbors are requested
* @param range the range within which we consider points to be neighbors (must be no more
* than one grid cell size)
*/
public void getNeighborsOf(final GridMember2Int member, final double range) {
int index;
double targetX;
double targetY;
double targetMinX;
double targetMaxX;
double targetMinY;
double targetMaxY;
int xAddr;
int yAddr;
GridMember2Int test;
int testIndex;
int[] starts;
int[] ends;
int[] array;
int end;
int xPos;
int yPos;
int which;
member.clearNeighbors();
index = member.getGridIndex();
targetX = member.getPosX();
targetY = member.getPosY();
targetMinX = targetX - range;
targetMaxX = targetX + range;
targetMinY = targetY - range;
targetMaxY = targetY + range;
xAddr = this.xAddresses[index];
yAddr = this.yAddresses[index];
// Test the column to the left of the object's cell
xPos = xAddr - 1;
if (xPos >= 0) {
array = this.sortedIndices[xPos];
starts = this.sortedIndexStarts[xPos];
ends = this.sortedIndexEnds[xPos];
// Test the cell below and left of the object's cell
yPos = yAddr - 1;
if (yPos >= 0) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
if ((test.getPosX() > targetMinX) && (test.getPosY() > targetMinY)) { // NOPMD SRB
member.addNeighbor(test);
}
}
}
// Test the cell to the left of the object's cell
end = ends[yAddr];
for (which = starts[yAddr]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
if (test.getPosX() > targetMinX) {
member.addNeighbor(test);
}
}
// Test the cell above and to the left of the object's cell
yPos = yAddr + 1;
if (yPos < this.gridHeight) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
if ((test.getPosX() > targetMinX) && (test.getPosY() < targetMaxY)) { // NOPMD SRB
member.addNeighbor(test);
}
}
}
}
// Test the column containing the object's cell
array = this.sortedIndices[xAddr];
starts = this.sortedIndexStarts[xAddr];
ends = this.sortedIndexEnds[xAddr];
// Test the cell below the object's cell
yPos = yAddr - 1;
if (yPos >= 0) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
if (test.getPosY() > targetMinY) {
member.addNeighbor(test);
}
}
}
// Test the object's cell
end = ends[yAddr];
for (which = starts[yAddr]; which < end; which++) {
testIndex = array[which];
if (testIndex != index) {
test = get(testIndex);
member.addNeighbor(test);
}
}
// Test the cell above the object's cell
yPos = yAddr + 1;
if (yPos < this.gridHeight) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
if (test.getPosY() < targetMaxY) {
member.addNeighbor(test);
}
}
}
// Test the column to the right of the object's cell
xPos = xAddr + 1;
if (xPos < this.gridWidth) {
array = this.sortedIndices[xPos];
starts = this.sortedIndexStarts[xPos];
ends = this.sortedIndexEnds[xPos];
// Test the cell below and right of the object's cell
yPos = yAddr - 1;
if (yPos >= 0) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
if ((test.getPosX() < targetMaxX) && (test.getPosY() > targetMinY)) { // NOPMD SRB
member.addNeighbor(test);
}
}
}
// Test the cell to the right of the object's cell
end = ends[yAddr];
for (which = starts[yAddr]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
if (test.getPosX() < targetMaxX) {
member.addNeighbor(test);
}
}
// Test the cell above and to the right of the object's cell
yPos = yAddr + 1;
if (yPos < this.gridHeight) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
if ((test.getPosX() < targetMaxX) && (test.getPosY() < targetMaxY)) { // NOPMD SRB
member.addNeighbor(test);
}
}
}
}
}
/**
* Identifies the neighboring objects to a specified object, and sets the bits corresponding to
* those potential neighbors in the temp
bit set.
*
* @param member the grid member whose neighbors are requested
*/
public void getNeighborsOf(final GridMember2Int member) {
int index;
int xAddr;
int yAddr;
int testIndex;
int[] starts;
int[] ends;
int[] array;
int end;
int xPos;
int yPos;
int which;
GridMember2Int test;
member.clearNeighbors();
index = member.getGridIndex();
xAddr = this.xAddresses[index];
yAddr = this.yAddresses[index];
// Test the column to the left of the object's cell
xPos = xAddr - 1;
if (xPos >= 0) {
array = this.sortedIndices[xPos];
starts = this.sortedIndexStarts[xPos];
ends = this.sortedIndexEnds[xPos];
// Test the cell below and left of the object's cell
yPos = yAddr - 1;
if (yPos >= 0) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
member.addNeighbor(test);
}
}
// Test the cell to the left of the object's cell
end = ends[yAddr];
for (which = starts[yAddr]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
member.addNeighbor(test);
}
// Test the cell above and to the left of the object's cell
yPos = yAddr + 1;
if (yPos < this.gridHeight) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
member.addNeighbor(test);
}
}
}
// Test the column containing the object's cell
array = this.sortedIndices[xAddr];
starts = this.sortedIndexStarts[xAddr];
ends = this.sortedIndexEnds[xAddr];
// Test the cell below the object's cell
yPos = yAddr - 1;
if (yPos >= 0) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
member.addNeighbor(test);
}
}
// Test the object's cell
end = ends[yAddr];
for (which = starts[yAddr]; which < end; which++) {
testIndex = array[which];
if (testIndex != index) {
test = get(testIndex);
member.addNeighbor(test);
}
}
// Test the cell above the object's cell
yPos = yAddr + 1;
if (yPos < this.gridHeight) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
member.addNeighbor(test);
}
}
// Test the column to the right of the object's cell
xPos = xAddr + 1;
if (xPos < this.gridWidth) {
array = this.sortedIndices[xPos];
starts = this.sortedIndexStarts[xPos];
ends = this.sortedIndexEnds[xPos];
// Test the cell below and right of the object's cell
yPos = yAddr - 1;
if (yPos >= 0) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
member.addNeighbor(test);
}
}
// Test the cell to the right of the object's cell
end = ends[yAddr];
for (which = starts[yAddr]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
member.addNeighbor(test);
}
// Test the cell above and to the right of the object's cell
yPos = yAddr + 1;
if (yPos < this.gridHeight) {
end = ends[yPos];
for (which = starts[yPos]; which < end; which++) {
testIndex = array[which];
test = get(testIndex);
member.addNeighbor(test);
}
}
}
}
/**
* Called when the capacity of the sparse array is changed, to allow other programs that need
* to keep arrays of the same size to adjust their arrays.
*
* @param array the array whose capacity is changing
* @param newCapacity the new capacity of the sparse array
*/
public void capacityChanged(final SparseArray> array, final int newCapacity) {
int len;
int[] newXAddr;
int[] newYAddr;
len = this.xAddresses.length;
newXAddr = new int[newCapacity];
newYAddr = new int[newCapacity];
System.arraycopy(this.xAddresses, 0, newXAddr, 0, len);
System.arraycopy(this.yAddresses, 0, newYAddr, 0, len);
this.xAddresses = newXAddr;
this.yAddresses = newYAddr;
}
/**
* Adds a member index to the set of sorted indices. The object, X address, and Y address
* should be populated before calling this method.
*
* @param index the index to add
*/
private void addSortedIndex(final int index) {
int xAddr;
int yAddr;
int start;
int end;
int[] array;
int nextStart;
int priorEnd;
int[] newArray;
int size;
int pos;
xAddr = this.xAddresses[index];
yAddr = this.yAddresses[index];
// Get array and current start and end of the block within the array
array = this.sortedIndices[xAddr];
start = this.sortedIndexStarts[xAddr][yAddr];
end = this.sortedIndexEnds[xAddr][yAddr];
for (int test = start; test < end; test++) {
if (array[test] == index) {
LOG.log(Level.WARNING, "Request to add object to sorted list it is already in",
new Exception());
return;
}
}
// Find the start of the next block
if (yAddr < (this.gridHeight - 1)) {
nextStart = this.sortedIndexStarts[xAddr][yAddr + 1];
} else {
nextStart = array.length;
}
// Find the end of the prior block
if (yAddr > 0) {
priorEnd = this.sortedIndexEnds[xAddr][yAddr - 1];
} else {
priorEnd = 0;
}
// If there is room after the current block, insert the element at the end of the current
// block and advance its end position. Otherwise, if there is room before the block,
// insert the element before the block and move its start position back one. If neither
// can be done, expand storage to make room at the end of the block then add the element.
if (nextStart > end) {
array[end] = index;
this.sortedIndexEnds[xAddr][yAddr] = end + 1;
} else if (priorEnd < start) {
array[start - 1] = index;
this.sortedIndexStarts[xAddr][yAddr] = start - 1;
} else {
// If we're going to reallocate, size the array so there are four empty slots at the
// end of each block (this keeps arrays from growing too large while ensuring we only
// do this at most every fourth add)
size = 0;
for (int y = 0; y < this.gridHeight; y++) {
size += this.sortedIndexEnds[xAddr][y] - this.sortedIndexStarts[xAddr][y] + 4;
}
newArray = new int[size];
// Copy the array data into the new array
pos = 0;
for (int y = 0; y < this.gridHeight; y++) {
size = this.sortedIndexEnds[xAddr][y] - this.sortedIndexStarts[xAddr][y];
if (size > 0) {
System.arraycopy(array, this.sortedIndexStarts[xAddr][y], newArray, pos, size);
}
this.sortedIndexStarts[xAddr][y] = pos;
this.sortedIndexEnds[xAddr][y] = pos + size;
pos += size + 4;
}
this.sortedIndices[xAddr] = newArray;
// Now there's room to add the new element
end = this.sortedIndexEnds[xAddr][yAddr];
newArray[end] = index;
this.sortedIndexEnds[xAddr][yAddr] = end + 1;
}
}
/**
* Removes a member index from the set of sorted indices.
*
* @param index the index to remove
*/
private void removeSortedIndex(final int index) {
int xAddr;
int yAddr;
int start;
int end;
int[] array;
int pos;
xAddr = this.xAddresses[index];
yAddr = this.yAddresses[index];
array = this.sortedIndices[xAddr];
start = this.sortedIndexStarts[xAddr][yAddr];
end = this.sortedIndexEnds[xAddr][yAddr];
for (pos = start; pos < end; pos++) {
if (array[pos] == index) {
array[pos] = -1;
break;
}
}
if (pos == start) {
// If it was the first item, just shift the start ahead one
this.sortedIndexStarts[xAddr][yAddr] = start + 1;
} else if (pos == (end - 1)) {
// If it was the last item, just shift the end back by one
this.sortedIndexEnds[xAddr][yAddr] = end - 1;
} else if (pos < (end - 1)) {
// If it was in the middle, shift the end to the position we found,
// then shift the end back by one
array[pos] = array[end - 1];
this.sortedIndexEnds[xAddr][yAddr] = end - 1;
} else {
LOG.warning("index not found while removing from sorted arrays");
}
}
}