Duda sobre como programar el juego Timbiriche

[mifiar]

hola, tengo una duda sobre la forma de programar este juego, por si no lo conocen, consiste en una especie de cuadrícula con muchos puntos, los cuales se tienen que unir con lineas, con el objetivo de formar cuadros. Espero me haya dado a entender; estaba pensando la manera de como hacerlo, tengo la idea de como hacer algunas cosas, pero lo que no puedo siquiera imaginar es como identificar durante el juego cuando se ha formado un cuadro (y si quieren aportar algunas otras ideas que creen me pudieran servir bienvenidas sean ), por lo que acudo a ustedes a ver si alguien ha hecho algo parecido y pudiera orientarme. Tambien quiero saber si delphi es la herramienta idónea para hacer este tipo de cosas; espero sus respuestas y gracias de antemano .

[JXJ]

idonea. yo creo que si...

este tipo de cosas de reconocer formas....
me han dicho que tienen que ver con la programacion de
redes neuronales.

en torry hay unos componentes que es para reconocer
texto, y pasarlo a texto. desde una imagen escaneada
de un libro.

eso puede servir, como idea orientativa.

[[Delphius]]

No se si es función únicamente de los moderadores, pero bueno: ¡Bienvenido a Clubdelphi!

Empezado por mifiar

estaba pensando la manera de como hacerlo, tengo la idea de como hacer algunas cosas

¿Serías tan amable, de indicarnos como estabas pensando resolverlo? Para un problema pueden existir miles de soluciones, sería conveniente que nos indiques la tuya para poder ofrecerte una ayuda más precisa.

[[Delphius]]

Empezado por JXJ

este tipo de cosas de reconocer formas....
me han dicho que tienen que ver con la programacion de
redes neuronales

¿Redes nueornales? Eso me huele complicado.... y creo que lo es, ¿que acaso no está relacionado con lo que es IA (Inteligencia Artificial)?
Debe haber algo más simple.

Por ejemplo yo estaba pensando en hacer un "tablero" con una estructura adecuada de nodos (con punteros, oviamente) donde cada nodo representa un punto de cada cuadrícula. NOTA: para que esto funcione, habría que identificar a cada nodo. Entonces, si se puede hacer algún procedimiento hipotético BuscarVecinos() y se pasa como parámetro dicho identificador que devuelva algún valor booleano que refleje si hay un rectángulo.

NOTA:
1. Habría que contemplar si el nodo en cuestión está ubicado en las esquinas.
2. Se entiende por nodo vecino a todo nodo que lo "rodee" al mismo. Claro está que un nodo tendrá entonces cuatro punteros.

Algo así:
nodo1 - nodo2 - nodo3
| | |
nodo4 - nodo5 - nodo6
| | |
nodo7 - nodo8 - nodo9

Cada línea representaría el enlace de los nodos.
Crearía una clase que hiciera lo siguiente:

Hasta el momento podría ser así:

Código Delphi [-]
procedure CrearTablero(Tamanno: integer);
// crea el tablero con una estructura de nodos
 
function BuscarVecinos(IDNodo: TIDNodo): boolean;
// buscar vecinos: si encuentra a los vecinos marcados 
//(hay una línea entre ellos) indica que se ha formado un cuadrado
 
// estructura de nodo
Nodo = ^TNodo;
TNodo = record
Marcado: boolean;
Vecino1,Vecino2,Vecino3,Vecino4: Nodo;
end;

No se si me explico.

[dec]

Hola,

Empezado por Delphius

No se si es función únicamente de los moderadores, pero bueno: ¡Bienvenido a Clubdelphi!

No solamente no es cuestión únicamente de los moderadores, pero, todo lo contrario, diría yo.

Recordarle a mifiar la guía de estilo y el buscador de estos Foros, pues que le serán seguro útiles.

La bienvenida ya se la diste tú Delphius, y, que sea enhorabuena.

[roman]

Vamos a ver, no creo que sea muy complicado. Como pienso las cosas lo primero que hay que hacer es separar la parte gráfica de la parte lógica.

