Multithreading the pathfinding in a tower defense game

Question

Hi, I'm making a tower defense game and I'm stuck at the multithreading of the pathfinding. If i don't make the pathfinding an NSInvocationOperation then there is an increasing pause in the rendering the more fiends and towers i have.

However i cannot solve the "locking" issue. I get frequent crashes about enumerating my fiend NSMutableArray while mutating it. If i instead try to lock the enumeration in the main thread while pathfinding is being done, the game still locks up and i have lost the whole point of the multithreading..

How do i solve this kind of issue?

Answer 1

Think about what happens when another tower is placed. Enemies will either have to consider the new tower in their path decision or not. Determining those new paths takes time, and collectively will cause a delay no matter what multithreading solution you choose. The problem ultimately lies in your path-finding algorithm. If it is taking too long to calculate then you're going to see that delay.

Take a look at ways you can avoid having to find those paths. Does dropping a tower at location (x,y) effect all enemies? Can you calculate only a few paths and enemies choose which one to follow? Can you cache paths and reuse parts that have already been calculated (like a how river flows with branching tributaries)?

I think there are many ways you can reduce the impact of path finding in your problem.

Answer 2

I agree with Tim Rupe that optimizing pathfinding would probably be helpful.

Another (additional) approach would be separate your 'current' array of paths from your 'next' array of paths. So, the game continues with the current array of paths, while the next array is being calculated in another thread. This avoid the deadlocking, crashing, etc.

Then, at some well-defined point, you swap in the 'next' for the 'current' (protected by a mutex or whatever). Basically, you are always dealing with snapshots - but you have control over the rate at which snapshots are swapped (provided your pathfinding algorithm is not too slow).

Answer 3

Threading would definitely help with delay tactics such as starting to move in the general direction before the path finding is complete.

Edit: I missed that you said it was your fiend array that was causing problems. I think your best bet is looser coupling. Try not to make the path finder dependent on your fiend array. Send it a copy of just the data it needs for one fiend (starting position, goal position, etc.) and get an array of points back. Don't give it access to the whole array or even a reference to any fiend object.

Answer 4

Sending mutable data across thread boundaries is a good recipe for problems. You should always use NSArray, NSString, NSSSet, etc, instead of their mutable subclass when sending an object to another thread. This simple rule makes multithreading so much more pleasant.

Thankfully all collection classes implements the NSCopying protocol and thus have a nifty -[copy] method that return s an immutable copy of itself.

Next thing you need to decide is what to do if you mutate the original array. Sould you:

1. Just enqueue a new pathfinder operation?
2. Discard the current pathfinder operation, and start a new?

Option 1. to just add a new operation is easiest, but may/will waste time if your original arrays are mutated frequently. Option 2. require some more work on your part. More specifically:

1. You must hold onto the last operation so that you can send a -[NSOperation cancel] message to it. Or alternatively if you have a queuededicated to only pathfinding that you can cancel all operations on it using [NSOperationQueue cancelAllOperations].
2. You should bail out early from your operations if they are cancelled. This requires you to subclass NSOperation, you can no longer just use NSInvocationOperation as-is.

Your NSOperation subclass implementation should look something like this:

@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