¿Unidades de desove en un mundo hecho por el ruido de Perlin?

Hay algunos problemas que he encontrado en mi juego basado en el ruido Perlin. Echa un vistazo a la captura de pantalla adjunta a continuación.

Las áreas blancas que ves son paredes, y las áreas negras son transitables. El triángulo en el medio es el jugador.

Implementé la física en este juego dibujándola en una textura (píxeles blancos o negros) y luego obteniéndola de la CPU.

Sin embargo, ahora estoy con un problema diferente a la mano. Quiero que las unidades (o escalofríos, como los llames) se generen constantemente, en el borde de la pantalla. El punto aquí es que en el juego final, habrá una "niebla de guerra" que no permitirá que el jugador vea tan lejos de todos modos.

Pensé que podría escanear los píxeles en el borde de la pantalla y ver si su textura física es negra, y luego generar cosas al azar allí. Sin embargo, si echas un segundo vistazo a la captura de pantalla, hay (en la esquina superior izquierda) un ejemplo de dónde no quisiera que aparezcan los pelos de punta (ya que no podrían alcanzar al jugador desde allí) .

¿Es posible que la GPU determine de alguna manera estos puntos de generación para mí, o de alguna otra manera? Pensé en hacer vectores entre el punto propuesto en el borde de la pantalla y el reproductor, y luego seguirlo cada 10 vóxeles, y ver si una pared choca, antes de generar una unidad allí.

Sin embargo, la solución propuesta anteriormente puede ser demasiado intensiva de la CPU.

¿Alguna sugerencia sobre este asunto?

Nota 1 Para las unidades engendradas, no quiero utilizar ninguna forma de búsqueda de caminos para evitar colisiones en la pared mientras estas unidades corren hacia el jugador. Por lo tanto, las unidades deben aparecer en el borde de la pantalla, en un lugar donde caminar en línea recta hacia el jugador no chocaría con ninguna pared.

Hay un algoritmo bastante útil para este trabajo, mucho más eficiente que el algoritmo de inundación en esta situación (su complejidad es el tiempo de ejecución es proporcional al tamaño del límite en lugar del área inundada): es el algoritmo de cuadrados de marcha. El concepto es simple: comience desde la ubicación de los jugadores (punto medio de la pantalla), elija una dirección y camine hasta encontrar una pared. Cuando chocas con la pared, comienzas el algoritmo: eliges una orientación (arriba o abajo) y comienzas a marchar sobre el límite de esta área, resaltando los píxeles. Esto le da el límite interno para el área permitida. Luego, simplemente verifica si los puntos candidatos para las unidades de desove se encuentran en este límite.

Este es el principio que debe seguir para ejecutar el límite:

http://en.wikipedia.org/wiki/File:Marchsquares.png (meh todavía no puedo publicar fotos)

Descripción de Wikipedia (aunque tiene mucha más complejidad porque se usa con otras aplicaciones en mente):

http://en.wikipedia.org/wiki/Marching_squares

Haz un relleno de inundación desde la posición del jugador; cada área "inundada" es entonces un área de juego válida, y todas las demás son paredes.

EDITAR: En cuanto al requisito adicional "accesible en línea recta", tenga en cuenta que en un espacio discreto , debe definir esto un poco más. Por ejemplo, todos los caminos anteriores podrían ser una "línea recta" válida en dicho entorno, y he visto que todos se usan en un juego en algún momento u otro:

En particular, la mayoría de ellos no son conmutativos , lo que significa que solo puede llegar a B desde A en una "línea recta" no significa que también puede llegar a A desde B; tampoco es lo contrario necesariamente cierto.

Además, está la cuestión de cómo maneja el movimiento diagonal si uno o ambos puntos "laterales" están bloqueados.

¿Qué tal si dejamos que ocurran los engendros? No veo ningún problema en particular en eso.

Si es importante que marque solo puntos con una línea recta válida para el jugador, puede usar un algoritmo como el siguiente (es un código c ++), consume más de lo normal en el relleno. puede haber algunos errores menores (me alegraría si alguien los corrige) ya que no probé el código yo mismo, pero se dará cuenta de la idea.

