Thursday, January 27, 2011

Movement in MMORPG games

Typical for MMORPG games is that there are a lot of players running around, and they usually want to interact with each other in some way - to the very least extent they want to see that other people are there.

This can of course be a potential problem, due to the massive amount of data that needs to be sent over the internet. The amount of character data to send grows quadratically with the number of players in crowded locations.

There are some tricks you can use to at the very least reduce the constant factor in order to increase the number of players supported.

First, it is important to note that not all online games have the same requirements when it comes to character movement:
  • In first-player shooters, it is important that all other players are always displayed in the correct locations, in order to be able to aim and fire accurately. This is not true for most MMORPG games.
  • MMORPG:s need to handle hundreds of players in the same location, first-player shooters tend to support much fewer.
  • Smooth movement and high fidelity of small movements is important in MMORPGs for the social interactions to feel more natural, whereas in first-player shooters it's much more important to fast forward movements to always be up to date - it's also preferable to do dead reckoning in order to account for latency.
This leads me to the conclusion that we should design the movement system to be more like a VCR (if anyone still remembers those). Clients record their movements and sends compiled packages to other players for playback. This makes it easy to support smooth movement. It also makes it easier to compress the data sent. The tradeoff is course slightly more cpu and memory usage for reduced network traffic.

Here come some of the tricks we currently use for Spaced.

Path compaction

Path compaction is the first step in reducing network traffic.
Basically we compact movement paths to a straight line if the distance from the start to the end is close enough to the sum of the distance of each path segment. This can easily be done in constant time for each added path segment, so it's a simple choice.

Same state

Send a bitfield with one bit for each type of movement data (position, rotation, animation state). Then simply don't send the actual data if it hasn't changed since last frame. This by itself reduces our network usage to about 40 bytes per second and character, with sending frames at least ten times per second, when the character is idling.

Compressed positions

Position vectors are stored clientside with very high precision (64 bits per component), which is useful for local calculations, but is probably a bit silly for sending it over the network, so we just convert it to floats instead.

Compressed rotations

Character rotations (the facing) are represented as quaternions, with four double components in the range [-1, 1].
Since we don't really need that high resolution for the rotation for movement playback, we simply encode each component as a signed byte, with -127 mapping to -1 and 127 mapping to 1.

Movement deltas

I think this the most interesting trick of the ones described.
Instead of sending the position each frame, we can just send the delta compared to previous frame!

With a naive encoding, this will be as expensive to send as the actual position, but we can take advantage of the fact that most movements will be very small vectors.

Start with size = ceil(log_2(max(x, y, z)))
size will hopefulle be an int in the range [-128, 127] because then we can store it in a byte (otherwise we'll just revert to sending a full position instead)

Now we know that x / 2^size must be in the range [-1, 1] which is great, since we can store it in a byte with some (a lot!) lost precision.

Calculate the actual bytes to send as x_send = x * 127 / 2^size (and the same for y and z)

By sending size along with these three bytes, we can send a compressed vector in just four bytes. It can be decompressed as: (x * 2^size / 127, y * 2^size / 127, z * 2^size / 127).

But wait a second...

You're probably thinking that this won't work, because you lose to much data when you compress it, and when you add up all those delta vectors, you'll get more and more value drift!

That's true, but the solution is quite simple.
Instead of calculating the deltas as Delta(n) = compress(P(n) - P(n - 1)), we calculate it as Delta(n) = compress(P(n) - Q(n-1)), where Q(n) is defined as Q(n-1) + Delta(n).
This means that all the drift errors that we generate at P(n) will be accounted for when we generate P(n+1). The total drift error at P(n) will thus never be greater than 1/127 of the size of the movement at P(n).

This has been stress tested by a scenario test which measures the actual drift for millions of updates, and it never increases more than 0.1.

Wednesday, January 19, 2011

Subversion and feature branches

I've used subversion for a long time (probably around five or six years), but it's only recently I've started to use feature branches actively.

Mostly it was because it was a huge pain to do. You used to have to manually track revisions for all merges for it to work at all. Fortunately that was greatly improved with subversion 1.6, but it was still quite possible to mess it up.

Usual symptoms were crazy conflicts when merging from files not even touched in the branch.

These days, I happily use feature branches, because I finally figured out how to manage them properly. I can't remember exactly who I got this from, it was quite possibly several different people independently from each other.

Basic rules to avoid pain:
  • Always stand in the project root (/trunk/ or /branches/branch/) when doing subversion operations.
  • Update often.
  • Commit often.
  • Sync trunk -> branch often.
  • Merge branch -> trunk only once, and then delete it.
Here are the general operations I use nowadays.

To create a branch:
svn copy TRUNK_URL BRANCH_URL

Start using the branch:
svn switch BRANCH_URL

List existing branches:
svn list BASE_URL/branches

Sync trunk to branch:
svn up
svn merge TRUNK_URL .
svn commit -m "Merged trunk to branch BRANCH"

Reintegrate branch (make sure it's commited and synced recently):
svn switch TRUNK_URL
svn merge --reintegrate BRANCH_URL .
svn commit -m "Reintegrated BRANCH"
svn delete -m "Deleting reintegrated BRANCH" BRANCH_URL

It doesn't look so hard, right?
The trick is that if you do something else at some point, like cherry picking revisions into the branch, subversion tends to get confused. I am not sure if it's subversions fault or the users fault, but in either case, cleaning it up usually gets messy.

An annoying thing is all those URL:s you need to enter.
To simplify things for my most common usage, I wrote a simple bash script:

It mostly just ensures that I don't forget any steps, does some basic error checking, and most importantly, it lets me skip writing the full URL all the time.

Here's what it looks like:

And here is the actual script if anyone is interested.
#!/bin/bash

ERROR='\033[1;31m'
REPO='\033[1;32m'
CBRANCH='\033[1;33m'
COMMAND='\033[1;34m'
EXECUTE='\033[1;35m'
ENDCOL='\033[0m'

FULLURL=`svn info | grep -E "^URL: "| cut -d " " -f 2`
if [ "$FULLURL" == "" ]; then exit 1; fi
TRUNKURL=$(echo $FULLURL | grep -E -o "^.*/trunk")
BRANCHURL=$(echo $FULLURL | grep -E -o "^.*/branches/[^/]+")

set -e

function error() {
echo -e "${ERROR}$1${ENDCOL}"
exit 1
}

function execute() {
echo -e "> ${EXECUTE}$@${ENDCOL}"
$@
}

if [ "$TRUNKURL" != "" ]; then
if [ "$FULLURL" != "$TRUNKURL" ]; then
error "Please stand in the project root.\n Expected $TRUNKURL\n but was $FULLURL"
fi
BRANCH="trunk"
BASEURL=$(echo $TRUNKURL | sed "s/\\/trunk//")
elif [ "$BRANCHURL" != "" ]; then
if [ "$FULLURL" != "$BRANCHURL" ]; then
error "Please stand in the project root.\n Expected $BRANCHURL\n but was $FULLURL"
fi
BRANCH=$(echo $FULLURL | grep -E -o "[^/]+$")
BASEURL=$(echo $BRANCHURL | sed "s/\\/branches\\/$BRANCH//")
else
error "Could not determine trunk or branch from $FULLURL"
fi

function sync() {
if [ "$BRANCH" == "trunk" ]; then error "Must be on a branch to sync or reintegrate!"; fi
CLEAN=`svn status|grep -v "^\\?"`
if [ "$CLEAN" != "" ]; then error "Working copy is not clean. Revert or commit first!"; fi

execute svn up
execute svn merge $BASEURL/trunk .

UPDATED_FILES=`svn status|grep -E -v "^\\?"|cut -b 9-`
if [ "$UPDATED_FILES" == "" ]; then
echo "Nothing changed, skipping sync."
elif [ "$UPDATED_FILES" == "." ]; then
echo "Only trivial changes merge - reverting merge"
execute svn revert -R .
else
execute svn commit -m "Merged trunk to branch $BRANCH"
fi

}

case $1 in
switch)
if [ "$2" == "" ]; then error "Missing parameter to switch: branch"; fi
execute svn switch $BASEURL/branches/$2
;;
trunk)
execute svn switch $BASEURL/trunk/
;;
list)
echo -e "> ${EXECUTE}svn list $BASEURL/branches${ENDCOL}"
echo "Available branches:"
BRANCHES=`svn list $BASEURL/branches | grep -E -o "^[a-zA-Z]*"`
for b in $BRANCHES; do
echo -e " ${CBRANCH}$b${ENDCOL}"
done
;;
reintegrate|reint)
sync
execute svn switch $BASEURL/trunk
execute svn merge --reintegrate $BASEURL/branches/$BRANCH .
execute svn commit -m "Reintegrated $BRANCH"
execute svn delete -m "Deleting reintegrated $BRANCH" $BASEURL/branches/$BRANCH
;;
sync)
sync
;;
create)
if [ "$2" == "" ]; then error "Missing parameter to create: branch"; fi
execute svn copy $BASEURL/trunk $BASEURL/branches/$2 -m "Creating branch $2 from trunk"
execute svn switch $BASEURL/branches/$2
;;
delete)
if [ "$2" == "" ]; then error "Missing argument to delete: branch"; fi
if [ "$BRANCH" == "$2" ]; then error "Can not delete active branch. Switch first!"; fi
execute svn delete -m "Deleting branch $2" $BASEURL/branches/$2
;;
*)
echo -e "Repository: ${REPO}$BASEURL${ENDCOL}"
echo -e "Active branch: ${CBRANCH}$BRANCH${ENDCOL}"
echo "Usage: ./branch <command> [option]"
echo "Commands:"
echo -e " ${COMMAND}switch${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- switches to the branch"
echo -e " ${COMMAND}trunk${ENDCOL} -- switches to trunk"
echo -e " ${COMMAND}list${ENDCOL} -- list available branches"
echo -e " ${COMMAND}reintegrate${ENDCOL} or ${COMMAND}reint${ENDCOL} -- reintegrate active branch to trunk"
echo -e " ${COMMAND}sync${ENDCOL} -- syncs current branch with trunk"
echo -e " ${COMMAND}create${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- creates a new branch from trunk and switches to it"
echo -e " ${COMMAND}delete${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- deletes a branch without reintegrating it"
;;
esac

