IDs únicas

Publicado por LaNsHoR el 26/05/2014 en Problemas | 5 comentarios

Volvemos con los problemas de la semana. Este es uno de mis favoritos, muy útil para usar en una entrevista de trabajo si queréis poner a prueba al candidato 😉 (debería hacer una colección con este tipo de problemas, porque son simples, pero demuestran mucho de quien los resuelve; me gustan mucho!).

Pregunta: En cualquier lenguaje de programación, escribe una función UID que devuelva un ID (número) único cada vez que se ejecute.

Consideraciones: La función no puede hacer uso de datos o variables globales de ninguna forma ni aceptar parámetros. Toda su funcionalidad debe quedar encapsulada. Tampoco puede ser el método de un objeto.

Ejemplo de ejecución:

x=UID(); //x vale 1
x=UID(); //x vale 2
x=UID(); //x vale 3
/* Nota: Los números pueden o no ser secuenciales,
 el único requisito es que nunca se repitan. */

Expansión (para los que quieran sumar puntos extra): Escribe en cualquier lenguaje de programación, una función GUID que devuelva una función (o puntero a función en lenguajes como C++) según las especificaciones del problema anterior pero que funcionen de forma independiente.

Ejemplo de ejecución:

UID1=GUID();
UID2=GUID();
UID3=GUID();
x=UID1(); //x vale 1
x=UID1(); //x vale 2
x=UID2(); //x vale 1
x=UID1(); //x vale 3
x=UID2(); //x vale 2
x=UID1(); //x vale 4
x=UID3(); //x vale 1

*** SOLUCIÓN ***

El enunciado era sencillo pero la solución puede complicarse si no tomamos una primera decisión correcta. Erful consiguió resolverlo en Javascript (aunque no tenía Internet y no pudo responder con su código) y StormByte iba muy bien encaminado con la solución.

La primera decisión correcta e importante es la elección lenguaje de programación; en algunos lenguajes la solución es trivial… por eso es importante, cuando leemos “en cualquier lenguaje de programación”, no interpretarlo como “nuestro favorito” o “el que más dominamos”; si no “el más adecuado” para el problema.

Necesitamos un lenguaje que soporte clausuras o cálculo lambda.

Con esto, vamos con las soluciones:

Solución Simple en Javascript:

var UID = (function() {
   var id=0; return function() {
      return ++id;
   }
})();
//===========================
var x;
x=UID(); //x vale 1
x=UID(); //x vale 2
x=UID(); //x vale 3

Lo que tenemos es la creación de una función anónima que se ejecuta conforme es definida. Esta función forma la clausura que contiene a una variable id inicializada a 0. Además la función devuelve otra función que retorna e incrementa el valor de id, esta función es la que se asigna a UID, y que cada vez que se ejecuta, tiene acceso a la variable id de ámbito superior que pertenece a la clausura de la función anónima.

Con esta idea, hacer un generador de funciones UID es trivial:

Solución Expandida en Javascript:

function GUID() {
   var id=0;
   return function() {
      return ++id;
   }
};
//===========================
var UID1=GUID();
var UID2=GUID();
x=UID1(); //x vale 1
x=UID1(); //x vale 2
x=UID2(); //x vale 1
x=UID1(); //x vale 3
x=UID2(); //x vale 2

La diferencia es que la función anónima de clausura original, ya no es anónima, si no que se llama GUID y se ejecuta creando una nueva clausura cada vez, devolviendo la función que incrementa y devuelve el valor de id.

En otros lenguajes de programación el planteamiento es el mismo:

Solución Expandida PHP

function GUID() {
   $id=0;
   return function() use (&$id) {
      return ++$id;
   };
}
//===========================
$UID1=GUID();
$UID2=GUID();
echo $UID1(); //1
echo $UID1(); //2
echo $UID2(); //1
echo $UID1(); //3
echo $UID2(); //2

Fijaos en la sintaxis, para ejecutar UID1 y UID2 no se utiliza la sintaxis de llamada a función normal; si no que es necesario indicar que son variables: así a() != $a(). Requiere PHP >= 5.3 para funcionar.

Solución Expandida C++

#include <iostream>
#include <functional>

//===========================
std::function<int()> GUID()
{
    return []()->std::function<int()>
    {
        int id=0;
        return [=]() mutable -> int { return ++id; };
    }();
}
//===========================

int main(int argc, char * argv[])
{
    auto UID1= GUID();
    auto UID2= GUID();

    std::cout << UID1() << std::endl; //1
    std::cout << UID1() << std::endl; //2
    std::cout << UID2() << std::endl; //1
    std::cout << UID1() << std::endl; //3
    std::cout << UID2() << std::endl; //2
    return 0;
}

Para simplificar y evitar el uso de punteros a funciones usamos el tipo function de c++11 (la última versión del estándar C++, requiere G++>=4.7). Usamos el cálculo lambda para crear la clausura necesaria y devolver la función. Si queréis aprender sobre la sintaxis del cálculo lambda en C++ está bien explicada en la documentación de referencia de MSDN.

¿Os animáis a hacer la prueba en otros lenguajes? 😉 ¿Quién nos enseña una solución en LISP o SCHEME?

Pathfinding: A*

Publicado por LaNsHoR el 12/04/2014 en Inteligencia Artificial | 15 comentarios

Introducción