void straightlineFill(Point startPoint, Texture target)
{
    queue<Point> pointQueue;
    for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(startPoint.x + dx, startPoint.y + dy));
    while (!pointQueue.empty())
    {
        point front = pointQueue.front();
        pointQueue.pop();
        if (target.pixelAt(front) == COLOR_SPAWNABLE||
            target.pixelAt(front) == COLOR_WALL||
            target.pixelAt(front) == COLOR_NOT_SPAWNABLE)
                continue;
        taraget.setPixelAt(front, colorFilled); 
        for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(front.x + dx, front.y + dy));
        // up until now was the normal floodfill code
        // and here is the part that will do the real straight line checking

        // lineDX & lineDY will keep how much the line we are checking is skewed
        int lineDX = front.x - startPoint.x;
        int lineDY = front.y - startPoint.y;

        // step will show us how much we have to travel to reach each point of line
        point step;
        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDX < 0)
                step = point(-1,0);
            if (lineDX == 0)
                if (lineDY < 0)
                    step = point(0,-1);
                else
                    step = point(0,1);
            if (lineDX > 0)
                step = point(1,0);
        }

        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDY < 0)
                step = point(0,-1);
            if (lineDY == 0)
                if (lineDX < 0)
                    step = point(-1,0);
                else
                    step = point(1,0);
            if (lineDY > 0)
                step = point(0,1);
        }

        // moved will keep how much we have traveled so far, it's just some value that will speed up calculations and doesn't have any mathematical value
        point moved = 0;

        // spawnable will keep if the current pixel is a valid spawnpaint

        bool spawnable = true;

        // now we will travel on the straight line from player position to the edges of the map and check if whole line is valid spawn points or not.

        while (target.isInside(front))
        {
            front = front + step;
            moved = moved + point(step.x * lineDX, step.y * lineDY);
            if (step.x != 0 && moved.x < moved.y)
            {
                moved.x = moved.x - lineDY * sign(lineDY);
                front.y = front.y + sign(lineDY);
            }
            if (step.y != 0 && moved.y < moved.x)
            {
                moved.y = moved.y - lineDX * sign(lineDX);
                front.x = front.x + sign(lineDX);
            }

            if (target.getPixelAt(front) == COLOR_WALL)
                spawnable = false;

            if (spawnable)
            {
                target.setPixelAt(front,COLOR_SPAWNABLE);
                for (int dx = -1;dx <=1;dx ++)
                    for(int dy = -1;dy <=1;dy++)
                        if(dx != 0 && dy != 0)
                            pointQueue.push(point(front.x + dx, front.y + dy));             
            }
            else
            {
                target.setPixelAt(front,COLOR_NOT_SPAWNABLE);
            }
        }
    }
}

Puede llenar el mapa con colores que representen áreas convexas ..., de esta manera puede generar su unidad si se encuentra en la misma área. O puede buscar más fácilmente áreas accesibles.

Estos son datos estáticos para que pueda calcularlos previamente.

tuvo que llenar los puntos de búsqueda de imágenes donde hay un cambio de convave a convex, visualmente parece fácil de encontrar, tiene dos situaciones:

1. Horizontal: donde cambia de naranja a azul.
2. Vertical: donde el rojo cambia a verde y naranja.

Aquí hay algo que realmente utilicé en mi propio juego (mundo generado en ruido 2D simplex, casi exactamente como el tuyo): Rays. Comience en el jugador, determine una orientación (aleatoria si lo desea), y siga esa línea hasta que golpee algo (borde de la pantalla O asteroide). Si golpeas el borde de la pantalla (y no un asteroide / burbuja blanca), entonces sabes que hay una línea recta y abierta desde el borde de la pantalla hasta el jugador. Luego engendra un monstruo en el punto donde golpeas. Si golpeas un asteroide, vuelve a hacer la prueba.

Otra solución (no GPU) que puede usar es la búsqueda de rutas. Antes de dibujar el mapa, busque la ruta desde cada punto de generación potencial en cada borde del mapa y vea si hay una ruta hacia el centro. Una * búsqueda de ruta está bastante bien en costo / rendimiento, pero puede hacer esto antes de que comience el juego si eso es un problema.

Cualquier punto de generación que no tenga una ruta puede colocarse en una lista de exclusión; o viceversa (cualquier punto con una ruta se puede poner en una lista de inclusión).