## Finding maximal rectangles in a grid

Maximal rectangles problem is to find rectangles inside an area that have maximum possible surface area. This is often needed in games to show the player where in area a certain item can fit etc.. There are many ways to approach the problem, and for some cases (such as areas defined by polygon) they can get complex to implement. Here is one relatively simple method for looking up those maximum rectangles inside an area in a common grid. It’s pretty efficient and does support following restrictions

• Rectangles can have minimum size (e.g. larger than 2×2).
• There can be more than one maximum rectangle in the area. (in case two large areas are joined with narrow path)

First part is defining function that looks up rectangle dimensions. This function starts from a tile that will be left top corner of rectangle and returns its width and height. The listings here are in pseudocode.

Listing 1. Get rectangle size

FUNC get_rectangle_size( tile, tiles )
BEGIN
# find rectangle width
width = 1
WHILE contains( (tile.x + width, c.y,  tiles )
width = width + 1

# find rectangle height
height = 0
stop = false
REPEAT
height = height + 1
LOOP FROM x = tile.x TO tile.x + width
IF NOT contains( (x, tile.y + height), tiles )
THEN
stop = true
BREAK
ELSE
x = x + 1
UNTIL stop

RETURN (width, height)
END

Function finds the maximum width of the rectangle starting from the left corner and working right (lines 5-6), then it finds rectangle height by looking up rows of same width (lines 11-20).

The actual algorithm that finds the rectangles accepts list of grid tiles as input and outputs the found rectangles that are maximally sized. The pseudocode listing here assumes some helper functions for simplicity.

• sort ( list, compare ) – Sorts list in place by compare function
• remove (item, list) – Removes item from list
• contains( item, list ) – Returns true if item is found from list
• length( list ) – Returns lists length
• overlap (rect1, rect2) – Returns true if two rectangles overlap

Listing 2. Find maximal rectangles. Unoptimized for readability!

FUNC find_tiles( tiles )  # the list of tiles as (x,y) tuples
BEGIN
rectangles = []  # list of found rectangles

# sort with compare order by y and x.
sort(tiles,  (a, b) => a.y == b.y ? a.x - b.x : a.y - b.y)

WHILE length(tiles) > 0
c = head(tiles)   # take first item from the sorted list

# get rectangle size
(width, height) = get_rectangle_size( c, tiles )

# remove tiles that can not be part of any larger rectangle
LOOP FROM x = c.x TO c.x + width
LOOP FROM y = c.y TO c.y + height
IF NOT contains( (c.x - 1, y, tiles) AND
NOT contains( (c.x + width, y), tiles) AND
NOT contains( (x, c.y - 1), tiles) AND
NOT contains( (x, c.y + height), tiles)
THEN
remove( (x, y), tiles )

# if big enough rectangle add it to list
IF width > 1 AND height > 1
THEN
add ( (c.x, c.y, width, height), rectangles )

# sort rectangles by area size
sort( rectangles, (r1, r2) => r2.width * r2.height - r1.width * r1.height )

# remove overlapping rectangles
i = 0
WHILE i < length(rectangles) - 1
LOOP FROM j = length(rectangles) - 1 TO i + 1 # descending order
IF overlaps(rectangles[i], rectangles[j])
THEN
remove(rectangles[j], rectangles)
i = i + 1

RETURN rectangles
END

Here is example how the algorithm works, here white area presents the working set of tiles that algorithm works on, white presents the tiles that are in list tiles.

Algorithm sorts first the tiles in top-to-bottom and left-to-right order so it starts from top left tile. The pink denotes the current working tile c. The green represents the tiles that belong to rectangle as determined by call to get_rectangle_size.

Next step is to remove tiles from working set that can not be part of any other rectangle. This is determined by checking if the row and column of tile are bounded inside the current rectangle. The purple presents tiles that were removed from the working set tiles. Found rectangle is added in the list rectangles if it’s large enough (in this case larger than 2×2).
Then loop is executed again with next corner tile c.

Next iteration of the main loop returns another rectangle and closed tiles are removed and rectangle added to list.

Final loop of the rectangle. There are no more tiles to work so main loop stops.

Finally algorithm sorts the found rectangles in descending surface area order and removes overlap. The resulting rectangles are returned as output.

## Class Persistence in Unity

Games need to store some persistent data like high scores and progress between the game sessions. Fortunately Unity gives us PlayerPrefs class that is essentially a persistent hash map.

Reading and writing values with PlayerPrefs is as simple as calling get and set.

// saving data
PlayerPrefs.SetInt("foobar", 10);
PlayerPrefs.SetString("something", "foo");
PlayerPrefs.Save();
...
int foo = PlayerPrefs.GetInt("foobar");
}

It has its limitations, only strings and numbers can be stored and that makes more complex data lot more difficult to maintain.

What we can do is to write simple utility that can be used to serialize classes to strings that can then be read and written with PlayerPrefs. SerializerUtil is static class with two methods to Load and Write object. In case loading fails it returns default value of the data, usually null.

using System;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;

public static class SerializerUtil {
static BinaryFormatter bf = new BinaryFormatter ();

{
return default(T);

try {
string tmp = PlayerPrefs.GetString(key);
MemoryStream dataStream = new MemoryStream(Convert.FromBase64String(tmp));
return (T)bf.Deserialize(dataStream);

} catch (Exception e) {
Debug.Log("Failed to read "+ key+ " err:" + e.Message);
return default(T);
}
}

public static void SaveObject<T>(string key, T dataObject)
{
MemoryStream memoryStream = new MemoryStream ();
bf.Serialize (memoryStream, dataObject);
string tmp = Convert.ToBase64String (memoryStream.ToArray ());
PlayerPrefs.SetString ( key, tmp);
}
}

[Serializable]
public class PlayerData {
public int points;
public string name;
}

You can then easily store instances of the class.

var data = new PlayerData();
data.points = 50;
data.name = "Teemu";

SerializerUtil.SaveObject("player1", data);

PlayerData data;
// data.points is 50
// data.name is "Teemu"

Classes can be also more complicated, you can add member functions and also exclude some member variables from serialization. It’s also possible to define member function that will be called after serialization, it’s good way to init class after deserialization from disk.

[Serializable]
public class PlayerData : IDeserializationCallback {
public int points;
public string name;

// serialization ignores this member variable
[NonSerialized] Dictionary<int, int> progress = new Dictionary<int, int>();

// constructor is called only on new instances
public PlayerData() {
points = 0;
name = "Anon";
}

// serializable class can have member methods as usual
public bool ValidName()
{
return name.Trim().Length > 4;
}

// Called only on deserialized classes
void IDeserializationCallback.OnDeserialization(System.Object sender)
{
// do your init stuff here
progress = new Dictionary<int, int>();
}
}

## Caveats

This serialization does not support versioning. You can not read the stored instance anymore if you change the class members as the LoadObject will fail to deserialize the data.

You need to add following environment variable to force Mono runtime to use reflection instead JIT. Otherwise the serialization will fail on iOS devices. Do this before doing any loading or saving of classes.

void Awake() {
Environment.SetEnvironmentVariable("MONO_REFLECTION_SERIALIZER", "yes");
...

## Lightweight CSV reader for Unity

Managing game data in Unity scene objects can get really painful especially when more than one people needs to edit the same thing. It’s usually better to have some data in CSV file where it can be controlled centrally.

When facing this problem I couldn’t find CSV reader for Unity that would have been exactly what I need. i.e. not be very buggy, huge or require new assembly dependencies.
So here is very simple CSV reader for Unity. It is bare bones but still robust enough parse quoted text and comma’s inside text. Reader assumes that csv files are in Resources folder of your Unity project.

using UnityEngine;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;

{
static string SPLIT_RE = @",(?=(?:[^""]*""[^""]*"")*(?![^""]*""))";
static string LINE_SPLIT_RE = @"\r\n|\n\r|\n|\r";
static char[] TRIM_CHARS = { '\"' };

public static List<Dictionary<string, object>> Read(string file)
{
var list = new List<Dictionary<string, object>>();
TextAsset data = Resources.Load (file) as TextAsset;

var lines = Regex.Split (data.text, LINE_SPLIT_RE);

if(lines.Length <= 1) return list;

for(var i=1; i < lines.Length; i++) {

var values = Regex.Split(lines[i], SPLIT_RE);
if(values.Length == 0 ||values[0] == "") continue;

var entry = new Dictionary<string, object>();
for(var j=0; j < header.Length && j < values.Length; j++ ) {
string value = values[j];
value = value.TrimStart(TRIM_CHARS).TrimEnd(TRIM_CHARS).Replace("\\", "");
object finalvalue = value;
int n;
float f;
if(int.TryParse(value, out n)) {
finalvalue = n;
} else if (float.TryParse(value, out f)) {
finalvalue = f;
}
}
}
return list;
}
}

Drop this in your Scripts folder as CSVReader.cs and make folder Resources under your Assets folder. Put there any CSV files you want to use.

Example CSV file example.csv in Resources folder.

name,age,speed,description
cat,2,4.5,"cat stalks, jumps and meows"
dog,2,5.5,dog barks

How to use

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class Main : MonoBehaviour {

void Awake() {

for(var i=0; i < data.Count; i++) {
print ("name " + data[i]["name"] + " " +
"age " + data[i]["age"] + " " +
"speed " + data[i]["speed"] + " " +
"desc " + data[i]["description"]);
}

}

// Use this for initialization
void Start () {
}

// Update is called once per frame
void Update () {

}
}

See full example code in Github: https://github.com/tikonen/blog/tree/master/csvreader

## Now Hiring in Mobile Gaming!

I’m pleased to announce that my start-up Nonstop Games recently joined the King family and we are now a King studio in Singapore. We’re expanding the studio and it’s a great time to join us, as you will contribute and shape the games in the pipeline and be part of an awesome and passionate team!

We are looking for talented game and server developers and if you are looking for an exciting challenge where you can really make a difference, then check out our positions and apply!

http://www.nonstop-games.com/jobs

## Finding Patterns in Data Sequences

Some time ago I was presented question if there would be easy and quick way to recognize certain usage patterns in huge amount of event data. The events in question were common user activity like clicking buttons, waiting certain time between and so on. This data could then used to improve user experience or catch cheaters that write bots to play their game for them and so on.

There are multiple ways to approach this problem but I came up with relatively simple method that seems to have flexibility. We can think the events of interest as sequence of symbols and in case also time between events is of interest, quantize the time as symbols for short, long and medium time. Then, sequence of events can be presented as list of symbols

ABC123ABC123ABC123ABC123XABC123ABC123ABC123ABC123XABC123ABC123ABC123ABC123X

Here A could be button click to open window, B a tab click in window, C close button, 1 a second pause before moving mouse, 2 a few second pause before moving mouse and X is collect resources etc..

Now we can approach problem with pattern finding. First let’s define function that is supposed to find recurring patterns and output them and input as sequence of those patterns. (Following is written in Python)

def findpattern(s, trivial):
patterns = {}
symbolmap = {}

p = patterns
acc = []
output = []
for c in s:
if not c in p:
if not c in patterns or (not trivial and acc[-1] == c):
p[c] = {}
p = p[c]
acc.append(c)
else:
acc = ''.join(map(lambda x: str(x),acc))
if not acc in symbolmap:
symbolmap[acc] = true
output.append(acc)

acc = [c]
p = patterns[c]
else:
p = p[c]
acc.append(c)

if acc:
acc = ''.join(map(lambda x: str(x),acc))
if not acc in symbolmap:
symbolmap[acc] = true
output.append(acc)

return (symbolmap.keys(), output)

Function accepts two arguments, the list of symbols and flag if trivial pattern should be accepted. This is needed to determine if you consider a input list “AAAAA” to be one instance of pattern “AAAAA” or 5 instances of pattern “A”.

When this function is applied on the example string above, we get list of core patterns and the input as pattern list.

> s = "ABC123ABC123ABC123ABC123XABC123ABC123ABC123ABC123XABC123ABC123ABC123ABC123X"
> findpattern(s, False)
['ABC123', 'ABC123X'] ['ABC123', 'ABC123', 'ABC123', 'ABC123X', 'ABC123', 'ABC123', 'ABC123', 'ABC123X', 'ABC123', 'ABC123', 'ABC123', 'ABC123X']

Here it’s easy to see that the string is composed of two main patterns, ABC123 and ABC123X. The second output list is the input string split as instances of pattern.
Real data is noisier than the example here, so proper data cleaning and event definition / filtering are vital for any kind of useful pattern recognition.

In this case one could guess that the player might be bot, as the same sequence occur regularly with too much precision and too little variability for human player. (Remember that the symbols 1, 2 and 3 presented also time in this example.)

Going forward we can also define function that recursively uses the output of the findpattern to find patterns of patterns up to the “prime” pattern of the input, i.e. the pattern that when repeated N times produces the original input string.

def findprimepattern(s, trivial=False):
o = s
while True:
s, o = findpattern(o, trivial)
print s,o
if len(s) == 1:
return s[0]

Example with more complicated pattern string

> s = (((("ABC"*2)+"DE")*3+"X")*2+"O")*4
"ABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXOABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXOABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXOABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXO"
> findprimepattern(s)
['ABCDEXO', 'ABC', 'ABCDE', 'ABCDEX'] ['ABC', 'ABCDE', 'ABC', 'ABCDE', 'ABC', 'ABCDEX', 'ABC', 'ABCDE', 'ABC', 'ABCDE', 'ABC', 'ABCDEXO', 'ABC', 'ABCDE', 'ABC', 'ABCDE', 'ABC', 'ABCDEX', 'ABC', 'ABCDE', 'ABC', 'ABCDE', 'ABC', 'ABCDEXO', 'ABC', 'ABCDE', 'ABC', 'ABCDE', 'ABC', 'ABCDEX', 'ABC', 'ABCDE', 'ABC', 'ABCDE', 'ABC', 'ABCDEXO', 'ABC', 'ABCDE', 'ABC', 'ABCDE', 'ABC', 'ABCDEX', 'ABC', 'ABCDE', 'ABC', 'ABCDE', 'ABC', 'ABCDEXO']
['ABCABCDE', 'ABCABCDEX', 'ABCABCDEXO'] ['ABCABCDE', 'ABCABCDE', 'ABCABCDEX', 'ABCABCDE', 'ABCABCDE', 'ABCABCDEXO', 'ABCABCDE', 'ABCABCDE', 'ABCABCDEX', 'ABCABCDE', 'ABCABCDE', 'ABCABCDEXO', 'ABCABCDE', 'ABCABCDE', 'ABCABCDEX', 'ABCABCDE', 'ABCABCDE', 'ABCABCDEXO', 'ABCABCDE', 'ABCABCDE', 'ABCABCDEX', 'ABCABCDE', 'ABCABCDE', 'ABCABCDEXO']
['ABCABCDEABCABCDEABCABCDEX', 'ABCABCDEABCABCDEABCABCDEXO'] ['ABCABCDEABCABCDEABCABCDEX', 'ABCABCDEABCABCDEABCABCDEXO', 'ABCABCDEABCABCDEABCABCDEX', 'ABCABCDEABCABCDEABCABCDEXO', 'ABCABCDEABCABCDEABCABCDEX', 'ABCABCDEABCABCDEABCABCDEXO', 'ABCABCDEABCABCDEABCABCDEX', 'ABCABCDEABCABCDEABCABCDEXO']
['ABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXO'] ['ABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXO', 'ABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXO', 'ABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXO', 'ABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXO']
ABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXO

And indeed the input string is the prime pattern ABCABCDEABCABCDEABCABCDEXABCABCDEABCABCDEABCABCDEXO concatenated 4 times.

Note effect of parameter trival on the function.

> findprimepattern('AAAA', False)
['AAAAA'] ['AAAAA']
AAAAA
> findprimepattern('AAAA', True)
['A'] ['A', 'A', 'A', 'A', 'A']
A

Former is single instance of pattern “AAAA” and latter is 4 instances of pattern “A”.

## Permutation of a list

Let’s consider following requirement. We have list of objects, say questions, that we want to show our users. Let’s also assume that the list is very long, 500 messages.

Each message is unique and we want to

1. show each question only once for each user.
2. show the questions in different order to each user.

Each user responds to only few questions each day so it will take several months before they exhaust the list. We need to remember over each session where user left off.

Basic way to implement this is to take the list of questions, make a copy of it, shuffle it’s content and save it as part of users profile data. This has obvious drawbacks of the data duplication and maintenance. Also if the list changes, every single copy of the list has to be updated.

Cheaper way to implement this is to use prime walk. In this method we can keep only single copy of the list and store only number of answered questions in the users profile.

1. First define the list, say we have 500 items.
2. Find prime number that is greater than 500. For example 503.
3. Select seed for each user. This seed is any number that is constant for an user, like user id or time of account creation.

Then we define function that uses these values. Note that this implementation is tail-recursive for code simplicity, efficient implementation should not use recursion.

var prime = 503;
var list = ["question1", "question2", ... "question500"];

function pick_nth(seed, n, p, l) {
if(!n) return l[seed % p];
return pick_nth((seed + l.length) % p, n - 1, l);
}

Now picking up n:th question from list becomes easy. For example:

pick_nth(userId, 0, prime, list);  // first question
pick_nth(userId, 1, prime, list);  // second question
...
pick_nth(userId, 499, prime, list);  // 500th question

Function returns items from list in different order for every unique user id. Only thing needed to keep track of progress is to store the number of questions user has answered.

Changing list requires some care. To delete question, just mark the entry in list to null to skip it. To add questions, add another list that is used after user has exhausted the original one.
If you change the list length, the order of selection changes and it’s not anymore guaranteed that user sees every question and sees every question only once.

## Selecting biased random objects from a set

Normal random pick from set of objects will return every object equally likely.
For example, following function returns any character with equal probability from the argument string.

function randomselect(s) {
return s[~~(Math.random() * s.length)];
}

This is usually the desired functionality, but games often require to pick one thing more likely than another. Typical use case are random drops from enemies, the common loot should drop most often and the good stuff should be much more rare.

Biased random pick is selecting object from a set randomly, so that some of them selected more often than others.

Calling randomselect("abc") will return each “a”, “b” and “c” with 33% probability.
Selection can be biased by just adding more of characters in the string. Calling randomselect("aaabbc") will return “a” with 50%,”b” with 33% and “c” with 16% propability.

Just adding entries in a list is bit clumsy, and more generic method is to use integral of probability density.

// define elements and probability for each
var elems = [
['a', 0.5],
['b', 0.333],
['c', 0.166]
]

// Biased random entry selection
function select(elems) {
var r = Math.random();
var ref = 0;

for(var i=0; i < elems.length; i++) {
var elem= elems[i];
ref += elem[1];
if (r < ref) return elem[0];
}
// This happens only if probabilities do not add up to 1
return null;
}

Calling select(elems) returns a with 50%, b with 33.3% and c with 16.6% probability.
If defined probabilities do not sum to 1 you can get null, i.e not selection. In this case 0.5 + 0.333 + 0.166 is 0.999 so there is 0.1% probability (one out 1000) to get nothing.

For example to pick 100 times randomly from the set.

var elems = [
['a', 0.5],
['b', 0.333],
['c', 0.166]
];

var s = '';
for(var i=0; i < 100; i++) {
s += select(elems);
}
console.log(s);

Run this with node to get string of randomly picked characters. Here you can see that selection bias works, half of the letters are ‘a’, one third ‘b’ and rest ‘c’.

\$ node biased.js
babbaaaabaabbaabaccbaacabbbabbacbaabacabccacacacbacaaaaacbcaaaababaccbcbbbcaabcaabaccabbbcbcbacaabaa