# Random 2D dungeon generation in Unity using BSP (Binary Space Partitioning) trees

## Intro

The approach and algorithm is based on this Stackexchange answer, and these related resources: eskerda.com/bsp-dungeon-generation and gamedevelopment.tutsplus.com/tutorials/how-to-use-bsp-trees-to-generate-game-maps

The sprites used in this post come from existing games and are used here only for learning purpose.

## Build the structure

Let’s start with a new 2D project in Unity 5. Create a new Game Object called Board for holding the whole dungeon. On this game object create a new Script component called BoardManager. We’ll code the dungeon generation logic into it.

I recommend you refer to the stackexchange answer above for the illustrations of the following steps.

The idea of the algorithm is to start with a rectangular cell representing the whole dungeon. Then we’ll split this dungeon in two sub-dungeons, with a randomly chosen splitting position. The process will be repeated again for each sub-dungeons recursively, until the sub-dungeons are approximately the desired size of a room.

Our BoardManager script should look like this:

Then set the public variables for board and rooms size in the Unity editor.

When launching the game you should have something like this in the console :

## Create the rooms

We now have a tree structure with the leaves corresponding to the smallest sub-dungeons. In each of these leaves we’ll now create a room with a random size.

Add the following variable and method to the SubDungeon class :

And call it in the Start() method :

The output console should look like this:

## Drawing the rooms ½: add a sprite for the floor

Instead of relying on console output, it would be more intuitive to start having a visual representation. First thing is to add a sprite for the floor of the rooms. You can use this one and add it as an asset in your project.

Also be careful to set the Pixels Per Unit to exactly the size of the sprite (16 for this sprite), so that the sprite will cover exactly a square in the board.

Next create a Prefab with this sprite (drag and drop it on the scene screen, then drag and drop back the object in the assets):

In the script we’ll need to add a public GameObject variable to hold this prefab:

Then in the editor drag and drop the prefab to set it.

## Drawing the rooms 2/2: write the code

Back in the script we add a method to draw the rooms. Also as we draw the rooms, we’ll register the drawed squares in a variable representing the board called `boardPositionsFloor`. This variable is not really useful at first but will be essential when starting to construct a game above.

And in the Start() method initialize boardPositionsFloor and call DrawRooms on the root:

You should get something like this in the scene view :

Now that we have a visual feedback, it’s also easier to play with the parameters :

## Connect the rooms: create corridors between rooms

Isolated rooms are not very useful, so we’ll add corridors between them. To do so, we’ll connect each leaf to its sibling. Then going up one level in the tree, we’ll repeat the process to connect parents sub-dungeons, until finally we connect the two initial sub-dungeons (see the stackexchange answer for illustrations).

Add `using System.Collections.Generic;` at the beginning of the script, then in the SubDungeon class add:

We’ll also need a method to get the room of a sub-dungeon. If the sub-dungeon is not a leaf (i.e. doesn’t contain a room), the method will return the room of a child.

And now the method to create the corridor between rooms:

You should see the corridors being created in the console:

It’s hard to see visualize without the corridors being drawed but for this example it would look like this:

## Draw the corridors ½: add the corridor sprite

Same as before for the rooms we’ll need a sprite , a prefab in Unity and variable to hold the prefab:

Remember to correctly set Pixels Per Unit setting:

Next create a prefab:

And add a variable in the code:

And finally set the variable in the editor:

## Draw the corridors 2/2: write the code

The drawing function will be quite similar to the one for the rooms:

In the Start() method, you can call DrawCorridors before DrawRooms to better see what is going on:

If DrawRooms is called before :

Now that the random generation is working future improvements could be adding walls and of course a player sprite and controls and enemies.

And with a camera on the player and some further improvements it can become the basis of a simple rogue-like or dungeon crawler:

# Backbone, Leaflet, Bootstrap, Node.js and MongoDB using Responsive Design

Little webapp hacked with Backbone, Leaflet, Bootstrap, Node.js and MongoDB using Responsive Design.

The landing page is a map with places around you fetched from the database (new places are eventually added through a request to OpenStreetMap). When you click on a place you can see comments from other people and leave yours.

Live Demo (currently down)

Github repo

Mobile

Desktop

Technically the app features these concepts/technologies :

# Paris Public Transports route planning app

TL;DR : RATP Open Data (GTFS) –> JSON graph –> Dijkstra with Priority Queue in JS –> Firefox OS webapp

This is a Paris public transports route planning POC webapp.

DATA come from RATP (Paris Public Transports operator).

You can try it here : http://www.rombdn.com/fxos-metrobusparis/demo2/

Source for the DATA transformation : https://github.com/rombdn/ratp-gtfs-to-json

External libs : Leaflet (map), Firefox OS Building Blocks, JQuery and Bootstrap (for autocompletion, didn’t have time to implement mine)

# Background

