Unity C++ Native Plugin Examples

Unity scripting environment runs C# Mono container which supports native C/C++ plugins with Mono PInvoke. This allows easy integration of native library functions to both pass and receive data between Unity managed C# and native platform code.

Basic concept is simple. Native function descriptor that specify calling convention and dynamically loaded library (DDL) tell Mono how it’s parameters and returns values should be converted. Mono handles things mostly automatically from there on.

Some care is required to do this efficiently. C# PInvoke defines marshaling as a protocol to serialize and deserialize managed objects back and forth towards native code. This may generate lot of overhead. Mono garbage collector might accidentally destroy memory of an object while it’s used in the native code space.

Example C++ code is for a native Win32 plugin but is trivial to port to any platform.

Basic Data

Passing simple integral types, integers and arrays of them is straightforward.

Native c code.

extern "C" {


    PLUGINEX(int) ReturnInt()
        return 0xBABE;

    PLUGINEX(void) AcceptArray1(char *arr, int length)
        for (int i = 0; i < length; i++) {
           arr[i] = 'A' + i;

C# declarations and example calling code.

private static extern int ReturnInt();

private static extern void AcceptArray1([In, Out] byte[] arr, int length);

void TestIntegral() {
    // return int

    // accept byte array, uses marshaling to pass array back and forth
    byte[] arr1 = { 0, 0, 0 };
    AcceptArray1(arr1, arr1.Length);
    for (int i = 0; i < arr1.Length; i++)
        print("arr" + i + "=" + arr1[i]);

Strings are passed and returned as character arrays. It’s possible to use automatic marshaling conversions and return dynamically allocated strings that will be automatically deallocated.

Native c code.

extern "C" {


	PLUGINEX(bool) AcceptStr(LPCSTR pStr)
		return !strcmp(pStr, "FOO");
	PLUGINEX(LPSTR) ReturnDynamicStr()
		LPSTR str = (LPSTR)CoTaskMemAlloc(512);
		strcpy_s(str, 512, "Dynamic string");
		return str;

	PLUGINEX(LPCSTR) ReturnConstStr()
		return "Constant string";

C# declarations and example calling code.

private static extern bool AcceptStr([MarshalAs(UnmanagedType.LPStr)] string ansiStr);

// automatically deallocates the return string with CoTaskMemFree
[return: MarshalAs(UnmanagedType.LPStr)]
private static extern string ReturnDynamicStr();

private static extern IntPtr ReturnConstStr();

void TestStrings() {
    // accept string
    bool r1 = AcceptStr("BAR");
    bool r2 = AcceptStr("FOO");
    print("r1=" + r1); // r1=false
    print("r2=" + r2); // r1=true

    // return dynamically allocated string
    string s1 = ReturnDynamicStr();
    print("s1=" + s1);

    // return constant string
    string s2 = Marshal.PtrToStringAnsi(ReturnConstStr());
    print("s2=" + s2);

Both dynamic and constant arrays can be supported but some helper functions are needed.

Native c code.

extern "C" {


	PLUGINEX(void) AcceptArray1(char *arr, int length)
		for (int i = 0; i < length; i++) {
			arr[i] = 'A' + i;

	PLUGINEX(void) AcceptArray2(char *arr, int length)
		for (int i = 0; i < length; i++) {
			arr[i] = 'A' + i;

	PLUGINEX(int) AcceptStrArray(const char* const *strArray, int size)
		int total = 0;
		for (int i = 0; i < size; i++) {
			auto str = strArray[i];
			total += (int)strlen(str);
		// return total length of the strings in the array to demonstrate that
		// it was passed correctly
		return total;

	PLUGINEX(LPBYTE) ReturnDynamicByteArray(int &pSize)
		pSize = 0xFF;
		LPBYTE pData = (LPBYTE)CoTaskMemAlloc(pSize);

		// fill with example data
		for (int i = 0; i < pSize; i++) {
			pData[i] = i + 1;

		return pData;

	PLUGINEX(LPSTR*) ReturnDynamicStrArray(int &pSize)
		// Allocate an array with pointers to 3 dynamically allocated strings
		pSize = 3;
		LPSTR* pData = (LPSTR*)CoTaskMemAlloc((pSize)*sizeof(LPSTR));		
		pData[0] = (LPSTR)CoTaskMemAlloc(128);
		pData[1] = (LPSTR)CoTaskMemAlloc(128);
		pData[2] = (LPSTR)CoTaskMemAlloc(128);

		strcpy_s(pData[0], 128, "String 1");
		strcpy_s(pData[1], 128, "String 2");
		strcpy_s(pData[2], 128, "String 3");

		return pData;

C# declarations and example calling code.

private static extern void AcceptArray1(IntPtr arr, int length);

private static extern void AcceptArray2(IntPtr arr, int length);

private static extern int AcceptStrArray(IntPtr array, int size);

private static extern IntPtr ReturnDynamicByteArray(ref int size);

private static extern IntPtr ReturnDynamicStrArray(ref int size);

///// Helper functions for marshalling /////

// Convert and copy array of strings to raw memory
private static IntPtr MarshalStringArray(string[] strArr)
    IntPtr[] dataArr = new IntPtr[strArr.Length];
    for (int i = 0; i < strArr.Length; i++)
        dataArr[i] = Marshal.StringToCoTaskMemAnsi(strArr[i]);
    IntPtr dataNative = Marshal.AllocCoTaskMem(Marshal.SizeOf(typeof(IntPtr)) * strArr.Length);
    Marshal.Copy(dataArr, 0, dataNative, dataArr.Length);

    return dataNative;

// Decodes string array from raw pointer
private static string[] MarshalStringArray(IntPtr dataPtr, int arraySize)
    var dataPtrArray = new IntPtr[arraySize];
    var strArray = new String[arraySize];
    Marshal.Copy(dataPtr, dataPtrArray, 0, arraySize);
    for (int i = 0; i < arraySize; i++)
        strArray[i] = Marshal.PtrToStringAnsi(dataPtrArray[i]);
    return strArray;

// Dellocates encoded string array
private static void CleanUpNativeStrArray(IntPtr dataPtr, int arraySize)
    var dataPtrArray = new IntPtr[arraySize];
    Marshal.Copy(dataPtr, dataPtrArray, 0, arraySize);
    for (int i = 0; i < arraySize; i++)

void TestArrays() {

    // accept byte array, uses marshalling to pass array back and forth
    byte[] arr1 = { 0, 0, 0 };
    AcceptArray1(arr1, arr1.Length);
    for (int i = 0; i < arr1.Length; i++)
        print("arr" + i + "=" + arr1[i]);

    // accept byte array, passes no-copy raw memory pointer
    byte[] arr2 = { 0, 0, 0 };
    GCHandle h = GCHandle.Alloc(arr2, GCHandleType.Pinned);
    AcceptArray2(h.AddrOfPinnedObject(), arr2.Length);
    for (int i = 0; i < arr2.Length; i++)
        print("arr" + i + "=" + arr2[i]);

    // return dynamically allocated byte array
    int arraySize = 0;
    IntPtr dataPtr = ReturnDynamicByteArray(ref arraySize);
    byte[] data = new byte[arraySize];
    Marshal.Copy(dataPtr, data, 0, arraySize);
    Marshal.FreeCoTaskMem(dataPtr); // deallocate unmanaged memory
    print("data["+arraySize+"] = [" + data[0] + ", " + data[1] + ", " + data[2] + ",...]");

    // return dynamically allocated string array
    arraySize = 0;
    dataPtr = ReturnDynamicStrArray(ref arraySize);
    String[] strArray = MarshalStringArray(dataPtr, arraySize);
    print("strArray["+arraySize+"] = [" + String.Join(",", strArray) + "]");

    // string array as parameter
    dataPtr = MarshalStringArray(new String[] { "foo1", "foo2", "foo3" });
    int len = AcceptStrArray(dataPtr, arraySize);
    print("len=" + len);
    CleanUpNativeStrArray(dataPtr, arraySize);

Structures and Arrays of Structures

Array handling is similar to the string arrays. Most objects can be passed as is but if they have array properties those must be of fixed size.

Native c code.

extern "C" {


	struct ExampleStruct {
		INT16 val1;
		INT32 array1[3];
		INT16 array2len;
		INT32 array2[10];
		LPSTR str1;

	PLUGINEX(int) AcceptStruct(ExampleStruct &s)
		// Modify struct
		s.val1 -= 1111;
		for (int i= 0; i < 3; i++) {
			s.array1[i] += 1;			
		for (int i = 0; i < s.array2len; i++) {
			s.array2[i] += 10;
		// return length of the string in the argument struct to demonstrate that
		// it was passed correctly
		return (int)strlen(s.str1);

	struct ExamplePoint {
		FLOAT x;
		FLOAT y;
		FLOAT z;

	PLUGINEX(ExamplePoint *) ReturnArrayOfPoints(int &size)
		size = 4;
		ExamplePoint *pointArr = (ExamplePoint*)CoTaskMemAlloc(sizeof(ExamplePoint) * size);

		// fill with some example data
		for (int i = 0; i < size; i++) {
			pointArr[i] = { i + 0.1f, i + 0.2f, i + 0.3f };
		return pointArr;

	// this return type is blittable
	// https://stackoverflow.com/questions/10320502/c-sharp-calling-c-function-that-returns-struct-with-fixed-size-char-array
	PLUGINEX(ExamplePoint) ReturnStruct()
		return { 1, 2, 3 };

C# declarations and example calling code.

public struct ExamplePoint
    public float x;
    public float y;
    public float z;

    // for debugging
    public override String ToString()
        return "{" + x + ","+ y + "," + z + "}";

private static extern IntPtr ReturnArrayOfPoints(ref int size);

[StructLayout(LayoutKind.Sequential, CharSet = CharSet.Ansi)]
public struct ExampleStruct
    public UInt16 val1;
    [MarshalAsAttribute(UnmanagedType.ByValArray, SizeConst = 3)]
    public UInt32[] array1;
    public UInt16 array2len;
    [MarshalAsAttribute(UnmanagedType.ByValArray, SizeConst = 10)]
    public UInt32[] array2;
    public string str1;

private static extern int AcceptStruct(ref ExampleStruct s);

private static extern ExamplePoint ReturnStruct(); 

void TestStructures() {
    // Structure as parameter
    ExampleStruct s = new ExampleStruct
        val1 = 9999,
        array1 = new UInt32[3],
        array2 = new UInt32[10]
    s.array1[0] = 1;
    s.array1[1] = 2;
    s.array1[2] = 3;
    s.array2len = 5;
    s.array2[0] = 10;
    s.array2[1] = 11;
    s.array2[2] = 12;
    s.array2[3] = 13;
    s.array2[4] = 14;
    s.str1 = "Cat is a feline";

    len = AcceptStruct(ref s);
    print("s.val1=" + s.val1 + " len=" + len);

    // return struct
    ExamplePoint p = ReturnStruct();

    // Marshal array of point objects
    arraySize = 0;
    dataPtr = ReturnArrayOfPoints(ref arraySize);
    ExamplePoint[] pointArr = new ExamplePoint[arraySize];

    // memory layout
    // |float|float|float|float|float|float|float|float|float|float..
    // |   ExamplePoint0 |   ExamplePoint1 |   ExamplePoint2 |
    int offset = 0;
    int pointSize = Marshal.SizeOf(typeof(ExamplePoint));
    for(int i=0; i < arraySize; i++)
        pointArr[i] = (ExamplePoint)Marshal.PtrToStructure(new IntPtr(dataPtr.ToInt32() + offset), typeof(ExamplePoint));
        offset += pointSize;
    print("pointArr["+arraySize+"]=["+pointArr[0]+", "+pointArr[1]+",...]");


Many of these examples can be done in cleaner way using MarshalAsAttribute. Code above does show what is happening under the hood.

Get full implementation ftom https://github.com/tikonen/blog/tree/master/unityplugin

Git revision as compiler definition in build with CMake

This is how to auto-generate a version header file with git revision (SHA) and the exact build time as C defines. Include header in your source as convenient way to have access to the exact git version for the application version string or diagnostics output.

Header file with the git revision and build timestamp.

// gitversion.h
#pragma once

#define GIT_REVISION "f8d2aca"
#define BUILD_TIMESTAMP "2017-07-14T20:24:36"

CMake script generates the header in cmake build directory

# cmake/gitversion.cmake
cmake_minimum_required(VERSION 3.0.0)

message(STATUS "Resolving GIT Version")

set(_build_version "unknown")

    COMMAND ${GIT_EXECUTABLE} rev-parse --short HEAD
    WORKING_DIRECTORY "${local_dir}"
    OUTPUT_VARIABLE _build_version
  message( STATUS "GIT hash: ${_build_version}")
  message(STATUS "GIT not found")

string(TIMESTAMP _time_stamp)

configure_file(${local_dir}/cmake/gitversion.h.in ${output_dir}/gitversion.h @ONLY)

It’s possible to run this script only once in configuration, but you could also use it in main CMakeLists.txt to execute it before every build.

# Example CMakeLists.txt
cmake_minimum_required(VERSION 3.7.0)

set(_target Main)
add_executable(${_target} src/main.c)

add_custom_command(TARGET ${_target}
    -P "${CMAKE_CURRENT_SOURCE_DIR}/cmake/gitversion.cmake"

# for finding generated gitversion.h
target_include_directories(${_target} PRIVATE ${CMAKE_BINARY_DIR})

– Build steps are executed only if the build is really needed, if target is up to date no command is executed.
– All build steps are not supported when using the Unix Makefile generator.

Get full example from https://github.com/tikonen/blog/tree/master/cmake/git_version

update_directory command for CMake

CMake offers several platform independent commands for manipulating files that are used often in the custom build commands. (For more details see Command-Line Tool Mode.)

One of the more useful ones is the copy_directory that is commonly used in post-build step to copy configuration and support files (configs, DLLs, …) to the binary directory so program can be directly executed in a IDE or debugger.
Unfortunately this command always overwrites the contents of the destination directory so all changes in the target folder are lost, this is a problem when developer wants to keep local configuration changes during development.

Here is how you can implement a custom update_directory that works exactly like copy_directory but writes files to the destination folder only if they are missing or the file timestamp is older.

# cmake/update_directory.cmake
file(GLOB_RECURSE _file_list RELATIVE "${src_dir}" "${src_dir}/*")

foreach( each_file ${_file_list} )
  set(destinationfile "${dst_dir}/${each_file}")
  set(sourcefile "${src_dir}/${each_file}")
  if(NOT EXISTS ${destinationfile} OR ${sourcefile} IS_NEWER_THAN ${destinationfile})
    get_filename_component(destinationdir ${destinationfile} DIRECTORY)
    file(COPY ${sourcefile} DESTINATION ${destinationdir})

This is how you might use it in CMakeLists.txt

# Example CMakeLists.txt
cmake_minimum_required(VERSION 3.7.0)

set(_target Dummy)
add_executable(${_target} src/dummy.c)

set(source_dir "${CMAKE_CURRENT_SOURCE_DIR}/configs")
set(dest_dir "$<TARGET_FILE_DIR:${_target}>")

# Copy changed files from config to the binary folder after
# a successful build
add_custom_command(TARGET ${_target}
    -P "${CMAKE_CURRENT_SOURCE_DIR}/cmake/update_directory.cmake"

Caveat! CMake post build steps are executed only if the build is really needed, if target is up to date no command is executed.

Get full example from https://github.com/tikonen/blog/tree/master/cmake/update_directory

C++11 Variadic Templates implementation of parameterized strings

C++11 introduces variadic templates that allow nice way to have generic functions with unknown arguments, especially when used in recursive way. This makes easy to implement functions that before were cumbersome to write or hard to use.

Nice use case are parametric formatted strings where part of the strings are replaced with run time data. For example:

"Hello {0}, how are you?"
"Hello {name}, you logged in last {date}".

This find of format is quite easy to implement with recursive variadic templates so that it supports both indexed  and named replacement.

inline std::string format_r(int /*pos*/, std::string format) { return format; }
inline std::string format(const std::string format) { return format; }

template <typename T, typename... ARGS>
std::string format_r(int pos, std::string format, const T&amp; value, ARGS... args);

// convenience short hand for building a format parameter
template <typename... ARGS>
std::pair<ARGS...> _p(ARGS... args) { return std::make_pair(std::forward<ARGS>(args)...); };

template <typename K, typename T, typename... ARGS>
std::string format_r(int pos, std::string format, const std::pair<K, T>& value, ARGS... args)
    std::ostringstream os;
    os << value.second;
    auto parameter = str("{", value.first, "}");
    replace_all(format, parameter, std::string(os.str()));
    return format_r(pos + 1, format, std::forward<ARGS>(args)...);

template <typename T, typename... ARGS>
std::string format_r(int pos, std::string format, const &T value, ARGS... args)
    return format_r(pos, format, std::make_pair(str(pos), value), std::forward<ARGS>(args)...);

template <typename T, typename... ARGS>
std::string format(const std::string format, const &T value, ARGS... args)
    return format_r(0, format, value, std::forward<ARGS>(args)...);


Format function wraps a recursive function that builds the string by replacing one parameter at a time and then processing it again for the next argument until it runs out of parameters.

String conversions are handled with std::ostringstream that supports overloaded ‘<<‘ operation for most common data types.

Format function can be called with index formatting:

using util::format;
format("Hello {0}!", "World"); // Hello World
format("{0} {1}!", "Hello", "World"); // Hello World
format("{0} + {1} = {2}", 1, 2, 3); // 1 + 2 = 3

Or alternatively with explicit parameter names:

using util;
format("Hello {what}!", _p("what", "World"));
format("{word} {other}!", _p("word", "World"), _p("other", "World"));
format("{a} + {b} = {c}", _p("a", 1), _p("b", 2), _p("c", 3));

Get full implementation ftom https://github.com/tikonen/blog/tree/master/variadicformat

Update Gandi.net DNS on Amazon EC2 server boot up

Cloud servers get often randomly picked public IP when they are booted up.  Here is a script can be used to update the Gandi.net DNS records automatically on EC2 server startup.

Step 1. Get API key

Activate and get your Gandi.net API key with  these instructions.  Also, ensure that your Zone file for the domain is updatable. Usually this means that you’ve made copy of the template Zone file.

Step 2. Configure

Download update_domain.py python script and fill in your domain details and the Gandi.net API key.

DOMAIN = "yourdomain.com" # the domain name to update
NAMES  = ["@", "www"]     # A record names to update
API_KEY= '*********'      # fill in gandi API key

Configuration above would update IP for records ‘yourdomain.com’ and ‘www.yourdomain.com’.

You can also redefine the function ‘resolve_ip’ to adapt the script for other environments than EC2. Current implementation uses EC2’s internal REST API to query instances public IP.

Step 3. Run and test

Run the script on the EC2 server, it should resolve the local IP, Zone file and check if records need to be updated.

$ python update_domain.py

Script does dry run by default and will not update records, set DRY_RUN flag to False to update the records for real.

DRY_RUN = False          # Set false to actually modify Zone

Step 4. Run on boot up

When you’re satisfied with the settings and tested script manually, run command ‘crontab -e’ and add the following entry.

@reboot python /home/ubuntu/update_domain.py

Cron will now run the script on every reboot.

Quick and robust C++ CSV reader with boost

This is quick and simple CSV reader based on Boost regular expression token iterator. Parser splits the input with a regular expressions and returns the result as a collection of vectors of strings.
Regular expression handles neatly lot of the complicated edge cases such as empty columns, quoted text, etc..

Parser code

#include <boost/regex.hpp>

// used to split the file in lines
const boost::regex linesregx("\\r\\n|\\n\\r|\\n|\\r");

// used to split each line to tokens, assuming ',' as column separator
const boost::regex fieldsregx(",(?=(?:[^\"]*\"[^\"]*\")*(?![^\"]*\"))");

typedef std::vector<std::string> Row;

std::vector<Row> parse(const char* data, unsigned int length)
    std::vector<Row> result;

    // iterator splits data to lines
    boost::cregex_token_iterator li(data, data + length, linesregx, -1);
    boost::cregex_token_iterator end;

    while (li != end) {
        std::string line = li->str();

        // Split line to tokens
        boost::sregex_token_iterator ti(line.begin(), line.end(), fieldsregx, -1);
        boost::sregex_token_iterator end2;

        std::vector<std::string> row;
        while (ti != end2) {
            std::string token = ti->str();
        if (line.back() == ',') {
            // last character was a separator
    return result;


CSV data with common problem cases, such as empty quotes, commas inside quotes and empty last column.

3,a b,5
7,x,long story no commas
8,y,"some, commas, here,"

Read and parse the CSV data above and output the parsed result

int main(int argc, char*argv[])
	// read example file
	std::ifstream infile;
	char buffer[1024];
	infile.read(buffer, sizeof(buffer));
	buffer[infile.tellg()] = '\0';

	// parse file
	std::vector<Row> result  = parse(buffer, strlen(buffer));

	// print out result
	for(size_t r=0; r < result.size(); r++) {
		Row& row = result[r];
		for(size_t c=0; c < row.size() - 1; c++) {
			std::cout << row[c] << "\t";
		std::cout << row.back() << std::endl;


$ ./reader
a      	b      	c
1      	"cat"  	3
",2"   	dog    	4
3      	a b    	5
4      	empty
5      	        empty
6      	""      empty2
7      	x      	long story no commas
8      	y      	"some, commas, here,"

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

Unity Debug.Log with multiple arguments

Javascript has neat debugging function console.log that accepts multiple variables which makes easy to compose and modify debug output. It’s easy to do same kind of utility script for the Unity.

public class Console
    public static void Log(params object[] a)
        var s =a[0].ToString();
        for ( int i = 1; i < a.Length; i++ ) {
            s += " ";
            s += a[i].ToString();

Now it’s easy to write debug strings like this

var i = 4;
var a = "the";
Console.Log("Hello", i, a, "World");
// => "Hello 4 the World"

Instead of this crappy string concatenation..

var i = 4;
var a = "the";
Debug.Log("Hello " + i.ToString() + " " + a + "World");
// "Hello 4 theWorld" .. forgot one space :(

Quickstart for SQLite in Unity

I had some troubles setting up SQLite for my Unity project for Android and iOS app. Let’s hope this quickstart helps you faster up to speed with your mobile app.

DISCLAIMER. This example is for OS/X development environment and Android and iOS builds. Never tried this for Windows but I guess installing sqlite3.dll should do the trick.

Step 1. Get wrapper API

First, get the SQLite library by @busta117 from Github: https://github.com/Busta117/SQLiteUnityKit

Step 2. Copy API files on your project

Copy the DataTable.cs and SqliteDatabase.cs somewhere under your projects Assets/Scripts/ folder. If you build also for android, then copy libsqlite3.so in your projects Assets/Plugins/Android/ folder. iOS does not need plugin as it has native support for sqlite.

Step 3. Create default database

This is the database that should contain the tables you need with any default data you may want to have. Default database is used to bootstrap the actual in app database.

Create folder Assets/StreamingAssets/. Then create your default template database with sqlite3.

$ sqlite3 Assets/StreamingAssets/default.db
SQLite version 2015-02-25 13:29:11
Enter ".help" for usage hints.
sqlite> create table example (
   ...> name string,
   ...> dummy int
   ...> );
sqlite> .schema example
CREATE TABLE example (
name string,
dummy int
sqlite> insert into example values ("hello world", 1);
sqlite> select * from example;
hello world|1

Now you have default database and your project should have files like these.


Step 4. Database initialization code.

Initialize the database in your main scripts Awake() method. This checks if database already exists and if not, it copies the default db as template.

SqliteDatabase sqlDB;

void Awake() 
    string dbPath = System.IO.Path.Combine (Application.persistentDataPath, "game.db");
    var dbTemplatePath = System.IO.Path.Combine(Application.streamingAssetsPath, "default.db");

    if (!System.IO.File.Exists(dbPath)) {
        // game database does not exists, copy default db as template
        if (Application.platform == RuntimePlatform.Android)
            // Must use WWW for streaming asset
            WWW reader = new WWW(dbTemplatePath);
            while ( !reader.isDone) {}
            System.IO.File.WriteAllBytes(dbPath, reader.bytes);
        } else {
            System.IO.File.Copy(dbTemplatePath, dbPath, true);
    sqlDB = new SqliteDatabase(dbPath);

You can use the script execution order setting to ensure that this code is always executed first.

Step 5. Use the database!

API supports normal selects, inserts and updates.

var result = sqlDB.ExecuteQuery("SELECT * FROM example");
var row = result.Rows[0];
print("name=" + (string)row["name"]);
print("dummy=" + (int)row["dummy"]);

API is simple to use, check detailed documentation from the https://github.com/Busta117/SQLiteUnityKit.

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 )
    # find rectangle width
    width = 1
    WHILE contains( (tile.x + width, c.y,  tiles )
      width = width + 1
    # find rectangle height
    height = 0
    stop = false
       height = height + 1
       LOOP FROM x = tile.x TO tile.x + width
         IF NOT contains( (x, tile.y + height), tiles )
            stop = true
            x = x + 1
    UNTIL stop  

    RETURN (width, height)

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
  • add( item, list ) – Adds item to a list
  • 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
  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)
            remove( (x, y), tiles )
    # if big enough rectangle add it to list
    IF width > 1 AND height > 1
      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])
          remove(rectangles[j], rectangles)
    i = i + 1

  RETURN rectangles

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");
// reading data
if(PlayerPrefs.HasKey("foobar")) {
    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 ();
	public static T LoadObject<T>(string key)
		if (!PlayerPrefs.HasKey(key))
			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);

To load and save your classes, declare them as 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);

Reading classes is also simple

PlayerData data;
data = SerializerUtil.LoadObject<PlayerData>("player1");
// 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.

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>();	


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");