Generarción De Mapas Tipo Worms

[Loover]

 Je, pues si te animas tu antes adelante, porque yo lo mismo no tengo tiempo hasta dentro de 2 meses, que estoy ahora con mil cosas. Pero mira, la idea, que es lo importante y lo que me interesaba por ahora, ya la tengo :)

Gracias de nuevo.

[senior wapo]

 Coincido con Pogacha en la parte de asignar la textura pero no en la de generación de "bordes".

Su algoritmo es de fuerza bruta y requiere operaciones de CPU por cada pixel y uso de bloques de memoria (ancho*alto). A medida que aumentas la resolución y dimensiones, se hace más lento. Ojo, es válido, pero yo propongo esto:

Yo haria una rasterización vertical (conversión a scanlines) de los polígonos aprovechando que los vértices ya los tienes ordenados en el sentido de las agujas del reloj. El algoritmo es similar al de render por software de poligonos, solo procesas los bordes, no todos los pixeles.

Asumo 2 cosas:
1. Vertices ordenados en el sentido de las agujas del reloj
2. Las aristas no se cruzan, no es un polígono degenerado.
3. El polígono esta cerrado, ultimo vértice está conectado con el primero.

Algoritmo para cada poligono:
1. Preparas un span buffer (s-buffer) por cada columa de pantalla. sbuffer[ancho_pantalla]. Lo inicializas vacío.
2. Selecciono vertice con la coordenada Y más elevada (importante).
Para todo vertice  del poligono:
3. Calculo deltaX respecto a siguiente vertice (vertices_x[2]-vertices_x[1]).
4. Si deltaX>0 es un borde superior (pasto/hierba), si es <0 es inferior (fin roca, debajo hay aire) y si es 0, es el mismo tipo que el segmento anterior.
5. Interpolar la coordenada Y a lo largo de X e insertar en el sbuffer

• (ordenado, una simple lista enlazada vale, que habrá pocos scanlines por cada columna, normalmente 1 o 2).
  5. volver a .3 mientras quedan segmentos.
  
  Ahora tienes para cada columna de pantalla (X) una lista de posiciones Y donde empiezan y acaban los pixeles del terreno, primer valor es un inicio, siguiente un final, siguiente otro inicio, etc...
  
  
  Los dibujas como ha dicho pogacha.
  
  Complejidad del algoritmo: lineal, O(ancho_mapa+numero_vertices) en lugar de O(ancho_mapa*alto_mapa), y uso de memoria muy inferior. Además no necesitas calcular primero la mascara de bits.

[senior wapo]

 Aclaro lo de deltaX=0, consideras que el segemento es del mismo tipo que el anterior de cara a texturar bordes (lo guardas aparte como caso especial si quieres borde por todo el contorno) , pero no insertas sus bordes en el sbuffer.

Como regla general puedes simplemente ignorar los segmentos totalmente verticales si quieres.

[Loover]

 Bueno, me da vueltas la cabeza pero despues de 3 horas programando y preparando grafiquillos ya tengo un resultado más o menos decente. Faltan por pulir detalles y tal, pero bueno.

La verdad, es que el uso de la libreria gráfica que tengo (a ver si algún día de estos la cuelgo en algún lao) me ha ayudado mucho en cuanto a cosas de bajo nivel. Porque ya tenía hecha toda la parte de crear una imagen procedural, cortar y pegar bloques, sets, gets, cargar y salvar a disco, transformar la imagen en una textura cortando los bloques automáticamente, etc.

El mapa se genera muy rápido, no he mirado cuanto, pero menos de un segundo.

Senior Wapo, gracias por la recomendación, pero creo que sobra velocidad, dado que el mapa se va a generar en tiempo de carga en el editor.

Gracias Pogacha de nuevo por los consejos, el código no lo miré porque suelo liarme con el código ajeno, pero las ideas fueron muy acertadas y ataste todos los cabos. Y gracias también a ti Matriax por prestarme los gráficos.

[Sacrifai]

  (genial)  

[Helius]

 Eyyy que bueno  (ole)  

[Loover]

 Mas imágenes, un poco tochas (sorry).



===>

[Pogacha]

 Quedo mejor de lo que crei.
Pero noto un error.
Se ve claro en la letra L de lover, el pasto tiene que llegar a la mitad (o un porcentaje arbitrario, quizas 2/3 sea mas adecuado) del alto de la franja de tierra y aqui crece hasta el fondo.

Sobre lo que dice el senior Wapo es todo cierto, mi algortimo hace varias pasadas por pixel y si usas span buffers la redundancia sera 0.

En realidad unos de los tipos del team 17 (que hacen el worms) paso por aca y dejo spam de sus sitio.
http://www.sortgames.com

Saludos

[Sacrifai]

 Deberías poner el source, mas de uno te o agradecería  (uoh)  .

[Pogacha]

 @Offtopic
Sacrifai:
Que es ese numero que solo 1/20 programador conoce?

Las siglas tag del formato PNG ?

[senior wapo]

 Mola como ha quedado  (ole)  

[Loover]

 Subsanado el error, gracias Pogacha.

Bueno, mi código no es muy elegante. Además necesitarás mi libreria gráfica (LooverLib, xD) para compilarlo. Si quieres puedo empaquetarla y subilar también, aunque la documentación está al 95%. Aunque las funciones que he usado si están documentadas.