La búsqueda de caminos (pathfinding) es uno de mis problemas favoritos de todos los tiempos y una de las cosas que más he disfrutado programando; por un montón de razones… La primera, es que los humanos creemos erróneamente que es algo que hacemos muy bien, y sólo cuando nos comparamos con una máquina tomamos consciencia de cómo únicamente logramos buenos resultados en entorno sencillos. Por ejemplo, en la imagen siguiente, si estamos en la casilla del círculo marrón y tenemos que ir a la casilla del círculo rojo; y las casillas grises representan un muro, ninguno tenemos problema en esquivar el muro y trazar el camino más corto hacia nuestro destino: la casilla del círculo rojo.

Sin embargo, en la vida real, al conducir o pasear por la calle, no calculamos los caminos entre origen y destino de forma tan matemática como pensamos, y nos dejamos llevar por las anchuras de las avenidas, otros caminos que ya conocemos, la cantidad de luz de una calle, etc. El resultado es que nosotros siempre nos sentimos 100% satisfechos con el camino que hemos elegido, pero muy rara vez este camino es el óptimo; ni el más corto, ni el más rápido.

Me gusta además su enorme utilidad, tendremos que diseñar una solución al problema en cualquier entorno con agentes inteligentes, sistemas robóticos, videojuegos, etc. Y, además, a pesar de su enunciado sencillo, rara vez a los programadores que se enfrentan al problema por primera vez se les ocurre alguna solución que no esté basada en backtracking.

La solución “universal” que durante muchos años ha servido de guía a este problema es el algoritmo A-Estrella (escrito A*). Un algoritmo muy sencillo que ofrece buenos resultados, y ha estado presente en casi todas las aplicaciones de búsqueda de caminos desde el principio de los tiempos hasta la última década.

Vamos a describir en qué consiste y luego lo implementaremos en Javascript.

Desglose y trazas: A*

El problema inicial, como hemos visto, trata de trazar el camino para ir del punto A (círculo marrón) al punto B (círculo rojo).

Idea general:

La primera operación a realizar, es dividir el espacio en casillas. En nuestro ejemplo las casillas son cuadradas, pero realmente podremos adaptar el algoritmo a dividir el espacio de la forma que deseemos (triángulos, hexágonos, etc). A partir de ahora cada casilla será una celda espacial (crearemos una estructura de datos que la represente) relacionada con sus adyacentes y con su “padre”; el padre será la celda por la cual hemos llegado a tener en cuenta a la actual como posible candidata a formar parte del camino final.

Aspectos:

1) Tener dos listas de celdas; una abierta y una cerrada. En la lista abierta iremos introduciendo celdas que tenemos que evaluar, para ver si son buenas candidatas a formar parte del camino final. En la lista cerrada introduciremos las celdas ya evaluadas.

2) La evaluación de las celdas se hace en base a dos factores: la longitud del camino más corto para llegar desde el punto de origen a la celda actual, y la estimación del camino más corto que podría quedar para llegar al destino. La estimación para el destino se hace usando una función heurística, en concreto se suele usar la Distancia Manhattan, que esencialmente consiste en contar cuantas celdas nos separan del destino vertical y horizontalmente, sin movimientos diagonales; como si estuviéramos recorriendo manzanas en una gran ciudad y no pudiéramos atravesarlas, sólo bordearlas; de ahí viene el nombre.

Factores

Cada celda va a tener 3 factores. G, H y F.

– G: Es el coste de ir desde la celda origen a la celda actual. Cada vez que nos movamos un paso en horizontal o vertical, añadiremos 10 puntos de coste. Cada vez que nos movamos en diagonal, añadiremos 14. ¿Por qué 14? Porque aunque geométricamente la proporción exacta debería ser 14.14213 {sqrt(10*10+10*10)}, 14 es una buena aproximación entera que nos hará ganar velocidad al evitar el uso de coma flotante (nota: en javascript en realidad esta mejora no se aplica, ya que todos los números se tratan como floats internamente).

– H: Es la distancia mínima y optimista, sin usar diagonales, que queda hasta el destino. La heurística basada en Distancia Manhattan de la que hemos hablado antes.

– F: Es la suma de G y H.

Traza explicada

Iteración 1

Tras la primera iteración, la celda origen queda en la lista cerrada (border violeta). Las adyacentes quedan en la lista abierta (borde rojo). Las celdas tienen sus tres valores G, H y F calculados. La F aparece en la esquina superior izquierda de cada celda. La G en la inferior izquierda. La F en la inferior derecha.

Además cada celda tiene una bolita azul que indica qué celda es su padre, tras esta iteración, todas las celdas de la lista abierta tienen como padre a la celda origen.

Iteración 2

En esta iteración hemos añadido la celda a la derecha (la de menor F de la lista abierta) de la celda origen a la lista cerrada (borde violeta). No se han producido más cambios.

Iteración 3

Se añade la celda superior derecha desde el origen a la lista cerrada (es la de menor F de la lista abierta) y se añaden las adyacentes que no estaban ya.

Iteración N

Y algoritmo sigue. De forma sencilla, hasta alcanzar el objetivo:

Ejecución de traza interactiva I

Podéis ejecutar el algoritmo paso a paso haciendo clic en la imagen inicial siguiente. Cada clic equivale a una iteración:

Ejecución de traza interactiva II

