Отображение пути разветвляющейся плитки

Question

Я работаю над игрой (и уже задавал пару вопросов по ней), и теперь у меня есть еще один вопрос к вам, ребята.

Формат уровня в этой игре настроен как карта тайлов Uint16 (я использую SDL), которые являются индексами в массив структур tilemapData. Одним из битов структуры tilemapData является isConductive bit / boolean.

Этот бит используется, в основном, для создания путей, которые соединяют различные объекты в одну "сеть PowerNet". Ниже приведен код текущего метода (который работает, но я расскажу, почему я его действительно ненавижу)

void findSetPoweredObjects(unsigned long x, unsigned long y, powerNetInfo * powerNet) {
  //Look for poweredObjs on this tile and set their powerNet to the given powernet
  for (int i = 0; i < level->numChunks[CHUNKTYPE_POWEREDDEF]; i++)
    if (level->poweredObjects[i]->position[0] == x && level->poweredObjects[i]->position[1] == y)
      level->poweredObjects[i]->powerNet = powerNet, powerNet->objectsInNet++;
}

void recursiveCheckTile(bool * isWalked, powerNetInfo * powerNet, unsigned long x, unsigned long y, tilemapData * levelMap) {
  //If out of bounds, return
  if (x < 0 || y < 0 || x >= level->mapDimensions[0] || y >= level->mapDimensions[1]) return;
  //If tile already walked, return
  if (isWalked[x + (y * level->mapDimensions[0])]) return;
  //If tile is nonconductive, return
  if (!(level->tiles[levelMap->map[x + (y * level->mapDimensions[0])]]->flags & TILETYPE_CONDUCTIVE)) return;

  //Valid tile to check, see if there's a poweredobj on the tile (link it to the net if it is) and check the adjacent tiles.
  isWalked[x + (y * level->mapDimensions[0])] = true;

  findSetPoweredObjects(x,y,powerNet);

  recursiveCheckTile(isWalked, powerNet, x - 1, y, levelMap);
  recursiveCheckTile(isWalked, powerNet, x + 1, y, levelMap);
  recursiveCheckTile(isWalked, powerNet, x, y - 1, levelMap);
  recursiveCheckTile(isWalked, powerNet, x, y + 1, levelMap);
}

bool buildPowerNets(void) {
  //Build the powernets used by the powered objects
  //TODO: Rewrite buildPowerNets() & recursiveCheckTile() to avoid stack overflows and make it easier to backtrace powernets in-game
  bool * isWalked;
  isWalked = new bool[(level->mapDimensions[0] * level->mapDimensions[1])];
  unsigned long x, y;
  tilemapData * levelMap = level->layers[level->activeMap];
  for (y = 0; y < level->mapDimensions[1]; y++) {
    for (x = 0; x < level->mapDimensions[0]; x++) {
      if (isWalked[x + (y * level->mapDimensions[0])]) continue;
      isWalked[x + (y * level->mapDimensions[0])] = true;
      if (level->tiles[levelMap->map[x + (y * level->mapDimensions[0])]]->flags & TILETYPE_CONDUCTIVE) {
        //it's conductive, find out what it's connected to.

        //But first, create a new powernet
        powerNetInfo * powerNet = new powerNetInfo;
        powerNet->objectsInNet = 0;
        powerNet->producerId = -1;
        powerNet->supplyType = POWER_OFF;
        powerNet->prevSupplyType = POWER_OFF;
        powerNet->powerFor = 0;

        //Find adjacent tiles to this one, add them to it's powernet, and then mark them walked.  Then repeat until the net is done.
        recursiveCheckTile(isWalked, powerNet, x, y, levelMap);
      }
    }
  }
  delete isWalked;
  for (int i = 0; i < level->numChunks[CHUNKTYPE_POWEREDDEF]; i++)
      if (level->poweredObjects[i]->powerNet == NULL) return false;
  return true;
}

Обратите внимание, что возвращение false означает, что функция завершилась ошибкой (в этом случае она не правильно связала все объекты).

Меня беспокоит то, что из-за переполнения стека функция обхода токопроводящих плиток не сработает на более сложных картах. Каковы некоторые идеи о том, как уменьшить этот риск с помощью этих функций? Я могу предоставить больше информации об используемых структурах, если это необходимо.

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

Если это имеет значение, скорость здесь совершенно не важна, поскольку эта функция запускается только один раз, когда карта обрабатывается перед использованием, и поэтому использование небольшого дополнительного времени не повредит.

Answer 1

Заливка

Похоже, вы в основном делаете заливку своей сеткой. Вы можете устранить рекурсию, используя очередь или стек квадратов, которые необходимо проверить. Смотрите раздел "Альтернативные реализации" статьи в Википедии, чтобы узнать псевдокод.

Преимущество сохранения очереди / стека самостоятельно заключается в том, что вы удаляете квадраты из списка при их посещении, тогда как в рекурсивном решении квадраты остаются в стеке даже после того, как вы их посетили.

Вот "простая" альтернативная реализация из статьи Википедии, адаптированная к вашей проблеме:

1. Set Q to the empty queue.
2. Add node to the end of Q.
3. While Q is not empty: 
4.     Set n equal to the first element of Q
5.     Remove first element from Q
6.     If n has already been visited:
7.         Go back to step 3.
8.     Mark n as visited.
9.     Add the node to the west to the end of Q.
10.    Add the node to the east to the end of Q.
11.    Add the node to the north to the end of Q.
12.    Add the node to the south to the end of Q.
13. Return.

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

Заполнение очереди на основе

Стековая заливка

Маркировка подключенных компонентов

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

Answer 2

Вы можете переписать эту функцию итеративно.

Подумайте об этом так: вы неявно используете стек вызовов в качестве стека пути для вашего алгоритма поиска. Каждый раз, когда вы звоните recursiveCheckTile Вы помещаете узел в этот стек. Тем не менее, стек вызовов относительно невелик, поэтому вы быстро его выбросите.

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

add starting node to stack

while( nodes on stack )
{
    pop node
    if( node is conductive )
    {
        add node to powerSet
        push 4 adjoining nodes onto stack
    }
}

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