Simulando "línea de visión" con obstáculos en la cuadrícula 2D?

10

Se topó con un problema interesante. Necesito descubrir cómo simular la línea de visión, lo suficientemente simple, solo en una cuadrícula 2D con obstáculos. O una celda de cuadrícula es visible o no lo es.

Puedo hacer que algo realmente rudimentario funcione, como esparcir n espacios desde el jugador o bloquear la propagación horizontal cuando se detecta un obstáculo adyacente, pero no puedo permitirme vivir con él. Muchas otras aplicaciones están utilizando métodos más sofisticados que inclinan la línea de visión alrededor de las esquinas, etc., y quiero estar a la altura.

Hasta ahora DCSS ha sido mi fuente de inspiración cuando estoy perplejo, espero obtener algo parecido a lo que tienen: http://crawl.sz.org/ .

Cualquier idea sería apreciada, ¡gracias por la ayuda!

(Perdona si esto es vergonzosamente novato: solo comencé el desarrollo del juego hace unas semanas, tratando de ponerme al día).

CodeMoose
fuente
2
Cuando dices "inclina la línea de visión alrededor de las esquinas", ¿qué quieres decir exactamente?
Djentleman
Lo mejor que puedo decir es ver un juego en crawl.sz.org. Como ejemplo, cuando el jugador está parado debajo de una pared horizontal de 5 fichas de ancho, la línea de visión se rompe por encima del plano horizontal de esa pared, pero no de manera poco realista más allá de ella. Lo mejor que he podido aproximar es mantener la línea de visión en el plano horizontal de la pared.
CodeMoose

Respuestas:

7

La proyección de rayos es una forma muy rápida y eficiente de determinar la línea de visión. Básicamente implica enviar un rayo (piense en él como un láser infinito que no se puede redirigir) desde una determinada posición en una determinada dirección. Usando este rayo, puede determinar cosas como qué punto (s) se cruzan y qué tan lejos del origen estaba cuando cruzó un cierto punto.

Entonces, por ejemplo, en un escenario de jugador / enemigo, el rayo podría originarse en el enemigo, siendo la dirección la ubicación del jugador. Si el rayo choca con una ficha sólida, el enemigo no puede ver al jugador. Si no lo hace, el enemigo puede ver al jugador.

Aquí hay un excelente tutorial que debería ayudar.

También puede considerar el algoritmo de línea de Bresenham (resumido, crea líneas) para algo que podría escalarse más fácilmente a los mosaicos.

Caballero
fuente
1
Parece el camino a seguir, especialmente el de Bresenham. Gracias por la ayuda djent!
CodeMoose
3

He bloggeado código para calcular la línea de visión desde un mapa de altura. Un mapa plano simple con obstáculos es solo un mapa de altura muy plano, y esta implementación sigue siendo completamente aplicable.

ingrese la descripción de la imagen aquí

Aquí está en C ++ y sus O(n); Si conoce la altura máxima en el mapa, puede rastrear una línea de exploración que no tiene rayos restantes por debajo de esa altura, y desde el principio:

typedef std::vector<float> visbuf_t;

inline void map::_visibility_scan(const visbuf_t& in,visbuf_t& out,const vec_t& eye,int start_x,int stop_x,int y,int prev_y) {
    const int xdir = (start_x < stop_x)? 1: -1;
    for(int x=start_x; x!=stop_x; x+=xdir) {
        const int x_diff = abs(eye.x-x), y_diff = abs(eye.z-y);
        const bool horiz = (x_diff >= y_diff);
        const int x_step = horiz? 1: x_diff/y_diff;
        const int in_x = x-x_step*xdir; // where in the in buffer would we get the inner value?
        const float outer_d = vec2_t(x,y).distance(vec2_t(eye.x,eye.z));
        const float inner_d = vec2_t(in_x,horiz? y: prev_y).distance(vec2_t(eye.x,eye.z));
        const float inner = (horiz? out: in).at(in_x)*(outer_d/inner_d); // get the inner value, scaling by distance
        const float outer = height_at(x,y)-eye.y; // height we are at right now in the map, eye-relative
        if(inner <= outer) {
            out.at(x) = outer;
            vis.at(y*width+x) = VISIBLE;
        } else {
            out.at(x) = inner;
            vis.at(y*width+x) = NOT_VISIBLE;
        }
    }
}

void map::visibility_add(const vec_t& eye) {
    const float BASE = -10000; // represents a downward vector that would always be visible
    visbuf_t scan_0, scan_out, scan_in;
    scan_0.resize(width);
    vis[eye.z*width+eye.x-1] = vis[eye.z*width+eye.x] = vis[eye.z*width+eye.x+1] = VISIBLE;
    scan_0.at(eye.x) = BASE;
    scan_0.at(eye.x-1) = BASE;
    scan_0.at(eye.x+1) = BASE;
    _visibility_scan(scan_0,scan_0,eye,eye.x+2,width,eye.z,eye.z);
    _visibility_scan(scan_0,scan_0,eye,eye.x-2,-1,eye.z,eye.z);
    scan_out = scan_0;
    for(int y=eye.z+1; y<height; y++) {
        scan_in = scan_out;
        _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y-1);
        _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y-1);
    }
    scan_out = scan_0;
    for(int y=eye.z-1; y>=0; y--) {
        scan_in = scan_out;
        _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y+1);
        _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y+1);
    }
}
Será
fuente
Esto es bueno, pero creo que mucho más de lo que busca si lo que quiere es algo como el enlace que publicó.
Djentleman
Muy profundo e impresionante, pero djent está bien, fuera de mi alcance. Gracias por el post sin embargo!
CodeMoose
@CodeMoose eh su código de trabajo; simplemente corte y pegue, traduzca literalmente a cualquier idioma al que se dirija. Es una implementación de Bresenham, realizada de forma incremental, por lo que solo visita cada casilla una vez. Si, por cada cuadro de la cuadrícula, haces una línea de Bresenham al jugador, lo encontrarás masivamente más lento.
Será el
Good point will
CodeMoose