Vería muy difícil que del sólo trazo gráfico Canvas.LineTo(X, Y) pudieras determinar si se cierra o no un cuadrado. Así que lo primero es pensar en cómo podemos representar el juego de manera lógica sin meternos para nada en lo gráfico. De hecho esto último es meramente secundario.

Piensa en el tablero del timbiriche como lo muestra esta figura donde numeras las filas de arriba hacia abajo y las columnas de izquierda a derecha.

Ahora piensa en una raya horizontal y en una raya vertical.

La raya horizontal queda determinada por dos parámetros (i, j), significando que es la raya en la fila i que va de la columna j a la j+1.

De la misma forma, la raya vertical requiere de dos parámetros (i, j), sólo que ahora significan que la raya está en la columna j y va de la fila i a la i+1.

Puedes entonces crear dos arreglos bidimensionales H y V de valores booleanos:

Código Delphi [-]
var
  H: array[0..m-1, 0..n-2] of Boolean;
  V: array[0..m-2, 0..n-1] of Boolean;

donde m es el número de filas y n el número de columnas. H te indicaría cuáles rayas horizontales están ya pintadas y V te diría cuáles rayas verticales ya lo están.

Resumiendo,

• si H[i, j] es true, significa que ya está pintada la raya en la fila i que va de la columna j a la j+1.
  
  
• si V[i,j] es true, significa que ya está pintada la raya en la columna j que va de la fila i a la i+1.

Con esto tendrías representado el estado del juego en todo momento, y éste terminará cuando todas las entradas de los dos arreglos sean true.

Ahora bien, cuando trazas una raya horizontal sólo hay dos cuadrados que pueden cerrarse, como se ve en esta figura y análogamente sucede con una raya vertical, como puedes ver aquí.

Así pues, al trazar la raya H[i, j] debes ver si las otras aristas del cuadrado de arriba o del de abajo ya están trazadas. Las tres rayas del cuadrado superior son

(a) H[i-1, j], V[i-1, j] y V[i-1, j+1]

mientras que las del cuadrado inferior son

(b) H[i+1, j], V[i, j] y V[i, j+1]

Entonces, al trazar la raya horizontal en la fila i que va de la columna j a la j+1 (la correspondiente a H[i, j]) debes verificar si las tres entradas de (a) son todas true o bien si todas las entradas de (b) son true.

Un análisis similar haces para cuando trazas la raya V[i, j]. En este caso tienes que considerar:

(c) V[i, j-1], H[i, j-1] y H[i+1, j-1]

(d) V[i, j+1], H[i, j] y H[i+1, j]

Claro que hay que considerar aparte los casos en que la raya se trace en un extremo de la retícula de puntos ya que en ese caso, la raya sólo puede estar cerrando a lo sumo un cuadrado.

Obvio que esto es apenas una parte de todo el juego. Cada vez que una raya cierre un cuadrado tendrías que ver si puede cerrarse otro más para desarrollar la cadena de cuadrados. Y ni qué decir que la parte más difícil- si quieres que la pc juegue contra el humano -será implementar la estrategia ganadora.

Desde luego no sé qué tan buena es esta representación del juego en cuanto a eficiencia, pero considerando que un tablero de timbiriche no puede ser demasiado grande, quizá no importe demasiado.

En cuanto a la parte gráfica, como ya te indicó David, buscando en los foros podrás encontrar varias referencias a cómo dibujar. De momento se me ocurre un PaintBox en cuyo evento OnPaint repasas los dos arreglos para saber qué rayas has de pintar.

postdata

Esto lo comencé a escribir antes de ver que ya Delphius había proporcionado una idea concreta. Analiza ambas para ver cuál te acomoda más. Puede ser que la de él sea más viable, no lo sé. El punto es que tomes la que facilite más la búsqueda del cuadrado.

// Saludos

[[Delphius]]

Empezado por roman

