//
// $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