When the RATP opened their data earlier this year I thought it was a good opportunity to create an offline route planning app acrosse the whole public transportation network.

The technical challenges were : – The full subway (metro) and bus graph, including edges with informations like durations, had to fit in less than a MB to minimize loading time – The shortest path search had to be fast.

# Conception and implementation

## DATA transformation (GTFS –> JSON Graph)

The DATA provided by RATP are 1GB of flat text files with informations on every route, trips, stop times for each day of the year…

• Collapse stations : in the original DATA, stations are duplicated for every direction (route) and every line. This would have leaded to an overly complicated graph
• Average durations and wait times

The final graph contains approximatly 6000 stations (stops) and around 3 edges per stations instead of 26000 stations and up to 20 edges per station.

Link to data transformation Github project : ratp-gtfs-to-json

### Original DATA

routes.txt : route_id, trip_id, type, line (directory)

trips.txt : route_id, trip_id

stop_times.txt : stop_id, trip_id, arrival_time

stops.txt : stop_id, stop_name

### Graph output :

This is achieved with 2 scripts : the first in C to parse the file stop_times.txt (650MB, millions of entry) to create the raw edges, and the second in ruby to create the graph (JSON format).

## Javascript Shortest Path with Priority Queue

The first version was a straight forward implementation of Dijkstra’s algorithm. It was too slow so I decided to use a priority queue.

I started from a binary heap implementation from the book Eloquent Javascript by Marijn Haverbeke link.

Binary Heap with Keys source (`idFunction` is the method called to get the index).

# Identify Backbone Models in Chrome Heap Profiler

Note: this post is based on the idea of Named Constructors from the Coccyx library

In this post I showed an example of a memory leak in Backbone, and how to troobleshoot it using the Chrome Heap Profiler :

But identifying these views is not easy because models extended from Backbone Model/View have their constructor named `child` in the Heap Profiler.

A solution to this problem would be the possibility to name the constructors. Here is a simple hack to do that :

In backbone.js, around line 1541 :

Simply add a case for an optional constructor name :

Note: due to the use of ‘eval’ it is not safe in production…

Now we can add a ‘constructorName’ in our models/views.

### Example with the leaking view from part 1

Now the Views Constructors are correctly named in the Heap Profiler :

Hope this will help!

# Backbone Memory leaks analysis with Chrome Heap Profiler

## Intro

The Heap Profiler in Chrome is a great tool to analyze memory usage in web applications. Here are some useful links :

Why do we have to worry about memory management in JS when there is a Garbage Collector ? Because memory leaks can still happen : as long as an object is referenced by another it cannot be disposed by the GC. These references are “Retaining Paths” in the Heap Profiler.

A common source of these problems are event binding : events are references, which prevent object to be destroyed after they are removed from the DOM. This can happen with Backbone Views.

## Example

Here is a simple example (using the Backbone global object as an event mediator) :

Console Ouptput :

Nothing should appear in the console because every view is removed after its creation. As we can see this is not the case : the views are still catching `greetingEvent` and displaying a message.

A heap snapshot confirm that all the ZombieViews are still here (extended Backbone models have their constructor named `child`, see this post for a solution).

Why the views aren’t removed ?

## Troobleshoot

If we take a heap snapshot we can see that the greetingEvent is in the retaining path of the views. This path prevent the GC to dispose the object.

Let’s modify the code with a call to `listenTo` instead of `Backbone.on`. With `listenTo` models can keep track of events binded so they can be unbinded by the remove method and thus allow the GC to dispose the attached views.

This time nothing shows up in the console, which is the expected output : all the views where removed, none catched the event.

Note: You may have noted that the views have their constructor named ‘child’ which complicate identification, a solution is provided in this post.

# Linerider clone with HTML5 Canvas and Box2D JS

Dog Sled is a little weekend project game hacked with HTML5 Canvas, Javascript and Box2D :

## Code details

### Main loop

I used Box2DWeb, a javascript port of box2d 2.1. It lacks features like rope joint but I realized it too late… More up to date ports i didn’t try :

Have fun!

Good tutorials : Seth Ladd’s blog

# JMeter HTTP tips and examples

## Load all resources attached to a html file

Useful when working with frames to avoid one http request per frame (I use this a lot when scripting for PeopleSoft ERP).

## Extract a value to a variable with a regular expression

You can use a Debug Listener to adjust the regexp. In this example (PeopleSoft) I checked “Main sample and sub-samples” because the value to be extracted is in a frame.

## Test a variable

In this example I verify that the Regular Expression hereabove worked.

## Javascript in parameters (e.g. to randomize a choice)

First we get the number of values :

Then we replace the parameter with our javascript :

In JMeter it becomes :

Note : The double `\$\$` is due to variable names in PeopleSoft (`AF_PCC_WRK_SELECT_PB\$1`, `AF_PCC_WRK_SELECT_PB\$2`…)