Almacenar paredes que están entre azulejos

Estoy escribiendo un motor isométrico en c ++. Decidí adoptar un enfoque más realista y hacer que las paredes ocuparan espacio entre dos fichas, no una sola ficha completa, como se muestra en la imagen a continuación (al igual que en Los Sims).

Mi problema es que no tengo idea de cómo almacenar los datos relacionados con el mapa de mosaico en algo que no es cuadrícula. En esta situación, supongo que tendré que hacerlo A * amigable, por lo que habrá nodos y bordes entre los mosaicos no divididos por paredes. Aquí hay otra imagen que muestra lo que quiero lograr:

Así que aquí está la pregunta (s):

Como podria yo:

• almacenar todo el mapa, tanto azulejos como paredes
• optimizarlo para renderizar
• ¿lo usa para A * y otros algoritmos bastante sencillos de implementar en una cuadrícula simple pero ahora usa paredes (bordes) para determinar la visibilidad, la colisión, etc.?

Comienzo con sistemas de coordenadas: las coordenadas para las ubicaciones de la cuadrícula son (x, y) pero, como Krom mencionó en una respuesta diferente, para los muros puede haber hasta dos muros para cada ubicación de la cuadrícula. Eso lleva a un segundo sistema de coordenadas, para los bordes entre los azulejos . En este artículo usé Oeste y Sur para que los bordes puedan ser (x, y, Oeste) o (x, y, Sur), pero puedes elegir dos siempre que seas consistente.

Estos dos sistemas de coordenadas (cuadrículas y bordes) están relacionados. Querrá preguntar: ¿qué cuatro bordes rodean un mosaico?

Para la búsqueda de rutas, A * quiere saber qué mosaicos son vecinos (B) del mosaico actual (A). En lugar de devolver los cuatro mosaicos adyacentes, puede verificar los cuatro bordes. Incluye el mosaico B como vecino solo si no hay un muro entre A y B.

En lugar de almacenar dos paredes para cada mosaico, como sugiere Krom, generalmente mantengo las paredes en una estructura de datos separada: un conjunto de coordenadas de borde. Cuando A * quiera saber si B es vecino de A, comprobaré si ese borde está en el conjunto. Si es así, entonces no devuelvo B.

Probablemente no necesite esto para A *, pero para otras cosas probablemente querrá saber para cualquier borde, qué dos mosaicos están conectados a él:

Consulte la sección "Algoritmos" de la página para ver los cálculos de estas dos operaciones.

También tenga en cuenta: para algunos tipos de mapas, en realidad querrá almacenar cuatro bordes por mosaico de cuadrícula, para que pueda admitir movimientos unidireccionales.

En cada mosaico puede almacenar paredes que tiene en el norte y el este. De esa forma, cada mosaico necesita almacenar solo 2 booleanos más (o ints, si desea almacenar el tipo de muro). La desventaja es que las fichas a lo largo de los bordes Sur y Oeste no pueden tener paredes en el Sur y Oeste a menos que agregue una fila más de fichas ocultas que las tendrán.

En cada mosaico, podría almacenar los vecinos (o conectividad) a los que tiene acceso. Quizás como un mapa de bits. Las paredes son donde las dos fichas adyacentes no están conectadas. Esto es muy amigable con A *.

El segundo enfoque es almacenar la conectividad del mosaico como una enumeración. Por ejemplo, un mosaico completamente abierto es 0, un mosaico con pared hacia el norte y resto abierto es 1, un mosaico con pared hacia sur y resto abierto es 2, y así sucesivamente hasta que haya cubierto todas las combinaciones posibles.

Espero que este C # esté bien para ti, mi C ++ está muy oxidado:

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
}

Puede agregar información específica del muro a la clase Muro, información específica del mosaico a la clase Mosaico y refinar más las condiciones en el método "CanGo". Por ejemplo, cuando una pared es en realidad una puerta cerrada, por ejemplo, una clase de puerta.

Para dibujar esto, comenzaría con un mosaico arbitrario, digamos el mosaico en el medio de la posición actual de la cámara. Luego, muévase hacia y a la izquierda de la cámara de acuerdo con el tamaño de los mosaicos. Luego, haga un recorrido transversal de los nodos IMapFeature, dibujando cada muro / mosaico en el orden encontrado.

A * funcionará en esta estructura, aunque obviamente necesitaría algunas modificaciones para manejar algo como puertas cerradas.

Si quisiera, también podría mantener un índice espacial de los mosaicos, que incluiría implícitamente los muros, para descubrir qué mosaicos estaban dentro de los límites de la cámara.

Todavía solo necesitaría elegir un mosaico inicial y una distancia para recorrer según el tamaño del mosaico.