FreeLife: Implementación del "juego de la vida"

Bueno decirte q hay uno en desarrollo desde hace bastante tiempo, y desde hace bastante tiempo no avanza.
http://www.wiibrew.org/wiki/User:Drei000/WiiLife

En cuanto al algoritmo, tal vez deberías de haberlo planteado como una tabla y hacer tu mismo el control de los casos, si te es complicado el modelo q has encontrado. Yo ahora mismo estoy tratando de seguirlo y me estoy volviendo loco para entenderlo (tal vez también por q todo lo ultimo q he hecho es orientado a objetos y me he mal acostumbrado).

EL algoritmo esta organizado en dos tablas.

La tabla world que contiene todos los posibles neighbours (y que es de clase O(n), ya que es lineal a la resolucion) de momento esa no es el problema.
La segunda es la lista de vivos que se recorre dos veces y que es de orden cuadratico. Esta ademas es dependiente de la resolucion (que da el rendimiento minimo cuando todos las celulas estan vivas), pero evoluciona con el tiempo. Aqui es donde tengo que optimizar.

La primera optimización que voy a implementar (invertir el algoritmo cuando hay mas vivas que muertas) deberia darme una mejora del 50%. Pero aun necesito optimizar el sistema de "cuenta compañeros" pues necesito que no sature cuando entre el 35 y el 50% de celulas vivas.

