Группировка 2D-массива экземпляров

Question

Группировка 2D-массива экземпляров

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

Я работаю над подключением> = 3, украшенной драгоценностями игрой в стиле пазл. Когда состояние «платы» меняется, я группирую все части так, что, если они «соединены» по горизонтали или вертикали, они разделяют ID. Вот как я делаю это сейчас:

[Псевдо]

for all( array object* )
{
if !in_a_group() check_neighbours( this )
}

void check_neighbours( ID )
{
if ( check_is_same_type( left ) )
{
if !in_a_group() this.ID = ID ; check_neighbours( ID )
else if( in_a_group ) change_IDs(this.ID, ID )
}
same for right ...
up ...
down ...
}

Это действительно грязная псевдо версия того, что я делаю.
Я рекурсивно вызываю check_neighbours, передавая идентификатор первого элемента ветви вперед (я использую этот указатель как идентификатор, а не генерирую его).

Если я нахожу часть с другим идентификатором, которая подключена, я перезаписываю все части с этим идентификатором новым идентификатором (здесь у меня есть ASSERT, потому что на самом деле это не должно происходить. Такого еще не было во многих тестах)

Я не проверяю_соседства в исходной ветви, если у части нет идентификатора.

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

Также я новичок в stackoverflow, достаточно плохо знаком с программированием, и любые советы по этикету и т. Д. Приветствуются.

0

2d-games c++optimization

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Как бы вы предложили избегать рекурсии?

Насколько я понимаю, ваш алгоритм представляет собой «заливку» небольшим поворотом.

В любом случае, чтобы избежать рекурсии, вам нужно выделить массив для хранения координат необработанных элементов и использовать очередь или fifo. Поскольку вы знаете размеры сетки (и так как это игра в стиле с драгоценными камнями (?), Вы должны быть в состоянии распределить ее в любом месте).

псевдокод для любого рекурсивного алгоритма типа заливки.

struct Coord{
int x, y;
}

typedef std::queue<Coord> CoordQueue;

bool validCoord(Coord coord){
return (coord.x >= 0) && (coord.y >= 0)
&& (coord.x < boardSizeX) && (coord.y < boardSizeY);
}

bool mustProcessCoord(Coord coord);

void processAll(){
CoordQueue coordQueue;
Coord startPoint = Coord(0, 0);
coordQueue.pushBack(startPoint);

while (!coordQueue.empty()){
const Coord &curCoord = coordQueue.front();
//do something with current coordinates.
processCoord(curCoord);

const int numOffsets = 4;
const int offsets[numOffsets][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
for (int offsetIndex = 0; offsetIndex < numOffsets; offsetIndex++){
Coord neighborCoord = Coord(curCoord.x + offsets[offsetIndex][0],
curCoord.y + offsets[offsetIndex][1]);
if (!isValidCoord(neighborCoord) || !mustProcessCoord(neighborCoord))
continue;
coordQueue.push_back(neighborCoord);
}

coordQueue.pop_front();
}
}

Увидеть ? нет рекурсии, просто петля. Практически любую рекурсивную функцию можно развернуть в нечто подобное.

Если ваша базовая платформа ограничена, и у вас нет std :: queue, используйте вместо него массив (кольцевой буфер, реализованный как массив, может действовать как очередь fifo). Поскольку вы знаете размер платы, вы можете предварительно рассчитать размер массива. Остальное должно быть легко.

0