Esto lo comencé a escribir antes de ver que ya Delphius había proporcionado una idea concreta. Analiza ambas para ver cuál te acomoda más. Puede ser que la de él sea más viable, no lo sé. El punto es que tomes la que facilite más la búsqueda del cuadrado.

Empezado por Yo

Para un problema pueden existir miles de soluciones, sería conveniente que nos indiques la tuya para poder ofrecerte una ayuda más precisa.

Tal como lo dije antes, para un problema hay muchas soluciones.... Habría que ver como lo estaba pensando mifiar, lo ideal sería "ajustar" sus ideas más que ofrecerle alternativas.

PD: roman, al principio lo había pensado así pero al usar arrays limitaría demasiado el tamaño del tablero... me pareció oportuno trabajar con nodos (a pesar de que sería complicado) ya que podría crearse tableros de distintos tamaños. NOTA: Me llamó la atención de que tu tablero sea de (mxn), tengo entendido que el tablero debe ser de (nxn)

[roman]

Empezado por Delphius

NOTA: Me llamó la atención de que tu tablero sea de (mxn), tengo entendido que el tablero debe ser de (nxn)

Pues no sé si hay alguna regla oficial. En mis tiempos de escolar, hace muchas lunas, lo jugábamos en cualquier papel cuadriculado que tuviéramos a mano y el tamaño del "tablero" era proporcional a qué tan aburrida estaba la clase del profesor.

// Saludos

[[Lepe]]

Pues yo abogo porque un cuadrado esté formado por 2 lineas nada más .

La idea es que esas líneas son las que estarían al Norte y al Oeste del centro del cuadrado, y dos Vecinos, VecinoSur, VecinoEste.

Supongo que no se entiende, aqui va pintado un Timbiriche de 4 casillas Cada color representa un solo cuadrado.

 -  -
|1 |2
 -  -
|3 |4

Ya sé que queda Abierto por la derecha y por abajo, veamos la declaración en delphi:

Código Delphi [-]
type
Tcuadrado = class;

Tcuadrado = Class(Tobject)
public
   Norte: Boolean;
   Oeste:Boolean;
   VecinoSur:Tcuadrado;
   VecinoEste:Tcuadrado;
end;

Si VecinoSur es nil significa que ese lado corresponde con el borde inferior del Timbiriche.

Si VecinoEste es nil significa que ese lado corresponde con el borde Derecho del Timbiriche.

Para pintar el borde izquierdo del timbiriche, pondríamos a true el Oeste de ese cuadro.
Para pintar el borde superior del timbiriche, pondríamos a true el Norte de ese cuadro.

Para que se cierre un cuadrado comprobamos los siguientes elementos:
- Norte = True
- Oeste = True
- VecinoSur = nil ó bien que VecinoSur.Norte = True
- VecinoEste =nil ó bien que VecinoEste.Oeste = True

Personalmente lo veo conceptualmente más claro[...] una vez que se ha entendido el concepto

Quizás declararlo como TObject sea demasiado, quizás con punteros sería más eficiente, por claridad, lo pongo así.

PD: Desarrollar esta idea surge de las aportaciones de roman y Delphius, ya que tener claro qué cuadrado se va a pintar, y acceder a sus vecinos es bastante engorroso, quizás este híbrido pueda servir de ayuda.

saludos

[[Lepe]]

Bien pensado, hace falta:

Código Delphi [-]
type
Tcuadrado = class;

Tcuadrado = Class(Tobject)
public
   Norte: Boolean;
   Oeste:Boolean;

   VecinoSur:Tcuadrado;
   VecinoEste:Tcuadrado;
   VecinoNorte:Tcuadrado;
   VecinoOeste:Tcuadrado;
end;

Para poder navegar y propagar los cuadrados cerrados. Me refiero a cuando se cierra un cuadrado y se puede seguir cerrando otros cuadros más. Aquí se necesita tener las direcciones de los demás cuadrados y comprobar hacia donde se puede propagar el cierre de cuadros.

saludos

[[Héctor Randolph]]

