This is OExplore.m in view mode; [Download] [Up]
//
// $Id: OExplore.m,v 1.1 1997/10/28 05:11:25 nygard Exp $
//
//
// This file is a part of Empire, a game of exploration and conquest.
// Copyright (C) 1996 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 "Empire.h"
RCSID ("$Id: OExplore.m,v 1.1 1997/10/28 05:11:25 nygard Exp $");
#import "OExplore.h"
#import "SNHeap.h"
#import "SNGraphNode.h"
#import "Map.h"
#import "OShortestMoveTo.h"
#import "Unit.h"
//======================================================================
// Comparison functions for maintaining a heap.
//======================================================================
//----------------------------------------------------------------------
//
// This compares the distance between two nodes. If they are the same
// distance away, the one closest to the given origin point will be
// used to break the tie.
//
//----------------------------------------------------------------------
NSComparisonResult compare_distance (id object1, id object2, void *context)
{
EMMapLocation *origin = (EMMapLocation *)context;
int d1, d2;
NSCParameterAssert (object1 != nil);
NSCParameterAssert (object2 != nil);
NSCParameterAssert (context != NULL);
d1 = [object1 distance];
d2 = [object2 distance];
if (d1 < d2)
{
return NSOrderedAscending;
}
else if (d1 == d2)
{
d1 = EMDistanceBetweenLocations ([object1 nodeLocation], *origin);
d2 = EMDistanceBetweenLocations ([object2 nodeLocation], *origin);
if (d1 < d2)
{
return NSOrderedAscending;
}
else if (d1 == d2)
{
return NSOrderedSame;
}
else
{
return NSOrderedDescending;
}
}
return NSOrderedDescending;
}
//----------------------------------------------------------------------
//
// This compares the distance between two nodes.
//
//----------------------------------------------------------------------
NSComparisonResult compare_distance1 (id object1, id object2, void *context)
{
int d1, d2;
NSCParameterAssert (object1 != nil);
NSCParameterAssert (object2 != nil);
d1 = [object1 distance];
d2 = [object2 distance];
if (d1 < d2)
{
return NSOrderedAscending;
}
else if (d1 == d2)
{
return NSOrderedSame;
}
return NSOrderedDescending;
}
//======================================================================
//
// This instructs the unit to explore unexplored territory. It does
// this by finding the closest unexplored location and moving towards
// it.
//
// This implementation records the location of the unit when it
// received the order, and uses the distance from that as a tie breaker
// when two locations are equally distant. This tends to make the
// units explore the territory around the start point first.
//
// Without this bias, the unit tends to cut a path straight north,
// and then explore from there. This is because we are doing a breadth
// first search for the nearest unexplored territory, and we always
// deepen the search starting to the north.
//
//======================================================================
#define OExplore_VERSION 1
@implementation OExplore
+ (void) initialize
{
if (self == [OExplore class])
{
[self setVersion:OExplore_VERSION];
}
}
//----------------------------------------------------------------------
- initForUnit:(Unit *)aUnit explore:(Map *)aMap
{
EMMapSize mapSize;
int l;
[super initForUnit:aUnit];
map = aMap;
movementType = 0;
mapSize = [map mapSize];
startingLocation = [unit unitLocation];
nodes = (SNGraphNode **) malloc (sizeof (SNGraphNode *) * mapSize.width * mapSize.height);
NSAssert (nodes != NULL, @"Error malloc()'ing nodes");
nodePointers = (SNGraphNode ***) malloc (sizeof (SNGraphNode **) * mapSize.height);
NSAssert (nodePointers != NULL, @"Error malloc()'ing nodePointers");
for (l = 0; l < mapSize.width * mapSize.height; l++)
nodes[l] = nil;
for (l = 0; l < mapSize.height; l++)
nodePointers[l] = &nodes[l * mapSize.width];
[self reset];
return self;
}
//----------------------------------------------------------------------
- (void) dealloc
{
EMMapSize mapSize = [map mapSize];
int count = mapSize.width * mapSize.height;
int l;
if (nodePointers != NULL)
free (nodePointers);
for (l = 0; l < count; l++)
{
SNRelease (nodes[l]);
}
free (nodes);
[super dealloc];
}
//----------------------------------------------------------------------
- (NSString *) orderText
{
EMMapLocation target = [subOrder destination];
return [NSString stringWithFormat:@"Explore (%d,%d)", target.row, target.column];
}
//----------------------------------------------------------------------
- (void) aboutToMove
{
[subOrder aboutToMove];
}
//----------------------------------------------------------------------
- (Direction) nextMove
{
Direction dir;
if ([subOrder isOrderComplete] == YES
|| EMExploredComponent ([map tokenAtLocation:[subOrder destination]]) == YES)
{
SNRelease (subOrder);
[self reset];
}
dir = [subOrder nextMove];
return dir;
}
//----------------------------------------------------------------------
- (BOOL) wasBlocked
{
BOOL r;
blockedCount++;
r = [subOrder wasBlocked];
return r;
}
//----------------------------------------------------------------------
- (void) unblocked
{
[subOrder unblocked];
[super unblocked];
}
//----------------------------------------------------------------------
- (BOOL) isOrderComplete
{
if ([subOrder isOrderComplete] == YES)
{
SNRelease (subOrder);
[self reset];
}
return subOrder == nil;
}
//----------------------------------------------------------------------
- (void) reset
{
EMMapSize mapSize = [map mapSize];
int count = mapSize.width * mapSize.height;
int l;
for (l = 0; l < count; l++)
{
SNRelease (nodes[l]);
}
movementType = 0;
if (unit != nil)
movementType = [unit movementType];
[self findClosestToLocation:[unit unitLocation]];
}
//----------------------------------------------------------------------
//
// This lazily creates nodes for the given location. It returns nil
// if the location is off the map, or if the unit cannot move on the
// target terrain.
//
//----------------------------------------------------------------------
- (SNGraphNode *) nodeAtLocation:(EMMapLocation)target
{
EMMapSize mapSize = [map mapSize];
SNGraphNode *node = nil;
Player thisPlayer = [unit playerNumber];
if (target.row >= 0 && target.column >= 0 && target.row < mapSize.height && target.column < mapSize.width)
{
Terrain terrain;
Player player;
Icon icon;
BOOL explored;
EMMapLocation unitLocation = [unit unitLocation];
EMMapTokenComponents ([map tokenAtLocation:target], &terrain, &player, &icon, &explored);
// Not immediately blocked by units in adjacent squares, so ignore them.
if ((terrain == t_city && player == thisPlayer)
|| ((movementType & WATER_UNIT) != 0 && terrain == t_water)
|| ((movementType & LAND_UNIT) != 0 && terrain == t_land)
|| explored == NO
|| (target.row == unitLocation.row && target.column == unitLocation.column))
{
node = nodePointers[target.row][target.column];
if (node == nil)
{
node = [[SNGraphNode alloc] initWithLocation:target];
nodePointers[target.row][target.column] = node;
}
}
}
return node;
}
//----------------------------------------------------------------------
//
// This does the search until it finds a path to the nearest unexplored
// location. It builds up the graph nodes that give us the information
// about the path.
//
//----------------------------------------------------------------------
- (void) findClosestToLocation:(EMMapLocation)target
{
SNGraphNode *node, *adj;
EMMapLocation location;
int row_deltas[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
int col_deltas[8] = { 0, 1, 0, -1, -1, 1, 1, -1};
int l;
SNHeap *nodeQueue;
int distance;
nodeQueue = [SNHeap heapUsingFunction:compare_distance context:&startingLocation];
node = [self nodeAtLocation:target];
[node setDistance:0];
[nodeQueue insertObject:node];
if (subOrder != nil)
{
SNRelease (subOrder);
}
while ([nodeQueue count] > 0 && subOrder == nil)
{
node = [nodeQueue extractObject];
location = [node nodeLocation];
//startingLocation = [node biasValue];
for (l = 0; l < 8; l++)
{
EMMapLocation adjacentLocation = location;
adjacentLocation.row += row_deltas[l];
adjacentLocation.column += col_deltas[l];
adj = [self nodeAtLocation:adjacentLocation];
if (adj != nil && adj != node && [adj nodeColor] == c_white)
{
distance = EMDistanceBetweenLocations (startingLocation, adjacentLocation);
[adj setNodeColor:c_gray];
[adj setPredecessor:node];
[adj setBiasValue:distance];
[nodeQueue insertObject:adj];
if (EMExploredComponent ([map tokenAtLocation:adjacentLocation]) == NO)
{
subOrder = [[OShortestMoveTo alloc] initForUnit:unit moveToLocation:adjacentLocation onMap:map];
break;
}
}
}
//[node setNodeColor:c_black];
//[nodeQueue removeObjectAt:0];
}
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.