Edit: apparently the term toroidal array is a concise name for a grid with the wrapping behavior which I implemented in the Grid class I wrote. So, obviously that much has been done before, as I suspected when I originally posted this article. However, my node “deletion” system may still be something new. Actually, the deletion system seems to be horribly bugged, and I don’t have time to fix it.
I wrote a pair of classes to handle a 2×2 or larger grid of nodes. Each node borders 4 other nodes. For example, a 3×3 grid would look like:
0 1 2
3 4 5
6 7 8
Node 0 would be connected to node 6 to the north, node 1 to the east, node 3 to the south, and node 2 to the west. (Node connections wrap to the other side of the grid when the node is on an “edge” of the grid.) Node 4 would be connected to 1, 5, 7, and 3, respectively.
Upon deleting a node, the hole is filled by the remaining nodes. I’m probably not the first one to implement something like this, but I was kinda bored and felt like coding it from scratch.
See full article for source code and further details.
Grid.java:
public class Grid {
private int width, height;
private GridNode[] nodes;
public Grid(int width, int height) {
super();
this.width = width;
this.height = height;
nodes = new GridNode[width * height];
int north, south, east, west;
for (int i=0; i<width*height; i++) {
north = findNorthBoundary(i);
east = findEastBoundary(i);
south = findSouthBoundary(i);
west = findWestBoundary(i);
nodes[i] = new GridNode(north, east, south, west);
}
}
public Grid() {
}
public GridNode getNode(int index) {
return nodes[index];
}
public int[] getConnectedNodes(int index) {
int allNodes[] = new int[] { nodes[index].getNorth(), nodes[index].getEast(),
nodes[index].getSouth(), nodes[index].getWest() };
int intact = 4;
for (int i=0; i<4; i++) {
if (allNodes[i] == -1) {
intact--;
}
}
int intactNodes[] = new int[intact];
int pos = 0;
for (int i=0; i<4; i++) {
if (allNodes[i] == -1) {
continue;
} else {
intactNodes[pos] = allNodes[i];
pos++;
}
}
return intactNodes;
}
private int findWestBoundary(int i) {
if (isWestEdge(i)) {
return i + width - 1;
} else {
return i - 1;
}
}
private int findSouthBoundary(int i) {
if (isSouthEdge(i)) {
return i % width;
} else {
return i + width;
}
}
private int findNorthBoundary(int i) {
if (isNorthEdge(i)) {
return (width * height - (width - i));
} else {
return i - width;
}
}
private int findEastBoundary(int i) {
if (isEastEdge(i)) {
return i - width + 1;
} else {
return i + 1;
}
}
private boolean isWestEdge(int index) {
return ((index % width) == 0);
}
private boolean isEastEdge(int index) {
return ((index % width) == (width - 1));
}
private boolean isSouthEdge(int index) {
return (index >= ((width * height) - width));
}
private boolean isNorthEdge(int index) {
return (index < width);
}
public void deleteNode(int i) {
if (isEastEdge(i)) {
nodes[i-1].setEast(i-width + 1);
nodes[i-width+1].setWest(i-1);
} else if (isWestEdge(i)) {
nodes[i+1].setWest(i + width - 1);
nodes[i + width - 1].setEast(i+1);
} else {
nodes[i-1].setEast(i + 1);
nodes[i+1].setWest(i-1);
}
if (isNorthEdge(i)) {
nodes[i+width].setNorth((width * height) - width + i);
nodes[(width * height) - width + i].setSouth(i+width);
} else if (isSouthEdge(i)) {
nodes[i-width].setSouth(i % width);
nodes[i%width].setNorth(i-width);
} else {
nodes[i-width].setSouth(i + width);
nodes[i+width].setSouth(i-width);
}
nodes[i].collapse();
}
public boolean isAvailable(int i) {
return nodes[i].isAvailable();
}
}
GridNode.java:
public class GridNode {
private int north, east, south, west;
private boolean available;
public GridNode(int north, int east, int south, int west) {
super();
this.north = north;
this.east = east;
this.south = south;
this.west = west;
this.available = true;
}
public int getNorth() {
return north;
}
public void setNorth(int north) {
this.north = north;
}
public int getEast() {
return east;
}
public void setEast(int east) {
this.east = east;
}
public int getSouth() {
return south;
}
public void setSouth(int south) {
this.south = south;
}
public int getWest() {
return west;
}
public void setWest(int west) {
this.west = west;
}
public boolean isAvailable() {
return this.available;
}
public void collapse() {
this.west = -1;
this.south = -1;
this.north = -1;
this.east = -1;
this.available = false;
}
}
Usage example:
//constructs a grid with nodes 0-25 Grid grid = new Grid(5, 5); grid.deleteNode(8);
The resulting grid will have node 7 connected to node 9, and node 3 connected to node 13.
Some limitations:
- You should of course check the result of
grid.isAvailable(index)before you try to do anything with a given node. - The grid must have at least two nodes in every row and column, unless it's okay for your nodes to link to themselves.
- I also didn't handle deleting nodes that are adjacent, so try to avoid that unless you want a mess. This was just a quick hackish implementation, after all...
If you make any improvements to these classes, please leave a comment here.