Maneira eficiente de calcular "cones de visão" no mapa de blocos 2D?

13

Estou tentando calcular quais peças uma determinada unidade pode "ver" se estiver voltada para uma determinada direção em um mapa de peças (dentro de um determinado intervalo e ângulo de face). A maneira mais fácil seria desenhar um certo número de peças para fora e transmitir raios para cada peça. No entanto, espero algo um pouco mais eficiente. Uma imagem diz mil palavras:

cones de visão

O ponto vermelho é a unidade (que está voltada para cima). Meu objetivo é calcular os azulejos amarelos. Os blocos verdes são paredes (as paredes são entre peças, e é fácil verificar se você pode passar entre duas peças). A linha azul representa algo como o método "raycasting" de que eu estava falando, mas prefiro não ter que fazer isso.

EDIT: As unidades só podem estar voltadas para norte / sul / leste / oeste (0, 90, 180 ou 270 graus) e o FoV é sempre 90 graus. Deve simplificar alguns cálculos. Eu estou pensando que existe algum tipo de algoritmo recursivo-ish / baseado em pilha / baseado em fila, mas não consigo entender direito.

Obrigado!

2d algorithm tilemap Robert Fraser
fonte
A direção oposta pode ser de qualquer ângulo ou apenas 0,45,90, etc. etc.?
Wondra
O FoV também é sempre 90?
J_F_B_M 20/08/14
@wondra Apenas NSEW (0, 90, 180, 270).
Robert Fraser
@ Larethian - Sim, o FoV é sempre 90. Isso deve ajudar a simplificar as coisas. Estou achando que pode haver uma maneira baseada na pesquisa aprofundada, mas não consigo entender direito.
Robert Fraser
Isso soa como os algoritmos de visão usados ​​em roguelikes . Essas podem ser alguma inspiração. Encontrei uma página listando várias abordagens para o problema.
Anko

Respostas:

13

Yay eu encontrei um trabalho de pesquisa!

Em termos de custo computacional, o Shadow Mapping parece um vencedor bastante claro.

insira a descrição da imagem aqui

