/*
	Ken Hughes's xwave.c, wind.c, and neighbor.c
*/


// Include Files

#include <math.h>
#include "trulla.h"


// Symbolic Constants

#define MAXCONDITIONS  20
#define ABS(x)        (x >= 0) ? x : -x
#define SGN(x)        (x < 0) ? 1 : 0
#define DECODE(x,y)   (x & y) == y

// the normal could be -2 or -1 (meaning there is no obstacle between the
// current gridel and goal (or subgoal)), or 0 through 3 representing the
// quadrant containing an obstacle to avoid
#define NORMAL(x,y)  ((x < 0) ? 1 : 0) | ((y < 0) ? 2 : 0)
#define DIST(x,y)    sqrt ( (double) x * x + (double) y * y )


// External Declarations

extern int      currRowCell;
extern int      lastRowCell;
extern int      nextRowCell;
extern GRIDEL * validCellPtr;
extern GRIDEL * gridPtr;
extern int      wsWidthInCells;
extern int      wsHgtInCells;
extern int      maxInt;
extern float    maxFloat;


// Globals

long enableCondition [MAXCONDITIONS];
int  ni[8] = { -1 , 0 , 1 , -1 , 1 , -1 ,  0 ,  1 };
int  nj[8] = {  1 , 1 , 1 ,  0 , 0 , -1 , -1 , -1 };
int  neighXOffset, neighYOffset;
int  targetXOffset, targetYOffset;
int  horzCellOffset, vertCellOffset;
int  targetCellOffset;
int  neighCellOffset;


// Symbolic Constants

#define HVWGT_NE_CWGT                  0x40000  // horz/vert region; curr wgt
#define TREG_GT_ZERO		               0x20000  // target region
#define TREG_LE_ZERO		               0x10000  // target region
#define HWGT_NE_CWGT		               0x8000   // horz/curr wgt
#define HWGT_EQ_CWGT		               0x4000   // horz/curr wgt
#define TARGETXOFFSET_NE_ZERO		      0x2000
#define TARGETXOFFSET_EQ_ZERO		      0x1000
#define TARGETXOFFSET_EQ_NEIGHXOFFSET	0x0800
#define TARGETYOFFSET_NE_ZERO	         0x0400
#define TARGETYOFFSET_EQ_ZERO		      0x0200
#define TARGETYOFFSET_EQ_NEIGHYOFFSET  0x0100
#define NEIGHXOFFSET_EQ_ZERO		      0x0080
#define NEIGHYOFFSET_EQ_ZERO		      0x0040
#define TWGT_NE_CWGT		               0x0020  // target/curr wgt
#define TWGT_LT_CWGT		               0x0010  // target/curr wgt
#define TWGT_EQ_CWGT		               0x0008  // target/curr wgt
#define TWGT_GT_CWGT		               0x0004  // target/curr wgt
#define VWGT_NE_CWGT		               0x0002  // vert/curr wgt
#define VWGT_EQ_CWGT		               0x0001  // vert/curr wgt


// Function Prototypes

void InitEnableConditions ();
int  ChooseBestValidCell ();
int  IsGoodNeighbor ();
void SetCellOffsets ( int validCellOffset );
long CalcEnableVector ();
int  DecodeEnableVector ( long enable, int validCellOffset );
void CalcOldDeltas ( int validCellOffset );
void CalcNewDeltas ( int validCellOffset, int cellWeight, float cellTDist,
	char neighType );
void SortValidCells ( int numValidCells );
int  ChooseWinner ( int n1, int n2 );


/////////////////////////////////////////////////////////////////////
//   Function:  InitEnableConditions
//   Purpose:  Conditions under which propagation is allowed.  If any
//      of these conditions test true, then the values of the target
//      cell will be propagated.
/////////////////////////////////////////////////////////////////////

