Stockage des murs entre les carreaux

J'écris un moteur isométrique en c ++. J'ai décidé d'adopter une approche plus réaliste et de faire en sorte que les murs occupent l'espace entre deux tuiles, pas une seule tuile entière, comme le montre l'image ci-dessous (comme dans Les Sims).

Mon problème est que je ne sais pas comment stocker les données liées à la carte de tuiles dans quelque chose qui n'est pas une grille. Dans cette situation, je suppose que je devrai le rendre compatible avec A *, donc il y aura des nœuds et des bords entre les carreaux non divisés par des murs. Voici une autre photo montrant ce que je veux réaliser:

Voici donc la (les) question (s):

Comment devrais-je:

• stocker toute la carte, les carreaux et les murs
• l'optimiser pour le rendu
• l'utiliser pour A * et d'autres algorithmes plutôt simples à implémenter sur une grille simple mais en utilisant maintenant des murs (bords) pour déterminer la visibilité, la collision, etc.?

Je commence par les systèmes de coordonnées - les coordonnées pour les emplacements de grille sont (x, y) mais comme Krom l'a mentionné dans une réponse différente, pour les murs, il peut y avoir jusqu'à deux murs pour chaque emplacement de grille. Cela conduit à un deuxième système de coordonnées, pour les bords entre les tuiles . Dans cet article, j'ai utilisé Ouest et Sud pour que les bords puissent être (x, y, ouest) ou (x, y, sud), mais vous pouvez en choisir deux tant que vous êtes cohérent.

Ces deux systèmes de coordonnées (tuiles de grille et arêtes) sont liés. Vous voudrez vous demander: quels quatre bords entourent une tuile?

Pour l'orientation, A * veut savoir quelles tuiles sont voisines (B) de la tuile actuelle (A). Au lieu de retourner les quatre tuiles adjacentes, vous pouvez vérifier les quatre bords. Vous incluez la tuile B comme voisin uniquement s'il n'y a pas de mur entre A et B.

Au lieu de stocker deux murs pour chaque tuile, comme le suggère Krom, je garde généralement les murs dans une structure de données distincte: un ensemble de coordonnées de bord. Quand A * veut savoir si B est un voisin de A, je vérifierai si cette arête est dans l'ensemble. Si c'est le cas, je ne retourne pas B.

Vous n'avez probablement pas besoin de cela pour A *, mais pour d'autres choses, vous voudrez probablement savoir pour n'importe quel bord, les deux tuiles qui y sont connectées:

Voir la section «Algorithmes» de la page pour les calculs de ces deux opérations.

Notez également: pour certains types de cartes, vous souhaiterez en fait stocker quatre bords par mosaïque de grille, afin de pouvoir prendre en charge les déplacements à sens unique.

Dans chaque tuile, vous pouvez stocker les murs qu'elle a au nord et à l'est. De cette façon, chaque tuile ne doit stocker que 2 booléens supplémentaires (ou des entiers, si vous souhaitez stocker le type de mur). L'inconvénient est que les tuiles le long des bords sud et ouest ne peuvent pas avoir de murs au sud et à l'ouest, sauf si vous ajoutez une rangée de tuiles cachées supplémentaires qui en auront.

Dans chaque tuile, il pourrait stocker les voisins (ou connectivité) auxquels il a accès. Peut-être sous forme de bitmap. Les murs sont là où les deux tuiles adjacentes ne sont pas connectées. C'est très amical avec A *.

La deuxième approche consiste à stocker la connectivité des tuiles comme une énumération. Par exemple, une tuile entièrement ouverte vaut 0, une tuile avec un mur au nord et un reste ouvert est 1, une tuile avec un mur au sud et un reste ouvert est 2, et ainsi de suite jusqu'à ce que vous ayez couvert toutes les combinaisons possibles.

Espérons que ce C # vous convient - mon c ++ est très rouillé:

abstract class MapFeature
{
    public void Draw();
    public bool IsWall();
}
enum Direction
{
    North, South, East, West
}
class Wall : MapFeature
{
    public bool IsWall() { return true; }
    public Tile Front, Back; // Tiles on either side of the wall, otherwise null.

    #region Implementation of MapFeature

    public void Draw()
    {
        // Wall specific drawing code...
    }

    #endregion
}
class Tile : MapFeature
{
    public bool IsWall() { return false; }

    public MapFeature North, South, East, West; // Tiles/Walls on each side, otherwise null

    public bool CanGo(Direction direction)
    {
        switch (direction)
        {
            case Direction.North:
                return !North.IsWall();
            case Direction.South:
                return !South.IsWall();
            case Direction.East:
                return !East.IsWall();
            case Direction.West:
                return !West.IsWall();
            default:
                throw new ArgumentOutOfRangeException("direction");
        }
    }

    #region Implementation of MapFeature

    public void Draw()
    {
        // Tile specific drawing code...
    }

    #endregion
}

Vous pouvez ajouter des informations spécifiques à un mur à la classe Wall, des informations spécifiques à Tile à la classe Tile et affiner davantage les conditions dans la méthode "CanGo". Par exemple, lorsqu'un mur est en fait une porte verrouillée, disons une classe Door.

Pour dessiner ceci, vous commenceriez avec une tuile arbitraire - disons la tuile au milieu de la position actuelle de la caméra. Ensuite, déplacez-vous vers et vers la gauche de la caméra en fonction de la taille des carreaux. Effectuez ensuite une première traversée des nœuds IMapFeature, en dessinant chaque mur / tuile dans l'ordre rencontré.

A * fonctionnera sur cette structure, bien que vous ayez évidemment besoin de quelques modifications pour gérer quelque chose comme des portes verrouillées.

Si vous le souhaitez, vous pouvez également conserver un index spatial des tuiles, qui inclurait implicitement les murs, afin de savoir quelles tuiles se trouvaient dans les limites de la caméra.

Il ne vous restait plus qu'à choisir une tuile de départ et une distance à parcourir en fonction de la taille de la tuile.