your daily cup of tea™

powered by

Terrible bash is worse than bash

There’s endless cargo cult about bash being a terrible language and how it should be avoided in favor of go and python for any script longer than N lines. The fact is, no language is going to protect you from being a terrible programmer.

There are many good reasons for using bash where it is suited. There are many good reasons for _not_ using bash where it is not suited.

No matter what the reason is though, there’s no excuse for not using ShellCheck when writing Bash scripts. Every warning and error is clearly documented at https://github.com/koalaman/shellcheck/wiki. It’s an amazing tool, give it a try.

cmdbikes: a terminal client for Citybikes

Lo and behold cmdbikes, a client to get bike share information right at your terminal.

cmdbikes

You can install it by

$ pip install cmdbikes

Looks good, but why?

Most of the time I spend on Citybikes is either working on pybikes or the API but rarely using it, aka eating my own dog food. For a while I thought the API syntax was sufficiently straightforward to not even need an interface for a language. Turns out I was wrong: the v2 syntax of the API has some caveats and having an abstraction over it helps make everything easier and cleaner.

I first noticed this whilst attending an open data Hackatiño organized by Coruña Dixital and GPUL. Even though I was invited to just be part of the jury, being in a room full of people coding made me want to join in on the fun and prompted me to start working on a telegram bot for Citybikes (which I plan to release on the following weeks/months).

It’s impossible to assume an API is going to have a perfect representation, so abstracting it in some way will always hide the ugly parts and will make building API consumers easier. There are already some interfaces for other languages but I haven’t find any for python, most probably due to the fact that requests is an ubiquitous library that makes things much easier.

Precisely for that reason I decided to create python-citybikes, an interface for the Citybikes API that makes working with it a real pleasure. Some things might change so I will keep it under 0.1 for a while.

The cool part of python-citybikes is that it abstracts all code relating to requesting stuff and from the code point of view, all resources are accessed just when they are needed and saved for later reuse (though an update on the data can be forced).

This snippet, for instance, gives you the first station of the first network on the API.

import citybikes

client = citybikes.Client()
# This will do a request to https://api.citybik.es/v2/networks
a_network = next(iter(client.networks))
# This will do a request to https://api.citybik.es/v2/networks/foobar
an_station = next(iter(a_network.stations))
# This will do no further requests
len(client.networks)
# Neither will this
len(an_station.stations)

This one instantiates a network by its id

import citybikes

client = citybikes.Client()
bicing = client.Network(client, uid='bicing')
# This will do a request to https://api.citybik.es/v2/networks/bicing
print(bicing)
# This will not do further requests
len(bicing.stations)

Another good thing of having an interface for an API is that it allows the addition of utility functions. In this case, I added a near function that will return resources based on distance to a given point.

import citybikes

# Gives you 5 nearest stations on a given lat / lng
lat, lng = 40.7831, -73.9712
client = citybikes.Client()
network = next(iter(client.networks.near(lat, lng)))
stations = list(network.stations.near(lat, lng))[:5]

See where this is going? The best way to assert that an interface for an API is useful is by writing a simple terminal client to play with the API, and that’s what cmdbikes is. Even though it would be fairly easy to bundle cmdbikes together with python-citybikes, I have decided against it. This way I get to feel what’s like to install and use it separately.

This is not the first time I think about writing a terminal client for Citybikes. Some years ago I did a live coding exercise on a talk at pycones 2014 precisely about that. Although, since the talk was about pybikes, the exercise used pybikes and not the API directly.

All in all, writing cmdbikes and python-citybikes has been a useful exercise. For a long time I’ve avoided learning the proper way to publish a package on pypi or writing things on python 3.

Turns out writing a proper package and publishing on pypi is not that difficult (at least anymore) and it’s straightforward to write new python 3 code that is compatible with python 2.7 (at least for a simple case like this).

Revisitando BiciMAD