void InitEnableConditions ()
{

// if the new neighbor is 4c ...
// ... and it is in a different region, make it a subgoal

// *move horizontally to target cell & target cell has wgt equal to curr
// cell's & target cell points to cell w/wgt equal to or less than its own
	enableCondition[0] = TARGETYOFFSET_EQ_ZERO | TWGT_EQ_CWGT | TREG_LE_ZERO;

// *move vertically to target cell & target cell has wgt equal to curr cell's
// & target cell points to cell w/wgt equal to or less than its own
	enableCondition[1] = TARGETXOFFSET_EQ_ZERO | TWGT_EQ_CWGT | TREG_LE_ZERO;

// *move horizontally to target cell & target cell has wgt equal to curr
// cell's & target cell points to cell w/wgt greater than its own
	enableCondition[2] = TARGETYOFFSET_EQ_ZERO | TWGT_EQ_CWGT | TREG_GT_ZERO;

// *move vertically to target cell & target cell has wgt equal to curr
// cell's & target cell points to cell w/wgt greater than its own
	enableCondition[3] = TARGETXOFFSET_EQ_ZERO | TWGT_EQ_CWGT | TREG_GT_ZERO;

// *move horizontally to target cell & target cell wgt is not equal to curr
// cell's
	enableCondition[4] = TARGETYOFFSET_EQ_ZERO | TWGT_NE_CWGT;

// *move vertically to target cell & target cell wgt is not equal to curr
// cell's
	enableCondition[5] = TARGETXOFFSET_EQ_ZERO | TWGT_NE_CWGT;

// new neighbor is a diagonal 8c neighbor
// destination cell is in the same region
// both 4c neighbors are in the same region

// *move diagonally to target cell; target & critical cells are equal in wgt
// to curr cell; target cell points to cell of equal or less wgt than itself
	enableCondition[6] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								TWGT_EQ_CWGT | HWGT_EQ_CWGT | VWGT_EQ_CWGT |
								TREG_LE_ZERO;

// *move diagonally to target cell; target & critical cells are equal in wgt
// to curr cell; target cell points to cell of greater wgt than itself
	enableCondition[7] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								TWGT_EQ_CWGT | HWGT_EQ_CWGT | VWGT_EQ_CWGT |
								TREG_GT_ZERO;

// horizontal 4c neighbor is inheriting neighbor and is in region

// *move diagonally to target cell; target & horz critical cells are equal
// in wgt to curr cell; vert critical cell wgt is NE to curr cell wgt;
// original neighbor is horizontal but it points to a diagonal target cell
	enableCondition[8] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								TWGT_EQ_CWGT | HWGT_EQ_CWGT | VWGT_NE_CWGT |
								TARGETXOFFSET_EQ_NEIGHXOFFSET | NEIGHYOFFSET_EQ_ZERO;

// vertical 4c neighbor is inheriting neighbor and is in region

// *move diagonally to target cell; target & vert critical cells are equal
// in wgt to curr cell; horz critical cell wgt is NE to curr cell wgt;
// original neighbor is vertical but it points to a diagonal target cell
	enableCondition[9] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								TWGT_EQ_CWGT | VWGT_EQ_CWGT | HWGT_NE_CWGT |
								TARGETYOFFSET_EQ_NEIGHYOFFSET | NEIGHXOFFSET_EQ_ZERO;

// destination cell (i.e., target cell) is NOT in the same region
// check for allowable low-to-high region motions
// both 4c neighbors are in the same region, but horizontal
//		neighbor is the propagating gridel

// *move diagonally to target cell; critical cells have wgt equal to curr
// cell's; target cell's wgt is greater than curr cell's; original neighbor
// is horizontal but it points to a diagonal target cell
	enableCondition[10] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_GT_CWGT | HWGT_EQ_CWGT | VWGT_EQ_CWGT |
								 TARGETXOFFSET_EQ_NEIGHXOFFSET | NEIGHYOFFSET_EQ_ZERO;

// both 4c neighbors are in the same region, but vertical
//		neighbor is the propagating gridel

// *move diagonally to target cell; critical cells have wgt equal to curr
// cell's; target cell's wgt is greater than curr cell's; original neighbor
// is vertical but it points to a diagonal target cell
	enableCondition[11] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_GT_CWGT | VWGT_EQ_CWGT | HWGT_EQ_CWGT |
								 NEIGHXOFFSET_EQ_ZERO | TARGETYOFFSET_EQ_NEIGHYOFFSET;

// if we get here, one of the 4c neighbors is in a different region
//	and the destination gridel is the propagating gridel

// *move diagonally to target cell; target cell's wgt is greater than curr
// cell's; target cell IS original neighbor cell
	enableCondition[12] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_GT_CWGT | TARGETXOFFSET_EQ_NEIGHXOFFSET |
								 TARGETYOFFSET_EQ_NEIGHYOFFSET;

// the horizontal 4c gridel is the propagating gridel

// *move diagonally to target cell; target cell's wgt is greater than curr
// cell's; original neighbor is horizontal but it points to a diagonal
// target cell
	enableCondition[13] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_GT_CWGT | TARGETXOFFSET_EQ_NEIGHXOFFSET |
								 NEIGHYOFFSET_EQ_ZERO;

// the vertical 4c gridel is the propagating gridel

// *move diagonally to target cell; target cell's wgt is greater than curr
// cell's; original neighbor is vertical but it points to a diagonal
// target cell
	enableCondition[14] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_GT_CWGT | TARGETYOFFSET_EQ_NEIGHYOFFSET |
								 NEIGHXOFFSET_EQ_ZERO;

// check for allowable high -to-low region motions
// both 4c neighbors are in the same region, but horizontal
//		neighbor is the propagating gridel

// *move diagonally to target cell; critical cells are equal in wgt to curr
// cell; target cell's wgt is less than curr cell's; original neighbor is
// horizontal but it points to a diagonal target cell
	enableCondition[15] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_LT_CWGT | HWGT_EQ_CWGT | VWGT_EQ_CWGT |
								 TARGETXOFFSET_EQ_NEIGHXOFFSET | NEIGHYOFFSET_EQ_ZERO;

// both 4c neighbors are in the same region, but vertical
//		neighbor is the propagating gridel

// *move diagonally to target cell; critical cells are equal in wgt to curr
// cell; target cell's wgt is less than curr cell's; original neighbor is
// vertical but it points to a diagonal target cell
	enableCondition[16] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_LT_CWGT | VWGT_EQ_CWGT | HWGT_EQ_CWGT |
								 NEIGHXOFFSET_EQ_ZERO | TARGETYOFFSET_EQ_NEIGHYOFFSET;

// if we get here, one of the 4c neighbors is in a different region and
// the destination gridel is the propagating gridel

// *move diagonally to target cell; target cell's wgt is less than curr
// cell's; target cell IS neighbor cell
	enableCondition[17] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_LT_CWGT | TARGETXOFFSET_EQ_NEIGHXOFFSET |
								 TARGETYOFFSET_EQ_NEIGHYOFFSET;

// the horizontal 4c gridel is the propagating gridel

// *move diagonally to target cell; target cell's wgt is less than curr
// cell's; original neighbor is horizontal but it points to a diagonal
// target cell
	enableCondition[18] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_LT_CWGT | TARGETXOFFSET_EQ_NEIGHXOFFSET |
								 NEIGHYOFFSET_EQ_ZERO;

// the vertical 4c gridel is the propagating gridel

// *move diagonally to target cell; target cell's wgt is less than curr
// cell's; original neighbor is vertical but it points to a diagonal
// target cell
	enableCondition[19] = TARGETXOFFSET_NE_ZERO | TARGETYOFFSET_NE_ZERO |
								 TWGT_LT_CWGT | TARGETYOFFSET_EQ_NEIGHYOFFSET |
								 NEIGHXOFFSET_EQ_ZERO;
}


