/******************************Module*Header*******************************\
* Module Name: node.cxx
*
* Pipes node array
*
* Copyright (c) 1995 Microsoft Corporation
*
\**************************************************************************/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <sys/types.h>
#include <time.h>
#include <windows.h>

#include "sspipes.h"
#include "node.h"


/**************************************************************************\
*
* NODE_ARRAY constructor
*
\**************************************************************************/

NODE_ARRAY::NODE_ARRAY()
{
    nodes = NULL; // allocated on Resize

    numNodes.x = 0;
    numNodes.y = 0;
    numNodes.z = 0;
}

/**************************************************************************\
*
* NODE_ARRAY destructor
*
\**************************************************************************/

NODE_ARRAY::~NODE_ARRAY( )
{
    if( nodes )
        delete nodes;
}

/**************************************************************************\
*
* Resize
*
\**************************************************************************/

void
NODE_ARRAY::Resize( IPOINT3D *pNewSize )
{
    if( (numNodes.x == pNewSize->x) &&
        (numNodes.y == pNewSize->y) &&
        (numNodes.z == pNewSize->z) )
        return;

    numNodes = *pNewSize;

    int elemCount = numNodes.x * numNodes.y * numNodes.z ;

    if( nodes )
        delete nodes;

    nodes = new Node[elemCount];

    SS_ASSERT( nodes, "NODE_ARRAY::Resize : can't alloc nodes\n" );

    // Reset the node states to empty

    int i;
    Node *pNode = nodes;
    for( i = 0; i < elemCount; i++, pNode++ )
        pNode->MarkAsEmpty();

    // precalculate direction offsets between nodes for speed
    nodeDirInc[PLUS_X] = 1;
    nodeDirInc[MINUS_X] = -1;
    nodeDirInc[PLUS_Y] = numNodes.x;
    nodeDirInc[MINUS_Y] = - nodeDirInc[PLUS_Y];
    nodeDirInc[PLUS_Z] = numNodes.x * numNodes.y;
    nodeDirInc[MINUS_Z] = - nodeDirInc[PLUS_Z];
}

/**************************************************************************\
*
* Reset
*
\**************************************************************************/

void
NODE_ARRAY::Reset( )
{
    int i;
    Node *pNode = nodes;

    // Reset the node states to empty
    for( i = 0; i < (numNodes.x)*(numNodes.y)*(numNodes.z); i++, pNode++ )
        pNode->MarkAsEmpty();
}

/**************************************************************************\
*
* GetNodeCount
*
\**************************************************************************/

void
NODE_ARRAY::GetNodeCount( IPOINT3D *count )
{
    *count = numNodes;
}

/**************************************************************************\
*
* ChooseRandomDirection
*
* Choose randomnly among the possible directions.  The likelyhood of going
* straight is controlled by weighting it.
*
\**************************************************************************/

int 
NODE_ARRAY::ChooseRandomDirection( IPOINT3D *pos, int dir, int weightStraight )
{
    Node *nNode[NUM_DIRS];
    int numEmpty, newDir;
    int choice;
    Node *straightNode = NULL;
    int emptyDirs[NUM_DIRS];

    SS_ASSERT( (dir >= 0) && (dir < NUM_DIRS), 
            "NODE_ARRAY::ChooseRandomDirection: invalid dir\n" );

    // Get the neigbouring nodes
    GetNeighbours( pos, nNode );

    // Get node in straight direction if necessary
    if( weightStraight && nNode[dir] && nNode[dir]->IsEmpty() ) {
        straightNode = nNode[dir];
        // if maximum weight, choose and return
        if( weightStraight == MAX_WEIGHT_STRAIGHT ) {
            straightNode->MarkAsTaken();
            return dir;
        }
    } else
        weightStraight = 0;

    // Get directions of possible turns
    numEmpty = GetEmptyTurnNeighbours( nNode, emptyDirs, dir );

    // Make a random choice
    if( (choice = (weightStraight + numEmpty)) == 0 )
        return DIR_NONE;
    choice = ss_iRand( choice );

    if( choice < weightStraight ) {
        straightNode->MarkAsTaken();
        return dir;
    } else {
        // choose one of the turns
        newDir = emptyDirs[choice - weightStraight];
        nNode[newDir]->MarkAsTaken();
        return newDir;
    }
}