Vamos a darle más juego al algoritmo. Podemos añadir fácilmente tipos de terrenos con diferentes costes a la hora de transitarlos. En el siguiente ejemplo vamos a usar los siguientes tipos de terreno:

– Césped (verde claro): Movimiento al 100%
– Bosque (verde oscuro): Movimiento al 75% de la velocidad normal
– Agua (azul claro): Movimiento al 50% de la velocidad normal
– Agua profunda (azul oscuro): Movimiento al 10% de la velocidad normal
– Muro (gris): Infranqueable (0% de velocidad)
– Puente de madera (marrón): Movimiento al 90% de la velocidad normal

El escenario es el siguiente:

Y el resultado (clic en la imagen para ampliar):

Podéis ejecutarlo paso a paso en la siguiente simulación (tened en cuenta que habrá interacciones vacías que sólo eliminan nodos). Cada clic en el mapa será una iteración.

Y por último… lo más importante; el código 😉

Como siempre, si tenéis cualquier duda, preguntadme 🙂

Os recomiendo leerlo despacio y entenderlo (es muy sencillo y claro). Se lee bien.

function Map(width, height, cell_size, canvas)
{
	//-- init
	this.width=width || 10;
	this.height=height || 10;
	this.cell_size=cell_size || 50;
	canvas.width=this.width*this.cell_size;
	canvas.height=this.height*this.cell_size;
	this.ctx=canvas.getContext("2d");
	this.origin=0x0;
	this.destiny=0x0;
	//-- inside globals
	var map=this;
	var ctx=this.ctx;
	//-- members
	this.cells=[];
	var terrains=[
		{awkwardness:1.00, color:"#6DBF50", name:"ground"},
		{awkwardness:0.75, color:"#1F7F3A", name:"forest"},
		{awkwardness:0.50, color:"#6FD1FF", name:"water"},
		{awkwardness:0.10, color:"#2B427D", name:"deep_water"},
		{awkwardness:0.00, color:"#26221E", name:"wall"},
		{awkwardness:0.90, color:"#76421E", name:"bridge"}
	];
	// -- allow external access by name (like map.terrain.water...)
	(function indexTerrains()
	{
		map.terrains={};
		for(var i=0;i<terrains.length;i++)
			map.terrains[terrains[i].name]=terrains[i];
	}());
	//-- utils
	this.randTerrain=function()
	{
		var index=Math.floor(Math.random()*terrains.length-0.2);
		return terrains[index>0?index:0];
	}
	this.drawFlag=function(x,y,color)
	{
		var x=x*this.cell_size+this.cell_size/2;
		var y=y*this.cell_size+this.cell_size/2;
		ctx.save();
		ctx.fillStyle=color;
		ctx.strokeStyle="#000";
		ctx.beginPath();
		ctx.arc(x,y,this.cell_size/3,0,2*Math.PI);
		ctx.stroke();
		ctx.fill();
		ctx.restore();
	}
	//-- private classes
	function Cell(x, y)
	{
		this.G="";
		this.H="";
		this.F=this.G+this.H;
		this.x=x;
		this.y=y;
		this.list=0x0;
		this.dad=0x0;
		this.terrain=map.randTerrain();
		this.drawDad=function(x,y)
		{
			ctx.save();
			ctx.fillStyle="#4D92FF";
			ctx.strokeStyle="#000";
			ctx.beginPath();
			ctx.arc(x,y,map.cell_size/10,0,2*Math.PI);
			ctx.stroke();
			ctx.fill();
			ctx.restore();
		}
		this.render=function()
		{
			ctx.save();
			ctx.fillStyle=this.terrain.color;
			ctx.strokeStyle="#000";
			ctx.fillRect(0,0,map.cell_size, map.cell_size);
			ctx.strokeRect(0,0,map.cell_size, map.cell_size);
			//Draw data
			ctx.fillStyle="#000";
			ctx.font = "10px Arial";
			ctx.textAlign="start";
			ctx.textBaseline="top";
			ctx.fillText(this.F,1,1);
			ctx.textBaseline="bottom";
			ctx.fillText(this.G,1,map.cell_size);
			ctx.textAlign="end";
			ctx.fillText(this.H,map.cell_size-1,map.cell_size);
			//Draw list
			if(this.list)
			{
				ctx.strokeStyle=this.list=="open"?"#F00":"#a0F";
				ctx.strokeRect(1,1,map.cell_size-2, map.cell_size-2);
			}
			//Draw dad
			if(this.dad)
			{
				var offset=(map.cell_size/10)*3;
				var x=offset;
				var y=offset;
				if(this.dad.x==this.x)
					x=map.cell_size/2;
				if(this.dad.x>this.x)
					x=map.cell_size-offset;
				if(this.dad.y==this.y)
					y=map.cell_size/2;
				if(this.dad.y>this.y)
					y=map.cell_size-offset;
				this.drawDad(x,y);
			}	
			ctx.restore();

		}
	}
	//-- constructor
	for(var i=0;i<this.width;i++)
	{
		this.cells[i]=[];
		for(var j=0;j<this.height;j++)
			this.cells[i].push(new Cell(i,j));
	}	
	//--methods
	this.render=function()
	{
		for(var i=0;i<this.width;i++)
		{
			for(var j=0;j<this.height;j++)
			{
				ctx.save();
				ctx.translate(i*this.cell_size,j*this.cell_size);
				this.cells[i][j].render();
				ctx.restore();
			}
		}
		if(this.origin)
			this.drawFlag(this.origin.x,this.origin.y,"#A65C3E");
		if(this.destiny)
			this.drawFlag(this.destiny.x,this.destiny.y,"#A92535");
	}
	this.fill=function(terrain, skip_render)
	{
		for(var i=0;i<this.width;i++)
			for(var j=0;j<this.height;j++)
				this.cells[i][j].terrain=terrain;
		if(!skip_render)
			this.render();
	}
	this.rect=function(terrain, x, y, w, h, skip_render)
	{
		for(var i=x;i<x+w;i++)
			for(var j=y;j<y+h;j++)
				this.cells[i][j].terrain=terrain;
		if(!skip_render)
			this.render();
	}
	this.addTerrain=function(terrain)
	{
		terrains.push(terrain);
		indexTerrains();
	}
	this.getAdjacentCells=function(cell)
	{
		var adjacent_cells=[];
		for(var i=cell.x-1;i<=cell.x+1;i++)
		{
			for(var j=cell.y-1;j<=cell.y+1;j++)
			{
				try
				{
					if(this.cells[i][j] && !(i==cell.x && j==cell.y))
						adjacent_cells.push(this.cells[i][j]);
				}
				catch(ex) {}
			}
		}
		return adjacent_cells;
	}
}