/////////////////////////////////////////////////////////////////////
//   Function:  ChooseBestValidCell
//   Purpose:  Checks the propagation values of the eight connected
//      neighbors of the current cell to see which ones could possibly
//      be used to update the values of the current cell.  The
//      propagation values of the neighbors which survive a number of
//      tests are used to calculate new values for possible use by the
//      current cell.  These new values are stored in temporary gridels
//      which are considered valid cells.  The valid cells are then
//      sorted by total distance to the goal.  The best of these valid
//      cells is selected to possibly update the values of the current
//      cell.  (If the values of the current cell are better than the
//      best of the valid cells, the current cell values will not be
//      updated.)
/////////////////////////////////////////////////////////////////////

int ChooseBestValidCell ()
{
	int i;
	int numValidCells, validCellOffset;
	long enable;

// try to get a propagated value from each neighbor
	validCellOffset = 0;
	for ( i = 0 ; i < 8 ; ++i ) {  // 8 neighbors
		neighXOffset = ni[i];
		neighYOffset = nj[i];
		neighCellOffset = currRowCell+neighXOffset+neighYOffset*wsWidthInCells;

		if ( IsGoodNeighbor () ) {
			SetCellOffsets ( validCellOffset );
			enable = CalcEnableVector ();
			if ( DecodeEnableVector (enable, validCellOffset) )
				validCellOffset++;
		}
	}

// sort the valid cells based on total distance to the goal
	numValidCells = validCellOffset;
	SortValidCells ( numValidCells );

// starting with the closest, look for a gridel which wins all the
//	neighbor comparisons
	while ( validCellOffset-- > 0 ) {
		for ( i = 0 ; i < validCellOffset ; ++i ) {
			if ( i == ChooseWinner ( i, validCellOffset ) )
				break;
		}
		if ( i == validCellOffset )
			return ( validCellOffset );
	}

	return ( -1 );
}