/**************************************************************************\
*
* ChoosePreferredDirection
*
* Choose randomnly from one of the supplied preferred directions.  If none
* of these are available, then try and choose any empty direction
*
\**************************************************************************/

int 
NODE_ARRAY::ChoosePreferredDirection( IPOINT3D *pos, int dir, int *prefDirs,
                                      int nPrefDirs )
{
    Node *nNode[NUM_DIRS];
    int numEmpty, newDir;
    int emptyDirs[NUM_DIRS];
    int *pEmptyPrefDirs;
    int i, j;

    SS_ASSERT( (dir >= 0) && (dir < NUM_DIRS), 
            "NODE_ARRAY::ChoosePreferredDirection : invalid dir\n" );

    // Get the neigbouring nodes
    GetNeighbours( pos, nNode );

    // Create list of directions that are both preferred and empty

    pEmptyPrefDirs = emptyDirs;
    numEmpty = 0;

    for( i = 0, j = 0; (i < NUM_DIRS) && (j < nPrefDirs); i++ ) {
        if( i == *prefDirs ) {
            prefDirs++;
            j++;
            if( nNode[i] && nNode[i]->IsEmpty() ) {
                // add it to list
                *pEmptyPrefDirs++ = i;
                numEmpty++;
            }
        }
    }

    // if no empty preferred dirs, then any empty dirs become preferred
    
    if( !numEmpty ) {
        numEmpty = GetEmptyNeighbours( nNode, emptyDirs );
        if( numEmpty == 0 )
            return DIR_NONE;
    }
                
    // Pick a random dir from the empty set

    newDir = emptyDirs[ss_iRand( numEmpty )];
    nNode[newDir]->MarkAsTaken();
    return newDir;
}

/**************************************************************************\
*
* FindClearestDirection
*
* Finds the direction with the most empty nodes in a line 'searchRadius'
* long.  Does not mark any nodes as taken.
*
\**************************************************************************/

int 
NODE_ARRAY::FindClearestDirection( IPOINT3D *pos )
{
    static Node *neighbNode[NUM_DIRS];
    static int emptyDirs[NUM_DIRS];
    int nEmpty, newDir;
    int maxEmpty = 0;
    int searchRadius = 3;
    int count = 0;
    int i;

    // Get ptrs to neighbour nodes

    GetNeighbours( pos, neighbNode );

    // find empty nodes in each direction

    for( i = 0; i < NUM_DIRS; i ++ ) {
        if( neighbNode[i] && neighbNode[i]->IsEmpty() )
        {
            // find number of contiguous empty nodes along this direction
            nEmpty = GetEmptyNeighboursAlongDir( pos, i, searchRadius );
            if( nEmpty > maxEmpty ) {
                // we have a new winner
                count = 0;
                maxEmpty = nEmpty;
                emptyDirs[count++] = i;
            }
            else if( nEmpty == maxEmpty ) {
                // tied with current max
                emptyDirs[count++] = i;
            }
        }
    }

    if( count == 0 )
        return DIR_NONE;

    // randomnly choose a direction
    newDir = emptyDirs[ss_iRand( count )];

    return newDir;
}
/**************************************************************************\
*
* ChooseNewTurnDirection
*
* Choose a direction to turn
*
* This requires finding a pair of nodes to turn through.  The first node
* is in the direction of the turn from the current node, and the second node
* is at right angles to this at the end position.  The prim will not draw
* through the first node, but may sweep close to it, so we have to mark it
* as taken.
*
* - if next node is free, but there are no turns available, return
*   DIR_STRAIGHT, so the caller can decide what to do in this case
* - The turn possibilities are based on the orientation of the current xc, with
*   4 relative directions to seek turns in.
\**************************************************************************/

