Archive

Archive for July, 2010

Placing monsters randomly with good performance

July 28, 2010 Leave a comment

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;
}

}

Categories: Uncategorized

Android Development Tip #1: Don’t use Integer keys

July 25, 2010 Leave a comment

Maybe it’s useful to condense some of my learnings into tips. So here’s #1: Don’t use Integer keys. If you think that e.g. a HashMap is good, try to opt for an array of Anything. If your Integers can grow arbitrarily big, maybe create e.g. an 8-bit Hashkey from your integer, and create an array of ArrayList.

It seems that you should avoid very dynamic objects, like a temporary Integer key created to lookup a HashMap, at all costs. For me the performance of the level generation grew from many minutes to a few seconds after changing that.

Categories: Uncategorized Tags: , , ,

My first dungeon level on the Android emulator :-)

July 22, 2010 Leave a comment

An actual, working, freshly generated level (monster placement is visualized wrongly, some end up in walls...)

Categories: New Feature, Progress

Dungeon Generation works! (well, works a little bit)

July 21, 2010 Leave a comment

After a lot of debugging yesterday, my first test UI that allows to browse dungeon levels that have been generated starts to work.

I like the new way of constructing levels:

  • One single web page for a whole dungeon (this also eats up less web bandwidth compared to what Web Raid is doing)
  • One sentence defines the level tree; some letters mean “this level has one child”, others “this level has two children”, others “this is a leaf level”. This results in much nicer level structures.
  • Monsters and items are placed in these levels in a way that fits their levels: easy beasts in Leve l 1, tough ones in the lowest levels.

It all still takes a bit long (generating a full dungeon takes a minute), but we’ll see about that…

Categories: New Feature, Progress

Dalvik. A small village in iceland

July 21, 2010 Leave a comment

… that mostly lives from catching fish and leads a rural life, not doing that fancy stuff that those guys in the cities do.

How very fitting a name for the Android Java VM.

Yesterday I spent over an hour again re-engineering one of my Web Raid classes, the one that picks a fitting color name for a certain color. This class relies on a big list of names + colors taken from Wikipedia, and needs to find the closest match for a given RGB color. I was using a hash map that maps Hue values to lists of colors of that hue value and that then picks the best one.

This is blindingly fast with Hotspot.

With Dalvik, the little step of generating Integer objects for the int hue values slows down the VM to a crawl. Probably Dalvik uses the kind of ancient Garbage collector that Sun was using with 1.1…

Oh well. Now, with a simple array of 4*360 values (so I can have four different colors for one hue key) it works blindingly fast again. But I notice that I need to rewrite major portions of Web Raid to run on an Android device.

Categories: dalvik