sábado, 27 de octubre de 2012

Algoritmo Marching Squares

En el post anterior, comenté que no hay solamente una forma de representar voxels en pantalla. Mostré las formas mas simples y mencioné el algoritmo Marching Cube como una posibilidad para suavizar el renderizado de voxels.

En este post, en lugar de mostrar el algoritmo Marching Cubes voy a mostrar su versión 2D: Marching Squares. El algoritmo Marching Squares permite hacer una analogía directa con Marching Cubes y puede ser comprendido mas fácilmente.

La idea entonces, es que tenemos un campo de voxels 2D. Una posible representación de ese campo de voxels es un simple array bidimensional de números enteros:

  v = [[0,     0,   0, 0],
       [30,  100,  30, 0],
       [100, 100, 100, 0],
       [ 30, 100,  30, 0]];

Una forma de representar esto sería utilizando una escala de grises con 0 = blanco y 100 = negro. Pero para  evitar un resultado pixelado sería necesario un array de mayor dimensión.

Si lo que buscamos es usar un array de tamaño reducido para representar los voxels, pero a su vez un resultado no tan pixelado, podemos generar una "curva de nivel". Esto es, un contorno continuo de este campo usando segmentos de lineas. Es ahi donde entra Marching Squares.

Algoritmo Marching Squares

Este algoritmo permite obtener una "curva de nivel" de una función discreta (en este caso, los voxels). Los pasos a seguir son:
  1. Convertir los voxels a un campo de valores 0 o 1 según un isovalor predeterminado.
  2. Seleccionar un sub cuadrado 2x2 del campo de valores 0/1 y determinar un caso utilizando una tabla de casos (ver table mas adelante).
  3. Utilizar los valores del campo de voxels original junto con el caso determinado en el paso 2 para obtener una linea interpolada.
  4. Repetir desde el paso 2 para cada subcuadrado 2x2 del array original.
Utilizando el ejemplo anterior sería:

1. Convertir a campo de valores:

En este paso elijo un isovalor de 50 (punto medio entre 0 y 100) y creo un nuevo array que tiene 0 cuando el valor v[i][j] es menor o igual a 50 y 1 cuando v[i][j] es mayor a 50.

  v_iso = [[0, 0, 0, 0],
           [0, 1, 0, 0],
           [1, 1, 1, 0],
           [0, 1, 0, 0]];

2. Determinar casos:

Viendo cada subarray de 2x2 y comparando con la siguiente tabla de casos, determino el caso.