int 
NODE_ARRAY::ChooseNewTurnDirection( IPOINT3D *pos, int dir )
{
    int turns[NUM_DIRS], nTurns;
    IPOINT3D nextPos;
    int newDir;
    Node *nextNode;

    SS_ASSERT( (dir >= 0) && (dir < NUM_DIRS), 
            "NODE_ARRAY::ChooseNewTurnDirection : invalid dir\n" );


    // First, check if next node along current dir is empty

    if( ! GetNextNodePos( pos, &nextPos, dir ) )
        return DIR_NONE; // node out of bounds or not empty

    // Ok, the next node is free - check the 4 possible turns from here

    nTurns = GetBestPossibleTurns( &nextPos, dir, turns );
    if( nTurns == 0 )
        return DIR_STRAIGHT; // nowhere to turn, but could go straight

    // randomnly choose one of the possible turns
    newDir = turns[ ss_iRand( nTurns ) ];

    SS_ASSERT( (newDir >= 0) && (newDir < NUM_DIRS), 
            "NODE_ARRAY::ChooseNewTurnDirection : invalid newDir\n" );

    // mark taken nodes

    nextNode = GetNode( &nextPos );
    nextNode->MarkAsTaken();

    nextNode = GetNextNode( &nextPos, newDir );
    nextNode->MarkAsTaken();

    return newDir;
}

/**************************************************************************\
*
* GetBestPossibleTurns
*
* From supplied direction and position, figure out which of 4 possible 
* directions are best to turn in.
*
* Turns that have the greatest number of empty nodes after the turn are the
* best, since a pipe is less likely to hit a dead end in this case.
* - We only check as far as 'searchRadius' nodes along each dir.
* - Return direction indices of best possible turns in turnDirs, and return 
*   count of these turns in fuction return value.
*
\**************************************************************************/

int 
NODE_ARRAY::GetBestPossibleTurns( IPOINT3D *pos, int dir, int *turnDirs )
{
    Node *neighbNode[NUM_DIRS]; // ptrs to 6 neighbour nodes
    int i, count = 0;
    BOOL check[NUM_DIRS] = {TRUE, TRUE, TRUE, TRUE, TRUE, TRUE};
    int nEmpty, maxEmpty = 0;
    int searchRadius = 2;

    SS_ASSERT( (dir >= 0) && (dir < NUM_DIRS), 
            "NODE_ARRAY::GetBestPossibleTurns : invalid dir\n" );

    GetNeighbours( pos, neighbNode );

    switch( dir ) {
        case PLUS_X:    
        case MINUS_X:
            check[PLUS_X] = FALSE;
            check[MINUS_X] = FALSE;
            break;
        case PLUS_Y:    
        case MINUS_Y:
            check[PLUS_Y] = FALSE;
            check[MINUS_Y] = FALSE;
            break;
        case PLUS_Z:    
        case MINUS_Z:
            check[PLUS_Z] = FALSE;
            check[MINUS_Z] = FALSE;
            break;
    }

    // check approppriate directions
    for( i = 0; i < NUM_DIRS; i ++ ) {
        if( check[i] && neighbNode[i] && neighbNode[i]->IsEmpty() )
        {
            // find number of contiguous empty nodes along this direction
            nEmpty = GetEmptyNeighboursAlongDir( pos, i, searchRadius );
            if( nEmpty > maxEmpty ) {
                // we have a new winner
                count = 0;
                maxEmpty = nEmpty;
                turnDirs[count++] = i;
            }
            else if( nEmpty == maxEmpty ) {
                // tied with current max
                turnDirs[count++] = i;
            }
        }
    }

    return count;
}


/**************************************************************************\
*
* GetNeighbours
*
* Get neigbour nodes relative to supplied position
*
*       - get addresses of the neigbour nodes,
*         and put them in supplied matrix
*       - boundary hits are returned as NULL
*
\**************************************************************************/

void 
NODE_ARRAY::GetNeighbours( IPOINT3D *pos, Node **nNode )
{
    Node *centerNode = GetNode( pos );

    nNode[PLUS_X]  = pos->x == (numNodes.x - 1) ? NULL : 
                                            centerNode + nodeDirInc[PLUS_X];
    nNode[PLUS_Y]  = pos->y == (numNodes.y - 1) ? NULL :
                                            centerNode + nodeDirInc[PLUS_Y];
    nNode[PLUS_Z]  = pos->z == (numNodes.z - 1) ? NULL : 
                                            centerNode + nodeDirInc[PLUS_Z];

    nNode[MINUS_X] = pos->x == 0 ? NULL : centerNode + nodeDirInc[MINUS_X];
    nNode[MINUS_Y] = pos->y == 0 ? NULL : centerNode + nodeDirInc[MINUS_Y];
    nNode[MINUS_Z] = pos->z == 0 ? NULL : centerNode + nodeDirInc[MINUS_Z];
}


