Comunidad Game Maker

   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)

  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í.