O algoritmo usado pode ser encontrado aqui e uma implementação em C # pode ser encontrada aqui , bit relevante abaixo.

    #region FOV algorithm

    //  Octant data
    //
    //    \ 1 | 2 /
    //   8 \  |  / 3
    //   -----+-----
    //   7 /  |  \ 4
    //    / 6 | 5 \
    //
    //  1 = NNW, 2 =NNE, 3=ENE, 4=ESE, 5=SSE, 6=SSW, 7=WSW, 8 = WNW

    /// <summary>
    /// Start here: go through all the octants which surround the player to
    /// determine which open cells are visible
    /// </summary>
    public void GetVisibleCells()
    {
        VisiblePoints = new List<Point>();
        foreach (int o in VisibleOctants)
            ScanOctant(1, o, 1.0, 0.0);

    }

    /// <summary>
    /// Examine the provided octant and calculate the visible cells within it.
    /// </summary>
    /// <param name="pDepth">Depth of the scan</param>
    /// <param name="pOctant">Octant being examined</param>
    /// <param name="pStartSlope">Start slope of the octant</param>
    /// <param name="pEndSlope">End slope of the octance</param>
    protected void ScanOctant(int pDepth, int pOctant, double pStartSlope, double pEndSlope)
    {

        int visrange2 = VisualRange * VisualRange;
        int x = 0;
        int y = 0;

        switch (pOctant)
        {

            case 1: //nnw
                y = player.Y - pDepth;
                if (y < 0) return;

                x = player.X - Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
                if (x < 0) x = 0;

                while (GetSlope(x, y, player.X, player.Y, false) >= pEndSlope)
                {
                    if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
                    {
                        if (map[x, y] == 1) //current cell blocked
                        {
                            if (x - 1 >= 0 && map[x - 1, y] == 0) //prior cell within range AND open...
                                //...incremenet the depth, adjust the endslope and recurse
                                ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x - 0.5, y + 0.5, player.X, player.Y, false));
                        }
                        else
                        {

                            if (x - 1 >= 0 && map[x - 1, y] == 1) //prior cell within range AND open...
                                //..adjust the startslope
                                pStartSlope = GetSlope(x - 0.5, y - 0.5, player.X, player.Y, false);

                                VisiblePoints.Add(new Point(x, y));
                        }                            
                    }
                    x++;
                }
                x--;
                break;

            case 2: //nne

                y = player.Y - pDepth;
                if (y < 0) return;                  

                x = player.X + Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
                if (x >= map.GetLength(0)) x = map.GetLength(0) - 1;

                while (GetSlope(x, y, player.X, player.Y, false) <= pEndSlope)
                {
                    if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
                    {
                        if (map[x, y] == 1)
                        {
                            if (x + 1 < map.GetLength(0) && map[x + 1, y] == 0)
                                ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x + 0.5, y + 0.5, player.X, player.Y, false));
                        }
                        else
                        {
                            if (x + 1 < map.GetLength(0) && map[x + 1, y] == 1)
                                pStartSlope = -GetSlope(x + 0.5, y - 0.5, player.X, player.Y, false);

                            VisiblePoints.Add(new Point(x, y));
                        }                            
                    }
                    x--;
                }
                x++;
                break;

            case 3:

                x = player.X + pDepth;
                if (x >= map.GetLength(0)) return;

                y = player.Y - Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth))); 
                if (y < 0) y = 0;

                while (GetSlope(x, y, player.X, player.Y, true) <= pEndSlope)
                {

                    if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
                    {

                        if (map[x, y] == 1)
                        {
                            if (y - 1 >= 0 && map[x, y - 1] == 0)
                                ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x - 0.5, y - 0.5, player.X, player.Y, true));
                        }
                        else
                        {
                            if (y - 1 >= 0 && map[x, y - 1] == 1)
                                pStartSlope = -GetSlope(x + 0.5, y - 0.5, player.X, player.Y, true);

                            VisiblePoints.Add(new Point(x, y));
                        }                           
                    }
                    y++;
                }
                y--;
                break;

            case 4:

                x = player.X + pDepth;
                if (x >= map.GetLength(0)) return;

                y = player.Y + Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
                if (y >= map.GetLength(1)) y = map.GetLength(1) - 1;

                while (GetSlope(x, y, player.X, player.Y, true) >= pEndSlope)
                {

                    if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
                    {

                        if (map[x, y] == 1)
                        {
                            if (y + 1 < map.GetLength(1)&& map[x, y + 1] == 0)
                                ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x - 0.5, y + 0.5, player.X, player.Y, true));
                        }
                        else
                        {
                            if (y + 1 < map.GetLength(1) && map[x, y + 1] == 1)
                                pStartSlope = GetSlope(x + 0.5, y + 0.5, player.X, player.Y, true);

                             VisiblePoints.Add(new Point(x, y));
                        }                          
                    }
                    y--;
                }
                y++;
                break;

            case 5:

                y = player.Y + pDepth;
                if (y >= map.GetLength(1)) return;

                x = player.X + Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
                if (x >= map.GetLength(0)) x = map.GetLength(0) - 1;

                while (GetSlope(x, y, player.X, player.Y, false) >= pEndSlope)
                {
                    if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
                    {

                        if (map[x, y] == 1)
                        {
                            if (x + 1 < map.GetLength(1) && map[x+1, y] == 0)
                                ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x + 0.5, y - 0.5, player.X, player.Y, false));
                        }
                        else
                        {
                            if (x + 1 < map.GetLength(1)
                                    && map[x + 1, y] == 1)
                                pStartSlope = GetSlope(x + 0.5, y + 0.5, player.X, player.Y, false);

                            VisiblePoints.Add(new Point(x, y));
                        }
                    }
                    x--;
                }
                x++;
                break;

            case 6:

                y = player.Y + pDepth;
                if (y >= map.GetLength(1)) return;                  

                x = player.X - Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
                if (x < 0) x = 0;

                while (GetSlope(x, y, player.X, player.Y, false) <= pEndSlope)
                {
                    if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
                    {

                        if (map[x, y] == 1)
                        {
                            if (x - 1 >= 0 && map[x - 1, y] == 0)
                                ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x - 0.5, y - 0.5, player.X, player.Y, false));
                        }
                        else
                        {
                            if (x - 1 >= 0
                                    && map[x - 1, y] == 1)
                                pStartSlope = -GetSlope(x - 0.5, y + 0.5, player.X, player.Y, false);

                            VisiblePoints.Add(new Point(x, y));
                        }
                    }
                    x++;
                }
                x--;
                break;

            case 7:

                x = player.X - pDepth;
                if (x < 0) return;

                y = player.Y + Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));                    
                if (y >= map.GetLength(1)) y = map.GetLength(1) - 1;

                while (GetSlope(x, y, player.X, player.Y, true) <= pEndSlope)
                {

                    if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
                    {

                        if (map[x, y] == 1)
                        {
                            if (y + 1 < map.GetLength(1) && map[x, y+1] == 0)
                                ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x + 0.5, y + 0.5, player.X, player.Y, true));
                        }
                        else
                        {
                            if (y + 1 < map.GetLength(1) && map[x, y + 1] == 1)
                                pStartSlope = -GetSlope(x - 0.5, y + 0.5, player.X, player.Y, true);

                            VisiblePoints.Add(new Point(x, y));
                        }
                    }
                    y--;
                }
                y++;
                break;

            case 8: //wnw

                x = player.X - pDepth;
                if (x < 0) return;

                y = player.Y - Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
                if (y < 0) y = 0;

                while (GetSlope(x, y, player.X, player.Y, true) >= pEndSlope)
                {

                    if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
                    {

                        if (map[x, y] == 1)
                        {
                            if (y - 1 >=0 && map[x, y - 1] == 0)
                                ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x + 0.5, y - 0.5, player.X, player.Y, true));

                        }
                        else
                        {
                            if (y - 1 >= 0 && map[x, y - 1] == 1)
                                pStartSlope = GetSlope(x - 0.5, y - 0.5, player.X, player.Y, true);

                            VisiblePoints.Add(new Point(x, y));
                        }
                    }
                    y++;
                }
                y--;
                break;
        }


        if (x < 0)
            x = 0;
        else if (x >= map.GetLength(0))
            x = map.GetLength(0) - 1;

        if (y < 0)
            y = 0;
        else if (y >= map.GetLength(1))
            y = map.GetLength(1) - 1;

        if (pDepth < VisualRange & map[x, y] == 0)
            ScanOctant(pDepth + 1, pOctant, pStartSlope, pEndSlope);

    }

    /// <summary>
    /// Get the gradient of the slope formed by the two points
    /// </summary>
    /// <param name="pX1"></param>
    /// <param name="pY1"></param>
    /// <param name="pX2"></param>
    /// <param name="pY2"></param>
    /// <param name="pInvert">Invert slope</param>
    /// <returns></returns>
    private double GetSlope(double pX1, double pY1, double pX2, double pY2, bool pInvert)
    {
        if (pInvert)
            return (pY1 - pY2) / (pX1 - pX2);
        else
            return (pX1 - pX2) / (pY1 - pY2);
    }


    /// <summary>
    /// Calculate the distance between the two points
    /// </summary>
    /// <param name="pX1"></param>
    /// <param name="pY1"></param>
    /// <param name="pX2"></param>
    /// <param name="pY2"></param>
    /// <returns>Distance</returns>
    private int GetVisDistance(int pX1, int pY1, int pX2, int pY2)
    {
        return ((pX1 - pX2) * (pX1 - pX2)) + ((pY1 - pY2) * (pY1 - pY2));
    }

    #endregion
ClassicThunder
fonte
Obrigado! Parece que pode ser complicado fazer isso funcionar com paredes entre células, mas vou tentar e ver como funciona!
Robert Fraser
Eu usaria um dos algoritmos permissivos, veja a tabela na 8ª página do artigo
Gustavo Maciel
Excelente artigo, embora minha conclusão seja diferente, de que não há diferença prática de velocidade. Os resultados mostram que, para mapas típicos de invasores, a maioria dos algoritmos é executada em 50 microssegundos, o que significa que, na prática, é melhor escolher com base em critérios diferentes da velocidade.
congusbongus