Un moyen efficace de calculer les «cônes de vision» sur une carte de tuiles 2D?

13

J'essaie de calculer quelles tuiles une unité particulière peut "voir" si elle fait face à une certaine direction sur une carte de tuiles (dans une certaine plage et un certain angle de face). La manière la plus simple serait de dessiner un certain nombre de tuiles vers l'extérieur et de diffuser des rayons sur chaque tuile. Cependant, j'espère quelque chose d'un peu plus efficace. Une image dit mille mots:

cônes de vision

Le point rouge est l'unité (qui est tournée vers le haut). Mon objectif est de calculer les tuiles jaunes. Les blocs verts sont des murs (les murs sont entre les carreaux, et il est facile de vérifier si vous pouvez passer entre deux carreaux). La ligne bleue représente quelque chose comme la méthode de "raycasting" dont je parlais, mais je préfère ne pas avoir à le faire.

EDIT: Les unités ne peuvent faire face qu'au nord / sud / est / ouest (0, 90, 180 ou 270 degrés) et FoV est toujours à 90 degrés. Devrait simplifier certains calculs. Je pense qu'il y a une sorte d'algorithme récursif / basé sur la pile / basé sur la file d'attente, mais je ne peux pas vraiment le comprendre.

Merci!

2d algorithm tilemap Robert Fraser
la source
La direction de face peut-elle être un angle quelconque ou juste 0,45,90, .. etc.?
wondra
Le FoV est-il toujours à 90?
J_F_B_M
@wondra Uniquement NSEW (0, 90, 180, 270).
Robert Fraser
@Larethian - Oui, FoV a toujours 90 ans. Cela devrait aider à simplifier les choses. Je pense qu'il pourrait y avoir un moyen basé sur la recherche en profondeur, mais je ne peux pas vraiment le comprendre.
Robert Fraser
Cela ressemble aux algorithmes de vision utilisés dans les roguelikes . Ce pourrait être une source d'inspiration. J'ai trouvé une page répertoriant diverses approches du problème.
Anko

Réponses:

13

Oui, j'ai trouvé un document de recherche!

En termes de coût de calcul, le Shadow Mapping semble être un gagnant assez clair.

entrez la description de l'image ici

L'algorithme utilisé peut être trouvé ici et une implémentation C # peut être trouvée ici , bit pertinent ci-dessous.

    #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
la source
Merci! Il semble que cela puisse être difficile de faire fonctionner cela avec des murs entre les cellules, mais je vais essayer et voir comment cela fonctionne!
Robert Fraser
J'irais avec l'un des algorithmes permissifs, voir le tableau dans la 8ème page de l'article
Gustavo Maciel
Excellent papier, bien que ma conclusion soit différente, qu'il n'y a pas de différence de vitesse pratique. Les résultats montrent que pour les cartes typiques de type voyous, la plupart des algorithmes fonctionnent dans un délai de 50 microsecondes, ce qui signifie qu'en pratique, il vaut mieux choisir en fonction de critères autres que la vitesse.
congusbongus