your daily cup of tea™

powered by

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)

cube_hd

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

citybikes-logo

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.

Fun with the Arduino UNO and a NES gamepad

luigi

A while ago I wanted to play the original NES. It turned out my console was broken and so, decided to find a way to connect the NES gamepad to the computer using an Arduino.

I looked on the Internet and found many things, but not exactly what I wanted:

What I found

  • Read the NES gamepad from an Arduino
  • Emulate a keyboard on the computer, and interpret Arduino serial input as keyboard presses.
  • How to build USB firmwares for AVR microcontrollers. How to build an USB firmware for AVR that acts as a gamepad.

What I wanted

  • A NES gamepad that showed on the computer as an USB game HID: something you can plug into any computer / console and will (hopefully) work out of the box, plug and play.

So, all the pieces for the puzzle were there, and the only thing left was to put them together. Now that it’s working as I intended to I have decided to write this post to save some time to anyone interested in building similar things. This post might be too verbose for the purpose of this thing, but what’s the fun on putting something together you can barely understand? I decided to spend more time than usual inspecting all the things involved on the process.

Note that these are not the instructions on how to do it, but a mix up of story, missing gaps of information I found, or at least some useful information to lower the entrance barrier a bit, and some reference links. For instructions check the repository.

TL;DR: I put together a USB HID gamepad with the NES controller and an Arduino.  Also, first post.

P1011229_t

Onto the NES Gamepad

The NES gamepad has a 8-bit shift register that, upon receiving a LATCH saves the state of the 8 buttons (GND means pressed). Clocking a signal through the CLK line, the state byte is shifted through the DATA pin.

    NES gamepad controller pinout

        o 4    1. +5VDC Supply                            INPUT
    1 o o 5    2. ?
    2 o o 6    3. ?                                 _|_|_|_|_|_|_|_|_
    3 o o 7    4. GND                   LATCH  ____|                 |
               5. CLK                              |     IC 4021     |
               6. LATCH                   CLK  ____|\                |----- DATA
               7. DATA                             |/                |
                                                   |_________________|
           ________
    LATCH |        |
    ______|        |______________________________________________________________________________

                     ____      ____      ____      ____      ____      ____      ____      ____ 
    CLK             |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    ________________|    |____|    |____|    |____|    |____|    |____|    |____|    |____|    |__

         _  ________  ________  ________  ________  ________  ________  ________  ________  ______
    DATA  \/    A   \/    B   \/ Select \/  Start \/   Up   \/  Down  \/  Left  \/  Right \/
         _/\________/\________/\________/\________/\________/\________/\________/\________/\______
                     |--12µs--|

A diagram on extracting the input from a NES gamepad. Some pins on the IC 4021 omitted for clarity.

The following code outputs the input from a NES gamepad in binary words.

int CLK = 2;
int LATCH = 3;
int DATA = 4;

byte last_read = 0xFF;

void setup();
void loop();

void setup()
{
    Serial.begin(115200);
    pinMode(CLK, OUTPUT);
    pinMode(LATCH, OUTPUT);
    pinMode(DATA, INPUT);
}

void loop()
{
    byte reading = read_NESpad();
    if (reading != last_read){
         Serial.println(reading, BIN);
    }
    last_read = reading;
}

byte read_NESpad() {
      /*
        NES Word Mapping
        x x x x x x x x
        | | | | | | | |_  A
        | | | | | | |___  B
        | | | | | |_____  SELECT
        | | | | |_______  START
        | | | |_________  UP
        | | |___________  DOWN
        | |_____________  LEFT
        |_______________  RIGHT
     */

  // Send a HIGH pulse to latch. Make 8 shift register store state
  // of all buttons
  digitalWrite(LATCH, HIGH);
  delayMicroseconds(12);
  digitalWrite(LATCH, LOW);

  // Clock the 8 shift register to get the
  // state of the buttons
  byte output = 0x00;
  for (int i = 0; i < 8; i++){
      output |= digitalRead(DATA) << i;
      digitalWrite(CLK, HIGH);
      delayMicroseconds(6);
      digitalWrite(CLK, LOW);
      delayMicroseconds(6);
  }
  return output;
}

This was enough to build a minimum viable hack, consisting on an arduino sketch reading the gamepad and sending it through the serial interface and a Node.js (\o/) server reading it and firing xdotool to emulate key presses. Ugly, but enough for a hit of nostalgia for the rest of the weekend (if you really want to see, it lives on this branch). With this I was on the same as most of the links I found googling around.

After playing with it for a while I sort of felt this was well behind my initial goal. Which I initially wanted was to actually build an USB gamepad you could plug onto your friends’ computers, no install, no anything. Upon researching, I found out that meant flashing a new firmware to the UNO, even if I did not really understand what that meant.

A little guide on Arduino and DFU

Instead of using an specific purpose USB-to-serial chip, the Arduino comes with an ATmega programmed to act as an USB to serial device (so you can upload compiled bytecode from sketches into the EEPROM). That’s what gets detected when you connect the Arduino into the computer. In better words:

The Uno differs from all preceding boards in that it does not use the FTDI USB-to-serial driver chip. Instead, it features the Atmega16U2 (Atmega8U2 up to version R2) programmed as a USB-to-serial converter.
http://arduino.cc/en/Main/arduinoBoardUno

    ____________________
   | o       ···········
RESET ---> + · ·
GND -----> + · ·
  _|____
 |      |
 | USB  |
 |______|
   |
   |

In order for the Arduino UNO to appear (and act) as a different device, a new firmware has to be flashed into the ATmega16U2, by putting it into DFU (direct firmware upgrade) mode which, depending on the board, is done with more or less messy ways which for older versions may require soldering.

Hopefully my board is an R3, which can be cleanly put into DFU mode by jumping the RESET and GND pins on the Atmega16U2 together for a fraction, using a jumper or, if feeling wild, just a piece of copper.

Looking for inspiration

At this point, I did not really know what to do. I could read the NES gamepad from the Arduino using sketches, and was able to flash new firmwares onto the arduino, next step?

LUFA

LUFA (Lightweight USB Framework for AVRs, formerly known as MyUSB) is an open-source complete USB stack for the USB-enabled Atmel AVR8 and (some of the) AVR32 microcontroller series, released under the permissive MIT License (see documentation or project source for full license details). The complete line of Atmel USB AVRs and USB AVR boards are supported by the library, as are any custom user boards, via custom board hardware drivers supplied by the user.
http://www.fourwalledcubicle.com/LUFA.php

Darran Hunt’s Arduino Hacking blog has a nice set of posts with examples on how to build different HID devices using LUFA and Arduino. In particular, there’s one example that emulates an USB joystick with two axis and two buttons, which is almost what I needed. The example is, at the same time, based on one example from the LUFA library, and Arduino’s USB-to-Serial firmware.

HID Devices interact with the USB stack using HID reports. The firmware describes itself as an USB HID Joystick and reads on the serial interface from the main processor (the ATmega328), which means it can read data from the main code (sketch, running on the ATmega328) to the firmware code (running on the ATmega16U2). The sketch handles all the input, and sends it through the serial interface using a packed struct. The firmware just roams there, waiting for data, and then sends it to the USB stack as a proper HID report.

I found Darran’s design on this issue pretty clever and on the line of what Arduino is supposed to feel like. The firmware is doing all the heavy lifting, and all the logic lives on the sketch.

Note that there was no real need to compile a modified version of the firmware. I could be ok by using one example that has 40 buttons, and throttles and more axis. But when I get into something, I really want to understand how all the parts work together. If not, it’s almost time wasted.

HID report descriptors 101

For the USB stack to know what device is it talking to, and how this reports do look like, it uses a descriptor table. In this descriptor table you fill up everything about your device: what’s its purpose, what type of device is it, how many inputs it has and how are they represented. Oh, and it has to be 8 byte aligned, which means adding a padding every time you are sending less than a byte. Everything is documented on the USB HID Specification document (have fun with it).

Some reference links: [wikipedia] [USnooBie’s USB HID Report Descriptor Tutorial 1]

2 Axis
Min Max Value (-100, 100)
2^3 = 8 (size, signed integer), #2 (axis)
4 Buttons
size 1 (boolean), # 4
+ 4bits of padding.

Device and manufacturer ID

Devices identify themselves using a device and manufacturer ID. For acquiring one yourself you would have to pay large sums of money to the USB foundation. I have decided to leave the original Atmel Corp. LUFA Joystick Demo Application.

The whole thing

P1011227_t

Hacking a firmware yourself

You’ll need to:

  • Set up the LUFA environment
  • Read these posts in Darran’s blog, just for reference.
  • Take an example from the LUFA library that suits what you want.
  • Look into arduino’s usb-serial original firmware.
  • Combine them both to interface with the Arduino.
  • Write your HID Descriptor
  • Start hacking.

Chicken and egg

At this point, I assume I could be doing all the ‘nintendo’ parsing part on the firmware, be it by directly interfacing with the INPUT ports or just getting the 8 bits through the serial interface instead of the whole HID Report, but that would make it too specific. Having just a firmware that does one thing, and does it well just keeps everything simpler.

But being that Arduino is meant for easy hacking into microcontrollers, that would not make much sense, and I would be better by just glueing an atmel microcontroller into a NES Gamepad.

Conclusions

After this I would love to put together a project to ease the creation of USB game devices, just by using the arduino library, similar to unojoy. While describing a 30 button – 6 axis – 1 hat switch device could be enough to have a generic firmware, I want my devices to appear on the computer exactly as they are. What I think of would be some compilation variables or a descriptor generator, and then a different protocol of communication between the sketch and the firmware.

Also, I cannot wait to get more gamepads of consoles I did not have, like the SNES and the N64.

Finally, it will be interesting to put two gamepads together on the same board and make them appear as two devices by using report ids on the HID descriptor.