Hace dos años publiqué una “auditoria de seguridad” de BiciMAD. Entrecomillado, porque no era tal. Usando un par de herramientas a disposición de la mayoría salieron errores que no se deberían permitir en ningún proyecto público-privado. Éso era sólo la punta del iceberg, se encontraron más gazapos, hubo amenazas, se escribieron artículos y, como es costumbre, se olvidó todo para dar paso al siguiente escándalo.

De no ser por mi proyecto, Citybikes, yo también me habría olvidado. Para contextualizar, Citybikes es un agregador de sistemas de bicicletas públicas y a día de hoy, es la fuente pública más utilizada para crear desde apps a proyectos de investigación que requieran datos sobre bicicletas públicas.

Ante la duda sobre si incluir BiciMAD al proyecto, mi decisión fue la de no hacerlo hasta que no se ofreciera desde el ayuntamiento o la empresa gestora de una fuente abierta y claramente licenciada de datos (para el que no lo sepa, algo conocido como “open data”).

Bien, han pasado dos años. ¿Ha cambiado algo?

La página de BiciMAD sigue mostrando el siguiente ridículo “mapa-imagen”.


Los datos sobre localización y disponibilidad de las bases (que son los que realmente importan) siguen sin ser públicos. Ésto es un extracto de la propuesta en el portal de datos de Madrid.

Información completa BiciMad (NO VIABLE)
Resumen de la propuesta: “Informacion completa BiciMad ”
Fecha de recepción: 30/09/2015
Propuesto por: ciudadano
Estado:NO VIABLE

Actualmente la aplicación biciMad de gestión del servicio público de bicicleta no dispone, en tiempo real, de la información que se solicita, por lo que actualmente no es viable que dicha información se publique en el portal de Datos abiertos por cuestiones técnicas. Creemos que en el plazo de un año, podríamos disponer, con la colaboración y apoyo de la EMT, de una aplicación más enfocada a la actual política de transparencia en beneficio de todos.
Actualmente, ya se publica en el Portal información sobre la bicicleta pública como la posición (georreferenciada) de las estaciones, las incidencias (SYR), media de bicicletas disponibles diaria u usos diarios, tanto de abonados mensuales como ocasionales y el importe pagado en concepto de indicadores de calidad del servicio.

No obstante, si tenemos previsto a lo largo de la primera quincena del mes de junio, publicar en el Portal de Datos abiertos una mayor información sobre biciMad. Entre esta información estarían los datos completos de los gastos del Ayuntamiento por este servicio.

Recientemente ha llegado una contribución a pybikes (una de las partes fundamentales de Citybikes) que añade el sistema de BiciMAD. Dado que, tras dos años, todavía hay excusas “técnicas” sobre la imposibilidad de abrir ésta fuente, no tengo más remedio que aceptar la contribución. Al menos ahora BiciMAD dispone de una API y un mapa online, aunque sea a través nuestro, y sus usuarios podrán elegir entre la multitud de aplicaciones que ya funcionan con Citybikes.

A disfrutar.

Configuring the Polaroid Cube on Linux (or anywhere)

The Polaroid Cube is all fun and games until you see the only way to configure it is through a program for either Windows or OS X.

Fortunately that configuration program does not do anything fancy, it just edits the files Setting.txt and time.txt that live in the root level of the sdcard. These files are read by the firmware of the camera when powered on, and can be edited by any text editor. The syntax is a bit sloppy.

CUBE-V1.01 
UPDATE:N           <--- Set this field to Y before saving!
        FORMAT     <--- No idea
LightFrequency:1   <--- Europe: 50Hz(1), US: 60Hz(0)
TimeStamp:0        <--- Show a timestamp on the topleft corner of videos (dashcam)
CycleRecord:0      <--- Record a video in loop (dashcam)
BuzzerVolume:0     <--- Set this to 0 for disabling the annoying beep. 1 to 50 if you like it
-------------------------------
LightFrequency
	0 ~ 1, def:0, 0:60Hz  1:50Hz
TimeStamp
	0 ~ 1, def:0, 0:Off   1:On
CycleRecord
	0 ~ 1, def:0, 0:Off   1:On
BuzzerVolume
	0 ~ 50, def:5

Setting.txt

UPDATE:N             <--- Set this field to Y before saving!
 
