This is OShortestMoveTo.m in view mode; [Download] [Up]
//
// $Id: OShortestMoveTo.m,v 1.1 1997/10/28 05:11:45 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: OShortestMoveTo.m,v 1.1 1997/10/28 05:11:45 nygard Exp $");
#import "OShortestMoveTo.h"
#import "EmPlayer.h"
#import "Map.h"
#import "PathSegment.h"
#import "SNGraphNode.h"
#import "Unit.h"
//======================================================================
//
// This order go to great lengths to tr to move a unit to the new
// location in the shortest known path. Unknown territory is assumed
// to be crossable, until we find out otherwise. Other units are
// assumed to move out of the way before we get there. If a friendly
// unit is blocking us, (right in front of us, where we want to move),
// we try to move around. Support for moving to within a given number
// of squares of the destination is provided to help with the Escort
// Ship order.
//
// It's not perfect, but seems to do a pretty good job. It could be
// slow on really large maps.
//
// Note: This could take up large chunks of memory, especially as it
// is currently implemented. It never released the graph nodes
// from the breadth first search. Instead, it keeps them around
// and recycles them for the next time.
//
//======================================================================
#define OShortestMoveTo_VERSION 1
@implementation OShortestMoveTo
+ (void) initialize
{
if (self == [OShortestMoveTo class])
{
[self setVersion:OShortestMoveTo_VERSION];
}
}
//----------------------------------------------------------------------
- initForUnit:(Unit *)aUnit moveToLocation:(EMMapLocation)newLocation onMap:(Map *)thisMap
{
EMMapSize mapSize = [thisMap mapSize];
int l;
[super initForUnit:aUnit moveToLocation:newLocation onMap:map];
map = thisMap;
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];
movementType = 0;
if (unit != nil)
movementType = [unit movementType];
[self doBFSFromLocation:[unit unitLocation]];
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];
}
//----------------------------------------------------------------------
- copyWithZone:(NSZone *)zone
{
OShortestMoveTo *theCopy = [[OShortestMoveTo allocWithZone:zone] initForUnit:unit
moveToLocation:destination
onMap:map];
return theCopy;
}
//----------------------------------------------------------------------
- (NSString *) orderText
{
return [NSString stringWithFormat:@"Move(s) to %d,%d", destination.row, destination.column];
}
//----------------------------------------------------------------------
- (void) aboutToMove
{
if (blockedCount < 3)
[self unblocked];
}
//----------------------------------------------------------------------
- (Direction) nextMove
{
return [self nextMoveWithin:0];
}
//----------------------------------------------------------------------
- (Direction) nextMoveWithin:(int)distance;
{
Direction dir = d_none;
EMMapLocation unitLocation;
SNGraphNode *node, *predecessor;
unitLocation = [unit unitLocation];
node = nodePointers[unitLocation.row][unitLocation.column];
if (node != nil && [node distance] > distance)
{
predecessor = [node predecessor];
if (predecessor != nil)
{
Direction deltaToDir[9] = {d_northwest, d_north, d_northeast, d_west, d_none, d_east, d_southwest, d_south, d_southeast};
EMMapLocation predecessorLocation = [predecessor nodeLocation];
if (blockedCount != 2 || EMIconComponent ([map tokenAtLocation:predecessorLocation]) == i_none)
{
int delta_row = predecessorLocation.row - unitLocation.row;
int delta_col = predecessorLocation.column - unitLocation.column;
dir = deltaToDir[3 * (delta_row + 1) + delta_col + 1];
}
else
{
[unit skipMove];
dir = d_none;
}
}
}
return dir;
}
//----------------------------------------------------------------------
- (BOOL) isTooClose:(int)distance
{
EMMapLocation unitLocation;
SNGraphNode *node;
unitLocation = [unit unitLocation];
node = nodePointers[unitLocation.row][unitLocation.column];
return (node != nil) && [node distance] < distance;
}
//----------------------------------------------------------------------
- (BOOL) wasBlocked
{
EMMapLocation unitLocation = [unit unitLocation];
SNGraphNode *node;
blockedCount++;
// First time, just try to find the shortest path again.
// Second time, maybe we're blocked by our own unit in an
// adjacent square -- make sure there is a path (ignoring
// blocking by adjacent units. If there is, skip move.
// First time, reset and check to make sure there is a path.
// - if there wasn't, reset (ignoring blocking by adjacent
// units),
if (blockedCount == 1)
{
[self reset];
node = nodePointers[unitLocation.row][unitLocation.column];
if (node == nil)
{
blockedCount++;
}
}
if (blockedCount == 2)
{
[self reset];
node = nodePointers[unitLocation.row][unitLocation.column];
}
if (blockedCount == 3)
[unit skipMove];
return blockedCount < 4;
}
//----------------------------------------------------------------------
//
// 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
{
SNGraphNode *node = nil;
Player thisPlayer = [unit playerNumber];
EMMapSize mapSize = [map mapSize];
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.
// Isn't this an interesting piece of code?
if ((terrain == t_city && player == thisPlayer)
|| ((movementType & WATER_UNIT) != 0 && terrain == t_water
&& (icon == i_none || target.row < unitLocation.row - 1 || target.row > unitLocation.row + 1
|| target.column < unitLocation.column - 1 || target.column > unitLocation.column + 1 || blockedCount == 2))
|| ((movementType & LAND_UNIT) != 0 && terrain == t_land
&& (icon == i_none || target.row < unitLocation.row - 1 || target.row > unitLocation.row + 1
|| target.column < unitLocation.column - 1 || target.column > unitLocation.column + 1 || blockedCount == 2))
|| explored == NO
|| (target.row == destination.row && target.column == destination.column)
|| (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 breadth first search until it finds a path to the
// target location. It builds up the graph nodes that give us the
// information about the path.
//
//----------------------------------------------------------------------
- (void) doBFSFromLocation:(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;
NSMutableArray *nodeQueue = [NSMutableArray array];
node = [self nodeAtLocation:destination];
[node setDistance:0];
[nodeQueue addObject:node];
while ([nodeQueue count] > 0)
{
node = [nodeQueue objectAtIndex:0];
location = [node nodeLocation];
if (location.row == target.row && location.column == target.column)
break;
for (l = 0; l < 8; l++)
{
EMMapLocation newLocation;
newLocation.row = location.row + row_deltas[l];
newLocation.column = location.column + col_deltas[l];
adj = [self nodeAtLocation:newLocation];
if (adj != nil && adj != node && [adj nodeColor] == c_white)
{
[adj setNodeColor:c_gray];
[adj setPredecessor:node];
[nodeQueue addObject:adj];
}
}
[node setNodeColor:c_black];
[nodeQueue removeObjectAtIndex:0];
}
[nodeQueue removeAllObjects];
}
//----------------------------------------------------------------------
- (void) reset
{
EMMapSize mapSize;
int count;
int l;
EMMapLocation location;
mapSize = [map mapSize];
count = mapSize.width * mapSize.height;
for (l = 0; l < count; l++)
{
SNRelease (nodes[l]);
}
movementType = 0;
if (unit != nil)
movementType = [unit movementType];
location = [unit unitLocation];
[self doBFSFromLocation:location];
}
//----------------------------------------------------------------------
//
// This generates paths from the search for the shortest path. It's
// and interesting debugging tool.
//
//----------------------------------------------------------------------
- (NSArray *) pathsForMapView:(MapView *)mapView
{
NSMutableArray *array = [NSMutableArray array];
EMMapSize mapSize = [map mapSize];
EMMapLocation location;
SNGraphNode *node, *predecessor;
for (location.row = 0; location.row < mapSize.height; location.row++)
{
for (location.column = 0; location.column < mapSize.width; location.column++)
{
node = nodePointers[location.row][location.column];
if (node != nil)
{
predecessor = [node predecessor];
if (predecessor != nil)
{
PathSegment *pathSegment = [[[PathSegment alloc] initPathFromLocation:[node nodeLocation]
toLocation:[predecessor nodeLocation]
in:mapView] autorelease];
[array addObject:pathSegment];
}
}
}
}
return array;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.