/**************************************************************************\
*
* NodeVisited
* 
* Mark the node as non-empty
* 
\**************************************************************************/

void 
NODE_ARRAY::NodeVisited( IPOINT3D *pos )
{
    (GetNode( pos ))->MarkAsTaken();
}

/**************************************************************************\
*
* GetNode
*
* Get ptr to node from position
*
\**************************************************************************/

Node *
NODE_ARRAY::GetNode( IPOINT3D *pos )
{
    return nodes +
           pos->x +
           pos->y * numNodes.x +
           pos->z * numNodes.x * numNodes.y;
}

/**************************************************************************\
*
* GetNextNode
*
* Get ptr to next node from pos and dir
*
\**************************************************************************/

Node *
NODE_ARRAY::GetNextNode( IPOINT3D *pos, int dir )
{
    Node *curNode = GetNode( pos );

    SS_ASSERT( (dir >= 0) && (dir < NUM_DIRS), 
            "NODE_ARRAY::GetNextNode : invalid dir\n" );

    switch( dir ) {
        case PLUS_X:
            return( pos->x == (numNodes.x - 1) ? NULL : 
                              curNode + nodeDirInc[PLUS_X]);
            break;
        case MINUS_X:
            return( pos->x == 0 ? NULL : 
                              curNode + nodeDirInc[MINUS_X]);
            break;
        case PLUS_Y:
            return( pos->y == (numNodes.y - 1) ? NULL : 
                              curNode + nodeDirInc[PLUS_Y]);
            break;
        case MINUS_Y:
            return( pos->y == 0 ? NULL : 
                              curNode + nodeDirInc[MINUS_Y]);
            break;
        case PLUS_Z:
            return( pos->z == (numNodes.z - 1) ? NULL : 
                              curNode + nodeDirInc[PLUS_Z]);
            break;
        case MINUS_Z:
            return( pos->z == 0 ? NULL : 
                              curNode + nodeDirInc[MINUS_Z]);
            break;
        default:
            return NULL;
    }
}


/**************************************************************************\
*
* GetNextNodePos
*
* Get position of next node from curPos and lastDir
*
* Returns FALSE if boundary hit or node empty
*
\**************************************************************************/

BOOL
NODE_ARRAY::GetNextNodePos( IPOINT3D *curPos, IPOINT3D *nextPos, int dir )
{
    static Node *neighbNode[NUM_DIRS]; // ptrs to 6 neighbour nodes

    SS_ASSERT( (dir >= 0) && (dir < NUM_DIRS), 
            "NODE_ARRAY::GetNextNodePos : invalid dir\n" );

// don't need to get all neighbours, just one in next direction
    GetNeighbours( curPos, neighbNode );

    *nextPos = *curPos;

    // bail if boundary hit or node not empty
    if( (neighbNode[dir] == NULL) || !neighbNode[dir]->IsEmpty() )
        return FALSE;

    switch( dir ) {
        case PLUS_X:
            nextPos->x = curPos->x + 1;
            break;

        case MINUS_X:
            nextPos->x = curPos->x - 1;
            break;

        case PLUS_Y:
            nextPos->y = curPos->y + 1;
            break;

        case MINUS_Y:
            nextPos->y = curPos->y - 1;
            break;

        case PLUS_Z:
            nextPos->z = curPos->z + 1;
            break;

        case MINUS_Z:
            nextPos->z = curPos->z - 1;
            break;
    }

    return TRUE;
}


/**************************************************************************\
*             
*    GetEmptyNeighbours()
*       - get list of direction indices of empty node neighbours,
*         and put them in supplied matrix
*       - return number of empty node neighbours
*
\**************************************************************************/

int 
NODE_ARRAY::GetEmptyNeighbours( Node **nNode, int *nEmpty )
{
    int i, count = 0;

    for( i = 0; i < NUM_DIRS; i ++ ) {
        if( nNode[i] && nNode[i]->IsEmpty() )
            nEmpty[count++] = i;
    }
    return count;
}

/**************************************************************************\
*             
*    GetEmptyTurnNeighbours()
*       - get list of direction indices of empty node neighbours,
*         and put them in supplied matrix
*       - don't include going straight
*       - return number of empty node neighbours
*
\**************************************************************************/

