Master Baboon The sea of the simulation

21Feb/095

Advanced math functions for AS3

Did you ever need to sample from a Dirichlet distribution in Actionscript 3.0? What about computing a value of the Gamma function? Probably not 😉 In case you did, I wrote a class with a few math methods:

  • a function to sample from multinomial distributions; this is useful if you need to choose randomly from a set of elements, each with a different probability;
  • functions to draw samples from the Dirichlet and Gamma distribution;
  • the Gamma function
  • a factorial function that works even for large values (using the identity n! = Gamma(n+1))
  • other utility functions, e.g. to compute mean and variance of an array, or add two arrays together

You can download the AdvancedMath class here, it includes AsUnit tests.

This is an example of how to use the AdvancedMath class to simulate a rigged dice: the code below throws the dice 1000 times, and keeps a count of how many times one gets the different faces.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import com.masterbaboon.AdvancedMath;

// probability of the faces; 6 is about twice more likely to appear
var p:Array = [0.14, 0.14, 0.14, 0.14, 0.14, 0.3];
           
// count the number of times a face appears
var count:Array = AdvancedMath.zeros(6);
           
// throw dice 1000 times
var face:int;
for (var i:int = 0; i < 1000; i++) {
    face = AdvancedMath.sampleMultinomial(p);
    count[face]++;
}
           
// show how many times we got which face
trace(count);