2014-10-20 00:57:44  <--- Set with current date, YYYY-MM-DD HH:MM:SS  

time.txt

Notice the two dashcam options. Is it an added feature or a hint of the Cube's hardware origin? Even if it is just a glorified dashcam with a sexy underwater case and the Polaroid brand slapped into it, this toy is well worth the buzz: nice concept, fits on the pocket, has a magnet and feels nice on the hand.

Writing a simple QML client for configuring the Polaroid Cube should be simple enough, but I guess it's not really worth the time: Text is the universal interface, maybe another day.

Auditoria de seguridad: BiciMAD

Tras varios años en CityBikes, cada vez que aparece un sistema nuevo de bicicletas realizo un análisis general sobre el funcionamiento de sus sistemas. Qué sorpresa éste lunes cuando llegué a casa y me enteré de que BiciMAD ya está en marcha.

Ubicación de las estaciones

Normalmente, lo primero que hago es consultar si el sistema pone a la disposición un mapa en su página web: http://www.bicimad.com/mapa.html.

Si miramos el código fuente, podemos ver en la línea #158 como no aparecen las estaciones que deberían pintarse en el mapa. Mi única suposición es que varios servicios ya han estado scrapeando la web y desde el ayuntamiento o bonopark se ha decidido atajar el asunto.

var estaciones = [
					
	                  ]; 

Pero qué hay de las aplicaciones móviles? De alguna forma accederán a esos datos… El primer paso será descargarse la aplicación de android de bicimad y usarla. Curiosamente, no se puede usar sin estar dado de alta, pero eso tiene fácil solución. Tendremos que decompilar la aplicación y rastrear strings en búsqueda de algún servidor escondido ;) La navaja suiza en éste caso se compone de: Dex2jar, apktool y jd. No es que tengamos especial interés en el código fuente de la aplicación, sólo en las cadenas de texto que representen urls:

grep -r "http://" .
...
./json/JSONParser.java: public static final String URL_SERVIDOR = "http://xxx.xxx.xxx.xx/bicimadMovil/";
./json/JSONParser.java: public static final String url_all_estaciones = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_all_estaciones.php";
./json/JSONParser.java: public static final String url_change_password = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/change_password.php";
./json/JSONParser.java: public static final String url_enviar_push_bienvenida = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/send_push_welcome.php";
./json/JSONParser.java: public static final String url_estaciones_cercanas = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_estaciones_cercanas.php";
./json/JSONParser.java: public static final String url_generate_password = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/generate_new_password.php";
./json/JSONParser.java: public static final String url_get_datos_usuario = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_datos_usuario.php";
./json/JSONParser.java: public static final String url_get_info_tarjeta_consorcio = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_info_tarjeta_consorcio.php";
./json/JSONParser.java: public static final String url_get_ranking_usuarios = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_ranking_usuarios.php";
./json/JSONParser.java: public static final String url_get_ruta_usuario = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_historial_rutas_usuario.php";
./json/JSONParser.java: public static final String url_get_user = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_usuario.php";
./json/JSONParser.java: public static final String url_get_user_by_dni = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_usuario_por_dni.php";
./json/JSONParser.java: public static final String url_get_weather = "http://api.openweathermap.org/data/2.5/weather?q=Madrid,Spain";
./json/JSONParser.java: public static final String url_registrar_incidencia = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/registrar_incidencia.php";
./json/JSONParser.java: public static final String url_reservar_base = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/set_base_reservada.php";
./json/JSONParser.java: public static final String url_save_new_user = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/set_new_usuario.php";
./json/JSONParser.java: public static final String url_save_ruta = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/set_ruta_usuario.php";
./json/JSONParser.java: public static final String url_submit_form_alta = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/submit_form_tpv.php";
./json/JSONParser.java: public static final String url_submit_form_alta_tutor = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/submit_form_tpv_tutor.php";
./json/JSONParser.java: public static final String url_submit_form_recarga = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/submit_form_recarga_tpv.php";
./json/JSONParser.java: public static final String url_update_user = "http://xxx.xxx.xxx.xx/bicimadMovil/functions/update_usuario.php";
...