Casos de marching squares
Tabla de casos. Un circulo negro corresponde a un voxel con valor superior al isovalor, uno blanco corresponde a un valor inferior. Los extremos de la linea resultante tienen que ser interpolados utilizando los valores de los voxels
En nuestro ejemplo, volviendo a v_iso, el primer subarray de 2x2 es
  [[0, 0], 
   [0, 1]

Comparando con la imagen, esto corresponde al caso 2. Ese caso es una linea diagonal de abajo hacia la derecha.

3. Interpolar usando voxels:

Si miramos en la tabla, cada extremo de las lineas celestes tiene una flecha que indica que ese extremo deberá ser ubicado teniendo en cuenta los valores de los extremos del lado. Tomemos el ejemplo encontrado en el paso anterior. Los valores de cada voxel eran 0, 0, 30 y 100, que resultaron en un Caso 2:

En este punto, hay que tener en cuenta que lo que estamos buscando es una linea correspondiente a un valor de 50. Si la distancia vertical y horizontal entre voxels es L y los valores en la posición de cada voxel son los valores dados por el voxel, entonces podemos interpolar las posiciones de cada extremo de la linea usando una proporción.
(100-30)/L = (50-30)/x
que implica que x es L*(50-30)/(100-30) = 0.28L

De la misma manera, para obtener la coordenada Y de la posición del otro extremo, podemos usar una proporción similar. En este caso, dado que los extremos corresponden a 0 y a 100, el valor de y es en el centro exacto de los voxels, o sea y=L*(50-0)/(100-0) = 0.5L

4. Repetir cada paso:

Si repetimos los pasos anteriores para cada subarray de 2x2 obtenemos el siguiente gráfico:
En el dibujo ya están las posiciones interpoladas de cada linea y un sombreado marcando el interior del polígono resultante. El interior del polígono se puede determinar fácilmente modificando la tabla de casos para mostrar cual es el interior en cada caso.

Ejemplo interactivo

La mejor forma de entender el algoritmo es utilizando un ejemplo interactivo y viendo el código. Hice un pequeño widget para poder experimentar. El ejemplo está realizado completamente en HTML5 usando webgl y javascript, por lo que es necesario un navegador moderno. El código fuente está disponible en google code.

Para usar el ejemplo solamente hay que asignar valores en la tabla. Se puede desactivar y activar el renderizado de voxels y de la isolinea.


En el  próximo artículo voy a mostrar cómo se generaliza esta idea a un caso 3D con el algoritmo Marching Cubes.

miércoles, 17 de octubre de 2012

Introducción a Voxels

Una forma utilizada frecuentemente para representar objetos tridimensionales es mediante triángulos en un espacio tridimensional. Esto es, conjuntos de vértices que forman triángulos en el espacio. Esta es la forma en que las placas de video actuales reciben los datos antes de representarlos en pantalla y por lo tanto es la forma en que se almacenan los polígonos que se utilizan en aplicaciones gráficas.


Un ortoedro representado mediante triángulos. Representación gráfica y formulación matemática.
Una forma alternativa de almacenar información tridimensional es el uso de voxels. Así como un pixel es un elemento 2D que indica el estado (color) de un punto en una pantalla, un voxel es un elemento 3D que asocia un valor (o valores) a cada posición de un espacio tridimensional. El voxel puede contener información de "cantidad" de materia (0 a 1 con 0 = vacío y 1 = lleno) así como información mas compleja como tipo de material, textura, etc.
Representación gráfica y matemática de los voxels. Solo se muestran 4 voxels "vacíos" pero se supone que hay voxels vacios en todas las posiciones en que no hay voxels llenos.
En la imagen se ve una representación de la figura de antes, pero ahora usando voxels. Así como antes se almacenaban vértices y uniones entre estos para formar triángulos, en la representación de voxels se asignan valores a los distintos puntos del espacio tridimensional. En la representación anterior se almacenaba información de la superficie de la figura, en la representación actual se almacena información del volumen.

Esta representación es solo una forma de almacenar información. La ventaja de esta forma de representar la información es que permite editar el objeto representado simplemente agregando o removiendo voxels. 

En la figura de arriba se puede ver cada voxel como un cubo. Esta representación asume que un voxel solo puede tener el valor 0 o 1 (lleno/vacío), pero en general podríamos asignar cualquier valor entre 0 y 1 a cada voxel. Por otro lado, está el problema de convertir los voxels a un formato que pueda ser manejado por una placa de video (o sea, una serie de triángulos).

Formas de Representación


Izquierda: alta densidad de voxels representados mediante cubos de colores.
Derecha: baja densidad de voxels con la misma representación. (fuente: Google Images)
Si uno se limita a reemplazar puntos por cubos de color (así como en una imagen 2D se reemplazan puntos por rectángulos), el resultado es una imagen pixelada. Al igual que en una imagen 2D (pantalla o impresión) la calidad de la imagen depende de la densidad de pixels, la calidad de la representación 3D dependerá de la densidad de voxels. Es posible aumentar la resolución de voxels tanto como el hardware lo permita y obtener objetos fotorealistas. Esta forma de representar voxels no es eficiente para renderizado en tiempo real (por ejemplo un videojuego) si lo que se busca es fotorealismo ya que una alta densidad de voxels se traduce en una alta densidad de vértices incluso si evita renderizar las caras de los voxels que no son visibles por la cámara.

Una alternativa a lo anterior, para bajas densidades de voxels, es utilizar cubos con textura para reemplazar cada voxel. Esto permite darle una ambientación retro a un juego 3D, ver por ejemplo Minecraft.
Mincraft renderiza voxels usando cubos texturados.
Si lo que se busca es evitar formas "pixeladas" pero a la vez evitar usar altas densidades de voxels, hay que recurrir a algoritmos que utilicen el estado del voxel y el estado de sus vecinos para generar una superficie suave.

En el próximo post voy a explicar el algoritmo de Marching Cubes usando un ejemplo 2D para simplificar la explicación. 

jueves, 1 de abril de 2010

Se acerca el momento de desempolvar la Wii

viernes, 5 de marzo de 2010

Probando Unity3D

Estuve probando Unity3D como una forma de hacer juegos web. En el espíritu de "dejar todo asentado", muestro y explico los resultados.

Después de implementar el tutorial de plataformas, me largué a hacer un pequeño asset.

El desafío:
  • Hacerlo con scripts en C# (lenguaje que desconozco)
  • Interactuar con algún servicio web, usando JSON como tecnología
El resultado:

Lector de twitter en Unity3D

La primera impresión es que hacer scripts es extremadamente intuitivo. Si a alguien le interesa le puedo exportar el asset completo para que lo examinen en detalle.

Para comunicarme con Twitter, usé JSON. Existen muchos parsers JSON para C#, pero el que yo usé es "LitJson". Usarlo es tan simple como hacer un drag and drop de todos los archivos .cs de la distribución al árbol del proyecto Unity.

Paso a explicar el script:

using UnityEngine;
using System.Collections;
using LitJson;

public class TwitterPlatform : MonoBehaviour {
 public Camera camera;
 public Transform player;
 public string queryString="pozzoeRand";
 private Transform messageBoard;
 private ParticleEmitter emitter;
 private string twitterText;
 private MeshRenderer meshRender;
 private bool active=false;

No hay mucho de decir. A diferencia de Unity+Javascript, todo nuestro código debe ser implementado en una clase hija de MonoBehaviour. El nombre de la clase debe ser igual al archivo donde se encuentra el script.

Gracias a la magia de Unity, todas las variables públicas de la clase, son puestas en el object Inspector de Unity y pueden ser configuradas como parámetros del script. Instalar un script en un objeto implica haber instanciado un objeto de la clase del script. Y cada objeto tiene su propia variable. Eso hace que uno pueda tener un "query string" distinto en cada lector Twitter.

La variables "camera" y "player" deben ser configuradas al momento de instanciar un objeto que hace uso de este script. La forma de configurarlas es simplemente arrastrar una cámara y un jugador al slot correspondiente en el inspector de objetos. La cámara y el jugador se usan para permitirle al script acomodar el mensaje de texto de modo tal que sea siempre visible por el jugador.

El flag active indica si la plataforma está activada. El string twitterText es el texto a mostrar en el cartel de texto.

void Start () {
  this.emitter=this.transform.Find("CommunicationEffect")
    .GetComponent();
  this.messageBoard=this.transform.Find("TextRenderer");
  this.meshRender=this.messageBoard.GetComponent();
  this.meshRender.enabled=true;
  this.setDefaultText();
 }

La función Start es llamada automáticamente cuando se inicia la escena (el juego en este caso). En este script ajusto algunas variables privadas. Los detalles son mas evidentes al ver la estructura del objeto en si. El objeto donde está ubicado el script, tiene objetos hijos que se pueden acceder con la función Find. El objeto CommunicationEffect es un "efecto especial" que utiliza partículas para mostrar al usuario que está "pasando algo".

Por otro lado, el objeto "TextRenderer" es un cartel de texto que va a ser usado para mostrar el resultado de los queries al Api Twitter y también para mostrar el querystring antes que el jugador haya activado la plataforma.

void Update () {
  this.meshRender.transform.forward = this.camera.transform.forward;
  if (this.active==false)
   return;

  this.meshRender.transform.position = 
  this.player.transform.position 
  + this.camera.transform.forward*20
  + this.camera.transform.up*8;
 }

La función update es llamada automáticamente en cada frame del juego. Lo primero que hace es asegurarse que el cartel está paralelo al plano de la cámara, para que sea visto claramente.

Después, si la plataforma está desactivada (el jugador no ha pisado la plataforma), termina.

Si la plataforma está activada, la función update se asegura de que el cartel de texto esté puesto en un lugar de la plataforma que permita al jugador leer el texto. Las variables forward y up son vectores en las coordenadas locales del objeto (en este caso la cámara).

void OnTriggerEnter(){
  this.emitter.Emit();
  StartCoroutine(this.readTwitter());
  this.messageBoard.GetComponent().transform.position=this.player.transform.position+this.camera.transform.forward*20+this.camera.transform.up*8;
  this.active=true;
 }

La función OnTriggerEnter es llamada cuando el engine detecta una colisión con el mesh del objeto en el que se encuentra el script. Mas adelante muestro dos funciones relacionadas.

La función Emit() es llamada sobre el emisor de partículas. Hace que se emita un chorro de partículas. Luego, se inicia una corrutina que es la que se encarga de interactuar con twitter. Una corrutina es una función que puede interrumpir su ejecución para luego resumir en el mismo punto. La función StartCoroutine, usada de esta forma, ejecuta la corrutina readTwitter en paralelo a la función update, y continua ejecutando la funcion update.

IEnumerator readTwitter()
 {
  while (true) {
   string url="http://search.twitter.com/search.json?q="+this.queryString;
   this.twitterText="Loading";
   WWW tweets = new WWW (url); 
   
   int retries=0;
   bool  reload=false;
   while (!tweets.isDone){
    if (retries>20) {
     /*Will retry after trying 0.2*20 seconds*/
     this.twitterText="Loading";
     retries=0;
     reload=true;
     break;
    }
    this.twitterText+=".";
    yield return new WaitForSeconds(0.2f);
    retries++;
   }
   if (reload)
    continue;

Esta función es la que lee de Twitter. Recordemos que se está ejecutando en paralelo con el resto de las funciones. Y en particular, esta corrutina se está ejecutando en un loop infinito.
Lo que se hace es crear una petición al servidor de Twitter. Y después esperar hasta que Twitter responda. El problema es que no sabemos cuanto se puede demorar Twitter (con sus magnificos servers) en responder. Y aca es cuando entra la magia de las corrutinas. Cada "yield" es como un return, que devuelve la ejecución para que el engine sigua funcionando, con la particularidad de que al llamar la corrutina en el próximo frame la ejecución se continua en el yield, como si nunca se hubiera abandonado.
En particular se puede hacer otras cosas como yield return new WaitForSeconds(0.2f), hace que unity suspenda la ejecución de la corrutina y espere 0.2 segundos antes de continuar. De esta manera, en cada paso se le pregunta al objeto "tweet" si ya terminó de cargar todo lo que twitter le devolvió. Si no, se aumenta un contador y se espera 0.2 segundos antes de volver a preguntar. Si el server tarda mas de 4 segundos en responder, se vuelve a empezar desde el principio, o sea, se envía otro query (al menos es lo que teóricamente debería pasar, no lo probé, si alguien piensa lo contrario que hable).

En caso contrario, la corrutina continua su ejecución.

JsonData queryResult=JsonMapper.ToObject(tweets.data);
   JsonData tweetList=queryResult["results"];
   for (int i=0;i<tweetList.Count; i++)
   {
    this.messageReceived();
    this.twitterText=wrap((string)tweetList[i]["text"]);
    yield return new WaitForSeconds(4f);

   }

  } 
 }
Esta parte de la corrutina usa el parser de JSON para leer uno a uno los tweets. No hay mucho que sea especifico de Unity. Solo que nuevamente se espera 4 segundos entre tweet y tweet, para darle tiempo al jugador de que lea cada uno.

Este lector de twitter es absolutamente precario e ineficiente. Lo ideal sería que se muestren los tweets de mas viejo a mas nuevo y luego se actualizen los nuevos tweets a medida que la gente los va publicando. Todo eso es posible, pero no tiene sentido perder mas tiempo en este script que es solo de prueba.

La función MessageReceived simplemente activa el efecto del emisor de partículas. Se puede extender para que también reproduzca un sonido, por ejemplo.

void OnTriggerStay() {
  this.messageBoard.GetComponent().text=this.twitterText;
  
 }
 void OnTriggerExit(){
  StopAllCoroutines();
  this.active=false;
  this.setDefaultText();
 }
La función OnTriggerStay es ejecutada una y otra vez mientras el jugador está en contacto con la plataforma. Lo único que hace es mantener actualizado el texto de la plataforma. Tranquilamente podría haberse hecho en la función Update, luego de comprobar que la plataforma se encuentra activa.

La función OnTriggerExit es ejecutada automáticamente cuando se abandona la plataforma. En este caso, se detiene la ejecución de todas las corrutinas de este objeto y luego se vuelve a mostrar el texto con el querystring ubicado en el centro de la plataforma.

void setDefaultText()
 {
  this.meshRender.transform.position=this.transform.position+this.meshRender.transform.up*1;
  this.messageBoard.GetComponent().text=this.queryString;
 }
 void messageReceived(){
  this.emitter.Emit();
 }
 string wrap(string text)
 {
  string newText="";
  text=text.PadRight(140);
  for (int i=0; i<text.Length-28; i+=28)
  {
   newText+= text.Substring(i, 28)+"\n";
  }
  return newText;
 }

Estas son funciones de ayuda. La única que no mencioné es wrap, que simplemente distribuye el mensaje en varias lineas.

Este script es incompleto. Sería adecuado considerar errores como que twitter no devuelva tweets, y probar algunos detalles del funcionamiento.

Pero esto no es nada mas que un proyecto descartable para probar algunas de las características de Unity.

La idea inicial era implementar el automata celular mostrado anteriormente en Unity. Pero no estoy seguro de que sea lo mejor la performance de los scripts para ese tipo usos. Lo ideal sería extender la funcionalidad de Unity usando C++, pero esa es una característica disponible solamente en la version Pro (i.e. paga).

jueves, 11 de febrero de 2010

Automatas Celulares para simulación de explosiones en juegos

Ayer me puse a implementar un Autómata Celular. El objetivo final es simular una explosión en tiempo real. Voy a mostrar unos resultados preliminares que obtuve con Python, pero primero explico la idea.

En general, simular fenómenos físicos como explosiones, fluidos y fuego, en forma realista es demasiado costoso numéricamente como para que se pueda hacer en tiempo real en un videojuego. Sin embargo, hay una técnica que permite obtener aproximaciones visualmente plausibles utilizando los llamados Autómatas Celulares (AC).

Autómatas Celulares

Un Autómata Celular se puede pensar como una grilla cuyas celdas tienen asociado uno o varios valores. Cada celda tiene vecinos, generalmente 4. Al principio, se asignan valores iniciales, y luego se va haciendo evolucionar el AC siguiendo una regla matemática predefinida. Con este esquema general se pueden simular muchos fenómenos biológicos y físicos interesantes. Ver por ejemplo una implementación en Flash

Este concepto se puede generalizar mediante grafos dinámicos. Un grafo es en conjunto de Vértices, unidos mediante conexiones llamadas Aristas. Tanto los Vértices como las Aristas pueden tener propiedades asignadas.

 Ejemplo de grafo: mis contactos de Facebook. Cada Vértice (círculos) es un amigo. Cada Arista (lineas) indica que mis contactos se tienen en sus respectivas listas de contactos. También hay propiedades asociadas: cada Arista tiene un tamaño dado por la actividad del contacto, una foto y un color que indica que el contacto pertenece a un "cluster". Los lados tienen un numero relacionado que indica la cantidad de fotos en la que ambos aparecen juntos.

Usando ese concepto general, se puede generalizar un Autómata Celular. El ejemplo básico de una grilla 2D, se traslada a un grafo en que cada Vértice tiene una posición (lo que originalmente era una coordenada en la grilla) y cuatro Aristas que conectan al Vértice con sus vecinos.


Esquema básico de un grafo que reemplaza a una grilla. Cada vértice de las paredes está conectado con un vértice de la pared opuesta, para crear un "mundo infinito". Todo lo que "sale" por la derecha "entra" por la izquierda.

Este esquema es mas general en varios sentidos. Primero, permite desacoplar fácilmente el espacio "real" de nuestro Autómata Celular, de esa forma ahora cada nodo del grafo puede estar en posiciones arbitrarias del espacio y, en particular, ubicados en forma no uniforme. Se puede entonces simular con mas detalle la física en algunas partes que en otras. Solamente es cuestión de ser cuidadoso a la hora de crear nuestro algoritmo. Otra virtud que tiene este esquema es que se pueden generar obstrucciones en el grafo para simular obstrucciones reales. Por ejemplo
Simular obstrucciones es solo cuestión de romper Aristas o Vértices. La imagen muestra cómo se puede relacionar un grafo con un mapa de nuestro juego. En esquemas mas complicados se pueden mantener todos los Vértices y Aristas y asignar pesos a las Aristas. De esta forma se pueden simular distintos tipos de "rigidez" o incluso destrucción de paredes.

Simulando explosiones

En este post explico como usar este esquema para simular explosiones plausibles en un juego, con poco costo numérico. El primer código que uso es python puro, con fines demostrativos. Incluso con la lentitud de implementar un algoritmo que recorre nodos en python, es posible ejecutar en tiempo real una grilla de 30x30 que ya presenta resultados interesantes.
Para simular una explosión se necesita un grafo que tenga definida una presión en cada Vértice. En cada paso de tiempo, se mira Vértice por Vértice y se compara la presión del Vértice con la presión de sus vecinos. Luego se calcula un flujo de "aire" entre el Vértice y el vecino y se lo utiliza para modificar sus presiones.
El esquema es básico e intuitivo: El nodo que tiene mas presión le entrega un poco a cada uno de los vecinos que tienen menos. Y así, paso por paso, se genera una frente de presión.

Voy a mostrar los resultados primero, y dejar el código comentado al final para quien quiera leerlo.

Explosión al lado de un obstáculo pequeño. Los tiempos son t=1, 4, 10, 20, 40, 80 y 200.

Explosión en una "puerta". La linea marrón es una pared. La simulación es para tiempos t=1, 4, 8, 20, 100 y 200.


Trasladando los efectos de la explosión al juego

Supongamos que el objeto que nos interesa se encuentra cerca de la explosión. Podemos calcular el vector de flujo sumando los vectores de flujo entre un Vértice y sus vecinos. En el ejemplo de la imagen siguiente, el vector de flujo sobre el nodo en que se encuentra el personaje tiene dirección sur oeste. Ese flujo, multiplicado por algún valor que represente la sección de área del personaje, nos indica una fuerza que actúa sobre el personaje.

Es interesante notar que en una explosión, todo sucede muy rápido en los primeros instantes de tiempo. En un juego uno podría simular decenas de pasos de un CA por cada frame del juego y utilizar un promedio en el tiempo del vector de flujo. Este promedio es el impulso a transferir a los objetos del juego en cada frame. De esta forma se puede simular el efecto medio de la onda expansiva en los jugadores, objetos ubicados en el mapa y en el mapa mismo.

También se puede sumar las magnitudes de flujo, para simular efectos como sordera momentanea, ruptura de vidrios, o daño general.

 Cómo trasladar el efecto de la onda expansiva al personaje: Las flechas azules son los vectores de flujo entre el nodo del personaje y sus vecinos. La flecha roja es la suma de los vectores azules, que multiplicadas por el cross-section del personaje dan la fuerza que actúa sobre el personaje debido a la explosión. Promediando esta fuerza durante varios pasos del AC se obtiene el impulso sobre el personaje.
Código Python

Este es el código de los dos ejemplos mostrados. El próximo paso es convertir el loop principal a código C y exponer funciones para calcular los impulsos transmitidos a objetos del mapa.



def iterate_fl(N=30, steps=10):
    '''Automata Celular simple para calcular una explosión.
    Implementación de algoritmo de Tom Forsyth.
    Mas detalles:
    http://home.comcast.net/~tom_forsyth/papers/cellular_automata_for_physical_modelling.html'''

    from itertools import product, combinations
    def clamp(value, max, min):
        '''
        Función clamp, devuelve value si value está entre min y max, devuelve min o max si no.
        '''
        if value<min:
            return min
        if value>max:
            return max
        return value
   
    class Node():
        '''
        Decidí usar una implementación python pura para las pruebas preliminares.
        Este modelo permite CA en 3D y simular paredes u objetos inmoviles mediante desconexiones de nodos.
        '''
        pressure=0.0
        new_pressure=0.0
        t=0
       
        def __init__(self, position):
            self.position=position
            '''Los grafos tienen un conjunto de vecinos.'''
            self.neighbours=set()
           
        def __repr__(self):
            return 'node pressure: %s'%self.pressure
   
   
    '''Mantengo un diccionario posicion->nodo para poder acceder los nodos facilmente'''
    nodes=dict([(position,Node(position)) for position in product(range(N),range(N))])
   
    '''Cada nodo representa una celda en un espacio 2D, cuyo vecino es el vecino físico'''
    for node in nodes.values():
        '''En este ejemplo muestro dos tipos de condiciones de contorno en un grafo:
        paredes rígidas y condiciones periodicas'''
        if node.position[0]+1<N-1:
            '''Hay paredes rigidas a la derecha del mapa.'''
            nodes[node.position].neighbours.add(nodes[(node.position[0]+1, node.position[1])])
        if node.position[0]-1>0:
            '''Hay paredes rígidas a la izquierda del mapa'''
            nodes[node.position].neighbours.add(nodes[(node.position[0]-1, node.position[1])])

        '''La funcion mod (%) me asegura que la parte superior e inferior del mapa están
        conectadas. Lo que sale por arriba, aparece por abajo.
        '''
        nodes[node.position].neighbours.add(nodes[(node.position[0],(node.position[1]+1)%N)])
        nodes[node.position].neighbours.add(nodes[(node.position[0],(node.position[1]-1)%N)])
   
    '''Crea pared, removiendo nodos del grafo. Se pueden hacer paredes removiendo solamente conexiones
    Tipos de pared:'''
    wall=product((10,),range(0,15)+range(17,N)) #pared que cruza el mapa en x=10, con un agujero
    #wall=product((10,),range(14,17)) #pared de tamaño limitado en x=10
    for edg_pos in wall:
        node=nodes[edg_pos]
        for neigh in node.neighbours:
            neigh.neighbours.remove(node)
        del nodes[edg_pos]
   
    '''La explosión propiamente dicha.'''
    #explosion=product(range(4,10),(5,15)) # Un rectangulo
    explosion=((9,15),) #Solo un punto
    for node in explosion:
        nodes[node].pressure=300.0 #La explosion son puntos de alta presion
        nodes[node].new_pressure=300.0 #Este es un detalle del algoritmo
   
       
    '''Ejecutar CA'''   
    i=0
    while i<steps:
        i=i+1
        '''Algoritmo CA para explosiones'''
        for node in nodes.values():
            '''
            Recorremos todo el grafo
            '''
            if node.t!=i:
                '''Detalle de implementación: iteramos por todo el grafo aplicando las reglas del CA,
                los calculos se realizan con el estado actual del grafo y se almacenan los resultados en
                new_pressure, en el siguiente paso de tiempo, se actualizan los valores de la presion usando
                los valores calculados en el paso anterior.'''
                node.t=i
                node.pressure=node.new_pressure
               
           
            for neight in node.neighbours:
                '''Para cada nodo, se miran los vecinos. Este ejemplo es 2D, pero se puede hacer
                3D. En 2D tenemos 4 vecinos por cada posicion del espacio, pero puede haber menos
                vecinos si hay una obstrucción.'''
                if neight.t!= i:
                    '''Nos aseguramos de estar usando los valores de presion
                    calculados en el paso anterior'''
                    neight.t=i
                    neight.pressure=neight.new_pressure
                   
                '''Se calcula la dif. de presion entre el nodo actual y su vecino'''
                dpres=node.pressure-neight.pressure
               
                '''Calculamos el flujo como una fracción de la diferencia de presion.
                0.12 es un numero magico que indica la fluidez del medio. Un valor muy chico
                hace que la presion se propague mas lentamente.
                Usamos la funcion clamp para evitar valores negativos en el nodo.
                Se hace que el flujo no produsca una presión negativa'''
                flow=clamp(0.12*dpres, node.pressure/4.0, -neight.pressure/4.0)
               
                #Actualizamos la presion (usando new_pressure en lugar de pressure) substrayendo
                #presion del nodo actual y agregandola a su vecino. Un flujo negativo implica
                #que la presion del nodo actual aumenta y la del vecino disminuye.
                node.new_pressure -= flow
               
                neight.new_pressure += flow
       
    return nodes

lunes, 1 de febrero de 2010

Instalando Django a la par de un sitio PHP en Apache2 Ubuntu

Estoy comenzando a portear el sitio www.cruzandoelsuquia.com.ar, hecho en Joomla, a Django. Para eso necesito instalar Django en mi server de desarrollo (Una instalación básica de Ubuntu 9.10).

El objetivo es mantener la instalación actual del sitio Joomla, http:// localhost:80/ , y agregar una instalación de Django en el puerto 8000.

Los siguientes pasos son triviales, pero los dejo asentados para cualquiera que le pueda interesar.

Paso 1 - Instalar los paquetes
Instalar los paquetes de django, python para apache2 y los paquetes para acceder a mysql:

sudo apt get install libapache2-mod-python python-django python-mysqldb

Paso 2 - La configuración de Apache2
Suponiendo que el sitio de django se encuentra en la carpeta /home/usuario/django/sitio, debemos agregar el siguiente archivo:


# /etc/apache2/sites-available/django
 MaxRequestsPerChild 1
<VirtualHost *:8000>
    DocumentRoot /home/guillermo/django/cruzandoelsuquiaDJ/
  
    <Location "/">
        SetHandler python-program
        PythonHandler django.core.handlers.modpython
        SetEnv DJANGO_SETTINGS_MODULE cruzandoelsuquiaDJ.settings
        PythonDebug On
    PythonPath "['/home/guillermo/django'] + sys.path"
    </Location>
    <Location "/media">
        SetHandler None
    </Location>
    <Location "/feincms_media">
        SetHandler None
    </Location>
    <LocationMatch "\.(jpg|gif|png)$">
        SetHandler None
    </LocationMatch>

</VirtualHost>

Luego, para activar este host virtual, es necesario agregar el sitio a la lista de sitios activados:

cd /etc/apache2/sites-enabled/
ln -s ../sites-available/django 001-django

En mi caso particular, tengo el sitio predeterminado 000-default, que es mi instalación de Joomla en el pueto standard 80.

Paso 3 - Activar los puertos

Agregar lo marcado en rojo en el archivo /etc/apache2/ports.conf

# /etc/apache2/ports.conf

...

  NameVirtualHost *:80
  Listen 80

  NameVirtualHost *:8000
  Listen 8000
...


Paso 4 - Reiniciar Apache

cd /etc/init.d
sudo ./apache2 restart

Paso 5 - Servir los media del admin de django a travez de Apache

Hay varias opciones, una es linkear la carpeta "media" de la instalacion de django, para tener los css e imagenes del backend:

cd /home/usuario/sitio
ln -s /var/lib/python-support/python2.6/django/contrib/admin/media media

Esto es una solución provisoria, la solución final es usar la carpeta admin_media, previamente configurada en settings.py.

Espero que esto le sirva a alguien. A mi me hubiera servido.

miércoles, 20 de enero de 2010

Creando un directorio joomla en un par de semanas

A veces uno comienza un proyecto que no es necesariamente divertido, o intelectualmente recompensante, sino que es necesario realizar por razones prácticas.

Tal es el caso de un proyecto al que me dediqué las ultimas semanas. La idea es simple y ya recorrida: un directorio de locales comerciales (si, ya se, soy un SEO whore). La diferencia con otros directorios es que este solo tiene el modesto objetivo de contener la información de todos los locales comerciales del barrio general paz y barrios aledaños. Digo modesto porque no pretende ser un directorio a nivel pais y mucho menos mundial. Pero es un sitio que se me hace necesario (y supongo que a otras personas del barrio).

Relevar un barrio no es solo un problema tecnológico, implica también caminar por el barrio y recolectar la información necesaria. Pretender que un 80% del barrio se abalance a mi página a cargar su local (y que lo hagan correctamente) es fantasioso. Pero este es un tema que no voy a tratar en este post.

La razón de este post es explicar la "tecnología" detrás del sitio y la razón para usarla.

Como este no es una novela de suspenso, voy a empezar revelando el misterio.

Tecnología usada en el sitio

La solución es mas bien "enlatada" y consiste en:
Con estas partes pude cumplir el objetivo de hacer lo que podríamos llamar "un bosquejo" del sitio que me propuse. Esto en solo unas 3 semanas, utilizando tiempo libre.

¿Por qué Joomla?

Antes que nada, tengo que aclarar algo que mucha gente que no usa Joomla piensa: Joomla no es solamente un sistema gestor de contenidos, también tiene un framework PHP que permite programar cualquier funcionalidad en forma de nuevos componentes, módulos y plugins para Joomla, usando la filosofía MVC. Una vez aclarado esto, no es esta la razón por la que usé Joomla. La razón para usar Joomla es que quería obtener un producto funcionando en el menor tiempo posible.

El sitio necesitaba tener un gestor de usuarios, de categorías, de locales comerciales, de tags. Y a la vez tener un nivel básico de seguridad.

Una vez instalados los componentes, módulos y plugins, solo me restó crear un template, o sea la parte visual del sitio. Todavía hay partes incompletas, y las partes completas fueron diseñadas por mi, con lo cual hay mucho que desear. Creé un template yo mismo para que sea lo mas simple posible.

El resto del tiempo dedicado al proyecto fue en parte configuración de los componentes para que funciones entre ellos (por ejemplo, que el sitemap muestre las categorias y avisos del componente de directorio comercial, o que las busquedas devuelvan locales, o que los tags cambien según el contexto de la categoría de SOBI2 que el usuario está mirando, etc).

Pero el mayor consumo de tiempo vino de pulir la parte visual de los componentes. Y esto nos lleva a los problemas de Joomla (o mas bien de sus componentes).

Los problemas de Joomla

En principio, el framework PHP que provee Joomla permite utilizar el paradigma MVC de diseño. Con lo cual adaptar los componentes visualmente para un sitio propio debería ser tan simple como crear un view. El problema es que Joomla no obliga al programador a usar MVC y me atrevería a decir que la mayor parte de los componentes de Joomla no están programados usando dicha filosofía. La razón principal, me imagino, es que muchos componentes fueron creado para versiones viejas de Joomla que no poseían herramientas para desarrollar en MVC y luego adaptado para nuevas versiones.

Uno de los puntos que me llevó mas tiempo fue unificar el componente de directorio comercial y el componente de avisos clasificados para que tuvieran una estructura html similar y que utilizaran las mismas hojas CSS (esto para unificar ambas partes visualmente y para disminuir el numero de hojas de estilo descargadas por el usuario).

Por alguna razón que desconozco, ambos componentes utilizan tablas para posicionar las categorías y subcategorías. Pero en el caso de SOBI2 la situación fue especialmente odiosa, con las instrucciones que corresponderían al view "desparramadas" por varios archivos, entre queries sql y llamadas a funciones.

Básicamente tuve que hackear a travez del componente para cambiar lineas del estilo "echo ''", incrustadas entre llamadas a la base de dato, a funciones de otros archivos e includes.... Y esto en múltiples lugares, ya que al no abstraer el view hay una repetición de código según el contexto en que se muestran los distintos elementos. Todavía se puede ver en el código fuente del sitio, vestigios de tablas que no sé en que momento son mostradas.

Por otro lado, varios queries SQL son impenetrables: JOINS muútiples concatenados, múltiples niveles de SELECT, etc. Lo cual me llevó a preguntarme: ¿No hay una abstracción de la base de datos en el framework Joomla? En general los frameworks modernos proveen algún tipo de abstracción, por ejemplo Rails y Turbogears permiten al usuario programar usando objetos, los cuales son mapeados en forma semiautomatica a tablas en la base de datos. Entonces, en lugar de tener que escribir un query sql que use JOINS entre tablas puedo manejarme con objetos, con los JOINS abstraidos convenientemente como una composición de objetos.  Probablemente Joomla tenga dicha abstracción, pero los programadores de SOBI2 no la hayan usado.

En principio podría haber usado otro componente en lugar de SOBI2. Pero según lei en internet SOBI2 es "el" componente de directorios para Joomla. Y claramente, desde el punto de vista del usuario que no va a modificar el código del componente, SOBI2 es una excelente herramienta, altamente configurable.

Esto es un problema principalmente de SOBI2, no de Joomla. Es interesante comparar, por ejemplo, con el poco trabajo que tuve cuando quise adaptar el componente nativo de busqueda de Joomla para mostrar los resultados en un Google Map. En este caso solo fue cuestión de buscar el modelo, insertar código para sacar de la base de datos la información geográfica de los resultados de busqueda y luego buscar el view e insertar el código para mostrar dicha información en un mapa. En un rato ya tenía el problema de los mapas solucionado.

A pesar de todos estos inconvenientes, es claro que la opción de programar el componente o el sitio yo mismo hubiera sido mucho mas costoso en tiempo.

Seguridad

Desconozco si existe algún tipo de agujero de seguridad en mi sitio. Dejo como tarea al lector tratar de hackear mi sitio. Todo se encuentra adecuadamente backupeado y listo para ser restaurado ante cualquier eventualidad. Solamente le pido que tenga en consideración describir la técnica usada en un comment de este blog.

El sitio es tan fuerte como el mas débil de sus componentes. Y teniendo los componentes distintos orígenes (y habiendo visto el código fuente de alguno de ellos), no me extrañaría que exista alguna vulnerabilidad.

Conclusión

Utilizar las herramientas que mencioné es una buena opción porque me permitió tener un sitio funcionando con poco tiempo de programación. Esto me permite empezar a dedicarme a promocionar el sitio y encontrar el set de funcionalidades óptimo para los posibles clientes.

Por otro lado, los cambios que tuve que hacer en los componentes hacen que se me haga imposible aplicar las actualizaciones oficiales sin romper mis cambios. Con esto en mente, es posible que en un futuro, cuando solucione o encamine el tema del "Business model" , se haga conveniente reimplementar el sitio desde 0 usando algún framework web. Hasta entonces, esta solución es adecuada.

Sería interesante saber si alguien conoce una mejor solución.



Licencia


Creative Commons License
Esta obra de Ezequiel Pozzo se encuentra bajo una licencia Creative Commons Atribución-No Comercial-Compartir Obras Derivadas Igual 2.5 Argentina License.
Se puede obtener permisos mas allá de los otorgados por esta licencia en ezequielpozzo.blogspot.com.