function Pathfinding(map)
{
	//OpenList class
	function OpenList()
	{
		var cells=[];
		this.add=function(cell)
		{
			cell.list="open";
			cells.push(cell);
		}
		this.getFirst=function()
		{
			var first=cells.splice(0,1)[0];
			return first;
		}
		this.sort=function()
		{
			cells.sort(function(a,b) {return a.F-b.F;});
		}
		this.contains=function(cell)
		{
			return cells.indexOf(cell)<0?false:true;
		}
	}
	//ClosedList class
	function ClosedList()
	{
		var cells=[];
		this.add=function(cell)
		{
			cell.list="closed";
			cells.push(cell);
		}
		this.contains=function(cell)
		{
			return cells.indexOf(cell)<0?false:true;
		}
	}
	//init
	var open_list=new OpenList();
	var closed_list=new ClosedList();
	var ctx=map.ctx;
	open_list.add(map.cells[map.origin.x][map.origin.y]);
	this.ended=false;
	this.iterations=0;
	//members
	this.next=function(skip_render)
	{
		if(this.ended)
			return;
		this.interations++;
		//get the first cell
		var dad=open_list.getFirst();
		closed_list.add(dad);
		//add the adjacents cells to the open list
		var adjacent_cells=map.getAdjacentCells(dad);
		for(var i=0;i<adjacent_cells.length;i++)
		{
			var cell=adjacent_cells[i];
			//~~~ Start check end
			if(cell.x==map.destiny.x && cell.y==map.destiny.y)
			{
				this.ended=true;
				cell.dad=dad;
				if(!skip_render)
					this.drawPath(cell);
				return cell;
			}
			//~~~ End check end
			//~~~ Start of the exclusion zone
			if(!cell.terrain.awkwardness)
				continue;
			if(closed_list.contains(cell))
				continue;
			if(open_list.contains(cell))
			{
				var awk=cell.terrain.awkwardness;
				//Change the dad and G,H,F if the current path is better
				var newG=parseInt(cell.x!=dad.x && cell.y!=dad.y? dad.G+14/awk : dad.G+10/awk);
				if(cell.G<newG) //worse? ok, skip
					continue;
			}
			//~~~ End of the exclusion zone
			one_change_at_least=true;
			cell.dad=dad;
			//Length to the origin
			var awk=cell.terrain.awkwardness;
			cell.G=Math.round(parseInt(cell.x!=dad.x && cell.y!=dad.y? dad.G+14/awk : dad.G+10/awk));
			//Manhattan heuristic
			var dx=Math.abs(map.destiny.x-cell.x);
			var dy=Math.abs(map.destiny.y-cell.y);
			cell.H=(dx+dy)*10;
			//Update F
			cell.F=cell.G+cell.H;
			open_list.add(cell);
		}
		//sort open list
		open_list.sort();
		//render
		if(!skip_render)
			map.render();
	}
	this.drawPath=function(cell)
	{
		var offset=map.cell_size/2;
		var next=cell.dad;
		ctx.save();
		while(next)
		{
			ctx.moveTo(cell.x*map.cell_size+offset,cell.y*map.cell_size+offset)
			ctx.lineTo(next.x*map.cell_size+offset,next.y*map.cell_size+offset);
			ctx.stroke();
			cell=next;
			next=cell.dad;
		}
		ctx.restore();
	}
	this.solve=function()
	{
		var last_cell=0x0;
		while(!this.ended)
			last_cell=this.next(true);
		map.render();
		this.drawPath(last_cell);
	}
}

var map=new Map(30,15,50,canvas);
map.fill(map.terrains.ground)
map.rect(map.terrains.wall, 4, 2, 2, 6);
map.rect(map.terrains.water, 8, 0, 4, 15);
map.rect(map.terrains.deep_water, 9, 0, 2, 15);
map.rect(map.terrains.forest, 13, 6, 5, 5);
map.rect(map.terrains.water, 15, 1, 4, 4);
map.rect(map.terrains.deep_water, 16, 2, 2, 2);
map.rect(map.terrains.wall, 19, 3, 1, 6);
map.rect(map.terrains.bridge, 8, 10, 4, 1);
map.origin={x:2,y:2};
map.destiny={x:27,y:4};
map.render();
var pathfinding=new Pathfinding(map);