/////////////////////////////////////////////////////////////////////
//   Function:  IsGoodNeighbor
//   Purpose:  Runs a neighbor cell through some preliminary tests to
//      see if its values could possibly be considered to update the
//      values of the current cell.
/////////////////////////////////////////////////////////////////////

int IsGoodNeighbor ()
{
	GRIDEL * currCell, * neighCell;
	int newDelx, newDely;
	int absNewDelx, absNewDely, absNeighDelx, absNeighDely;
	int sgnNewDelx, sgnNewDely, sgnNeighDelx, sgnNeighDely;

// the neighbor cell is not a connected neighbor or is not in the workspace
	currCell = gridPtr + currRowCell;
	if ( ( neighXOffset < 0 && currCell->xloc == 0 ) ||
	( neighYOffset < 0 && currCell->yloc == 0 ) ||
	( neighXOffset > 0 && currCell->xloc == wsWidthInCells-1 ) ||
	( neighYOffset > 0 && currCell->yloc == wsHgtInCells-1 ) )
		return (!OKAY);

// the neighbor cell is an obstacle or has no new propagation values
	neighCell = gridPtr + neighCellOffset;
	if ( neighCell->r_weight == MAXWGT || neighCell->s_dist == maxFloat )
		return (!OKAY);	// 00

// set up for the next two tests
	newDelx = neighCell->delx - neighXOffset * currCell->r_weight;
	newDely = neighCell->dely - neighYOffset * currCell->r_weight;
	absNewDelx = ABS ( newDelx );
	absNewDely = ABS ( newDely );
	absNeighDelx = ABS ( neighCell->delx );
	absNeighDely = ABS ( neighCell->dely );
	sgnNewDelx = SGN ( newDelx );
	sgnNewDely = SGN ( newDely );
	sgnNeighDelx = SGN ( neighCell->delx );
	sgnNeighDely = SGN ( neighCell->dely );

// the propagation values are closer to the subgoal than the
// neighbor's (???)
	if ( ( absNewDelx < absNeighDelx && absNewDely < absNeighDely ) ||
	( neighCell->delx && sgnNewDelx != sgnNeighDelx ) ||
	( neighCell->dely && sgnNewDely != sgnNeighDely ) )
		return (!OKAY);

// the gridels are in two different regions and the propagation is
//	"backwards" (back into the region the propagating gridel itself
//	propagated from)
	if ( ( neighXOffset && absNewDelx < absNeighDelx ) ||
	( neighYOffset	&& absNewDely < absNeighDely ) )
		return (!OKAY);

	return OKAY; // all tests were passed so try to get values from this neighbor
}