int 
NODE_ARRAY::GetEmptyTurnNeighbours( Node **nNode, int *nEmpty, int lastDir )
{
    int i, count = 0;

    for( i = 0; i < NUM_DIRS; i ++ ) {
        if( nNode[i] && nNode[i]->IsEmpty() ) {
            if( i == lastDir )
                continue;
            nEmpty[count++] = i;
        }
    }
    return count;
}

/**************************************************************************\
* GetEmptyNeighboursAlongDir
*
* Sort of like above, but just gets one neigbour according to supplied dir
*
* Given a position and direction, find out how many contiguous empty nodes 
* there are in that direction.
* - Can limit search with searchRadius parameter
* - Return contiguous empty node count
\**************************************************************************/

int
NODE_ARRAY::GetEmptyNeighboursAlongDir( IPOINT3D *pos, int dir,
                            int searchRadius )
{
    Node *curNode = GetNode( pos );
    int nodeStride;
    int maxSearch;
    int count = 0;

    SS_ASSERT( (dir >= 0) && (dir < NUM_DIRS), 
            "NODE_ARRAY::GetEmptyNeighboursAlongDir : invalid dir\n" );

    nodeStride = nodeDirInc[dir];

    switch( dir ) {
        case PLUS_X:    
            maxSearch = numNodes.x - pos->x - 1;
            break;
        case MINUS_X:
            maxSearch = pos->x;
            break;
        case PLUS_Y:    
            maxSearch = numNodes.y - pos->y - 1;
            break;
        case MINUS_Y:
            maxSearch = pos->y;
            break;
        case PLUS_Z:    
            maxSearch = numNodes.z - pos->z - 1;
            break;
        case MINUS_Z:
            maxSearch = pos->z;
            break;
    }
    
    if( searchRadius > maxSearch )
        searchRadius = maxSearch;

    if( !searchRadius )
        return 0;

    while( searchRadius-- ) {
        curNode += nodeStride;
        if( ! curNode->IsEmpty() )
            return count;
        count++;
    }
    return count;
}

/**************************************************************************\
* FindRandomEmptyNode
*
* - Search for an empty node to start drawing
* - Return position of empty node in supplied pos ptr
* - Returns FALSE if couldn't find a node
* - Marks node as taken (mf: renam fn to ChooseEmptyNode ?
*
\**************************************************************************/

// If random search takes longer than twice the total number
// of nodes, give up the random search.  There may not be any
// empty nodes.

#define INFINITE_LOOP   (2 * NUM_NODE * NUM_NODE * NUM_NODE)

BOOL
NODE_ARRAY::FindRandomEmptyNode( IPOINT3D *pos )
{
    int infLoopDetect = 0;

    while( TRUE ) {

        // Pick a random node.

        pos->x = ss_iRand( numNodes.x );
        pos->y = ss_iRand( numNodes.y );
        pos->z = ss_iRand( numNodes.z );

        // If its empty, we're done.

        if( GetNode(pos)->IsEmpty() ) {
            NodeVisited( pos );
            return TRUE;
        } else {
            // Watch out for infinite loops!  After trying for
            // awhile, give up on the random search and look
            // for the first empty node.

            if ( infLoopDetect++ > INFINITE_LOOP ) {

                // Search for first empty node.

                for ( pos->x = 0; pos->x < numNodes.x; pos->x++ )
                    for ( pos->y = 0; pos->y < numNodes.y; pos->y++ )
                        for ( pos->z = 0; pos->z < numNodes.z; pos->z++ )
                            if( GetNode(pos)->IsEmpty() ) {
                                NodeVisited( pos );
                                return TRUE;
                            }

                // There are no more empty nodes.
                // Reset the pipes and exit.

                return FALSE;
            }
        }
    }
}

/**************************************************************************\
* FindRandomEmptyNode2D
*
* - Like FindRandomEmptyNode, but limits search to a 2d plane of the supplied
*   box.
*
\**************************************************************************/

#define INFINITE_LOOP   (2 * NUM_NODE * NUM_NODE * NUM_NODE)
#define MIN_VAL 1
#define MAX_VAL 0