//Para avanzar un paso pathfinding.next();
//Para resolver directamente pathfinding.solve();

He de decir que he disfrutado mucho escribiendo este pequeño código. Mi parte favorita son las líneas de las 26 a las 31. ¿Todo el mundo las entiende y sabe qué hacen y por qué funcionan? 😉

Conjunto de Mandelbrot

Publicado por LaNsHoR el 11/04/2014 en Matemáticas, Scripting | 0 comentarios

Dejo un pequeña “piece of code” de hace un par de años para generar el conjunto de Mandelbrot en un canvas con Javascript. Quería tener una imagen muy grande del conjunto con tonos azules, así que decidí generarla de la forma más rápida posible: un canvas y unas pocas líneas de código.

Fue una mala idea, descubrí entonces que la mayoría de navegadores soportan como máximo una dimensión en píxeles de 8192×8192 para el canvas; así que la imagen se limitaría como mucho a ese tamaño.

Descargar imagen final en tamaño completo

En cualquier caso… desde aquí podéis ejecutar el script; y el código (hecho ad hoc para generar la imagen y nada más):

var width=7500;
var height=width*0.88;
var canvas=document.getElementById("canvas");
var control=document.getElementById("control");
canvas.width=width;
canvas.height=height;
var context=canvas.getContext("2d");
var minAbsRe=-2.00;
var maxAbsRe=+0.80;
var minAbsIm=-1.25;
var maxAbsIm=+1.25;
var zoom=1;
var y=0;
function draw()
{
   var minRe=minAbsRe*zoom;
   var maxRe=maxAbsRe*zoom;
   var minIm=minAbsIm*zoom;
   var maxIm=maxAbsIm*zoom;
   var reFactor=(maxRe-minRe)/(width-1);
   var imFactor=(maxIm-minIm)/(height-1);
   var maxIterations = 30;
   var c_im=maxIm-y*imFactor;
   for(var x=0;x<width;++x)
   {
      var c_re=minRe+x*reFactor;
      var zRe=c_re, zIm=c_im;
      var isInside=true;
      for(var n=0;n<maxIterations;++n)
      {
         var zRe2=zRe*zRe,zIm2=zIm*zIm;
         if(zRe2+zIm2>4)
         {
            isInside=false;
            if(n<maxIterations/2)
               context.fillStyle="rgb(0,0,"+(n*255/(maxIterations/2))+")";
            else
            {
               var a=Math.round((n-(maxIterations*0.5))*255/(maxIterations/2));
               var b=Math.round(a*Math.pow(n/maxIterations,3));
               context.fillStyle ="rgb("+b+","+a+",255)";
            }
            context.fillRect(x,y,1,1);
            break;
         }
         zIm=2*zRe*zIm+c_im;
         zRe=zRe2-zIm2+c_re;
      }
      if(isInside)
      {
         context.fillStyle="#000";
         context.fillRect(x,y,1,1);
      }
   }
   if(y<height)
   {
      var progress=(y*100/height);
      control.innerHTML=progress.toFixed(2)+"%";
      y++;
      setTimeout(draw,25);
   }
   else
   {
      var img=canvas.toDataURL("image/png");
      control.innerHTML='<img src="'+img+'"/>';
   }
}

Octarino

Publicado por LaNsHoR el 11/04/2014 en Citas | 0 comentarios

Arthur C. Clarke

Atractores, caos, sistemas complejos y mariposas

Publicado por LaNsHoR el 09/04/2014 en Computación Gráfica, Matemáticas | 0 comentarios

Siempre nos sentimos más cómodos con aquello que creemos que conocemos; con aquello que ya sabemos y no puede cambiar. Pero en en realidad, siendo un poco puristas, la estabilidad no existe. Ningún sistema en la naturaleza (sistemas reales, no artefactos matemáticos imaginarios) es estable; en el sentido de que no va a permanecer inalterado para siempre. No existe nada en este universo, que haya detenido su evolución nunca.

En la práctica, cuando hacemos ciencia y estudiamos sistemas “aislados”, rebajamos considerablemente nuestros requisitos de estabilidad; y decimos que un sistema ha alcanzado la estabilidad cuando su evolución cesa durante “un tiempo lo suficientemente largo”.

Sí, es tan poco riguroso como suena…

Pero lo divertido está en la incertidumbre, y una vez perdemos el miedo a lo desconocido podemos empezar a disfrutar de ella. Veamos algunos tipos de sistemas con ejemplos sencillos y clasifiquémoslos:

Sistemas Simples

Un ejemplo de sistema simple es una taza de café caliente suspendida en una atmósfera de aire. Poco a poco la taza irá enfriándose hasta alcanzar la temperatura ambiente del aire (el sistema alcanzará la estabilidad). En sus inicios, el sistema no es estable, pero nos sentimos casi tan cómodos con estos sistemas como con los estables porque es fácil predecir su evolución.

Sistemas Complejos

