So I promised some custom NSDictionary key code and here it is. For those of you not in the know, I’m using A* Pathing for my monsters. For a game like this, A* Pathing is really easy. I have a 10×10 grid of 32×32 squares, so it’s not like I’m Pathing across the entire 320×320 pixel map – just a smaller grid representation of it.
I happen to think that a 150-line implementation of A*Pathing is pretty sweet, considering I don’t have a CS degree or anything outside of self-taught coding skills. I rely on some iOS 4 features, blocks, and custom NSDictionary Keys. It’s pretty slick I think.
Code is after the jump (so as not to clutter you up!) but the jist of it is, by creating and using my own custom NSKey (which is mutable 😀 ) the new while-loop creates NO objects, while the old loop creates 13 objects per cycle. A vast improvement when we’re talking about an ‘n’ of 100 or so!
- (BOOL) discoverPathInMap:(TDMap*)map { NSLog(@"Making a Path"); // Use A* Pathing self.path = [[NSMutableDictionary alloc] initWithCapacity:[map mapSize]/2]; heuristic = 0.0f; valid = NO; int count = 0;// // Create Piles // NSMutableDictionary *openPile = [[NSMutableDictionary alloc] initWithCapacity:[map mapSize]/4]; // For Consideration NSMutableDictionary *closedPile = [[NSMutableDictionary alloc] initWithCapacity:[map mapSize]/2]; // For Certain TDPoint *c = [[TDPoint alloc] init]; TDPoint *n = [[TDPoint alloc] init]; TDPoint *s = [[TDPoint alloc] init]; TDPoint *e = [[TDPoint alloc] init]; TDPoint *w = [[TDPoint alloc] init]; TDStep *current = nil; TDStep *next = nil; current = [TDStep stepWithLocation:_start andParent:nil]; [closedPile setObject:current forKey:current]; while (!valid) { count ++; //if (count > 100) break; NSLog(@"Consideration: %d - %@",count, current); // NSLog(@"Current: %@", [current description]); // Consider points in cardinal directions (North, South, East, West) c.q = current.q; c.r = current.r; n.q = c.q; n.r = c.r+1; s.q = c.q; s.r = c.r-1; e.q = c.q+1; e.r = c.r; w.q = c.q-1; w.r = c.r; // Block (unrolls a foreach loop over the above points) TDStep* (^testDirection)(TDPoint*) = ^(TDPoint* pt){ TDStep *testStep = nil; if ([map hasLocationAtPoint:pt] && !([openPile hasStepWithPt:pt] || [closedPile hasStepWithPt:pt])) { TDLocation *location = [map locationAtPoint:pt]; if (location.passable) { testStep = [TDStep stepWithLocation:pt andParent:current]; //NSLog(@"Testing Dir: %@ in Locatin: %@ at Step: %@ from Current: %@", pt, location, testStep, current); testStep.heuristic = [testStep distanceToPoint:_end]; [openPile setObject:testStep forKey:testStep]; } } return testStep; }; // Test if N,S,E,W are viable steps to take. if so, add to open pile. TDStep *north = testDirection(n); TDStep *south = testDirection(s); TDStep *east = testDirection(e); TDStep *west = testDirection(w); // Find "Best" next candidate float testH = CGFLOAT_MAX; if (isValid(south)){// && (south.heuristic < testH || !isValid(North))) { testH = south.heuristic; next = south; } if (isValid(west)){// && (west.heuristic < testH || !isValid(West))) { testH = west.heuristic; next = west; } if (isValid(east)){// && (east.heuristic < testH || !isValid(South))) { testH = east.heuristic; next = east; } if (isValid(north)){// && north.heuristic < testH) { testH = north.heuristic; next = north; } if (next != nil) { // Next Best Step Chosen //count = 0; heuristic += testH; [closedPile setObject:next forKey:next]; [openPile removeObjectForKey:next]; valid = [next isEqual:_end]; } else if ([openPile count] == 0) { // No more steps to take - path impossible; NSLog(@"No More Steps: Open %@, Closed %@, Map %@", openPile, closedPile, GlobalMap); valid = NO; break; } else { // No Best Step From current next = [[openPile allValues] lastObject]; [openPile removeObjectForKey:next]; NSLog(@"No best candidate. openPile: %d, closedPile: %d", [openPile count], [closedPile count]); } // Setup Next Iteration current = next; next = nil; } //NSLog(@"Closed: %@", closedPile); if (valid) { // Build the Walkable Path by tracing back up from end. TDStep *final = [closedPile objectForKey:_end]; //NSLog(@"Path: %@", [final description]); [self setPoint:final withDestination:(TDPoint*)[NSNull null]]; TDStep *walkUp = final; while (isValid(walkUp.parent)) { [self setPoint:[TDPoint pointWithTDLocation:walkUp.parent] withDestination:[TDPoint pointWithTDLocation:walkUp]]; walkUp = walkUp.parent; } NSLog(@"%@", [self description]); } else { NSLog(@"Invalid Path: %@", [self description]); } [openPile release]; [closedPile release]; [c release]; [n release]; [e release]; [s release]; [w release];return valid; }
So i think that’s pretty darn eloquent if I must say so myself! Tight, clear, concise. Just the way code should be. Below is the same bit of code, but doesn’t have the advantage of what I’ve learned in Obj-C/Cocoa/iOS over the past month since changing day jobs:
- (id) initWithMap:(SFMap *)map start:(CGPoint) start end:(CGPoint) end
{
if ((self = [super init])) {
_path = [[NSMutableDictionary alloc] initWithCapacity:[map mapSize]/2];
_valid = NO;
_pathHeuristic = 0.0f;
_name = [NSStringFromCGPoint(start) stringByAppendingString:NSStringFromCGPoint(end)];
// A* Pathing
NSMutableDictionary *openPile = [NSMutableDictionary dictionaryWithCapacity:[map mapSize]/2]; // for consideration
NSMutableDictionary *closedPile = [NSMutableDictionary dictionaryWithCapacity:[map mapSize]/2]; // for certain
CGPoint c,n,s,e,w;
SFStep *curStep;
SFStep *nextStep;
[closedPile setValue:[SFStep stepWithLocation:start parent:nil andHeuristic:0.0f]
forKey:NSStringFromCGPoint(start)];
curStep = [closedPile valueForKey:NSStringFromCGPoint(start)];
while (!self.isValid) {
nextStep = nil; // clear
c = curStep.location; // +
n = CGPointMake(c.x, c.y+1.0f); // ^
s = CGPointMake(c.x, c.y-1.0f); // v
e = CGPointMake(c.x+1.0f, c.y); // >
w = CGPointMake(c.x-1.0f, c.y); // <
// Block (unrolls a foreach loop over the above points)
SFStep* (^testDirection)(CGPoint) = ^(CGPoint pt){
SFStep *testStep = nil;
if ([map hasLocation:pt] && !([openPile hasStepWithPt:pt] || [closedPile hasStepWithPt:pt])) {
if ( ![map getLocation:pt].isBlocking) {
testStep = [SFStep stepWithLocation:pt parent:curStep andHeuristic:[[map getLocation:pt] heuristicsToPoint:end]];
[openPile setValue:testStep forKey:NSStringFromCGPoint(pt)];
}
}
return testStep;
};
SFStep *north = testDirection(n);
SFStep *south = testDirection(s);
SFStep *east = testDirection(e);
SFStep *west = testDirection(w);
// Find "Best" next candidate
float heuristic;
if (north && ![map getLocation:n].isBlocking) {
heuristic = north.heuristic;
nextStep = north;
}
if (south && ![map getLocation:s].isBlocking) {
heuristic = south.heuristic;
nextStep = south;
}
if (east && ![map getLocation:e].isBlocking) {
heuristic = east.heuristic;
nextStep = east;
}
if (west && ![map getLocation:w].isBlocking) {
heuristic = west.heuristic;
nextStep = west;
}
if (nextStep != nil) {
// Just for fun, usable with Path Cache
_pathHeuristic += heuristic;
// have a valid next step, add to certain and remove from consideration
[closedPile setValue:nextStep forKey:NSStringFromCGPoint(nextStep.location)];
[openPile removeObjectForKey:NSStringFromCGPoint(nextStep.location)];
// Test End Condition if we had a shortest from this batch.
if (((int)end.x == (int)nextStep.location.x) &&
((int)end.y == (int)nextStep.location.y)) _valid = YES;
} else if ([openPile count] == 0) {
// NO CANDIDATES, NO PATH
return nil;
} else {
// no valid next step, test "last" and remove from consideration (to not test again)
nextStep = [[openPile allValues] lastObject];
[openPile removeObjectForKey:NSStringFromCGPoint(nextStep.location)];
//[openPile removeObjectForKey:NSStringFromCGPoint(nextStep.location)];
NSLog(@"no best candidate. openPile: %d, closedPile: %d", [openPile count], [closedPile count]);
}
// Set for Next Loop
curStep = nextStep;
}
//Build the walkable path by back tracing from the end.
SFStep *realStep = [closedPile valueForKey:NSStringFromCGPoint(end)];
[_path setValue:SFFinal forKey:NSStringFromCGPoint(realStep.location)];
while ([realStep parent] != nil) {
//NSLog(@"Step: %@ Parent: %@",NSStringFromCGPoint(realStep.location), NSStringFromCGPoint(realStep.parent.location));
[self setPoint:realStep.parent.location withDestination: realStep.location];
realStep = [realStep parent];
}
}
return self;
}“Sure,” you say, “this implementation is 50 lines smaller!” LoC is not what’s important here. Look again. Notice how many times NSStringFromCGPoint() is called? Within both loops, I count about 9 times. Also, count how many times CGPointMake() is called? 4 Times.
In the previous bit of code, how many creation methods are called? (Outside of TDStep/SFStep…) How about none?
So the second block of code calls 13x the Memory Allocation methods during the operation than the first one does. (Step creation is unavoidable, I believe) That means it runs FAR more inefficiently. It allocates and releases 13 more objects per iteration… which is one of the most costly operations in this algorithm. 13x!!! That’s like O(13n) vs O(n). Now, asymptotically for 1,000,000 iterations 13x isn’t significant – but since there’s only 100 squares, it’s like comparing 1300 to 100… which is an order of magnitude faster! if each iteration took 1ms, then the new algorithm could run 10x a second, while the old one runs once every 1.3 seconds.
So it’s muuuuuuuch better!