/////////////////////////////////////////////////////////////////////
//   Function:  SetCellOffsets
//   Purpose:  Initializes the temporary gridel pointers.  Also,
//      initializes the delx and dely of the valid cell selected as
//      the best cell whose values could possibly be used to update
//      the values of the current cell.
/////////////////////////////////////////////////////////////////////

void SetCellOffsets ( int validCellOffset )
{
	GRIDEL * validCell, * neighCell, * currCell;

	currCell = gridPtr + currRowCell;
	neighCell = gridPtr + neighCellOffset;
	validCell = validCellPtr + validCellOffset;

	validCell->delx =	neighCell->delx - neighXOffset *	currCell->r_weight;
	validCell->dely =	neighCell->dely - neighYOffset *	currCell->r_weight;

// The neighbor cell tells the current cell which way to go to get to the
// goal or subgoal.  It may be that the neighbor says to go through a cell
// which happens to be another neighbor of the current cell.  This latter
// neighbor is the target cell.  Just because the neighbor cell sends the
// robot through the target cell, the path through the neighbor cell will
// not necessarily be abandoned in favor of the path directly through the
// target cell.
	targetXOffset = (validCell->delx < 0 ? 1 : (validCell->delx > 0 ? -1 : 0));
	targetYOffset = (validCell->dely < 0 ? 1 : (validCell->dely > 0 ? -1 : 0));

	horzCellOffset = currRowCell + targetXOffset;

	if ( targetYOffset > 0 ) {
		targetCellOffset = nextRowCell + targetXOffset;
		vertCellOffset = nextRowCell;
	}
	else if ( targetYOffset == 0 ) {
		targetCellOffset = currRowCell + targetXOffset;
		vertCellOffset = currRowCell;
	}
	else {
		targetCellOffset = lastRowCell + targetXOffset;
		vertCellOffset = lastRowCell;
	}
}


/////////////////////////////////////////////////////////////////////
//   Function:  CalcEnableVector
//   Purpose:  Sets to TRUE (1) the bits in the enable vector which
//      passes the series of tests listed below.  Later, if certain
//      combinations of these tests are true (i.e., if certain
//      combinations of bits in the enable vector are on), then new
//      values of the selected valid cell will be calculated and
//      possibly used to update the current cell.
/////////////////////////////////////////////////////////////////////

