Saludos makeros:
Estuve revisando notas para realizar IAs y no tengo muy claro cual es la mejor forma de implementar "árboles" en GML.
Para aquellos que no lo saben, un árbol es una estructura, parecida a una lista o un array, pero organizada de forma tal que parta de un nodo central, o raiz, hasta uno o varios nodos externos, u hojas.
En caso de que desde cada nodo se puede acceder a dos o menos hojas se le llama árbol binario. como el de la imagen adjunta.
Desde ya, Muchas Gracias a todos. ;D
Me uno a la pregunta, estoy necesitando uno para unos menús. o sea ir recorriendo el arbol
Por ahora lo hice guardando en un array la traza (por ejemplo {14, 4, 9, 7, -1, -1, -1} en donde -1 no fue recorrido) El problema es que para guardar el arbol lo hice con switchs, va viendo uno por uno y va devolviendo las alternativas. En fin mi metodo es un lio.
Mh se me ocurre usar mi script de arrays con infinitos índices, cada índice representaría un nivel de nodos, y de ahí armás el árbol con facilidad. Algo así
(Dejo el link a mi script) (http://www.comunidadgm.org/index.php?topic=11517.0)
Gracias mil, makero Texic:
Repaso la idea y te digo... ;D
No llegue a entender.
Se me ocurrio poner arrays dentro de arrays, o sea segun la imagen:
Hay un array de tamaño 2 que se llama 14, dentro de el hay dos arrays que se llaman 4 y 5
El array 4 tiene dentro un array que se llama 3 y otro que se llama 9
Etc, etc, etc.
Pero el GM no creo que deje meter arrays dentro de arrays :-\
Nono, fijate el link que pasé de mi script, se puede armar facilmente un array con infinitos índices, cada número que ves en la imágen es un índice, en un rato te hago un ejemplo práctico con búsqueda y todo
Cita de: Mgbu en Febrero 21, 2013, 09:01:30 PM
No llegue a entender.
Se me ocurrio poner arrays dentro de arrays, o sea segun la imagen:
Hay un array de tamaño 2 que se llama 14, dentro de el hay dos arrays que se llaman 4 y 5
El array 4 tiene dentro un array que se llama 3 y otro que se llama 9
Etc, etc, etc.
Pero el GM no creo que deje meter arrays dentro de arrays :-\
No, he intentado varias veces pero no logré insertar un "array" dentro de otro. :/
Por eso la opción que nos brinda Texic es bienvenida, además que no tendrá el límite de los 32000 índices. ;)
De todas formas estaba trabajando en una forma de recrear un árbol en una sola dimensión. Siempre basado en un convencionalismo que establezca de ante mano, por supuesto. Aún así sería incómodo trabajar con él de esa forma. La manera de Texic parece más natural. ;D
Ahí va un ejemplo, lo hice rapido, las funcionalidades a agregar pueden ser muchas más, depende más que nada de tus habilidades como programador
¡Muy bueno, makero Texic! :
Como decimos acá: ¡Estás escapa'o! XD
Lo único que me resta para dar por cerrado el tema es que me expliques que significa realmente la solución esa de: "1_2_1" para la letra "F" :-[
por el resto doy SOLUCIONADO al tema... ;D
Es la posición en el árbol en la que encontró el valor buscado. Eso se tendría que trabajar un poco con funciones de manejo de strings para obtener algo más limpio, pero no tenía muchas ganas y lo dejé así xD
Oh. Muy interesante. Nunca he usado árboles, pero al ver que makero Mgbu mencionó que quiere usarlo para implementar menús, me entró la duda. Una pregunta para Mgbu ¿a qué te refieres con switches? Quizás es lo que se me ha ocurrido, pero no lo sé. Por favor miren mi diagrama
Ahí los índices están en binario. El valor entre paréntesis es el valor en decimal del índice. No estoy seguro si esto facilitaría su implementación o al contrario, la complicaría. Por ejemplo, lo que menciona Texic de traducir 1_2_1 con funciones de strings, podría hacerse así
101 = 6 = F
Mediante una conversión binario a decimal. El detalle es... que por ahora no tengo idea de cómo implementar algo así. Me ha surgido el interés por las operaciones binarias y bit a bit, pero no tengo idea de cómo hacerlas en GM
No sé si Texic podría echarme la mano con un script. ¿Usar los índices binarios traería ningún beneficio o es mejor olvidarse de la idea?
Gracias
Ah, ahora entiendo, gracias Texic! (se deberian poder dar puntos a respuestas además de poder dar puntos a temas :P)
Claro, cada variable va guardando la "traza" o el "camino" para llegar a el.
Cita de: penumbra en Febrero 22, 2013, 09:50:19 AM
Oh. Muy interesante. Nunca he usado árboles, pero al ver que makero Mgbu mencionó que quiere usarlo para implementar menús, me entró la duda. Una pregunta para Mgbu ¿a qué te refieres con switches? Quizás es lo que se me ha ocurrido, pero no lo sé. Por favor miren mi diagrama
Yo tenía un arbol para un menu que no era binario, o sea que cada indice puede tener más "hijos", normalmente tienen 4 en lo que necesito, si necesitas un arbol binario creo que se volveria demasiado largo. Ademas esta hecho programaticamente (o como se diga), o sea que si necesitas varios arboles tenes que copipar y pegar el codigo :P. Pero seria asi:
Cada indice tiene un "id" en forma de string, parecido a el ejemplo de Textic, entonces la F tendria un id de "121". Y luego para guardar en que indice estoy (o en que menu estoy) tengo un array que va guardando el caminito que recorrí, o sea guardo cada uno de los id de lo menues por los que pase, si estoy en el menu F el array sería así {1, 2, 1, -1} (por -1 todavia no pasé)
Los switches de los que hablaba eran para saber cuales eran las opciones desde ese indice, o sea que si estas en el indice F las opciones son L y M. Si fuera un arbol binario la respuest seria facil, chequear los indices con arrget en "1_2_1_1" y "1_2_1_2", pero como mi arbol no es binario, no sabia como resolver el problema, entonces mi switch era así:
switch(traza[0]) {
case -1: {
casillas = {"0", "1"};
}
case 0: {
switch(traza[1]) {
case -1: {
casillas = {"00", "01", "02", "03"};
}
case 0: {
casillas = {"000", "001", "002", "003"};
}
case 1: {
casillas = {"010", "011", "012", "013"};
}
case 2: {
casillas = {"020", "021"};
}
case 3: {
casillas = {"030", "031", "032", "033"};
}
}
break;
}
case 1: {
switch(traza[1]) {
case -1: {
casillas = {"10", "11", "12", "13"};
}
case 0: {
casillas = {"100", "101", "102", "103"};
}
case 1: {
casillas = {"110", "111", "112", "113"};
}
case 2: {
casillas = {"120", "121"};
}
case 3: {
casillas = {"130", "131", "132", "133"};
}
}
break;
}
}Ahí "casillas" guardaría las opciones a elegir.
Pero claro, mi arbol era más ancho que largo por asi decirlo, y mi solucion fue a fuerza bruta, nada de ahorrar codigo, entonces necesitaba solo tres switches, pero en un arbol binario como el de la imagen la cantidad de switches seria de como 6
Al final mi solucion es la unica que me sirve, porque al tener indices con distinta cantidad de hijos no tengo forma de saber cuales son los hijos de determinado indice sin tener que hacer un switch gigante como el que hice ¿O hay otra forma?
Si, se puede, ahora te hago un ejemplo, lo que importa en lo que hice es que el último número pertenece al identificador del nodo y todos los anteriores a el recorrido para llegar hasta él, si yo por ejemplo pusiera arbol_1_3 sería totalmente válido, simplemente habría que acomodar el algoritmo de búsqueda porque está hecho para un máximo de 2 ramas por nodo, pero no resultaría para nada dificil cambiarlo a uno que sea infinito, simplemente tendría que chequear por la rama siguiente hasta que no exista una
Cita de: penumbra en Febrero 22, 2013, 09:50:19 AM
Oh. Muy interesante. Nunca he usado árboles, pero al ver que makero Mgbu mencionó que quiere usarlo para implementar menús, me entró la duda. Una pregunta para Mgbu ¿a qué te refieres con switches? Quizás es lo que se me ha ocurrido, pero no lo sé. Por favor miren mi diagrama
Ahí los índices están en binario. El valor entre paréntesis es el valor en decimal del índice. No estoy seguro si esto facilitaría su implementación o al contrario, la complicaría. Por ejemplo, lo que menciona Texic de traducir 1_2_1 con funciones de strings, podría hacerse así
101 = 6 = F
Mediante una conversión binario a decimal. El detalle es... que por ahora no tengo idea de cómo implementar algo así. Me ha surgido el interés por las operaciones binarias y bit a bit, pero no tengo idea de cómo hacerlas en GM
No sé si Texic podría echarme la mano con un script. ¿Usar los índices binarios traería ningún beneficio o es mejor olvidarse de la idea?
Gracias
Mh, si, se puede usar y para usarlo dentro de un script podría llegar a traer algún beneficio por el hecho de que los argumentos del script están limitados, pero hay que hacer mucho cálculo para pasar de binario a hexadecimal y viceversa. Además el código se puede llamar con facilidad fuera de un script y ponerle tantos argumentos como sea necesario, después de todo sería una sola línea de código
Saludos makeros:
Ya puedo dar por cerrado el tema.
Muchas gracias todos por la atención prestada.
Cita de: Mgbu en Febrero 22, 2013, 03:11:15 PM
Ah, ahora entiendo, gracias Texic! (se deberian poder dar puntos a respuestas además de poder dar puntos a temas :P)
Claro, cada variable va guardando la "traza" o el "camino" para llegar a el.
Mgbu estoy de acuerdo contigo en que se deben puntuar las respuestas. Eso es algo imprescindible para este foro.
Cita de: penumbra en Febrero 22, 2013, 09:50:19 AM
Ahí los índices están en binario. El valor entre paréntesis es el valor en decimal del índice.
Makero penumbra muy interesante la notación en binario.
Cita de: penumbra en Febrero 22, 2013, 09:50:19 AM
No sé si Texic podría echarme la mano con un script. ¿Usar los índices binarios traería ningún beneficio o es mejor olvidarse de la idea?
Sería un problema en cuanto a la memoria utilizada ya que hasta dodne yo llego, los números en binarios los he tenido que implementar utilizando simples "strings" y cada "char" es alrededor de dos "bytes".
Si hay algún tipo de datos binario en GML lo desconozco y solicito me lo muestren para aprender. :-[
Mil gracias a todos, cierro el tema... ;D
PD: aún así, si alguien tiene una forma diferente de implementar "árboles" puede colocarla y revivir el tema para todos aprender... :)
Cita de: Texic en Febrero 22, 2013, 04:14:32 PM
Mh, si, se puede usar y para usarlo dentro de un script podría llegar a traer algún beneficio por el hecho de que los argumentos del script están limitados, pero hay que hacer mucho cálculo para pasar de binario a hexadecimal y viceversa. Además el código se puede llamar con facilidad fuera de un script y ponerle tantos argumentos como sea necesario, después de todo sería una sola línea de código
Nah, en realidad no es tanto calculo, hace tiempo se me ocurrió una manera sencilla. El mayor problema es que solo se permitirían 2 hijos por nodo por así decirlo y bueno los argumentos.
Cita de: ferhand en Febrero 22, 2013, 10:56:28 PM
Si hay algún tipo de datos binario en GML lo desconozco y solicito me lo muestren para aprender. :-[ [/color]
EJem todos?¿, quizás quisiste decir boleano.
Cita de: ferhand en Febrero 22, 2013, 10:56:28 PM
PD: aún así, si alguien tiene una forma diferente de implementar "árboles" puede colocarla y revivir el tema para todos aprender... :) [/color]
El tema me dio una idea, si logro algo lo posteo aquí.
Edit: ignoren mi idea, no funciono o parece ser algo mas complejo de lo que creí.
Cita de: brunoxzx en Febrero 23, 2013, 08:03:36 AM
Cita de: ferhand en Febrero 22, 2013, 10:56:28 PM
Si hay algún tipo de datos binario en GML lo desconozco y solicito me lo muestren para aprender. :-[ [/color]
EJem todos?¿, quizás quisiste decir boleano.
Saludos makero brunoxzx:
No, no quice decir "buleano", me refería a "binario" esos números que están formados con ceros y unos y la posición de cada dígito influye ne el valor que representan...
No logro encontrar nada en GM para implementarlos y he tenido que utilizar una cadena de texto para eso. Por lo que se vuelve más costoso en cuanto a memoria pues cada "caracter" pesa entre uno y dos megas.
Cita de: ferhand en Febrero 27, 2013, 07:36:30 PM
Saludos makero brunoxzx:
No logro encontrar nada en GM para implementarlos y he tenido que utilizar una cadena de texto para eso. Por lo que se vuelve más costoso en cuanto a memoria pues cada "caracter" pesa entre uno y dos megas.
1 y 2 megas? no se a que te refieras con megas(mega bytes?) pero cada carácter pesa un byte osea 8 bits osea un numero entre 0 y 255, o al menos eso es en la codificación ascii, creo que en unicode cada carácter es de 2 bytes no estoy seguro de cual use gm.
Cita de: ferhand en Febrero 27, 2013, 07:36:30 PM
Saludos makero brunoxzx:
No, no quice decir "buleano", me refería a "binario" esos números que están formados con ceros y unos y la posición de cada dígito influye ne el valor que representan...
Uhm, es que en realidad todos los números están en binario al igual que cualquier dato en una computadora lo está.
Por ejemplo: tu computadora ve un diez en decimal como un 1010 (que es 10 en binario), bueno en realidad la computadora le pone un montón de ceros atrás para que se complete el numero de bits que mide la variable, por ejemplo una variable de 16 bits (o 2 bytes) sin signo representa el numero 10 de esté modo 0000 0000 0000 1010. Creo que las variables de gm son de 64 bits.
Bueno ahora para manejar los bits de un numero se usan los operadores a nivel de bits (http://es.wikipedia.org/wiki/Operador_a_nivel_de_bits) usándolos puedes modificar los bits de un numero. Por ejemplo las funciones de desplazamiento a la derecha(>>) e izquieda(<<) mueven los bits de un numero un determinado numero de posiciones a la dirección indicada.
(5 << 3) // moverá los bits de 5 en tres posiciones a la izquierda.
//5=0101: (0101 << 3) = 0101000 = 40.
//ahora lo mismo pero al revez.
(40 >> 3) // moverá los bits de 40 en tres posiciones a la derecha.
//40=0101000: (0101000 >> 3) = 0000101 = 5.
.
Ahora, lo que tu quieres quizás sea usar algo como:
[gml]
var a;
a=bin(0, 0, 1, 1) * bin(0, 1, 0, 0);
//que es igual a 7 * 4 = 28[/gml]
ok, puedes construir una función para hacerlo. nota es para gm8.1 o superior ya que otras versiones no tienen la maravilla de usar argumentos como arrays lo cual es genial!.
[gml]
//Ejemplo de uso bin(1, 0, 1, 1);
var n;
n=0;
for(i=1; i<=argument_count; i+=1){
n = n | (argument[argument_count-i] << (i-1));
}
return(n);
[/gml]
ese sería un script, para hacer las conversaciones. No le veo mucha utilidad, pero quizás la tenga. Ademas solo acepta 16 argumentos osea que el numero más grande que puedes hacer es el 65535.
También se puede hacer un script que haga lo contrario, es decir que te devuelva el binario de un numero en decimal. El problema sería como devolver el numero, quizás una lista con ceros y unos o un string. Aunque le veo más utilidad al string por que ese puedes dibujarlo (de hecho no le veo utilidad a una función como está mas que para dibujar el resultado en binario), de esté modo podrías hacer algo como esto.
[gml]
var a;
a=bin(0, 0, 1, 1) * bin(0, 1, 0, 0);
//que es igual a 7 * 4 = 28 = 11100
show_message( bin_get( a ) ); // debería mostrar 11100[/gml]
Ahora, lo que tu quieres quizás sea usar algo como:
[gml]
var a;
a=bin(0, 0, 1, 1) * bin(0, 1, 0, 0);
//que es igual a 7 * 4 = 28[/gml]
¿Mmm... de dónde sale el 7?
Cita de: brunoxzx en Febrero 28, 2013, 08:31:26 AM
Cita de: ferhand en Febrero 27, 2013, 07:36:30 PM
Saludos makero brunoxzx:
No logro encontrar nada en GM para implementarlos y he tenido que utilizar una cadena de texto para eso. Por lo que se vuelve más costoso en cuanto a memoria pues cada "caracter" pesa entre uno y dos megas.
1 y 2 megas? no se a que te refieras con megas(mega bytes?) pero cada carácter pesa un byte osea 8 bits osea un numero entre 0 y 255, o al menos eso es en la codificación ascii, creo que en unicode cada carácter es de 2 bytes no estoy seguro de cual use gm.
Disculpa makero brunoxzx:
Quise decir Bytes y no Mega Bytes, gracias por aclararlo. :-[
Al tener que utilizar "strings" para representar un número en binario el costo en memoria RAM es de uno a dos bytes por caracter. 8)
Muy costoso. :-[
Cita de: penumbra en Febrero 28, 2013, 10:45:06 AM
Ahora, lo que tu quieres quizás sea usar algo como:
[gml]
var a;
a=bin(0, 0, 1, 1) * bin(0, 1, 0, 0);
//que es igual a 7 * 4 = 28[/gml]
¿Mmm... de dónde sale el 7?
El makero penumbra tiene razón... ¿Dónde está el siete (7)? XD
Yo veo un tres (3)... :-[
Es una lástima que no tenga el GM8.1 para probar esas funciones nuevas...
Lucen muy interesantes. ;D
Cita de: ferhand en Febrero 28, 2013, 08:35:46 PM
Cita de: penumbra en Febrero 28, 2013, 10:45:06 AM
Ahora, lo que tu quieres quizás sea usar algo como:
[gml]
var a;
a=bin(0, 0, 1, 1) * bin(0, 1, 0, 0);
//que es igual a 7 * 4 = 28[/gml]
¿Mmm... de dónde sale el 7?
El makero penumbra tiene razón... ¿Dónde está el siete (7)? XD
Yo veo un tres (3)... :-[
Ah, perdón el sueño no me dejaba ver correctamente XD quise decir bin(1, 1, 1) (
a decir verdad sigo viendo un 3 :P), de hecho tampoco es necesario poner los ceros a la izquierda no se por que los puse.
Sobre lo de los códigos, estoy a punto de morir de sueño si gustas mañana los adapto a gm8, aunque en gm8 seguro que serán mas grandes y feos los códigos.
Ahora un chite para que te rias un poco, cuando lei de el titulo del post, lo primero que pense fue.
- Y por que Fer... No usa mejor sprites o modelos si son mas practicos. jajajaja
Cita de: elviskelley en Marzo 02, 2013, 01:51:43 AM
Ahora un chite para que te rias un poco, cuando lei de el titulo del post, lo primero que pense fue.
- Y por que Fer... No usa mejor sprites o modelos si son mas practicos. jajajaja
Hacer un generador de arboles aleatorios estilo Minecraft estaria bueno, ahora que diste la idea :P
Sí, yo al leer el titulo también me imagine algo como esto (http://www.youtube.com/watch?v=98HAIwJRxyU). Pero de igual modo también resulto ser algo interesante.
Hice la adaptación del script a gm8 y se ve como algo en extremo lento y horrible ademas de que necesitas especificar el numero de argumentos.
[gml]
//Se tiene que especificar el numero de argumentos...
//ej bin(6, 1, 0, 1, 0, 1, 0) = 42;
var n;
n=0;
n= n | (argument1 << (argument0-1) );
if argument0 < 2 return (n);
n= n | (argument2 << (argument0-2) );
if argument0 < 3 return (n);
n= n | (argument3 << (argument0-3) );
if argument0 < 4 return (n);
n= n | (argument4 << (argument0-4) );
if argument0 < 5 return (n);
n= n | (argument5 << (argument0-5) );
if argument0 < 6 return (n);
n= n | (argument6 << (argument0-6) );
if argument0 < 7 return (n);
n= n | (argument7 << (argument0-7) );
if argument0 < 8 return (n);
n= n | (argument8 << (argument0-8) );
if argument0 < 9 return (n);
n= n | (argument9 << (argument0-9) );
if argument0 < 10 return (n);
n= n | (argument10 << (argument0-10) );
if argument0 < 11 return (n);
n= n | (argument11 << (argument0-11) );
if argument0 < 12 return (n);
n= n | (argument12 << (argument0-12) );
if argument0 < 13 return (n);
n= n | (argument13 << (argument0-13) );
if argument0 < 14 return (n);
n= n | (argument14 << (argument0-14) );
if argument0 < 15 return (n);
n= n | (argument15 << (argument0-15) );
return(n);
[/gml]
Lo vez! es enorme, quizás lo mejor y más rápido sea limitar el numero de argumentos, por ejemplo a 4:
[gml]
return( (argument0 << 3 ) + (argument1 << 2 ) + (argument2 << 1 ) + argument3 );
//puedes reemplazar el "+" con un "|", pero no se que sea más rápido.
[/gml]
mucho más bonito, pensándolo bien quizás sea mejor así, aunque tienes que reyenar con ceros el resto,
bin(0, 0, 0, 1) está bien pero NO bin(1) ni bin(0, 1).
El script para transformar un numero en decimal a uno en binario y devolverlo como string podria ser.
[gml]
//get_bit(255, 31);
//aunque para 255 basta con 8 bits.
//get_bit(255, 8);
//argument0 numero
//argument1 cuantos bits se checan (no recomiendo usar más de 31(mas el 0 son 32) ).
str="";
for(i=argument1; i>=0; i-=1){
if ( (argument0 >> i) & 1 ) begin str=str+"1" end;
else begin str=str+"0" end;
}
return(str);
[/gml]
También hice estas dos para obtener el bit que tiene un numero en la posición indicada.
[gml]//argument0 numero.
//argument1 posicion.
return( (argument0>>argument1) & 1 );[/gml]
y esté para cambiar un bit de un numero en la posicion indicada a 1, quizás sea mejor uno para invertirlo.
[gml]
//argument0 numero;
//argument1 posicion;
return( argument0 | (1 << argument1) );
[/gml]