Placing monsters randomly with good performance

Now this is not as easy as it seems… Let’s suppose you have a dungeon of nxn squares, about 50% of which is solid walls, and you want to place a number of monsters in this dungeon, randomly… (actually not randomly in my game, but controlled by the letters of a sentence, i.e. the letter A corresponds to a low coordinate, Z to a high coordinate).

The straightforward case to do this is to get random coordinates, check, and repeat this until you find a good space.

This didn’t work out so well with a lowly Android phone / Dalvik VM combination.

What did work well was using a “SnailIterator”:

1. pick a random x/y

2. Move around this x/y, slowly away, like you’d be drawing a snail shell around it. Always check the coordinates and pick the first that fits.

This gave me a much better performance, particularly as the snail iterator also doesn’t construct a single object (thus forcing me not to implement the Iterator contract which would have forced me to e.g. return Dimension objects for next() and kill performance.

Here’s the code (beautifully un-intended by WordPress… I have to learn to change this…):


public class SnailIterator {

private int x;
private int y;

private int xsize;
private int ysize;

private int n;
private int step;
private int count;
private int dx;
private int dy;
private boolean finished;

/**
* Creates a new snail iterator with a given start coordinate and a given size that must not
* be reached.
* @param x        the start x coordinate
* @param y        the start y coordinate
* @param xsize    the x size; all coordinates must be between 0 and xsize-1
* @param ysize    the y size; all coordinates must be between 0 and ysize-1
*/
public SnailIterator(int x, int y, int xsize, int ysize) {
this.x = x;
this.y = y;
this.xsize = xsize;
this.ysize = ysize;

dx = 0;
dy = -1;
n = 1;
step = 0;
count = 0;

finished = x < 0 || x >= xsize || y < 0 || y >= ysize;
}

/**
* Returns whether getX() and getY() will return valid values
*/
public boolean hasValue() {
return !finished;
}

/**
* Determines the next values for getX() and getY()
*/
public void next() {
if (step >= n) {
turnRight();
step = 1;
count++;
if (count == 2) {
count = 0;
n++;
}
}
else {
step++;
}
x = x + dx;
y = y + dy;
finished = x < 0 || x >= xsize || y < 0 || y >= ysize;
}

private void turnRight() {
int xx = dx;
int yy = dy;

if (xx != 0)
dx = 0;
else
dx = -yy;

if (yy != 0)
dy = 0;
else
dy = xx;
}

/**
* Returns the current x value
* @return
*/
public int getX() {
return x;
}

/**
* Returns the current y value
* @return
*/
public int getY() {
return y;
}

}