Con respecto a la otra implementacion: `Modo ninapequena on'
el mio ez mejo po:
1. Mi univezo ez infinito y toroidal, el suyo no!
2. Mi implementacio va mas rapido!
3. Su sistema hace el scrolling mal! y como pongas progresivo parece que anda a lo chiquito de la calzada!
4. El zum, no lo haze en el zentro!
5. Zolo zoporta laz reglaz bazicas! Azi culquiera!
6. El mio tiene colorines!!!!!
7. Aunque el edit mode mola. Ze lo voy a copiar!!!!
'Modo ninapequena off'
8. No da las fuentes.

Olvidate del main file. Mirate los ficheros del repertorio cell_algo, que estan bien documentados y describen el algoritmo.
Por cierto, un detalle que te lo mires

He visto algunos puntos de la documentacion que se pueden mejorar... el calculate_neighbours supongo que no hay dudas. Para el otro es mas complicado.
1. Por cada celula del universo, recuperamos el numero de vecinos.
2. Transformamos ese numero a una mascara de regla (1 << numero_de_vecinos)
3. Si esa mascara es nula (no vecinos) => a por la siguiente, esta muerta.
4. Hay dos reglas, las de supervivencia (en conway 2 y 3 vecinos) y las de nacimiento (3 vecinos en Conway)
5. Si la celula estaba viva en la iteracion previa y el AND de la mascara con la regla de supervivencia no es nula => viva
6. Si la celula estaba muerta en la iteracion previa y el AND de la mascara con la regla de nacimiento no es nula => viva
7. Si no, muerta.

Supongo que ahi se podria restringir un poco la busqueda... pero me preocupa mas el calculate_neighbours.

No he mirado tu código, pero te pongo algunas reglas, por si eso te ayuda.

1ª Regla: el calculo mas rápido es el que no se realiza. Por ejemplo, supongamos que tenemos una matriz bidimensional, tal como esta char a[5][5]. Para acceder al elemento a[4][1] , la operación sería direccion_base+(4*5)+(1). Por tanto, podriamos crear una tabla que almacenase ese desplazamiento precalculado, por ejemplo asi:



2ª Regla: Usar numeros de base 2 para optimizar los calculos. Por ejemplo, la tabla anterior la definiamos como a[5][5]. Sin embargo, nada nos impide (excepto cuestiones de espacio) definirla como a[8][8] para poder utillizar desplazamientos en lugar de multiplicaciones y trabajar teniendo en cuenta solo 5 elementos de cada dimension: 3*8 = (3<<3) y aqui el compilador nos puede echar una mano a la hora de traducir las direcciones o en todo caso, nosotros podemos optimizar los calculos para posicionar en la tabla utilizando un puntero que apunte a la direccion base de la tabla y usando desplazamientos para reemplazar multiplicaciones.


3ª Regla: Si necesitamos acceder a elementos proximos alrededor de una casilla en una unidad, podemos crear una tabla con un 'borde' de elementos vacios para ahorrarnos la comprobación de limites: esto se puede hacer si la tabla tiene un tamaño fijo, de forma que por ejemplo, si tiene 512x512 elementos, utilizariamos 510x510 y el primer elemento sería el (1,1) . El borde se utilizaría para evitar comprobaciones de límite de tabla (rellenando con 0).

4ª Regla: Evitar calculos estúpidos. Por ejemplo, imaginemos que tenemos una tabla char a[512][512] y queremos comprobar si los elementos vecinos a (y,x) contienen un dato:




Si tu idea es utilizar una tabla 'infinita', de forma que se vayan reasignando la memoria que quede desocupada (llena de celulas muertas), usando tablas que se ajusten a calculos de base 2, podrás manejarlas facilmente, usando una matriz de punteros que almacene por ejemplo, 'porciones' de tabla de 8x8 elementos, de forma similar a como explicaba en la 'Regla 1ª', solo que aquí almacenarias la direccion completa y no únicamente el desplazamiento. En este caso, tendras que tener cuidado con las operaciones para que cuando se salga del límite de la mini-tabla, se ajuste de forma correcta (mas lento, eso si9

Si haces una tabla fija de 4096x4096 elementos, gastas 16MB de RAM y reservando un borde de una unidad, 4094x4094 es un buen pedazo de tabla, creo yo y puedes trabajar con ella muy rapidamente.

Si encima tienes la precaucion de crear una tabla que 'controle' sectores (una tabla que contenga un flag que almacene si en un grupo de 64x64 casillas (por poner un tamaño), hay vida o no, para evitar tener que recorrer toda la tabla en busca de vida que evolucionar), puedes ganar bastante velocidad.

Espero que te sirva de ayuda

Hermes escribió:1ª Regla: el calculo mas rápido es el que no se realiza. Por ejemplo, supongamos que tenemos una matriz bidimensional, tal como esta char a[5][5]. Para acceder al elemento a[4][1] , la operación sería direccion_base+(4*5)+(1). Por tanto, podriamos crear una tabla que almacenase ese desplazamiento precalculado, por ejemplo asi..[/b]

Ese ejemplo me parece que está un poco cogido con pinzas en CPUs modernas como la de la Wii. Las multiplicaciones se realizan en un ciclo de reloj, mientras que con una tabla tardas mas por el acceso a memoria (a no ser que esté en caché, y entonces estás malgastando espacio en ella).

En casos como este, y teniendo en cuenta los avances en CPUs modernas y en las optimizaciones en los compiladores, yo creo que es bastante mas importante centrarse en las optimizaciones mas a nivel alto del algoritmo (sobre todo evitar saltos, por ejemplo, que no le gustan nada a las CPUs si la predicción sale mal), en lugar de en micro-optimizaciones como sustituir una instrucción de multiplicación por un acceso a tabla (que probablemente termine siendo mas lento). Cuando las cosas se pueden calcular en un ciclo de reloj o dos, muchas veces es mucho mas rápido recalcularlas cada vez que malgastar la memoria para cachearlas.

marcansoft escribió:

Hermes escribió:1ª Regla: el calculo mas rápido es el que no se realiza. Por ejemplo, supongamos que tenemos una matriz bidimensional, tal como esta char a[5][5]. Para acceder al elemento a[4][1] , la operación sería direccion_base+(4*5)+(1). Por tanto, podriamos crear una tabla que almacenase ese desplazamiento precalculado, por ejemplo asi..[/b]

Ese ejemplo me parece que está un poco cogido con pinzas en CPUs modernas como la de la Wii. Las multiplicaciones se realizan en un ciclo de reloj, mientras que con una tabla tardas mas por el acceso a memoria (a no ser que esté en caché, y entonces estás malgastando espacio en ella).

En casos como este, y teniendo en cuenta los avances en CPUs modernas y en las optimizaciones en los compiladores, yo creo que es bastante mas importante centrarse en las optimizaciones mas a nivel alto del algoritmo (sobre todo evitar saltos, por ejemplo, que no le gustan nada a las CPUs si la predicción sale mal), en lugar de en micro-optimizaciones como sustituir una instrucción de multiplicación por un acceso a tabla (que probablemente termine siendo mas lento). Cuando las cosas se pueden calcular en un ciclo de reloj o dos, muchas veces es mucho mas rápido recalcularlas cada vez que malgastar la memoria para cachearlas.

Es un ejemplo generico, pero obviamente, si la CPU de Wii usa un unico ciclo de reloj en la multiplicaciones, no tiene sentido ni utilizar desplazamientos (siempre y cuando, no haya otros "trucos", como que operando de otra forma, la CPU pueda estar haciendo otra cosa. Por ejemplo, la CPU de PS2, tenía dos unidades de multiplicacion y aparte de que no lo hacian en un solo ciclo, usaban un registro especial del que luego tenias que mover el dato... y ya la hemos liado (o a lo mejor no te quedaba mas huevos que sincronizar). Eso si, para almacenar calculos mas complejos, una tabla te puede salvar la vida (por ejemplo, almacenar senos y cosenos)

Sobre los compiladores, pues depende mucho la cosa porque desde el mismo momento que por activar una optimización puedes tener errores en tu programa rarisimos, pues fiarte de ellos, no es lo mas aconsejable .

Al final me he liado yo... las multiplicaciones se hacen en dos ciclos, no en uno. Pero sigue siendo mas rápido que meterse a leer de RAM - una carga de datos tarda 2 ciclos (con latencia de pipeline), pero como no lo tengas en la caché L1 entonces se te dispara rápidamente. En este caso, lo mas rápido sería hacer que la dimensión horizontal sea una potencia de 2, y dejar que el compilador optimice y use un desplazamiento. Esto tambien ayuda porque el PPC tiene dos unidades de enteros, pero solo una puede hacer multiplicaciones y divisiones, asi que si usas un shift entonces puedes usar cualquiera de las dos.

Lo que si que tarda siglos son las divisiones, claro - 19 ciclos.

Una optimización que yo creo que ayudaría mucho sería eliminar los ifs:

claro, mientras tengas cuidado de mantener las celdas solo a 1 o 0. Al eliminar ese salto del IF (que encima es muy aleatorio y va a liar muchisimo al predictor del micro), lo conviertes en un simple load y una suma (punt=r3, lleno=r4):

marcansoft escribió:Al final me he liado yo... las multiplicaciones se hacen en dos ciclos, no en uno. Pero sigue siendo mas rápido que meterse a leer de RAM - una carga de datos tarda 2 ciclos (con latencia de pipeline), pero como no lo tengas en la caché L1 entonces se te dispara rápidamente. En este caso, lo mas rápido sería hacer que la dimensión horizontal sea una potencia de 2, y dejar que el compilador optimice y use un desplazamiento. Esto tambien ayuda porque el PPC tiene dos unidades de enteros, pero solo una puede hacer multiplicaciones y divisiones, asi que si usas un shift entonces puedes usar cualquiera de las dos.

Lo que si que tarda siglos son las divisiones, claro - 19 ciclos.

Una optimización que yo creo que ayudaría mucho sería eliminar los ifs:

lleno += *(punt-512);


claro, mientras tengas cuidado de mantener las celdas solo a 1 o 0. Al eliminar ese salto del IF (que encima es muy aleatorio y va a liar muchisimo al predictor del micro), lo conviertes en un simple load y una suma (punt=r3, lleno=r4):

lbz r5, -512(r3)
addi r4, r4, r5


Si, la recarga de cache, da un poco por culo, pero todo depende de la maquina y lo que estés haciendo (yo por ejemplo, en otras maquinas he creado pequeñas tablas en la pila (moviendo los datos) y se notaba la cosa, pues la tabla siempre estaba en cache y no penalizaba el acceso), pero todo depende de la maquina en cuestion.

Lo que dices de eliminar los saltos, tienes razón: al final me he liado yo y como lo estaba haciendo al vuelo, me he olvidado de que el dato lo normal es que contenga 1 o 0 y que es mejor sumar

El caso es evitando usar funciones, o usando funciones inline, y teniendo cuidado de definir como "register" ciertas variables claves (que es posible que el compilador las asigne o no, de esa forma, pero que no le viene mal que se lo digas tu) pues algo podemos ir ganando.

Al final lo mejor para estas cosas, es medir el tiempo que tardan los diferentes metodos y asi se sale de dudas

Bueno,

He estado mirando y he implementado dos pequeñas modificaciones.
1. Cambiar a acceso diferencial en la busqueda de vecinos. No más multiplicaciones.
2. Mejor alineado de ´world´
3. Eliminar la optimización de prefetch loop (que me estaba trasheando la cache de mala manera)
4. Implementar una doble lista, de manera que cuando más del 50% de las celulas estén vivas, se cambia el sistema a buscar muertos.
4a. Aplicar este cambio por regiones, de manera que se busque cual es el mejor sistema por cachitos. (En desarrollo esto)

Pero... es que me he dado cuenta de que el algoritmo no es tan lento... El problema esta aquí.



La dichosa llamada a GRRLIB_Rectangle es lentísima... (Y como la llamo por cada célula viva, la cosa empeora brutalmente...)

He intentado utilizar la función GRRLIB_DrawImg, pasándole un bitmap en formato RGBA8, pero los parametros de esa función son de risa, y la documentación inexistente, y he sido incapaz de utilizarla (tengo superscaning, flickering, no me llena la pantalla, vamos un desatre).

Así que voy a dejar de utilizar GRRLIB y asi ni tengo que preocuparme por la licencia... Solo una pregunta.
Alguien sabe cual es el formato del framebuffer?

En la firma de hermes tienes tu solucion.

Yo ahora estoy implementado una pequeña libreria para trabajar en 2D, con funciones de dibujo, etc, para un nuevo proyecto que estoy llevando a cabo

No está pensada para ser rapida (evitando enviar ciertos parametros graficos para conectar texturas/desconectarlas), porque la estoy haciendo para poder diseñar una interfaz tipo ventana, pero tiene funciones para dibujar superficies (vamos, el tipico QUAD con textura), rectangulos con o sin las esquinas redondeadas, rellenos o con un determinado grosor de linea, elipses, graficas de pastel y por supuesto, una fuente de letra y una funcion s_printf que equivale al printf normal mas o menos, solo que el '\n' pasa de el y permite distintos tamaños de letra y alguna cosilla mas

No está bien pulida todavía, pero si te hace falta para orientarte o funcionar, te la paso sin problemas (con eso y con el tutorial que hice, sobre las GX, que puedes encontrar aquí: http://mods.elotrolado.net/~hermes/index.html en "[Wii] Graficos 3D para Wii (PDF + Ejemplos)" te puedes apañar)

Técnicamente, tener una superficie del tamaño de la pantalla usando lo mio, sería algo asi:



Si te interesa, dímelo y mañana lo subo.

Lo malo es que no hay nada documentado, pero vamos, aqui mismo te puedo explicar como usar algunas cosas. Por ejemplo, se puede modificar la funcion DrawSurface para que dibuje una matriz de pantalla de menor tamaño a pantalla completa, para ver los pixeles ampliados (320x240, que serian 4:3 darian una ampliacion de 2x2)

Saludos

Hola Hermes,

Gracias por tu respuesta, y perdona por no haber mirado tu firma! El tutorial 3D explica prácticamente todo, (y sinceramente, me he enterado mejor de como va el Tiling con tu tiling4x4 que con el reverse engineering que estaba sacando de PNGU).

Todavía tengo algunos problemas, puesto que no puedo cargar la textura 640x480 ARGB8 (supongo que por problemas de memoria, 320x240 cabe). Y sigo utilizando GRRLIB para sacar la textura a display... (que hace un filtrado bastante feo.

Pues si, si que interesa la librería... en cualquier caso será más rapido que lanzar 640x480 peticiones de drawrect a GX

dmnieto escribió:Hola Hermes,

Gracias por tu respuesta, y perdona por no haber mirado tu firma! El tutorial 3D explica prácticamente todo, (y sinceramente, me he enterado mejor de como va el Tiling con tu tiling4x4 que con el reverse engineering que estaba sacando de PNGU).

Todavía tengo algunos problemas, puesto que no puedo cargar la textura 640x480 ARGB8 (supongo que por problemas de memoria, 320x240 cabe). Y sigo utilizando GRRLIB para sacar la textura a display... (que hace un filtrado bastante feo.

Pues si, si que interesa la librería... en cualquier caso será más rapido que lanzar 640x480 peticiones de drawrect a GX

Mi tiling4x4 tiene un fallo en ese tutorial: si te fijas, usa una memoria local para luego hacer el volcado u16 mem_tile[]; pues cambialo a u16 mem_tile[1024*8]; y podras trabajar con texturas a pantalla completa (el fallo está en un despiste mio, porque al principio el programa trabajaba con texturas de 16 bits, que sería lo logico como textura para ahorrar espacio y usar color directo)

En la libreria lo tengo resuelto (me di cuenta del fallo haciendo Wiiengine, donde uso esa misma tecnica y si estudias el fuente, veras que "camuflo" el tema de forma similar a como te he explicado aqui, para trabajar con una pantalla de 384x256 en los menus y de hasta 512x256 en el caso del emulador.

Te explico algunas cosas de la librería:

s_printf(), funciona como printf() (admite parametros con formatos y tal) pero está pensado para trabajar a una linea de pantalla (si desborda por la derecha, se pierde el texto)

Para controlarlo tienes estas variables en screen.c

static struct tagsizeletter // font size table (use 'sizeletter' as index)
{
unsigned tx,ty;
} sizelet[9] = {
{64,64},{32,32},{16,24},{12,16},{16,16},{12,24},{15,24},{128,192},{128,128}
};

int xclip=640; // screen width (recorte)

int autocenter=0; // centra en la linea
unsigned sizeletter=2; // tamaño de letra 2 (16x24) ver sizelet
unsigned bkcolor=0x00000000; // color de fondo de las letras (transparente en este caso)
unsigned color=0xffffffff; // color de las letras (blanco en este caso)
unsigned PX=0,PY=0; // coordenadas donde se empezara a dibujar el texto (en pixeles)

Por defecto, te sube una fuente de letra que es de un tamaño de 16x16 y te la prepara con una mascara (en la medida de lo posible) para mejorar el contraste.

Eso lo puedes controlar tu con UploadFontTexture(0) (sin mascara) o UploadFontTexture(1) (con mascara), pero recuerda
que eso es una textura que no deberias cambiar durante el frame a menos que aguardes a que se dibuje todo el texto con GX_DrawDone(); (cada letra es un quad y esa funcion de GX aguarda a que se dibujen todos los poligonos)

Mas: las funciones incluyen un parametro 'layer'. Esto tecnicamente, es la profundidad Z donde 0 es el elemento mas prioritario y 65535 por ejemplo, es el mas lejano (no uses numeros negativos). Las letras se dibujan en layer 0. Si dibujas letras y despues un rectangulo que ocupe toda la pantalla que tenga layer 1, no borrará las letras. Puedes usar esto, para superponer capas sin necesidad de ordenar las escrituras de superficies, etc.

Tambien recuerda que el parametro alpha aqui está activo: color con alpha 0, es completamente transparente, con 0x80 es semi transparente y con 0xff es completamente solido. Por lo tanto, aqui el color negro no es 0, si no 0xff000000 (con esa ordenacion de izquierda a derecha seria ABGR con 8 bit por componente)

Las funciones:

void DrawSurface(GXTexObj *surface,int x,int y, int width, int height, int layer, u32 color);

void DrawBox(int x,int y, int width, int height, int layer, int thickness, u32 color);
void DrawFillBox(int x,int y, int width, int height, int layer, u32 color);

void DrawRoundBox(int x,int y, int width, int height, int layer, int thickness, u32 color);
void DrawRoundFillBox(int x,int y, int width, int height, int layer, u32 color);

void DrawSlice(int x,int y, int dx, int dy, int layer, int thickness, int degrees_start, int degrees_end, u32 color);
void DrawFillSlice(int x,int y, int dx, int dy, int layer, int degrees_start, int degrees_end, u32 color);


void DrawEllipse(int x,int y, int rx, int ry, int layer, int thickness, u32 color);
void DrawFillEllipse(int x,int y, int dx, int dy, int layer, u32 color);

void DrawLine(int x,int y, int x2, int y2, int layer, int thickness, u32 color);

No tienen mucho misterio: thickness es el grosor de linea de 1 a ... lo que sea! para superficies no rellenas.

Lo que si tienes que saber que previamente, puedes usar SetTexture(NULL); para que se dibuje sin textura, usando el color especificado o con SetTexture(GXTexObj *texture); puedes usar una textura como trama (textura que puedes crear de igual forma que dibujas la pantalla y "subirla" al objeto GXTex con CreateTexture() solo que en este caso, pon el parametro 'repeat' a 1
para que se repita la trama en forma de mosaico o a 0, si no te hace falta.


Por defecto yo he creado unas pocas tramas que puedes ver definidas en screen.h (acuerdate de incluirlo ). Por ejemplo
SetTexture(SQUARE_PATTERN); para usar este tipo de tramado

#define STRIPED_PATTERN &tex_pattern[0]
#define CROSS_PATTERN &tex_pattern[1]
#define SQUARE_PATTERN &tex_pattern[2]
#define MOSAIC_PATTERN &tex_pattern[3]
#define NULL_PATTERN NULL

Y creo que ya esta todo mas o menos comentado: si quieres que Drawsurface actue como 'aumento' no tienes que hacer nada aqui (ayer me despiste y no recordé que uso coordenadas fijas en textura ). Simplemente, usa lo que te puse arriba pero en vez de subir una textura del tamaño de la pantalla, sube una de 320x240 o la resolucion que mas te apetezca (procura que siga la regla 4:3 eso si, para no ver pixeles rectangulares)

NOTA: Recuerda siempre, terminar con Screen_flip(); el frame. Esto es muy importante, si vas a salir del programa, llama antes a esa funcion para prevenir que haya cosas en transito al GX y que se pueda colgar el programa

Te paso los fuentes como enlace (y si alguien lo encuentra de interés, que no se corte en bajarlo, claro ):

Bueno, acabo de subir una última versión que más o menos me satisface en cuanto a velocidad...

Todavía no utilizo la librería de Hermes, pero la próxima versión dejará de utilizar GRRLIB.
Con el particionamiento que estoy implementando, el algoritmo ya no es el cuello de botella, es el traceado.

Voy a seguir utilizando el método de texturizar el mundo... tengo que mirarme un poco el tutorial de Hermes, porque el cálculo de la posición de las células en la pantalla lo sigo haciendo a mano. ( y por favor, no miréis el código del zoom, que hace daño... creo que no lo he documentado para no darme vergüenza a mi misma...)

Que alguien me corrija si me equivoco, pero creo que debería ser posible (y más rapido) generar siempre la textura de 640x480 (o incluso más). Luego modificar el viewport para que la textura se expanda toroidalmente y luego para mover la imagen, utilizar HW scrolling (aka, mover el viewpoint en XY).

A ver que tal

EDIT:

Hermes, voy a subir una versión que usa tu librería. Te importa que la incluya en el project dir? (Licencia intacta, por supuesto)

dmnieto escribió:
EDIT:

Hermes, voy a subir una versión que usa tu librería. Te importa que la incluya en el project dir? (Licencia intacta, por supuesto)

Subela que no hay ningun problema: esa licencia la pongo así para que hagais vuestras modificaciones a titulo personal con completa libertad. Esto no es una GRRLIB que tenga que mantener el formato, ni estas obligada a pasarme los cambios que hagas

Mas bien mi idea era hacer algo para uso propio pero que tambien sirva a todo el que quiera hacer un uso 2D clásico y no sepa apañarse con las GX, para que tengan un punto de partida y lo adapten a su uso personal (uno de mis objetivos siempre es fomentar el desarrollo por vuestra parte y facilitarlo en todo lo que esté en mi mano )

jeje, gracias

De hecho, ya la he modificado un poquito... el filtrado lo he pasado a GX_NEAR para tener mis buenos cuadraditos...

dmnieto escribió:jeje, gracias

De hecho, ya la he modificado un poquito... el filtrado lo he pasado a GX_NEAR para tener mis buenos cuadraditos...

La verdad es que ya habia caido yo en ello, pero he preferido no decirte nada (llámalo una especie de prueba)

Creías que no me iba a leer la documentación?

Pues sí, soy rara , yo me leo hasta los libretos de instrucciones de la tostadora. (A veces hay sorpresas)

Editado... parecía que l echaba la bronca a Hermes ...(osara yo)

dmnieto escribió:Creías que no me iba a leer la documentación?

Pues sí, soy rara , yo me leo hasta los libretos de instrucciones de la tostadora. (A veces hay sorpresas)

No, pero date cuenta que no te conozco! No se que competencia tienes en programación, y aunque algunas de mis explicaciones van para todos los que nos lean (no estamos solos... ), no es lo mismo hablar para una persona que se adapta rapido y tiene recursos, que para alguien que le pones delante el código y se lo explicas y se ha quedado casi igual .

Por tanto, había dos posibilidades:

a) Te das cuenta del detalle y me preguntas como arreglarlo (no pasa nada y yo te oriento para arreglarlo)

b) Lo haces tu solita sin preguntar (y con esto demuestras que mi intuición no se equivoca y me gano un galifante )

[/size]

Hermes escribió:Por tanto, había dos posibilidades:

a) Te das cuenta del detalle y me preguntas como arreglarlo (no pasa nada y yo te oriento para arreglarlo)

b) Lo haces tu solita sin preguntar (y con esto demuestras que mi intuición no se equivoca y me gano un galifante )

I've got something for you!

Bueno, aunque todos estamos recuperándonos del maravilloso trabajo de nuestro marcan y bushing (y nos relamemos de pensar en las posibilidades) támbién los pequeños novatillos de la scene seguimos trabajando

He estado implementando una mejora interesante que es el particionamiento:

Hasta ahora el algoritmo consta de dos(+1) partes:
1. Recorrer la lista de vivos (o de zombies) e incrementar el numero de vecinos de las celulas que lo rodean.
2. Recorrer el mundo y matchear los vecinos de cada celula con las reglas del universo. Marcar la célula como viva o muerta.
3. Comparar el numero de vivos con el de muertos, y actualizar una variable que permitirá al paso uno saber si debe analizar el numero de vivos o de muertos (lo que cueste menos).

La extensión de este algoritmo al particionamiento no es otra cosa que dividir el mundo en cachitos y utilizar el mismo algoritmo a cada trozo. Esto tiene dos ventajas:
1. Permite un mejor aprovechamiento de la localidad (si solo hay celulas en un pedazo de la pantalla, solo se aplicaría la busqueda de zombies a ese cacho).
2. Se estructura el algortimo para un mejor proceso en paralelo. (la wii me parece que es mono-thread, pero en caso de portarse a otras arquitecturas sería interesante.

El algoritmo tiene varios problemas:
PROBLEMA 1. Celulas frontera: Las celulas frontera son las que delimitan un trozo del mundo. Si se aplica el algoritmo directamente, ocurre que en la frontera hay vecinos de como minimo dos regiones. Cual es el problema?
Basicamente cuando la parte (1) del algoritmo se ejecuta sobre una lista de vivos los vecinos suman, pero si es una lista de zombies los vecinos restan. La parte (2) sabe si recorre un mundo gobernado por vivos o zombies, asi que corrige esto automáticamente (basicamente suma 8 al valor de vecinos de la celula si se han analizado zombies). Este truco funciona siempre salvo en las células frontera donde puede ocurrir que tenga contribuciones a un lado de vivas (sumando) y al otro lado de zombies (restando) con lo que los valores son falsos.
Soluciones
a) Garantizar la coherencia de datos: Basicamente que todas las celulas escaneadas por (2), su numero de vecinos sea calculado de la manera correcta. Como? Partiendo el mundo en cachos que se 'overlapen'. El area de escaneado de los algoritmos le amplia en una celula (de manera que se incluyen las fronteras de los algoritmos adyacentes). Cuando se va a dibujar la pantalla sin embargo, estos pixeles extra no se dibujan.
Desventaja: 10% mas de memoria y mayor complejidad en la generacion de la textura. Complejidad extra en el calculo de desbordamiento.
b) Cambiar el calculo de vecinos. Se añade a la matriz world un campo llamado 'zombies' cuando (1) recorre una lista de zombies, suma en zombies, y cuando es de vivos suma en vivos. El numero de neighbours para la frontera se calcula (para un mundo de vivos) como
ELEMS_OUTSIDE es el numero de ceculas que rodean a la celula fronteriza y que caen fuera del mundo (puede ser 3,4 o 5 dependiendo de la posicion). Desventajas (+50% en memoria del mundo), requiere un loop con check internos en las celulas fronterizas para el paso (2).
Ya diré que solución cojo.

PROBLEMA 2 Threading, lo dicho Wii es mono thread, no puede ejecutar dos threads en paralelo. O al menos no que yo sepa, aun tengo que investigar de que manera organizo el particionamiento para optimizar al maximo el uso de la cpu. (de momento se ejecutan dos threads con los algoritmos realizados linealmente)

Pues eso es todo de momento... a dormir!

P.S.: Me pregunto si lo que cuento le interesa a alguien o si hablo sola...En fin Me lo paso bien!