Simulando "linha de visão" com obstáculos na grade 2D?

10

Deparou-se com um problema interessante. Eu preciso descobrir como simular a linha de visão - bastante simples, apenas em uma grade 2D com obstáculos. Uma célula da grade é visível ou não.

Posso obter algo realmente rudimentar - como espalhar n espaços do jogador ou bloquear a propagação horizontal quando um obstáculo adjacente é detectado, mas não posso me permitir viver com ele. Muitos outros aplicativos estão usando métodos mais sofisticados que inclinam a linha de visão em torno dos cantos, etc., e eu quero estar no mesmo nível.

Até agora, o DCSS tem sido minha fonte de inspiração quando estou perplexo, na esperança de obter algo próximo do que eles têm: http://crawl.sz.org/ .

Qualquer insight seria apreciado - obrigado pela ajuda!

(Perdoe se isso é embaraçosamente noobish - apenas iniciei o desenvolvimento do jogo há algumas semanas, tentando alcançá-lo.

CodeMoose
fonte
2
Quando você diz "incline a linha de visão em torno dos cantos", o que exatamente você quer dizer?
precisa saber é o seguinte
O melhor que posso dizer é conferir um jogo no crawl.sz.org. Por exemplo, quando o jogador está em pé abaixo de uma parede horizontal com 5 ladrilhos de largura, a linha de visão quebra acima do plano horizontal dessa parede - mas não de maneira irrealista além dela. O melhor que pude aproximar é manter a linha de visão no plano horizontal da parede.
CodeMoose

Respostas:

7

A fundição por raio é uma maneira muito rápida e eficiente de determinar a linha de visão. Basicamente, envolve o envio de um raio (pense nele como um laser infinito que não pode ser redirecionado) de uma determinada posição em uma determinada direção. Usando esse raio, você pode determinar coisas como o (s) ponto (s) em que ele se cruza e a que distância da origem estava quando cruzou um determinado ponto.

Assim, por exemplo, em um cenário de jogador / inimigo, o raio pode se originar do inimigo, com a direção sendo a localização do jogador. Se o raio colidir com uma peça sólida, o inimigo não poderá ver o jogador. Caso contrário, o inimigo pode ver o jogador.

Aqui está um excelente tutorial que deve ajudar.

Você também pode considerar o algoritmo de linha de Bresenham (resumido, ele cria linhas) para algo que pode ser mais facilmente dimensionado para blocos.

Djentleman
fonte
11
Parece o caminho a percorrer - especialmente o de Bresenham. Obrigado pela ajuda djent!
CodeMoose
3

Eu escrevi um código no blog para calcular a linha de visão a partir de um mapa de altura. Um mapa plano simples com obstáculos é apenas um mapa de altura muito plano e essa implementação ainda é completamente aplicável.

insira a descrição da imagem aqui

Aqui está em C ++ e seu O(n); se você souber a altura máxima no mapa, poderá rastrear uma linha de varredura que não tenha raios restantes sob essa altura e sair mais cedo:

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);
    }
}
Vai
fonte
Isso é bom, mas acho muito mais do que ele está procurando se o que ele quer é algo como o link que ele postou.
Djentleman
Muito profundo e impressionante, mas djent está certo - está fora do meu alcance. Obrigado pelo post!
precisa saber é o seguinte
@CodeMoose eh seu código de trabalho; basta recortar e colar, traduzir literalmente para o idioma desejado. É uma implementação de Bresenham, feita de forma incremental, para que ele visite cada quadrado apenas uma vez. Se você, para cada quadrado da grade, fizer uma linha de Bresenham com o jogador, você a achará muito mais lenta.
Will
Bom ponto vai
CodeMoose 17/01