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