Хранение стен между плитками

Пишу изометрический движок на с ++. Я решил использовать более реалистичный подход и сделать так, чтобы стены занимали пространство между двумя плитками, а не одной плиткой целиком, как показано на рисунке ниже (как в The Sims).

Моя проблема в том, что я понятия не имею, как хранить данные, относящиеся к карте тайлов, в виде, который не является сеткой. В этой ситуации, я думаю, мне нужно будет сделать его дружественным к A *, чтобы между плитками были узлы и ребра, не разделенные стенами. Вот еще одна картина, показывающая, чего я хочу достичь:

Итак, вот вопрос (ы):

Как я должен:

• хранить всю карту, как плитки, так и стены
• оптимизировать его для рендеринга
• использовать его для A * и других алгоритмов довольно просто для реализации на простой сетке, но теперь использовать стены (ребра) для определения видимости, столкновения и т. д.?

Я начну с систем координат - координаты для местоположений сетки (x, y), но, как упоминал Кром в другом ответе, для стен может быть до двух стен для каждого местоположения сетки. Это приводит ко второй системе координат, для ребер между плитками . В этой статье я использовал запад и юг, поэтому края могут быть (x, y, запад) или (x, y, юг), но вы можете выбрать два, если вы последовательны.

Эти две системы координат (сетка и ребра) взаимосвязаны. Вы хотите спросить: какие четыре края окружают плитку?

Для поиска пути A * хочет знать, какие плитки являются соседями (B) текущей плитки (A). Вместо того, чтобы возвращать все четыре соседние плитки, вы можете проверить четыре края. Вы включаете плитку B в качестве соседа, только если между A и B. нет стены.

Вместо того, чтобы хранить две стены для каждой плитки, как предлагает Кром, я обычно держу стены в отдельной структуре данных: наборе координат ребер. Когда A * хочет узнать, является ли B соседом A, я проверю, есть ли этот край в наборе. Если это так, то я не возвращаю Б.

Вам, вероятно, не нужно это для A *, но для других вещей вы, вероятно, захотите узнать для любого ребра, какие две плитки связаны с ним:

См. Раздел «Алгоритмы» на странице для расчетов для этих двух операций.

Также обратите внимание: для некоторых типов карт вы фактически хотите сохранить четыре ребра на плитку сетки, чтобы вы могли поддерживать односторонние перемещения.

В каждой плитке вы можете хранить стены на севере и востоке. Таким образом, каждая плитка должна хранить только еще 2 логических значения (или целые, если вы хотите хранить тип стены). Недостатком является то, что плитки на южном и западном краях не могут иметь стены на юге и западе, если вы не добавите еще один ряд скрытых плиток, которые будут иметь их.

В каждой плитке он может хранить соседей (или подключения), к которым у него есть доступ. Возможно, как растровое изображение. Стены, где две соседние плитки не связаны. Это очень дружелюбно с A *.

Второй подход заключается в сохранении связности тайла в качестве перечисления. Например, полностью открытый тайл равен 0, тайл со стеной на север и открытым - 1, тайл со стеной на юг и открытым - 2 и т. Д., Пока вы не охватите все возможные комбинации.

Надеюсь, этот C # вам подходит - мой c ++ очень ржавый:

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
}

Вы можете добавить специфическую для стены информацию в класс Wall, специфичную для Tile информацию в класс Tile и дополнительно уточнить условия в методе «CanGo». Например, когда стена на самом деле является запертой дверью - скажем, классом Двери.

Чтобы нарисовать это, вы должны начать с некоторой произвольной плитки - скажем, плитки в середине текущей позиции камеры. Затем двигайтесь в направлении и влево от камеры в соответствии с размером плиток. Затем выполните обход в ширину узлов IMapFeature, рисуя каждую стену / плитку в указанном порядке.

A * будет работать с этой структурой, хотя вам, очевидно, потребуются некоторые модификации для обработки чего-то вроде запертых дверей.

Если вы хотите, вы можете также поддерживать пространственный индекс плиток, который бы неявно включал стены, чтобы выяснить, какие плитки были в пределах границ камеры.

Вам все равно нужно будет выбрать стартовую плитку и расстояние для прохождения в зависимости от размера плитки.