BOOL
NODE_ARRAY::FindRandomEmptyNode2D( IPOINT3D *pos, int plane, int *box )
{
    int *newx, *newy;
    int *xDim, *yDim;

    switch( plane ) {
        case PLUS_X:
        case MINUS_X:
            pos->x = box[plane];
            newx = &pos->z;
            newy = &pos->y;
            xDim = &box[PLUS_Z]; 
            yDim = &box[PLUS_Y]; 
            break;
        case PLUS_Y:
        case MINUS_Y:
            pos->y = box[plane];
            newx = &pos->x;
            newy = &pos->z;
            xDim = &box[PLUS_X]; 
            yDim = &box[PLUS_Z]; 
            break;
        case PLUS_Z:
        case MINUS_Z:
            newx = &pos->x;
            newy = &pos->y;
            pos->z = box[plane];
            xDim = &box[PLUS_X]; 
            yDim = &box[PLUS_Y]; 
            break;
    }

    int infLoop = 2 * (xDim[MAX_VAL] - xDim[MIN_VAL] + 1) *
                      (yDim[MAX_VAL] - yDim[MIN_VAL] + 1);
    int infLoopDetect = 0;

    while( TRUE ) {

        // Pick a random node.

        *newx = ss_iRand2( xDim[MIN_VAL], xDim[MAX_VAL] );
        *newy = ss_iRand2( yDim[MIN_VAL], yDim[MAX_VAL] );

        // If its empty, we're done.

        if( GetNode(pos)->IsEmpty() ) {
            NodeVisited( pos );
            return TRUE;
        } else {
            // Watch out for infinite loops!  After trying for
            // awhile, give up on the random search and look
            // for the first empty node.

            if ( ++infLoopDetect > infLoop ) {

                // Do linear search for first empty node.

                for ( *newx = xDim[MIN_VAL]; *newx <= xDim[MAX_VAL]; (*newx)++ )
                    for ( *newy = yDim[MIN_VAL]; *newy <= yDim[MAX_VAL]; (*newy)++ )
                        if( GetNode(pos)->IsEmpty() ) {
                            NodeVisited( pos );
                            return TRUE;
                        }

                // There are no empty nodes in this plane.
                return FALSE;
            }
        }
    }
}

/**************************************************************************\
* TakeClosestEmptyNode
*
* - Search for an empty node closest to supplied node position
* - Returns FALSE if couldn't find a node
* - Marks node as taken
* - not completely opimized - if when dilating the box, a side gets
*   clamped against the node array, this side will continue to be searched
*
\**************************************************************************/

static void
DilateBox( int *box, IPOINT3D *bounds );

BOOL
NODE_ARRAY::TakeClosestEmptyNode( IPOINT3D *newPos, IPOINT3D *pos )
{
    static int searchRadius = SS_MAX( numNodes.x, numNodes.y ) / 3;

    // easy out
    if( GetNode(pos)->IsEmpty() ) {
        NodeVisited( pos );
        *newPos = *pos;
        return TRUE;
    }

    int box[NUM_DIRS] = {pos->x, pos->x, pos->y, pos->y, pos->z, pos->z};
    int clip[NUM_DIRS] = {0};

    // do a random search on successively larger search boxes
    for( int i = 0; i < searchRadius; i++ ) {
        // Increase box size
        DilateBox( box, &numNodes );
        // start looking in random 2D face of the box
        int dir = ss_iRand( NUM_DIRS );
        for( int j = 0; j < NUM_DIRS; j++, dir = (++dir == NUM_DIRS) ? 0 : dir ) {
            if( FindRandomEmptyNode2D( newPos, dir, box ) )
                return TRUE;
        }
    }

    // nothing nearby - grab a random one
    return FindRandomEmptyNode( newPos );
}

/**************************************************************************\
* DilateBox
*
* - Increase box radius without exceeding bounds
*
\**************************************************************************/

static void
DilateBox( int *box, IPOINT3D *bounds )
{
    int *min = (int *) &box[MINUS_X];
    int *max = (int *) &box[PLUS_X];
    int *boundMax = (int *) bounds;
    // boundMin always 0

    for( int i = 0; i < 3; i ++, min+=2, max+=2, boundMax++ ) {
        if( *min > 0 )
            (*min)--;
        if( *max < (*boundMax - 1) )
            (*max)++;
    }
}