Un sistema complejo es un sistema cuya evolución es muy difícil de determinar; ya que existen factores no evidentes que afectan de forma dramática a cómo evoluciona el sistema. Un ejemplo es el campo gravitatorio, cuando hay varios cuerpos en juego y en movimiento; es difícil calcular la evolución de las trayectorias.

Para verlo mejor; he escrito un pequeño script para hacer simulaciones (del que hablaremos después). En la primera simulación tendréis 6 puntos negros que representan cuerpos “fijos” que atraen a otro “móvil” cuya trayectoria queda marcada por una estela azul. La simulación es infinita y no se estabiliza nunca (aunque durante un rato el objeto móvil se salga de la pantalla, tarde o temprano volverá).

comenzar simulación

Para empezar la simulación haced clic en “empezar simulación” (podéis reiniciarla cuando queráis). ¿Podéis calcular mentalmente su trayectoria (la evolución del sistema)? Entonces, es un sistema complejo. Otro ejemplo de sistema complejo es el clima de la tierra.

Sistemas Caóticos

Un sistema caótico es un sistema, que además de complejo, cumple la siguiente propiedad fundamental: un mínimo y casi insignificante cambio en las condiciones iniciales hace que el sistema evolucione de forma radicalmente distinta.

Para ilustrarlo vamos a hacer una simulación como la anterior; pero esta vez, habrá tres objetos móviles (uno rojo, uno verde y uno azul). Los tres objetos estarán en la misma posición, pero con una diferencia de 0.001 píxeles. Esta diferencia, provocará que con el tiempo, los tres objetos sigan trayectorias completamente distintas.

comenzar simulación

La vida es un propio ejemplo de sistema caótico. A veces pensamos que ya hemos vivido situaciones similares a las que estamos viviendo en un momento dado; y creemos que la experiencia pasada nos puede servir, pensando que ya sabemos qué va a ocurrir. Pero en realidad, cualquier mínimo detalle puede ser determinante para que la evolución de sucesos sea completamente distinta.

De los sistemas caóticos como este viene “la teoría del caos”; y la famosa metáfora de la mariposa que bate sus alas y cambia radicalmente los acontecimientos futuros en una suerte de efecto dominó cuyas consecuencias se van amplificando. Es una forma de decir; que el más mínimo detalle es crucial para la evolución del sistema.

NOTA: Los sistemas caóticos, a pesar de su nombre, no son azarosos en absoluto; son completamente deterministas.

Atractores

Los atractores, como mención importante (fuera de los propósitos de esta entrada), son sistemas complejos y o caóticos, pero, en los que las trayectorias próximas permanecen siempre próximas, siento permisivos con ciertas perturbaciones en sus condiciones iniciales y evolución.

A todos os sonará el más famoso de todos: el atractor de Lorenz (prometo dedicar una entrada para hablar exclusivamente de atractores ;))

El código

Propongo como ejercicio escribir un sistema de simulación como el que hemos usado en esta entrada. Lo único un poco más complicado (sigue siendo sencillo) es hacer las estelas que se van difumando.

Si queréis la solución directa, mi código, con una inicialización de ejemplo que ejecuta una simulación con 25 atractores y 150 objetos móviles (todos aleatorios) es:

function Attractor(canvas)
{
	//-[utils]---------------- *********************************************
	function randChannel()  {return Math.floor(Math.random()*255)}
	function randPosition() {return [Math.random()*canvas.width,Math.random()*canvas.height]}
	//-[balls]---------------- *********************************************
	function Ball(x, y, mass, rgb)
	{
		//-{init}
		this.x=x || randPosition()[0];
		this.y=y || randPosition()[1];
		this.mass=mass || 4;
		this.vx=0;
		this.vy=0;
		this.radius=this.mass/2;
		if(rgb)
			this.color="rgb("+rgb[0]+","+rgb[1]+","+rgb[2]+")";
		else
			this.color="rgb("+randChannel()+","+randChannel()+","+randChannel()+")";
		balls.push(this);
		//-{methods}
		this.move=function()
		{
			var tmp_vx=0;
			var tmp_vy=0;
			for(var i=0;i<acelerators.length;i++)
			{
				var dx=acelerators[i].x-this.x;
				var dy=acelerators[i].y-this.y;
				var theta=Math.atan2(dy,dx);
				var mod=Math.sqrt(Math.pow(dx,2)+Math.pow(dy,2));
				var force=Math.min(acelerators[i].force/Math.pow(mod,2),3);
				tmp_vx+=force*Math.cos(theta);
				tmp_vy+=force*Math.sin(theta);
			}
			this.vx+=tmp_vx/this.mass;
			this.vy+=tmp_vy/this.mass;
			this.x+=this.vx;
			this.y+=this.vy;
		}
		this.render=function()
		{
			current_ctx.save();
			current_ctx.fillStyle=this.color;
			current_ctx.beginPath();
			current_ctx.arc(this.x, this.y, this.radius, 0, 2*Math.PI, false);
			current_ctx.closePath();
			current_ctx.fill();
			current_ctx.restore();
		}
	}
	//-[acelerator]---------------- *********************************************
	function Accelerator(x, y, force)
	{
		//-{init}
		this.x=x || randPosition()[0];
		this.y=y || randPosition()[1];
		this.force=force || 200;
		this.radius=this.force/50;
		acelerators.push(this);
		//-{methods}
		this.render=function()
		{
			ctx.save();
			ctx.fillStyle="#000";
			ctx.beginPath();
			ctx.arc(this.x, this.y, this.radius, 0, 2*Math.PI, false);
			ctx.closePath();
			ctx.fill();
			ctx.restore();
		}
	}
	//-[attractor]----------- *********************************************
	//-[setup]----------------
	var ctx=canvas.getContext("2d");	//main context
	var balls=[];						//balls array
	var acelerators=[];					//acelerators array
	//-[wake]-----------------
	var wake_resolution=20; //number of canvas for the wake
	var ctx_buffer=[];      //context array for the wake
	var current_ctx=0;		//current context object
	var arrow=0;			//pointer to the current context
	var wake_time=2000/wake_resolution; //5 seconds of wake
	var last_timestamp=0;	//last time of buffer change
	var frames=0;			//frame count
	//-[init]-----------------
	for(var i=0;i<wake_resolution;i++)
	{
		var tmp_canvas=document.createElement("canvas");
		tmp_canvas.width=canvas.width;
		tmp_canvas.height=canvas.height;
		ctx_buffer[i]=tmp_canvas.getContext("2d");
	}
	current_ctx=ctx_buffer[0];
	//-[run]------------------
	this.run=function()
	{
		frames++;
		ctx.clearRect(0,0,canvas.width,canvas.height);
		//chance of change current context
		var now=Date.now();
		if(now-last_timestamp>wake_time)
		{
			last_timestamp=now;
			current_ctx=ctx_buffer[(++arrow%ctx_buffer.length)];
			current_ctx.clearRect(0,0,canvas.width,canvas.height);
		}
		//render balls at current context
		for(var i=0;i<balls.length;i++)
		{
			balls[i].move();
			balls[i].render();
		}
		//composition of the wake at main context
		var step_alpha=1/ctx_buffer.length;
		for(var i=1;i<=ctx_buffer.length;i++)
		{
			var tmp_ctx=ctx_buffer[(arrow+i)%ctx_buffer.length];
			ctx.save();
			ctx.globalAlpha=i*step_alpha;
			ctx.drawImage(tmp_ctx.canvas,0,0);
			ctx.restore();
		}
		//render acelerators at main context
		for(var i=0;i<acelerators.length;i++)
			acelerators[i].render();
	}
	//-[stop]-----------------
	this.stop=function()
	{
		clearInterval(this.id_int); //external setter
	}
	//-[classes]-----------------
	this.Ball=Ball;
	this.Accelerator=Accelerator;
}

//gogogo!
(function gogogo()
{
	var attractor=new Attractor(canvas);
	for(var i=0;i<25;i++)
		new attractor.Accelerator();
	for(var i=0;i<150;i++)
		new attractor.Ball();
	attractor.id_int=setInterval(function(){attractor.run()},60/1000); //run at 60 fps
}());

Más simulaciones

Sistema aleatorio con 10 atractores y 20 objetos móviles:

reiniciar simulación aleatoria

Dedicatoria

Esta entrada está dedicada a Virgy; que me inspiró para escribir el simulador tras una conversación; y que finalmente he aprovechado (al margen de su fin original) para hacer esta entrada 🙂

La visión en los perros

Publicado por LaNsHoR el 08/03/2014 en Computación Gráfica | 1 comentario

Llevo tiempo preguntándome cómo se ve el mundo desde los ojos de Arthur. Algunas personas piensan que los perros ven en blanco y negro, pero lo cierto es que sí distinguen algunos colores. En concreto, perros, lobos, zorros… y la mayoría de los cánidos y mamíferos poseen una forma de visión dicromática llamada deuteranopía; y es también, de hecho, una forma de daltonismo en humanos.

Los colores

Para entender nuestra visión: en la retina humana (y en la de muchos primates) podemos encontrar bastones (células de visión por intensidad) y tres tipos de conos (células responsables de la visión en color); cada tipo de cono especializado en una longitud de onda diferente: “azules” sensibles en un rango de longitudes centradas en el azul (unos 430nm), “verdes” especializados en longitudes de onda similares a la del verde (unos 520nm) y “rojos” para longitudes de onda largas cercanas al rojo (~650nm).

Dado que estas son las longitudes de los colores primarios aditivos (rojo – verde- azul); la composición de la información receptada por cada tipo de cono completa un espectro como el siguiente:

En los animales con deuteranopía los conos responsables de la recepción del verde no están presentes o no son funcionales. La composición de la información receptada presenta en estos casos un espectro como el siguiente:

Niveles de gris

Otra diferencia importante entre la visión humana y la de un perro es la diferencia mínima perceptible entre factores de gris (AR). Para esta medición se suele usar la ley de Weber-Fechner; una regla psicofísica que establece una relación cuantitativa entre la magnitud de un estímulo físico y cómo éste es percibido. El resultado de la fracción de Webber para humanos se estima en 0.11, y para perros en 0.22; esto significa que los perros son sólo capaces de captar la mitad de niveles de grises que nosotros.

Por ejemplo, los perros verían los siguientes cuadrados del mismo color:

Si tú ves el mismo color en ambos cuadrados, puede deberse a que tu monitor sea de gama baja y no sea capaz de mostrar correctamente los colores (o que esté mal configurado en parámetros de brillo, contraste y temperatura). Descartamos la opción de que seas un perro, claro.

Agudeza visual