[ad#adpost]

14Feb/096

Guess 2/3 game: sending data from Flash to a remote database

I wrote a simple game to learn how to store on and retrieve data from a server-side database. The rules are simple: you have to guess 2/3 of the average of the guesses of all the players. So, for example, if you think that the other players guessed on average 100, your guess should be 67. The 2/3 rule is there to avoid the trivial strategy of  submitting the same number over and over again. According to game theory, the game has a Nash equilibrium at 0, which in this case does not correspond to a rational strategy. Wikipedia has some information and links about the game. Give it a try:

Get Adobe Flash player

The score you see after submitting is the distance from your guess to the true 2/3 of the average. Since you get some information about your and others' score, it should be possible to find a strategy to win in a small number of trials... Let me know if you find one!

Communicating with the server

To implement the game, I created a MySQL table in a database on the server that is used to store the players' name and guess. The database is accessed by calling a server-side PHP script from the game Actionscript client.

The PHP script gets the player's information and stores it in the database; then it computes the 2/3 of the average of all entries, and returns the score and rank of the current player, along with the top scores in the database. The script receives the data as a HTTP request (the ?var1=value1&var2=value2 thing you see in many dynamical web pages), and returns an XML fragment.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
\n";
// top scores
while (($row = mysql_fetch_array($hit)) &amp;&amp; ($currentrank==0 || $rank&lt;=$ntop)) {
  if ($rank&lt;=$ntop) {
    print "
\n";
    print "
\t{$row['name']}\n";
    print "
\t{$row['diff']}\n";
    print "
\n";
  }
  if ($row['time'] == $time) {
    $currentrank = $rank;
    $currentscore = $row['diff'];
  }
  $rank = $rank + 1;
}

// current score
print "
\n\t{$name}\n\t{$currentscore}\n";
print "


\n";

mysql_close();

?&gt;

Calling the script from AS3 is relativelty easy. The remote call is done by a URLLoader object; the actual request is stored in a URLRequest object, and the request variables are wrapped in a URLVariables instance. I had an annoying problem with testing the code: for some reason, Flash always caches the requests. I looked around and it seems that the only workaround is to add a dummy variable to the request with a value that changes constantly, e.g., the current time.

This is the code for the communication with the server:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public function submitGuess(name:String, guess:uint, ntop:int):void {
    var request:URLRequest = new URLRequest("http://www.masterbaboon.com/php/guess23/guess23submit.php");
    var httpHeader : URLRequestHeader = new URLRequestHeader("pragma", "no-cache");
    request.requestHeaders.push(httpHeader);

    // request variables: name of player, guess, number of top scores to return
    var vars:URLVariables = new URLVariables();
    vars.name = name;
    vars.guess = guess;
    vars.ntop = ntop;
    // this is to trick AS3 into not caching the URL request
    vars.nocache = Number(new Date().getTime());

    request.method = URLRequestMethod.GET;
    request.data = vars;

    // send to server and call loadingComplete when complete
    var loader:URLLoader = new URLLoader();

    // the results of the request is not returned immediately, but
    // we can monitor the COMPLETE event dispatched by the loader
    loader.addEventListener(Event.COMPLETE, loadingComplete);
    try {
        loader.load(request);
    } catch (e:Error) {
        trace("An error has occurred while communicating with the server.");
        trace(e);
    }
}

public function loadingComplete(e:Event):void {
    // this is how to access the data returned from the request
    data = XML(e.target.data);
    // switch frame
    gotoAndStop("highScoreFrame");
}

You're welcome to download the whole code.

[ad#adpost]

7Feb/092

Spatial database for collision detection

In games and other graphical applications one has to keep track multiple sprites and detect collisions between them. A naif approach would loop over all sprites and check for collision with *every other sprite*. This is, of course, terribly inefficient and can be very slow even for a small number of sprites.

One way out of this nightmare  is to register the sprites in a spatial database that stores them according to their position, and is able to determine which of them is close to a given point. As a result, one only needs to check for collision between neighboring sprites. There are many implementations of spatial databases, some of which are quite sophisticated. In this post I'm going to describe an ActionScript 3 implementation of a grid-based spatial database, that can be used for simple flash games.

Grid: 2D Array with neighborhood

A Grid is a two-dimensional array with a concept of neighborhood. In addition to be able to store and retrieve information on the 2D grid, one can request neighboring elements of a given array element.

For example, let's create a simple 4x4 grid, and store at each point an increasing number:


1
2
3
4
5
6
7
var grid:Grid = new Grid(4, 4);
var k:int = 1;
for (var i:int = 0; i &lt; 4; i++) {
    for (var j:int = 0; j &lt; 4; j++) {
        grid.set(i, j, k++);
    }
}

This image shows the resulting grid, with small numbers indicating grid coordinates and large, bold ones the stored values:

grid11

We can now query the grid to get neighbors of a given position: For example, the following code


1
2
3
4
var neighbors:Array = grid.getNeighbors(1, 1);
trace(neighbors);
neighbors = grid.getNeighbors(1, 3);
trace(neighbors);

displays 1, 2, 3, 5, 7, 9, 10, 11 and 3, 4, 7, 11, 12, respectively, as shown here:

grids2and3

Note that, by default, the neighbors stop at the border. It is possible to work on a "toroidal" grid, meaning that the opposite borders of the grid are connected:

grid4


1
2
3
grid.setToroidal(true);
neighbors = grid.getNeighbors(1, 3);
trace(neighbors);

which prints 3,4,1,7,5,11,12,9 .

I added two functions that simplify working with neighbors. The first, mapOnNeighbors(x, y, fct), applies a function fct to all neighbors of (x,y). Let's  see which of the neighbors of (1,3), are even numbers, just for fun:


1
2
3
function isEven(x:int):Boolean { return (x % 2 == 0); }
var neighborsAreEven:Array = grid.mapOnNeighbors(1, 3, isEven);
trace(neighborsAreEven);

This gives false,true,false,false,false,false,true,false. There are several interesting uses of this method: collecting information from elements in a region of the grid, activating neighboring elements, ...

The second function, reduceOnNeighbors(x, y, fct), is a bit more difficult to explain, but equally useful: it returns a single value constructed by iterating over the neighbors of (x,y) and calling fct(a, b) on the first two items of the sequence, then on the result and the next item, and so on. We can use this function to compute the sum of all neighbors:


1
2
3
function sum(x:Number, y:Number):Number { return x + y; }
var sumOfNeighbors:Number = grid.reduceOnNeighbors(1, 1, sum);
trace(sumOfNeighbors);

prints 48 = 1+2+3+5+7+9+10+11 . This function could have been used for example in the previous post in the Cellular Automaton code, to compute the number of alive neighbors for every cell of the CA.

SpatialDatabase

The SpatialDatabase class registers sprites in a Grid with coarser resolution. For example, a Shape at position (31, 23) on the stage would be stored in element (3,2) if the resolution of the grid is 10 pixels.

That's basically all there is to it! For collision detection, we can query the spatial database for sprites registered at neighboring elements in the grid:


1
2
3
4
5
6
7
8
9
10
// Check collision with shape:Shape
// 1. get neighbors
var neighbors:Array = spatialDatabase.getAllNeighbors(shape.x, shape.y);
// 2. loop over all neighbors and check collision
for each (var s:Shape in neighbors) {
    // check collision
    if (checkCollision(shape, s)) {
        // do something (bounce, explode, ...)
    }
}

A higher resolution gives an optimal performance. Just keep in mind that the grid size should be larger than the size of the largest sprite, otherwise some collisions may go undetected.

There exist much more sophisticated methods to improve the efficiency of collision detection (see for example this post and the excellent tutorial at metanet software). However, this simple grid-based approach can be *very* efficient for many applications!

You can grab the code for the Grid and SpatialData`base classes here (including AsUnit tests for the Grid class). I have a nice example of this class at work, but this post is already long enough, have a look at the next one!

[ad#adpost]