Con respecto a la inteligencia artificial del juego de timbiriche, leí algunos artículos y en realidad no es nada sencillo programarlo; hay que meterse con árboles de búsqueda, heurísticas y lo propio de la inteligencia artificial, sin embargo encontré esta sencilla propuesta:

The computer player is to follow a very simple AI algorithm to determine which side should be selected.

1. If the fourth side of a box can be selected, select such a side. If multiple fourth sides exist, randomly select one of them.
2. If no fourth side exists and a first or second side of a box can be selected, select such a side. If multiple first or second sides exist, randomly select one of them.
3. If only the only choice is selecting the third side of a box, select such a side. If multiple third sides exist, randomly select one of them.

Por lo pronto les dejo un enlace bastante entretenido

Dot & Boxes

[mifiar]

Hola, gracias por sus respuestas, he estado revisando con detenimiento cada una de las ideas expuestas, pero no alcanzo a comprenderlas del todo ya que soy relativamente nuevo en esto, además de que se me dificulta algo , pero la lucha le hago , si pudieran explicarme las ideas aún mas detalladas se los agradecería . En lo que respecta a las ideas que tenía para realizar este programa se me atraviesa un inconveniente; les expongo la idea:

 pv:=0;
  ph:=0;
  
  
  	for a := 0 to 5 do
  	begin
  	  for b := 0 to 4 do
  	  begin
  		Imagenes[a,b]:=TShape.Create(Self);
  		Imagenes[a,b].Parent := Form1;
  		Imagenes[a,b].Left := ph+10;
  		Imagenes[a,b].Top := pv+10;
  		Imagenes[a,b].height := 7;
  		Imagenes[a,b].width := 7;
  		Imagenes[a,b].Shape := stCircle;
  		Imagenes[a,b].OnMouseDown:= CirclesMouseDown;
  		Imagenes[a,b].OnMouseMove:= CirclesMouseMove;
  		pv:=pv+50;
  		  if b=4 then
  		  begin
  		  pv:=0;
  		  end;
  	  end;
  	  ph:=ph+50;
  	end;

Es para crear la cuadrícula; lo que sucede es que no se como hacer referencia a un elemento en particular, dado que son creados en tiempo de ejecución. Tambien realicé un evento OnMouseDown y se lo asigné a cada uno de los puntos (o pequeños circulos) de la cuadrícula, con el objetivo de obtener la posicion que ocupan dentro de la forma, pero esa posicion la toma con relacion al objeto creado y no a la forma; conocen alguna manera de hacer que tome la posicion con respecto a la forma ? Se siguen aceptando sugerencias , gracias.

[[Lepe]]

En qué tienes dudas, y cual de las alternativas te gusta más, porque hay distintas formas de hacerlo en este mismo hilo.

Por cierto, siempre puedes hacer referencia a través de Imagenes[fila, columna].

Veo que estas intentando hacer el cuadriculado mediante TShapes, te aconsejo que busques algún componente ya hecho. En mi caso he usado el TLMDSimplePanel de las libreria LMDTOOLS (direccion en google), son gratis, y permite dibujar un panel, poniendo las lineas por separado, es decir, pinto los bordes de blanco, y cuando se hace clic en un lateral, pinto ese lado nada más de color negro. Pintar es simplemente decirle al panel BorderSides := BorderSides + bsLeft para añadir el borde izquierdo.

Si tienes que implementarlo todo a mano.... mi más sincero pésame

saludos

[roman]

Empezado por Lepe

Si tienes que implementarlo todo a mano.... mi más sincero pésame

No tanto. Yo lo haría dibujando directamente en un PaintBox. No es tan complicado ya que sólo son segmentos horizontales y verticales y si acaso, rellenar los cuadros ya cerrados del color de cada jugador. Al final de cuentas resulta más fácil que andar colocando shapes aquí y allá, además de que sería más lento.

Yo también preguntaría cuáles son las dudas específicas y de qué opción le interesa. Creo que nosostros ya hicimos nuestro esfuerzo. Ahora le toca a él.

