Armazenando paredes que estão entre ladrilhos

Estou escrevendo mecanismo isométrico em c ++. Decidi adotar uma abordagem mais realista e fazer com que as paredes ocupassem espaço entre dois ladrilhos, e não um único ladrilho inteiro, como mostra a figura abaixo (como no The Sims).

Meu problema é que não tenho idéia de como armazenar os dados relacionados ao mapa de blocos em algo que não é grade. Nesta situação, acho que vou precisar torná-lo A * amigável, para que haja nós e arestas entre os ladrilhos não divididos por paredes. Aqui está outra imagem mostrando o que eu quero alcançar:

Então, aqui estão as perguntas:

Como devo:

• armazenar o mapa inteiro, tanto azulejos quanto paredes
• otimizá-lo para renderização
• usá-lo para A * e outros algoritmos bastante simples de implementar em uma grade simples, mas agora usando paredes (arestas) para determinar a visibilidade, colisão etc.?

Começo com sistemas de coordenadas - as coordenadas para os locais da grade são (x, y), mas, como Krom mencionou em uma resposta diferente, para paredes, pode haver até duas paredes para cada local da grade. Isso leva a um segundo sistema de coordenadas, para arestas entre blocos . Em este artigo eu usei Oeste e Sul para que as bordas podem ser (x, y, West) ou (x, y, Sul), mas você pode escolher dois, enquanto você está consistente.

Esses dois sistemas de coordenadas (ladrilhos e arestas) estão relacionados. Você vai querer perguntar: quais quatro arestas cercam um ladrilho?

Para a busca de caminhos, A * deseja saber quais blocos são vizinhos (B) do bloco atual (A). Em vez de retornar todos os quatro blocos adjacentes, você pode verificar as quatro arestas. Você inclui o bloco B como vizinho apenas se não houver parede entre A e B.

Em vez de armazenar duas paredes para cada bloco, como sugere Krom, normalmente mantenho as paredes em uma estrutura de dados separada: um conjunto de coordenadas de aresta. Quando A * quer saber se B é um vizinho de A, vou verificar se essa borda está no conjunto. Se for, não retornarei B.

Você provavelmente não precisa disso para A *, mas, para outras coisas, provavelmente desejará saber sobre qualquer borda, quais dois blocos estão conectados a ela:

Consulte a seção "Algoritmos" da página para obter os cálculos para essas duas operações.

Observe também: para alguns tipos de mapas, você realmente deseja armazenar quatro arestas por bloco de grade, para que você possa suportar movimentos unidirecionais.

Em cada ladrilho, você pode armazenar paredes no norte e no leste. Dessa forma, cada bloco precisa armazenar apenas mais 2 booleanos (ou ints, se você deseja armazenar o tipo de parede). A desvantagem é que os ladrilhos ao longo das bordas sul e oeste não podem ter paredes no sul e oeste, a menos que você adicione mais uma linha de ladrilhos ocultos que os terão.

Em cada bloco, ele pode armazenar os vizinhos (ou conectividade) aos quais tem acesso. Talvez como um bitmap. As paredes são onde os dois ladrilhos adjacentes não estão conectados. Isso é muito amigável com o A *.

A segunda abordagem é armazenar a conectividade do bloco como uma enumeração. Por exemplo, um ladrilho totalmente aberto é 0, um ladrilho com parede ao norte e descanso aberto é 1, um ladrilho com parede ao sul e descanso aberto é 2 e assim sucessivamente até você cobrir todas as combinações possíveis.

Espero que este C # seja bom para você - meu c ++ está muito enferrujado:

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
}

Você pode adicionar informações específicas de parede à classe Wall, informações específicas de Tile à classe Tile e refinar ainda mais as condições no método "CanGo". Por exemplo, quando uma parede é na verdade uma porta trancada - digamos, uma classe Door.

Para desenhar isso, você começaria com algum bloco arbitrário - diga o bloco no meio da posição atual da câmera. Em seguida, mova-se para a esquerda da câmera e de acordo com o tamanho dos ladrilhos. Em seguida, faça uma travessia da largura dos nós IMapFeature, desenhando cada parede / bloco na ordem encontrada.

O A * funcionará nessa estrutura, embora você obviamente precise de algumas modificações para lidar com algo como portas trancadas.

Se você quiser, também poderá manter um índice espacial dos ladrilhos, o que incluiria implicitamente as paredes, para descobrir quais ladrilhos estavam dentro dos limites da câmera.

Você ainda precisará escolher um bloco inicial e uma distância para percorrer com base no tamanho do bloco.