Dicho en pocas (pero muy imprecisas) palabras; la agudeza visual es la resolución espacial del sistema visual. Al tratarse de un término de resolución es fácil imaginar que está directamente relacionado con la densidad de conos y bastones de la retina. Esta densidad varía según la zona; así, perdemos resolución en los límites de nuestro campo visual (donde apenas podemos percibir objetos) y alcanzamos el máximo en el punto donde centramos la vista.

El máximo de agudeza visual para humanos está entre 50 y 60 CPD. En los perros se sitúa entre 6.5-9 y 11.6 CPD.

Simular cómo es la visión con una agudeza visual diferente a la nuestra es complicado; intervienen muchos factores y es alterada circunstancialmente por el entorno. Por ejemplo el desenfoque por profundidad de campo se dispara (no podemos simularlo en una imagen 2D) al enfocar; y la cantidad de luz recibida también afecta de forma virtual; ya que los perros tienen mayor densidad de bastones que los humanos, pupilas más grandes y un tapetum lucidum refractivo; así en la oscuridad la agudeza visual de los perros acabaría superando a la del humano.

Aunque esta aproximación sea muy imprecisa; podemos ilustrar la pérdida de resolución con la siguiente figura; asumiendo un factor de /4 para los perros.

AV /1

AV /4

Al lío. Dedos al código.

Con todo este resumen; la idea es escribir una pequeña función javascript que dada una imagen de ejemplo la transforme y haga una aproximación acertada de cómo la percibiría un perro.

La función tiene 3 tareas independiente a realizar:

1) Simulación de deuterapía: No es tan sencillo como pueda parecer, ya que los niveles de luz y ponderaciones entre colores cambian gradualmente según la curva de sensibilidad de los conos que sí están presentes (rojo-azul). En este paper [1] encontramos los factores medidos experimentalmente -para humanos; aunque la diferencia con perros es mínima (comparamos con [2])- que necesitaremos para la conversión.

2) Discretizamos algunos niveles de luz. No vamos a implementar todas las curvas; sólo una aproximación. Algo de información adicional en [3]. Hacemos una reducción de la intensidad a niveles pares.

3) Desenfoque gausiano a la imagen. Para hacerlo correctamente el desenfoque variaría su grado arbitrariamente según la zona; y para ello necesitaríamos una imagen tridimensional, información sobre la exposición y el punto de enfoque marcado. Como no tenemos nada de eso, hacemos un desenfoque suave y global que simule el máximo grado de agudeza visual en todos los puntos. El desenfoque podemos hacerlo eficientemente (usando la GPU) mediante un filtro en CSS3 (fuera del código javascript).

function DogVision() //v0.1 - LaNsHoR @ 2014
{
	//===================================================
	//Factors
	var gamma=1.0 /* normal value: 1.8;
                         -0.8 correction for dogs */
	var by=127, k=[9591, 23173, -730];
	for(var luts={}, invluts={}, i=0; i<256; i++)
	{
	    luts[i]=0.992052*Math.pow(i/255, gamma)+0.003974;
	    invluts[i]=255*Math.pow(i/255, 1/1.8);
	}
	//===================================================
	//Functions
	//-- RGB normalization
	function normalize(value)
                     {return value<0?0:value>255?255:value;}
	//-- Dog light reduction
	function even(value) {return value%2?value-1:value;}
	//===================================================
	this.dogPixel=function(r,g,b)
	{
	    var r_lin=luts[r], g_lin=luts[g], b_lin=luts[b];
	    var r_blind=((k[0]*r_lin)+(k[1]*g_lin))/by;
	    var b_blind=((k[2]*r_lin)-(k[2]*g_lin)+32768*b_lin)/by;
	    r_blind=normalize(r_blind);
        b_blind=normalize(b_blind);
	    var red=invluts[Math.round(r_blind)];
            var blue=blue=invluts[Math.round(b_blind)];
	    return [even(red), even(red), even(blue)];
	}
}

Y ya está! Podemos empezar a jugar con los resultados 🙂

Ejemplos

Conclusión de andar por casa

Por todo lo dicho y visto; los perros en ambientes de luz diurna tienen una visión mucho más precaria que la humana. Sin embargo, con condiciones de baja luz su percepción de siluetas es mucho mejor que la nuestra (fijaos en los ejemplos). Además, su mayor número de bastones les hacen mejores detectando pequeños movimientos a grandes distancias (algo que no podemos percibir en imágenes estáticas).

No está nada mal. Después de todo; su sentido principal es el olfato (la mayoría de neuronas de su corteza cerebral están dedicadas a este sentido; la mayoría de las nuestras, a la visión). Aún con una visión mediocre, si sumamos sus excelentes olfato y oído su nivel de percepción sensorial global es superior al nuestro. Y desde luego, perfectamente adaptado a lo que necesitan.

Dedicatoria
Esta entrada y el código fuente de la función que hemos escrito están dedicados a Quarkyta… una de las preciosas perritas de Virgy, que nos dejó hace unos días 🙁

Referencias

[1] Digital Video Colourmaps for Checking the Legibility of Displays by Dichromats

[2] Color Vision in the dog

[3] The spectral luminosity curves for a dichroma tic eye and a normal eye

Los verdaderos programadores

Publicado por LaNsHoR el 23/02/2014 en Miscelánea | 0 comentarios