Simulación de Ecosistemas
En el apartado anterior vimos como crear organismos virtuales autónomos. También vimos como lograr que estos organismos se muevan de forma natural, pero hasta el momento, estos organismos no logran percibir a sus pares. Es decir, a pesar de moverse por un espacio en común, no pueden verse entre sí.
Es ahora, entonces, cuando veremos como lograr que estos seres virtuales interactuen entre sí, para ello es preciso que puedan percibirse unos a los otros. En este caso en particular, la forma en que estos agentes se manifiestan es a partir de su posición y movimiento, dado que eso es todo lo que por el momento saben hacer. Por lo tanto la forma en que ellos pueden percibir al resto es conociendo la posición de los demás.
La explosión combinatoria
La forma concreta en la que se logra que los agentes interactúen, es haciendo que cada uno de ellos compare su posición en el espacio, con la de todos los demás. Por ejemplo, si tenemos 5 agentes, el 1 deberá comparar su posición en el 2, el 3, el 4 y el 5.
Pero luego cada uno de los otras deberá hacer lo mismo:
Si el vínculo que se establece entre dos agentes no tiene dirección, es decir que, visto desde los dos individuos es lo mismo, entonces, cuando hay 4 agentes el número total de vínculos simples es 6. Pero, si en cambio, el vínculo cambia según la dirección, entonces con 4 agentes tenemos una 12 vínculos bidireccionales:
En la tabla anterior se puede ver claramente que pequeñas cantidades de agentes implican grandes cantidades de vínculos. El problema de esto es que este tipo de simulaciones son interesantes cuando la cantidad de agentes superan los cientos. Sin embargo la cantidad de interacciones que requieren cientos de agentes puede ser muy alta para seguir sosteniendo la performance de una aplicación en tiempo-real.
División del territorio
Supongamos que tenemos un escenario con 20 agentes y que queremos que estos se muevan libremente, pero cuando se cruzan con otro, lo esquiven, haciendo que salgan en la dirección opuesta. Un escenario como este necesitaría de 380 interacciones. Pero si se analiza el problema en profundidad, se observa que no tiene sentido comparar los agentes que se encuentran lejos unos de otros. El problema de este razonamiento, es que para saber cuales están lejos de los otros, es necesario hacer la comparación, después de todo, el sentido de la comparación era revisar las distancias.
Existe otra forma de resolver el problema. Esta consiste en dividir el espacio en espacios más pequeños, en los que quepan menos agentes. De esta forma, el espacio queda dividido en un número homogéneo de celdas, las cuales albergan menor cantidad de agentes. Así se puede determinar que agentes se encuentran cerca unos de otros, dado que en principio pertenecerán a la misma celda.
Por ejemplo, en el diagrama que se encuentra arriba, se pueden ver 20 agentes distribuidos en 9 celdas. Algunas celdas poseen desde 1 hasta 5 agentes, algunas no poseen ninguno. Con esta división la cantidad de interacciones se reduce a 52. Cuanto más chicas sean las celdas, menor será la cantidad de agentes que quepan dentro de cada una de estas, y por ende menor la cantidad de interacciones. Sin embargo, en casos extremos el tamaño de las celdas podría ser tan pequeño que sólo entrase un o ningun agente, por lo que estos serían incapaces de ver al resto.
En el ejemplo anterior también se puede ver que el agente 20 y el 10 (aproximadamente en el centro de la escena) se encuentra relativamente cerca, pero no interactuarán, dado que se encuentran en diferentes celdas, y sin embargo la 20 interactúa con la 3, siendo que se encuentra más lejana que la 10.
Esquivando a los otros
Ejemplo Vida 05 En el ejemplo que esta arriba, los organismos son capaces de recorrer el espacio e intentear esquivar a los otros organismos. Para esto fue necesario implementar un algoritmo que administre el territorio de la forma antes descripta. La idea del mismo, es que en cada ciclo (cada fotograma) de la ejecución, luego de mover los organismos, se los ubica a cada uno en la celda de territorio que les corresponde. Para esto se crearon un conjunto de funciones que organizan el desarrollo de este algoritmo:
void draw(){ ... revisar_Territorio(); resolver_Encuentros_Organismos(); mover_Organismos(); dibujar_Organismos(); ... }Hecho en Processing
En el código escrito arriba se puede observar el ciclo de funcionamiento:
1- Revisa la posición de cada organismo y los ubica en la celda de territorio que les corresponde.
2- Recorre celda por celda el territorio y en cada una de estas revisa los encuentros entre organismos.
3- Mueve los organismos en función de lo resuelto en cada encuentro.
4- Dibuja los organismos en pantalla.Los dos últimos pasos son exactamente iguales a los vistos en el apartado anterior. De hecho el comportamiento mover() (de la clase Organismo) no ha cambiado en nada.
void mover_Organismos(){ for(int i=0;i<cantAnimales;i++){ //se recorre cada animal y : animales[i].mover(); //cada uno camina hacia la // comida y actualiza su energia } } void dibujar_Organismos(){ for(int i=0;i<cantAnimales;i++){ //se recorre cada animal y : animales[i].dibujar(); //dibuja cada animal } }Hecho en Processing
Como se ve arriba, estas nuevas funciones lo único que hacen es recorrer el arreglo de organismos y ejecutar sus comportamientos mover( ) y dibujar( ).
La duda que puede surgir en este punto es ¿cómo es que sin cambios en el comportamiento mover( ) los organismos se comportan distintos? Esto se logra por que la desición de hacia dónde moverse se resuelve en un omportamiento, llamado resolverEncuentro( ):
void resolverEncuentro( Organismo otro ){ if( dist( x , y , otro.x , otro.y ) < radio*4 ){ //si se encuentra a menos de dos cuerpos //de distancia del otro, entonces sale en la dirección opuesta direccion = atan2( y-otro.y , x-otro.x ); } }Hecho en Processing
El comportamiento resolverEncuentro( ) recibe un objeto Organismo como parámetro (llamado otro). Dado que otro es también un organismo, posee los mismos datos que este objeto, es decir: x, y, dirección, velocidad, dx, dy, radio,etc. Entonces utiliza los datos de posición (x e y) para compararlos con los propios y así estimar la distancia del otro: dist( x , y , otro.x , otro.y ) < radio*4 (la función dist(x1,y1,x2,y2) calcula la distancia entre dos puntos ). Si esta condición se cumple, entonces toma la dirección contraria: direccion = atan2( y-otro.y , x-otro.x ) ( la operación atan2(y2-y1,x2-x1) devuelve el ángulo descripto por dos puntos (la pendiente).
Administrando el territorio
Si bien la clase Organismo tiene un comportamiento para resolver el encuentro con otro. Es necesario ejecutar esta acción desde fuera, presentándole los diferentes otros a cada organismo. Como vimos al principio hacer esto entre todos los organismos en forma indiscriminada puede generar problemas por la explosión combinatoria. Por eso es necesario administrar el territorio según el criterio que antes describimos. Para ello desarrollamos una clase Territorio que a su vez está conformada por una matriz de objetos de tipo T_Lugar. La función de los objetos T_Lugar es registrar los organismos de cada celda en que se divide el territorio. Para ello posee tres arreglos, dos para las posiciones de los organismos (x[ ] e y[ ] ) y otro para registrar los identificadores de estos ( id[ ] el número de índice en el arreglo de organismos).
class T_Lugar{ int cantidad; int limite; int fila,col; float x[], y[]; int id[]; T_Lugar( int col_ , int fila_ ){ fila = fila_; col = col_; cantidad = 0; limite = 100; x = new float[limite]; y = new float[limite]; id = new int[limite]; } void agregar( float x_ , float y_ , int id_ ){ if( cantidad < limite-1 ){ x[ cantidad ] = x_; y[ cantidad ] = y_; id[ cantidad ] = id_; cantidad ++; } } }Hecho en Processing
Las variables fila y col sirven para almacenar la posición de la celda en el territorio. Sólo es útil para hacerle posteriores consultas a la celda.
El comportamiento agregar( float x_ , float y_ , int id_ ), que es el que nos interesa, permite agregar un nuevo organismo a esta celda. Por cada organismo que se agrega, se carga en los arreglos (x[ ], y[ ] e id[ ] ) y luego se incrementa la variable cantidad.
A su vez el objeto territorio se encarga de verificar en cuál celda está el organismo:
class Territorio{ float ancho; float alto; int filas; int col; int modH,modV; T_Lugar lugares[][]; Territorio( float anchoPantalla , float altoPantalla , int filas_ , int col_ ){ //inicializa el objeto definiendo la matriz de celdas ancho = anchoPantalla; alto = altoPantalla; filas = filas_; col = col_; modH = int(ancho/col); modV = int(alto/filas); lugares = new T_Lugar[ col ][ filas ]; for(int i=0;i < col;i++){ for(int j=0;j<filas;j++){ lugares[i][j] = new T_Lugar(i,j); } } } void ubicar( float x , float y , int id ){ //este comportamiento ubica a cada objeto en su celda if( x>0 && x<ancho && y>0 && y<alto){ int cualX = int(x/modH); //define el lugar horizontal en el que //cae el objeto int cualY = int(y/modV); //define el lugar vertical en el que cae //el objeto cualX = (cualX >= col ? col-1 : cualX); cualY = (cualY >= filas ? filas-1 : cualY); //agrega el objeto en la celda elegida lugares[ cualX ][ cualY ].agregar( x , y , id ); } } ...Hecho en Processing
Como se observa arriba, el constructor de la clase Territorio recibe como parámetros las dimensiones de la pantalla (la escena) y la cantidad de filas y columnas de la matriz de celdas en las que se divide el territorio. En función de estos parámetros, el constructor calcula las variables modH y modV, las cuales describen las dimensiones (en píxels) de cada celda.
El comportamiento ubicar( float x , float y , int id ) se encarga de recibir la posición e identificación de cada organismo, para calcular en cúal celda está ubicado, esto lo hace con las operaciones:
int cualX = int(x/modH)
int cualY = int(y/modV)
Luego le envía la información a la celda seleccionada para que esta lo agregue a su lista:
lugares[ cualX ][ cualY ].agregar( x , y , id ).Las funciones que comandan estas acciones desde la estructura principal son revisar_Territorio( ) y
resolver_Encuentros_Organismos( ). La primera es bastante sencilla:
void revisar_Territorio(){ miTerritorio = new Territorio( width , height , celdas , celdas); for(int i=0;i<cantAnimales;i++){ //se recorre cada animal y : miTerritorio.ubicar( animales[i].x , animales[i].y , i ); } }Hecho en Processing
Inicializa el territorio, es decir, vacía todas las celdas ejecutando el contructor:
miTerritorio = new Territorio( width , height , celdas , celdas)
Luego, recorre todos los organismos, ejecutando la acción ubicar( ), para que el territorio los ubique en la celda que les corresponde.La función resolver_Encuentros_Organismos( ) es algo más compleja:
void resolver_Encuentros_Organismos(){ int limiteEncuentros = 20; for( int i=0 ; i<miTerritorio.col ; i++ ){ //recorre una por una las for( int j=0 ; j<miTerritorio.filas ; j++ ){ //celdas del territorio T_Lugar esteLugar = miTerritorio.lugar( i , j ); //toma cada lugar del territorio for( int k=0 ; k < esteLugar.cantidad-1 && k<limiteEncuentros ; k++ ){ // toma uno por uno los objetos de este lugar int id1 = esteLugar.id[k]; // recupera el id for( int l=k+1 ;l < esteLugar.cantidad && l<limiteEncuentros ; l++ ){ // toma otro objeto del lugar int id2 = esteLugar.id[l]; // recupera el id animales[id1].resolverEncuentro( animales[id2] ); // enfrenta al organismo // 1 con el 2 animales[id2].resolverEncuentro( animales[id1] ); // enfrenta al organismo // 2 con el 1 } } } } }Hecho en Processing
Los dos primeros ciclos for (los que corresponden a las variable i y j) se encargan de recorrer el territorio celda por celda. La instrucción T_Lugar esteLugar = miTerritorio.lugar( i , j ) carga en la variable esteLugar la celda correspondiente a la posición( i y j). Luego, el ciclo for correspondiente a la variable k se encarga de recorrer uno a uno los organismos de esa celda.
En este ciclo, la condición k<limiteEncuentros sirve para que la cantidad de encuentros no superen un límite preestablecido. Esto es dado que podría suceder el hipotético caso de que todos los organismos estén en una única celda de todo el territorio, en cuyo caso estaríamos con el mismo problema que al principio. Frente a esta posible situación, no nos queda más remedio que limitar la cantidad de encuentros.
El cuerto ciclo, el correspondiente a la variable l, se encarga de seleccionar un nuevo organismos para enfrentar al ya seleccionado, por eso el recorrido del ciclo se hace desde l=k+1. La combinación de recorrido de los dos ciclos for (el de k y l) asegura que se recorre todos los casos de combinación (en tanto no se llegue al límite de encuentros), sin nunca llegar hacer que k y l sean iguales:
for( int k=0 ; k < esteLugar.cantidad-1 && k<limiteEncuentros ; k++ ){
for( int l=k+1 ; l < esteLugar.cantidad && l<limiteEncuentros ; l++ ){Por último, se les pide a los organismos seleccionados que enfrenten a su pareja:
animales[ id1 ].resolverEncuentro( animales[ id2 ] )
animales[ id2 ].resolverEncuentro( animales[ id1 ] )