This is PathFinder.m in view mode; [Download] [Up]
//
// This file is a part of Risk by Mike Ferris.
// Copyright (C) 1997 Steve Nygard
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
// You may contact the author by:
// e-mail: nygard@telusplanet.net
//
#import "../Risk.h"
RCSID ("$Id: PathFinder.m,v 1.1.1.1 1997/12/09 07:19:16 nygard Exp $");
#import "PathFinder.h"
#import "Country.h"
#import "RiskWorld.h"
#import "SNHeap.h"
#import "DNode.h"
#import "SNUtility.h"
NSComparisonResult PFCompareDistances (id country1, id country2, void *context)
{
NSDictionary *nodeDictionary;
NSString *name1, *name2;
int distance1, distance2;
NSComparisonResult result;
nodeDictionary = (NSDictionary *)context;
name1 = [(Country *)country1 countryName];
name2 = [(Country *)country2 countryName];
distance1 = [[nodeDictionary objectForKey:name1] distance];
distance2 = [[nodeDictionary objectForKey:name2] distance];
if (distance1 < distance2)
result = NSOrderedAscending;
else if (distance1 == distance2)
{
int troopCount1, troopCount2;
// Choose country with fewest troops.
troopCount1 = [(Country *)country1 troopCount];
troopCount2 = [(Country *)country2 troopCount];
if (troopCount1 < troopCount2)
{
result = NSOrderedAscending;
//NSLog (@"<");
}
else if (troopCount1 == troopCount2)
{
result = NSOrderedSame;
//NSLog (@"==");
}
else
{
result = NSOrderedDescending;
//NSLog (@">");
}
if (result == NSOrderedAscending)
{
NSCAssert (troopCount1 < troopCount2, @"troopCount1 >= troopCount2");
}
else if (result == NSOrderedSame)
{
NSCAssert (troopCount1 == troopCount2, @"troopCount1 != troopCount2");
}
else
{
NSCAssert (troopCount1 > troopCount2, @"troopCount1 <= troopCount2");
}
}
else
result = NSOrderedDescending;
return result;
}
//----------------------------------------------------------------------
int PFConstantDistance (Country *country1, Country *country2)
{
return 1;
}
//----------------------------------------------------------------------
BOOL PFCountryForPlayer (Country *country, void *context)
{
BOOL flag;
Player number;
number = (Player)context;
flag = [country playerNumber] == number;
return flag;
}
//----------------------------------------------------------------------
BOOL PFCountryForPlayerHasEnemyNeighbors (Country *country, void *context)
{
BOOL flag;
Player number;
number = (Player)context;
if ([country playerNumber] == number && [[country enemyNeighborCountries] count] > 0)
flag = YES;
else
flag = NO;
return flag;
}
//======================================================================
@implementation PathFinder
+ shortestPathInRiskWorld:(RiskWorld *)aWorld
fromCountry:(Country *)source
forCountries:(BOOL (*)(Country *, void *))anIsCountryAcceptableFunction
context:(void *)aContext
distanceFunction:(int (*)(Country *, Country *))aDistanceFunction
{
return [[[PathFinder alloc] initWithRiskWorld:aWorld
fromCountry:source
forCountries:anIsCountryAcceptableFunction
context:aContext
distanceFunction:aDistanceFunction] autorelease];
}
//----------------------------------------------------------------------
- initWithRiskWorld:(RiskWorld *)aWorld
fromCountry:(Country *)source
forCountries:(BOOL (*)(Country *, void *))anIsCountryAcceptableFunction
context:(void *)aContext
distanceFunction:(int (*)(Country *, Country *))aDistanceFunction
{
[super init];
acceptableCountries = [[NSMutableSet set] retain];
nodeDictionary = [[NSMutableDictionary dictionary] retain];
isCountryAcceptable = anIsCountryAcceptableFunction;
context = aContext;
distanceFunction = aDistanceFunction;
world = [aWorld retain];
[self _buildShortestPathsFromCountry:source];
return self;
}
//----------------------------------------------------------------------
- (void) dealloc
{
[acceptableCountries release];
[nodeDictionary release];
[world release];
[super dealloc];
}
//----------------------------------------------------------------------
- (void) _buildShortestPathsFromCountry:(Country *)source
{
NSSet *allCountries;
NSEnumerator *countryEnumerator, *neighborEnumerator;
Country *country, *neighbor;
DNode *node;
SNHeap *countryHeap;
[nodeDictionary removeAllObjects];
[acceptableCountries removeAllObjects];
allCountries = [world allCountries];
// Build acceptable countries.
countryEnumerator = [allCountries objectEnumerator];
while (country = [countryEnumerator nextObject])
{
if (isCountryAcceptable (country, context) == YES)
{
[acceptableCountries addObject:country];
node = [DNode dNode];
[nodeDictionary setObject:node forKey:[country countryName]];
}
}
node = [nodeDictionary objectForKey:[source countryName]];
[node setDistance:0];
countryHeap = [SNHeap heapUsingFunction:PFCompareDistances context:nodeDictionary];
countryEnumerator = [acceptableCountries objectEnumerator];
while (country = [countryEnumerator nextObject])
{
[countryHeap insertObject:country];
}
while (country = [countryHeap extractObject])
{
neighborEnumerator = [[country ourNeighborCountries] objectEnumerator];
while (neighbor = [neighborEnumerator nextObject])
{
int tmp;
tmp = [[nodeDictionary objectForKey:[country countryName]] distance] + distanceFunction (country, neighbor);
if ([[nodeDictionary objectForKey:[neighbor countryName]] distance] > tmp)
{
[[nodeDictionary objectForKey:[neighbor countryName]] setDistance:tmp withPrevious:country];
//[countryHeap heapifyFromObject:neighbor];
[countryHeap removeObject:neighbor];
[countryHeap insertObject:neighbor];
}
}
}
}
//----------------------------------------------------------------------
- (SNHeap *) _minimumDistanceCountryHeap
{
SNHeap *countryHeap;
NSEnumerator *countryEnumerator;
Country *country;
countryHeap = [SNHeap heapUsingFunction:PFCompareDistances context:nodeDictionary];
countryEnumerator = [acceptableCountries objectEnumerator];
while (country = [countryEnumerator nextObject])
{
[countryHeap insertObject:country];
}
return countryHeap;
}
//----------------------------------------------------------------------
- (NSArray *) shortestPathToCountry:(Country *)target
{
NSMutableArray *path1, *path2;
DNode *node;
Country *previous;
NSEnumerator *objectEnumerator;
id object;
path1 = [NSMutableArray array];
path2 = [NSMutableArray array];
//NSLog (@"target: %@", target);
[path1 addObject:target];
node = [nodeDictionary objectForKey:[target countryName]];
while (previous = [node previous])
{
[path1 addObject:previous];
target = previous;
node = [nodeDictionary objectForKey:[target countryName]];
}
objectEnumerator = [path1 reverseObjectEnumerator];
while (object = [objectEnumerator nextObject])
{
[path2 addObject:object];
}
//NSLog (@"Initial path is: %@", path2);
// Remove first object? It should be the source.
if ([path2 count] > 0)
{
[path2 removeObjectAtIndex:0];
}
return path2;
}
//----------------------------------------------------------------------
- (NSArray *) shortestPathToAcceptableCountry:(BOOL (*)(Country *, void *))isCountryAcceptableTarget context:(void *)aContext
{
SNHeap *countryHeap;
Country *country;
NSArray *path;
path = nil;
countryHeap = [self _minimumDistanceCountryHeap];
while (country = [countryHeap extractObject])
{
if (isCountryAcceptableTarget (country, aContext) == YES)
{
path = [self shortestPathToCountry:country];
break;
}
}
return path;
}
//----------------------------------------------------------------------
- (Country *) firstStepToCountry:(Country *)target
{
NSArray *path;
Country *first;
path = [self shortestPathToCountry:target];
if ([path count] > 0)
first = [path objectAtIndex:0];
else
first = nil;
return first;
}
//----------------------------------------------------------------------
- (Country *) firstStepToAcceptableCountry:(BOOL (*)(Country *, void *))isCountryAcceptableTarget context:(void *)aContext
{
NSArray *path;
Country *first;
path = [self shortestPathToAcceptableCountry:isCountryAcceptableTarget context:aContext];
//NSLog (@"path is: %@", path);
if ([path count] > 0)
first = [path objectAtIndex:0];
else
first = nil;
#if 0
if (first == nil)
{
NSLog (@"path is: %@", path);
}
#endif
return first;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.