Thursday, November 11, 2010

Deep thoughts about deep mocks

A deep mock is a mock that has methods that also return mocks. In theory, you could follow a chain of mocks for as long as you wanted.

Deep mocks are supported by both Mockachino and Mockito, with the exception that a method from a mock can't return a mock if the return type is primitive or final.

Another problem with deep mocks was previously generics.
The following would fail in both Mockachino and Mockito:
static interface ListSet extends List<Set> {}
@Test
public void testDeepMockWithClass() {
ListSet mock = mock(ListSet.class, RETURNS_DEEP_STUBS);
Set mock2 = mock.get(0);
}

This would fail on the last line, because the mocking frameworks wouldn't understand that the return type of get(int) should be Set instead of Object.

This has been fixed in Mockachino 0.5.0 (with a fairly small patch, I'm happy to say!) but it is still broken in Mockito 1.8.5.

Now, this particular example takes advantage of the fact that the class we're dealing with has no open generic types. The type is fully bound.

It would be much harder to support something like this:
@Test
public void testDeepMockWithClass() {
List<Set> mock = mock(List<Set>.class, RETURNS_DEEP_STUBS);
Set mock2 = mock.get(0);
}


This is in fact not even legal Java syntax. It's also not valid Java semantics, since the runtime doesn't maintain type information except for some special cases.
So we simplify it into this, which is valid Java syntax:
@Test
public void testDeepMockWithClass() {
List<Set> mock = mock(List.class, RETURNS_DEEP_STUBS);
Set mock2 = mock.get(0);
}

Unfortunately, at the time of the call to mock, we only know about List.class, not that it should have Set as its generic type parameter, so it would be impossible to deduce which type it should create at mock.get(0).

This has two possible solutions. Either create a specific sub interface/class, like we did with ListSet. The other solution is to use the TypeLiteral concept, found in Google Guice:
@Test
public void testDeepMockWithClass() {
List<Set> mock = mock(
new TypeLiteral<List<Set>>() {},
fallback(DEEP_MOCK));
Set mock2 = mock.get(0);
}


Since we're actually creating a new anonymous class here, Java manages to retain the type information. It's unfortunately a bit verbose, but it should still come in handy in the few times you'd need to use deep mocks with generics.

Friday, August 20, 2010

Random numbers without repetition

The origin of this problem comes from picking K elements from a collection of elements of size N (N >= K, obviously). If K = N, this is the same thing as shuffling, which can be done using the excellent Fisher-Yates algorithm in O(N). This algorithm can be used when K is smaller than N as well, you just have to disregard N - K of the elements. However, if K is very small and N is very large, this algorithm is quite far from optimal.

Another approach is to simply pick elements randomly from the collection and keep track of which elements have already been picked. If you hit the same element again, you simply pick another one. This would work if the entropy source was good enough to ensure that would always pick numbers in a range with equal probability, to avoid getting stuck picking numbers already used. If K is much smaller than N, this would work well, but if K was very close to N, you could probably end up doing far too many retries to be reasonable as soon as you start filling up the result.

Instead, you could use the original Fisher-Yates strike-out approach and simply stop after K elements. This could be done in O(K*(log(K) + K)), which can be simplified to O(K^2) with a naive implementation:

public <T> List<T> take(List<T> source, int k) {
int n = source.size();
if (k > n) {
throw new IllegalStateException(
"Can not take " + k +
" elements from a list with " +
n + " elements");
}
List<T> result = new ArrayList<T>(k);
SortedSet<Integer> offsets = new TreeSet<Integer>();

for (int i = 0; i < k; i++) { // O(K)
int off = random.nextInt(n - i);

for (int offset : offsets) { // O(K)
if (off >= offset) {
off++;
} else {
break;
}
}
offsets.add(off); // O(log(K))
result.add(source.get(off));
}
return result;
}


if K >= O(sqrt(N)), then the plain shuffle is better, but when K is smaller than sqrt(N), this approach would be the winner.

I wonder if it's possible to do it faster than O(K^2). One idea is to use some sort of binary search to quicker find the actual offset without having to iterate the list of offsets. This would make the algorithm O(K*log(K)) instead which would be much better.

I experimented a bit by repeatedly running a binary search of the offset until the offset can not be incremented further. If N is large and K is small, this would often stop after the first iteration since it's sparse between findings, but you can still easily construct worst case scenarios which would need to iterate O(K) times.

Does anyone know any good articles / papers / blogs about algorithms for picking K distinct random numbers in the range 1..N?

Update:

After having eaten lunch, I figured out how to make it run in O(K):

public <T> List<T> take(List<T> source, int k) {
int n = source.size();
if (k > n) {
throw new IllegalStateException(
"Can not take " + k +
" elements from a list with " + n +
" elements");
}
List<T> result = new ArrayList<T>(k);
Map<Integer,Integer> used = new HashMap<Integer,Integer>();
int metric = 0;
for (int i = 0; i < k; i++) {
int off = random.nextInt(n - i);
while (true) {
metric++;
Integer redirect = used.put(off, n - i - 1);
if (redirect == null) {
break;
}
off = redirect;
}
result.add(source.get(off));
}
assert metric <= 2*k;
return result;
}
The idea here is to instead of recalculating off to the actual position, as in Fisher-Yates, just assume that the random index is correct. Then, use the map to check if the index has already been used, and if so, use another guaranteed free index instead.

The while loop make look bad, but it never runs more than 2*K times in total.
(I haven't proven this formally, I just ran a lot of benchmarks on random input.)

If I were to prove it though, my general strategy would be that the loop is entered exactly K times, and you will follow at most K links, since only K links will be constructed and no link is followed more than once.

Update 2:
Apparently Robert Floyd already invented this algorithm (well, it's very similar at least) (published in Communications of the ACM, September 1987, Volume 30, Number 9).
public <T> List<T> take(List<T> source, int k) {
int n = source.size();
List<T> result = new ArrayList<T>(k);
Set<Integer> used = new HashSet<Integer>();
for (int i = n - k; i < n; i++) {
int off = random.nextInt(i + 1);
if (!used.add(off)) {
off = i;
used.add(off);
}
result.add(source.get(off));
}
return result;
}
The only problem with this is that the ordering of result is not random, only which elements have been chosen. This is easily fixed by running Collections.shuffle(result, random) though.

I see two significant differences with this approach.

The first (which is of the least relevance) is the amount of entropy used.
If we assume that calling random.nextInt(n) consumes log_2(n) bits of entropy then my algorithm uses: log_2(n) + log_2(n-1) + log_2(n-2) + ... + log_2(n - k + 1) = log_2(n! / (n - k)!) = log_2(n!) - log_2((n - k)!) bits of entropy.

Robery Floyd with an additional plain shuffle uses:
log_2(n!) - log_2((n - k)!) + log_2(k!) bits of entropy which may be significant if k is large compared to n, and if entropy is expensive where the algorithm is used.

The second difference is much more important. The Robert Floyd-algorithm can't be run interactively, picking one or more numbers at a time. You need to know the value of k (or an upper bound of k) before requesting a random number, since the first number chosen by the algorithm will be in the range [0, n - k).
My algorithm on the other hand can be run partially and resumed without knowing the value of k at all.

Friday, August 6, 2010

Python annoyances - generators

Another annoyance in Python is generators. Since Python 2.5, the generator concept was extended to include coroutine support. (See http://www.python.org/dev/peps/pep-0342/ )
I for one think it's an odd design of coroutines.
Note that this comes from someone who is used to (and spoiled by) Lua's coroutines.

I have two problems with coroutines/generators in Python:

First of all, "def" gets multiple meanings. It's not just a function definition anymore.
It could also be a generator definition! And the only way to notice this is to
scan the entire function definition for a yield statement.

I would not have a problem with this if it wasn't for the case that generator
definitions and function definitions behave completely differently.
def gen():
return 123
I can call this with gen() and get 123 back. Simple!
def gen():
yield 123
If I call gen() now, I don't get 123 back, I get a generator object.
So I have to do this instead:
g = gen()
value = g()
That by itself isn't much trickier, but it's hard to know by just looking at the code if it's a generator. It's completely invisible at the call site, and at the definition it could be anywhere in the function. This is probably why most generators I've seen in Python have been fairly short and simple (which is a good thing for function design over all anyway).

Let's compare it to Lua, which was the language that introduced me to coroutines:
-- Simple function call
function gen()
return 123
end
value = gen()

-- Using a generator / coroutine
function gen()
coroutine.yield(123)
end
c = coroutine.wrap(gen)
value = c()
Here it's quite clear at the call site that we're dealing with a coroutine. And if we were to call gen as a regular function, we'd get a runtime error unless we were actually running in a coroutine already.

That gets us into the second annoyance. Python only supports yield in the generator definition. If you were to build a more complex generator, you'd have to write it as one long function instead of splitting it up into many small functions.

As it happens, I have a good example to use. The following is actual code I have for a hobby project. It's an AI implemented with Lua coroutines. To keep it small, not all functions have been defined, but I've kept everything that deals with coroutines.
function resume(entity)
if not entity.coroutine then
entity.coroutine = coroutine.create(function()
return entity:runAI()
end)
end
coroutine.resume(entity.coroutine)
end

function Entity:moveTowards(x, y)
local dx = sign(x - self.x)
local dy = sign(y - self.y)
local dir = getDirection(dx, dy)
if dir ~= -1 then
TryMove(self.entity, dir)
coroutine.yield()
end
end

function Entity:moveTo(x, y)
while self.x ~= x or self.y ~= y do
self:moveTowards(x, y)
end
end

function Entity:attack(dx, dy)
local dir = getDirection(dx, dy)
if dir ~= -1 then
TryAttack(self.entity, dir)
coroutine.yield()
end
end

function Entity:chasePlayer()
while true do
local distance = self:distanceToPlayer()
if distance > 8 then
break
end
if distance <= 2 then
local dx = px - self.x
local dy = py - self.y
self:attack(dx, dy)
else
self:moveTowards(px, py)
end
end
end

function Entity:patrolTo(x, y)
while self.x ~= x or self.y ~= y do
local distance = self:distanceToPlayer()
if distance <= 5 then
self:chasePlayer()
else
self:moveTowards(x, y)
end
end
end

-- Populate world with deadly enemies
local entity = Entity:new(20, 10)
function entity:runAI()
while true do
self:moveTo(20, 8)
self:moveTo(20, 12)
end
end
addEntity(entity)

local entity = Entity:new(15, 15)
function entity:runAI()
while true do
self:patrolTo(15, 15)
self:patrolTo(15, 10)
self:patrolTo(10, 10)
self:patrolTo(10, 15)
end
end
addEntity(entity)

As you can see, each entity type can be written by using very high level
constructs, which themselves are defined by simple logic and calls to lower level
functions. This lets you write an AI as if it was running in its own thread,
but in reality, the game engine only calls the resume-function for each entity
on its main thread.

Without coroutines, you'd have to resort to writing a state machine instead,
which can be more painful to write and maintain.

Now, I've tried converting this to Python to see what it would look like.
This was my first iteration, which won't run because the generators itself
don't contain the actual yield-call.
def resume(entity):
if entity.coroutine == None:
entity.coroutine = entity.runAI()
return entity.coroutine()

class Entity:
def __init__(self, x, y):
self.x = x
self.y = y

def moveTowards(self, x, y):
dx = sign(x - self.x)
dy = sign(y - self.y)
dir = getDirection(dx, dy)
if dir != -1:
TryMove(self.entity, dir)
yield

def moveTo(self, x, y):
while self.x != x or self.y != y:
self.moveTowards(x, y)

def attack(self, dx, dy):
dir = getDirection(dx, dy)
if dir != -1:
TryAttack(self.entity, dir)
yield

def chasePlayer(self):
while True:
distance = self.distanceToPlayer()
if distance > 8:
break
if distance <= 2:
dx = px - self.x
dy = py - self.y
self.attack(dx, dy)
else:
self.moveTowards(px, py)

def patrolTo(self, x, y):
while self.x != x or self.y != y:
distance = self.distanceToPlayer()
if distance <= 5:
self.chasePlayer()
else:
self.moveTowards(x, y)

# Populate world with deadly enemies
class Runner(Entity):
def runAi(self):
while True:
self.moveTo(20, 8)
self.moveTo(20, 12)
entity = Runner(20, 10)
addEntity(entity)

class Patroller(Entity):
def runAi(self):
while True:
self.patrolTo(15, 15)
self.patrolTo(15, 10)
self.patrolTo(10, 10)
self.patrolTo(10, 15)

entity = Patroller(15, 15)
addEntity(entity)
Now, let's try refactoring until all yields are in the actual generator.
To do this, we could either simply inline all the functions that would yield,
until they're all in the runAi-method. The problem with this is a lot of
duplicated code, so that's not a good option.

Another way would be to only have the yields in the runAi, and let the currently
yielding functions return some value instead. The problem with that is that we
lose the knowledge of where to resume from, and thus we have to build some sort
of state maching to remember it, which would remove the point of having
coroutines in the first place.

If anyone can see a good way of refactoring that Python code (I am fairly new
to Python after all) to work as a coroutine, please let me know!

Until then, I'll just assume that python coroutines are inferior to Lua's. ;-)

[Here's an interesting article about coroutines: http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf ]

Python annoyance - scoping

I recently tried writing a small program in Python, and I have to give it credit here - it was pretty easy to get started, using the online language reference and standard library reference for help.

One thing I stumbled over was a subtlety in the scoping that I didn't expect. Here's an example:
foo = 123
def fun():
print(foo)
fun()
print(foo)
This prints 123 and 123, as you would expect. This implies that function blocks can access variables in outer blocks. Let's try another example:
foo = 123
def fun():
foo = 456
print(foo)
fun()
print(foo)
This prints 456 and 123. This means that assignment of a variable in a function doesn't assign the outer variable. Instead it creates a new variable local to the function block. Let's look at the final example:
foo = 123
def fun():
print(foo)
foo = 456
print(foo)
fun()
print(foo)
I can think of two reasonable ways to interpret this:
  1. First print 123 (from the outer block), then 456 (creating a new variable in the function block), then 123 (outer block variable unchanged)
  2. First print 123 (from the outer block), then 456 (modifying the outer variable), then 456.
Instead, Python throws an error:
UnboundLocalError: local variable 'foo' referenced before assignment
This means that Python actually inspects the entire function and searches for assignment operations. If it finds any, it creates a new local variable. If it doesn't, it refers to the outer.

You can override this behaviour by doing this:
foo = 123
def fun():
global foo
print(foo)
foo = 456
print(foo)
fun()
print(foo)
This forces python to only refer to the outer variable instead of creating a new. This outputs 123, 456, 456.

The annoyance is that Pythons automatic choice between "read outer" and "create new local" comes from inspecting the entire function, which means that an assignment at the end of the function can create an error at the first line of the function, which can be very confusing for a beginner.

I think a better solution would have been to always have outer by default, except for in loops and function parameter definitions. You could then add the keyword "local, my, var or val" for when you really want to create a new local variable (like lua, perl, javascript, scala et.c. does).

Friday, June 18, 2010

Symmetric getters and setters

Using getters and setters is a very common pattern for classes in Java projects. In general, I think they should be avoided, especially since setters eliminates the possibility of having final fields. Also, blindly adding getters to your classes is a bad idea since you expose implementation details to the outside world. Of course, some times you do no need them, and the rest of this post assumes that you do.

Sometimes you want to do some preprocessing on the inputs to the setters, to support cases where the input is out of range or other things of that nature. For instance, your domain objects may have a requirement that the values of the field should be in a specific range. You can then either:
  • Throw an illegal argument exception - if the ranges are clearly defined and the caller should know them, this is a valid approach.
  • Silently clamp the input value to be inside the range. This can sometimes be the desired approach, but it ultimately depends on the system.
  • Accept the value as it is, and just hope that the callers behave nicely. This is usually not a good idea, and should only be done if you control all the callers and its in a cpu critical section of the code.
There is a symmetry law which I think should hold for pairs of getters and setters.
Note that is a completely personal opinion. I don't expect everyone to agree with it. It's a good thing this blog is also completely personal!

Anyway, here is the law:
Values provided from a getter should be legal values when calling the setter, and if you run the following code, then x and y should be equal:

x = obj.getFoo();
obj.setFoo(x);
y = obj.getFoo();
assert x.equals(y);


For simple getters and setters that just uses a single field, this obviously always holds, even if the setters throws exceptions on bad values, or clamps the values out of range. This probably one of the reasons that many people assume that this symmetry usually holds.

However, sometimes the getters and setters don't really correspond to a specific field, but instead triggers other code to be modified. In this case, it's not clear that the symmetry holds.

for instance, you may have something like this:

public class Foo {
private final Bar bar;
public void setValue(int value) {
bar.setValue(value);
}

public int getValue() {
return offset + bar.getValue();
}
}

This is clearly asymmetric, so how do you fix it?
You could try something like this, but it's very prone to error, depending on how bar.setValue is implemented:

public void setBar(int value) {
bar.setValue(value - offset);
}


A better option is to remove the setter entirely and expose the bar object directly. I don't think anyone would take for granted that foo.getBar().setValue(...) needs to be symmetric with foo.getValue()

Yet another variant is simply renaming setValue to setBarValue (or setBaseValue or setDelegateValue, or something else, depending on the context) - this simple transformation also makes it clear that it's not symmetric.

Kahlua on Android

Yes, that's right, Kahlua supports Android (or Android supports Kahlua, depending on how you see it). And it worked surprisingly easy. All in all, I spent two hours installing the Android SDK, reading the Android documentation and creating an example program that used Kahlua. I even managed to create a very simple interpreter. And it didn't just load the Kahlua core, it also supports the J2SE extensions. It was almost out of the box, and I'll expand on that later.

This was a great success, and I attribute it to the following reasons:
  • The Android SDK is really polished. It was easy to install, easy to get started, and the documentation was pretty good!
  • Kahlua (core and J2SE) is compatible with the same subset of Java 5 that Android supports.
As far as I can tell, the classes in Android are fully compatible with Suns Java classes; at least I haven't found any bugs in Kahlua on Android yet.

The only problem I had was that I got a NoSuchMethodError when invoking Arrays.copyOfRange. It turns out that this method was introduced in Java 6, which explains why Android didn't support it. I simply converted the code into using the old and trusted System.arrayCopy and the code worked!

The Android interpreter even supported the reflection- and annotation-based exposing of Java methods, which I demonstrated by exposing a method that called Thread.sleep. (This was also useful for testing that the UI components in Android worked correctly while executing a script.)

The Android Kahlua interpreter is checked in to the git repository for Kahlua2, if anyone is interested in seeing it. It is basically a single Java file in 148 lines of code.

Sunday, June 6, 2010

Automated tests for content

Games are generally considered to consist of code and content.
  • The code is the game engine that defines all the rules of the game, input handling, network, graphics rendering, and so on.
  • Content in a game includes a lot of things: textures, sounds, level designs, ai, animations, meshes, dialogues and more.
Another (less formal) way of looking at it is that code is the part of the game produced by the programmers, and content is the part of the game produced by artists, game designers or level designers.

Programmers are used to writing tests for their code (if they're using TDD, they're even writing some, if not all, tests before they write the code), but content creators generally are not. They instead rely on manual testing, both by themselves and by gameplay testers.

Why is code tested and not content?
I think the code is what makes the game robust, coherent and logical. It's easy to detect broken code - broken code either crashes or behaves incorrectly. This makes it feasable to write tests for the code.

Content on the other hand is harder to verify automatically. How can a machine decide that a texture is broken? We could certainly verify that the texture has the correct dimensions and correct color depth, and other properties needed for the game engine to support it. We should have tests to verify the integrity of the content to as large extent as possible, and I think we do.

The things we can't verify automatically is the fun and the user experience.

The corner case
This was just the setup. Now for one of the corner cases, the parts that can be considered both code and content: AI!

AI is definitely a part of the content. Meeting unique non-player characters (NPC) with custom AI adds a new user experience that is something unknown, and therefore possibly exciting. The AI however is also expressed in some sort of code, either as a script in some embedded language, as a behaviour tree or behaviour stack.

The problem with AI as code, is that it tends to mutate at a much faster pace than game engine code. AI is driven by the content around it, not technical demands, and so it must change often.

Writing tests for each individual AI is expensive, since fully testing all the possible code paths can require a lot of manual setup, and verifying correctness is also tricky for a suffiently complex AI. What's worse, the test is bound to be very fragile, since content makers like to tweak and redo AIs if it's too easy, too difficult or simply not fun enough.

Should content like this be covered by automated tests? To some extent, definitely! I am not convinced that content should be tested individually, but testing the content by type is quite useful to detect errors.

For AIs this could mean:
  • Running automated smoke tests that run the AI characters for a long time (game time, not real time) to increase the chance of running many code paths (possibly with the AI opponent doing random moves) and simply checking that it doesn't crash. This type of test could apply to most if not all AI. It would be cheap to implement, and probably be fairly stable.
  • Smoke testing the AI with measurements of key values, such as damage output, movement speed, actions per minute, et.c. and check that the values are in a sane range. If some of the values are zero, this would indicate that the AI is blocked somewhere and one of the code paths is never run, and extremely high values would indicate that the AI is stuck in one of the code path loops.
Conclusion
You should always consider the cost versus the gain of writing tests. For game engine code, the gain is almost always greater than the cost, but for content it's not as clear.
You should also consider how to test something. A small unit test is suitable for many parts of code development, but it's probably overkill for content (which tends to change a lot).
If you can write one or a few tests that can verify something about a specific content type, and apply the test to all the content, the gain will quickly become large, since you can scale up the size of the content without scaling up the number of tests.

Friday, June 4, 2010

More details of the exposer

As I said before, there is more to the exposer than I wrote before.

Lua is, as you already know, a language that supports multiple return values. Java however does not, and that makes integration slightly less straightforward.

It is not obvious how to do it, but it is possible to expose Java methods and have them return multiple values.

Exposing multiple return values
The workaround is to create your java method like this:
@LuaMethod
public void getUnitLocation(ReturnValues rv, String unitName) {
Unit unit = service.getUnit(unitName);
rv.push(unit.getX());
rv.push(unit.getY());
}
You can then use the function like this:
local x, y = getUnitLocation("theUnit")
This looks a lot like how it's done using a raw JavaFunction, you might exclaim! This is not by coincidence. In fact, ReturnValues is just a thin layer on top of the original LuaCallFrame.

In order for this to work, the exposer mechanism performs special handling if the first parameter of the method is of the type ReturnValues.

Varargs
If the java method is a vararg method, i.e. defined like this:
public String concat(String... strings) {
return Arrays.toString(strings);
}
then Lua scripts can call it with concat("a", "b", "c") and get "[a, b, c]" back. This may seem obvious and it should be, but I'll mention it anyway.

Error handling
What if you do something wrong, such as calling getUnitLocation(), thus not passing in the name? The exposer will detect an incorrect number of arguments and throw an error message at you.

This however, is ok: getUnitLocation("theName", "something else"). The exposer will simply disregard the extra parameter. You may expect it to similarly throw an error, but this is in fact in line with how Lua generally handles too many arguments.

If you supply the incorrect type, you'll also get an error (unless the type can be converted to the Java type of course). If you supply nil, it'll go through into the method - so you have to add the null checks yourself.

Method overloading
I mentioned method overloading earlier, and that the exposer can handle it to some extent. I'll clarify that here.

Assume you have the following class:
public class Example {
public void myMethod() {
}
public void myMethod(Object a, Object b, Object c) {
}
public void myMethod(String a, String b) {
}
public void myMethod(int a, int b) {
}
}
If all these methods are exposed, the exposer will detect that it's already been exposed, and will convert the generated JavaFunction to a dispatching JavaFunction.
This dispatcher will inspect the arguments passed in the call to try to determine which method to call. The actual algorithm for selecting is very naive, but most likely good enough for almost all cases. In any case, you shouldn't use overloading too much - that's bound to confuse your users.

The dispatcher first sorts the list of matching methods by decreasing parameter count. Varargs count as zero. In our case, this means the following ordering:
public void myMethod(Object a, Object b, Object c);
public void myMethod(String a, String b);
public void myMethod(int a, int b);
public void myMethod();
The middle two have the same number of parameters, and thus can occur in any order.
When getting a call, it simply goes through the list in order and tries to call it. If it can't be called, it simply tries the next.
A call like myMethod("a", "b") will fail the first method, since it doesn't have enough arguments, but it will match the second.
myMethod("a", 123) won't match 1, 2 or 3, but it could be reduced to the 4th.
myMethod(nil, nil, nil) will match the first (since nil matches all types).

Methods and functions
What is a method? What is a function?

I'd like to define method as a function that's associated with an object. In Java, all instance methods falls under that definition of method. Static methods in Java can be considered functions, since they are not associated with specific objects.

Real methods don't really exist in Lua - all functions are plain functions. However, you can simulate methods easily. There is a simple syntactic sugar in Lua for this:

Sugar for a method definition:
function obj:method(args...)
end
is equivalent to:
function obj.method(self, args...)
end
That means that in the first case, it simply injects a new local variabel "self" assigned to the first argument.

Similarly, there is sugar for a method call:
obj:method(args...)
is equivalent to:
obj.method(obj, args...)
which of course is a regular function call.

This also how the exposer differentiates between methods and functions. If it's annoted with @LuaMethod(global = true) or is static, it's a function, and arguments are passed straight through from Lua to Java.

If global = false (which is the default), the first argument is consumed by the exposer and used to find the actual object to invoke the method on, and it's not passed along to the method.

Thursday, June 3, 2010

Differences between Kahlua2 and Lua 5.1

There are some noticable differences between Lua 5.1 and Kahlua2, and it may be good to know what they are.

Tables
Tables in Kahlua2 are implemented using a backing Hashtable or ConcurrentHashMap and as a result, implementing "next" properly would be inefficient and instead of implementing "next", it was removed. The function "pairs" still works, so use that instead. One common idiom using next in Lua 5.1 was checking if a table is empty:
function isempty(t) return next(t) == nil end


An alternative implementation of that in Kahlua2 would be:
function isempty(t) return pairs(t)() == nil end

but it would be inefficient, since it would create an iterator for each call to isempty.

Instead, you can use the method table.isempty(t) in Kahlua2.

Another side effect of using Java maps to implement tables, is that key equality is slightly different between Lua 5.1 and Kahlua2. In Lua 5.1, keys are equal in a table if they refer to the same object while in Kahlua2 they are equal if their hashcodes are equal and their equals()-methods return true. For strings, it works just as in Lua 5.1, but for numbers it's slightly different. Java treats -0 and +0 as different keys while Lua treats them as the same.

tostring
When converting things to strings in Kahlua2 (for example when calling tostring(obj)), it will not just return "userdata" if it doesn't have a better guess, it will instead use the toString() method for the object.

Weak tables
Kahlua2 doesn't support the __mode = "[k][v]" metatable magic to create weak tables. If you need weak tables, consider exposing a new method for creating a KahluaTable backed by a WeakHashMap or something similar.

Kahlua2 doesn't support the __gc feature for metatables, since there is no good way in Java to get notified when an object is about to get garbage collected. If you need this functionality, consider putting the object in a SoftReference to manually check when it's collected.

Libraries
Kahlua2 does not include any io or debug library. Some parts of the debug library may be added in the future, but the io library is better left added as a custom extension if necessary. The same thing goes for the os library, which is only partially implemented.

xpcall
Kahlua2 doesn't implement xpcall yet, but it might come in the future.

random and randomseed
random and randomseed in Lua uses a mutable global state, which is undesirable in Kahlua2.
Instead, use the following:
local myrandom = newrandom()
myrandom:random() -- real number in the range 0 to 1
myrandom:random(max) -- integer number in the range 1 to max
myrandom:random(min, max) -- integer number in the range min to max
myrandom:seed(obj) -- seeds the random instance with the hashcode of the object.

Wednesday, June 2, 2010

Kahlua - the J2SE goodies

In this post, Lua will generally refer to the language specification, whereas Kahlua will refer to this actual implementation so don't be confused when I talk about Lua scripts running under Kahlua.

The goodies
Kahlua has a couple of useful extensions that makes your life as a developer easier when integrating Kahlua into your applications. Some of them depend on each other, so I'll go through them in dependency order to make the reading more digestible.

Converting objects
Since Lua only has a few built in types (String, Double, Boolean, KahluaTable) and Java has many many more types, it's sometimes useful to automatically convert types when going back and forth between Lua and Java.

For instance, if Java were to send an Integer object to Kahlua, that object would just be an opaque reference, without any operations. If we instead convert it to a Double, Kahlua can work with it without any problems. This is the rationale for introducing the first J2SE goodie - the KahluaConverterManager.

This is a class that can help you convert types back and forth between Lua and Kahlua. By itself, it can't convert anything at all, but you can register actual converters with it. For convenience, a couple of generic converters are bundled with Kahlua and you can also write custom converters if you need to.

The converter manager has two conversion methods: fromLuaToJava and fromJavaToLua.
Converting from Lua to Java takes an object and a Java class.
The converter manager then uses the type of the object and the Java class to determine which converter best matches the conversion. If nothing matches it returns null instead.

Converting from Java to Lua is different - it doesn't have a target type, since Lua is dynamically typed. Instead the converter just looks at the Java type to choose converter. If no suitable converter is found, it returns the object as it is.

Here are the already existing converters:

The number converter
Registering the number converter allows you to automatically convert Lua numbers (which are implemented as Double) to the numeric types in Java (int, long, char, byte, short, float, double).

It also works the other way around, converting the numeric types in Java to Double.

The table converter
This one also converts both ways. KahluaTable instances can be converted both to List and Map, and Lists and Maps can be converted back to KahluaTable. It also converts maps recursively, so be careful to avoid converting cyclic structures.

The enum converter
You can also convert enums to their string representations (enum.name()) and back, which means that you can
call Java methods that takes an enum just by passing in a string that matches one of the enums.

Calling Lua from Java
LuaCaller.protectedCall is a utility method that simplifies the usage of thread.pcall. Instead of returning a raw array where the first return value always is true or false, it returns an abstraction that hides the details: the LuaReturn class.

LuaReturn has the methods isSuccess(), getErrorMessage(), getStacktrace(), getJavaException() which makes it easier to use than extracting result[0] (and 1, 2, 3, respectively).

LuaCaller.protectedCall additionally applies the installed converters to the inputs before the call. It doesn't apply it to the return values, because it doesn't know which types it wants.

Calling Java from Lua
Be prepared - here comes the most advanced, the most useful and simply best feature of the J2SE goodies.

The LuaJavaClassExposer is a class that eliminates the need to manually define JavaFunction implementations for things that you want to expose to Lua.

Imaging writing a simple game, which is scriptable with Kahlua, and you want to be able to query a game units health from the Lua script.
Without the exposer, you'd have to write something like this:

public class GetUnitHealth implements JavaFunction {
public int call(LuaCallFrame callFrame, int nArguments) {
if (nArguments < 1) {
throw new IllegalArgumentException("Expected at least one argument");
}
Object arg = callFrame.get(0);
if (arg == null || !(arg instanceof String)) {
throw new IllegalArgumentException("Expected a string argument but got " + arg);
}
String s = (String) arg;
Unit unit = unitService.getUnit(s);
callFrame.push(unit.getHealth());
return 1;
}
}

Using the exposer instead, you can write something like this:

public class UnitFunctions {
@LuaMethod
public int getUnitHealth(String unitName) {
Unit unit = unitService.getUnit(unitName);
return unit.getHealth();
}
}

It removes a lot of the boilerplate right? The exposer takes care of all the conversions and argument matchings for us!

Instead, you can write an ordinary method in any class, and let the exposer expose that class. One JavaFunction per method will be created, and the method will be available in Lua. The generated JavaFunction will automatically use the installed converters which makes it really easy to integrate the Java and Lua code.

There are basically two different styles available when exposing:

Exposing like java
The first style is exposing things to work almost the same as in Java.
You simply call exposer.exposeLikeJava(yourClass, staticBase).
After that, a Lua script may call obj:yourMethod(arg1, arg2, ...) if obj is of type yourClass and yourMethod is a method in yourClass.

You may be wondering what staticBase means (and if not, you're not paying enough attention). A method are only available for the object if it's a regular java method.
Static methods and constructors can't be used this way. Instead, Kahlua uses the staticBase argument, which is a KahluaTable, to fill up with methods that don't belong to specific objects. If you expose the class java.util.Date, then the constructors will be available as:
staticBase.java.util.Date.new
and static methods such as parse are available as:
staticBase.java.util.Date.parse

If the class name is unique enough, it is also available directly from the staticBase root, such as staticBase.Date

These static methods and functions are what I call functions instead of methods.
Instead of invoking them with obj:method, do it like this:

local unixTimeStamp = 123
local dateObject = staticBase.java.util.Date.new(unixTimeStamp)
local dateObject = staticBase.Date.new(unixTimeStamp)
local NewDate = staticBase.Date.new
local dateObject = NewDate(unixTimeStamp)

Any of those would work.

You can also use exposer.exposeLikeJavaRecursively(yourClass) which works the sam but additionally it also exposes all other classes that yourClass interacts with in any way. This can be useful if you want to avoid manually setting up a lot of exposing, but don't use it when dealing with untrusted code.

Annotation based exposing
For untrusted code, or simply when you need more custom configuration, consider using the annotation based exposing instead.

Use one of these methods to expose a class or objects by using annotations:
exposer.exposeGlobalFunctions(object) and exposer.exposeClass(class),

Exposing global function takes an actual Java objects and scans it for method annotations. All methods which are marked as global will be exported to Lua as functions, implicitly bound to the object. This means that you should not use the obj:method() notation of invoking them, just use method().

Exposing a class instead creates Lua methods for objects of the class, and also exposes static methods as function, if they're marked as global.

The available annotations are: @LuaMethod and @LuaConstructor.

@LuaMethod has two optional parameters. "name" gives you the option to expose
the method with a different name. If this is left out, it uses the method name. The second parameter is "global" which can be true or false. True means that the method will be exposed as a function, and false means that it will be an object method. False is the default.

@LuaConstructor similarly takes a "name" parameter.
Note that it doesn't take a "global" , since constructors are never bound to an object; they are always implicitly global.

Overloading
Java supports method overloading based on parameter types, but since functions are first class objects in Lua, it can't support overloading. However, the Kahlua exposer can detect overloaded Java methods and create a limited form av overloading by creating a function that can call any of the overloaded Java methods.
Kahlua then uses the parameter types to try to invoke the method that best matches the supplied arguments.

Here are some concrete usage examples:

public class Vector {
private final double x, y, z;
@LuaConstructor(name = "newvector")
public Vector(double x, double y, double z) {
this.x = x;
this.y = y;
this.z = z;
}

@LuaMethod(name = "length")
public double length() {
return Math.sqrt(x*x + y*y + z*z);
}
}


If this class were exposed by exposer.exposeClass(Vector.class), then Lua scripts could use it like this:

local v = newvector(3, 4, 0)
local len = v:length()
assert(len == 5)

The other method is mostly useful for service-type features:

public class NetworkService {
private final Pinger pinger;

@LuaMethod(name = "ping", global = true)
public int ping(String host) {
return pinger.ping(host);
}
}
exposer.exposeGlobalFunctions(new NetworkService());

Used as:

local pingTime = ping("localhost")
That's it for this time! I could probably go on more in depth with the advanced features in the exposer, but this should already be enough for you to digest.

Time for you get started with embedding Kahlua in your Java application, and let me know how it works out! Feedback is always appreciated.

Friday, May 28, 2010

Getting started with Kahlua2

This post contains some words and acronyms that are good to know about.
  • J2SE - Java 2 Standard Edition - is the Java version that is available on desktops. Kahlua core depends on J2SE 1.4 or higher, while the J2SE extensions require J2SE 1.5 or higher.
  • CLDC - Connected Limited Device Configuration - is a slimmed down version of Java, with many features removed. Kahlua requires CLDC 1.1 or higher to work.
  • Midlet - Application for mobile devices using CLDC (and MIDP, but let's not go too deep).

Kahlua2 is built with a modular design.
This means you can configure your system the way you want it but it also means that there are some basic things that need to be set up to get started.

The platform
First of all, you need a Platform.

The core of Kahlua2 has some dependencies that are platform specific. For instance, Kahlua2 needs to be able to create tables, and the table implementations are different for J2SE and CLDC 1.1. They are backed by ConcurrentHashMap and Hashtable respectively.
For that reason, Platform has the method:
KahluaTable newTable();


Fortunately for you, getting hold of a platform is easy!
Just call J2SEPlatform.getInstance() or CLDC11Platform.getInstance().
These platform implementations are immutable, so don't worry about sharing the platform with others.

Typically you want to use CLDC11Platform for writing midlets and J2SEPlatform for everything else. If for some reason, neither of these platforms suit your purposes, you can simply create your own.

An environment
The global scope in Kahlua (as well as in Lua) is just a regular table. The compiler makes sure to translate any variable that isn't declared as a local to a lookup in the environment table.

If the environment is just a regular table, can we simply create one by calling platform.newTable()? Yes! That works perfectly well.

However, this environment will be empty, so you can't find the standard library functions in it, and most of the scripts you want to run probably needs a couple
of standard functions to do anything interesting.

An alternative way of creating an environment is to call platform.newEnvironment(); This creates a new table, but also populates it with useful stuff. J2SEPlatform for instance loads the environment with BaseLib, MathLib, RandomLib, StringLib, CoroutineLib, OsLib, TableLib and the compiler.

If you're curious, take a look inside J2SEPlatform, it should be easy to follow.

Compiling scripts
Having an environment is not very exciting in itself, you probably also want to run some scripts! Kahlua has two ways of creating closures (or functions) for these scripts. The easiest and best way is to use one of the static methods in LuaCompiler; use loadstring if you have the input as a string, and loadis if you have an inputstream or reader. All closures needs environments, so you need to pass in your environment as the last parameter (or another environment if you prefer).

Note that the compiler will throw a KahluaException (which is a RuntimeException) if the script is malformed. You should be prepared to handle it.

The other option is to load the bytecode directly. This is mostly useful on devices where you dont want to bundle the full compiler, such as limited mobile devices. The solution is to compile the scripts offline, either with the standard luac bundled with Lua, or with Kahluas own Java class called LuaC. The resulting binary file can then be loaded with KahluaUtil.loadByteCodeFromResource.

The thread
With a platform, an environment and some closures, you're almost set to start running your scripts, but there is one more thing needed - a thread to run them in.
KahluaThread t = new KahluaThread(platform, env)

is all you need to create a thread.

Kahlua is concurrent in the way that you can create multiple threads that reference the same environment, but don't try to run scripts on the same KahluaThread from different Java threads! Things would blow up in mysterious and unexpected ways.

The most basic way of invoking your closure is by using thread.call(closure, args...). However, if the closure invocation should throw an error, a RuntimeException will propagate out to the Java code. A safer option is to use thread.pcall(closure, args...) which traps all Lua errors and returns the error information as part of the return values.

For J2SE, there are few more ways of invoking closures, but more on that in a later post.

Java functions
Most applications that use an embedded script engine have a need for the scripts to access domain specific functions. If I were to write a game engine, then my AI scripts might need a way to execute orders. So the opposite of Java invoking Lua scripts is needed; we need to be able to call Java methods from Lua.

There are several ways of doing this in Kahlua, but they all boil down to this core functionality:

interface JavaFunction {
int call(LuaCallFrame callFrame, int nArguments);
}


Kahlua can call any object that implements this interface. This is how all of the standard library in Kahlua is implemented. This is also the only way to do it in CLDC 1.1, due to lack of a reflection API.

The parameters to call is a callframe, which contain the arguments passed to the function, and the number of arguments. The return value of call should be the number of return values, since Lua supports multiple return values. The return values themselves need to be pushed on the Kahlua stack, and there are convenience methods for that in the LuaCallFrame object.

Here is a simple example a JavaFunction implementation intended to be used like this:

local x, y = GetUnitLocation("The unit name")


public class GetUnitLocation implements JavaFunction {
public int call(LuaCallFrame callFrame, int nArguments) {
if (nArguments < 1) {
throw new IllegalArgumentException("Expected at least one argument");
}
Object arg = callFrame.get(0);
if (arg == null || !(arg instanceof String)) {
throw new IllegalArgumentException("Expected a string argument but got " + arg);
}
String s = (String) arg;
Unit unit = unitService.getUnit(s);
callFrame.push(unit.getX());
callFrame.push(unit.getY());
return 2;
}
}

Due to the dynamic nature of Kahlua, there needs to be a lot of boilerplate error checking, but the rest of the implementation is straight forward.

Exposing things
Just having a JavaFunction implementation is not enough - it needs to reach the lua scripts in order to be useful. This can be done in several ways. The first, and most obvious, is to put it in the environment:

environment.rawset("GetUnitLocation", new GetUnitLocation());


The lua script can then call it by just doing:
GetUnitLocation("the unit name")


The lua script can also copy it somewhere, redefine it - "GetUnitLocation" is just a key in a table, and can be manipulated like any other object, so you can do things like this:
fun = GetUnitLocation
fun("the unit name")

or
local oldfun = GetUnitLocation
function GetUnitLocation(s)
print("calling GetUnitLocation here")
return oldfun(s)
end

Conclusion
That's all you need to know to get started with Kahlua. It may seem like there was a lot of steps involved, but each step is really very simple.

For mobile platform targets, there isn't much more to add but for J2SE users there are additional goodies available, which I'll go over some time in the near future.

Tuesday, May 25, 2010

Half baked objects

A half baked object is an object that after construction is still not ready to use.
Using it will either just silently behave badly (that's bad) or throw a usage exception (that's less bad).

This is a really irritating code smell, because it makes it much too easy to introduce bugs. The best APIs I've used have made it impossible (or atleast very difficult) to use it incorrectly because once they've given me an object to work with, they've guaranteed that they're set up properly and are ready for action.

There are some generic rules you can use to avoid having half baked objects:
  1. Set up everything in the constructor. This is not always possible, but when it is, do it.
  2. Use final fields - they enforce you set up everything in the constructor, which reduces the risk for bugs. Note that final fields in itself doesn't make the object immutable, you can still have final lists, maps and sets in your object, which themselves are mutable.
  3. Use builders - and don't allow creating the real object until the builder has all the necessary requirements.
  4. Be suspicious of methods named things like "init", "postconstruct", "setup" or similar. They could be indicators of a half baked object.
However, I have found one case of needing half baked objects, and I currently don't have any workaround for it.
This is a new feature in Mockachino, where I want to create an alias for a combination of a mock object and a method signature.
Since I can't pass a method signature as a parameter in Java (without using icky reflection) my only choice is to capture the method invocation and record it in the Alias.


interface Foo {
foo(int n);
}


Foo mock = mock(Foo.class);

mock.foo(123);

SimpleAlias alias = newAlias(); // alias is half baked here - it's not bound to any mock

alias.bind(mock).foo(anyInt()); // now alias is fully setup

alias.verifyOnce();


This is one of few cases where half baked objects is hard to avoid, but if anyone has any clever suggestions, I'm all ears.

Temporal testable code

A lot of code is time dependent. Code either needs to wait or timeout for a specific amount of time, or it needs to fetch the current system time for some reason.

If the code uses Thread.sleep(), System.currentTimeMillis(), new Date(), or anything like that, it has a hidden and implicit dependency. This can be a problem when you're trying to write tests for such code.

The tests usually end up with a lot of:

Thread.sleep(1000); // wait for code to finish doing its job.

This will make your test suite unnecessarily slow to run, and you want your tests to finish almost instantly.

The solution is to convert this implicit dependency to an explicit!
This is done by creating the following interface:

public interface TimeProvider {
long now(); // Replaces System.currentTimeMillis();
sleep(long timeInMilliSeconds) throws InterruptedException; // Replaces Thread.sleep
}


All the code that is time dependent in any way should inject an object of this interface.
Now, you need two implementations of this interface, one for real usage and one for testing. Fortunately, these are trivial to write:


public class SystemTimeProvider implements TimeProvider {
@Override
public long now() {
return System.currentTimeMillis();
}

@Override
public void sleep(long timeInMilliSeconds) throws InterruptedException {
Thread.sleep(timeInMilliSeconds);
}
}

public class MockTimeProvider implements TimeProvider {

private long now;

public void setNow(long now) {
this.now = now;
}

public void advanceTime(long amountInMillis) {
now += amountInMillis;
}

@Override
public long now() {
return now;
}

@Override
public void sleep(long timeInMilliSeconds) {
now += timeInMilliSeconds;
}
}


For the real application, everything will behave the same.
For testing purposes, just inject the MockTimeProvider instead, and manually manipulate the time.

Here's simple example to illustrate how this works in practice.
Basically we want to ensure that when we generate UUIDs, a specific part of the UUID remains the same if two UUIDs are generated close enough temporally, but different if there's a small time difference:


public class UUIDTest {
private final MockTimeProvider mockTimeProvider = new MockTimeProvider();
private final UUIDFactory factory = new UUIDFactoryImpl(mockTimeProvider, new SecureRandom());

@Test
public void combTest() throws InterruptedException {

mockTimeProvider.setNow(0);
UUID firstUuid = factory.combUUID();
UUID secondUuid = factory.combUUID();

assertFalse(firstUuid.equals(secondUuid));
long combPart1 = getCombPart(firstUuid);
long combPart2 = getCombPart(secondUuid);
assertEquals(combPart1, combPart2);

mockTimeProvider.advanceTime(20);

UUID thirdUuid = factory.combUUID();
long combPart3 = getCombPart(thirdUuid);
assertFalse(combPart1 == combPart3);

}

private long getCombPart(UUID uuid) {
String combString = "0x" + uuid.toString().substring(24, 36);
return Long.decode(combString);
}
}
Stop using static ways of using time in your code!
Using an injected TimeProvider works almost identically if it's a SystemTimeProvider, so the only cost is a slightly more costly method invocation since it's through an additional abstraction layer.
But the benefits are huge! Your code will be more testable, and the dependency on time is no longer hidden.

Friday, May 21, 2010

The history of Kahlua

In 2007, there was really only one alternative if you wanted to run Lua on Java.
LuaJava implements a native binding from Java to the real Lua,
which requires you to bundle a platform specific library with your Java application.

This meant that the integration with Java wasn't as easy to use as it could have been - the memory spaces were completely separated, just like the memory space of regular Lua is separated from C.
It also meant that Lua on J2ME devices was complete out of the questions - you're not allowed to bundle native libraries in J2ME applications, and even if you did,
they would probably be much too large.

So I thought it would be a fun idea to implement a pure Java implementation of Lua to see how similar it would be. I figured that it wouldn't be too much work, since several data types in Lua would be easily mapped by existing classes in Java:
  • strings, numbers and booleans in Lua could be implemented by the String class, Double class and Boolean class respectively in Java. These types are immutable in both languages and have the same behaviour, which
    makes it a good fit.
  • the special value nil was trivially mapped to null in Java.
  • tables can be implemented as a plain Java class.
  • java functions (a Java object implementing a specific interface).

Regular Lua implements sophisticated memory management with garbage collection. This is completely avoided in Java by just using the same memory space and taking advantage of the built in garbage collector in the JVM.

Error handling in Lua were adapted similarly, by simply mapping Lua errors to Java RuntimeException.

Kahlua was originally written with the goal of implementing the basic virtual machine for running Lua bytecode. There were no plans for having a compiler or supporting advanced features such as coroutines. It was aimed at both J2ME and J2SE, and thus only supported the common subset between the two - CLDC 1.1.
Since the project goals were fairly modest, and the actual virtual machine can be written fairly simple and straightforward, it didn't take long until Kahlua could load bytecode compiled from the regular Lua and run it with a limited implementation of the base library.

After the success of having the toy project actually work, I set out to implement more of the advanced features of Lua - Upvalues, coroutines, weak metatables and the complete string library. Getting all this to work took some time, but it ended up quite compatible with Lua.

Soon after that, I started working on a hobby J2SE game project, and thought it would be fun to start using Kahlua as a scripting language there. Kahlua worked nicely there, but it relied on external compilation so we had to either precompile scripts with the commandline luac or make a JNI binding to the lua library. We started with the precompiling, but once we realized that we needed hot reloads,
doing the second approach was unavoidable.

Within the next couple of years after the initial release of Kahlua, several other pure Lua implementations emerged.
First after Kahlua, I think, was Mochalua which was also aimed at J2ME and had more core functionality for directly interacting with MIDP instead of just CLDC, which unfortunately made it harder to use in J2SE. Mochalua was more of a direct port of the original C code than a reimplementation but just like Kahlua, it lacked a compiler.

Not long after Mochalua, LuaJ appeared, which also was based on a port of Lua.
LuaJ had however also implemented/ported a compiler and had a coroutine implementation based on Java threads. This was a quite sophisticated project, with a very modular design. It had a clever solution for supporting both J2ME and J2SE based on a platform interface that both J2ME and J2SE implemented, which I ended up getting inspiration from later on.

It also turned out that LuaJ's compiler could, with a little bit of refactoring, be adapted to fit in with Kahlua, so I forked it and put it into Kahlua and seemingly over night, Kahlua had its own compiler and the JNI solution could be dropped. Thanks LuaJ!

A while after this project, yet another Lua project in Java appeared. JILL, or Java Implementation of the Lua Language wasn't really a new project - Nokia had funded it and it had just recently been open sourced. I haven't really looked into it much, but it seemed to use a similar approach as Kahlua, adapting the implementation to Java instead of doing a straight port.

Now, back to the game project!

We were writing our entire UI system in Lua, with gui and game logic methods implemented in Java and made available to Kahlua. Creating the raw JavaFunction's needed for Kahlua required a lot of low level operations, such as verifying correct number of arguments and the types of the arguments as well as pushing return values, so we decided to implement an easier mechanism for exposing methods.

This ended up as a contrib-library in Kahlua that supported exposing Java classes annotated with @LuaMethod. It handled all of the problems above, which made our lives much easier. In time, this library grew to also include conversion between Lua and Java types. Since Lua only used Double as a numeric type, we needed conversions from the other numeric types in Java. Lists and Maps in Java were converted to KahluaTable.

This was pretty much the last real development for Kahlua, but I started getting other ideas for the further development of Kahlua.

The birth of Kahlua2
I started getting a lot of ideas for how to modernize Kahlua which meant departing from many of the original design decisions, and introducing big incompatibilities with the original Kahlua. So, Kahlua2 was born, this time on github instead of Google Code. The reason for this was unrelated to the actual development of Kahlua - I just wanted to learn git, and investigate if its workflow and features had any real life benefits over Subversion.

I've identified three main categories of design changes.

Modularity
Kahlua didn't differentiate the versions for J2SE and J2ME, which meant that J2SE had to suffer a bit (not much, but a bit). The most significant effect was that most of the math operations were implemented in software, which is both slower and less precise than the built in operations in J2SE.

The solution in Kahlua2 was to introduce a platform interface implemented for both J2SE and J2ME, and creating two separate math libraries, similar to the solution used in LuaJ.

Compatibility
Keeping compatibility with Lua was one of the original goals of Kahlua, and it reached pretty far. Tables in Kahlua had the same behaviour as tables in Lua.
This was done with a complete low level implementation of tables and special handling of doubles (0 and -0 are the same key in lua tables, but in Java they are distinct). The low level implementation was required to achieve a reasonably fast implementation of next().

I meant for Kahlua to be primarily a way of extending Java with a good script language and thus compatibility with Java is more important than compatibility with Lua. Also, keeping the code simple and efficient should have a high priority.
The handcoded table implementation in Kahlua is likely not as a good as the built in maps in Java, so Kahlua2 simply drops compatibility on table keys, removes the next function, and removes support for weak tables. I hope no one will miss these features too much.

Concurrency
Kahlua, and all other Lua implementations I knew of were inheritly single threaded.
Each lua state could only be run by one thread at a time, and states couldn't really share data.
With the loosening of compatibility, Kahlua2 can instead implement tables as a simple facade to either Hashtable (for J2ME) or ConcurrentHashMap (for J2SE),
which means that Kahlua2 suddenly becomes concurrent.

All native datatypes in Kahlua (and Lua) are immutable except for tables, upvalues and the stack itself. The stack concurrency is solved by not letting multiple Java threads use the same KahluaThread at the same time. Upvalues are solved by simply making the set and get-methods be synchronized.

Unlike Kahlua, Kahlua2 separates the script environment and thread. Multiple KahluaThreads can share the same environment, which is the key to concurrency.
The threads are not to be confused with Coroutines, which still work just like in Lua.
Many KahluaThreads can share Coroutines, but only one thread can run a coroutine at a time.

Present day
You can currently find Kahlua2 on github and it's still evolving, although the core ideas for Kahlua2 described above are already implemented. The changes at the point in time mostly consist of bug fixes, refactoring of the compiler (it's still mostly a C port, which fits badly with Java).

That's it for now!
Stay tuned for The History of Kahlua part 2, expected somewhere around 2013 perhaps.

Relevant links:
LuaJava
Mochalua
LuaJ
JILL

Kahlua
Kahlua2

The hobby game, with working title Spaced

Tuesday, May 18, 2010

What's up with String.format

I noticed a while back that Javas own String.format() is slower than I expected it to be. I compared it to the handbuilt version in Kahlua which is built with a naive approach using only Java 1.4 features.

To follow up on this, I wrote a benchmark to see if I can really be sure that it is in fact slower. Writing benchmarks is always tricky and is easy to get wrong. Here's my approach of writing a test.


public class StringFormatTest {
static interface Runner {
String run(String format, Double x, Double y);
String name();
}

static class JavaRunner implements Runner {

@Override
public String run(String format, Double x, Double y) {
return String.format(format, x, y);
}

@Override
public String name() {
return "Java String.format";
}
}

static class LuaRunner implements Runner {
private final KahluaThread thread;
private final LuaClosure closure;

public LuaRunner(KahluaThread thread, LuaClosure closure) {
this.thread = thread;
this.closure = closure;
}

@Override
public String run(String format, Double x, Double y) {
return (String) thread.call(closure, format, x, y);
}

@Override
public String name() {
return "Lua string.format";
}
}

@Test
public void testFormat() throws IOException {
String format = "Hello %3.2f world %13.2f";
Double x = 123.0;
Double y = 456.0;


Platform platform = new J2SEPlatform();
KahluaTable env = platform.newEnvironment();
KahluaThread thread = new KahluaThread(platform, env);
LuaClosure closure1 = LuaCompiler.loadstring("" +
"local stringformat = string.format;" +
"return function(format, x, y)" +
"return stringformat(format, x, y)" +
"end", null, env);
LuaClosure closure = (LuaClosure) thread.call(closure1, null, null, null);

Runner luaRunner = new LuaRunner(thread, closure);
Runner javaRunner = new JavaRunner();

List<Runner> list = new ArrayList<Runner>();
for (int i = 0; i < 20; i++) {
list.add(luaRunner);
list.add(javaRunner);
}
Collections.shuffle(list);

for (Runner runner : list) {
int count = 0;
long t1 = System.currentTimeMillis();
long t2;

while (true) {
t2 = System.currentTimeMillis();
if (t2 - t1 > 1000) {
break;
}
runner.run(format, x, y);
count++;
}
double performance = (double) count / (t2 - t1);
System.out.println(String.format(
"%30s %10.2f invocations/ms",
runner.name(),
performance));
}
}
}



I've done my best to make this test be fair. The obvious first thing to do is to run each test many times, to ensure that cache misses, JIT optimizations, warmups, et.c. are all taken into account. The second obvious thing is to shuffle the ordering of tests to avoid introducing accumulating interference.
For instance, if I were to run the tests as A, B, A, B, ... then any garbage being produced at the end of A would punish B when it ran its garbage collector.

Having run this test suite for a bit, I consistently get these results:

Lua string.format 232.71 invocations/ms
Java String.format 170.07 invocations/ms
Lua string.format 231.61 invocations/ms
Java String.format 170.34 invocations/ms
Lua string.format 232.73 invocations/ms
Java String.format 170.10 invocations/ms
Java String.format 170.11 invocations/ms
Java String.format 171.23 invocations/ms


Why is the Lua version faster? It should be much slower considering:
  1. The Lua version has to go into its interpreter loop as additional overhead.
  2. The Lua implementation of string.format is a naive and short implementation, and not built by the elite development team of Sun.
Perhaps the difference is that the default Java implementation handles a lot of additional use cases such as locale, but that still doesn't really explain it.

Does anyone have any ideas why Javas String.format is slow?

Monday, May 17, 2010

TDD - levels of insight

Test Driven Development (or Design) is a method of developing code where you first write small tests that express the requirements, it can either be requirements from the customer or product owner, or requirements the developers themselves deduce are needed of the product.

The idea is that by writing the tests first, the design of the code improves, because it will automatically become modular (writing tests for code that's not modular is much harder, if not impossible). The tests also increase your development speed, since running your suite of tests takes a much shorter time than starting up the application and manually testing everything. If you make a mistake somewhere when refactoring the code or writing a new feature, it will become obvious directly, since the tests will expose it, if it breaks any of the requirements.

But let's not go into the details of TDD, there are plenty of other sources that describe TDD much better than I ever could.

Instead, this blog post will be about a hypothesis I have.
I don't believe you can really study TDD and just get it. You have to try it out for yourself and become convinced by experiencing the benefits. You will notice that you can keep maintaining a project without losing speed and your code will be extendable.

So what is the hypothesis? Glad you asked!
Every developer will go through a series of levels of insight, with each level being closer to being a TDD master.

And here are the levels I've identified, based on anecdotal evidence consisting of my personal experience, and what I've observed in others.

#1 Obliviousness
As a fresh developer, it's obvious that at some point in your life, you didn't know about TDD. I'd also take a guess that it's common to start programming before starting to write tests. From the various educations I've been to and talked to others about, testing is not something that's introduced early in programming training.

Obliviousness simply means that you're unaware of TDD is a practice and its usefulness. I was unfortunately in this category for much too long, which I suspect is true for a lot of developers.

#2 Disregard
The next step is hearing about TDD and getting the initial thought: "Writing tests first? That sounds backwards!". Not only that, you may also think that is seems like a waste of time to spend a lot of time writing tests that will soon be obsolete anyway, or tests for things that have obvious failures "I'll obviously notice immediately when starting up if this breaks".

#3 Awareness
Level 3 is being aware of TDD and that it can be a useful tool, and not just a stupid overhead designed as support for bad developers.

The easiest way to get past level 2 onto level 3 is to work with someone who's already past it, who seems to be using it successfully.

"Hmm, that guy produces clean code and doesn't seem to introduce as many bugs as I do, I wonder why..." Deeper investigation may lead to the introduction of TDD.

This may inspire you to try out writing tests first (or just writing tests at all), but since you're unfamiliar with TDD to begin with, your code will be hard to test, and it will be a pain to write the tests. You'll spend a long time to write the test, and you'll become irritated. "Do I really gain anything from spending so much time writing tests instead of producing code? QA will find any bugs I produce anyway, better to spend the time later to bugfix it instead."

Unfortunately, this is a typical setback that some people fail to get past.

#4 Empirical
Level 4 is when you've tried TDD for such a long time that you're really convinced that it's the best way to develop.
To reach this level, you need to really have used for such a long time that you have started to reap the benefits.

You have may have done a simple refactoring or introduced a new feature when one of your oldest tests break, and you look into it. "Aha, of course I needed to consider that before I did this, no wonder it broke!".

This is when you'll start building up the confidence in your code. If you introduce some code change that will break something, your tests will catch it.

Writing good tests, and writing them before the code is hard, as is writing clean and modular code. Becoming good at TDD takes time and effort, but it also makes you a better developer and better designer. Suddenly all your code will have at least two use cases - the test code and the runtime code.

#5 Mastery
After having been in level 4 long enough, TDD will become second nature to you.
You would use TDD for all development with the insight that it drives good design and saves time. No aspect of code is too hard to write test driven for a master, not even the typical daunting tasks intimidates the TDD master: UI, database, network, et.c.

Conclusion
I personally am stuck in level 4 at the moment. Perhaps I'll stay there forever, but even so it's probably a good idea to keep striving to reach level 5. I do this by trying to embrace TDD in my development as much as I can, but how can I be sure that's enough? Perhaps some other insight is needed to step up to the next level.

If I find any answers to that, You can expect a follow up post.