Bueno, ahí va el código, que se podrá mejorar mil veces (por ejemplo colocar el cesped y la arena es prácticamente el mismo procedimiento y se podría hacer en una sola función cambiando parámetros) pero me vale así, xD:

Código [Seleccionar] Expand

/*
==================
Genera un mapa del juego a partir de un mapa de bits en blanco y negro
==================
*/
void GenerateMap (LOV_Image *pSource,
    LOV_Image *pTexBase,
    LOV_Image *pTexUp,
    LOV_Image *pTexDown)
{
int x, y, k, alt;
int mCes = 0;

// Colocamos la textura base
for (x = 0; x < pSource->GetWidth(); x ++)
{
 for (y = 0; y < pSource->GetHeight(); y ++)
 {
  byte R1, G1, B1, A1;
  mGame.ImageManager->GetPixel (pSource, x, y, &R1, &G1, &B1, &A1);

  if (!R1)
  {
   mGame.ImageManager->GetPixel (pTexBase, x, y, &R1, &G1, &B1, &A1);
   mGame.ImageManager->PutPixel (pSource, x, y, R1, G1, B1, A1);
  }
 }
}

// Colocamos la "arena" (abajo)
for (x = 0; x < pSource->GetWidth(); x ++)
{
 for (y = 0; y < pSource->GetHeight(); y ++)
 {
  byte R1, G1, B1, A1;
  mGame.ImageManager->GetPixel (pSource, x, y, &R1, &G1, &B1, &A1);

  // Si es tierra
  if (R1 != 255 || G1 != 255 || B1 != 255)
  {
   mGame.ImageManager->GetPixel (pSource, x, y + 1, &R1, &G1, &B1, &A1);
   
   // Si es aire el pixel de encima dibujamos "arena"
   if (R1 == 255 && G1 == 255 && B1 == 255)
   {
    // Miramos la altura
    alt = 0;
    R1 = 0;
    while (R1 != 255 || G1 != 255 || B1 != 255)
    {
     mGame.ImageManager->GetPixel (pSource, x, y - alt, &R1, &G1, &B1, &A1);
     alt++;    
    }

    int mUntil;

    if (alt < pTexDown->GetHeight())
     mUntil = alt / 2;
    else
     mUntil = pTexDown->GetHeight();

    // Dibujamos una tira de cesped hacia abajo
    for (k = 0; k < mUntil; k++)
    {
     if (mCes > pTexDown->GetWidth () - 1) mCes = 0;
     mGame.ImageManager->GetPixel (pTexDown, mCes, k, &R1, &G1, &B1, &A1);

     if (R1 != 255 && G1 != 0 && B1 != 255)
      mGame.ImageManager->PutPixel (pSource, x, y - k, R1, G1, B1, 0);
    }
    mCes++;
   }
  }
 }
}


// Colocamos el "cesped"
for (x = 0; x < pSource->GetWidth(); x ++)
{
 for (y = 0; y < pSource->GetHeight(); y ++)
 {
  byte R1, G1, B1, A1;
  mGame.ImageManager->GetPixel (pSource, x, y, &R1, &G1, &B1, &A1);

  // Si es tierra
  if (R1 != 255 || G1 != 255 || B1 != 255)
  {
   mGame.ImageManager->GetPixel (pSource, x, y - 1, &R1, &G1, &B1, &A1);
   
   // Si es aire el pixel de encima dibujamos "cesped"
   if (R1 == 255 && G1 == 255 && B1 == 255)
   {
    // Miramos la altura
    alt = 0;
    R1 = 0;
    while (R1 != 255 || G1 != 255 || B1 != 255)
    {
     mGame.ImageManager->GetPixel (pSource, x, y + alt, &R1, &G1, &B1, &A1);
     alt++;    
    }

    int mUntil;

    if (alt / 2 < pTexUp->GetHeight())
     mUntil = alt / 1.4;
    else
     mUntil = pTexUp->GetHeight();

    if (mUntil > pTexUp->GetHeight()) mUntil = pTexUp->GetHeight();

    // Dibujamos una tira de cesped hacia abajo
    for (k = 0; k < mUntil; k++)
    {
     if (mCes > pTexUp->GetWidth () - 1) mCes = 0;
     mGame.ImageManager->GetPixel (pTexUp, mCes, k, &R1, &G1, &B1, &A1);

     if (R1 != 255 && G1 != 0 && B1 != 255)
      mGame.ImageManager->PutPixel (pSource, x, y + k, R1, G1, B1, 0);
    }
    mCes++;
   }
  }
 }
}

mGame.ImageManager->Save (pSource, "temporal.png");
}

[ethernet]

 Hola, muy interesante el post, pero viendo las imágenes hay ciertos puntos de la roca donde hay discontinuidad (se nota mucho la linea de cambio). Está hecho adrede imitanto un estrato (minipunto) ? Por lo demás me parece un resultado muy bueno.

saludos

[TheAzazel]

 Esta bastante curioso  (ole)  

[Loover]

 La roca esta mal porque la textura la recorte yo mal ayer aprisa y corriendo :) Con una textura bien escogida, que al pegarla una detrás de otra no se vea el corte se vería bien. Es decir, no es fallo del algoritmo. Matriax a ver si me pasas unas buenas texturas :)