Многопоточность поиска пути в игре Tower Defense

Question

Я делаю игру Tower Defense, и я застрял в многопоточности поиска пути. Если я не определяю поиск пути как NSInvocationOperation, то при рендеринге увеличивается пауза, тем больше у меня друзей и башен.

Однако я не могу решить проблему "блокировки". Я получаю частые сбои при перечислении моего друга NSMutableArray при его изменении. Если вместо этого я попытаюсь заблокировать перечисление в основном потоке во время поиска пути, игра все равно будет заблокирована, и я потерял весь смысл многопоточности.

Как мне решить эту проблему?

Answer 1

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

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

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

Answer 2

Отправка изменяемых данных через границы потоков - хороший способ решения проблем. Вы должны всегда использовать NSArray, NSString, NSSSet и т. Д. Вместо их изменяемого подкласса при отправке объекта в другой поток. Это простое правило делает многопоточность намного приятнее.

К счастью, все классы коллекции реализуют протокол NSCopying и, таким образом, имеют отличный метод -[copy], который возвращает неизменную копию самого себя.

Следующее, что вам нужно решить, это что делать, если вы изменяете исходный массив. Не могли бы вы:

1. Просто поставить в очередь новую операцию поиска пути?
2. Отменить текущую операцию поиска пути и начать новую?

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

1. Вы должны удержать последнюю операцию, чтобы отправить ей сообщение -[NSOperation cancel]. Или, если у вас есть очередь, предназначенная только для поиска пути, вы можете отменить все операции над ней, используя [NSOperationQueue cancelAllOperations].
2. Вы должны выйти из операции на ранней стадии, если она будет отменена. Это требует от вас подкласса NSOperation, вы больше не можете просто использовать NSInvocationOperation как есть.

Ваша реализация подкласса NSOperation должна выглядеть примерно так:

@implementation CWPathfinderOperation

-(id)initWithFiends:(NSArray*)fiends delegate:(id<CWPathfinderOperation>)delegate {
    self = [super init];
    if (self) {
        self.fiends = fiends;
        self.delegate = delegate;
    }
    return self;
}

-(void)main {
    NSAutoreleasePool* pool = [[NSAutoreleasePool alloc] init];
    while (notDone) {
        if ([self isCancelled]) goto bailOut;
        // Do smallpart of work
    }
    [self.delegate performSelectorOnMainThread:@selector(pathfinderOperatioDidFindPaths:)
                                    withObject:result
                                 waitUntilDone:NO];
bailOut:
    [pool release];
}
@end

Answer 3

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

Редактировать: я пропустил, что вы сказали, что ваш массив демонов вызывал проблемы.Я думаю, что ваш лучший выбор - более слабая связь.Старайтесь не делать поиск пути зависимым от вашего массива демонов.Отправьте ему копию только данных, которые ему нужны для одного изверга (начальная позиция, позиция цели и т. Д.), И верните массив точек назад.Не предоставляйте ему доступ ко всему массиву или даже к ссылке на любой объект демона.

Answer 4

Я согласен с Тимом Рупом в том, что оптимизация поиска пути, вероятно, была бы полезной.

Другой (дополнительный) подход будет отделять ваш «текущий» массив путей от вашего «следующего» массива путей.Итак, игра продолжается с текущим массивом путей, а следующий массив вычисляется в другом потоке.Это позволяет избежать взаимоблокировок, сбоев и т. Д.

Затем в какой-то четко определенной точке вы меняете «следующее» на «текущее» (защищенное мьютексом или чем-то еще).По сути, вы всегда имеете дело со снимками - но вы можете контролировать скорость, с которой меняются снимки (при условии, что алгоритм поиска пути не слишком медленный).