long CalcEnableVector ()
{
	long enable;
	GRIDEL * currCell, * horzCell, * vertCell, * targetCell;

	currCell = gridPtr + currRowCell;
	horzCell = gridPtr + horzCellOffset;
	vertCell = gridPtr + vertCellOffset;
	targetCell = gridPtr + targetCellOffset;

	enable = 0;

//  HVWGT_NE_CWGT     0x40000
	enable = ( horzCell->r_weight != currCell->r_weight ||
				  vertCell->r_weight != currCell->r_weight ) | ( enable << 1 );

// 	TREG_GT_ZERO		0x20000
	enable = ( targetCell->region > 0 ) | ( enable << 1 );

// 	TREG_LE_ZERO		0x10000
	enable = ( targetCell->region <= 0 ) | ( enable << 1 );

// 	HWGT_NE_CWGT		0x8000
	enable = ( horzCell->r_weight != currCell->r_weight ) | ( enable << 1 );

// 	HWGT_EQ_CWGT		         0x4000
	enable = ( horzCell->r_weight == currCell->r_weight ) | ( enable << 1 );

// 	TARGETXOFFSET_NE_ZERO		0x2000
	enable = ( targetXOffset != 0 ) | ( enable << 1 );

// 	TARGETXOFFSET_EQ_ZERO		0x1000
	enable = ( targetXOffset == 0 ) | ( enable << 1 );

// 	TARGETXOFFSET_EQ_NEIGHXOFFSET		0x0800
	enable = ( targetXOffset == neighXOffset ) | ( enable << 1 );

// 	TARGETYOFFSET_NE_ZERO		0x0400
	enable = ( targetYOffset != 0 ) | ( enable << 1 );

// 	TARGETYOFFSET_EQ_ZERO		0x0200
	enable = ( targetYOffset == 0 ) | ( enable << 1 );

// 	TARGETYOFFSET_EQ_NEIGHYOFFSET 		0x0100
	enable = ( targetYOffset == neighYOffset ) | ( enable << 1 );

// 	NEIGHXOFFSET_EQ_ZERO		0x0080
	enable = ( neighXOffset == 0 ) | ( enable << 1 );

// 	NEIGHYOFFSET_EQ_ZERO		0x0040
	enable = ( neighYOffset == 0 ) | ( enable << 1 );

// 	TWGT_NE_CWGT		0x0020
	enable = ( targetCell->r_weight != currCell->r_weight ) | ( enable << 1 );

// 	TWGT_LT_CWGT		0x0010
	enable = ( targetCell->r_weight < currCell->r_weight ) | ( enable << 1 );

// 	TWGT_EQ_CWGT		0x0008
	enable = ( targetCell->r_weight == currCell->r_weight ) | ( enable << 1 );

// 	TWGT_GT_CWGT		0x0004
	enable = ( targetCell->r_weight > currCell->r_weight ) | ( enable << 1 );

// 	VWGT_NE_CWGT		0x0002
	enable = ( vertCell->r_weight != currCell->r_weight ) | ( enable << 1 );

// 	VWGT_EQ_CWGT		0x0001
	enable = ( vertCell->r_weight == currCell->r_weight ) | ( enable << 1 );

	return enable;
}


/////////////////////////////////////////////////////////////////////
//   Function:  DecodeEnableVector
//   Purpose:  Determines if certain combinations of bits in the
//      enable vector are on by comparing the vector to a series of
//      enable conditions.  If any of the combinations are matched,
//      then new values will be calculated using the selected valid
//      cell and will possibly be used to update the values of the
//      current celll.
/////////////////////////////////////////////////////////////////////

int DecodeEnableVector ( long enable, int validCellOffset )
{
	int i;
	GRIDEL * validCell, * neighCell, * targetCell;
	GRIDEL * horzCell, * vertCell;

	validCell = validCellPtr + validCellOffset;
	neighCell = gridPtr + neighCellOffset;
	targetCell = gridPtr + targetCellOffset;
	horzCell = gridPtr + horzCellOffset;
	vertCell = gridPtr + vertCellOffset;

	for ( i = 0; i < MAXCONDITIONS; i++ ) {
		if ( DECODE (enable,enableCondition[i]) ) {
			switch (i) {
				case 0 : case 1 : case 6 :
					validCell->normal = neighCell->normal;
					CalcOldDeltas ( validCellOffset );
					return OKAY;

				case 2 : case 3 : case 4 : case 5 : case 7 :
					validCell->normal = -1;
					CalcNewDeltas ( validCellOffset, targetCell->r_weight,
						targetCell->t_dist, 't' ); // 't'=use target offsets
					return OKAY;

 				case 8 : case 13 :
					validCell->normal = NORMAL ( -targetXOffset, targetYOffset );
					CalcNewDeltas ( validCellOffset, horzCell->r_weight,
							 horzCell->t_dist, 'n' ); // 'n'=use neighbor offsets
					return OKAY;

				case 9 : case 14 :
					validCell->normal = NORMAL ( targetXOffset, -targetYOffset );
					CalcNewDeltas ( validCellOffset, vertCell->r_weight,
							 vertCell->t_dist, 'n' ); // 'n'=use neighbor offsets
					return OKAY;

				case 10 :
					validCell->normal = NORMAL ( targetXOffset, targetYOffset );
					CalcNewDeltas ( validCellOffset,horzCell->r_weight,
							 horzCell->t_dist, 'n' ); // 'n'=use neighbor offsets
					return OKAY;

				case 11 :
					validCell->normal = NORMAL ( targetXOffset, targetYOffset );
					CalcNewDeltas ( validCellOffset, vertCell->r_weight,
							 vertCell->t_dist, 'n' ); // 'n'=use neighbor offsets
					return OKAY;

				case 12 : case 17 :
					validCell->normal = -1;
					CalcNewDeltas ( validCellOffset, targetCell->r_weight,
							 targetCell->t_dist, 'n' ); // 'n'=use neighbor offsets
					return OKAY;

				case 15 : case 18 :
					validCell->normal = -1;
					CalcNewDeltas ( validCellOffset, horzCell->r_weight,
							 horzCell->t_dist, 'n' ); // 'n'=use neighbor offsets
					return OKAY;

				case 16 : case 19 :
					validCell->normal = -1;
					CalcNewDeltas ( validCellOffset, vertCell->r_weight,
							 vertCell->t_dist, 'n' ); // 'n'=use neighbor offsets
					return OKAY;
			}
		}
	}

	return (!OKAY);
}