// Saludos

[mifiar]

Hola, si me pudieran explicar Lepe y Roman sus metodos un poco mas a fondo ademas de como asociar la parte gráfica con el codigo que me proponen si no es mucha molestia.

En lo de hacer referencia a los objetos lo que pasa que al momento de seleccionarlo, ya en tiempo de ejecución, no encuentro la manera de saber cual de los componentes creados, los circulos en este caso, estoy seleccionando. Si me pudieran explicar tambien lo como hacer que las coordenadas de los pixeles me las de de acuerdo a la posicion que estan en la forma y no con respecto al objeto creado . Gracias .

[[Lepe]]

En lo que me toca, ya he dicho que uso un panel al que se le pueden poner las lineas independientes, y la parte lógica (la clase TCuadro) informa mediante un evento cuando se cierra un cuadro a la parte gráfica. En ese evento es cuando repinto el fondo de un color si está cerrado o no.

El dibujar una linea, se hace en la parte gráfica, al hacer clic cerca de los bordes , detecto qué borde es y directamente lo pinto, despues informo a TCuadro, y este propaga un mensaje por sus vecinos para ver si se deben cerrar o no. Básicamente es como una onda expansiva, en cuanto a eficiencia no es nada bueno, pero son las primeras pruebas que he realizado.

Mi Tcuadro queda así (aunque no descarto cambios):

Código Delphi [-]
type
  TCuadro = class;
  TNotifyText = procedure (Sender:Tcuadro; Cerrado:boolean) of object;
  TLineas = (lNorte, lSur,lEste, lOeste);
  SetOflineas = set of TLineas;

  TCuadro = Class(TObject)
  protected
    Semaforo:Boolean;
  public
    constructor Create();
  published
    property Oeste:Boolean read FOeste Write SetOeste default False;
    property Norte:Boolean read FNorte Write SetNorte default False;
    property Sur:Boolean read GetSur;
    property Este:Boolean read GetEste;

    property VecinoNorte :Tcuadro read VNorte Write SetVNorte;
    property VecinoSur   :Tcuadro read VSur Write SetVSur;
    property VecinoOeste :Tcuadro read VOeste Write SetVOeste;
    property VecinoEste  :TCuadro read VEste Write SetVEste;

    property Cerrado:Boolean read GetCerrado Write SetCerrado;
    property Lineas:SetOflineas read GetLineas;
    property NLineas :Integer read GetNLineas;
    property Contro:TComponent read Fcontrol Write Fcontrol;

    property OnCierre:TNotifyText read FOncierre Write FOnCierre;
    procedure CompruebaCierre;
  end;

Sur y Este, lo que hacen es ver si su vecino tiene el Oeste marcado, o si es el borde inferior/derecho del Timbiriche

Al inicio, VecinoXXXXX será nil, y al crear la cuadrícula es cuando se unen unos con otros.

Lineas y NLineas, son propiedades de ayuda, para ver qué lineas tiene pintada un cuadro determinado.

Contro es el control de la interfaz gráfica al que está asociado, Mi Panel. Una vez creado el Panel en tiempo de ejecución, y la clase, los asocio mediante esa propiedad, igual que se hace con un TAction.

Por último, tenemos el evento de cierre, que me indica el cuadro que se ha cerrado.

[JXJ]

creo algo más facil.

como el juego en java que puso hectorrandolf

se pueden usar botones y aprovechar sus eventos on click
para activarlos.
y sus propiedades de colores.
y colocarlos sobre una cuadricula dibujada,. en un canvas
solo a modo de como se van a colocar los botones.
y unos botones que la haran como sensores.

Creo se puede usar eso de detecion de colisiones.
si el boton sensor. detecta. que se colisiona con el boton
largo. en el que se ha hecho clik. se pone una bandera.
.. de que se ha puesto. una linea a la derecha o a la izquierda
arriba o abajo. .. lo de IA. como en el juego java.
es otra cosa. que no visualizo bien.