Atiza! Bueno, para empezar tenemos ya un enlace a un feed de datos.

curl http://xxx.xxx.xxx.xx/bicimadMovil/functions/get_all_estaciones.php | json_pp
{
   "success" : 1,
   "estaciones" : [
      {
         "porcentaje" : 62.5,
         "latitud" : "40.4168961",
         "longitud" : "-3.7024255",
         "numero_bases" : "24",
         "libres" : "15",
         "luz" : "0",
         "idestacion" : "1a",
         "activo" : "1",
         "numero_estacion" : "1a",
         "nombre" : "Puerta del Sol",
         "direccion" : "Puerta del Sol No 1"
      },
      {
         "porcentaje" : 45.833333333333,
         "latitud" : "40.4170009",
         "longitud" : "-3.7024207",
         "numero_bases" : "24",
         "libres" : "11",
         "luz" : "0",
         "idestacion" : "1b",
         "activo" : "1",
         "numero_estacion" : "1b",
         "nombre" : "Puerta del Sol",
         "direccion" : "Puerta del Sol No 1"
      },
      {
         "porcentaje" : 54.166666666667,
         "latitud" : "40.4205886",
         "longitud" : "-3.7058415",
         "numero_bases" : "24",
         "libres" : "13",
         "luz" : "0",
         "idestacion" : "2",
         "activo" : "1",
         "numero_estacion" : "2",
         "nombre" : "Miguel Moya",
         "direccion" : "Miguel Moya No 1"
      },
      {
         "porcentaje" : 22.222222222222,
         "latitud" : "40.4302937",
         "longitud" : "-3.7069171",
         "numero_bases" : "18",
         "libres" : "4",
         "luz" : "0",
         "idestacion" : "3",
         "activo" : "1",
         "numero_estacion" : "3",
         "nombre" : "Conde Suchil",
         "direccion" : " Plaza Conde Suchil No 2-4"
      },
      ...
   ]
}

Pero aún hay más, sin tan siquiera querer mirar urls tan jugosas como get_usuario_por_dni, el uso de http (no cifrado) para registrarse y hacer login desde la aplicación o analizar a fondo JSONParser nos encontramos con las siguientes joyas:

bicimad
key

Es eso que veo ahí una clave RSA privada para enviar notificaciones push a los dispositivos? Para los legos en materia, suponiendo que la clave esté en uso se podría, por ejemplo, enviar publicidad de parte de BiciMAD a todas las personas con la aplicación instalada. Es decir, suplantar la identidad de BiciMAD. Sin nombrar el resto de scripts de administración que tienen públicos en el listing, PRUEBA.php, etc. Llegados a éste punto decido dejar de hurgar en el bote de gusanos antes de ensuciarme demasiado. Ésto es sólo la punta del iceberg.

Un proyecto enmarcado en el Lote 5 de la contratación de gestión de los servicios públicos de Madrid de 884 millones de euros en los próximos 12 años, con licitación a Bonopark S.L. de 25 millones de euros en 10 años… no lo tengo muy claro.

Me gustaria añadir cómo lo ocurrido aquí defiende la tesis sostenida por CityBikes:

  1. Los datos deben ser abiertos. Más aún cuando el proyecto es público.
  2. Los datos deben ser propiedad del ayuntamiento y nunca de la empresa gestora. Ésta “cláusula” permite al ayuntamiento desarrollar libremente aplicaciones móviles sin depender de la empresa gestora o como me gusta llamarlo, sin que la empresa gestora secuestre los datos.
  3. Los datos son más importantes que las aplicaciones móviles: con datos se pueden fabricar aplicaciones, con las aplicaciones no se fabrica nada (excepto en algunos casos frustraciones).

Recomiendo encarecidamente al ayuntamiento de Madrid seguir los pasos de otros ayuntamientos en política de apertura de datos, como Londres o Barcelona. También al gobierno de España inspirarse en la política de datos abiertos de Francia y su licencia de datos abiertos Open Data Licence que recientemente obligó a JCDecaux a proporcionar una API pública.