/////////////////////////////////////////////////////////////////////
//   Function:  CalcOldDeltas
//   Purpose:  Calculates new propagation values that may be used to
//      update the values of the current cell.  This function is called
//      when the weight of the target cell is equal to the weight of the
//      current cell and the target cell points to a cell with weight
//      equal to or less than its own.
/////////////////////////////////////////////////////////////////////

void CalcOldDeltas ( int validCellOffset )
{
	GRIDEL * validCell;
	GRIDEL * currCell;
	GRIDEL * targetCell;
	GRIDEL * neighCell;

	validCell = validCellPtr + validCellOffset;
	currCell = gridPtr + currRowCell;
	targetCell = gridPtr + targetCellOffset;
	neighCell = gridPtr + neighCellOffset;

	validCell->xgoal= neighCell->xgoal - neighXOffset;
	validCell->ygoal= neighCell->ygoal - neighYOffset;
	validCell->s_dist = neighCell->s_dist;
	validCell->t_dist = neighCell->s_dist +
							  DIST (validCell->delx , validCell->dely);
	validCell->region = targetCell->r_weight - currCell->r_weight;
}


/////////////////////////////////////////////////////////////////////
//   Function:  CalcNewDeltas
//   Purpose:  Calculates new propagation values that may be used to
//      update the values of the current cell.  This function is called
//      for all enable conditions other than those described in
//      function CalcOldDeltas.
/////////////////////////////////////////////////////////////////////

void CalcNewDeltas ( int validCellOffset, int cellWeight, float cellTDist,
							char neighType )
{
	GRIDEL * validCell;
	GRIDEL * currCell;
	int xOffset, yOffset;

	if ( neighType == 'n' ) {  // 'n'=use neighbor offsets
		xOffset = neighXOffset;
		yOffset = neighYOffset;
	}
	else {                   // default is 't'; use target offsets
		xOffset = targetXOffset;
		yOffset = targetYOffset;
	}

	currCell = gridPtr + currRowCell;
	validCell= validCellPtr + validCellOffset;

// if neighbor is obstacle, don't really propagate
	if ( cellWeight == MAXWGT ) {
		validCell->delx = validCell->dely = maxInt;
		validCell->s_dist = 0;
	}
	else {
		validCell->delx =	-xOffset * ( currCell->r_weight + cellWeight ) / 2;
		validCell->dely = -yOffset * ( currCell->r_weight + cellWeight ) / 2;
		validCell->xgoal= -xOffset;
		validCell->ygoal= -yOffset;
		validCell->s_dist = cellTDist;
		validCell->t_dist = cellTDist + DIST (validCell->delx,validCell->dely);
		validCell->region = cellWeight - currCell->r_weight;
	}
}


/////////////////////////////////////////////////////////////////////
//   Function:  SortValidCells
//   Purpose:  Bubble sorts the valid cells from longest total
//      distance to shortest total distance.
/////////////////////////////////////////////////////////////////////

