Рекурсивно созданные связанные списки с классом C++

Я использую С++ для рекурсивного создания шестиугольной сетки (используя стиль многосвязного списка). Я настроил его так, чтобы было легко создавать соседние плитки, но поскольку я делаю это рекурсивно, я действительно могу создать только все 6 соседей для данной плитки. Очевидно, это приводит к созданию повторяющихся плиток, и я пытаюсь каким-то образом избавиться от них. Поскольку я использую класс, проверка нулевых указателей не работает. Это либо не удается преобразовать мой класс Tile в int, либо каким-то образом преобразовать его, но не сделать это должным образом. Я явно устанавливаю все указатели в NULL при создании, и когда я проверяю, есть ли они, он говорит, что это не так, хотя я никогда не касался их с момента инициализации. Есть ли какой-то особый способ, которым я должен это сделать? Я даже не могу пройти по сетке без каких-либо NULL

Вот некоторые из моих соответствующих кодов. Да, я знаю, что это смущает.

Заголовок класса плитки:

class Tile
{
public:
    Tile(void);
    Tile(char *Filename);
    ~Tile(void);

    void show(void);
    bool LoadGLTextures();
    void makeDisplayList();
    void BindTexture();
    void setFilename(char *newName);

    char Filename[100];
    GLuint texture[2];
    GLuint displayList;
    Tile *neighbor[6];
    float xPos, yPos,zPos;
};`

Инициализация плитки:

Tile::Tile(void)
{
    xPos=0.0f;
    yPos=0.0f;
    zPos=0.0f;
    glEnable(GL_DEPTH_TEST);
    strcpy(Filename, strcpy(Filename, "Data/BlueTile.bmp"));
    if(!BuildTexture(Filename, texture[0]))
        MessageBox(NULL,"Texture failed to load!","Crap!",MB_OK|MB_ICONASTERISK);

    for(int x=0;x<6;x++)
    {
        neighbor[x]=NULL;
    }
}

Создание соседних плиток:

void MakeNeighbors(Tile *InputTile, int stacks)
{
    for(int x=0;x<6;x++)
    {
        InputTile->neighbor[x]=new Tile();
        InputTile->neighbor[x]->xPos=0.0f;
        InputTile->neighbor[x]->yPos=0.0f;
        InputTile->zPos=float(stacks);
    }
    if(stacks)
    {
        for(int x=0;x<6;x++)
            MakeNeighbors(InputTile->neighbor[x],stacks-1);
    }
}

И, наконец, обход сетки:

void TraverseGrid(Tile *inputTile)
{
    Tile *temp;
    for(int x=0;x<6;x++)
        if(inputTile->neighbor[x])
        {
            temp=inputTile->neighbor[x];
            temp->xPos=0.0f;
            TraverseGrid(temp);
            //MessageBox(NULL,"Not Null!","SHUTDOWN ERROR",MB_OK | MB_ICONINFORMATION);
        }

}

Ключевой строкой является «if(inputTile->neighbor[x])», и независимо от того, делаю ли я это «if(inputTile->neighbor[x]==NULL)» или что-то еще, оно просто не обрабатывает его должным образом. О, и я также знаю, что я не настроил список полностью. Сейчас только одно направление.


person Jon Brant    schedule 25.05.2010    source источник
comment
вы также можете указать, что означает неправильная обработка.   -  person Kornel Kisielewicz    schedule 25.05.2010
comment
Это не лучший кандидат для рекурсии. Не имея возможности найти своих соседей с помощью какой-либо формы координат, у вас нет разумного способа сшить их вместе (очевидно, проблема, с которой вы столкнулись). Вы могли бы сшить их вместе после того, как вы их создадите (newWestCell.northEastCell = this.northWestCell), но это быстро превратится в КОРОЛЕВСКУЮ боль в заднице - и все еще не подходит для рекурсии.   -  person Bill K    schedule 25.05.2010


Ответы (5)


Если вы хотите создать шестиугольную сетку, вы должны помнить, что ее легко можно смоделировать, используя обычную сетку!

    __    __    __
\__/2 \__/4 \__/6 \
/1 \__/3 \__/5 \__/
\__/8 \__/10\__/12\
/7 \__/9 \__/11\__/
\__/  \__/  \__/  \

Это сделает жизнь НАМНОГО проще :)

Следовательно, самым простым способом будет

  1. настроить временную квадратную сетку m*n
  2. заполните его плиткой
  3. пройти через сетку и правильно подключиться

Теперь соединения, исходя из схемы выше:

A) Connect to previous and next [x-1,y], [x+1,y]
B) Connect to row above and row below [x,y-1], [x,y+1]
C) Connect to row above previous and next [x-1,y-1], [x+1,y-1]

... и у вас есть все желаемые соединения (только не забудьте проверить границы, чтобы решить, не находится ли плитка на краю) - если вы держите плитки другим способом, вы даже можете удалить сетку :).

person Kornel Kisielewicz    schedule 25.05.2010
comment
Можно, но эта диаграмма не кажется мне полезной. Для двумерного массива, где каждый узел (x, y) соседствует с (x-1, y), (x + 1, y), (x, y-1), (x, y + 1), сотовый шаблон аналогично дополнительному связыванию с (x+1,y-1),(x+1,y+1) в четных строках и (x-1,y-1),(x-1,y+1) в нечетных ряды. - person Potatoswatter; 25.05.2010
comment
Хитрость заключается в том, чтобы сначала сжать шестиугольники в кирпичи, расположенные в шахматном порядке, а затем посмотреть, как кирпичи соотносятся с регулярной сеткой. - person Potatoswatter; 25.05.2010
comment
@Potatoswatter, вот, ph34r мой l33t ascii skillz ;› - person Kornel Kisielewicz; 25.05.2010
comment
Я уже нашел способ использовать систему координат, и у меня есть весь код для создания правильных соседей. Под неправильной обработкой я подразумеваю, что когда я устанавливаю указатели в NULL, а затем проверяю, являются ли они NULL; Я либо получаю сообщение об ошибке Cannot convert from Tile to int, либо просто говорит, что это не NULL, хотя я его не менял. Я отметил, что знаю, что они еще не связаны должным образом. Я просто еще не реализовал это. То, как я хочу это сделать, также должно иметь возможность проверять указатели NULL, поэтому это на первом месте. Спасибо за ответы - person Jon Brant; 25.05.2010
comment
На самом деле это довольно сложное решение. Вы должны знать, находитесь ли вы в четном или нечетном ряду, чтобы определить NE. Например, NE от 9 — это 10, а NE от 10 — это 5. Как, черт возьми, это работает? Но +8 за эту потрясающую графику вполне оправданы. - person Bill K; 25.05.2010

Я только догадываюсь, что делает MakeNeighbors(), но вместо того, чтобы слепо делать InputTile->neighbor[x]=new Tile();, вы могли бы проверить, не является ли сосед [x] не-NULL, прежде чем создавать новый и инициализировать его. Например. если его родитель создает его и устанавливает всю информацию о своем соседе, то он не должен идти и создавать своего родителя.

Когда родитель создает дочерние элементы, он также должен соответствующим образом определить других соседей дочерних элементов, насколько он их знает. Таким образом, он должен убедиться, что child[i] также является соседом с child[i-1] и child[i+1].

person dash-tom-bang    schedule 25.05.2010

Создание. Рекурсия — это изящный и элегантный способ решения некоторых проблем, но он не идеален для решения всех задач. Я подозреваю, что чисто рекурсивное решение для создания узлов было бы намного сложнее (т.е. менее элегантным), чем простое итеративное решение Корнела Кисилевича. Это связано с тем, что конструктору Tile необходимо знать расположение всех плиток в непосредственной близости от него, чтобы избежать повторного создания уже существующих узлов.

Обход. Основная проблема в вашем коде обхода узлов аналогична тому, что вы столкнетесь с бесконечным циклом и сбросом стека, потому что каждый узел в конечном итоге "перейдет" обратно к своему родителю, начиная цикл. очередной раз. Я полагаю, вы пытаетесь посетить каждую плитку ровно один раз, верно? В этом случае TraverseGrid() должен иметь параметр, указывающий, в каком направлении мы входим в узел, чтобы мы не возвращались в обратном направлении.

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

Одной из возможностей может быть изменение подписи TraverseGrid() на TraverseGrid(Tile *inputTile, int fromDir, bool leftmost), а затем использование следующих правил:

  • Если мы вошли сверху-слева, пройдите только сверху-справа, пройдя leftmost = false.
  • Если мы вошли снизу-слева или сверху-справа, идем только снизу-справа, минуя leftmost = false.
  • Если leftmost и слева внизу есть узел, то также проходим к этому узлу, минуя leftmost = true.

Конечно, fromDir и leftmost можно объединить в один параметр, но это дает общее представление.

Другой альтернативой может быть сохранение флага visited в каждом тайле, который проверяется перед переходом к этому тайлу. Тогда ваш обход будет заливкой. Но опять же, простой итеративный обход, скорее всего, будет намного проще и понятнее, а также имеет дополнительное преимущество, заключающееся в использовании постоянного пространства стека.

person j_random_hacker    schedule 25.05.2010

В объявлении класса есть второй конструктор Tile(char *Filename);. Может быть, этот конструктор используется для создания основного узла, но неправильно инициализирует neighbor? (Его реализация не показана.)

А на несвязанном узле у вас есть дубликат strcpy() в конструкторе, который не служит никакой цели и может привести только к проблемам:

strcpy(Filename, strcpy(Filename, "Data/BlueTile.bmp"));
person sth    schedule 25.05.2010
comment
О, ха-ха, да. Раньше я делал с ним что-то другое. Спасибо что подметил это. - person Jon Brant; 25.05.2010
comment
Я использую другой конструктор для указания текстуры не по умолчанию. - person Jon Brant; 25.05.2010

Я на самом деле сделал то же самое, но мой шаблон был больше похож на это:

00   01   02   03   04

   10    11   12   13   14

      20    21   22   23   24

         30   31   32   33   34

Это позволяет довольно легко понять, чего можно достичь, но создает странный шаблон смещения. Я просто избавился (в приведенном выше примере) от 00,01,10 и 20, чтобы сделать его более похожим на шестнадцатеричный шаблон:

            02   03   04   05   06

         11   12   13   14   15

            21   22   23   24   25

         30   31   32   33   34

Итак, если вы посмотрите на приведенный выше шаблон, достижимость всегда одна и та же:

от 23 (звонки 2 "а" и 3 "б") можно доехать:

NW(a-1, b), NE(a-1, b+1), W(a, b-1), E(a, b+1), SW(a+1, b-1), SE(a+1,b)

Этот шаблон должен быть правильным для всей сетки.

РЕДАКТИРОВАТЬ:

Я собирался сделать это в комментарии, но он получился слишком длинным. Я вижу два подхода.

1) Выделить массив узлов (нулевой, не выделять их). Всякий раз, когда вам нужно выделить узел, просто сделайте это, но используйте адрес массива всякий раз, когда вам нужно сослаться на узел, если он равен нулю, заполните его, если он имеет значение, используйте это значение. Огромные пустые массивы не должны занимать столько памяти, но если они это сделают...

2) Создайте HashSet для хранения ваших узлов, где значение Hash класса узла рассчитывается следующим образом: (a ‹‹ 32 || b). Таким образом, вы можете мгновенно посмотреть, существовал ли предыдущий узел или нет. Не забудьте также перегрузить "equals" (он должен возвращать true, только если сравниваемый объект имеет один и тот же тип, а a и b равны).

В наиболее заполненной системе, где известны границы, 1 сэкономит память, но если ваша система разрежена (как вы утверждаете), то № 2 может сэкономить МНОГО памяти без затрат на эффективность.

person Bill K    schedule 25.05.2010
comment
Да, у меня все это есть. Конкретная проблема, которую я изучаю, состоит в том, что агент ходит от плитки к плитке с определенным набором правил (на самом деле я делаю аналог муравья Лэнгтона с этим. И из-за его поведения он быстро достигнет края. Скорее чем создавать МАССИВНЫЙ массив для его перемещения, я хочу иметь возможность создавать новые плитки только при необходимости. - person Jon Brant; 25.05.2010
comment
На самом деле, глядя на ваш способ настройки, он немного более интуитивен, чем мой. - person Jon Brant; 25.05.2010
comment
Если выделение всей структуры данных нежелательно, возможно, вам следует подумать о ее моделировании в виде неявного графа — графа, в котором узлы (плитки) и ребра (соединения) обнаруживаются/выделяются только при необходимости. Библиотека Boost Graph — это очень надежная (хотя и сложная) структура, которая поможет вам, если вы пойдете по этому пути. Затем вы можете выполнять обходы и другие алгоритмы поиска пути поверх неявного графа. - person BenG; 25.05.2010
comment
@Jon Brant Этот комментарий просто для того, чтобы вы посмотрели на мою правку в ответ на ваш комментарий выше. - person Bill K; 25.05.2010