En general, la misión de CityBikes pasaría por incorporar éstos datos en nuestras fuentes y ponerlos a la disposición del público de forma libre ya sea para consumirlo desde aplicaciones de terceros como para poder montar proyectos relacionados. Ésta vez, no voy a incluir los datos de BiciMAD en CityBikes ni pybikes hasta que los problemas en sus sistemas informáticos estén “resueltos” y se provea, desde BiciMAD o el ayuntamiento de Madrid, de un feed de estaciones correctamente licenciado, tal como se nos vende desde el gobierno central: http://datos.gob.es/.

Categorizing data feeds at CityBikes

Heads up for a boring, but needed, post on categorization. CityBikes (API) aggregates to date 176 data sources of different bike sharing systems. One of the main efforts of this project is keeping everything in order to avoid duplicating implementation of feeds that share the same (or at least similar) syntax. In order to understand how to add a new city to the project it’s necessary to know the categorization of feeds inside CityBikes. Let’s make some analysis to be able to name the feeds for what they are.
(more…)

A conky config for thinkpads

Lately I was feeling a bit nostalgic about how the desktop looked when I started playing with linux, and decided that it was time to write myself a Conky config to pimp my laptop.

thinky

Much of the stuff could have been done using the Lua and Cairo API from Conky, but I played it off with just a bash script and iconic fontsets.

thinky

The cool thing about it is that some icons change depending on the state. For instance, the battery icon displays the charge level, and blinks if the charge level < 5%. Other features include:

  • An indicator for your ThinkLight™
  • Battery status
  • Volume and brightness controls
  • CPU and Memory usage
  • Disk usage
  • Network usage
  • CapsLk indicator

The light indicator, brightness and volume come from the ibm acpi module, thus some changes may be needed to make it work without it.

Installation