void SortValidCells ( int numValidCells )
{
	int i,j;

// bubble sort the gridels based on total distance
	for ( i = numValidCells ; --i > 0 ; ) {
		for ( j = 0 ; j < i ; ++j ) {
			if ( validCellPtr[j].t_dist < validCellPtr[j+1].t_dist ) {
				validCellPtr[9] = validCellPtr[j+1];  // use [9] as a temp
				validCellPtr[j+1] = validCellPtr[j];
				validCellPtr[j] = validCellPtr[9];
			}
		}
	}
}


/////////////////////////////////////////////////////////////////////
//   Function:  ChooseWinner
//   Purpose:  Selects the best valid cell.
/////////////////////////////////////////////////////////////////////

int ChooseWinner ( int n1, int n2 )
{
	int slope1, slope2;
	int delsign;
	int closer, farther;
	GRIDEL * validCloser, * validFarther;
	int sgnFartherDelx, sgnFartherDely;
	int sgnCloserDelx, sgnCloserDely;
	int absCloserDelx, absCloserDely;
	int absFartherDelx, absFartherDely;

// determine which subgoal is closer and get its normal's sign
	if ( (validCellPtr+n1)->t_dist - (validCellPtr+n1)->s_dist <
	(validCellPtr+n2)->t_dist - (validCellPtr+n2)->s_dist ) {
		closer = n1;
		farther = n2;
	}
	else {
		closer = n2;
		farther = n1;
	}

	validCloser = validCellPtr + closer;
	validFarther = validCellPtr + farther;

// calculate the slopes of the two segments
	slope1 = validCloser->delx * validFarther->dely;
	slope2 = validFarther->delx * validCloser->dely;


// if closer subgoal also has shortest path, take it
	if ( ( validCloser->delx != 0 || validCloser->dely != 0 ) &&
	validCloser->t_dist <= validFarther->t_dist )
		return closer;


	sgnCloserDelx = SGN ( validCloser->delx );
	sgnCloserDely = SGN ( validCloser->dely );
	sgnFartherDelx = SGN ( validFarther->delx );
	sgnFartherDely = SGN ( validFarther->dely );

// otherwise the farther subgoals lies on the best path; justify using it...
// if two gridels have the same slope, choose the farther subgoal
	if ( ( slope1 && slope1 == slope2 ) ||
	( !validCloser->delx && !validFarther->delx &&
	sgnCloserDely == sgnFartherDely ) ||
	( !validCloser->dely && !validFarther->dely &&
	sgnCloserDelx == sgnFartherDelx ) )
		return farther;


// if closer subgoal is the gridel itself (it happens) or
//		if gridels lie in different quadrants, choose the
//		farther subgoal

	if ( (validCloser->delx == 0 && validCloser->dely == 0) ||
	(validCloser->delx && sgnCloserDelx !=	sgnFartherDelx ) ||
	(validCloser->dely && sgnCloserDely != sgnFartherDely ) )
		return farther;


// if the closer subgoal not bounded by an inadmissible region, then
//	choose the farther (either side is ok)
	if ( validCloser->normal < 0 )
		return farther;


// if the farther subgoal actually lies closer in one or the
//		other component, choose it (we have cleared the obstacle)

	absCloserDelx = ABS (validCloser->delx);
	absCloserDely = ABS (validCloser->dely);
	absFartherDelx = ABS (validFarther->delx);
	absFartherDely = ABS (validFarther->dely);

	if ( (absCloserDelx > absFartherDelx) || (absCloserDely > absFartherDely))
		return farther;


// find a non-zero delta and choose its sign
	delsign = ( validCloser->dely != 0 ) ?
		( validCloser->dely > 0 ) : ( validCloser->delx > 0 );


// figure out which subgoal to choose
	if ( ( 1 - SGN( slope1 - slope2 ) ) ^
	( ( ( validCloser->normal & 2 ) == 0 ) ) ^
	( validCloser->dely == 0 ) ^ delsign ^ ( validCloser->normal == 0 ||
	validCloser->normal == 3 ) )
		return farther;
	else
		return closer;
}