git clone https://github.com/eskerda/thinky.git ~/.thinky
cp ~/.thinky/fonts/*.ttf ~/.fonts
conky -c ~/.thinky/conkyrc

Credits

The main font is OswaldFont by Vernon Adams, and the icons provided in the thinky-glyphs.ttf file are part of the following iconic fontsets: Font Awesome, Typicons, Entypo; repackaged into a single file using Fontello.

Dungeon generation using BSP trees

Essentially, a binary space partition algorithm will recursively divide a surface into two for a number of iterations. A binary tree provides the most obvious data structure to traverse the different levels of partitions.

For partitioning, in each iteration the direction of the division -horizontal or vertical- is assigned randomly and so is the size of the first partition, while the second just takes the remaining of the space. Later, on the leafs of the tree (down-most nodes), rooms can be grown within the container, be it randomly or by assigning some constraints that suit the generation. Finally, by connecting the center of each one of the partitions with his brother, all the partitions get connected and accessible.

bsp-dungeon-generation

Maybe it’s a good idea to check the interactive demo of the code that comes ahead before starting. To increase the number of iterations make sure to increase the map size accordingly.

Let’s get into it. First we need a toy implementation of a binary tree. Do not consider the following feature proof or efficient code-wise.

var Tree = function( leaf ) {
    this.leaf = leaf
    this.lchild = undefined
    this.rchild = undefined
}

That’s it. Well, we might sooner or later need some auxiliary functions to get an specific level of the tree and to get the down-most bottom leafs of it, be it for debugging or just for the exercise.

Tree.prototype.getLeafs = function() {
    if (this.lchild === undefined && this.rchild === undefined)
        return [this.leaf]
    else
        return [].concat(this.lchild.getLeafs(), this.rchild.getLeafs())
}

Tree.prototype.getLevel = function(level, queue) {
    if (queue === undefined)
        queue = []
    if (level == 1) {
        queue.push(this)
    } else {
        if (this.lchild !== undefined)
            this.lchild.getLevel(level-1, queue)
        if (this.rchild !== undefined)
            this.rchild.getLevel(level-1, queue)
    }
    return queue
}

Tree.prototype.paint = function(c) {
    this.leaf.paint(c)
    if (this.lchild !== undefined)
        this.lchild.paint(c)
    if (this.rchild !== undefined)
        this.rchild.paint(c)
}

This should be enough to keep things forward. Again, an array mapped tree would avoid us some unnecessary recursive steps, but this is a demo, right?

Now, some utils that will come handy

var Point = function(x, y) {
    this.x = x
    this.y = y
}

function random(min, max) {
    return Math.floor(Math.random() * (max - min + 1) + min)
}

Next thing we need a container prototype. Easy as pie:

var Container = function(x, y, w, h) {
    this.x = x
    this.y = y
    this.w = w
    this.h = h
    this.center = new Point(
        this.x + (this.w/2),
        this.y + (this.h/2)
    )
}

Container.prototype.paint = function(c) {
    c.strokeStyle = "#0F0"
    c.lineWidth   = 2
    c.strokeRect(this.x * SQUARE, this.y * SQUARE,
                 this.w * SQUARE, this.h * SQUARE)
}

Okay, let’s build this tree. We need a function that grows a binary tree of containers.

function split_container(container, iter) {
    var root = new Tree(container)
    if (iter != 0) {
        var sr = random_split(container)
        root.lchild = split_container(sr[0], iter-1)
        root.rchild = split_container(sr[1], iter-1)
    }
    return root
}

And now the actual function that splits a container

function random_split(container) {
    var r1, r2
    if (random(0, 1) == 0) {
        // Vertical
        r1 = new Container(
            container.x, container.y,             // r1.x, r1.y
            random(1, container.w), container.h   // r1.w, r1.h
        )
        r2 = new Container(
            container.x + r1.w, container.y,      // r2.x, r2.y
            container.w - r1.w, container.h       // r2.w, r2.h
        )
    } else {
        // Horizontal
        r1 = new Container(
            container.x, container.y,             // r1.x, r1.y
            container.w, random(1, container.h)   // r1.w, r1.h
        )
        r2 = new Container(
            container.x, container.y + r1.h,      // r2.x, r2.y
            container.w, container.h - r1.h       // r2.w, r2.h
        )
    }
    return [r1, r2]
}

Good, now let’s throw it into a canvas! The wording here might look a bit weird, just assume we are entering this in a development console.

var canvas       = document.getElementById('viewport')
var MAP_SIZE     = 50
var SQUARE       = canvas.width / MAP_SIZE
var N_ITERATIONS = 4

var c_context = canvas.getContext('2d')

var main_container = new Container(0, 0, canvas.width, canvas.height)
var container_tree = split_container(main_container, N_ITERATIONS)

c_context.fillStyle = "#000"
c_context.fillRect(0, 0, canvas.width, canvas.height)
container_tree.paint(c_context)

BSP gone wild
Woosh, not much impressive, this barely resembles a Piet Mondrian scam.

The ugly bits

Randomness it’s all good and fun, until you find out that containers sized too small or too large will result in weird looking results, so here I am discarding any container with a horizontal or vertical ratio smaller than a predefined one. Too aggressive ratios will follow with growing the stack size out of the heap limit.

I do not know if this is the best solution, or if I should not worry about too small partitions, or for instance if I could generate the random width or height with a minimum value (though, I do not like that, as it makes the algorithm code as straightforward. If we define a minimum of 3 squares, what happens when you are confronted by an hypothetical partition of 4 squares?).

function random_split(container) {
    var r1, r2
    if (random(0, 1) == 0) {
        // Vertical
        r1 = new Container(
            container.x, container.y,             // r1.x, r1.y
            random(1, container.w), container.h   // r1.w, r1.h
        )
        r2 = new Container(
            container.x + r1.w, container.y,      // r2.x, r2.y
            container.w - r1.w, container.h       // r2.w, r2.h
        )

        if (DISCARD_BY_RATIO) {
            var r1_w_ratio = r1.w / r1.h
            var r2_w_ratio = r2.w / r2.h
            if (r1_w_ratio < W_RATIO || r2_w_ratio < W_RATIO) {
                return random_split(container)
            }
        }
    } else {
        // Horizontal
        r1 = new Container(
            container.x, container.y,             // r1.x, r1.y
            container.w, random(1, container.h)   // r1.w, r1.h
        )
        r2 = new Container(
            container.x, container.y + r1.h,      // r2.x, r2.y
            container.w, container.h - r1.h       // r2.w, r2.h
        )

        if (DISCARD_BY_RATIO) {
            var r1_h_ratio = r1.h / r1.w
            var r2_h_ratio = r2.h / r2.w
            if (r1_h_ratio < H_RATIO || r2_h_ratio < H_RATIO) {
                return random_split(container)
            }
        }
    }
    return [r1, r2]
}

Ok, run again!

var canvas           = document.getElementById('viewport')
var MAP_SIZE         = 50
var SQUARE           = canvas.width / MAP_SIZE
var N_ITERATIONS     = 4
var DISCARD_BY_RATIO = true
var H_RATIO          = 0.45
var W_RATIO          = 0.45

var c_context = canvas.getContext('2d')

var main_container = new Container(0, 0, canvas.width, canvas.height)
var container_tree = split_container(main_container, N_ITERATIONS)

c_context.fillStyle = "#000"
c_context.fillRect(0, 0, canvas.width, canvas.height)
container_tree.paint(c_context)

BSP with filter ratios
Much more pleasing to the eye. It’s true that a pattern-like structure can be seen and by discarding small results epic randomness is also being discarded, with the possibility to delete rooms that are too small or impossible (hence, resulting in one less room in the map). In any case, the option of discarding is left open, and the results wielded are much more intelligible just for this post.

At the start I was looking after a city-like partition. To see if BSP will yield me what I was looking after, I did set the recursion level to 9 with a map size of 500 squares. The results resemble what I want, and give me enough material to move to the next stage.

Massive BSP

Into the rooms and paths

For the purpose of my generator both rooms and paths are a bit out of the scope as it is not exactly what I am looking for yet. However, I will include them for the sake of completeness, so inaccuracies should be expected.

As mentioned earlier in the post, when we are happy with a recursion level, rooms are placed within each container. The sizing on the room can be defined by any rules. In this example, rooms are grown with a random padding ranging from 0 to a third of the room size (for each of the sides). By allowing it to be 0, the possibility of touching rooms is contemplated, which should give interesting results.

var Room = function( container ) {
    this.x = container.x + random(0, Math.floor(container.w/3))
    this.y = container.y + random(0, Math.floor(container.h/3))
    this.w = container.w - (this.x - container.x)
    this.h = container.h - (this.y - container.y)
    this.w -= random(0, this.w/3)
    this.h -= random(0, this.w/3)
    return this
}
Room.prototype.paint = function(c) {
    c.fillStyle = "#888"
    c.fillRect(this.x * SQUARE, this.y * SQUARE,
               this.w * SQUARE, this.h * SQUARE)
}

Using the helper function to get the leafs of the tree rooms are created dependent of each one of them and later its paint function is called.

var canvas           = document.getElementById('viewport')
var MAP_SIZE         = 50
var SQUARE           = canvas.width / MAP_SIZE
var N_ITERATIONS     = 4
var DISCARD_BY_RATIO = true
var H_RATIO          = 0.45
var W_RATIO          = 0.45

var c_context = canvas.getContext('2d')

var main_container = new Container(0, 0, canvas.width, canvas.height)
var container_tree = split_container(main_container, N_ITERATIONS)

c_context.fillStyle = "#000"
c_context.fillRect(0, 0, canvas.width, canvas.height)
container_tree.paint(c_context)
var leafs = container_tree.getLeafs()
for (var i = 0; i < leafs.length; i++) {
    new Room(leafs[i]).paint(c_context)
}

BSP with rooms

Sweet. Now let’s add a way for paths to be drawn on the canvas. Again, the purpose of this demo is just on drawing the stuff, so we are not going to save them in any structure, nor carve it into a tile map. Let’s see what happens if we draw a line between the centers of containers with the same parent.

Container.prototype.drawPath = function(ctx, container) {
    ctx.beginPath()
    ctx.lineWidth = SQUARE
    c.strokeStyle = "#888"
    c.moveTo(this.center.x * SQUARE, this.center.y * SQUARE)
    c.lineTo(container.center.x * SQUARE, container.center.y * SQUARE)
    c.stroke()
}
var draw_paths = function(ctx, tree) {
    if (tree.lchild == undefined || tree.rchild == undefined)
        return
    tree.lchild.leaf.drawPath(ctx, tree.rchild.leaf)
    draw_paths(ctx, tree.lchild)
    draw_paths(ctx, tree.rchild)
}

var canvas           = document.getElementById('viewport')
var MAP_SIZE         = 50
var SQUARE           = canvas.width / MAP_SIZE
var N_ITERATIONS     = 4
var DISCARD_BY_RATIO = true
var H_RATIO          = 0.45
var W_RATIO          = 0.45

var c_context = canvas.getContext('2d')

var main_container = new Container(0, 0, canvas.width, canvas.height)
var container_tree = split_container(main_container, N_ITERATIONS)

c_context.fillStyle = "#000"
c_context.fillRect(0, 0, canvas.width, canvas.height)
container_tree.paint(c_context)
draw_paths(c_context, container_tree)
var leafs = container_tree.getLeafs()
for (var i = 0; i < leafs.length; i++) {
    new Room(leafs[i]).paint(c_context)
}

BSP, rooms and paths

Good as done. Now, what about some cleaning up?

var Map = function(canvas) {
    this.width  = canvas.width
    this.height = canvas.height
    this.ctx    = canvas.getContext('2d')
    this.c_tree = undefined
    this.rooms  = []
}

Map.prototype.init = function() {
    var m_container = new Container(0, 0, MAP_SIZE, MAP_SIZE)
    this.c_tree = split_room(m_container, N_ITERATIONS)
    this.growRooms()
}

Map.prototype.growRooms = function() {
    var leafs = this.c_tree.getLeafs()
    for (var i = 0; i < leafs.length; i++)
        this.rooms.push(new Room(leafs[i]))
}

Map.prototype.clear = function() {
    this.ctx.fillStyle = "#000"
    this.ctx.fillRect(0, 0, this.width, this.height)
}

Map.prototype.drawGrid = function() {
    this.ctx.beginPath()
    this.ctx.strokeStyle = "rgba(255,255,255,0.4)"
    this.ctx.lineWidth = 0.5
    for (var i = 0; i < MAP_SIZE; i++) {
        this.ctx.moveTo(i * SQUARE, 0)
        this.ctx.lineTo(i * SQUARE, MAP_SIZE * SQUARE)
        this.ctx.moveTo(0, i * SQUARE)
        this.ctx.lineTo(MAP_SIZE * SQUARE, i * SQUARE)
    }
    this.ctx.stroke()
}

Map.prototype.drawContainers = function() {
    this.c_tree.paint(this.ctx)
}

Map.prototype.drawRooms = function() {
    for (var i = 0; i < this.rooms.length; i++)
        this.rooms[i].paint(this.ctx)
}

Map.prototype.drawPaths = function(tree) {
   if (tree.lchild == undefined || tree.rchild == undefined)
        return
    tree.lchild.leaf.drawPath(this.ctx, tree.rchild.leaf)
    this.draw_paths(tree.lchild)
    this.draw_paths(tree.rchild)
}

Map.prototype.paint = function() {
    this.clear()
    this.drawGrid()
    this.drawContainers()
    this.drawRooms()
    this.drawPaths()
}

Which now can be run as

var map = new Map(document.getElementById('viewport'))
map.init()
map.paint()

bsp-dungeon-generation-random

Feel free to check the playground demo at /demos/dungeon.

The mule at the Blue Systems sprint

A Mule

At the last Blue Systems sprint in Pineda I found a mule roaring outside the house. I love how friendly these animals are. In particular, this one followed me through the fence while walking up the hill, and when I was out of my bike to snap a picture, decided to take his head off the fence. I can only assume this is his preferred spot to creep and get food from strangers.