summaryrefslogtreecommitdiffstats
path: root/game/code/roads
diff options
context:
space:
mode:
authorSvxy <aidan61605@gmail.com>2023-05-31 23:31:32 +0200
committerSvxy <aidan61605@gmail.com>2023-05-31 23:31:32 +0200
commiteb4b3404aa00220d659e532151dab13d642c17a3 (patch)
tree7e1107c4995489a26c4007e41b53ea8d00ab2134 /game/code/roads
downloadThe-Simpsons-Hit-and-Run-eb4b3404aa00220d659e532151dab13d642c17a3.tar
The-Simpsons-Hit-and-Run-eb4b3404aa00220d659e532151dab13d642c17a3.tar.gz
The-Simpsons-Hit-and-Run-eb4b3404aa00220d659e532151dab13d642c17a3.tar.bz2
The-Simpsons-Hit-and-Run-eb4b3404aa00220d659e532151dab13d642c17a3.tar.lz
The-Simpsons-Hit-and-Run-eb4b3404aa00220d659e532151dab13d642c17a3.tar.xz
The-Simpsons-Hit-and-Run-eb4b3404aa00220d659e532151dab13d642c17a3.tar.zst
The-Simpsons-Hit-and-Run-eb4b3404aa00220d659e532151dab13d642c17a3.zip
Diffstat (limited to 'game/code/roads')
-rw-r--r--game/code/roads/allroads.cpp10
-rw-r--r--game/code/roads/geometry.cpp1024
-rw-r--r--game/code/roads/geometry.h448
-rw-r--r--game/code/roads/intersection.cpp1374
-rw-r--r--game/code/roads/intersection.h312
-rw-r--r--game/code/roads/lane.cpp187
-rw-r--r--game/code/roads/lane.h187
-rw-r--r--game/code/roads/road.cpp830
-rw-r--r--game/code/roads/road.h249
-rw-r--r--game/code/roads/roadmanager.cpp2565
-rw-r--r--game/code/roads/roadmanager.h318
-rw-r--r--game/code/roads/roadrender.cpp401
-rw-r--r--game/code/roads/roadrendertest.cpp271
-rw-r--r--game/code/roads/roadrendertest.h60
-rw-r--r--game/code/roads/roadsegment.cpp792
-rw-r--r--game/code/roads/roadsegment.h267
-rw-r--r--game/code/roads/roadsegmentdata.cpp211
-rw-r--r--game/code/roads/roadsegmentdata.h61
-rw-r--r--game/code/roads/trafficcontrol.cpp98
-rw-r--r--game/code/roads/trafficcontrol.h106
20 files changed, 9771 insertions, 0 deletions
diff --git a/game/code/roads/allroads.cpp b/game/code/roads/allroads.cpp
new file mode 100644
index 0000000..38a1c3f
--- /dev/null
+++ b/game/code/roads/allroads.cpp
@@ -0,0 +1,10 @@
+#include <roads/geometry.cpp>
+#include <roads/intersection.cpp>
+#include <roads/lane.cpp>
+#include <roads/road.cpp>
+#include <roads/roadmanager.cpp>
+#include <roads/roadrender.cpp>
+#include <roads/roadrendertest.cpp>
+#include <roads/roadsegment.cpp>
+#include <roads/roadsegmentdata.cpp>
+#include <roads/trafficcontrol.cpp>
diff --git a/game/code/roads/geometry.cpp b/game/code/roads/geometry.cpp
new file mode 100644
index 0000000..d6ed51d
--- /dev/null
+++ b/game/code/roads/geometry.cpp
@@ -0,0 +1,1024 @@
+//=============================================================================
+// Copyright (C) 2002 Radical Entertainment Ltd. All rights reserved.
+//
+// File: geometry.cpp
+//
+// Description: Some linear algebra/geometry stuff mostly used in traffic
+// Also contains some useful structures.
+//
+// History: 09/09/2002 + Created -- Dusit Eakkachaichanvet
+//
+//=============================================================================
+
+
+
+#include <roads/geometry.h>
+#include <raddebug.hpp>
+
+/*
+//////////////////////////////////////////////////////////////////////////////
+// OLD OLD OLD STUFF
+//////////////////////////////////////////////////////////////////////////////
+
+bool fequals(float a, float b)
+{
+ return (rmt::Fabs(a-b)<=MYEPSILON)? true: false;
+}
+bool fequals(float a, float b, float epsilon)
+{
+ return (rmt::Fabs(a-b)<=epsilon)? true: false;
+}
+bool isVerticalLine( Line line )
+{
+ if( fequals(line.x1,line.x2) )
+ {
+ return true;
+ }
+ return false;
+}
+Line getLine( float x1, float y1, float x2, float y2, bool isInfinite )
+{
+ Line line;
+ line.x1 = x1;
+ line.y1 = y1;
+ line.x2 = x2;
+ line.y2 = y2;
+ line.isVertical = isVerticalLine( line );
+ if( !line.isVertical )
+ {
+ line.slope = (line.y2 - line.y1)/(line.x2 - line.x1);
+ line.b = line.y2 - line.slope * line.x2;
+ }
+ line.isInfinite = isInfinite;
+ line.isFinishLine = false;
+ return line;
+}
+bool isPointOnLine( Line line, Point p )
+{
+ // test first if point lies in line equation
+ if( !line.isVertical )
+ {
+ if( fequals(p.y, line.slope * p.x + line.b) )
+ {
+ // Ok, so we've verified that p lies on the line.
+ // now if the line is infinite, we're done
+ if( line.isInfinite )
+ {
+ return true;
+ }
+
+ // else test if point lies on line itself we always make sure
+ // x1 < x2 and y1 < y2, swapping values as needed.
+ if( line.x2 < line.x1 )
+ {
+ float temp = line.x2;
+ line.x2 = line.x1;
+ line.x1 = temp;
+ }
+ if( line.y2 < line.y1 )
+ {
+ float temp = line.y2;
+ line.y2 = line.y1;
+ line.y1 = temp;
+ }
+
+ // now check if p.x lies between acceptable values of x
+ // and if p.y lies between acceptable values of y
+ if( (line.x1 - MYEPSILON < p.x && p.x < line.x2 + MYEPSILON ) &&
+ (line.y1 - MYEPSILON < p.y && p.y < line.y2 + MYEPSILON ) )
+ {
+ return true;
+ }
+ }
+ }
+ else
+ { // if vertical line
+ if( fequals(p.x,line.x1) )
+ {
+ if( line.isInfinite )
+ {
+ return true;
+ }
+ if( line.y2 < line.y1 )
+ {
+ float temp = line.y2;
+ line.y2 = line.y1;
+ line.y1 = temp;
+ }
+
+ if( line.y1 - MYEPSILON < p.y && p.y < line.y2 + MYEPSILON )
+ {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+//==============================================================================
+// Helper function: IntersectLines2D
+//===============================================================================
+// Description: Intersects two co-planar lines
+//
+// Parameters: (rmt::Vector) (rmt::Vector) (rmt::Vector) (rmt::Vector) (rmt::Vector&)
+//
+// Return: bool
+//
+//==============================================================================
+bool IntersectLines2D( rmt::Vector p1,
+ rmt::Vector dir1,
+ rmt::Vector p2,
+ rmt::Vector dir2,
+ rmt::Vector& p )
+{
+ // These will temporarily contain our intersection point coords
+ // Remember that Point and Line work on x-y plane, not x-z plane
+ // so let y = z
+ //
+ Point pTemp;
+
+ rmt::Vector q1 = p1 + dir1;
+ rmt::Vector q2 = p2 + dir2;
+
+ Line line1 = getLine( p1.x, p1.z, q1.x, q1.z, true );
+ Line line2 = getLine( p2.x, p2.z, q2.x, q2.z, true );
+
+
+ // treat vertical cases separately
+ if( line1.isVertical && line2.isVertical )
+ {
+ return false;
+ }
+ else if( line1.isVertical && !line2.isVertical )
+ {
+ // line1 is vertical and line2 is not, so pluck line1's
+ // x-value into line2's equation to find y coord of
+ // the potential intersection point.
+ pTemp.x = line1.x1;
+ pTemp.y = line2.slope * pTemp.x + line2.b;
+ if( isPointOnLine(line1,pTemp) && isPointOnLine(line2,pTemp) )
+ {
+ p.x = pTemp.x;
+ p.y = p1.y;
+ p.z = pTemp.y;
+ return true;
+ }
+ return false;
+ }
+ //else if( !isVerticalLine(line1) && isVerticalLine(line2) )
+ else if( !line1.isVertical && line2.isVertical )
+ {
+ // same as case above, but switch line1, line2
+ pTemp.x = line2.x1;
+ pTemp.y = line1.slope * pTemp.x + line1.b;
+ if( isPointOnLine(line1,pTemp) && isPointOnLine(line2,pTemp) )
+ {
+ p.x = pTemp.x;
+ p.y = p1.y;
+ p.z = pTemp.y;
+ return true;
+ }
+ return false;
+ }
+ else
+ { //both non vertical
+
+ if( line1.slope == line2.slope )
+ return false;
+
+ // find intersection point
+ pTemp.x = (line2.b-line1.b)/(line1.slope-line2.slope);
+ pTemp.y = line1.slope* pTemp.x + line1.b;
+
+ // make sure this point lies within the bounds of both lines
+ if( isPointOnLine(line1,pTemp) && isPointOnLine(line2,pTemp) )
+ {
+ p.x = pTemp.x;
+ p.y = p1.y;
+ p.z = pTemp.y;
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ return false; // just in case
+}
+*/
+
+
+//////////////////////////////////////////////////////////////////////////////////
+// CUBIC BEZIER SHEEYATSU
+//////////////////////////////////////////////////////////////////////////////////
+
+bool CubicBezier::sIsInitialized = false;
+float CubicBezier::B0[CubicBezier::MAX_CURVE_POINTS] = {0.0f};
+float CubicBezier::B1[CubicBezier::MAX_CURVE_POINTS] = {0.0f};
+float CubicBezier::B2[CubicBezier::MAX_CURVE_POINTS] = {0.0f};
+float CubicBezier::B3[CubicBezier::MAX_CURVE_POINTS] = {0.0f};
+
+
+void CubicBezier::InitOnceLUTs()
+{
+ if( sIsInitialized )
+ {
+ return;
+ }
+
+ float bias = 1.0f / (float)(MAX_CURVE_POINTS - 1);
+
+ int i = MAX_CURVE_POINTS - 1;
+ float t = 0.0f, t2, t3;
+ for( i = MAX_CURVE_POINTS-1; i>=0; i-- )
+ {
+ t2 = t*t;
+ t3 = t2*t;
+
+ // Fill the LUTs
+ B0[i] = t3;
+ B1[i] = 3.0f * t2 * (1.0f-t);
+ B2[i] = 3.0f * t * (1.0f-t)*(1.0f-t);
+ B3[i] = (1.0f-t)*(1.0f-t)*(1.0f-t);
+
+ t += bias;
+ }
+
+ rAssert( i == -1);
+
+ sIsInitialized = true;
+}
+
+
+
+CubicBezier::CubicBezier()
+{
+ if( !CubicBezier::sIsInitialized )
+ {
+ CubicBezier::InitOnceLUTs();
+ }
+
+ mCurveIsCreated = false;
+ mCurveIsCreated2D = false;
+ mNumControlPointsAdded = 0;
+
+ rmt::Vector dummy( 0.0f, 0.0f, 0.0f );
+ int i;
+ for( i=0; i<CubicBezier::MAX_CONTROL_POINTS; i++ )
+ {
+ AddControlPoint( dummy );
+ }
+}
+
+CubicBezier::~CubicBezier()
+{
+}
+
+void CubicBezier::GetCubicBezierCurve(rmt::Vector*& pts, int& nPts)
+{
+ if( !mCurveIsCreated )
+ {
+ CreateCubicBezierCurve();
+ }
+ pts = mCurve;
+ nPts = MAX_CURVE_POINTS;
+}
+
+void CubicBezier::GetCubicBezierCurve2D(rmt::Vector*& pts, int& nPts)
+{
+ if( !mCurveIsCreated2D )
+ {
+ CreateCubicBezierCurve2D();
+ }
+ pts = mCurve2D;
+ nPts = MAX_CURVE_POINTS;
+}
+
+void CubicBezier::SetControlPoint( const rmt::Vector &cp, const int index )
+{
+ rAssert( 0 <= index && index < mNumControlPointsAdded );
+
+ mCurveIsCreated = false;
+ mCurveIsCreated2D = false;
+ mControlPoints[index] = cp;
+}
+
+void CubicBezier::AddControlPoint( const rmt::Vector &cp )
+{
+ rAssert( 0 <= mNumControlPointsAdded && mNumControlPointsAdded < MAX_CONTROL_POINTS );
+
+ mCurveIsCreated = false;
+ mCurveIsCreated2D = false;
+ mControlPoints[mNumControlPointsAdded] = cp;
+ mNumControlPointsAdded++;
+}
+
+
+void CubicBezier::CreateCubicBezierCurve()
+{
+ rAssert( mNumControlPointsAdded == MAX_CONTROL_POINTS );
+
+ if( mCurveIsCreated )
+ {
+ return;
+ }
+
+ int i;
+ for( i=0; i<MAX_CURVE_POINTS; i++ )
+ {
+ mCurve[i] = mControlPoints[0] * B0[i] +
+ mControlPoints[1] * B1[i] +
+ mControlPoints[2] * B2[i] +
+ mControlPoints[3] * B3[i];
+ }
+ mCurveIsCreated = true;
+
+}
+
+void CubicBezier::CreateCubicBezierCurve2D()
+{
+ rAssert( mNumControlPointsAdded == MAX_CONTROL_POINTS );
+
+ if( mCurveIsCreated2D )
+ {
+ return;
+ }
+
+ float ep = 0.1f;
+
+ // **** ASSERT INFORMATION ***
+ // If you encounter this assert, it means that the road segments in a nearby
+ // intersection don't have same values of y where they hit the intersection
+ // (intersection isn't horizontal). This is due to BAD ROAD DATA ON WORLD BUILDER SIDE.
+ //
+ // Because we're using CubicBezier in 2D now, the intersection must be FLAT!
+ // Or cars will "hop" when they make the turn.
+ //
+ // Please notify Sheik to check the road data around nearby intersections.
+ rAssert( rmt::Epsilon( mControlPoints[0].y, mControlPoints[1].y, ep ) &&
+ rmt::Epsilon( mControlPoints[0].y, mControlPoints[2].y, ep ) &&
+ rmt::Epsilon( mControlPoints[0].y, mControlPoints[3].y, ep ) );
+
+ int i;
+ for( i=0; i<MAX_CURVE_POINTS; i++ )
+ {
+ mCurve2D[i].x = mControlPoints[0].x * B0[i] +
+ mControlPoints[1].x * B1[i] +
+ mControlPoints[2].x * B2[i] +
+ mControlPoints[3].x * B3[i];
+
+ mCurve2D[i].y = mControlPoints[0].y;
+
+ mCurve2D[i].z = mControlPoints[0].z * B0[i] +
+ mControlPoints[1].z * B1[i] +
+ mControlPoints[2].z * B2[i] +
+ mControlPoints[3].z * B3[i];
+ }
+ mCurveIsCreated2D = true;
+
+}
+
+/////////////////////////////////////////////////////////////////
+// DListArray Class Definition
+//////////////////////////////////////////////////////////////////
+
+DListArray::DListArray()
+{
+ this->Clear();
+}
+
+
+void DListArray::Clear()
+{
+ int i=0;
+ for( i ; i<(MAX_ELEMS-1) ; ++i )
+ {
+ mElems[i].data = NULL;
+ mElems[i].next = i+1;
+ mElems[i].prev = -1;
+ }
+ mElems[i].data = NULL;
+ mElems[i].next = -1;
+ mElems[i].prev = -1;
+
+ mHead = -1;
+ mTail = -1;
+ mFree = 0;
+
+ mnElems = 0;
+}
+
+// returns the index value of the newly added element
+// or -1 on error
+int DListArray::AddLast( void* data )
+{
+ assert( data != NULL );
+
+ if( mFree == -1 )
+ {
+ return -1;
+ }
+
+ mElems[mFree].data = data;
+ mElems[mFree].prev = mTail;
+
+ if( mnElems > 0 )
+ {
+ mElems[mTail].next = mFree;
+ }
+ else
+ {
+ mHead = mFree;
+ }
+
+ mTail = mFree;
+ mFree = mElems[mFree].next;
+ mElems[mTail].next = -1;
+
+ mnElems++;
+ return mTail;
+}
+
+// returns the index value of the newly added element
+// or -1 on error
+int DListArray::AddFirst( void* data )
+{
+ assert( data != NULL );
+
+ if( mFree == -1 )
+ {
+ return -1;
+ }
+
+ int newIndex = mFree;
+ mFree = mElems[mFree].next;
+
+ mElems[newIndex].data = data;
+ mElems[newIndex].next = mHead;
+
+ if( mnElems > 0 )
+ {
+ mElems[mHead].prev = newIndex;
+ }
+ else
+ {
+ mTail = newIndex;
+ }
+
+ mHead = newIndex;
+
+ mnElems++;
+ return mHead;
+}
+
+
+// returns index value of the newly inserted element
+// or -1 on error
+int DListArray::InsertAfter( void* data, int i )
+{
+ assert( mnElems >= 1 );
+ assert( data != NULL );
+ assert( 0 <= i && i < MAX_ELEMS );
+ assert( mElems[i].data != NULL );
+
+ if( mFree == -1 )
+ {
+ return -1;
+ }
+
+ int newIndex = mFree;
+ mFree = mElems[mFree].next;
+
+ mElems[newIndex].data = data;
+ mElems[newIndex].prev = i;
+ mElems[newIndex].next = mElems[i].next;
+
+ if( mElems[i].next != -1 )
+ {
+ mElems[ mElems[i].next ].prev = newIndex;
+ }
+ else
+ {
+ mTail = newIndex;
+ }
+
+ mElems[i].next = newIndex;
+
+ mnElems++;
+ return newIndex;
+}
+
+//
+bool DListArray::Remove( void* data )
+{
+ assert( data != NULL );
+
+ int i = 0;
+ bool res = false;
+ for( i ; i<mnElems ; i++ )
+ {
+ if( mElems[i].data == data )
+ {
+ res = true;
+ break;
+ }
+ }
+ if( res )
+ {
+ res = Remove(i);
+ }
+ return res;
+}
+
+bool DListArray::Remove( int i )
+{
+ assert( 0 <= i && i < MAX_ELEMS );
+ assert( mElems[i].data != NULL );
+
+ if( mnElems <= 0 )
+ {
+ return false;
+ }
+
+ if( mElems[i].next != -1 )
+ {
+ mElems[ mElems[i].next ].prev = mElems[i].prev;
+ }
+ else
+ {
+ mTail = mElems[i].prev;
+ }
+
+ if( mElems[i].prev != -1 )
+ {
+ mElems[ mElems[i].prev ].next = mElems[i].next;
+ }
+ else
+ {
+ mHead = mElems[i].next;
+ }
+
+ mElems[i].next = mFree;
+ mElems[i].prev = -1;
+ mElems[i].data = NULL;
+
+ mFree = i;
+
+ mnElems--;
+ return true;
+}
+
+int DListArray::Find( void* data )
+{
+ rAssert( data != NULL );
+
+ int i = 0;
+ for( i ; i<mnElems ; i++ )
+ {
+ if( mElems[i].data == data )
+ {
+ return i;
+ }
+ }
+ return -1;
+}
+
+
+
+//////////////////////////////////////////////////////////////////////////////
+// MISC
+//////////////////////////////////////////////////////////////////////////////
+
+// for Ray p1 to p2 and sphere 2
+// return number of intersection points and the intersection points
+// q1 and q2
+int IntersectLineSphere( const rmt::Vector& p1,
+ const rmt::Vector& p2,
+ const rmt::Sphere& s,
+ rmt::Vector* intPts )
+{
+
+ float X1 = (float)p1.x;
+ float X2 = (float)p2.x;
+ float X3 = (float)s.centre.x;
+ float Y1 = (float)p1.y;
+ float Y2 = (float)p2.y;
+ float Y3 = (float)s.centre.y;
+ float Z1 = (float)p1.z;
+ float Z2 = (float)p2.z;
+ float Z3 = (float)s.centre.z;
+ float Sr = (float)s.radius;
+
+ float A, B, C;
+ A = (X2 - X1)*(X2 - X1) + (Y2 - Y1)*(Y2 - Y1) + (Z2 - Z1)*(Z2 - Z1);
+ B = (X2 - X1)*(X1 - X3) + (Y2 - Y1)*(Y1 - Y3) + (Z2 - Z1)*(Z1 - Z3);
+ C = (X1 - X3)*(X1 - X3) + (Y1 - Y3)*(Y1 - Y3) + (Z1 - Z3)*(Z1 - Z3) - Sr*Sr;
+ //B = 2 * ((X2 - X1)*(X1 - X3) + (Y2 - Y1)*(Y1 - Y3) + (Z2 - Z1)*(Z1 - Z3));
+ //C = X3*X3 + Y3*Y3 + Z3*Z3 + X1*X1 + Y1*Y1 + Z1*Z1 - 2*(X3*X1 + Y3*Y1 + Z3*Z1) - Sr*Sr;
+
+ float discriminant = B*B - A*C;
+ //float discriminant = B*B - 4*A*C;
+ float t[2];
+
+
+ if( discriminant < 0.0f )
+ {
+ return 0;
+ }
+ else if( rmt::Epsilon(discriminant, 0.0f, 0.001f) )
+ {
+ //t[0] = (-1*B)/2*A;
+ t[0] = (-1*B)/A;
+
+ if( 0.0f <= t[0] && t[0] <= 1.0f )
+ {
+ intPts[0].Set(
+ (float)(X1+t[0]*(X2-X1)),
+ (float)(Y1+t[0]*(Y2-Y1)),
+ (float)(Z1+t[0]*(Z2-Z1)));
+ return 1;
+ }
+ return 0;
+ }
+ else
+ {
+ float sqrtDiscriminant = rmt::Sqrt(discriminant); // *** SQUARE ROOT! ***
+// t[0] = (-1*B - sqrtDiscriminant) / 2*A;
+// t[1] = (-1*B + sqrtDiscriminant) / 2*A;
+ t[0] = (-1*B - sqrtDiscriminant) / A;
+ t[1] = (-1*B + sqrtDiscriminant) / A;
+
+ rmt::Vector testVec;
+ int i=0, j=0;
+ for( i; i<2; i++)
+ {
+ if( 0.0f <= t[i] && t[i] <= 1.0f )
+ {
+ intPts[j].Set(
+ (float)(X1+t[i]*(X2-X1)),
+ (float)(Y1+t[i]*(Y2-Y1)),
+ (float)(Z1+t[i]*(Z2-Z1)));
+ j++;
+ }
+ }
+ return j;
+ }
+ return -1;
+}
+
+
+bool TestIntersectLineSphere( const rmt::Vector& lOrig,
+ const rmt::Vector& lDir,
+ const rmt::Sphere& s )
+{
+ rmt::Vector closestPtOnLine;
+ FindClosestPointOnLine( lOrig, lOrig+lDir, s.centre, closestPtOnLine );
+
+ float distSqr = (s.centre - closestPtOnLine).MagnitudeSqr();
+ bool res = distSqr <= (s.radius * s.radius);
+ return res;
+}
+
+
+
+// Test using (normalized) myHeading DOT vectorFromMyHeadingToTarget
+bool WillCollide( const rmt::Vector& myPos,
+ const rmt::Vector& myHeading, // Must be normalized
+ const rmt::Vector& mySide, // Must be normalized
+ float myRadius,
+ float myLookAheadDist,
+ const rmt::Vector& targetPos,
+ bool& targetOnMyRightSide )
+{
+ rmt::Vector toTarget = targetPos - myPos;
+ float myLookAheadDistSqr = myLookAheadDist * myLookAheadDist;
+
+ // if target lies within my look-ahead distance
+ if( toTarget.MagnitudeSqr() < myLookAheadDistSqr )
+ {
+ float frontOrBehindTest = myHeading.Dot( toTarget );
+ if( frontOrBehindTest > 0.0f )
+ {
+ // target is in front, which is a concern...
+ float lateralDist = mySide.Dot( toTarget );
+ if( lateralDist > 0.0f )
+ {
+ targetOnMyRightSide = true;
+ }
+ else
+ {
+ targetOnMyRightSide = false;
+ }
+ lateralDist = rmt::Fabs( lateralDist );
+
+ // if target is in our path
+ if( lateralDist <= myRadius )
+ {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+
+rmt::Vector UpdateVUP( const rmt::Vector& position, const rmt::Vector& target )
+{
+ const float epsilon = 0.01f;
+ //Set the vUP by projecting the heading into the ZX plane and creating a
+ //crossproduct of a right angle to the projected heading along the X axis
+ //and the heading.
+ rmt::Vector X, Y, Z;
+ Z.Sub(target, position);
+ X.Set(Z.z, 0, -Z.x);
+
+ if ( rmt::Epsilon( X.x, 0, epsilon ) &&
+ rmt::Epsilon( X.y, 0, epsilon ) &&
+ rmt::Epsilon( X.z, 0, epsilon ) )
+ {
+ //Then the camera is looking straight down.
+ Y.Set( 0, 0, 1.0f ); //Up along the Z...
+ }
+ else
+ {
+ Y.CrossProduct(Z, X);
+ Y.Normalize(); // *** SQUARE ROOT! ***
+ }
+
+ return Y;
+}
+
+// Given points P1 and P2, and two points that define a line, A and B
+// P1 and P2 are on the same side of the line, if the Normals for BAxP1A
+// and BAxP2A are pointing on the same side of the plane (i.e.
+// N1-dot-N2 >= 0)
+
+bool PointsOnSameSideOfLine( const rmt::Vector& P1,
+ const rmt::Vector& P2,
+ const rmt::Vector& A,
+ const rmt::Vector& B )
+{
+ rmt::Vector BA, P1A, P2A, crossP1, crossP2;
+
+ BA.Sub( B, A );
+ P1A.Sub( P1, A );
+ P2A.Sub( P2, A );
+
+ crossP1.CrossProduct( BA, P1A );
+ crossP2.CrossProduct( BA, P2A );
+ if( crossP1.Dot(crossP2) >= 0 )
+ {
+ return true;
+ }
+ return false;
+}
+
+
+
+// Given triangle with vertices v1, v2, v3 and a point p
+// p is inside triangle if it is on the same side of line v1v2 as v3
+// and on the same side of line v2v3 as v1,
+// and on the same side of line v1v3 as v2
+//
+// NOTE: Because we use Which-Side-of-Line solution, the point
+// that is "within" a triangle is not necessarily on the
+// same plane as the triangle (it could still be above or
+// below the actual triangle, as long as it lies within the infinite
+// planes formed by the 3 sides of the triangle.
+//
+bool PointLiesInTriangle ( const rmt::Vector& p,
+ const rmt::Vector& v1,
+ const rmt::Vector& v2,
+ const rmt::Vector& v3 )
+{
+ if( PointsOnSameSideOfLine( p, v1, v2, v3 ) &&
+ PointsOnSameSideOfLine( p, v2, v1, v3 ) &&
+ PointsOnSameSideOfLine( p, v3, v1, v2 ) )
+ {
+ return true;
+ }
+ return false;
+}
+
+
+rmt::Vector GetProjectionVector( const rmt::Vector& source, const rmt::Vector& target )
+{
+ return target * ( target.Dot(source) / target.Dot(target) );
+}
+
+// In Lefthand coordinate system, turn vector to
+// the left (counter-clockwise) 90 degrees about Y axis & return new vector
+rmt::Vector Get90DegreeLeftTurn( const rmt::Vector& orig )
+{
+ rmt::Vector newVec;
+ newVec.Set( -1 * orig.z, orig.y, orig.x );
+ return newVec;
+}
+
+// In Lefthand coordinate system, turn vector to
+// the right (clockwise) 90 degrees about Y axis & return new vector
+rmt::Vector Get90DegreeRightTurn( const rmt::Vector& orig )
+{
+ rmt::Vector newVec;
+ newVec.Set( orig.z, orig.y, -1 * orig.x );
+ return newVec;
+}
+
+
+float GetRotationAboutY( float x, float z )
+{
+ float angle = 0.0f;
+ if( rmt::Epsilon(x, 0.0f) && rmt::Epsilon(z, 0.0f) )
+ {
+ angle = 0.0f;
+ }
+ else
+ {
+ // generate angle from x-z vector
+ // - assumes DEFAULT_FACING_VECTOR is (0,0,-1)
+ // - assumes UP VECTOR is (0,1,0)
+ angle = rmt::ATan2(x, z);
+ if( rmt::IsNan(angle) )
+ {
+ angle = 0.0f;
+ }
+
+ /*
+ angle = rmt::ATan2(-x, -z);
+
+ // wrap to [0, 2*pi)
+ if (angle < 0.0f)
+ {
+ angle += rmt::PI_2;
+ }
+ */
+ }
+ return angle;
+}
+
+
+bool PointToLineProjection2D( const rmt::Vector& inPt,
+ const rmt::Vector& linePt1,
+ const rmt::Vector& linePt2,
+ rmt::Vector& outPt )
+{
+ // The beauty of calling this 2D function is that we break it down into components
+ // so we don't do unnecessary float ops for the y values
+ float x1,x2,x3,z1,z2,z3;
+ x1 = linePt1.x;
+ x2 = linePt2.x;
+ x3 = inPt.x;
+ z1 = linePt1.z;
+ z2 = linePt2.z;
+ z3 = inPt.z;
+
+ // make sure we were given a line, not a point dammit!
+ rAssertMsg( !( rmt::Epsilon( x1,x2,0.0005f ) && rmt::Epsilon( z1,z2,0.0005f )),
+ "PointToLineProjection2D: The two points of the \"line\" are too close together.\n" );
+
+ // THEORY
+ // ======
+ // Let outPt be the point resulting from projecting inPt onto
+ // linesegment [linePt2 - linePt1]:
+ //
+ // 1) outPt = linePt1 + u * [linePt2 - linePt1];
+ //
+ // Since the projection is at Right Angle, we can say that the lines
+ // [linePt2 - linePt1] and [inPt - outPt] have zero-length dotproduct:
+ //
+ // 2) [inPt - outPt] dot [linePt2 - linePt1] = 0
+ //
+ // Substituting 1) into 2) gives:
+ //
+ // 3) [ inPt - [linePt1+u*[linePt2 - linePt1]] ] dot [linePt2 - linePt1] = 0
+ //
+ // Solving for u gives:
+ //
+ float x2MINUSx1 = x2-x1;
+ float z2MINUSz1 = z2-z1;
+ float u = ( (x3-x1)*x2MINUSx1 + (z3-z1)*z2MINUSz1 ) /
+ ( (x2MINUSx1*x2MINUSx1)+(z2MINUSz1*z2MINUSz1) );
+
+ // Populate the return point
+ outPt.Set( x1 + u*x2MINUSx1, inPt.y, z1 + u*z2MINUSz1 );
+
+ // If u is not on the line segment, outPt will not be in bounds
+ if( u < 0.0f || u > 1.0f )
+ {
+ return false;
+ }
+ return true;
+}
+
+
+bool PointOnLeftSideOfLine( const rmt::Vector& p,
+ const rmt::Vector& start,
+ const rmt::Vector& end )
+{
+ rmt::Vector start2p = p - start;
+ rmt::Vector start2end = end - start;
+ rmt::Vector leftVec = Get90DegreeLeftTurn( start2end );
+
+ float dp = leftVec.Dot( start2p );
+ if( dp > 0.0f ) // +ve means on the left
+ {
+ return true;
+ }
+ return false;
+}
+
+bool PointOnRightSideOfLine( const rmt::Vector& p,
+ const rmt::Vector& start,
+ const rmt::Vector& end )
+{
+ rmt::Vector start2p = p - start;
+ rmt::Vector start2end = end - start;
+ rmt::Vector rightVec = Get90DegreeRightTurn( start2end );
+
+ float dp = rightVec.Dot( start2p );
+ if( dp > 0.0f ) // +ve means on the right
+ {
+ return true;
+ }
+ return false;
+}
+
+float FindClosestPointOnLine( const rmt::Vector& start,
+ const rmt::Vector& end,
+ const rmt::Vector& p,
+ rmt::Vector& closestPt )
+{
+
+ rmt::Vector start2p = p - start;
+ rmt::Vector lDir = end - start;
+
+ float lDirMagSqr = lDir.Dot(lDir);
+
+ // if end and start are basically the same point,
+ // then lDir is zero. So the closest point returned
+ // is that point
+ //
+ if( rmt::Epsilon( lDirMagSqr, 0.0f, 0.001f ) )
+ {
+ closestPt = end;
+ return 0.0f;
+ }
+
+ float scale = lDir.Dot( start2p ) / lDirMagSqr;
+ if( scale > 1.0f )
+ {
+ closestPt = end;
+ }
+ else if( scale < 0.0f )
+ {
+ closestPt = start;
+ }
+ else
+ {
+ closestPt = start + lDir * scale;
+ }
+ return scale;
+}
+
+float GetLineSegmentT
+(
+ const rmt::Vector& segStart,
+ const rmt::Vector& segEnd,
+ const rmt::Vector& pt
+)
+{
+ float e = 0.0001f;
+
+#if defined( RAD_DEBUG ) || defined( RAD_TUNE )
+ // make sure this point is on the line
+ rmt::Vector closestPt;
+ FindClosestPointOnLine( segStart, segEnd, pt, closestPt );
+ rAssert( closestPt.Equals( pt, e ) );
+#endif
+
+ float segT = 0.0f;
+ if( rmt::Epsilon( segEnd.x, segStart.x, e ) )
+ {
+ if( rmt::Epsilon( segEnd.y, segStart.y, e ) )
+ {
+ if( rmt::Epsilon( segEnd.z, segStart.z, e ) )
+ {
+ segT = 0.0f;
+ }
+ else
+ {
+ segT = (pt.z - segStart.z) / (segEnd.z - segStart.z);
+ }
+ }
+ else
+ {
+ segT = (pt.y - segStart.y) / (segEnd.y - segStart.y);
+ }
+ }
+ else
+ {
+ segT = (pt.x - segStart.x) / (segEnd.x - segStart.x);
+ }
+ rAssert( 0.0f <= segT && segT <= 1.0f );
+ return segT;
+} \ No newline at end of file
diff --git a/game/code/roads/geometry.h b/game/code/roads/geometry.h
new file mode 100644
index 0000000..66620da
--- /dev/null
+++ b/game/code/roads/geometry.h
@@ -0,0 +1,448 @@
+//=============================================================================
+// Copyright (C) 2002 Radical Entertainment Ltd. All rights reserved.
+//
+// File: geometry.h
+//
+// Description: Some linear algebra/geometry stuff mostly used in traffic
+// Also contains some useful structures.
+//
+// History: 09/09/2002 + Created -- Dusit Eakkachaichanvet
+//
+//=============================================================================
+
+
+
+#ifndef GEOMETRY_H
+#define GEOMETRY_H
+
+// *************************
+// 2D & 3D GEOMETRY HELPERS
+// *************************
+#include <radmath/radmath.hpp>
+#include <raddebug.hpp> // for rAssert & other debug print outs
+
+/*
+//////////////////////////////////////////////////////////////////////////////
+// OLD OLD OLD STUFF
+//////////////////////////////////////////////////////////////////////////////
+#ifndef PI_F
+#define PI_F 3.1415926535897932384626433832795f
+#endif
+#define MYEPSILON 0.001
+#ifndef NULL
+ #define NULL 0
+#endif
+struct Line
+{
+ float x1;
+ float y1;
+ float x2;
+ float y2;
+ float slope;
+ float b;
+ bool isVertical;
+ bool isInfinite;
+ bool isFinishLine;
+};
+
+struct Point
+{
+ float x;
+ float y;
+ int id;
+};
+bool fequals(float a, float b);
+bool fequals(float a, float b, float epsilon);
+bool isVerticalLine( Line line );
+Line getLine( float x1, float y1, float x2, float y2, bool isInfinite );
+bool isPointOnLine( Line line, Point p );
+bool IntersectLines2D( rmt::Vector p1,
+ rmt::Vector dir1,
+ rmt::Vector p2,
+ rmt::Vector dir2,
+ rmt::Vector& p );
+*/
+
+//////////////////////////////////////////////////////////////////////////////
+// CUBIC BEZIER SHEEYATSU
+//////////////////////////////////////////////////////////////////////////////
+
+class CubicBezier
+{
+public:
+ enum
+ {
+ MAX_CONTROL_POINTS = 4, // total control points (including start & end points)
+ MAX_CURVE_POINTS = 30 // total curve points including start & end points
+ };
+
+ static void InitOnceLUTs();
+
+ static bool sIsInitialized;
+ static float B0[MAX_CURVE_POINTS];
+ static float B1[MAX_CURVE_POINTS];
+ static float B2[MAX_CURVE_POINTS];
+ static float B3[MAX_CURVE_POINTS];
+
+ CubicBezier();
+ ~CubicBezier();
+
+ void GetCubicBezierCurve(rmt::Vector*& pts, int& nCurvePts);
+ void GetCubicBezierCurve2D(rmt::Vector*& pts, int& nCurvePts);
+ void AddControlPoint(const rmt::Vector& cp);
+ void SetControlPoint(const rmt::Vector& cp, int index);
+
+
+protected:
+
+ void CreateCubicBezierCurve();
+ void CreateCubicBezierCurve2D();
+
+ rmt::Vector mCurve[MAX_CURVE_POINTS];
+ rmt::Vector mCurve2D[MAX_CURVE_POINTS];
+ rmt::Vector mControlPoints[MAX_CONTROL_POINTS];
+ int mNumControlPointsAdded;
+ bool mCurveIsCreated;
+ bool mCurveIsCreated2D;
+
+ //Prevent wasteful constructor creation.
+ CubicBezier( const CubicBezier& CubicBezier );
+ CubicBezier& operator=( const CubicBezier& CubicBezier );
+
+};
+
+
+
+//////////////////////////////////////////////////////////////////////////////
+// DListArray
+//////////////////////////////////////////////////////////////////////////////
+
+class DListArray
+{
+
+public:
+
+ enum
+ {
+ MAX_ELEMS = 20
+ };
+
+ DListArray();
+ void Clear();
+
+ // returns index value of found element, -1 on error
+ int Find( void* data );
+
+ // returns the index value of the newly added element
+ // or -1 on error
+ int AddLast( void* data );
+
+ // returns the index value of the newly added element
+ // or -1 on error
+ int AddFirst( void* data );
+
+ // returns index value of the newly inserted element
+ // or -1 on error
+ int InsertAfter( void* data, int i );
+
+ // Note: this incurs a linear search
+ bool Remove( void* data );
+
+ bool Remove( int i );
+
+ int GetNumElems() const;
+
+ int GetFree() const;
+
+ void* GetDataAt( int i ) const;
+
+ int GetNextOf( int i ) const;
+
+ int GetPrevOf( int i ) const;
+
+ void* GetFirst() const;
+
+ void* GetLast() const;
+
+ int GetHead() const;
+
+ int GetTail() const;
+
+private:
+
+ struct DLAElem
+ {
+ void* data;
+ int next;
+ int prev;
+ };
+
+ DLAElem mElems[MAX_ELEMS];
+ int mnElems;
+ int mHead;
+ int mTail;
+ int mFree;
+
+};
+
+inline int DListArray::GetNumElems() const
+{
+ return mnElems;
+}
+inline int DListArray::GetFree() const
+{
+ return mFree;
+}
+inline void* DListArray::GetDataAt(int i) const
+{
+ return mElems[i].data;
+}
+
+inline void* DListArray::GetFirst() const
+{
+ if( mHead != -1 )
+ {
+ return mElems[mHead].data;
+ }
+ return NULL;
+}
+inline void* DListArray::GetLast() const
+{
+ if( mTail != -1 )
+ {
+ return mElems[mTail].data;
+ }
+ return NULL;
+}
+inline int DListArray::GetHead() const
+{
+ return mHead;
+}
+inline int DListArray::GetTail() const
+{
+ return mTail;
+}
+
+inline int DListArray::GetNextOf( int i ) const
+{
+ rAssert( 0 <= i && i < MAX_ELEMS );
+ return mElems[i].next;
+}
+
+inline int DListArray::GetPrevOf( int i ) const
+{
+ rAssert( 0 <= i && i < MAX_ELEMS );
+ return mElems[i].prev;
+}
+
+
+// history tracking
+template <class T, int HISTORY_SIZE> class History
+{
+public:
+ History() : mNextSpot(0) {}
+ ~History() {}
+
+ void Init( const T& t )
+ {
+ mNextSpot = 0;
+
+ for( int i=0; i< HISTORY_SIZE; i++ )
+ {
+ mHistory[i] = t;
+ }
+
+ mAverage = t;
+ }
+
+ void UpdateHistory( const T& t)
+ {
+ // first get the old value & recalculate our average
+ mAverage -= (mHistory[mNextSpot] - t) / (float)(HISTORY_SIZE);
+ mHistory[mNextSpot] = t;
+ mNextSpot = (mNextSpot + 1) % HISTORY_SIZE;
+ }
+
+ void GetAverage( T& t )
+ {
+ t = mAverage;
+ }
+
+ T GetEntry( int i )
+ {
+ rAssert( 0 <= i && i < HISTORY_SIZE );
+ return mHistory[i];
+ }
+
+ T GetLastEntry()
+ {
+ int i = mNextSpot - 1;
+ if( i == -1 )
+ {
+ i = HISTORY_SIZE - 1;
+ }
+ rAssert( 0 <= i && i < HISTORY_SIZE );
+ return mHistory[i];
+ }
+
+ int GetSize()
+ {
+ return HISTORY_SIZE;
+ }
+
+private:
+ int mNextSpot;
+ T mHistory[HISTORY_SIZE];
+ T mAverage;
+};
+
+template <int HISTORY_SIZE> class VectorHistory : public History<rmt::Vector, HISTORY_SIZE>
+{
+public:
+ VectorHistory() {}
+ ~VectorHistory() {}
+
+ void Init( const rmt::Vector& t )
+ {
+ History<rmt::Vector,HISTORY_SIZE>::Init(t);
+ GetAverage(mNormalizedAverage);
+ }
+
+ void GetNormalizedAverage( rmt::Vector& vec )
+ {
+ if( rmt::Epsilon( mNormalizedAverage.MagnitudeSqr(), 1.0f, 0.0005f ) )
+ {
+ vec = mNormalizedAverage;
+ }
+ else
+ {
+ mNormalizedAverage.NormalizeSafe();
+ vec = mNormalizedAverage;
+ }
+ }
+
+ void UpdateHistory( const rmt::Vector& vec )
+ {
+ History<rmt::Vector,HISTORY_SIZE>::UpdateHistory(vec);
+ GetAverage(mNormalizedAverage);
+ }
+
+protected:
+
+ rmt::Vector mNormalizedAverage;
+};
+
+//////////////////////////////////////////////////////////////////////////////
+// MISC
+//////////////////////////////////////////////////////////////////////////////
+
+const float KPH_2_MPS = 1.0f/3.60f;
+
+// returns true if projection point is on line segment
+bool PointToLineProjection2D( const rmt::Vector& in,
+ const rmt::Vector& linePt1,
+ const rmt::Vector& linePt2,
+ rmt::Vector& out );
+
+rmt::Vector GetProjectionVector( const rmt::Vector& source,
+ const rmt::Vector& target );
+
+// MAYA: GAME:
+// Right-hand coord Left-hand coord
+//
+// +y (forefinger) +y (forefinger)
+// | |
+// | |
+// | |
+// /\ /\
+// / \ / \
+// / \ / \
+// +z (middle) +x (thumb) +x(thumb) +z(middle)
+//
+
+// In Lefthand coordinate system, turn vector to
+// the left (counter-clockwise) 90 degrees & return new vector
+rmt::Vector Get90DegreeLeftTurn( const rmt::Vector& orig );
+
+// In Lefthand coordinate system, turn vector to
+// the right (clockwise) 90 degrees & return new vector
+rmt::Vector Get90DegreeRightTurn( const rmt::Vector& orig );
+
+float GetRotationAboutY( float x, float z );
+
+// returns the number of intersections and po ints q1 & q2
+int IntersectLineSphere( const rmt::Vector& p1,
+ const rmt::Vector& p2,
+ const rmt::Sphere& s,
+ rmt::Vector* intPts);
+
+// just test if line segment intersects sphere... don't bother
+// finding the intersection point(s)
+bool TestIntersectLineSphere( const rmt::Vector& lOrig,
+ const rmt::Vector& lDir,
+ const rmt::Sphere& s );
+
+
+
+// Test using (normalized) myHeading DOT vectorFromMyHeadingToTarget
+bool WillCollide( const rmt::Vector& myPos,
+ const rmt::Vector& myHeading, // Must be normalized
+ const rmt::Vector& mySide, // Must be normalized
+ float myRadius,
+ float myLookAheadDist,
+ const rmt::Vector& targetPos,
+ bool& targetOnMyRightSide );
+
+rmt::Vector UpdateVUP( const rmt::Vector& position, const rmt::Vector& target );
+
+// Given points P1 and P2, and two points that define a line, A and B
+// P1 and P2 are on the same side of the line, if the Normals for BAxP1A
+// and BAxP2A are pointing on the same side of the plane (i.e.
+// N1-dot-N2 >= 0)
+
+bool PointsOnSameSideOfLine( const rmt::Vector& P1,
+ const rmt::Vector& P2,
+ const rmt::Vector& A,
+ const rmt::Vector& B );
+
+
+
+// Given triangle with vertices v1, v2, v3 and a point p
+// p is inside triangle if it is on the same side of line v1v2 as v3
+// and on the same side of line v2v3 as v1,
+// and on the same side of line v1v3 as v2
+//
+bool PointLiesInTriangle ( const rmt::Vector& p,
+ const rmt::Vector& v1,
+ const rmt::Vector& v2,
+ const rmt::Vector& v3 );
+
+
+// Given a point "p", and a line starting at point "start" and ending
+// at point "end", determine if p lies on the left side of the line
+// (assuming that the line is looking in the direction of start-to-end
+//
+bool PointOnLeftSideOfLine( const rmt::Vector& p,
+ const rmt::Vector& start,
+ const rmt::Vector& end );
+
+// Ditto.. but for the right side
+//
+bool PointOnRightSideOfLine( const rmt::Vector& p,
+ const rmt::Vector& start,
+ const rmt::Vector& end );
+
+// Given a line segment described by vector from start to end,
+// and an arbitrary point... return the point on the line segment
+// closest to this arbitrary point and the float parameter along
+// the line segment at which this closest point occurs
+float FindClosestPointOnLine( const rmt::Vector& start,
+ const rmt::Vector& end,
+ const rmt::Vector& p,
+ rmt::Vector& closestPt );
+
+float GetLineSegmentT( const rmt::Vector& segStart,
+ const rmt::Vector& segEnd,
+ const rmt::Vector& pt );
+
+#endif // GEOMETRY_H
diff --git a/game/code/roads/intersection.cpp b/game/code/roads/intersection.cpp
new file mode 100644
index 0000000..25f12f1
--- /dev/null
+++ b/game/code/roads/intersection.cpp
@@ -0,0 +1,1374 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: Intersection
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2001/02/02 Tbrown-John Created
+
+===========================================================================*/
+
+#include <roads/intersection.h>
+#include <roads/road.h>
+#include <roads/roadsegment.h>
+#include <roads/lane.h>
+#include <roads/trafficcontrol.h>
+
+#include <meta/triggerlocator.h>
+#include <memory/srrmemory.h>
+
+// Math includes.
+//
+#ifdef TOOLS
+#include <choreo/utility.hpp>
+#else
+#include <choreo/utility.hpp>
+#endif
+
+
+Intersection::Intersection( void )
+:
+mBigIntersection( 0 ),
+mIndex( -1 ),
+mpTrafficControl( NULL ),
+mnRoadsIn( 0 ),
+mnRoadsOut( 0 ),
+mfRotation( 0.0f ),
+mfRadius( 15.0f )
+{
+ mpAnimEntityList.Allocate(2);
+ int i;
+
+ for ( i = 0; i < MAX_ROADS; i++ )
+ {
+ mRoadListIn[ i ] = 0;
+ mRoadListOut[ i ] = 0;
+ }
+
+ mLightControl.SetIntersection( this );
+ mNWayControl.SetIntersection( this );
+}
+
+Intersection::Intersection( TriggerLocator* pLocator )
+:
+mBigIntersection( 0 ),
+mIndex( -1 ),
+mpTrafficControl( NULL ),
+mnRoadsIn( 0 ),
+mnRoadsOut( 0 ),
+mfRotation( 0.0f ),
+mfRadius( 15.0f )
+{
+ mpAnimEntityList.Allocate(2);
+
+ int i;
+
+ for ( i = 0; i < MAX_ROADS; i++ )
+ {
+ mRoadListIn[ i ] = 0;
+ mRoadListOut[ i ] = 0;
+ }
+ mLightControl.SetIntersection( this );
+ mNWayControl.SetIntersection( this );
+}
+
+Intersection::~Intersection( void )
+{
+ mWaitingRoads.Clear();
+ mShortestRoadsToAdjacentIntersectionsWithMultiplier.Clear();
+ mShortestRoadsToAdjacentIntersectionsNoMultiplier.Clear();
+ mOutgoingShortcuts.Clear();
+ if( mBigIntersection )
+ {
+ mBigIntersection->routesWithMultiplier.Clear();
+ mBigIntersection->routesNoMultiplier.Clear();
+ delete mBigIntersection;
+ }
+}
+// Simulate the intersection when there are cars nearby.
+/*
+==============================================================================
+Intersection::Update
+==============================================================================
+Description: Comment
+
+Parameters: ( unsigned int dt )
+
+Return: void
+
+=============================================================================
+*/
+void Intersection::Update( unsigned int dt )
+{
+ if( mpTrafficControl != NULL )
+ {
+ mpTrafficControl->Update( dt );
+ }
+}
+
+// advance the traffic in roads 'RoadMask' according to light state.
+/*
+==============================================================================
+Intersection::AdvanceTraffic
+==============================================================================
+Description: Comment
+
+Parameters: ( unsigned int RoadMask, unsigned int state )
+
+Return: void
+
+=============================================================================
+*/
+void Intersection::AdvanceTraffic( unsigned int RoadMask, unsigned int state ) const
+{
+ int i;
+
+ for ( i = 0; i < MAX_ROADS; i++ )
+ {
+ unsigned int mask = 1 << i;
+ if ( RoadMask & mask )
+ {
+ if ( mRoadListIn[ i ] )
+ {
+ unsigned int j;
+ for ( j = 0; j < mRoadListIn[i]->GetNumLanes(); j++ )
+ {
+ Lane* pLane = mRoadListIn[i]->GetLane( j );
+ if ( pLane )
+ {
+ pLane->NotifyWaitingTraffic( state );
+ }
+ }
+ }
+ }
+ }
+}
+
+
+void Intersection::AdvanceNextWaitingRoad()
+{
+ if( mWaitingRoads.mUseSize > 0 )
+ {
+ Road* road = mWaitingRoads[0];
+ for( unsigned int i=0; i<road->GetNumLanes(); i++ )
+ {
+ road->GetLane(i)->NotifyWaitingTraffic( TrafficControl::GREEN );
+ }
+ mWaitingRoads.RemoveKeepOrder( 0 );
+ }
+}
+
+// Is the intersection clear of all cars.
+/*
+==============================================================================
+Intersection::IsIntersectionClear
+==============================================================================
+Description: Comment
+
+Parameters: ( void )
+
+Return: bool
+
+=============================================================================
+*/
+bool Intersection::IsIntersectionClear( void ) const
+{
+ // TODO: Implement this properly.
+ return true;
+}
+
+// add a road to the in list.
+/*
+==============================================================================
+Intersection::AddRoadIn
+==============================================================================
+Description: Comment
+
+Parameters: ( Road *pRoad )
+
+Return: void
+
+=============================================================================
+*/
+void Intersection::AddRoadIn( Road *pRoad )
+{
+ mRoadListIn[ mnRoadsIn ] = pRoad;
+ mnRoadsIn++;
+}
+// add a road to the out list.
+/*
+==============================================================================
+Intersection::AddRoadOut
+==============================================================================
+Description: Comment
+
+Parameters: ( Road *pRoad )
+
+Return: void
+
+=============================================================================
+*/
+void Intersection::AddRoadOut( Road *pRoad )
+{
+ mRoadListOut[ mnRoadsOut ] = pRoad;
+ mnRoadsOut++;
+}
+// Find the road pointer in the road list.
+/*
+==============================================================================
+Intersection::FindRoadIn
+==============================================================================
+Description: Comment
+
+Parameters: ( const Road* pRoad )
+
+Return: int
+
+=============================================================================
+*/
+int Intersection::FindRoadIn( const Road* pRoad ) const
+{
+ unsigned int i;
+ for ( i = 0; i < mnRoadsIn; i++ )
+ {
+ if ( pRoad == mRoadListIn[ i ] )
+ {
+ // found it.
+ return i;
+ }
+ }
+ // not found
+ return -1;
+}
+
+// Find the road pointer in the road list.
+/*
+==============================================================================
+Intersection::FindRoadOut
+==============================================================================
+Description: Comment
+
+Parameters: ( const Road* pRoad )
+
+Return: int
+
+=============================================================================
+*/
+int Intersection::FindRoadOut( const Road* pRoad ) const
+{
+ unsigned int i;
+ for ( i = 0; i < mnRoadsOut; i++ )
+ {
+ if ( pRoad == mRoadListOut[ i ] )
+ {
+ // found it.
+ return i;
+ }
+ }
+ // not found
+ return -1;
+}
+
+/*
+==============================================================================
+Intersection::GetLocation
+==============================================================================
+Description: Comment
+
+Parameters: ( void )
+
+Return: const
+
+=============================================================================
+*/
+
+void Intersection::GetLocation( rmt::Vector& location ) const
+{
+ location = mLocation;
+}
+
+
+
+
+void Intersection::PopulateShortestRoads( SwapArray<RoadManager::ShortestRoad>& roadsToAdjacentInts, bool useMultiplier )
+{
+ ////////////
+ // First search through the IN roads, tallying up the shortest, unique IN roads
+ // that get us to distinct adjacent intersections
+
+ for( int i = 0; i< static_cast<int>(mnRoadsIn); i++ )
+ {
+ Road* road = mRoadListIn[i];
+ const Intersection* in = road->GetSourceIntersection();
+
+ // if the road loops back onto same intersection, forget it
+ if( in == this )
+ {
+ continue;
+ }
+
+ // if this is a shortcut road, forget it
+ if( road->GetShortCut() )
+ {
+ continue;
+ }
+
+ RoadManager::ShortestRoad sr;
+ sr.isOutRoad = false;
+ sr.road = road;
+
+ sr.cost = road->GetRoadLength();
+ sr.cost *= useMultiplier ? RoadManager::AGAINST_TRAFFIC_COST_MULTIPLIER : 1.0f;
+
+ // see if we already have this intersection listed
+ // If not, add it.
+ // If found, check if this road is shorter than road listed
+ RoadManager::ShortestRoad* testRoad = NULL;
+ const Intersection* testInt = NULL;
+
+ bool found = false;
+ for( int j=0; j<roadsToAdjacentInts.mUseSize; j++ )
+ {
+ testRoad = &(roadsToAdjacentInts[j]);
+ float testCost = testRoad->road->GetRoadLength();
+
+ if( testRoad->isOutRoad )
+ {
+ testInt = testRoad->road->GetDestinationIntersection();
+ }
+ else
+ {
+ testInt = testRoad->road->GetSourceIntersection();
+ testCost *= useMultiplier ? RoadManager::AGAINST_TRAFFIC_COST_MULTIPLIER : 1.0f;
+ }
+ if( testInt == in )
+ {
+ // ok, found "in" in our list...
+ // if the length of road is shorter, store this road
+ // instead of testRoad
+ found = true;
+
+ if( sr.cost < testCost )
+ {
+ roadsToAdjacentInts.Remove( j );
+ roadsToAdjacentInts.Add( sr );
+ }
+ // we need to break here since we modified the usesize.
+ break;
+ }
+ }
+ // if we never found it in any of our lists, add it to the list of IN roads
+ if( !found )
+ {
+ roadsToAdjacentInts.Add( sr );
+ }
+ }
+
+
+ /////////////////////
+ // Now do the same for the OUT roads
+
+ for( int i = 0; i<static_cast<int>(mnRoadsOut); i++ )
+ {
+ Road* road = mRoadListOut[i];
+ const Intersection* in = road->GetDestinationIntersection();
+
+ // if the road loops back onto same intersection, forget it
+ if( in == this )
+ {
+ continue;
+ }
+
+ // if this is a shortcut road, add it to the shortcut list,
+ // but skip adding it to adjacency list
+ if( road->GetShortCut() )
+ {
+ continue;
+ }
+
+
+ RoadManager::ShortestRoad sr;
+ sr.isOutRoad = true;
+ sr.road = road;
+ sr.cost = road->GetRoadLength();
+
+ // see if we already have this intersection listed
+ // If not, add it.
+ // If found, check if this road is shorter than road listed
+ RoadManager::ShortestRoad* testRoad = NULL;
+ const Intersection* testInt = NULL;
+
+ bool found = false;
+ for( int j=0; j<roadsToAdjacentInts.mUseSize; j++ )
+ {
+ testRoad = &(roadsToAdjacentInts[j]);
+ float testCost = testRoad->road->GetRoadLength();
+
+ if( testRoad->isOutRoad )
+ {
+ testInt = testRoad->road->GetDestinationIntersection();
+ }
+ else
+ {
+ testInt = testRoad->road->GetSourceIntersection();
+ testCost *= useMultiplier ? RoadManager::AGAINST_TRAFFIC_COST_MULTIPLIER : 1.0f;
+ }
+ if( testInt == in )
+ {
+ // ok, "in" already exists in our list...
+ // if the length of road is shorter, store this road
+ // instead of testRoad
+ found = true;
+ if( sr.cost < testCost )
+ {
+ roadsToAdjacentInts.Remove( j );
+ roadsToAdjacentInts.Add( sr );
+ }
+ // we need to break here since we modified the usesize.
+ break;
+ }
+ }
+ // if we never found it in any of our lists, add it to the list of IN roads
+ if( !found )
+ {
+ roadsToAdjacentInts.Add( sr );
+ }
+ }
+}
+
+
+
+
+
+/*
+==============================================================================
+Intersection::SortRoads
+==============================================================================
+Description: Sorts the roads into clockwise order.
+ Pick a road to start, add it to the head of the sorted list.
+ Find the first road to the right of that, add it to the sorted list.
+ Repeat until all roads have been added to the sorted list.
+
+Parameters: ( void )
+
+Return: void
+
+=============================================================================
+*/
+void Intersection::SortRoads( void )
+{
+ struct roadOrientation
+ {
+ Road* pRoad;
+ float fAngle;
+ };
+
+ // a copy of the list of the roads leading in to this intersection.
+ //
+ roadOrientation roadListIn[ MAX_ROADS ];
+
+ // a copy of the list of the roads leading out of this intersection.
+ //
+ roadOrientation roadListOut[ MAX_ROADS ];
+
+ for ( int i = 0; i < MAX_ROADS; i++ )
+ {
+ roadListIn[ i ].pRoad = mRoadListIn[ i ];
+ if ( mRoadListIn[ i ] )
+ {
+ rmt::Vector to, from;
+ // Get the facing vector by finding the two points that connect the road.
+ //
+ roadListIn[ i ].pRoad->GetSourceIntersection()->GetLocation( from );
+ this->GetLocation( to );
+ // Get the vector between and flip it.
+ // Choreo considers 0 0 -1 = 0 degrees.
+ //
+ to.Sub( from );
+ to.Scale( -1.0f );
+
+ roadListIn[ i ].fAngle = choreo::GetWorldAngle( to.x, to.z );
+ }
+
+ roadListOut[ i ].pRoad = mRoadListOut[ i ];
+ if ( mRoadListOut[ i ] )
+ {
+ rmt::Vector to, from;
+ // Get the facing vector by finding the two points that connect the road.
+ //
+ roadListOut[ i ].pRoad->GetDestinationIntersection()->GetLocation( from );
+ this->GetLocation( to );
+ // Get the vector between and flip it.
+ // Choreo considers 0 0 -1 = 0 degrees.
+ //
+ to.Sub( from );
+ to.Scale( -1.0f );
+
+ roadListOut[ i ].fAngle = choreo::GetWorldAngle( to.x, to.z );
+ }
+ }
+
+ for ( int i = 0; i < MAX_ROADS; i++ )
+ {
+ roadOrientation* pRoadOrientation = 0;
+ // A larger angle than would ever be stored.
+ //
+ float fMinAngle = rmt::PI * 4;
+
+ for ( int j = 0; j < MAX_ROADS; j++ )
+ {
+ // Take the smallest remaining angle each time through.
+ //
+ if ( roadListIn[ j ].pRoad && roadListIn[ j ].fAngle < fMinAngle )
+ {
+ // This is the best candidate so far.
+ //
+ fMinAngle = roadListIn[ j ].fAngle;
+ // So store it for later.
+ //
+ pRoadOrientation = &roadListIn[ j ];
+ }
+ }
+ if ( pRoadOrientation )
+ {
+ // Store this road in sorted order.
+ //
+ mRoadListIn[ i ] = pRoadOrientation->pRoad;
+ // Remove the road from consideration.
+ //
+ pRoadOrientation->pRoad = 0;
+ }
+ else
+ {
+ mRoadListIn[ i ] = 0;
+ }
+ }
+
+ for ( int i = 0; i < MAX_ROADS; i++ )
+ {
+ roadOrientation* pRoadOrientation = 0;
+ // A larger angle than would ever be stored.
+ //
+ float fMinAngle = rmt::PI * 4;
+
+ for ( int j = 0; j < MAX_ROADS; j++ )
+ {
+ // Take the smallest remaining angle each time through.
+ //
+ if ( roadListOut[ j ].pRoad && roadListOut[ j ].fAngle < fMinAngle )
+ {
+ // This is the best candidate so far.
+ //
+ fMinAngle = roadListOut[ j ].fAngle;
+ // So store it for later.
+ //
+ pRoadOrientation = &roadListOut[ j ];
+ }
+ }
+ if ( pRoadOrientation )
+ {
+ // Store this road in sorted order.
+ //
+ mRoadListOut[ i ] = pRoadOrientation->pRoad;
+ // Remove the road from consideration.
+ //
+ pRoadOrientation->pRoad = 0;
+ }
+ else
+ {
+ mRoadListOut[ i ] = 0;
+ }
+ }
+
+ //////////////////////////////////////////////////////////////////////////
+ // store shortcut roads going OUT of this intersection..
+ // Note, shortcuts can only be taken one way (e.g. a jump), so we
+ // only consider the OUTGOING shortcut roads...
+
+ SwapArray<Road*> outShortcutRoads;
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ outShortcutRoads.Allocate( MAX_ROADS );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ for( int i = 0; i<static_cast<int>(mnRoadsOut); i++ )
+ {
+ Road* road = mRoadListOut[i];
+ const Intersection* in = road->GetDestinationIntersection();
+
+ // if the road loops back onto same intersection, forget it
+ if( in == this )
+ {
+ continue;
+ }
+
+ // if this is a shortcut road, add it to the shortcut list,
+ // but skip adding it to adjacency list
+ if( road->GetShortCut() )
+ {
+ outShortcutRoads.Add( road );
+ continue;
+ }
+ }
+
+ // also, store away the list of shortcut roads
+ if( outShortcutRoads.mUseSize > 0 )
+ {
+ mOutgoingShortcuts.Allocate( outShortcutRoads.mUseSize );
+ for( int i=0; i<outShortcutRoads.mUseSize; i++ )
+ {
+ mOutgoingShortcuts.Add( outShortcutRoads[i] );
+ }
+ }
+ outShortcutRoads.Clear();
+
+ ////////////////////////////
+ // Determine shortest roads
+ // Store two versions: the one that uses AGAINST_TRAFFIC_COST_MULTIPLIER
+ // and the one that doesn't
+
+ SwapArray<RoadManager::ShortestRoad> roadsToAdjacentInts;
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ roadsToAdjacentInts.Allocate( MAX_ROADS*2 );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ PopulateShortestRoads( roadsToAdjacentInts, true );
+ if( roadsToAdjacentInts.mUseSize > 0 )
+ {
+ mShortestRoadsToAdjacentIntersectionsWithMultiplier.Allocate( roadsToAdjacentInts.mUseSize );
+ for( int i=0; i<roadsToAdjacentInts.mUseSize; i++ )
+ {
+ mShortestRoadsToAdjacentIntersectionsWithMultiplier.Add( roadsToAdjacentInts[i] );
+ }
+ }
+ roadsToAdjacentInts.ClearUse();
+
+ PopulateShortestRoads( roadsToAdjacentInts, false );
+ if( roadsToAdjacentInts.mUseSize > 0 )
+ {
+ mShortestRoadsToAdjacentIntersectionsNoMultiplier.Allocate( roadsToAdjacentInts.mUseSize );
+ for( int i=0; i<roadsToAdjacentInts.mUseSize; i++ )
+ {
+ mShortestRoadsToAdjacentIntersectionsNoMultiplier.Add( roadsToAdjacentInts[i] );
+ }
+ }
+ roadsToAdjacentInts.Clear();
+
+ // the choices of roads maybe different with or without multiplier, but
+ // the sizes of the two arrays should be the same because the number
+ // of reachable, neighboring intersections is the same
+ rAssert( mShortestRoadsToAdjacentIntersectionsWithMultiplier.mUseSize ==
+ mShortestRoadsToAdjacentIntersectionsNoMultiplier.mUseSize );
+
+ // see if we are a big intersection, doesn't matter which size we use here.
+ int numAdjacentInts = mShortestRoadsToAdjacentIntersectionsWithMultiplier.mUseSize;
+ if( numAdjacentInts > 2 )
+ {
+ mBigIntersection = new RoadManager::BigIntersection;
+ mBigIntersection->in = this;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // allocate space for waiting roads... only need to do it for IN roads
+ // because they're the ones approaching the intersection
+ if( mType != Intersection::NO_STOP )
+ {
+ if( mnRoadsIn > 0 )
+ {
+ mWaitingRoads.Allocate( mnRoadsIn );
+ }
+ }
+
+
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Do some checking here, shall we?
+ // Every intersection must have at least 1 neighbor (must be attached to rest of world)
+
+#if( RAD_TUNE || RAD_DEBUG )
+ if( numAdjacentInts <= 0 )
+ {
+ char msg[256];
+ sprintf( msg,
+ "Intersection at (%0.2f,%0.2f,%0.2f) is not joined to any other\n"
+ " intersection by any road!\n",
+ mLocation.x, mLocation.y, -mLocation.z );
+ rTuneAssertMsg( false, msg );
+ }
+#endif
+
+#ifdef RAD_DEBUG
+ for( int i = 0; i<mShortestRoadsToAdjacentIntersectionsWithMultiplier.mUseSize; i++ )
+ {
+ RoadManager::ShortestRoad* shortestRoad =
+ &(mShortestRoadsToAdjacentIntersectionsWithMultiplier[i]);
+
+ Intersection* testInt = NULL;
+ if( shortestRoad->isOutRoad )
+ {
+ testInt = (Intersection*)
+ shortestRoad->road->GetSourceIntersection();
+ }
+ else
+ {
+ testInt = (Intersection*)
+ shortestRoad->road->GetDestinationIntersection();
+ }
+ rAssert( testInt == this );
+ }
+ for( int i = 0; i<mShortestRoadsToAdjacentIntersectionsNoMultiplier.mUseSize; i++ )
+ {
+ RoadManager::ShortestRoad* shortestRoad =
+ &(mShortestRoadsToAdjacentIntersectionsNoMultiplier[i]);
+
+ Intersection* testInt = NULL;
+ if( shortestRoad->isOutRoad )
+ {
+ testInt = (Intersection*)
+ shortestRoad->road->GetSourceIntersection();
+ }
+ else
+ {
+ testInt = (Intersection*)
+ shortestRoad->road->GetDestinationIntersection();
+ }
+ rAssert( testInt == this );
+ }
+#endif
+
+#ifdef TOOLS
+// char baseMsg [1000];
+// char fullMsg [1100];
+
+ /*
+ // Every intersection should have at minimum 1 OUT road
+ if( mnRoadsOut <= 0 )
+ {
+ sprintf( fullMsg,
+ "You are doomed. Intersection at (%f,%f,%f)\n"
+ " does not have an out road.\n",
+ mLocation.x, mLocation.y, -1*mLocation.z );
+ rTuneAssertMsg( false, fullMsg );
+ }
+ */
+
+ /*
+ // Road segments coming in and going out of this intersection MUST have same values
+ // of y where they hit the intersection. If this is not so, it is due to BAD ROAD DATA.
+ // For the sake of traffic, the intersection must be FLAT (so Traffic only computes
+ // a spline in 2D rather than 3D).
+ //
+ // If the y values of any two segments do not match up, cars will "hop" when
+ // they transit through the intersection between these segments.
+ //
+ // Please notify Sheik to check the road data around nearby intersections.
+ //
+ sprintf( baseMsg,
+ "\nMismatching y-values at intersection (%f,%f,%f).\n"
+ " Check if y values are same for all IN & OUT road segments attached\n"
+ " to this intersection. Check hypergraph to see if the roadnodes leading\n"
+ " IN and OUT of this intersection contain all the proper roadsegments.\n"
+ " If you skip this, Traffic cars will \"hop\" when they transit through\n"
+ " the intersection between the road segments with mismatching y values.\n"
+ " Better to report error to me (Dusit) or Sheik.\n\n",
+ mLocation.x,
+ mLocation.y,
+ -1*mLocation.z );
+
+ float ep = 0.001f;
+ for( unsigned int m=0; m<mnRoadsIn; m++ )
+ {
+ // grab the last segment on the in road
+ RoadSegment* inSeg = mRoadListIn[m]->GetRoadSegment
+ ( mRoadListIn[m]->GetNumRoadSegments()-1 );
+ rTuneAssert( inSeg != NULL );
+
+ rmt::Vector p1, p2;
+ inSeg->GetCorner( 1, p1 );
+ inSeg->GetCorner( 2, p2 );
+
+ sprintf( fullMsg, "%s Offending road: IN \"%s\"\n",
+ baseMsg, mRoadListIn[m]->GetName() );
+ rTuneAssertMsg( rmt::Epsilon( p1.y, p2.y, ep ), fullMsg );
+
+ for( unsigned int n=0; n<mnRoadsOut; n++ )
+ {
+ // grab the first segment on the out road
+ RoadSegment* outSeg = mRoadListOut[n]->GetRoadSegment( 0 );
+ rTuneAssert( outSeg != NULL );
+
+ rmt::Vector q0, q3;
+ outSeg->GetCorner( 0, q0 );
+ outSeg->GetCorner( 3, q3 );
+
+ sprintf( fullMsg, "%s Offending roads: IN \"%s\", OUT \"%s\"\n",
+ baseMsg, mRoadListIn[m]->GetName(), mRoadListOut[n]->GetName() );
+ rTuneAssertMsg( rmt::Epsilon( p1.y, q0.y, ep ) &&
+ rmt::Epsilon( p1.y, q3.y, ep ), fullMsg );
+ }
+ }
+ */
+#endif
+}
+
+//==============================================================================
+// Intersection::GetType
+//==============================================================================
+// Description: Comment
+//
+// Parameters: ()
+//
+// Return: Intersection::Type
+//
+//==============================================================================
+Intersection::Type Intersection::GetType() const
+{
+ return mType;
+}
+
+
+//==============================================================================
+// Intersection::SetType
+//==============================================================================
+// Description: Comment
+//
+// Parameters: ( Type type )
+//
+// Return: void
+//
+//==============================================================================
+void Intersection::SetType( Type type )
+{
+ mType = type;
+ switch( mType )
+ {
+ case NO_STOP:
+ {
+ mpTrafficControl = NULL;
+ }
+ break;
+ case N_WAY:
+ {
+ mpTrafficControl = &mNWayControl;
+ }
+ break;
+ default:
+ {
+ mpTrafficControl = NULL;
+ }
+ break;
+ }
+}
+
+//=============================================================================
+// Intersection::IsPointInIntersection
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ( rmt::Vector& point )
+//
+// Return: bool
+//
+//=============================================================================
+bool Intersection::IsPointInIntersection( rmt::Vector& point ) const
+{
+ rmt::Vector vectorBetween;
+
+ vectorBetween.x = point.x - mLocation.x;
+ vectorBetween.y = 0.0f;
+ vectorBetween.z = point.z - mLocation.z;
+ vectorBetween.x *= vectorBetween.x;
+ vectorBetween.z *= vectorBetween.z;
+ vectorBetween.x += vectorBetween.z;
+
+ return ( vectorBetween.x <= rmt::Sqr( mfRadius ) );
+}
+
+
+void Intersection::FindGoodTrafficLane( const Road& road, unsigned int preferredLaneIndex, Lane*& outLane, unsigned int& outLaneIndex )
+{
+ Lane* lane = road.GetLane(preferredLaneIndex);
+ int numTrafficVehicles = 0;
+ if( lane != NULL )
+ {
+ numTrafficVehicles = lane->mTrafficVehicles.mUseSize;
+ rAssert( numTrafficVehicles >= 0 );
+
+ if( numTrafficVehicles < lane->GetDensity() )
+ {
+ outLane = lane;
+ outLaneIndex = preferredLaneIndex;
+ return;
+ }
+ }
+
+ // if can't use the preferred lane, gotta find the first lane that can support my vehicle...
+ for( unsigned int i=0; i<road.GetNumLanes(); i++ )
+ {
+ lane = road.GetLane(i);
+ rAssert( lane != NULL );
+
+ numTrafficVehicles = lane->mTrafficVehicles.mUseSize;
+ rAssert( numTrafficVehicles >= 0 );
+
+ if( numTrafficVehicles < lane->GetDensity() )
+ {
+ outLane = lane;
+ outLaneIndex = i;
+ return;
+ }
+ }
+
+ // finally, can't find any lane, return NULL...
+ outLane = NULL;
+ outLaneIndex = 0;
+ return;
+}
+
+
+void Intersection::GetLeftTurnForTraffic( const Road& inRoad,
+ unsigned int preferredLaneIndex,
+ Road*& outRoad,
+ Lane*& outLane,
+ unsigned int& outLaneIndex )
+{
+ outRoad = NULL;
+ outLane = NULL;
+ outLaneIndex = 0;
+
+ int index = FindRoadIn( &inRoad );
+ rAssert( index != -1 );
+ if( index == -1 )
+ {
+ return;
+ }
+
+ if( mnRoadsOut <= 0 )
+ {
+ return;
+ }
+
+ if( mnRoadsOut == 1 )
+ {
+ //No roads out. Or only a straight out.
+ rDebugString( "Intersection has only one OUT road!\n" );
+
+ outRoad = mRoadListOut[0];
+
+ // Pick an outLane & outLaneIndex
+ FindGoodTrafficLane( *outRoad, preferredLaneIndex, outLane, outLaneIndex );
+
+ if( outLane == NULL )
+ {
+ return;
+ }
+ }
+ else
+ {
+ // To find which turn will give a closest approximation to a "LEFT"
+ // turn, we turn our inDir by 90 degrees (to the left!) and
+ // iterate through the outDirs for one that's STRAIGHTEST along it.
+ //
+ rmt::Vector origInDir;
+ rmt::Vector inDir, outDir;
+
+ // Grab normal of trailing edge of the last segment of IN road (for comparison)
+ RoadSegment* segment;
+ unsigned int nSegments = inRoad.GetNumRoadSegments();
+ assert( nSegments > 0 );
+ segment = inRoad.GetRoadSegment( nSegments - 1 );
+
+ // TODO:
+ // Don't use Edge Normals, use Direction of Segment's LANE (but we'll have to
+ // pass in lane info)
+ segment->GetEdgeNormal( 2, origInDir );
+
+ // *** NOTE ***
+ // We rely on the assumption that the intersection is HORIZONTALLY FLAT
+ // Else, we'll have to project the In & Out vectors onto the plane of
+ // the intersection.
+ origInDir.y = 0.0f;
+ origInDir.Normalize(); // *** SQUARE ROOT! ***
+
+ // copy origInDir... we'll be modifying inDir to suit our needs
+ inDir = origInDir;
+ inDir.Scale(-1.0f);
+
+ // turn inDir CCW 90 degrees about y axis (the ideal left turn
+ // will be 180 angle from this vector)
+ rmt::Vector temp;
+ temp.Set( -1 * inDir.z, inDir.y, inDir.x );
+ inDir = temp;
+
+ float cosAlpha = 0.0f;
+
+ // Let bestCosAlpha be, initially, the WORST value possible
+ // cosAlpha of 1.0 = alphaBetwIn&OutRoads of 0 = 180 degree turn! BAD!
+ // As we iterate through the OUT roads, we want to find one with most
+ // alpha, or smallest cosAlpha
+ //
+ float bestCosAlpha = 1.0f;
+ bool stillLookingForFirstRoad = true;
+
+ outRoad = NULL;
+ outLane = NULL;
+ outLaneIndex = 0;
+
+ unsigned int i = 0;
+ for( i ; i<mnRoadsOut ; ++i )
+ {
+ // Grab normal of leading edge of the first segment of OUT road
+ segment = mRoadListOut[i]->GetRoadSegment(0);
+ segment->GetEdgeNormal(0, outDir);
+
+ // *** NOTE ***
+ // We rely on the assumption that the intersection is HORIZONTALLY FLAT
+ // Else, we'll have to project the In & Out vectors onto the plane of
+ // the intersection.
+ outDir.y = 0.0f;
+ outDir.Normalize(); // *** SQUARE ROOT! ***
+
+ // Skip this OUT road if it just goes back the way we came
+ // This prevents U-turn at an intersection when there are
+ // other roads to take, even if they don't turn the way
+ // we want. The decision is really up to traffic control or
+ // some other entity; for now, we hardcode it in the Intersection
+ if( outDir.Equals( origInDir * -1, 0.05f ) )
+ {
+ continue;
+ }
+
+ cosAlpha = inDir.Dot(outDir);
+
+ // *** NOTE ***
+ // If contention arises between a left and a right turn that
+ // both have bestCosAlpha, this inequality will favor the last
+ // best match.
+ if( stillLookingForFirstRoad || (cosAlpha <= bestCosAlpha) )
+ {
+ Lane* laneCandidate = NULL;
+ unsigned int laneIndexCandidate = 0;
+ FindGoodTrafficLane( *mRoadListOut[i], preferredLaneIndex, laneCandidate, laneIndexCandidate );
+
+ if( laneCandidate != NULL )
+ {
+ stillLookingForFirstRoad = false;
+ bestCosAlpha = cosAlpha;
+ outRoad = mRoadListOut[i];
+ outLane = laneCandidate;
+ outLaneIndex = laneIndexCandidate;
+ }
+ }
+ }// end of FOR LOOP
+
+ }// end of ELSE
+
+}
+
+
+
+void Intersection::GetStraightForTraffic( const Road& inRoad,
+ unsigned int preferredLaneIndex,
+ Road*& outRoad,
+ Lane*& outLane,
+ unsigned int& outLaneIndex )
+{
+ outRoad = NULL;
+ outLane = NULL;
+ outLaneIndex = 0;
+
+ int index = FindRoadIn( &inRoad );
+ rAssert( index != -1 );
+ if( index == -1 )
+ {
+ return;
+ }
+
+ if( mnRoadsOut <= 0 )
+ {
+ return;
+ }
+
+ if ( mnRoadsOut == 1 )
+ {
+ rDebugString( "Intersection has only one OUT road!\n" );
+
+ outRoad = mRoadListOut[0];
+
+ // Pick an outLane & outLaneIndex
+ FindGoodTrafficLane( *outRoad, preferredLaneIndex, outLane, outLaneIndex );
+
+ if( outLane == NULL )
+ {
+ return;
+ }
+ }
+ else
+ {
+ // Iterate through all the OUT roads to find which one gives us the angle closest to
+ // going STRAIGHT (180)
+ //
+ rmt::Vector origInDir;
+ rmt::Vector inDir, outDir;
+
+ // Grab normal of trailing edge of the last segment of IN road (for comparison)
+ RoadSegment* segment;
+ unsigned int nSegments = inRoad.GetNumRoadSegments();
+ assert( nSegments > 0 );
+ segment = inRoad.GetRoadSegment( nSegments - 1 );
+ segment->GetEdgeNormal( 2, origInDir );
+
+ // *** NOTE ***
+ // We rely on the assumption that the intersection is HORIZONTALLY FLAT
+ // Else, we'll have to project the In & Out vectors onto the plane of
+ // the intersection.
+ origInDir.y = 0.0f;
+ origInDir.Normalize(); // *** SQUARE ROOT! ***
+
+ inDir = origInDir;
+ inDir.Scale(-1.0f);
+
+ float cosAlpha = 0.0f;
+
+ // Let bestCosAlpha be, initially, the WORST value possible
+ // cosAlpha of 1.0 = alphaBetwIn&OutRoads of 0 = 180 degree turn! BAD!
+ // As we iterate through the OUT roads, we want to find one with most
+ // alpha, or smallest cosAlpha
+ //
+ float bestCosAlpha = 1.0f;
+ bool stillLookingForFirstRoad = true;
+
+ unsigned int i = 0;
+ for( i ; i<mnRoadsOut ; ++i )
+ {
+ // Grab normal of leading edge of the first segment of OUT road
+ segment = mRoadListOut[i]->GetRoadSegment(0);
+ segment->GetEdgeNormal(0, outDir);
+
+ // *** NOTE ***
+ // We rely on the assumption that the intersection is HORIZONTALLY FLAT
+ // Else, we'll have to project the In & Out vectors onto the plane of
+ // the intersection.
+ outDir.y = 0.0f;
+ outDir.Normalize(); // *** SQUARE ROOT! ***
+
+ // Skip this OUT road if it just goes back the way we came
+ // This prevents U-turn at an intersection when there are
+ // other roads to take, even if they don't turn the way
+ // we want. The decision is really up to traffic control or
+ // some other entity; for now, we hardcode it in the Intersection
+ if( outDir.Equals( origInDir * -1, 0.05f ) )
+ {
+ continue;
+ }
+
+ cosAlpha = inDir.Dot(outDir);
+
+ // *** NOTE ***
+ // This inequality will favor the last best match. (If another road
+ // has cosAlpha = current bestCosAlpha, we ignore it & go with the
+ // most recent one).
+ if( stillLookingForFirstRoad || (cosAlpha <= bestCosAlpha) )
+ {
+ Lane* laneCandidate = NULL;
+ unsigned int laneIndexCandidate = 0;
+ FindGoodTrafficLane( *mRoadListOut[i], preferredLaneIndex, laneCandidate, laneIndexCandidate );
+
+ if( laneCandidate != NULL )
+ {
+ stillLookingForFirstRoad = false;
+ bestCosAlpha = cosAlpha;
+ outRoad = mRoadListOut[i];
+ outLane = laneCandidate;
+ outLaneIndex = laneIndexCandidate;
+ }
+ }
+ }
+ }
+
+}
+
+// Given the current road, this should return a ref to the right turn road.
+void Intersection::GetRightTurnForTraffic( const Road& inRoad,
+ unsigned int preferredLaneIndex,
+ Road*& outRoad,
+ Lane*& outLane,
+ unsigned int& outLaneIndex )
+{
+ outRoad = NULL;
+ outLane = NULL;
+ outLaneIndex = 0;
+
+ int index = FindRoadIn( &inRoad );
+ rAssert( index != -1 );
+ if( index == -1 )
+ {
+ return;
+ }
+ if( mnRoadsOut <= 0 )
+ {
+ return;
+ }
+
+ if( mnRoadsOut == 1 )
+ {
+ //No roads out. Or only a straight out.
+ rDebugString( "Intersection has only one OUT road!\n" );
+
+ outRoad = mRoadListOut[0];
+
+ // Pick an outLane & outLaneIndex
+ FindGoodTrafficLane( *outRoad, preferredLaneIndex, outLane, outLaneIndex );
+
+ if( outLane == NULL )
+ {
+ return;
+ }
+ }
+ else
+ {
+ // To find which turn will give a closest approximation to a "LEFT"
+ // turn, we turn our inDir by 90 degrees (to the left!) and
+ // iterate through the outDirs for one that's STRAIGHTEST along it.
+ //
+ rmt::Vector origInDir;
+ rmt::Vector inDir, outDir;
+
+ // Grab normal of trailing edge of the last segment of IN road (for comparison)
+ RoadSegment* segment;
+ unsigned int nSegments = inRoad.GetNumRoadSegments();
+ assert( nSegments > 0 );
+ segment = inRoad.GetRoadSegment( nSegments - 1 );
+ segment->GetEdgeNormal( 2, origInDir );
+
+ // *** NOTE ***
+ // We rely on the assumption that the intersection is HORIZONTALLY FLAT
+ // Else, we'll have to project the In & Out vectors onto the plane of
+ // the intersection.
+ origInDir.y = 0.0f;
+ origInDir.Normalize(); // *** SQUARE ROOT! ***
+
+ // copy origInDir... we'll be modifying inDir to suit our needs
+ inDir = origInDir;
+ inDir.Scale(-1.0f);
+
+ // turn inDir CW 90 degrees about y axis (the ideal right turn
+ // is at 180 angle from this vector)
+ rmt::Vector temp;
+ temp.Set( inDir.z, inDir.y, -1 * inDir.x );
+ inDir = temp;
+
+ float cosAlpha = 0.0f;
+
+ // Let bestCosAlpha be, initially, the WORST value possible
+ // cosAlpha of 1.0 = alphaBetwIn&OutRoads of 0 = 180 degree turn! BAD!
+ // As we iterate through the OUT roads, we want to find one with most
+ // alpha, or smallest cosAlpha
+ //
+ float bestCosAlpha = 1.0f;
+ bool stillLookingForFirstRoad = true;
+
+ unsigned int i = 0;
+ for( i ; i<mnRoadsOut ; ++i )
+ {
+ // Grab normal of leading edge of the first segment of OUT road
+ segment = mRoadListOut[i]->GetRoadSegment(0);
+ segment->GetEdgeNormal(0, outDir);
+
+ // *** NOTE ***
+ // We rely on the assumption that the intersection is HORIZONTALLY FLAT
+ // Else, we'll have to project the In & Out vectors onto the plane of
+ // the intersection.
+ outDir.y = 0.0f;
+ outDir.Normalize(); // *** SQUARE ROOT! ***
+
+ // Skip this OUT road if it just goes back the way we came
+ // This prevents U-turn at an intersection when there are
+ // other roads to take, even if they don't turn the way
+ // we want. The decision is really up to traffic control or
+ // some other entity; for now, we hardcode it in the Intersection
+ if( outDir.Equals( origInDir * -1, 0.05f ) )
+ {
+ continue;
+ }
+
+ cosAlpha = inDir.Dot(outDir);
+
+ // *** NOTE ***
+ // If contention arises between a left and a right turn that
+ // both have bestCosAlpha, this inequality will favor the last
+ // best match.
+ if( stillLookingForFirstRoad || (cosAlpha <= bestCosAlpha) )
+ {
+ Lane* laneCandidate = NULL;
+ unsigned int laneIndexCandidate = 0;
+ FindGoodTrafficLane( *mRoadListOut[i], preferredLaneIndex, laneCandidate, laneIndexCandidate );
+
+ if( laneCandidate != NULL )
+ {
+ stillLookingForFirstRoad = false;
+ bestCosAlpha = cosAlpha;
+ outRoad = mRoadListOut[i];
+ outLane = laneCandidate;
+ outLaneIndex = laneIndexCandidate;
+ }
+ }
+ }
+ }
+}
+
+void Intersection::GetOtherIntersection
+(
+ bool useMultiplier,
+ Intersection* knownIntersection,
+ Intersection*& otherIntersection,
+ RoadManager::ShortestRoad*& road
+)
+{
+ rAssert( knownIntersection != NULL );
+
+ // works only for non-big intersections
+ if( mBigIntersection != NULL )
+ {
+ rAssert( false );
+ otherIntersection = NULL;
+ road = NULL;
+ return;
+ }
+
+ SwapArray<RoadManager::ShortestRoad>* array = useMultiplier ?
+ &mShortestRoadsToAdjacentIntersectionsWithMultiplier :
+ &mShortestRoadsToAdjacentIntersectionsNoMultiplier ;
+
+ // I'm a non-big intersection if I'm connected to either 1 or 2 other
+ // intersections
+ rAssert( 1 <= array->mUseSize && array->mUseSize <= 2 );
+
+ for( int i=0; i<array->mUseSize; i++ )
+ {
+ RoadManager::ShortestRoad* shortRoad = &((*array)[i]);
+ rAssert( shortRoad );
+
+ Intersection* otherIn = NULL;
+ if( shortRoad->isOutRoad )
+ {
+ otherIn = (Intersection*) shortRoad->road->GetDestinationIntersection();
+ }
+ else
+ {
+ otherIn = (Intersection*) shortRoad->road->GetSourceIntersection();
+ }
+ if( otherIn != knownIntersection )
+ {
+ road = shortRoad;
+ otherIntersection = otherIn;
+ return;
+ }
+ }
+}
diff --git a/game/code/roads/intersection.h b/game/code/roads/intersection.h
new file mode 100644
index 0000000..8dfc8d5
--- /dev/null
+++ b/game/code/roads/intersection.h
@@ -0,0 +1,312 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: Intersection
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2001/02/02 Tbrown-John Created
+
+===========================================================================*/
+
+#ifndef INTERSECTION_H_
+#define INTERSECTION_H_
+
+#include <radmath/radmath.hpp>
+#include <p3d/p3dtypes.hpp>
+#include <p3d/entity.hpp>
+#include <roads/TrafficControl.h>
+#include <roads/lane.h>
+#include <roads/geometry.h>
+#include <roads/roadmanager.h>
+#include <render/culling/swaparray.h>
+
+class Road;
+class CNavVertex;
+class TriggerLocator;
+class AnimEntityDSG;
+
+// somewhat arbitrary limit of MAX_ROADS way intersection.
+const int MAX_ROADS = 8;
+/*
+ AI is going to want to know these things about moving along a road:
+ 1. Am I at an intersection?
+ 2. What is my position and orientation?
+ 3. Do I want to change lanes?
+
+ AI is going to want to know these things when it is at an intersection:
+ 1. Can I move through this intersection.
+
+ AI is going to want to know these things about moving through intersection.
+ 1. Can I turn left from this lane?
+ 2. Can I turn right from this lane?
+ 3. Can I go straight in this lane?
+
+*/
+#ifdef TOOLS
+#define IS_ENTITY : public tEntity
+#else
+#define IS_ENTITY
+#endif
+
+class Intersection IS_ENTITY
+{
+public:
+ Intersection( );
+ Intersection( TriggerLocator* pLocator );
+ ~Intersection( void );
+
+ enum Type
+ {
+ NO_STOP,
+ N_WAY
+ };
+
+ Type GetType() const;
+ void SetType( Type type );
+ // Get the count of Roads into the intersection.
+ //unsigned int SizeRoadsIn( void ) const { return mnRoadsIn; }
+
+ // Get the count of Roads out of the intersection.
+ //unsigned int SizeRoadsOut( void ) const { return mnRoadsOut; }
+
+ // Get the count of Roads into and out of the intersection.
+ //unsigned int SizeRoads( void ) const { return mnRoadsIn + mnRoadsOut; }
+
+ // add a road to the in list.
+ void AddRoadIn( Road *pRoad );
+
+ // add a road to the out list.
+ void AddRoadOut( Road *pRoad );
+
+ void FindGoodTrafficLane( const Road& road,
+ unsigned int preferredLaneIndex,
+ Lane*& outLane,
+ unsigned int& outLaneIndex );
+
+ void GetLeftTurnForTraffic( const Road& inRoad,
+ unsigned int preferredLaneIndex,
+ Road*& outRoad,
+ Lane*& outLane,
+ unsigned int& outLaneIndex );
+
+ void GetRightTurnForTraffic( const Road& inRoad,
+ unsigned int preferredLaneIndex,
+ Road*& outRoad,
+ Lane*& outLane,
+ unsigned int& outLaneIndex );
+
+ void GetStraightForTraffic( const Road& inRoad,
+ unsigned int preferredLaneIndex,
+ Road*& outRoad,
+ Lane*& outLane,
+ unsigned int& outLaneIndex );
+
+ // So easy, it's almost free!
+ //
+ const Road* GetRoadIn( unsigned int index ) const;
+ const Road* GetRoadOut( unsigned int index ) const;
+ unsigned int GetNumRoadsIn() const;
+ unsigned int GetNumRoadsOut() const;
+
+ // Is the intersection clear of all cars.
+ //
+ bool IsIntersectionClear( void ) const;
+
+ // Simulate the intersection when there are cars nearby.
+ //
+ void Update( unsigned int dt );
+
+ // advance the traffic in roads 'RoadMask' according to light state.
+ //
+ void AdvanceTraffic( unsigned int RoadMask, unsigned int state ) const;
+
+ // returns the Intersection location in world space.
+ //
+ void GetLocation( rmt::Vector& location ) const;
+ void SetLocation( rmt::Vector& location );
+
+ // Temp method to display.
+ //
+ void Render( void ) const;
+
+ void SetRadius( float radius );
+ float GetRadius( void ) const
+ { return mfRadius; }
+
+ // Sorts the roads into clockwise order.
+ //
+ void SortRoads( void );
+
+ void SetName( const char* name );
+ tUID GetNameUID() const;
+
+ bool IsPointInIntersection( rmt::Vector& point ) const;
+
+ TrafficControl* GetTrafficControl();
+ void AdvanceNextWaitingRoad();
+
+ // Works only for non-big intersections
+ //
+ // Given an intersection connected to myself, I'll search through
+ // my list of shortest roads to other intersections to return the
+ // other intersection adjacent to me.
+ //
+ // The "useMultiplier" flag tells us to use the list of shortestroads
+ // whose "shortest" descriptive is defined using the road cost augmented
+ // by AGAINST_TRAFFIC_COST_MULTIPLIER
+ //
+ void GetOtherIntersection(
+ bool useMultiplier,
+ Intersection* knownIntersection,
+ Intersection*& otherIntersection,
+ RoadManager::ShortestRoad*& road );
+
+ void LinkAnimEntity( AnimEntityDSG* ipAnimEntity, int iIndex )
+ {
+ int i = iIndex - mpAnimEntityList.mUseSize + 1;
+ if(i>0) mpAnimEntityList.AddUse(i);
+
+ mpAnimEntityList[iIndex] = ipAnimEntity;
+ }
+
+ AnimEntityDSG* AnimEntity(int iIndex)
+ {
+ return mpAnimEntityList[iIndex];
+ }
+
+public:
+ SwapArray<Road*> mWaitingRoads; // list of roads waiting for a turn to go
+ SwapArray<Road*> mOutgoingShortcuts;
+ SwapArray<RoadManager::ShortestRoad> mShortestRoadsToAdjacentIntersectionsWithMultiplier;
+ SwapArray<RoadManager::ShortestRoad> mShortestRoadsToAdjacentIntersectionsNoMultiplier;
+ RoadManager::BigIntersection* mBigIntersection;
+ int mIndex; // index to RoadManager::mIntersections[pool==0] list
+
+private:
+ SwapArray<AnimEntityDSG*> mpAnimEntityList;
+ // methods
+ //
+
+ // Find the road pointer in the road list.
+ //
+ int FindRoadIn( const Road* pRoad ) const;
+
+ // Find the road pointer in the road list.
+ //
+ int FindRoadOut( const Road* pRoad ) const;
+
+ void PopulateShortestRoads( SwapArray<RoadManager::ShortestRoad>& roadsToAdjacentInts, bool useMultiplier );
+
+private: // data
+ // Roads are Clockwise ordered.
+ //
+ // 0
+ // |
+ // |
+ //3 ____|____ 1
+ // |
+ // |
+ // |
+ // 2
+ //
+ // a list of the roads leading in to this intersection.
+ //
+ Road* mRoadListIn[ MAX_ROADS ];
+
+ // a list of the roads leading out of this intersection.
+ //
+ Road* mRoadListOut[ MAX_ROADS ];
+
+ //
+ // A pointer to the traffic control object for this intersection.
+ // & the different controls this intersection might have
+ //
+ TrafficControl* mpTrafficControl;
+ TrafficLight mLightControl;
+ NWayStop mNWayControl;
+
+
+ // the actual number of roads in. <= MAX_ROADS.
+ //
+ unsigned int mnRoadsIn;
+
+ // the actual number of roads out. <= MAX_ROADS.
+ //
+ unsigned int mnRoadsOut;
+
+ // the location of the intersection in world space.
+ //
+ rmt::Vector mLocation;
+
+ // the rotation around the y vector of the intersection.
+ //
+ float mfRotation;
+
+ float mfRadius;
+
+ Type mType;
+
+ tUID mNameUID;
+};
+
+
+
+inline void Intersection::SetName( const char* name )
+{
+#ifdef TOOLS
+ tEntity::SetName( name );
+#endif
+ mNameUID = tEntity::MakeUID( name );
+}
+inline tUID Intersection::GetNameUID() const
+{
+ return mNameUID;
+}
+inline void Intersection::SetLocation( rmt::Vector& location )
+{
+ mLocation = location;
+}
+inline void Intersection::SetRadius( float radius )
+{
+ mfRadius = radius;
+}
+inline const Road* Intersection::GetRoadIn( unsigned int index ) const
+{
+ if(index >= mnRoadsIn)
+ {
+ return NULL;
+ }
+
+ return mRoadListIn[ index ];
+}
+inline const Road* Intersection::GetRoadOut( unsigned int index ) const
+{
+ if(index >= mnRoadsOut)
+ {
+ return NULL;
+ }
+
+ return mRoadListOut[ index ];
+}
+inline unsigned int Intersection::GetNumRoadsIn() const
+{
+ return mnRoadsIn;
+}
+inline unsigned int Intersection::GetNumRoadsOut() const
+{
+ return mnRoadsOut;
+}
+inline TrafficControl* Intersection::GetTrafficControl()
+{
+ return mpTrafficControl;
+}
+
+
+
+
+#endif \ No newline at end of file
diff --git a/game/code/roads/lane.cpp b/game/code/roads/lane.cpp
new file mode 100644
index 0000000..4615e5a
--- /dev/null
+++ b/game/code/roads/lane.cpp
@@ -0,0 +1,187 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: Lane
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2001/02/02 Tbrown-John Created
+
+===========================================================================*/
+
+#include <roads/lane.h>
+#include <roads/road.h>
+#include <roads/trafficcontrol.h>
+
+
+#ifndef TOOLS
+#include <memory/srrmemory.h>
+#else
+#define MEMTRACK_PUSH_GROUP(x)
+#define MEMTRACK_POP_GROUP()
+#endif
+
+#ifndef TOOLS
+#include <worldsim/redbrick/vehicle.h>
+#include <worldsim/redbrick/trafficlocomotion.h>
+#endif
+
+#include <raddebug.hpp>
+
+
+//=============================================================================
+// Lane::Lane
+//=============================================================================
+// Description: Constructor
+//
+// Parameters: None
+//
+//=============================================================================
+Lane::Lane() :
+#ifndef TOOLS
+ mWaitingVehicle( NULL ),
+#endif
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ mDesiredDensity( 5 ),
+ mPoints( NULL ),
+ mNumPoints( 0 )
+#else
+ mDesiredDensity( 5 )
+#endif
+{
+}
+
+Lane::~Lane()
+{
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ if ( mPoints )
+ {
+ delete[] mPoints;
+ mPoints = NULL;
+ }
+#endif
+ mTrafficVehicles.Clear();
+}
+
+void Lane::Create( int density, Road* parentRoad )
+{
+ // DUSIT [Oct21,2002]
+ // Took out this assert cuz we need to be able to set density to 0 to
+ // prevent traffic cars from going onto that lane. Why TBJ put this
+ // assert in there in the first place
+ //rAssertMsg( fDensity > 0.0f, "Desired Density must be greater than 0.0f" );
+
+ mDesiredDensity = density;
+ mpParentRoad = parentRoad;
+ if( density > 0 )
+ {
+ mTrafficVehicles.Allocate( density );
+ }
+}
+
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ void Lane::GetStart( rmt::Vector &point ) const
+ {
+ GetPoint( 0, &point );
+ }
+ void Lane::GetEnd( rmt::Vector &point ) const
+ {
+ GetPoint( GetNumPoints() - 1, &point );
+ }
+#endif
+
+
+
+// Notify waiting traffic that traffic control signal has changed.
+void Lane::NotifyWaitingTraffic( unsigned int state )
+{
+#ifndef TOOLS
+ if( TrafficControl::GREEN == state )
+ {
+ if( mWaitingVehicle != NULL )
+ {
+ Vehicle* v = mWaitingVehicle->GetVehicle();
+ rAssert( v != NULL );
+
+ // If the vehicle was removed from traffic, don't
+ // bother with notification. This can happen if
+ // player moves away from intersection.
+ // Also, if the vehicle is no longer in the intersection,
+ // we shouldn't just transit it back to DRIVING (it
+ // could be in any other state by now!)
+ if( mWaitingVehicle->GetIsActive() && v->mVehicleType == VT_TRAFFIC )
+ {
+ if( this == v->mTrafficLocomotion->GetAILane() &&
+ v->mTrafficLocomotion->GetAI()->GetState() ==
+ TrafficAI::WAITING_AT_INTERSECTION )
+ {
+ v->mTrafficLocomotion->SetAIState( TrafficAI::DRIVING );
+ }
+ }
+ mWaitingVehicle = NULL;
+ }
+ }
+ /*
+ if ( TrafficLight::ADVANCE_GREEN == state && CanTurnLeft() )
+ {
+ // Notify all waiting traffic.
+ //
+ }
+ else if ( TrafficLight::GREEN == state && !CanTurnLeft() )
+ {
+ // Notify all waiting traffic.
+ //
+ }
+ */
+#endif
+}
+
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+
+ void Lane::AllocatePoints( unsigned int numPoints )
+ {
+ MEMTRACK_PUSH_GROUP( "Lane" );
+ rAssert( mPoints == NULL );
+
+ //TODO: GET RID OF THIS.
+ #ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PushHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PushHeap( GMA_LEVEL_OTHER );
+ #endif
+ #endif
+ mPoints = new rmt::Vector[ numPoints ];
+ rAssert( mPoints );
+
+ mNumPoints = numPoints;
+
+ #ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PopHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PopHeap( GMA_LEVEL_OTHER );
+ #endif
+ #endif
+
+ MEMTRACK_POP_GROUP( "Lane" );
+ }
+
+ unsigned int Lane::GetNumPoints() const
+ {
+ return mNumPoints;
+ }
+
+ void Lane::SetPoint( unsigned int index, const rmt::Vector& point )
+ {
+ rAssert( index < mNumPoints );
+
+ mPoints[index] = point;
+ }
+
+#endif
+
diff --git a/game/code/roads/lane.h b/game/code/roads/lane.h
new file mode 100644
index 0000000..eb4fdd6
--- /dev/null
+++ b/game/code/roads/lane.h
@@ -0,0 +1,187 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: Lane
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2001/02/02 Tbrown-John Created
+
+===========================================================================*/
+
+#ifndef LANE_HPP_
+#define LANE_HPP_
+
+#include <radmath/radmath.hpp>
+#include <vector>
+#include <list>
+#include <roads/geometry.h>
+#include <render/culling/swaparray.h>
+#include <worldsim/traffic/trafficvehicle.h>
+
+class Road;
+class Lane;
+
+// the read only interface to the lane.
+struct ILaneInformation
+{
+ // get the max allowable speed.
+ virtual float GetSpeedLimit( void ) const = 0;
+ virtual int GetDensity( void ) const = 0;
+ // returns the parent road of this lane.
+ virtual const Road *GetRoad( void ) const = 0;
+
+#if defined(RAD_TUNE) || defined(RAD_DEBUG)
+ // For Rendering
+ // point is assigned the world position of the start of the lane
+ virtual void GetStart( rmt::Vector &point ) const = 0;
+ // point is assigned the world position of the end of the lane
+ virtual void GetEnd( rmt::Vector &point ) const = 0;
+ // given a parametric time, updates the 'point.' returns true if at the end of the lane.
+ virtual bool GetPoint( float t, rmt::Vector& point ) const = 0;
+#endif
+
+};
+
+// the write only interface to the lane.
+struct ILaneControl
+{
+ // set the max allowable speed.
+ virtual void SetSpeedLimit( float metrespersecond ) = 0;
+ // set the max allowable num traffic cars.
+ virtual void SetDensity( int numCars ) = 0;
+};
+
+class Lane
+:
+public ILaneInformation,
+public ILaneControl
+{
+public:
+
+ // ctor
+ Lane( void );
+ ~Lane();
+
+ // grab the spline associated with this lane.
+ void Create( int density, Road* parentRoad );
+
+
+ //////////////////////////////////////////////////
+ // Implementing ILaneInformation
+ //
+ float GetSpeedLimit( void ) const;
+ int GetDensity( void ) const;
+ const Road* GetRoad( void ) const;
+
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ // Rendering stuff
+ void GetStart( rmt::Vector &point ) const;
+ void GetEnd( rmt::Vector &point ) const;
+ bool GetPoint( float t, rmt::Vector& point ) const;
+ void GetPoint( unsigned int index, rmt::Vector* point ) const;
+#endif
+ //////////////////////////////////////////////////////
+
+ ///////////////////////////////////////////////////
+ // Implementing ILaneControl
+ //
+ void SetSpeedLimit( float metrespersecond );
+ void SetDensity( int numCars );
+ void NotifyWaitingTraffic( unsigned int state );
+ ////////////////////////////////////////////////////
+
+
+ // Temp method to display.
+ void Render( void );
+
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ void AllocatePoints( unsigned int numPoints );
+ unsigned int GetNumPoints( void ) const;
+ void SetPoint( unsigned int index, const rmt::Vector& point );
+#endif
+
+public:
+ // the vehicle at the front of all lane's traffic, waiting at the intersection.
+ TrafficVehicle* mWaitingVehicle;
+
+ // Add traffic to the lane's internal list to keep track of how many have been
+ // added to the lane (to conform to the lane's desired density).
+ SwapArray<TrafficVehicle*> mTrafficVehicles;
+
+
+private:
+ const Road *mpParentRoad; // the road that owns this lane.
+ float mfSpeedLimit; // the maximum allowable speed for this lane.
+ int mDesiredDensity; // the desired density ( in total cars )
+
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ // Rendering stuff
+ rmt::Vector* mPoints;
+ unsigned int mNumPoints;
+#endif
+
+};
+
+//*****************************************************************************
+//
+// Inline Public Member Functions
+//
+//*****************************************************************************
+
+//=============================================================================
+// Lane::SetSpeedLimit
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ( float metrespersecond )
+//
+// Return: void
+//
+//=============================================================================
+inline void Lane::SetSpeedLimit( float metrespersecond )
+{
+ mfSpeedLimit = metrespersecond;
+}
+
+
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ inline bool Lane::GetPoint( float t, rmt::Vector& point ) const
+ {
+ //t will equal what segment 0 - mpParentRoad->GetNumRoadSegments()
+ // *plus* 0-0.999999... for it's position in the road.
+ return false;
+ }
+
+ inline void Lane::GetPoint( unsigned int index, rmt::Vector* point ) const
+ {
+ rAssert( index < mNumPoints );
+ *point = mPoints[index];
+ }
+#endif
+
+
+
+inline const Road* Lane::GetRoad( void ) const
+{
+ return mpParentRoad;
+}
+inline float Lane::GetSpeedLimit() const
+{
+ return mfSpeedLimit;
+}
+inline void Lane::SetDensity( int numCars )
+{
+ mDesiredDensity = numCars;
+}
+inline int Lane::GetDensity() const
+{
+ return mDesiredDensity;
+}
+
+
+#endif \ No newline at end of file
diff --git a/game/code/roads/road.cpp b/game/code/roads/road.cpp
new file mode 100644
index 0000000..542fc82
--- /dev/null
+++ b/game/code/roads/road.cpp
@@ -0,0 +1,830 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: Road
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2001/02/02 Tbrown-John Created
+
+===========================================================================*/
+
+#include <roads/road.h>
+#include <roads/roadsegment.h>
+#include <roads/lane.h>
+#include <roads/geometry.h>
+#include <raddebug.hpp>
+
+#ifndef TOOLS
+#include <memory/srrmemory.h>
+#else
+#define MEMTRACK_PUSH_GROUP(x)
+#define MEMTRACK_POP_GROUP()
+#endif
+
+/*
+==============================================================================
+Road::Road
+==============================================================================
+Description: Comment
+
+Parameters: ( void )
+
+Return: na
+
+=============================================================================
+*/
+Road::Road( void )
+:
+mpSourceIntersection( 0 ),
+mpDestinationIntersection( 0 ),
+mLaneList( 0 ),
+mnLanes( 0 ),
+mppRoadSegmentArray( 0 ),
+mnMaxRoadSegments( 0 ),
+mnRoadSegments( 0 ),
+mSpeed( 0 ),
+mDensity( 0 ),
+mDifficulty( 0 ),
+mIsShortCut( false )
+{
+}
+
+/*
+==============================================================================
+Road::~Road
+==============================================================================
+Description: Comment
+
+Parameters: ( void )
+
+Return: na
+
+=============================================================================
+*/
+Road::~Road( void )
+{
+ if ( mLaneList )
+ {
+ delete [] mLaneList;
+ mLaneList = 0;
+ }
+
+ if ( mppRoadSegmentArray )
+ {
+ delete[] mppRoadSegmentArray;
+ mppRoadSegmentArray = NULL;
+ }
+}
+
+/*
+==============================================================================
+Road::AllocateSegments
+==============================================================================
+Description: Comment
+
+Parameters: ( unsigned int numSegments )
+
+Return: void
+
+=============================================================================
+*/
+void Road::AllocateSegments( unsigned int numSegments )
+{
+MEMTRACK_PUSH_GROUP( "Road" );
+#ifndef TOOLS
+#ifdef RAD_GAMECUBE
+ HeapMgr()->PushHeap( GMA_GC_VMM );
+#else
+ HeapMgr()->PushHeap( GMA_LEVEL_OTHER );
+#endif
+#endif
+
+ rAssert( numSegments > 0 );
+ rAssert( 0 == mppRoadSegmentArray );
+ rAssert( 0 == mnRoadSegments );
+
+ mnMaxRoadSegments = numSegments;
+ mppRoadSegmentArray = new RoadSegment*[ mnMaxRoadSegments ];
+
+ unsigned int i = 0;
+ for ( i = 0; i < mnMaxRoadSegments; i++ )
+ {
+ mppRoadSegmentArray[ i ] = 0;
+ }
+
+#ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PopHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PopHeap( GMA_LEVEL_OTHER );
+ #endif
+#endif
+MEMTRACK_POP_GROUP( "Road" );
+}
+
+/*
+==============================================================================
+Road::AddRoadSegment
+==============================================================================
+Description: Add a road segment.
+
+Parameters: ( RoadSegment* pRoadSegment )
+
+Return: void
+
+=============================================================================
+*/
+void Road::AddRoadSegment( RoadSegment* pRoadSegment )
+{
+ mppRoadSegmentArray[ mnRoadSegments ] = pRoadSegment;
+
+ pRoadSegment->SetSegmentIndex( mnRoadSegments );
+
+ mnRoadSegments++;
+
+ unsigned int numVertices = 4;
+ rmt::Vector vertex;
+ unsigned int i = 0;
+ for ( i = 0; i < numVertices; i++ )
+ {
+ pRoadSegment->GetCorner( i, vertex );
+ if ( 1 == mnRoadSegments && 0 == i )
+ {
+ // This is the first time.
+ // Initialize to some value.
+ //
+ mBox.low = mBox.high = vertex;
+ }
+ else
+ {
+ if ( mBox.low.x > vertex.x )
+ {
+ mBox.low.x = vertex.x;
+ }
+ if ( mBox.low.y > vertex.y )
+ {
+ mBox.low.y = vertex.y;
+ }
+ if ( mBox.low.z > vertex.z )
+ {
+ mBox.low.z = vertex.z;
+ }
+
+ if ( mBox.high.x < vertex.x )
+ {
+ mBox.high.x = vertex.x;
+ }
+ if ( mBox.high.y < vertex.y )
+ {
+ mBox.high.y = vertex.y;
+ }
+ if ( mBox.high.z < vertex.z )
+ {
+ mBox.high.z = vertex.z;
+ }
+ }
+ }
+ // now we should have a bounding box.
+ //
+ // compute the bounding sphere.
+ //
+ // first the centre.
+ //
+ rmt::Vector vectorBetween;
+ vectorBetween.Sub( mBox.high, mBox.low );
+ vectorBetween.Scale( 0.5f );
+ mSphere.centre.Add( mBox.low, vectorBetween );
+ // Then the radius
+
+ mSphere.radius = vectorBetween.Magnitude( );
+}
+
+/*
+==============================================================================
+Road::CreateLanes
+==============================================================================
+Description: Comment
+
+Parameters: ( void )
+
+Return: void
+
+=============================================================================
+*/
+void Road::CreateLanes( void )
+{
+MEMTRACK_PUSH_GROUP( "Road" );
+ // Allocate the lanes.
+ //
+ //TODO: REMOVE!
+ #ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PushHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PushHeap( GMA_LEVEL_OTHER );
+ #endif
+ #endif
+
+ mLaneList = new Lane[ mnLanes ];
+
+ // Allocate the memory for the lane points.
+ //
+ unsigned int totalDensity = GetDensity();
+ unsigned int laneDensity = totalDensity / mnLanes;
+
+ unsigned int i = 0;
+ for ( i = 0; i < mnLanes; i++ )
+ {
+ // Do this first.
+ //
+ // if on last lane, just add whatever's left of totalDensity
+ unsigned int density = 0;
+ if( i == mnLanes - 1 )
+ {
+ density = totalDensity;
+ }
+ else
+ {
+ density = laneDensity;
+ }
+ mLaneList[ i ].Create( (int)density, this );
+ totalDensity -= laneDensity;
+ mLaneList[ i ].SetSpeedLimit( (float)GetSpeed() * KPH_2_MPS ); //convert from kph to mps
+
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ // For each lane, allocate enough points to store all the roadSegment data plus one.
+ mLaneList[ i ].AllocatePoints( this->GetNumRoadSegments( ) + 1 );
+#endif
+
+ }
+ // Iterate through the segments.
+ //
+ for ( i = 0; i < mnRoadSegments; i++ )
+ {
+ RoadSegment* pSeg = mppRoadSegmentArray[ i ];
+ unsigned int j = 0;
+ for ( j = 0; j < mnLanes; j++ )
+ {
+ // For each lane in each segment, add a point to the lane.
+ //
+ rmt::Vector start, facing;
+ pSeg->GetLaneLocation( 0.0f, j, start, facing );
+
+ #if defined(RAD_TUNE) || defined(RAD_DEBUG)
+ mLaneList[ j ].SetPoint( i, start );
+ #endif
+ }
+ }
+ // This is attached to the out intersection.
+ //
+ RoadSegment* pSeg = mppRoadSegmentArray[ mnRoadSegments - 1 ];
+ // Now add the last point.
+ //
+ for ( i = 0; i < mnLanes; i++ )
+ {
+ rmt::Vector end, facing;
+ pSeg->GetLaneLocation( 1.0f, i, end, facing );
+ #if defined(RAD_TUNE) || defined(RAD_DEBUG)
+ mLaneList[ i ].SetPoint( mnRoadSegments, end );
+ #endif
+ }
+
+ //TODO: REMOVE!
+ #ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PopHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PopHeap( GMA_LEVEL_OTHER );
+ #endif
+ #endif
+
+MEMTRACK_POP_GROUP( "Road" );
+}
+
+/*
+==============================================================================
+Road::GetLane
+==============================================================================
+Description: Comment
+
+Parameters: ( unsigned int LaneId )
+
+Return: Lane*
+
+=============================================================================
+*/
+Lane* Road::GetLane( unsigned int LaneId ) const
+{
+ if ( LaneId < mnLanes )
+ {
+ return &mLaneList[ LaneId ];
+ }
+ else
+ {
+ return 0;
+ }
+}
+RoadSegment* Road::GetRoadSegment( unsigned int index ) const
+{
+ rAssert( index < mnRoadSegments );
+
+ return mppRoadSegmentArray[ index ];
+}
+
+//
+//
+/*
+==============================================================================
+Road::GetDestinationIntersectionJoinPoint
+==============================================================================
+Description: Return the point where the road attaches to the incoming intersection.
+
+Parameters: ( rmt::Vector& out )
+
+Return: void
+
+=============================================================================
+*/
+void Road::GetDestinationIntersectionJoinPoint( rmt::Vector& out )
+{
+ RoadSegment* pRoadSegment = this->GetRoadSegment( 0 );
+
+ pRoadSegment->GetCorner( 0, out );
+}
+/*
+==============================================================================
+Road::GetSourceIntersectionJoinPoint
+==============================================================================
+Description: Return the point where the road attaches to the outgoing intersection.
+
+Parameters: ( rmt::Vector& out )
+
+Return: void
+
+=============================================================================
+*/
+void Road::GetSourceIntersectionJoinPoint( rmt::Vector& out )
+{
+ RoadSegment* pRoadSegment = this->GetRoadSegment( this->GetNumRoadSegments( ) - 1 );
+
+ pRoadSegment->GetCorner( 1, out );
+}
+
+/*
+==============================================================================
+Road::GetRoadSegmentAtPoint
+==============================================================================
+Description: returns a road segment, if the point is inside a segment on this road.
+
+Parameters: ( const rmt::Vector& point, RoadSegment& outRoadSegment, int hint )
+
+Return: int - index of road segment this point is in.
+
+=============================================================================
+*/
+int Road::GetRoadSegmentAtPoint( const rmt::Vector& point, RoadSegment** ppOutRoadSegment, float& in, float& lateral, int hint ) const
+{
+ rmt::Vector vectorBetween;
+ // Do the 2D Math Explicitly.
+ // My profile test show it is significantly faster.
+ //
+ vectorBetween.x = point.x - mSphere.centre.x;
+ vectorBetween.y = 0.0f;
+ vectorBetween.z = point.z - mSphere.centre.z;
+ vectorBetween.x *= vectorBetween.x;
+ vectorBetween.z *= vectorBetween.z;
+ vectorBetween.x += vectorBetween.z;
+
+ if ( vectorBetween.x <= rmt::Sqr( mSphere.radius ) )
+ {
+ // Now test against AABB.
+ //
+ if ( point.x <= mBox.high.x
+ && point.x >= mBox.low.x
+ && point.z <= mBox.high.z
+ && point.z >= mBox.low.z )
+ {
+ int i = hint;
+ // Check the hint.
+ //
+ if ( !IsPointInRoadSegment( i, point, in, lateral ) )
+ {
+ // Check the one ahead.
+ //
+ if ( !IsPointInRoadSegment( ++i, point, in, lateral ) )
+ {
+ // Check the one behind.
+ //
+ if ( !IsPointInRoadSegment( i -= 2, point, in, lateral ) )
+ {
+ // Scan the entire list.
+ //
+ for ( i = 0; i < static_cast< int >( GetNumRoadSegments( ) ); i++ )
+ {
+ // Skip the ones we've looked at.
+ //
+ if ( i != hint && i != hint + 1 && i != hint - 1 )
+ {
+ // Stop when we find one.
+ //
+ if ( IsPointInRoadSegment( i, point, in, lateral ) )
+ {
+ break;
+ }
+ }
+ }
+ }
+ }
+ }
+ if ( i < static_cast< int >( GetNumRoadSegments( ) ) )
+ {
+ // We found one.
+ //
+ *ppOutRoadSegment = GetRoadSegment( i );
+ return i;
+ }
+ }
+ }
+ *ppOutRoadSegment = 0;
+ return -1;
+}
+
+/*
+==============================================================================
+Road::IsPointInRoadSegment
+==============================================================================
+Description: Tests the distance into and the lateral distance in a segment
+ if both lateral and in distance are between 0.0f - 1.0f
+ we return true.
+
+ Quick and Dirty performance number:
+ XBox 02/28/2002
+ 26.0 ms per 10000 calls point inside BBox
+ 1.0 ms per 10000 calls test BBox only.
+
+ 0.0025 / 10000
+
+ XBox 0.0025 ms in Debug for one call to IsPointInRoadSegment
+
+Parameters: ( int index )
+
+Return: bool - true if point is in road segment.
+
+=============================================================================
+*/
+bool Road::IsPointInRoadSegment( int index, const rmt::Vector& point, float& in, float& lateral ) const
+{
+ if ( index >= 0 && index < static_cast<int>( GetNumRoadSegments() ) )
+ {
+ RoadSegment* pRoadSegment = GetRoadSegment( index );
+ rmt::Vector vectorBetween;
+ rmt::Sphere sphere;
+ pRoadSegment->GetBoundingSphere( &sphere );
+
+ // Do the 2D Math Explicitly.
+ // My profile test show it is significantly faster.
+ //
+ vectorBetween.x = point.x - sphere.centre.x;
+ vectorBetween.y = 0.0f;
+ vectorBetween.z = point.z - sphere.centre.z;
+ vectorBetween.x *= vectorBetween.x;
+ vectorBetween.z *= vectorBetween.z;
+ vectorBetween.x += vectorBetween.z;
+
+ if ( vectorBetween.x <= rmt::Sqr( sphere.radius ) )
+ {
+ in = pRoadSegment->CalculateUnitDistIntoRoadSegment( point.x, point.z );
+ if ( in >= 0.0f && in <= 1.0f )
+ {
+ lateral = pRoadSegment->CalculateUnitHeightInRoadSegment( point.x, point.z );
+ if ( lateral >= 0.0f && lateral <= 1.0f )
+ {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+}
+
+
+//=============================================================================
+// RoadManager::FindRoadSegmentAhead
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ( const Road* pRoad,
+// float& dist,
+// const float maxDist,
+// RoadSegment** segment )
+//
+// Return: bool
+//
+//=============================================================================
+bool Road::FindSegmentAhead( float& dist,
+ const float maxDist,
+ const int currentIndex,
+ RoadSegment** segment ) const
+{
+ rmt::Vector backleft;
+ rmt::Vector frontleft;
+ rmt::Vector frontright;
+ rmt::Vector backright;
+ rmt::Vector leftdir;
+ rmt::Vector rightdir;
+ rmt::Vector direction;
+ rmt::Vector destination;
+
+ rmt::Vector currentPos;
+
+ RoadSegment* pCurrentSegment = GetRoadSegment( currentIndex );
+
+ //
+ // Temporarily use pCurrentSegment to get data about where
+ // we're starting
+ //
+
+ pCurrentSegment->GetCorner( 0, backleft );
+ pCurrentSegment->GetCorner( 1, frontleft );
+ pCurrentSegment->GetCorner( 2, frontright );
+ pCurrentSegment->GetCorner( 3, backright );
+
+ //
+ // Find the front midpoint of the segment
+ //
+ currentPos.Add( frontleft, frontright );
+ currentPos.Scale( 0.5f, 0.5f, 0.5f );
+
+ //
+ // Find the average direction of the segment
+ //
+
+ leftdir.Sub( frontleft, backleft );
+ leftdir.Normalize();
+ rightdir.Sub( frontright, backright );
+ rightdir.Normalize();
+
+ //
+ // Take the average and scale by 0.1
+ //
+ direction.Add( leftdir, rightdir );
+ direction.Scale( 0.05f, 0.05f, 0.05f );
+
+ //
+ // This should put us within the next segment
+ //
+ currentPos.Add( direction );
+
+ RoadSegment* pNextSegment = NULL;
+ pCurrentSegment = NULL;
+
+ //float in, lateral = 0.0f;
+ int segmentIndex = currentIndex;
+
+ float currentDist = dist;
+ while( currentDist < maxDist )
+ {
+ //
+ // This search is not optimal
+ //
+ //segmentIndex = pRoad->GetRoadSegmentAtPoint( currentPos,
+ // &pNextSegment, in, lateral, segmentIndex + 1 );
+
+ //
+ // Much faster when the segments are sorted. Yay!
+ //
+ segmentIndex += 1;
+
+ if( segmentIndex >= static_cast<int>( GetNumRoadSegments() ) )
+ {
+ //
+ // Get as close as we can to the desired distance.
+ // Returns NULL if we didn't find anything at all.
+ //
+ (*segment) = pCurrentSegment;
+ dist = currentDist;
+ return false;
+ }
+
+ pNextSegment = GetRoadSegment( segmentIndex );
+ rAssert( pNextSegment != NULL );
+
+ //
+ // Find the midpoint of the front edge
+ //
+ pNextSegment->GetCorner( 1, frontleft );
+ pNextSegment->GetCorner( 2, frontright );
+
+ destination.Add( frontleft, frontright );
+ destination.Scale( 0.5f, 0.5f, 0.5f );
+
+ //
+ // Gives a vector along the centre line assuming currentPos
+ // is on the front edge midpoint of the previous segment
+ //
+ direction.Sub( destination, currentPos );
+
+ float segLength = direction.Magnitude();
+ currentDist += segLength;
+
+ //
+ // Normalize the direction and scale it by 0.1
+ //
+ // not necessary for the fast method
+ //float invLen = 0.1f / segLength;
+ //direction.Scale( invLen, invLen, invLen );
+
+ //currentPos.Add( destination, direction );
+
+ pCurrentSegment = pNextSegment;
+
+ }
+
+ //
+ // Got to the distance the person wanted
+ //
+ (*segment) = pCurrentSegment;
+ dist = currentDist;
+ return true;
+}
+
+//=============================================================================
+// RoadManager::FindSegmentBehind
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ( const Road* pRoad,
+// float& dist,
+// const float maxDist,
+// RoadSegment** segment )
+//
+// Return: bool
+//
+//=============================================================================
+bool Road::FindSegmentBehind( float& dist,
+ const float maxDist,
+ const int currentIndex,
+ RoadSegment** segment ) const
+{
+ rmt::Vector backleft;
+ rmt::Vector frontleft;
+ rmt::Vector frontright;
+ rmt::Vector backright;
+ rmt::Vector leftdir;
+ rmt::Vector rightdir;
+ rmt::Vector direction;
+ rmt::Vector destination;
+
+ rmt::Vector currentPos;
+
+ RoadSegment* pCurrentSegment = GetRoadSegment( currentIndex );
+
+ //
+ // Temporarily use pCurrentSegment to get data about where
+ // we're starting
+ //
+
+ pCurrentSegment->GetCorner( 0, backleft );
+ pCurrentSegment->GetCorner( 1, frontleft );
+ pCurrentSegment->GetCorner( 2, frontright );
+ pCurrentSegment->GetCorner( 3, backright );
+
+ //
+ // Find the rear midpoint of the segment
+ //
+ currentPos.Add( backleft, backright );
+ currentPos.Scale( 0.5f, 0.5f, 0.5f );
+
+ //
+ // Find the average direction of the segment
+ //
+
+ leftdir.Sub( backleft, frontleft );
+ leftdir.Normalize();
+ rightdir.Sub( backright, frontright );
+ rightdir.Normalize();
+
+ //
+ // Take the average and scale by 0.1
+ //
+ direction.Add( leftdir, rightdir );
+ direction.Scale( 0.05f, 0.05f, 0.05f );
+
+ //
+ // This should put us within the next segment
+ //
+ currentPos.Add( direction );
+
+ RoadSegment* pNextSegment = NULL;
+ //float in, lateral = 0.0f;
+ int segmentIndex = currentIndex;
+
+ float currentDist = dist;
+ while( currentDist < maxDist )
+ {
+ pCurrentSegment = pNextSegment;
+
+ //
+ // This search is not optimal
+ //
+ //segmentIndex = pRoad->GetRoadSegmentAtPoint( currentPos,
+ // &pNextSegment, in, lateral, segmentIndex + 1 );
+
+ //
+ // Much faster when the segments are sorted. Yay!
+ //
+ segmentIndex -= 1;
+
+ if( segmentIndex < 0 )
+ {
+ //
+ // Get as close as we can to the desired distance.
+ // Returns NULL if we didn't find anything at all.
+ //
+ (*segment) = pCurrentSegment;
+ dist = currentDist;
+ return false;
+ }
+
+ pNextSegment = GetRoadSegment( segmentIndex );
+ rAssert( pNextSegment != NULL );
+
+ //
+ // Find the midpoint of the front edge
+ //
+ pNextSegment->GetCorner( 0, backleft );
+ pNextSegment->GetCorner( 3, backright );
+
+ destination.Add( backleft, backright );
+ destination.Scale( 0.5f, 0.5f, 0.5f );
+
+ //
+ // Gives a vector along the centre line assuming currentPos
+ // is on the front edge midpoint of the previous segment
+ //
+ direction.Sub( destination, currentPos );
+
+ float segLength = direction.Magnitude();
+ currentDist += segLength;
+
+ //
+ // Normalize the direction and scale it by 0.1
+ //
+ // not necessary for the fast method
+ //float invLen = 0.1f / segLength;
+ //direction.Scale( invLen, invLen, invLen );
+
+ //currentPos.Add( destination, direction );
+ }
+
+ //
+ // Got to the distance the person wanted
+ //
+ (*segment) = pCurrentSegment;
+ dist = currentDist;
+ return true;
+}
+
+
+//=============================================================================
+// Road::SetDensity
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ( unsigned int density )
+//
+// Return: void
+//
+//=============================================================================
+void Road::SetDensity( unsigned int density )
+{
+ mDensity = density;
+}
+
+//////////////////////////////////////////////////////////////////////////
+//////////////////////////////////////////////////////////////////////////
+void Road::FindRoadSegmentAtDist( float iDist, RoadSegment** oppRoadSegment )
+{
+ if(iDist>GetRoadLength())
+ {
+ *oppRoadSegment = NULL;
+ return;
+ }
+
+ RoadSegment* pRoadSegment = NULL;
+
+ float distAccum = 0.0f;
+ for(int i=mnRoadSegments-1; i>-1 && distAccum<iDist; i--)
+ {
+ pRoadSegment = mppRoadSegmentArray[i];
+ distAccum += pRoadSegment->GetSegmentLength();
+ }
+
+ *oppRoadSegment = pRoadSegment;
+}
+
diff --git a/game/code/roads/road.h b/game/code/roads/road.h
new file mode 100644
index 0000000..2d20e3e
--- /dev/null
+++ b/game/code/roads/road.h
@@ -0,0 +1,249 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: Road
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2001/02/02 Tbrown-John Created
+
+===========================================================================*/
+#ifndef ROAD_HPP_
+#define ROAD_HPP_
+
+#include <radmath/radmath.hpp>
+#include <p3d/p3dtypes.hpp>
+#include <string.h>
+
+#ifdef TOOLS
+#include <p3d/entity.hpp>
+#endif
+
+// forward declarations
+class Intersection;
+class Lane;
+class RoadSegment;
+
+// 3 lanes in one direction maximum.
+const unsigned int MAX_LANES = 3;
+
+
+#ifdef TOOLS
+#define IS_ENTITY : public tEntity
+#else
+#define IS_ENTITY
+#endif
+
+class Road IS_ENTITY
+{
+public: // methods
+
+ Road( void );
+ ~Road( void );
+
+ void SetNumLanes( int count );
+ unsigned int GetNumLanes( void ) const;
+
+ // Allocate memory for numSegments roadSegments.
+ //
+ void AllocateSegments( unsigned int numSegments );
+
+ // Return Lane at position 'laneId'. return NULL if lane doesn't exist.
+ //
+ Lane *GetLane( unsigned int laneId ) const;
+
+ // Add a road segment.
+ //
+ void AddRoadSegment( RoadSegment* pRoadSegment );
+
+ // Creates lanes based on RoadSegment list.
+ //
+ void CreateLanes( void );
+
+ // return the intersection at the beginning of this road.
+ //
+ const Intersection *GetSourceIntersection( void ) const
+ { return mpSourceIntersection; }
+
+ // return the intersection at the end of this road.
+ //
+ const Intersection *GetDestinationIntersection( void ) const
+ { return mpDestinationIntersection; }
+
+ // set the intersection at the beginning of this road.
+ //
+ void SetSourceIntersection( Intersection *pIntersection )
+ { mpSourceIntersection = pIntersection; }
+
+ // set the intersection at the end of this road.
+ //
+ void SetDestinationIntersection( Intersection *pIntersection )
+ { mpDestinationIntersection = pIntersection; }
+
+ // Return the point where the road attaches to the incoming intersection.
+ //
+ void GetSourceIntersectionJoinPoint( rmt::Vector& out );
+
+ // Return the point where the road attaches to the outgoing intersection.
+ //
+ void GetDestinationIntersectionJoinPoint( rmt::Vector& out );
+
+ unsigned int GetNumRoadSegments( void ) const
+ { return mnRoadSegments; }
+
+ unsigned int GetMaxRoadSegments( void ) const
+ { return mnMaxRoadSegments; }
+
+ RoadSegment* GetRoadSegment( unsigned int index ) const;
+
+ int GetRoadSegmentAtPoint( const rmt::Vector& point, RoadSegment** ppOutRoadSegment, float& in, float& lateral, int hint ) const;
+
+ bool IsPointInRoadSegment( int index, const rmt::Vector& point, float& in, float& lateral ) const;
+
+ void Render( const tColour& colour );
+
+ void SetSpeed( unsigned int speed );
+ unsigned int GetSpeed() const;
+
+ void SetDifficulty( unsigned int diff );
+ unsigned int GetDifficulty() const;
+
+ void SetShortCut( bool is );
+ bool GetShortCut() const;
+
+ void SetDensity( unsigned int density );
+ unsigned int GetDensity() const;
+
+ void FindRoadSegmentAtDist( float iDist, RoadSegment** ippRoadSegment );
+ //---------------Helpful methods
+ // returns true if got to maxdist on the current road
+ // false if got to the end of the road first
+ bool FindSegmentAhead( float& dist,
+ const float maxDist,
+ const int currentIndex,
+ RoadSegment** segment ) const;
+ bool FindSegmentBehind( float& dist,
+ const float maxDist,
+ const int currentIndex,
+ RoadSegment** segment ) const;
+
+#if !defined( RAD_RELEASE ) && !defined( TOOLS )
+ void SetName( const char* name ) { strcpy( mName, name ); };
+ const char* GetName() { return mName; }
+#endif
+
+ const rmt::Sphere& GetBoundingSphere() const { return mSphere; };
+
+ float GetRoadLength();
+ void SetRoadLength( float len );
+
+private: // data
+ // Intersection at the start of the road.
+ //
+ const Intersection *mpSourceIntersection;
+
+ // Intersection at the end of the road.
+ //
+ const Intersection *mpDestinationIntersection;
+
+ // List of Lanes in a left to right order.
+ //
+ Lane *mLaneList;
+
+ // how many lanes on this road.
+ //
+ unsigned int mnLanes;
+
+ // The pointer to the head of the RoadSegment Array.
+ //
+ RoadSegment** mppRoadSegmentArray;
+
+ // How many have we allocated.
+ //
+ unsigned int mnMaxRoadSegments;
+
+ // A count of road segments.
+ //
+ unsigned int mnRoadSegments;
+
+ /////////////////////////
+ // TODO: Get rid of this
+ // A bounding box in world space for the road.
+ //
+ rmt::Box3D mBox;
+
+ // A bounding sphere in world space for the road.
+ //
+ rmt::Sphere mSphere;
+
+ unsigned int mSpeed;
+ unsigned int mDensity;
+ unsigned int mDifficulty;
+ bool mIsShortCut;
+
+#ifndef RAD_RELEASE
+ char mName[256];
+#endif
+
+ float mLength;
+};
+
+
+
+inline void Road::SetSpeed( unsigned int speed )
+{
+ mSpeed = speed;
+}
+inline unsigned int Road::GetSpeed() const
+{
+ return mSpeed;
+}
+inline void Road::SetDifficulty( unsigned int diff )
+{
+ mDifficulty = diff;
+}
+inline unsigned int Road::GetDifficulty() const
+{
+ return mDifficulty;
+}
+inline void Road::SetShortCut( bool is )
+{
+ mIsShortCut = is;
+}
+inline bool Road::GetShortCut() const
+{
+ return mIsShortCut;
+}
+inline unsigned int Road::GetDensity() const
+{
+ return mDensity;
+}
+inline float Road::GetRoadLength()
+{
+ return mLength;
+}
+inline void Road::SetRoadLength( float len )
+{
+ rAssert( len >= 0.0f );
+ mLength = len;
+}
+inline void Road::SetNumLanes( int count )
+{
+ mnLanes = count;
+}
+inline unsigned int Road::GetNumLanes( void ) const
+{
+ return mnLanes;
+}
+/*
+inline float Road::GetWidth() const
+{
+ return mnLanes * mfLaneWidth;
+}
+*/
+
+#endif
diff --git a/game/code/roads/roadmanager.cpp b/game/code/roads/roadmanager.cpp
new file mode 100644
index 0000000..9b705ca
--- /dev/null
+++ b/game/code/roads/roadmanager.cpp
@@ -0,0 +1,2565 @@
+//=============================================================================
+// Copyright (C) 2002 Radical Entertainment Ltd. All rights reserved.
+//
+// File: RoadManager.cpp
+//
+// Description: Implement RoadManager
+//
+// History: 26/06/2002 + Created -- Cary Brisebois
+//
+//=============================================================================
+
+//========================================
+// System Includes
+//========================================
+// Foundation Tech
+#include <raddebug.hpp>
+#include <p3d/entity.hpp>
+#include <raddebugwatch.hpp>
+
+//========================================
+// Project Includes
+//========================================
+#include <render/intersectmanager/intersectmanager.h>
+#include <roads/RoadManager.h>
+#include <roads/road.h>
+#include <roads/intersection.h>
+#include <roads/roadsegmentdata.h>
+#include <roads/roadsegment.h>
+#include <roads/roadrendertest.h>
+
+#ifndef TOOLS
+#include <memory/srrmemory.h>
+#else
+#define MEMTRACK_PUSH_GROUP(x)
+#define MEMTRACK_POP_GROUP()
+void* operator new[](size_t size)
+{
+ return malloc(size);
+}
+#endif
+
+#include <render/RenderManager/RenderManager.h>
+#include <render/RenderManager/RenderLayer.h>
+
+//******************************************************************************
+//
+// Global Data, Local Data, Local Classes
+//
+//******************************************************************************
+RoadManager* RoadManager::mInstance = NULL;
+const float RoadManager::AGAINST_TRAFFIC_COST_MULTIPLIER = 1.30f;
+
+//******************************************************************************
+//
+// Public Member Functions
+//
+//******************************************************************************
+
+RoadManager* RoadManager::GetInstance()
+{
+MEMTRACK_PUSH_GROUP( "RoadManager" );
+ if ( !mInstance )
+ {
+#ifndef TOOLS
+ mInstance = new(GMA_LEVEL_OTHER) RoadManager();
+#else
+ mInstance = new RoadManager();
+#endif
+ //TODO: REMOVE
+ mInstance->Init( STARTUP );
+ }
+MEMTRACK_POP_GROUP( "RoadManager" );
+
+ return mInstance;
+}
+
+//=============================================================================
+// RoadManager::Destroy
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ()
+//
+// Return: void
+//
+//=============================================================================
+void RoadManager::Destroy()
+{
+ delete mInstance;
+ mInstance = NULL;
+}
+
+
+//==============================================================================
+// RoadManager::RoadManager
+//==============================================================================
+// Description: Constructor.
+//
+// Parameters: None.
+//
+// Return: N/A.
+//
+//==============================================================================
+RoadManager::RoadManager()
+{
+ mRoads = NULL;
+ mNumRoads = 0;
+ mNumRoadsUsed = 0;
+ mIntersections = NULL;
+ mNumIntersections = 0;
+ mNumIntersections = 0;
+ mRoadSegmentData = NULL;
+ mNumRoadSegmentData = 0;
+ mNumRoadSegmentDataUsed = 0;
+ mRoadSegments = NULL;
+ mNumRoadSegments = 0;
+ mNumRoadSegmentsUsed = 0;
+
+#ifndef RAD_RELEASE
+#ifdef DEBUGWATCH
+ mRender = new(GMA_LEVEL_OTHER) RoadRenderTest;
+
+ RenderManager* rm = GetRenderManager();
+ RenderLayer* rl = rm->mpLayer( RenderEnums::LevelSlot );
+ rAssert( rl );
+
+ rl->AddGuts( mRender );
+#endif
+#endif
+}
+
+//==============================================================================
+// RoadManager::~RoadManager
+//==============================================================================
+// Description: Destructor.
+//
+// Parameters: None.
+//
+// Return: N/A.
+//
+//==============================================================================
+RoadManager::~RoadManager()
+{
+ Init( SHUTDOWN );
+}
+
+//=============================================================================
+// RoadManager::Init
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ()
+//
+// Return: void
+//
+//=============================================================================
+void RoadManager::Init( bool shutdown )
+{
+ if ( mRoads )
+ {
+ delete[] mRoads;
+ mRoads = NULL;
+ }
+ mNumRoads = 0;
+ mNumRoadsUsed = 0;
+
+ if ( mIntersections )
+ {
+ delete[] mIntersections;
+ mIntersections = NULL;
+ }
+ mNumIntersections = 0;
+ mNumIntersectionsUsed = 0;
+
+ if ( mRoadSegmentData )
+ {
+ delete[] mRoadSegmentData;
+ mRoadSegmentData = NULL;
+ }
+ mNumRoadSegmentData = 0;
+ mNumRoadSegmentDataUsed = 0;
+
+ if ( mRoadSegments )
+ {
+ for(unsigned int x = 0; x < mNumRoadSegments; x++)
+ {
+ mRoadSegments[x]->Release ();
+ }
+ delete[] mRoadSegments;
+ mRoadSegments = NULL;
+ }
+ mNumRoadSegments = 0;
+ mNumRoadSegmentsUsed = 0;
+
+ if( !shutdown )
+ {
+ InitializeRoadSegmentDataMemory( 1200 );
+ //TODO: base this on incoming chunk data.
+ InitializeRoadMemory( 150 );
+ InitializeIntersectionMemory( 60 );
+ InitializeRoadSegmentMemory( 1200 );
+ }
+}
+void RoadManager::InitializeRoadMemory( unsigned int numRoads )
+{
+
+#ifndef TOOLS
+#ifdef RAD_GAMECUBE
+ HeapMgr()->PushHeap( GMA_GC_VMM );
+#else
+ HeapMgr()->PushHeap( GMA_LEVEL_OTHER );
+#endif
+#endif
+
+ if( mRoads )
+ {
+ delete[] mRoads;
+ }
+
+ mRoads = new Road[numRoads];
+ mNumRoads = numRoads;
+ mNumRoadsUsed = 0;
+
+#ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PopHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PopHeap( GMA_LEVEL_OTHER );
+ #endif
+#endif
+}
+
+
+void RoadManager::InitializeIntersectionMemory( unsigned int numIntersections )
+{
+#ifndef TOOLS
+#ifdef RAD_GAMECUBE
+ HeapMgr()->PushHeap( GMA_GC_VMM );
+#else
+ HeapMgr()->PushHeap( GMA_LEVEL_OTHER );
+#endif
+#endif
+
+ if( mIntersections )
+ {
+ delete[] mIntersections;
+ }
+
+ mIntersections = new Intersection[numIntersections];
+ mNumIntersections = numIntersections;
+ mNumIntersectionsUsed = 0;
+
+#ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PopHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PopHeap( GMA_LEVEL_OTHER );
+ #endif
+#endif
+}
+
+
+void RoadManager::InitializeRoadSegmentDataMemory( unsigned int numSegments )
+{
+#ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PushHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PushHeap( GMA_TEMP );
+ #endif
+#endif
+
+ if( mRoadSegmentData )
+ {
+ delete[] mRoadSegmentData;
+ }
+
+ mRoadSegmentData = new RoadSegmentData[numSegments];
+ mNumRoadSegmentData = numSegments;
+ mNumRoadSegmentDataUsed = 0;
+
+#ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PopHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PopHeap( GMA_TEMP );
+ #endif
+#endif
+}
+
+void RoadManager::DumpRoadSegmentDataMemory()
+{
+ if( mRoadSegmentData )
+ {
+ delete[] mRoadSegmentData;
+ }
+ mRoadSegmentData = NULL;
+ mNumRoadSegmentData = 0;
+ mNumRoadSegmentDataUsed = 0;
+}
+
+
+void RoadManager::InitializeRoadSegmentMemory( unsigned int numRoadSegments )
+{
+#ifndef TOOLS
+#ifdef RAD_GAMECUBE
+ HeapMgr()->PushHeap( GMA_GC_VMM );
+#else
+ HeapMgr()->PushHeap( GMA_LEVEL_OTHER );
+#endif
+#endif
+
+ if( mRoadSegments )
+ {
+ delete[] mRoadSegments;
+ }
+
+ mRoadSegments = new RoadSegment*[numRoadSegments];
+
+ unsigned int i = 0;
+ for( i ; i < numRoadSegments ; i++ )
+ {
+ mRoadSegments[i] = new RoadSegment;
+ mRoadSegments[i]->AddRef();
+ }
+ mNumRoadSegments = numRoadSegments;
+ mNumRoadSegmentsUsed = 0;
+
+#ifndef TOOLS
+ #ifdef RAD_GAMECUBE
+ HeapMgr()->PopHeap( GMA_GC_VMM );
+ #else
+ HeapMgr()->PopHeap( GMA_LEVEL_OTHER );
+ #endif
+#endif
+}
+
+
+
+Road* RoadManager::GetFreeRoadMemory()
+{
+ if( 0 <= mNumRoadsUsed && mNumRoadsUsed < mNumRoads )
+ {
+ Road* road;
+ road = &(mRoads[mNumRoadsUsed]);
+ return road;
+ }
+
+ return NULL;
+}
+
+Intersection* RoadManager::GetFreeIntersectionMemory()
+{
+ if( 0 <= mNumIntersectionsUsed && mNumIntersectionsUsed < mNumIntersections )
+ {
+ Intersection* intersection;
+ intersection = &(mIntersections[mNumIntersectionsUsed]);
+ return intersection;
+ }
+
+ return NULL;
+}
+
+RoadSegmentData* RoadManager::GetFreeRoadSegmentDataMemory()
+{
+ if( 0 <= mNumRoadSegmentsUsed && mNumRoadSegmentDataUsed < mNumRoadSegmentData )
+ {
+ RoadSegmentData* rsd;
+ rsd = &(mRoadSegmentData[mNumRoadSegmentDataUsed]);
+ return rsd;
+ }
+ else
+ {
+ rDebugPrintf( "NUMROADSUSED = %d, NUMROADS = %d\n",
+ mNumRoadSegmentDataUsed, mNumRoadSegmentData );
+ }
+
+ return NULL;
+}
+
+RoadSegment* RoadManager::GetFreeRoadSegmentMemory()
+{
+ if( 0 <= mNumRoadSegmentsUsed && mNumRoadSegmentsUsed < mNumRoadSegments )
+ {
+ return mRoadSegments[mNumRoadSegmentsUsed];
+ }
+ return NULL;
+}
+
+
+int RoadManager::GetMaxPathElements()
+{
+ // max elems we could ever have include:
+ // - sourceroad,
+ // - targetroad,
+ // - total number of intersections + their adjoining roads
+ return (1 + 1 + (GetNumIntersectionsUsed() * 2) - 1);
+}
+
+bool RoadManager::FindClosestPointOnRoad( const Road* pRoad,
+ const rmt::Vector& pos,
+ rmt::Vector& closestPos,
+ float& closestDistSqr,
+ int& segmentIndex )
+{
+ rAssert( pRoad );
+
+ rmt::Vector vec0, vec1, vec2, vec3;
+ rmt::Vector start, end;
+
+ // Take the destination intersection as the closest point so far
+ //
+ closestDistSqr = NEAR_INFINITY;
+ segmentIndex = -1;
+
+ for( int i = 0; i < (int)(pRoad->GetNumRoadSegments()); i++ )
+ {
+ RoadSegment* segment = pRoad->GetRoadSegment( i );
+ segment->GetCorner( 0, vec0 );
+ segment->GetCorner( 1, vec1 );
+ segment->GetCorner( 2, vec2 );
+ segment->GetCorner( 3, vec3 );
+
+ // Calc the midpoints at the start and end of the segment
+ //
+ start = (vec0+vec3) * 0.5f;
+ end = (vec1+vec2) * 0.5f;
+
+ // Calc the vector along the centre of the segment
+ //
+ rmt::Vector candidatePt;
+ FindClosestPointOnLine( start, end, pos, candidatePt );
+
+ // Calc vector between closest point on segment and target
+ //
+ float distSqr = (candidatePt - pos).MagnitudeSqr();
+ if( distSqr < closestDistSqr )
+ {
+ closestDistSqr = distSqr;
+ closestPos = candidatePt;
+ segmentIndex = i;
+ }
+ }
+
+ return true;
+}
+
+float RoadManager::DetermineRoadT( RoadSegment* seg, float segT )
+{
+ rAssert( seg );
+
+ unsigned int segIndex = seg->GetSegmentIndex();
+ Road* road = seg->GetRoad();
+ float roadT = 0.0f;
+
+ // determine progress "t" along the road
+ float segLen = 0.0f;
+ RoadSegment* prevSeg = NULL;
+ for( unsigned int j=0; j<segIndex; j++ )
+ {
+ prevSeg = road->GetRoadSegment( j );
+ segLen = prevSeg->GetSegmentLength();
+ roadT += segLen;
+ }
+ segLen = seg->GetSegmentLength();
+ roadT += segLen * segT;
+ roadT /= ((Road*)road)->GetRoadLength();
+
+ return roadT;
+}
+float RoadManager::DetermineSegmentT( const rmt::Vector& pos, RoadSegment* seg )
+{
+ rAssert( seg );
+
+ float segT = 0.0f;
+
+ // determine progress "t" along segment
+ rmt::Vector vec0, vec1, vec2, vec3;
+ rmt::Vector segStart, segEnd, closestPt;
+
+ seg->GetCorner( 0, vec0 );
+ seg->GetCorner( 1, vec1 );
+ seg->GetCorner( 2, vec2 );
+ seg->GetCorner( 3, vec3 );
+
+ segStart = (vec0 + vec3) * 0.5f;
+ segEnd = (vec1 + vec2) * 0.5f;
+
+ FindClosestPointOnLine( segStart, segEnd, pos, closestPt );
+
+ segT = GetLineSegmentT( segStart, segEnd, closestPt );
+ rAssert( 0.0f <= segT && segT <= 1.0f );
+ return segT;
+}
+
+
+//=============================================================================
+// RoadManager::CreateRoadNetwork
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ( void )
+//
+// Return: void
+//
+//=============================================================================
+void RoadManager::CreateRoadNetwork( void )
+{
+ for( unsigned int i = 0; i < mNumIntersectionsUsed; ++i )
+ {
+ // sort which ones are my IN & OUT roads, determine adjacency,
+ // determine if it's a big intersection (3 or more different adjacent
+ // intersections) and do some error checking
+ mIntersections[i].SortRoads();
+ mIntersections[i].mIndex = i;
+ }
+ PopulateConnectivityData( true, mIntersections, (int)(mNumIntersectionsUsed) );
+ PopulateConnectivityData( false, mIntersections, (int)(mNumIntersectionsUsed) );
+}
+
+
+void RoadManager::PopulateConnectivityData( bool useMultiplier, Intersection* intersections, int numInts )
+{
+ // nothing to do if there are no intersections
+ if( numInts <= 0 )
+ {
+ return;
+ }
+
+ //
+ // Create our temporary representation of each intersection:
+ // an array of Dijkstra nodes
+ //
+ SwapArray<DijkstraNode> nodes;
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ nodes.Allocate( numInts );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ nodes.mUseSize = numInts;
+
+ for( int i=0; i<numInts; i++ )
+ {
+ Intersection* in = &(intersections[i]);
+ nodes[i].in = in;
+ }
+
+ //
+ // Populate adjacency data for each Dijkstra node &
+ // store the cost for reachability
+ //
+ for( int i=0; i<numInts; i++ )
+ {
+ Intersection* in = nodes[i].in;
+ rAssert( in );
+
+ SwapArray<ShortestRoad>* shortestRoads = useMultiplier ?
+ &(in->mShortestRoadsToAdjacentIntersectionsWithMultiplier) :
+ &(in->mShortestRoadsToAdjacentIntersectionsNoMultiplier) ;
+
+ int numAdjacents = shortestRoads->mUseSize;
+ rAssert( numAdjacents > 0 );
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ nodes[i].adjacents.Allocate( numAdjacents );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ nodes[i].adjacents.mUseSize = numAdjacents;
+
+ int count = 0;
+
+ // for each adjacent intersection, fill in the corresponding
+ // dijkstra node pointer and distance
+ for( int j=0; j<shortestRoads->mUseSize; j++ )
+ {
+ ShortestRoad* sr = &((*shortestRoads)[j]);
+ rAssert( sr );
+ Road* road = sr->road;
+ rAssert( road );
+
+ Intersection* adjInt = NULL;
+ if( sr->isOutRoad )
+ {
+ adjInt = (Intersection*) road->GetDestinationIntersection();
+ }
+ else
+ {
+ adjInt = (Intersection*) road->GetSourceIntersection();
+ }
+ rAssert( adjInt );
+ rAssert( adjInt != in );
+
+ bool found = false;
+ for( int k=0; k<numInts; k++ )
+ {
+ if( adjInt == nodes[k].in )
+ {
+ found = true;
+ nodes[i].adjacents[count].adjacentNode = &(nodes[k]);
+ nodes[i].adjacents[count].shortestRoadThere = sr;
+ count++;
+ break;
+ }
+ }
+ rAssert( found );
+ }
+ rAssert( count == numAdjacents );
+ }
+
+ // foreach BIG intersection, populate its routing table
+ for( int i=0; i<numInts; i++ )
+ {
+ Intersection* src = &(intersections[i]);
+ if( !src->mBigIntersection )
+ {
+ continue;
+ }
+
+ SwapArray<NodeData>* routes = useMultiplier ?
+ &(src->mBigIntersection->routesWithMultiplier) :
+ &(src->mBigIntersection->routesNoMultiplier) ;
+
+ HeapMgr()->PushHeap(GMA_LEVEL_OTHER);
+ routes->Allocate( numInts );
+ HeapMgr()->PopHeap(GMA_LEVEL_OTHER);
+
+ routes->mUseSize = numInts;
+
+ // initialize every Dijkstra node
+ for( int j=0; j<numInts; j++ )
+ {
+ nodes[j].Init( NEAR_INFINITY, NULL );
+ }
+ // initialize distance to source to zero
+ DijkstraNode* s = &(nodes[src->mIndex]);
+ s->distToSrc = 0.0f;
+
+ // determine best route to get from s to every other node
+ VisitAll( nodes );
+
+ //
+ // Populate routes:
+ // For each node pointer "a" at index "i" in array "nodes",
+ // follow predecessor pointers back to some node pointer "n"
+ // adjacent to src node, and set routes[i].destIn = n->in
+ // set routes[i].dist = a->distToSrc
+ //
+ for( int j=0; j<numInts; j++ )
+ {
+ DijkstraNode* a = &(nodes[j]);
+ rAssert( a->in->mIndex == j );
+ // if this node is the source node...
+ if( a == s )
+ {
+ (*routes)[j].destIn = NULL;
+ (*routes)[j].roadToIn = NULL;
+ (*routes)[j].roadJustBeforeIn = NULL;
+ }
+ else
+ {
+ SwapArray<ShortestRoad>* shortestRoads = NULL;
+
+ // find the last road just before reaching destIn
+ DijkstraNode* n = a;
+ rAssert( n );
+ rAssert( n->predecessor );
+
+ shortestRoads = useMultiplier ?
+ &(n->predecessor->in->mShortestRoadsToAdjacentIntersectionsWithMultiplier) :
+ &(n->predecessor->in->mShortestRoadsToAdjacentIntersectionsNoMultiplier) ;
+
+ ShortestRoad* roadToTake = NULL;
+ for( int k=0; k<shortestRoads->mUseSize; k++ )
+ {
+ ShortestRoad* candidate = &((*shortestRoads)[k]);
+ rAssert( candidate );
+
+ Intersection* candidateInt = NULL;
+ if( candidate->isOutRoad )
+ {
+ candidateInt = (Intersection*)
+ candidate->road->GetDestinationIntersection();
+ }
+ else
+ {
+ candidateInt = (Intersection*)
+ candidate->road->GetSourceIntersection();
+ }
+ if( candidateInt == n->in )
+ {
+ roadToTake = candidate;
+ break;
+ }
+ }
+ rAssert( roadToTake );
+ (*routes)[j].roadJustBeforeIn = roadToTake;
+
+ // find the road immediately leaving this big intersection
+ // that will put us on the correct path towards destIn
+
+ while( n->predecessor != s )
+ {
+ n = n->predecessor;
+ rAssert( n != NULL );
+ }
+ rAssert( n->in != NULL );
+ (*routes)[j].destIn = n->in;
+
+ // find the road that will take us to dest intersection
+ shortestRoads = useMultiplier ?
+ &(src->mShortestRoadsToAdjacentIntersectionsWithMultiplier) :
+ &(src->mShortestRoadsToAdjacentIntersectionsNoMultiplier) ;
+
+ roadToTake = NULL;
+ for( int k=0; k<shortestRoads->mUseSize; k++ )
+ {
+ ShortestRoad* candidate = &((*shortestRoads)[k]);
+ rAssert( candidate );
+
+ Intersection* candidateInt = NULL;
+ if( candidate->isOutRoad )
+ {
+ candidateInt = (Intersection*)
+ candidate->road->GetDestinationIntersection();
+ }
+ else
+ {
+ candidateInt = (Intersection*)
+ candidate->road->GetSourceIntersection();
+ }
+ if( candidateInt == n->in )
+ {
+ roadToTake = candidate;
+ break;
+ }
+ }
+ rAssert( roadToTake );
+ (*routes)[j].roadToIn = roadToTake;
+ }
+ (*routes)[j].dist = a->distToSrc;
+ }
+ }
+ nodes.Clear();
+}
+
+void RoadManager::VisitAll( SwapArray<DijkstraNode>& nodes )
+{
+ int numInts = nodes.mUseSize;
+ rAssert( numInts > 0 );
+
+ ///////////////////
+ // Dijkstra
+ ///////////////////
+
+ // Create "VS": a list of pointers to nodes that haven't been visited
+ SwapArray<DijkstraNode*> VS;
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ VS.Allocate( numInts );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ VS.mUseSize = numInts;
+ int i;
+ for( i=0; i<numInts; i++ )
+ {
+ VS[i] = &(nodes[i]);
+ }
+
+ // Create "S": a list of pointers to nodes that we have visited
+ // which is initially empty
+ SwapArray<DijkstraNode*> S;
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ S.Allocate( numInts );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ // Greedy-extract cheapest node one by one from VS and put in S
+ while( VS.mUseSize > 0 )
+ {
+ // Find the cheapest, remove from VS, put in S
+ int cheapest = -1;
+ float cheapestDist = NEAR_INFINITY;
+ DijkstraNode* u = NULL;
+
+ for( i=0; i<VS.mUseSize; i++ )
+ {
+ DijkstraNode* node = VS[i];
+ if( node->distToSrc < cheapestDist )
+ {
+ u = node;
+ cheapestDist = node->distToSrc;
+ cheapest = i;
+ }
+ }
+ rAssert( 0 <= cheapest && cheapest < VS.mUseSize );
+ S.Add( u ); // Dijkstra giveth
+ VS.Remove( cheapest ); // Dijkstra taketh away
+ u->addedToS = true;
+
+ // Relax the cost for all nodes adjacent to cheapestNode
+ for( int i=0; i<u->adjacents.mUseSize; i++ )
+ {
+ DijkstraNode* v = u->adjacents[i].adjacentNode;
+ rAssert( v );
+
+ if( v->addedToS ) // skip v is already in S
+ {
+ continue;
+ }
+
+ /////////////////////////////////////////////////////////////
+ // the cost is the length of the shortest road to the
+ // adjacent intersection PLUS the cost of traversal
+ // through intersection "u" from the road from our
+ // predecessor to this shortest road.
+
+ float adjacentDist = u->adjacents[i].shortestRoadThere->cost;
+ if( u->shortestRoadFromPred )
+ {
+ ShortestRoad* fromRoad = u->shortestRoadFromPred;
+ ShortestRoad* toRoad = u->adjacents[i].shortestRoadThere;
+ adjacentDist += GetTraversalDistance( fromRoad, toRoad );
+ }
+
+ if( v->distToSrc > (u->distToSrc + adjacentDist) )
+ {
+ v->distToSrc = u->distToSrc + adjacentDist;
+ v->predecessor = u;
+ v->shortestRoadFromPred = u->adjacents[i].shortestRoadThere;
+ }
+ }
+ }
+
+ VS.Clear();
+ S.Clear();
+}
+
+float RoadManager::FindPathElementsBetween(
+ bool useMultiplier,
+ PathElement& sourceElem,
+ float sourceT, // used only if sourceElem is a road
+ const rmt::Vector& sourcePos, // used only if sourceElem is an intersection
+ PathElement& targetElem,
+ float targetT, // used only if targetElem is a road
+ const rmt::Vector& targetPos, // used only if targetElem is an intersection
+ SwapArray<PathElement>& elems ) // accumulate roads
+{
+ rAssert( sourceElem.elem != NULL );
+ rAssert( targetElem.elem != NULL );
+ rAssert( 0.0f <= sourceT && sourceT <= 1.0f );
+ rAssert( elems.IsSetUp() );
+
+ float totalDist = 0.0f;
+
+ // for safety's sake... make this check...
+ // we need to make sure that the last element's type was
+ // not the same as sourceElem's type... this maintains the nice
+ // "...-int-road-int-road-int-..." series
+ if( elems.mUseSize > 0 )
+ {
+ rAssert( elems[ elems.mUseSize-1 ].type != sourceElem.type );
+ if( elems[ elems.mUseSize-1 ].type == sourceElem.type )
+ {
+ return totalDist;
+ }
+ }
+
+ //
+ // We will be returning a swaparray of PathElements that lie between
+ // the source and the target PathElements. A PathElement can be a
+ // shortest road or an intersection.
+ //
+
+ // the first thing we add should be the source road!
+ if( sourceElem.type == ET_NORMALROAD )
+ {
+ elems.Add( sourceElem );
+
+ // if it's a shortcut, and target road isn't this road,
+ // call this function again with the destination intersection..
+ Road* srcRd = (Road*) sourceElem.elem;
+ if( srcRd->GetShortCut() && sourceElem != targetElem )
+ {
+ Intersection* srcInt = (Intersection*) srcRd->GetDestinationIntersection();
+
+ rmt::Vector intPos;
+ srcInt->GetLocation( intPos );
+
+ float distToDestInt = (1.0f - sourceT) * srcRd->GetRoadLength();
+
+ rmt::Vector vec1,vec2,endOfRdPos;
+ RoadSegment* endOfRdSeg = srcRd->GetRoadSegment( srcRd->GetNumRoadSegments()-1 );
+ endOfRdSeg->GetCorner( 1, vec1 );
+ endOfRdSeg->GetCorner( 2, vec2 );
+ endOfRdPos = (vec1+vec2) * 0.5f;
+
+ distToDestInt += (endOfRdPos - intPos).Magnitude(); // *** SQUARE ROOT! ***
+
+
+ /*
+ // TODO:
+ // This is a big problem. We're CHANGING sourceElem here... which
+ // changes the value for whoever passed in sourceElem (cuz sourceElem
+ // was passed in by reference .. BIATCH!)... Somehow things have been
+ // miraculously working, I'm not sure why.. Basically the only case
+ // where this bug applies is when the somebody (e.g. the avater, the AI,
+ // the HUD map, light path, etc.) is on a shortcut and
+ // he's pathfinding to some target. The sourceElem will be set to the
+ // destination intersection of that shortcut, so the Avatar and Ai's
+ // mLastPathElement members will be inaccurate... Aiya!
+ // Too late to change this at this point. Just leave it unless the
+ // problems are OVERWHELMINGLY bad...
+ //
+ PathElement tmpElem;
+ tmpElem.type = ET_INTERSECTION;
+ tmpElem.elem = srcInt;
+ */
+ sourceElem.type = ET_INTERSECTION;
+ sourceElem.elem = srcInt;
+
+ SwapArray<PathElement> tmpElems;
+
+ HeapMgr()->PushHeap( GMA_TEMP );
+ tmpElems.Allocate( elems.mSize );
+ HeapMgr()->PopHeap( GMA_TEMP );
+
+ totalDist += distToDestInt + FindPathElementsBetween( useMultiplier,
+ sourceElem, 0.0f, intPos, targetElem, targetT, targetPos, tmpElems );
+
+ for( int i=0; i<tmpElems.mUseSize; i++ )
+ {
+ elems.Add( tmpElems[i] );
+ }
+ tmpElems.Clear();
+
+ return totalDist;
+ }
+ }
+
+
+ // if source and target are the same, then return dist between them!
+ if( sourceElem == targetElem )
+ {
+ // if road, use T values to compute dist betw them
+ if( sourceElem.type == ET_NORMALROAD )
+ {
+ // TODO:
+ // Can't just happily return here... Not right to just
+ // compute the totalDist this way either...
+ // What if it's closer to go the other way (i.e. not along the
+ // given road, but via another road)? Hmm??
+ // Careful... Fixing this might change behavior below
+ // where some asserts assume that we have returned at this point...
+ //
+ // Here's the problem in detail:
+ //
+ // One of the other nuances with the pathfinding algo was quite
+ // evident in SuperSprint before we hacked the data to never produce
+ // the problem.. The bug still exists in code, however, but I haven't
+ // really seen it expressed anywhere else in the world.
+ //
+ // The algorithm "tries to be smart" and says, "Hey, if S is on the
+ // same road as T, then the distance between them must be just the
+ // distance along the road between S and T"... This is not necessarily
+ // the case.
+ //
+ // For example, take a particularly long road, with S and T near
+ // either ends of the road... But the road's either ends are connected
+ // via another road...like so (A and B are intersections):
+ //
+ // -<--S--A--<--B--T--<-
+ // | |
+ // | |
+ // ---->---------->-----
+ //
+ // In this case, it's actually closer to get from S to T via
+ // intersection A, then to B, then to T... but the algorithm returns
+ // the closest distance to be along the road from S to T
+ //
+
+ Road* someRoad = (Road*)sourceElem.elem;
+ float someRoadLen = someRoad->GetRoadLength();
+ float sourceProgress = someRoadLen * sourceT;
+ float targetProgress = someRoadLen * targetT;
+ totalDist += rmt::Fabs(sourceProgress - targetProgress);
+
+ return totalDist;
+ }
+ else // both in same intersection
+ {
+ totalDist += (sourcePos - targetPos).Length(); // *** SQUARE ROOT! ***
+ elems.Add( targetElem );
+ return totalDist;
+ }
+ }
+ else if( sourceElem.type == ET_NORMALROAD && targetElem.type == ET_NORMALROAD )
+ {
+ // figure out if the source is actually a road on the opposite lane..
+ // if so, ignore it if we're still close enough to the previous segment.
+ // This is to fix the problem where you're on the same physical road as
+ // your target, but you're on the incoming road and it's on the outgoing
+ // road, so you're actually doing unnecessary pathfinding around your
+ // own road to get to the correct road... stupid...
+ //
+ // Example:
+ // <--------------- you -----------------------------------
+ // -------AI ---------------------------- checkpoint ----->
+ //
+ // Here you are physically closer, but you're ranked second, behind the AI
+ // because you have to take extra pathfinding steps around your own road,
+ // to reach either intersections before getting on the correct road. Blegh.
+ //
+
+ Road* srcRoad = (Road*)sourceElem.elem;
+ Road* targRoad = (Road*)targetElem.elem;
+
+ rAssert( srcRoad != targRoad );
+
+
+ const Intersection* srcSrcInt = srcRoad->GetSourceIntersection();
+ const Intersection* srcDestInt = srcRoad->GetDestinationIntersection();
+ const Intersection* targSrcInt = targRoad->GetSourceIntersection();
+ const Intersection* targDestInt = targRoad->GetDestinationIntersection();
+
+ if( srcSrcInt == targDestInt && srcDestInt == targSrcInt )
+ {
+ // whoa, these roads are connecting the same intersections!
+ // figure out how far we really are from last road...
+
+ rmt::Vector closestPtOnSrc;
+ float distFromClosestPtOnSrcSqr = NEAR_INFINITY;
+ int closestSrcSegIndex = -1;
+
+ FindClosestPointOnRoad( srcRoad, sourcePos, closestPtOnSrc,
+ distFromClosestPtOnSrcSqr, closestSrcSegIndex );
+
+ rmt::Vector closestPtOnTarg;
+ float distFromClosestPtOnTargSqr = NEAR_INFINITY;
+ int closestTargSegIndex = -1;
+
+ FindClosestPointOnRoad( targRoad, closestPtOnSrc, closestPtOnTarg,
+ distFromClosestPtOnTargSqr, closestTargSegIndex );
+ /*
+ FindClosestPointOnRoad( targRoad, sourcePos, closestPtOnTarg,
+ distFromClosestPtOnTargSqr, closestTargSegIndex );
+ */
+
+ rAssert( closestTargSegIndex != -1 );
+
+ // if within 10 meters from road center, source and target roads
+ // must be part of the same road...
+ const float CLOSE_ENOUGH_TO_BE_ADJACENT_ROAD_SQR = 100.0f;
+
+ if( distFromClosestPtOnTargSqr < CLOSE_ENOUGH_TO_BE_ADJACENT_ROAD_SQR )
+ {
+ // TODO:
+ // Can't just happily return here... Not right to just
+ // compute the totalDist this way either...
+ // What if it's closer to go the other way (i.e. not along the
+ // given road, but via another road)? Hmm??
+ // Careful... Fixing this might change behavior below
+ // where some asserts assume that we have returned at this point...
+ //
+ // Here's the problem in detail:
+ //
+ // One of the other nuances with the pathfinding algo was quite
+ // evident in SuperSprint before we hacked the data to never produce
+ // the problem.. The bug still exists in code, however, but I haven't
+ // really seen it expressed anywhere else in the world.
+ //
+ // The algorithm "tries to be smart" and says, "Hey, if S is on the
+ // same road as T, then the distance between them must be just the
+ // distance along the road between S and T"... This is not necessarily
+ // the case.
+ //
+ // For example, take a particularly long road, with S and T near
+ // either ends of the road... But the road's either ends are connected
+ // via another road...like so (A and B are intersections):
+ //
+ // -<--S--A--<--B--T--<-
+ // | |
+ // | |
+ // ---->---------->-----
+ //
+ // In this case, it's actually closer to get from S to T via
+ // intersection A, then to B, then to T... but the algorithm returns
+ // the closest distance to be along the road from S to T
+ //
+ RoadSegment* closestTargSeg = (RoadSegment*) targRoad->GetRoadSegment(
+ (unsigned int)closestTargSegIndex );
+
+ float closestTargSegT = RoadManager::DetermineSegmentT( closestPtOnTarg, closestTargSeg );
+ float closestTargRoadT = RoadManager::DetermineRoadT( closestTargSeg, closestTargSegT );
+
+ float targRoadLen = targRoad->GetRoadLength();
+ float sourceProgress = targRoadLen * closestTargRoadT;
+ float targetProgress = targRoadLen * targetT;
+ totalDist += rmt::Fabs(sourceProgress - targetProgress);
+
+ elems.Remove( elems.mUseSize - 1 );
+ elems.Add( targetElem );
+
+ return totalDist;
+ }
+ }
+ }
+
+
+
+
+ // determine what we know about the target
+ float distFromTargetToInt = 0.0f;
+ float distFromTargetToOtherInt = 0.0f;
+ Intersection* targetInt = NULL; // the one we're heading towards
+ Intersection* targetOtherInt = NULL; // if targetElem is a road, it's the other intersection
+ ShortestRoad targetShortRoad;
+ targetShortRoad.cost = NEAR_INFINITY;
+
+ if( targetElem.type == ET_INTERSECTION )
+ {
+ targetInt = (Intersection*) targetElem.elem;
+ targetShortRoad.road = NULL;
+ }
+ else
+ {
+ rAssert( targetElem.type == ET_NORMALROAD );
+
+ Road* targetRoad = (Road*) targetElem.elem;
+ targetShortRoad.road = targetRoad;
+
+ targetInt = (Intersection*) targetRoad->GetSourceIntersection();
+ distFromTargetToInt = targetT * targetRoad->GetRoadLength();
+
+ if( !targetRoad->GetShortCut() )
+ {
+ targetOtherInt = (Intersection*) targetRoad->GetDestinationIntersection();
+ // if we're getting to target via dest int, we're going against traffic
+ // so use the multiplier
+ distFromTargetToOtherInt = (1.0f - targetT) * targetRoad->GetRoadLength() *
+ ((useMultiplier)? AGAINST_TRAFFIC_COST_MULTIPLIER : 1.0f);
+ }
+ else
+ {
+ targetOtherInt = NULL;
+ distFromTargetToOtherInt = NEAR_INFINITY;
+ }
+
+
+ }
+ // at least targetInt should exist...
+ rAssert( targetInt );
+
+ bool goingToTargetOther = false;
+
+ ShortestRoad* firstShortRoad = NULL;
+ ShortestRoad* lastShortRoad = NULL;
+ //////////////////////////////////////////////////////////////////////////////////
+
+
+ // deal with the simplest case first...
+ bool foundSimpleCase = false;
+ if( sourceElem.type == ET_INTERSECTION )
+ {
+ // if I'm a big intersection or if I only got one way to go...
+ // just call TraverseRoads...
+ Intersection* sourceInt = (Intersection*) sourceElem.elem;
+ SwapArray<ShortestRoad>* shortestRoads = useMultiplier ?
+ &(sourceInt->mShortestRoadsToAdjacentIntersectionsWithMultiplier) :
+ &(sourceInt->mShortestRoadsToAdjacentIntersectionsNoMultiplier) ;
+
+ if( sourceInt->mBigIntersection || shortestRoads->mUseSize == 1 )
+ {
+ foundSimpleCase = true;
+
+ SwapArray<PathElement> elemsToTargetInt, elemsToTargetOtherInt;
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ elemsToTargetInt.Allocate( elems.mSize );
+ elemsToTargetOtherInt.Allocate( elems.mSize );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ ErrorValue errVal;
+
+ float distViaTargetInt = NEAR_INFINITY;
+ float distViaTargetOtherInt = NEAR_INFINITY;
+
+ firstShortRoad = NULL;
+ lastShortRoad = NULL;
+
+ // PATH: sourceInt -> ... -> targetRoad's srcInt -> targetRoad
+ distViaTargetInt = FindDistToTargetInOneDirection( useMultiplier,
+ targetInt, sourceInt, sourceInt, NULL, elemsToTargetInt,
+ firstShortRoad, lastShortRoad, errVal ) +
+ distFromTargetToInt;
+ rAssert( errVal == FOUND_BIGINTERSECTION || errVal == FOUND_TARGET );
+ if( targetElem.type == ET_NORMALROAD )
+ {
+ if( lastShortRoad )
+ {
+ targetShortRoad.isOutRoad = true; // at target road's source intersection, the target road is an OUT road
+ distViaTargetInt += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+ }
+
+ if( targetOtherInt )
+ {
+ firstShortRoad = NULL;
+ lastShortRoad = NULL;
+
+ // PATH: sourceInt -> ... -> targetRoad's destInt -> targetRoad
+ distViaTargetOtherInt = FindDistToTargetInOneDirection( useMultiplier,
+ targetOtherInt, sourceInt, sourceInt, NULL, elemsToTargetOtherInt,
+ firstShortRoad, lastShortRoad, errVal ) +
+ distFromTargetToOtherInt;
+ rAssert( errVal == FOUND_BIGINTERSECTION || errVal == FOUND_TARGET );
+ if( targetElem.type == ET_NORMALROAD )
+ {
+ if( lastShortRoad )
+ {
+ targetShortRoad.isOutRoad = false; // at target road's dest intersection, the target road is an OUT road
+ distViaTargetOtherInt += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+ }
+
+ }
+
+ if( distViaTargetInt < distViaTargetOtherInt )
+ {
+ // don't need to copy over the roads, we're visiting sourceInt
+ // again
+ TraverseRoads( useMultiplier, targetInt, sourceInt, sourceInt, elems, errVal );
+ totalDist += distViaTargetInt;
+ }
+ else
+ {
+ rAssert( targetOtherInt );
+ // don't need to copy over the roads, we're visiting sourceInt
+ // again
+ goingToTargetOther = true;
+ TraverseRoads( useMultiplier, targetOtherInt, sourceInt, sourceInt, elems, errVal );
+ totalDist += distViaTargetOtherInt;
+ }
+ rAssert( errVal == FOUND_TARGET );
+ }
+ }
+
+ //
+ // Well we either got source being a road or a small intersection with
+ // 2 adjacent neighbors. Either way, we have to traverse in both directions...
+ //
+ if( !foundSimpleCase )
+ {
+ float distToTargetIntInOneDir = NEAR_INFINITY;
+ float distToTargetIntInOtherDir = NEAR_INFINITY;
+ float distToTargetOtherIntInOneDir = NEAR_INFINITY;
+ float distToTargetOtherIntInOtherDir = NEAR_INFINITY;
+
+ SwapArray<PathElement> elemsToTargetIntInOneDir;
+ SwapArray<PathElement> elemsToTargetIntInOtherDir;
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ elemsToTargetIntInOneDir.Allocate( elems.mSize );
+ elemsToTargetIntInOtherDir.Allocate( elems.mSize );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ SwapArray<PathElement> elemsToTargetOtherIntInOneDir;
+ SwapArray<PathElement> elemsToTargetOtherIntInOtherDir;
+ if( targetOtherInt )
+ {
+ HeapMgr()->PushHeap(GMA_TEMP);
+ elemsToTargetOtherIntInOneDir.Allocate( elems.mSize );
+ elemsToTargetOtherIntInOtherDir.Allocate( elems.mSize );
+ HeapMgr()->PopHeap(GMA_TEMP);
+ }
+ ErrorValue targetIntOneErr = DEAD_END;
+ ErrorValue targetIntOtherErr = DEAD_END;
+ ErrorValue targetOtherIntOneErr = DEAD_END;
+ ErrorValue targetOtherIntOtherErr = DEAD_END;
+
+ if( sourceElem.type == ET_NORMALROAD )
+ {
+ // Explore in both directions along our source road:
+ // - head toward the source intersection and keep going
+ // - head toward the dest intersection and keep going
+ //
+ Road* sourceRoad = (Road*) sourceElem.elem;
+
+ float distToSrcInt, distToDestInt;
+ distToSrcInt = sourceT * sourceRoad->GetRoadLength() *
+ ((useMultiplier)? AGAINST_TRAFFIC_COST_MULTIPLIER : 1.0f);
+ distToDestInt = (1.0f - sourceT) * sourceRoad->GetRoadLength();
+
+ Intersection* sourceSrcInt = (Intersection*) sourceRoad->GetSourceIntersection();
+ Intersection* sourceDestInt = (Intersection*) sourceRoad->GetDestinationIntersection();
+
+ ShortestRoad sourceShortRoad;
+ sourceShortRoad.road = sourceRoad;
+ sourceShortRoad.cost = NEAR_INFINITY;
+
+ if( !sourceRoad->GetShortCut() ) // shortcuts only go one way!!
+ {
+ firstShortRoad = NULL;
+ lastShortRoad = &sourceShortRoad;
+
+ // PATH: sourceRoad -> sourceRoad's srcInt -> ... -> targetRoad's srcInt -> targetRoad
+ sourceShortRoad.isOutRoad = false;
+ distToTargetIntInOneDir = FindDistToTargetInOneDirection( useMultiplier,
+ targetInt, sourceSrcInt, sourceDestInt, NULL, elemsToTargetIntInOneDir,
+ firstShortRoad, lastShortRoad, targetIntOneErr ) + distToSrcInt + distFromTargetToInt;
+ if( firstShortRoad && targetIntOneErr != DEAD_END )
+ {
+ distToTargetIntInOneDir += GetTraversalDistance( &sourceShortRoad, firstShortRoad );
+ }
+ if( targetElem.type == ET_NORMALROAD && targetIntOneErr != DEAD_END )
+ {
+ rAssert( lastShortRoad );
+ targetShortRoad.isOutRoad = true;
+ distToTargetIntInOneDir += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+
+ }
+
+ firstShortRoad = NULL;
+ lastShortRoad = &sourceShortRoad;
+
+ // PATH: sourceRoad -> sourceRoad's destInt -> ... -> targetRoad's srcInt -> targetRoad
+ sourceShortRoad.isOutRoad = true;
+ distToTargetIntInOtherDir = FindDistToTargetInOneDirection( useMultiplier,
+ targetInt, sourceDestInt, sourceSrcInt, NULL, elemsToTargetIntInOtherDir,
+ firstShortRoad, lastShortRoad, targetIntOtherErr ) + distToDestInt + distFromTargetToInt;
+ if( firstShortRoad && targetIntOtherErr != DEAD_END )
+ {
+ distToTargetIntInOtherDir += GetTraversalDistance( &sourceShortRoad, firstShortRoad );
+ }
+ if( targetElem.type == ET_NORMALROAD && targetIntOtherErr != DEAD_END )
+ {
+ rAssert( lastShortRoad );
+ targetShortRoad.isOutRoad = true;
+ distToTargetIntInOtherDir += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+
+ if( targetOtherInt )
+ {
+ if( !sourceRoad->GetShortCut() ) // shortcuts only go one way!!
+ {
+ firstShortRoad = NULL;
+ lastShortRoad = &sourceShortRoad;
+
+ // PATH: sourceRoad -> sourceRoad's srcInt -> ... -> targetRoad's destInt -> targetRoad
+ sourceShortRoad.isOutRoad = false;
+ distToTargetOtherIntInOneDir = FindDistToTargetInOneDirection( useMultiplier,
+ targetOtherInt, sourceSrcInt, sourceDestInt, NULL, elemsToTargetOtherIntInOneDir,
+ firstShortRoad, lastShortRoad, targetOtherIntOneErr ) +
+ distToSrcInt + distFromTargetToOtherInt;
+ if( firstShortRoad && targetOtherIntOneErr != DEAD_END )
+ {
+ distToTargetOtherIntInOneDir += GetTraversalDistance( &sourceShortRoad, firstShortRoad );
+ }
+ if( targetElem.type == ET_NORMALROAD && targetOtherIntOneErr != DEAD_END )
+ {
+ rAssert( lastShortRoad );
+ targetShortRoad.isOutRoad = false;
+ distToTargetOtherIntInOneDir += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+ }
+
+ firstShortRoad = NULL;
+ lastShortRoad = &sourceShortRoad;
+
+ // PATH: sourceRoad -> sourceRoad's destInt -> ... -> targetRoad's destInt -> targetRoad
+ sourceShortRoad.isOutRoad = true;
+ distToTargetOtherIntInOtherDir = FindDistToTargetInOneDirection( useMultiplier,
+ targetOtherInt, sourceDestInt, sourceSrcInt, NULL, elemsToTargetOtherIntInOtherDir,
+ firstShortRoad, lastShortRoad, targetOtherIntOtherErr ) +
+ distToDestInt + distFromTargetToOtherInt;
+ if( firstShortRoad && targetOtherIntOtherErr != DEAD_END )
+ {
+ distToTargetOtherIntInOtherDir += GetTraversalDistance( &sourceShortRoad, firstShortRoad );
+ }
+ if( targetElem.type == ET_NORMALROAD && targetOtherIntOtherErr != DEAD_END )
+ {
+ rAssert( lastShortRoad );
+ targetShortRoad.isOutRoad = false;
+ distToTargetOtherIntInOtherDir += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+ }
+ }
+ else
+ {
+ // I'm a small intersection with 2 adjacent neighbor intersections
+ // Visit both intersections on either sides of me...
+ rAssert( sourceElem.type == ET_INTERSECTION );
+
+ Intersection* sourceInt = (Intersection*) sourceElem.elem;
+ SwapArray<ShortestRoad>* shortestRoads = useMultiplier ?
+ &(sourceInt->mShortestRoadsToAdjacentIntersectionsWithMultiplier) :
+ &(sourceInt->mShortestRoadsToAdjacentIntersectionsNoMultiplier) ;
+
+ rAssert( shortestRoads->mUseSize == 2 );
+
+ // visit neighborB by feeding neighborA in as last intersection
+ Intersection* neighborA = NULL;
+ ShortestRoad* shortRoad = &((*shortestRoads)[0]);
+ if( shortRoad->isOutRoad )
+ {
+ neighborA = (Intersection*) shortRoad->road->GetDestinationIntersection();
+ }
+ else
+ {
+ neighborA = (Intersection*) shortRoad->road->GetSourceIntersection();
+ }
+
+ // now visit neighborA by feeding neighborB in as last intersection
+ Intersection* neighborB = NULL;
+ sourceInt->GetOtherIntersection( useMultiplier, neighborA, neighborB, shortRoad );
+
+ firstShortRoad = NULL;
+ lastShortRoad = NULL;
+
+ // PATH: sourceInt -> neighborB -> ... -> targetRoad's srcInt -> targetRoad
+ distToTargetIntInOneDir = FindDistToTargetInOneDirection( useMultiplier,
+ targetInt, sourceInt, neighborA, NULL, elemsToTargetIntInOneDir,
+ firstShortRoad, lastShortRoad, targetIntOneErr ) + distFromTargetToInt;
+ if( targetElem.type == ET_NORMALROAD && targetIntOneErr != DEAD_END )
+ {
+ if( lastShortRoad )
+ {
+ targetShortRoad.isOutRoad = true;
+ distToTargetIntInOneDir += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+ }
+
+
+ firstShortRoad = NULL;
+ lastShortRoad = NULL;
+
+ // PATH: sourceInt -> neighborA -> ... -> targetRoad's srcInt -> targetRoad
+ distToTargetIntInOtherDir = FindDistToTargetInOneDirection( useMultiplier,
+ targetInt, sourceInt, neighborB, NULL, elemsToTargetIntInOtherDir,
+ firstShortRoad, lastShortRoad, targetIntOtherErr ) + distFromTargetToInt;
+ if( targetElem.type == ET_NORMALROAD && targetIntOtherErr != DEAD_END )
+ {
+ if( lastShortRoad )
+ {
+ targetShortRoad.isOutRoad = true;
+ distToTargetIntInOtherDir += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+ }
+
+
+ // now do the other 2 alternatives...
+ if( targetOtherInt )
+ {
+ firstShortRoad = NULL;
+ lastShortRoad = NULL;
+
+ // PATH: sourceInt -> neighborB -> ... -> targetRoad's destInt -> targetRoad
+ distToTargetOtherIntInOneDir = FindDistToTargetInOneDirection( useMultiplier,
+ targetOtherInt, sourceInt, neighborA, NULL, elemsToTargetOtherIntInOneDir,
+ firstShortRoad, lastShortRoad, targetOtherIntOneErr ) + distFromTargetToOtherInt;
+ if( targetElem.type == ET_NORMALROAD && targetOtherIntOneErr != DEAD_END )
+ {
+ if( lastShortRoad )
+ {
+ targetShortRoad.isOutRoad = false;
+ distToTargetOtherIntInOneDir += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+ }
+
+
+ firstShortRoad = NULL;
+ lastShortRoad = NULL;
+
+ // PATH: sourceInt -> neighborA -> ... -> targetRoad's destInt -> targetRoad
+ distToTargetOtherIntInOtherDir = FindDistToTargetInOneDirection( useMultiplier,
+ targetOtherInt, sourceInt, neighborB, NULL, elemsToTargetOtherIntInOtherDir,
+ firstShortRoad, lastShortRoad, targetOtherIntOtherErr ) + distFromTargetToOtherInt;
+ if( targetElem.type == ET_NORMALROAD && targetOtherIntOtherErr != DEAD_END )
+ {
+ if( lastShortRoad )
+ {
+ targetShortRoad.isOutRoad = false;
+ distToTargetOtherIntInOtherDir += GetTraversalDistance( lastShortRoad, &targetShortRoad );
+ }
+ }
+
+ }
+ }
+
+ //
+ // One or all of these ways should make it to either a big intersection
+ // (where we decide whether or not the total cost to the target road
+ // is less in this direction than if we were to go in the other
+ // directions) or the target road itself (where we consider total dist
+ // to the target in this dir versus total dist to target in other dirs)
+ //
+ // shouldn't have found dead end in all directions!
+ rAssert( targetIntOneErr != DEAD_END ||
+ targetIntOtherErr != DEAD_END ||
+ targetOtherIntOneErr != DEAD_END ||
+ targetOtherIntOtherErr != DEAD_END );
+
+ SwapArray<DistErrMap> mappings;
+
+ HeapMgr()->PushHeap(GMA_TEMP);
+ mappings.Allocate( 4 );
+ HeapMgr()->PopHeap(GMA_TEMP);
+
+ mappings.mUseSize = 4;
+
+ mappings[0].dist = distToTargetIntInOneDir;
+ mappings[0].errVal = targetIntOneErr;
+ mappings[0].ID = 0;
+
+ mappings[1].dist = distToTargetIntInOtherDir;
+ mappings[1].errVal = targetIntOtherErr;
+ mappings[1].ID = 1;
+
+ mappings[2].dist = distToTargetOtherIntInOneDir;
+ mappings[2].errVal = targetOtherIntOneErr;
+ mappings[2].ID = 2;
+
+ mappings[3].dist = distToTargetOtherIntInOtherDir;
+ mappings[3].errVal = targetOtherIntOtherErr;
+ mappings[3].ID = 3;
+
+ int i;
+ // get rid of all the ones that never panned out
+ for( i=0; i<mappings.mUseSize; )
+ {
+ rAssert( mappings[i].errVal != STILL_LOOKING &&
+ mappings[i].errVal != UNEXPECTED );
+
+ if( mappings[i].errVal == DEAD_END )
+ {
+ mappings.Remove(i);
+ }
+ else
+ {
+ i++;
+ }
+ }
+ rAssert( mappings.mUseSize >= 1 );
+
+ // of whatever's left, we find the smallest dist...
+ int minIndex = -1;
+ float minDist = NEAR_INFINITY;
+ for( i=0; i<mappings.mUseSize; i++ )
+ {
+ if( mappings[i].dist < minDist )
+ {
+ minDist = mappings[i].dist;
+ minIndex = i;
+ }
+ }
+ rAssert( minIndex != -1 );
+ rAssert( minDist < NEAR_INFINITY );
+
+ ErrorValue errValToUse = mappings[minIndex].errVal;
+
+ totalDist += mappings[minIndex].dist;
+
+ switch( mappings[minIndex].ID )
+ {
+ case 0:
+ {
+ // copy over the roads
+ for( int i=0; i<elemsToTargetIntInOneDir.mUseSize; i++ )
+ {
+ elems.Add( elemsToTargetIntInOneDir[i] );
+ }
+ }
+ break;
+ case 1:
+ {
+ // copy over the roads
+ for( int i=0; i<elemsToTargetIntInOtherDir.mUseSize; i++ )
+ {
+ elems.Add( elemsToTargetIntInOtherDir[i] );
+ }
+ }
+ break;
+ case 2:
+ {
+ // copy over the roads
+ rAssert( elemsToTargetOtherIntInOneDir.IsSetUp() );
+ for( int i=0; i<elemsToTargetOtherIntInOneDir.mUseSize; i++ )
+ {
+ elems.Add( elemsToTargetOtherIntInOneDir[i] );
+ }
+ goingToTargetOther = true;
+ }
+ break;
+ case 3:
+ {
+ // copy over the roads
+ rAssert( elemsToTargetOtherIntInOtherDir.IsSetUp() );
+ for( int i=0; i<elemsToTargetOtherIntInOtherDir.mUseSize; i++ )
+ {
+ elems.Add( elemsToTargetOtherIntInOtherDir[i] );
+ }
+ goingToTargetOther = true;
+ }
+ break;
+ default:
+ {
+ rAssert( false );
+ }
+ break;
+ }
+
+ // clean out the temporary structures
+ elemsToTargetIntInOneDir.Clear();
+ elemsToTargetIntInOtherDir.Clear();
+ elemsToTargetOtherIntInOneDir.Clear();
+ elemsToTargetOtherIntInOtherDir.Clear();
+
+ // our choice in the error value to use (implies choice in direction of search)
+ // will take us to either the target or a big intersection, along the shortest
+ // path to the target
+ switch( errValToUse )
+ {
+ case FOUND_TARGET:
+ {
+ // We found targetInt before running into a big intersection.
+ // Just move on...
+ }
+ break;
+ case FOUND_BIGINTERSECTION:
+ {
+ rAssert( elems[elems.mUseSize-1].type == ET_INTERSECTION );
+
+ Intersection* bigInt = (Intersection*) elems[elems.mUseSize-1].elem;
+ rAssert( bigInt->mBigIntersection );
+
+ // pop it off the array, since TraverseRoads will add it again
+ // on first visit
+ elems.Remove( elems.mUseSize-1 );
+
+ // call TraverseRoads on it to fill the elems list with path elements
+ ErrorValue returnErr;
+ if( goingToTargetOther )
+ {
+ rAssert( targetOtherInt );
+ TraverseRoads( useMultiplier, targetOtherInt, bigInt, bigInt, elems, returnErr );
+ }
+ else
+ {
+ TraverseRoads( useMultiplier, targetInt, bigInt, bigInt, elems, returnErr );
+ }
+ rAssert( returnErr == FOUND_TARGET );
+ }
+ break;
+ case DEAD_END: // fall thru... the errVal we're using shouldn't lead to dead end
+ case STILL_LOOKING: // fall thru... only a tmp state for use before reaching end condition!
+ case UNEXPECTED: // fall thru
+ default:
+ {
+ // Shouldn't be here. We should have found either the target
+ // intersection (no more path finding necessary), or a big
+ // intersection.
+ rAssert( false );
+ }
+ break;
+ }
+ }
+
+ /////////////////////////////////////////////////////////////////////////////////
+ //
+ // Deal with adding the target element, if necessary...
+ //
+ // Given that source and target are not identical, at the very least,
+ // sourceElem (first thing we added) and targetInt (the last thing
+ // we should have found before getting to this point) exist in the list.
+ // But they could be the same element!
+ //
+#ifdef RAD_DEBUG
+ rAssert( elems.mUseSize >= 1 );
+ rAssert( elems[0] == sourceElem );
+ rAssert( elems[elems.mUseSize-1].type == ET_INTERSECTION );
+ if( goingToTargetOther )
+ {
+ rAssert( targetOtherInt );
+ rAssert( ((Intersection*)elems[elems.mUseSize-1].elem) == targetOtherInt );
+ }
+ else
+ {
+ rAssert( ((Intersection*)elems[elems.mUseSize-1].elem) == targetInt );
+ }
+#endif
+
+
+ // If targetElem is an intersection, then we're already done, because
+ // targetInt is already the last element in the list
+ if( targetElem.type == ET_INTERSECTION )
+ {
+ // Because of our earlier RETURN for when src == target, we know:
+ // - we have at least 2 elems, targetElem (this intersection) and source
+ rAssert( elems.mUseSize >= 2 );
+ rAssert( targetElem == elems[elems.mUseSize-1] );
+ rAssert( elems[elems.mUseSize-1].type == ET_INTERSECTION );
+ rAssert( elems[elems.mUseSize-2].type == ET_NORMALROAD );
+
+ // the intersection
+ Intersection* targetElemInt = (Intersection*)targetElem.elem;
+
+ // add dist from endpoint of last road to targetPos
+ rmt::Vector lastRoadEndPos, vec0, vec1, vec2, vec3;
+ Road* lastRoad = (Road*)elems[elems.mUseSize-2].elem;
+ RoadSegment* lastRoadSeg = NULL;
+ if( lastRoad->GetDestinationIntersection() == targetElemInt )
+ {
+ lastRoadSeg = lastRoad->GetRoadSegment( lastRoad->GetNumRoadSegments()-1 );
+
+ lastRoadSeg->GetCorner( 1, vec1 );
+ lastRoadSeg->GetCorner( 2, vec2 );
+ lastRoadEndPos = (vec1 + vec2) * 0.5f;
+ }
+ else
+ {
+ rAssert( lastRoad->GetSourceIntersection() == targetElemInt );
+
+ lastRoadSeg = lastRoad->GetRoadSegment( 0 );
+
+ lastRoadSeg->GetCorner( 0, vec0 );
+ lastRoadSeg->GetCorner( 3, vec3 );
+ lastRoadEndPos = (vec0 + vec3) * 0.5f;
+ }
+ totalDist += (lastRoadEndPos - targetPos).Magnitude(); // *** SQUARE ROOT! ***
+ }
+ else
+ {
+ // ok, target is a road... gotta add it
+ #ifdef RAD_DEBUG
+ rAssert( targetElem.type == ET_NORMALROAD );
+ if( ((Road*)(targetElem.elem))->GetShortCut() )
+ {
+ // we don't consider approaching target from its destination intersection
+ // when the target is on a shortcut road because a shortcut is one-way.
+ rAssert( targetOtherInt == NULL );
+ }
+ else
+ {
+ // if not a shortcut, of course we have to consider approaching the
+ // target from the target road's destination intersection
+ rAssert( targetOtherInt );
+ }
+ #endif
+
+ bool needToAddTargetRoad = true;
+ // well do some more asserting...
+ if( elems.mUseSize > 1 )
+ {
+ rAssert( elems[elems.mUseSize-2].type == ET_NORMALROAD );
+
+ rAssert( elems[elems.mUseSize-2] != targetElem );
+ /*
+ if( elems[elems.mUseSize-2] == targetElem )
+ {
+ // we already added the target road!
+
+ // TODO:
+ // Subtract away the added cost of traversing the target
+ // road... Shouldn't have to do any more adding to totalDist
+ // since we already added the traversal cost in the process
+ // of getting to the target road, and we already added the
+ // cost of the target's actual distance from the intersection
+ totalDist -= elems[elems.mUseSize-2].cost;
+
+ // Now just pop the redundant target intersection
+ elems.Remove( elems.mUseSize-1 );
+
+ needToAddTargetRoad = false;
+ }
+ */
+
+ }
+
+ if( needToAddTargetRoad )
+ {
+ // add the target road
+ elems.Add( targetElem );
+ }
+ }
+
+
+
+ // If source element is an intersection, we have to take into account
+ // the dist from sourcePos to the first road element...
+ if( sourceElem.type == ET_INTERSECTION )
+ {
+ // if source != target, source is an intersection, and target has been added,
+ // then we have at least 2 elems
+ rAssert( elems.mUseSize >= 2 );
+ rAssert( elems[1].type == ET_NORMALROAD );
+
+ Intersection* sourceElemInt = (Intersection*) sourceElem.elem;
+
+ // now add the dist from source to the second element (which should be a road)
+ Road* firstRoad = (Road*) elems[1].elem;
+
+ rmt::Vector firstRoadEndPos, vec0, vec1, vec2, vec3;
+ RoadSegment* firstRoadSeg = NULL;
+ if( firstRoad->GetDestinationIntersection() == sourceElemInt )
+ {
+ firstRoadSeg = firstRoad->GetRoadSegment( firstRoad->GetNumRoadSegments()-1 );
+
+ firstRoadSeg->GetCorner( 1, vec1 );
+ firstRoadSeg->GetCorner( 2, vec2 );
+ firstRoadEndPos = (vec1 + vec2) * 0.5f;
+ }
+ else
+ {
+ rAssert( firstRoad->GetSourceIntersection() == sourceElemInt );
+
+ firstRoadSeg = firstRoad->GetRoadSegment( 0 );
+
+ firstRoadSeg->GetCorner( 0, vec0 );
+ firstRoadSeg->GetCorner( 3, vec3 );
+ firstRoadEndPos = (vec0 + vec3) * 0.5f;
+ }
+ totalDist += (firstRoadEndPos - sourcePos).Magnitude(); // *** SQUARE ROOT! ***
+ }
+
+
+
+ /* NOTE: The cases we postulated below never happen... Thank god...
+ //
+ // Ok, damn.. targetElem is a road...
+ // we really want the last thing in the list to be targetRoad... but we
+ // have to be careful that we haven't added it already in the process
+ // of getting to target int...
+ //
+ // So if the second last elem in the list exists (had to have been a road)
+ // and was targetRoad, then trim off the last elem (target Int)
+ //
+ // If it wasn't... then the road needs to be added to the list after
+ // target Int...
+ //
+
+ // if only one item in there, then it was the sourceElem/target Int (they
+ // are one and the same), so add targetElem (which is an adjacent road)
+ if( elems.mUseSize == 1 )
+ {
+ // add in the target
+ elems.Add( targetElem );
+
+ // NOTE:
+ // Don't need to augment totalDist here since the
+ // distance from target to targetInt road has already
+ // been accounted for
+ }
+ else
+ {
+ // the second last elem must be a road (only the sequence
+ // "...-int-road-int-road-..." is allowed)
+ rAssert( elems[elems.mUseSize-2].type == ET_NORMALROAD );
+
+ rAssert( elems[elems.mUseSize-2] != targetElem );
+
+ ////////////////////////////////////////////////////////////
+ // NOTE:
+ // This case should NEVER happen! It means we chose the
+ // wrong target intersection to head to in our earlier
+ // distance comparison.
+ //
+ // If we already added the target elem in the process of
+ // getting to the target Int, then pop the target Int
+ // so the last thing in elems is targetElem
+ if( elems[elems.mUseSize-2] == targetElem )
+ {
+ // Here, there should be at least 3 elems in our list, since target
+ // is a road and source is not target and the last item added
+ // was an intersection and we maintain the int-road-int
+ // sequence
+ rAssert( elems.mUseSize >= 3 );
+
+ // since we found targetelem to be our second last elem,
+ // and since we just pathfinded to targetInt (or targetOtherInt)
+ // the third last should have been the targetOtherInt (or targetInt)
+ float distToAdd = 0.0f;
+ float distToSubtract = 0.0f;
+ if( goingToTargetOther )
+ {
+ rAssert( (Intersection*)(elems[elems.mUseSize-3].elem) == targetInt );
+ distToAdd = distFromTargetToInt;
+ distToSubtract = distFromTargetToOtherInt;
+ }
+ else
+ {
+ rAssert( (Intersection*)(elems[elems.mUseSize-3].elem) == targetOtherInt );
+ distToAdd = distFromTargetToOtherInt;
+ distToSubtract = distFromTargetToInt;
+ }
+
+ // take out the unnecessary intersection
+ elems.Remove( elems.mUseSize-1 );
+
+ // Need to adjust totalDist...
+ // So far totalDist has overcounted:
+ // A) distance from source to one target intersection a,
+ // B) plus the length of the target road element all the way to
+ // the other target intersection b,
+ // C) plus the distance from intersection b back to target roadT
+ //
+ // Now that we're removing the last element (the wrong target int)
+ // we must take away B and C and add the dist from target roadT to
+ totalDist -= ((Road*)targetElem.elem)->GetRoadLength();
+ totalDist -= distToSubtract;
+ totalDist += distToAdd;
+ }
+
+ ////////////////////////////////////////////////////////////
+ // NOTE:
+ // We dont' need to do this ELSE IF case at all!
+ // Our algorithm already ensures that this case doesn't happen
+ // where going along the longer target road is more beneficial.
+ //
+ // otherwise, check if the second last elem joins the same
+ // two intersections (target Int and some third last
+ // intersection element "otherInt") as targetElem
+ else if( elems.mUseSize >= 3 )
+ {
+ rAssert( elems[elems.mUseSize-3].type == ET_INTERSECTION );
+
+ Intersection* intA = (Intersection*) elems[elems.mUseSize-3].elem;
+ Intersection* intB = (Intersection*) elems[elems.mUseSize-1].elem;
+
+ // if the road at elems[usesize-2] was performing the same function
+ // as targetElem road in joining the same intersections,
+ // then replace it with targetElem road...
+ Intersection* testIntB = (goingToTargetOther)? targetInt : targetOtherInt;
+ Intersection* testIntA = (goingToTargetOther)? targetOtherInt : targetInt;
+
+ if( testIntB == intB && testIntA == intA )
+ {
+ // remove target Int
+ elems.Remove( elems.mUseSize-1 );
+
+ // remove the shortestroad before targetInt because
+ // we'll be replacing it with targetRoad
+ elems.Remove( elems.mUseSize-1 );
+ }
+ // add the target element
+ elems.Add( targetElem );
+
+ // we made changes recently that means we have to reexamine the logic
+ // of this case should we have re-enabled this case.
+ rAssert( false );
+ }
+ else
+ {
+ // still need to add target
+ elems.Add( targetElem );
+
+ // NOTE:
+ // Don't need to augment totalDist here since the
+ // distance from target to targetInt road has already
+ // been accounted for
+ }
+ }
+ */
+
+#ifdef RAD_DEBUG
+ // Do some checking
+ rAssert( elems.mUseSize >= 1 );
+ rAssert( elems[0].elem == sourceElem.elem );
+ rAssert( elems[elems.mUseSize-1].elem == targetElem.elem );
+ for( int i=1; i<elems.mUseSize; i++ )
+ {
+ PathElement* lastElem = &(elems[i-1]);
+ PathElement* currElem = &(elems[i]);
+
+ Intersection* in = NULL;
+ Road* rd = NULL;
+
+ if( currElem->type == ET_INTERSECTION )
+ {
+ rAssert( lastElem->type == RoadManager::ET_NORMALROAD );
+
+ in = (Intersection*) currElem->elem;
+ rd = (Road*) lastElem->elem;
+ }
+ else if( currElem->type == ET_NORMALROAD )
+ {
+ rAssert( lastElem->type == ET_INTERSECTION );
+
+ in = (Intersection*) lastElem->elem;
+ rd = (Road*) currElem->elem;
+ }
+
+ // find currRoad in lastElem
+ bool found = false;
+ unsigned int j;
+ for( j=0; j<in->GetNumRoadsIn(); j++ )
+ {
+ Road* inRoad = (Road*) in->GetRoadIn( j );
+ rAssert( inRoad );
+
+ if( inRoad == rd )
+ {
+ rAssert( (Intersection*) rd->GetDestinationIntersection() == in );
+ found = true;
+ break;
+ }
+ }
+ for( j=0; j<in->GetNumRoadsOut(); j++ )
+ {
+ Road* outRoad = (Road*) in->GetRoadOut( j );
+ rAssert( outRoad );
+
+ if( outRoad == rd )
+ {
+ rAssert( (Intersection*) rd->GetSourceIntersection() == in );
+ found = true;
+ break;
+ }
+ }
+ rAssert( found );
+ }
+#endif
+
+ return totalDist;
+}
+
+float RoadManager::GetTraversalDistance( ShortestRoad* fromRoad, ShortestRoad* toRoad )
+{
+ rAssert( fromRoad );
+ rAssert( toRoad );
+
+ rmt::Vector vec0, vec1, vec2, vec3, start, end;
+ const Intersection* traversedInt = NULL;
+ RoadSegment* fromSeg = NULL;
+ RoadSegment* toSeg = NULL;
+ if( fromRoad->isOutRoad )
+ {
+ // fromRoad is an OUT road at lastInt, so it's an IN road at currInt, so
+ // its last segment is at currInt
+
+ traversedInt = fromRoad->road->GetDestinationIntersection();
+
+ fromSeg = fromRoad->road->GetRoadSegment( fromRoad->road->GetNumRoadSegments()-1 );
+ fromSeg->GetCorner( 1, vec1 );
+ fromSeg->GetCorner( 2, vec2 );
+ start = (vec1+vec2) * 0.5f;
+ }
+ else
+ {
+ // fromRoad is an IN road at lastInt, so its an OUT road at currInt and therefore the
+ // first segment is at currInt
+
+ traversedInt = fromRoad->road->GetSourceIntersection();
+
+ fromSeg = fromRoad->road->GetRoadSegment( 0 );
+ fromSeg->GetCorner( 0, vec0 );
+ fromSeg->GetCorner( 3, vec3 );
+ start = (vec0+vec3) * 0.5f;
+ }
+
+ if( toRoad->isOutRoad )
+ {
+ // toRoad is an OUT road at currInt, so its first segment is at currInt
+
+ // make sure this is an OUT road belonging to the traversedInt (our currInt)
+ rAssert( toRoad->road->GetSourceIntersection() == traversedInt );
+
+ toSeg = toRoad->road->GetRoadSegment( 0 );
+ toSeg->GetCorner( 0, vec0 );
+ toSeg->GetCorner( 3, vec3 );
+ end = (vec0+vec3) * 0.5f;
+ }
+ else
+ {
+ // toRoad is an IN road at currInt, so its last segment is at currInt
+
+ // make sure this is an IN road belonging to the traversedInt (our currInt)
+ rAssert( toRoad->road->GetDestinationIntersection() == traversedInt );
+
+ toSeg = toRoad->road->GetRoadSegment( toRoad->road->GetNumRoadSegments()-1 );
+ toSeg->GetCorner( 1, vec1 );
+ toSeg->GetCorner( 2, vec2 );
+ end = (vec1+vec2) * 0.5f;
+ }
+
+ // now the traversal distance can be either obtained more accurately
+ // by us building a spline... or just by linear straight line dist..
+ // let's try the linear dist first.
+ float traversalDist = (start - end).Length(); // *** SQUARE ROOT! ***
+
+ // If our from road is the same as our to road, we're being foolish...
+ // so we penalize the request by augmenting the distance by the
+ // intersection's radius...
+ if( fromRoad->road == toRoad->road )
+ {
+ traversalDist += traversedInt->GetRadius();
+ }
+
+ return traversalDist;
+}
+
+
+//
+// Follows current intersection in the given direction till we reach
+// a big intersection, where we ask how far it is to get to the target intersection.
+// Returns this distance.
+//
+float RoadManager::FindDistToTargetInOneDirection(
+ bool useMultiplier,
+ Intersection* targetInt,
+ Intersection* currInt,
+ Intersection* lastInt,
+ ShortestRoad* shortestRoadFromLastInt,
+ SwapArray<PathElement>& elems,
+ ShortestRoad*& firstShortRoad, // needed for traversal dist from src road to srcInt
+ ShortestRoad*& lastShortRoad, // needed for traversal dist from targetInt to target road
+ ErrorValue& errVal )
+{
+ rAssert( targetInt );
+ rAssert( currInt );
+ rAssert( lastInt );
+ rAssert( elems.IsSetUp() );
+
+ // add current intersection to list
+ PathElement intElem;
+ intElem.type = ET_INTERSECTION;
+ intElem.elem = currInt;
+ elems.Add( intElem );
+
+ float cost = 0.0f;
+
+ // found target
+ if( targetInt == currInt )
+ {
+ errVal = FOUND_TARGET;
+ return cost;
+ }
+ // Found "Big" Intersection
+ if( currInt->mBigIntersection )
+ {
+ NodeData* nodeData = useMultiplier ?
+ &(currInt->mBigIntersection->routesWithMultiplier[ targetInt->mIndex ]) :
+ &(currInt->mBigIntersection->routesNoMultiplier[ targetInt->mIndex ]) ;
+
+ errVal = FOUND_BIGINTERSECTION;
+
+ // First add the total dist from this BigInt to target intersection
+ cost = nodeData->dist;
+
+ // Now if there was a previous road...
+ // Compute the traversal cost through the currInt, which is the
+ // distance from the end of the shortest road from lastInt to the
+ // start of the shortest road to destInt (stored in nodeData)
+ if( shortestRoadFromLastInt )
+ {
+ ShortestRoad* fromRoad = shortestRoadFromLastInt;
+ ShortestRoad* toRoad = nodeData->roadToIn;
+ cost += GetTraversalDistance( fromRoad, toRoad );
+ }
+
+ // update the first and last shortroad data..
+ if( firstShortRoad == NULL )
+ {
+ firstShortRoad = nodeData->roadToIn;
+ }
+ lastShortRoad = nodeData->roadJustBeforeIn;
+
+ return cost;
+ }
+ // Found "linear" Intersection
+ else
+ {
+ // Last intersection becomes current, current becomes last
+ ShortestRoad* shortRoad = NULL;
+ Intersection* nextInt = NULL;
+
+ // given last int, get the nextInt and the shortestRoad to nextInt
+ currInt->GetOtherIntersection( useMultiplier, lastInt, nextInt, shortRoad );
+ if( nextInt == NULL )
+ {
+ // if deadend
+ errVal = DEAD_END;
+ return NEAR_INFINITY;
+ }
+
+ lastInt = currInt;
+ currInt = nextInt;
+
+ // add road to list
+ PathElement roadElem;
+ roadElem.type = ET_NORMALROAD;
+ roadElem.elem = shortRoad->road;
+ elems.Add( roadElem );
+
+ errVal = STILL_LOOKING;
+
+ // the cost begins with the cost of the road to nextInt
+ // and, if there was a previous road, is augmented by the
+ // traversal cost through currInt, from end of shortestRoadToLastInt
+ // to start of shortestRoad to nextInt)
+ //
+ cost = shortRoad->cost;
+ if( shortestRoadFromLastInt )
+ {
+ ShortestRoad* fromRoad = shortestRoadFromLastInt;
+ ShortestRoad* toRoad = shortRoad;
+ cost += GetTraversalDistance( fromRoad, toRoad );
+ }
+
+ // update the first and last shortroad data..
+ if( firstShortRoad == NULL )
+ {
+ firstShortRoad = shortRoad;
+ }
+ lastShortRoad = shortRoad;
+
+ return cost + FindDistToTargetInOneDirection( useMultiplier,
+ targetInt, currInt, lastInt, shortRoad, elems,
+ firstShortRoad, lastShortRoad, errVal );
+ }
+
+ // shouldn't be here
+ rAssert( false );
+ errVal = UNEXPECTED;
+ return NEAR_INFINITY;
+}
+
+
+void RoadManager::TraverseRoads(
+ bool useMultiplier,
+ Intersection* targetInt,
+ Intersection* currInt,
+ Intersection* lastInt,
+ SwapArray<PathElement>& elems,
+ ErrorValue& errVal )
+{
+ rAssert( targetInt );
+ rAssert( currInt );
+ rAssert( lastInt );
+ rAssert( elems.IsSetUp() );
+
+ // add current intersection to list
+ PathElement intElem;
+ intElem.type = ET_INTERSECTION;
+ intElem.elem = currInt;
+ elems.Add( intElem );
+
+ // found target
+ if( targetInt == currInt )
+ {
+ errVal = FOUND_TARGET;
+ return;
+ }
+
+ ShortestRoad* shortRoad = NULL;
+
+ // Found "Big" Intersection
+ if( currInt->mBigIntersection )
+ {
+ SwapArray<NodeData>* routes = useMultiplier ?
+ &(currInt->mBigIntersection->routesWithMultiplier) :
+ &(currInt->mBigIntersection->routesNoMultiplier) ;
+
+ // find the adjacent intersection that will take us to the target
+ // & the shortest road that will get us there
+ Intersection* adjacentInt = (*routes)[ targetInt->mIndex ].destIn;
+ shortRoad = (*routes)[ targetInt->mIndex ].roadToIn;
+
+ // Move current Int...
+ Intersection* tmp = currInt;
+ currInt = adjacentInt;
+ lastInt = tmp;
+
+ errVal = FOUND_BIGINTERSECTION;
+ }
+ else //Linear Intersection
+ {
+ // Last intersection becomes current, current becomes last
+ Intersection* nextInt = NULL;
+
+ // given last int
+ currInt->GetOtherIntersection( useMultiplier, lastInt, nextInt, shortRoad );
+ if( nextInt == NULL )
+ {
+ // DEAD END??? Can't be... we only call TraverseRoads when
+ // we are SURE it will take us to the target
+ rAssert( false );
+ errVal = DEAD_END;
+ return;
+ }
+
+ lastInt = currInt;
+ currInt = nextInt;
+
+ errVal = STILL_LOOKING;
+
+ }
+
+ rAssert( shortRoad );
+ rAssert( currInt );
+ rAssert( lastInt );
+ rAssert( errVal == STILL_LOOKING || errVal == FOUND_BIGINTERSECTION );
+
+ // add road to list
+ PathElement roadElem;
+ roadElem.type = ET_NORMALROAD;
+ roadElem.elem = shortRoad->road;
+ elems.Add( roadElem );
+
+ return TraverseRoads( useMultiplier, targetInt, currInt, lastInt, elems, errVal );
+
+}
+
+Intersection* RoadManager::FindIntersection( const char* name )
+{
+ return FindIntersection( tEntity::MakeUID( name ) );
+}
+
+Intersection* RoadManager::FindIntersection( tUID name )
+{
+ unsigned int i;
+ for ( i = 0; i < mNumIntersectionsUsed; ++i )
+ {
+ if ( mIntersections[i].GetNameUID() == name )
+ {
+ //Found it!
+ return &(mIntersections[i]);
+ }
+ }
+
+ return NULL;
+}
+
+Intersection* RoadManager::FindIntersection( rmt::Vector& point )
+{
+ unsigned int i;
+ for ( i = 0; i < mNumIntersectionsUsed; ++i )
+ {
+ if ( (mIntersections[i]).IsPointInIntersection( point ) )
+ {
+ return &(mIntersections[i]);
+ }
+ }
+
+ return NULL;
+}
+
+Intersection* RoadManager::FindIntersection( int iIndex )
+{
+ return &(mIntersections[iIndex]);
+}
+
+
+
+
+bool RoadManager::FindRoad( const rmt::Vector& point,
+ const Road** ppRoad,
+ RoadSegment** ppOutRoadSegment,
+ int& segmentIndex,
+ float& in,
+ float& lateral,
+ bool considerShortCuts ) const
+{
+ unsigned int i;
+ for ( i = 0; i < mNumRoadsUsed; i++ )
+ {
+ if( !considerShortCuts && mRoads[i].GetShortCut() )
+ {
+ continue;
+ }
+
+ segmentIndex = mRoads[i].GetRoadSegmentAtPoint( point, ppOutRoadSegment, in, lateral, 0 );
+ if ( segmentIndex >= 0 )
+ {
+ // We found our road.
+ //
+ *ppRoad = &(mRoads[i]);
+
+ return true;
+ break;
+ }
+ }
+ *ppRoad = 0;
+
+ return false;
+}
+
+
+RoadSegmentData* RoadManager::FindRoadSegmentData( const char* name )
+{
+ tUID nameUID = tEntity::MakeUID( name );
+ return FindRoadSegmentData( nameUID );
+}
+
+RoadSegmentData* RoadManager::FindRoadSegmentData( tUID name )
+{
+ unsigned int i;
+ for ( i = 0; i < mNumRoadSegmentDataUsed; ++i )
+ {
+ if ( mRoadSegmentData[i].GetNameUID() == name )
+ {
+ //This is it!
+ return &(mRoadSegmentData[i]);
+ }
+ }
+
+ return NULL;
+}
+
+void RoadManager::AddRoad( Road* pRoad )
+{
+ rAssert( mNumRoadsUsed < mNumRoads );
+
+ //Make sure this is the current road...
+ rAssert( pRoad == &(mRoads[mNumRoadsUsed]) );
+
+ ++mNumRoadsUsed;
+}
+
+void RoadManager::AddIntersection( Intersection* pIntersection )
+{
+ rAssert( mNumIntersectionsUsed < mNumIntersections );
+
+ //Make sure this is the current intersection...
+ rAssert( pIntersection == &(mIntersections[mNumIntersectionsUsed]) );
+
+ ++(mNumIntersectionsUsed);
+}
+
+void RoadManager::AddRoadSegmentData( RoadSegmentData* pRoadSegmentData )
+{
+ rAssert( mNumRoadSegmentDataUsed < mNumRoadSegmentData );
+
+ //Make sure this is the current intersection...
+ rAssert( pRoadSegmentData == &(mRoadSegmentData[mNumRoadSegmentDataUsed]) );
+
+ ++(mNumRoadSegmentDataUsed);
+}
+
+void RoadManager::AddRoadSegment( RoadSegment* pRoadSegment )
+{
+ rAssert( mNumRoadSegmentsUsed < mNumRoadSegments);
+
+ //Make sure this is the current intersection...
+ //rAssert( pRoadSegment == &(mRoadSegments[mNumRoadSegmentsUsed]) );
+ rAssert( pRoadSegment == mRoadSegments[mNumRoadSegmentsUsed] );
+
+ ++(mNumRoadSegmentsUsed);
+}
+
+
+// search roads and intersections for whichever's closest, given a position
+void RoadManager::FindClosestPathElement
+(
+ const rmt::Vector& pos, // IN: search center
+ float searchRadius, // IN: search radius
+ PathfindingOptions options, // IN: search options
+
+ PathElement& closestElem, // OUT: closest element (road or intersection)
+ RoadSegment*& closestRoadSeg, // OUT: if closest element is road, this is closest seg
+ float& closestRoadSegT, // OUT: if closest element is road, this is segment t value
+ float& closestRoadT // OUT: if closest element is road, this is road's t value
+)
+{
+ rAssert( 0 <= options && options <= NUM_POS );
+
+ // must search for SOMETHING... default to all
+ if( !(options & PO_SEARCH_ROADS) && !(options & PO_SEARCH_INTERSECTIONS) )
+ {
+ options |= PO_SEARCH_ROADS | PO_SEARCH_INTERSECTIONS;
+ }
+
+ // APPROACH
+ // ========
+ // Search all roads in given radius to find:
+ // the closest road segment, and
+ // the distance to this road segment
+ //
+ // Search all intersections in given radius to find:
+ // the closest intersection, and
+ // the distance to this intersection
+ //
+ // If distance to closest road segment <= distance to closest intersection
+ // use the road segment
+ // else
+ // use the intersection
+ //
+
+ // find closets road segment
+ RoadSegment* closestSeg = NULL;
+ float distSqrToClosestSeg = 100000000.0f;
+
+ if( options & PO_SEARCH_ROADS )
+ {
+ if( options & PO_SEARCH_SHORTCUTS )
+ {
+ GetIntersectManager()->FindClosestAnyRoad(
+ pos,
+ searchRadius,
+ closestSeg,
+ distSqrToClosestSeg );
+ }
+ else
+ {
+ GetIntersectManager()->FindClosestRoad(
+ pos,
+ searchRadius,
+ closestSeg,
+ distSqrToClosestSeg );
+ }
+ rAssert( closestSeg );
+ }
+
+
+ // find closest intersection
+ Intersection* closestInt = NULL;
+ float distSqrToClosestInt = 100000000.0f;
+
+ if( options & PO_SEARCH_INTERSECTIONS )
+ {
+ for( unsigned int i = 0; i < mNumIntersectionsUsed; ++i )
+ {
+ rmt::Vector intPos;
+ mIntersections[i].GetLocation( intPos );
+
+ float distSqr = (intPos - pos).MagnitudeSqr();
+ if( distSqr < distSqrToClosestInt )
+ {
+ closestInt = &mIntersections[i];
+ distSqrToClosestInt = distSqr;
+ }
+ }
+
+ rAssert( closestInt );
+ }
+
+ // Populate return values
+ if( distSqrToClosestSeg <= distSqrToClosestInt )
+ {
+ rAssert( closestSeg );
+
+ closestElem.type = ET_NORMALROAD;
+ closestElem.elem = closestSeg->GetRoad();
+ closestRoadSeg = closestSeg;
+ closestRoadSegT = DetermineSegmentT( pos, closestRoadSeg );
+ closestRoadT = DetermineRoadT( closestRoadSeg, closestRoadSegT );
+ }
+ else
+ {
+ rAssert( closestInt );
+
+ closestElem.type = ET_INTERSECTION;
+ closestElem.elem = closestInt;
+ closestRoadSeg = NULL;
+ closestRoadSegT = 0.0f;
+ closestRoadT = 0.0f;
+ }
+}
+
+
+
+//******************************************************************************
+//
+// Private Member Functions
+//
+//******************************************************************************
diff --git a/game/code/roads/roadmanager.h b/game/code/roads/roadmanager.h
new file mode 100644
index 0000000..a5b6a83
--- /dev/null
+++ b/game/code/roads/roadmanager.h
@@ -0,0 +1,318 @@
+//=============================================================================
+// Copyright (C) 2002 Radical Entertainment Ltd. All rights reserved.
+//
+// File: roadmanager.h
+//
+// Description: Blahblahblah
+//
+// History: 26/06/2002 + Created -- Cary Brisebois (based on TBJ's work)
+//
+//=============================================================================
+
+#ifndef ROADMANAGER_H
+#define ROADMANAGER_H
+
+//========================================
+// Nested Includes
+//========================================
+#include <render/culling/swaparray.h>
+
+//========================================
+// Forward References
+//========================================
+class Road;
+class Intersection;
+class RoadSegmentData;
+class RoadSegment;
+class Lane;
+
+class RoadRenderTest;
+
+static const float NEAR_INFINITY = 100000.0f;
+
+//=============================================================================
+//
+// Synopsis: Blahblahblah
+//
+//=============================================================================
+
+class RoadManager
+{
+public:
+ enum { STARTUP = false, SHUTDOWN = true };
+
+ static const float AGAINST_TRAFFIC_COST_MULTIPLIER;
+
+ struct ShortestRoad
+ {
+ Road* road;
+ bool isOutRoad;
+ float cost;
+ };
+ struct NodeData
+ {
+ Intersection* destIn;
+ ShortestRoad* roadToIn;
+ ShortestRoad* roadJustBeforeIn;
+ float dist; // total distance to the destination intersection
+ };
+ struct BigIntersection
+ {
+ Intersection* in;
+ SwapArray<NodeData> routesWithMultiplier;
+ SwapArray<NodeData> routesNoMultiplier;
+ };
+ enum ElementType
+ {
+ ET_INTERSECTION, // Intersection*
+ ET_NORMALROAD // Road*
+ };
+ struct PathElement
+ {
+ ElementType type;
+ void* elem;
+ bool operator==( const PathElement& right ) const
+ {
+ return(elem==right.elem);
+ }
+ bool operator!=( const PathElement& right ) const
+ {
+ return(elem!=right.elem);
+ }
+ };
+
+
+ static RoadManager* GetInstance();
+ static void Destroy();
+
+ //---------------Initialization
+ void Init( bool shutdown );
+
+ void InitializeRoadMemory( unsigned int numRoads );
+ void InitializeIntersectionMemory( unsigned int numIntersections );
+ void InitializeRoadSegmentDataMemory( unsigned int numSegments );
+ void InitializeRoadSegmentMemory( unsigned int numRoadSegments );
+
+ void DumpRoadSegmentDataMemory();
+
+ Road* GetFreeRoadMemory( );
+ Intersection* GetFreeIntersectionMemory( );
+ RoadSegmentData* GetFreeRoadSegmentDataMemory( );
+ RoadSegment* GetFreeRoadSegmentMemory( );
+
+ void AddRoad( Road* pRoad );
+ void AddIntersection( Intersection* pIntersection );
+ void AddRoadSegmentData( RoadSegmentData* pRoadSegmentData );
+ void AddRoadSegment( RoadSegment* pRoadSegment );
+
+ int GetMaxPathElements();
+
+ void CreateRoadNetwork( void );
+
+
+ //---------------Data Aquisition
+ Intersection* FindIntersection( const char* name );
+ Intersection* FindIntersection( tUID name );
+ Intersection* FindIntersection( rmt::Vector& point );
+
+ Intersection* FindIntersection( int iIndex );
+
+ int GetNumIntersectionsUsed( );
+ unsigned int GetNumRoads( );
+
+ bool FindRoad( const rmt::Vector& point,
+ const Road** ppRoad,
+ RoadSegment** ppOutRoadSegment,
+ int& segmentIndex,
+ float& in,
+ float& lateral,
+ bool considerShortCuts=true ) const;
+
+ static bool FindClosestPointOnRoad( const Road* pRoad,
+ const rmt::Vector& pos,
+ rmt::Vector& closestPos,
+ float& closestDist,
+ int& segmentIndex );
+
+ static float DetermineRoadT( RoadSegment* seg, float segT );
+ static float DetermineSegmentT( const rmt::Vector& pos, RoadSegment* seg );
+
+
+
+ RoadSegmentData* FindRoadSegmentData( const char* name );
+ RoadSegmentData* FindRoadSegmentData( tUID name );
+
+ RoadRenderTest* GetRoadRenderTest();
+
+ // fully pathfind from source to target, returning float distance
+ float FindPathElementsBetween(
+ bool useMultiplier, // IN: direction-biased?
+ PathElement& sourceElem, // IN: starting element
+ float sourceT, // IN: used only if sourceElem is a road
+ const rmt::Vector& sourcePos, // IN: used only if sourceElem is an intersection
+ PathElement& targetElem, // IN: terminating element
+ float targetT, // IN: used only if targetElem is a road
+ const rmt::Vector& targetPos, // IN: used only if targetElem is an intersection
+ SwapArray<PathElement>& elems ); // OUT: accumulate roads or intersections
+
+ enum PathfindingOption
+ {
+ PO_SEARCH_SHORTCUTS = 1 << 0, // whether or not to take into account shortcut roads
+ PO_SEARCH_ROADS = 1 << 1, // whether or not to search for roads
+ PO_SEARCH_INTERSECTIONS = 1 << 2, // whether or not to search for intersections
+
+ NUM_POS = ( PO_SEARCH_SHORTCUTS |
+ PO_SEARCH_ROADS |
+ PO_SEARCH_INTERSECTIONS )
+ };
+
+ typedef char PathfindingOptions;
+
+ // search roads and intersections for whichever's closest, given a position
+ void FindClosestPathElement(
+ const rmt::Vector& pos, // IN: search center
+ float searchRadius, // IN: search radius
+ PathfindingOptions options, // IN: search options
+ PathElement& closestElem, // OUT: closest element (road or intersection)
+ RoadSegment*& closestRoadSeg, // OUT: if closest element is road, this is closest seg
+ float& closestRoadSegT, // OUT: if closest element is road, this is segment t value
+ float& closestRoadT ); // OUT: if closest element is road, this is road's t value
+
+ enum ErrorValue
+ {
+ DEAD_END,
+ STILL_LOOKING,
+ FOUND_TARGET,
+ FOUND_BIGINTERSECTION,
+ UNEXPECTED
+ };
+ struct DistErrMap
+ {
+ int ID;
+ ErrorValue errVal;
+ float dist;
+ };
+
+ float FindDistToTargetInOneDirection(
+ bool useMultiplier,
+ Intersection* targetInt,
+ Intersection* currInt,
+ Intersection* lastInt,
+ ShortestRoad* shortestRoadFromLastInt,
+ SwapArray<PathElement>& elems,
+ ShortestRoad*& firstShortRoad, // needed for traversal dist from src road to srcInt
+ ShortestRoad*& lastShortRoad, // needed for traversal dist from targetInt to target road
+ ErrorValue& errVal );
+
+ void TraverseRoads(
+ bool useMultiplier,
+ Intersection* targetInt,
+ Intersection* currInt,
+ Intersection* lastInt,
+ SwapArray<PathElement>& elems,
+ ErrorValue& errVal );
+
+
+
+private:
+
+ static RoadManager* mInstance;
+
+ Road* mRoads;
+ unsigned int mNumRoads;
+ unsigned int mNumRoadsUsed;
+
+ Intersection* mIntersections;
+ unsigned int mNumIntersections;
+ unsigned int mNumIntersectionsUsed;
+
+ struct DijkstraNode
+ {
+ struct AdjacencyData
+ {
+ DijkstraNode* adjacentNode;
+ ShortestRoad* shortestRoadThere;
+ };
+
+ Intersection* in;
+ float distToSrc;
+ DijkstraNode* predecessor;
+ ShortestRoad* shortestRoadFromPred;
+ bool addedToS;
+ SwapArray<AdjacencyData> adjacents;
+
+ DijkstraNode()
+ {
+ in = NULL;
+
+ distToSrc = NEAR_INFINITY;
+ predecessor = NULL;
+ shortestRoadFromPred = NULL;
+ addedToS = false;
+ }
+
+ ~DijkstraNode()
+ {
+ in = NULL;
+ adjacents.Clear();
+
+ distToSrc = NEAR_INFINITY;
+ predecessor = NULL;
+ shortestRoadFromPred = NULL;
+ addedToS = false;
+ }
+
+ void Init( float dist, DijkstraNode* pred )
+ {
+ distToSrc = dist;
+ predecessor = pred;
+
+ shortestRoadFromPred = NULL;
+ addedToS = false;
+ }
+ };
+ SwapArray<BigIntersection*> mBigIntersections;
+ void PopulateConnectivityData( bool useMultiplier, Intersection* intersections, int numInts );
+ void VisitAll( SwapArray<DijkstraNode>& nodes );
+
+ RoadSegmentData* mRoadSegmentData;
+ unsigned int mNumRoadSegmentData;
+ unsigned int mNumRoadSegmentDataUsed;
+
+ RoadSegment** mRoadSegments; // dynamically allocated array of pointers to RoadSegments
+ unsigned int mNumRoadSegments;
+ unsigned int mNumRoadSegmentsUsed;
+ /*
+ TransformRoadSegment** mRoadSegments;
+ unsigned int mNumRoadSegments;
+ unsigned int mNumRoadSegmentsUsed;
+ */
+
+ RoadRenderTest* mRender;
+
+ float GetTraversalDistance( ShortestRoad* fromRoad, ShortestRoad* toRoad );
+
+
+ //Singleton
+ RoadManager();
+ virtual ~RoadManager();
+
+ //Prevent wasteful constructor creation.
+ RoadManager( const RoadManager& roadmanager );
+ RoadManager& operator=( const RoadManager& roadmanager );
+};
+
+inline unsigned int RoadManager::GetNumRoads()
+{
+ return mNumRoadsUsed;
+}
+inline int RoadManager::GetNumIntersectionsUsed()
+{
+ return mNumIntersectionsUsed;
+}
+inline RoadRenderTest* RoadManager::GetRoadRenderTest()
+{
+ return mRender;
+}
+
+#endif //ROADMANAGER_H
diff --git a/game/code/roads/roadrender.cpp b/game/code/roads/roadrender.cpp
new file mode 100644
index 0000000..c7c5ce5
--- /dev/null
+++ b/game/code/roads/roadrender.cpp
@@ -0,0 +1,401 @@
+#include <roads/intersection.h>
+#include <roads/road.h>
+#include <roads/roadsegment.h>
+#include <roads/lane.h>
+#include <p3d/camera.hpp>
+#include <p3d/shader.hpp>
+#include <p3d/utility.hpp>
+#include <p3d/view.hpp>
+
+
+//#include "../../debugtools/debuginfo.h"
+
+// TODO: remove ugly hack for shader.
+//
+#include <roads/roadmanager.h>
+
+tShader* gpShader = NULL; //new tShader("simple");
+
+tShader* GetShader()
+{
+ if ( !gpShader )
+ {
+ gpShader = new tShader("simple");
+ }
+
+ return gpShader;
+}
+
+
+void DrawCircle( float radius, const rmt::Vector& center, int subDivisions, const tColour& colour )
+{
+ rmt::Vector a,b;
+ int i;
+ int n = subDivisions;
+ float r = radius;
+ pddiPrimStream* stream = p3d::pddi->BeginPrims( GetShader()->GetShader(), PDDI_PRIM_LINES, PDDI_V_C, n * 2 );
+ if ( stream )
+ {
+ for( i = 0; i < n; i++ )
+ {
+ a.x = center.x + r * rmt::Cos( i * rmt::PI_2 / n );
+ a.y = center.y;
+ a.z = center.z + r * rmt::Sin( i * rmt::PI_2 / n );
+ b.x = center.x + r * rmt::Cos( ( i + 1 ) * rmt::PI_2 / n );
+ b.y = center.y;
+ b.z = center.z + r * rmt::Sin( ( i + 1 ) * rmt::PI_2 / n );
+
+ stream->Vertex( ( ( pddiVector* )( &( a ) ) ), colour );
+ stream->Vertex( ( ( pddiVector* )( &( b ) ) ), colour );
+ }
+ }
+ p3d::pddi->EndPrims( stream );
+
+}
+
+void DrawBox( rmt::Box3D& box, const tColour& colour )
+{
+ // Render bounding box.
+ //
+ pddiPrimStream* stream = p3d::pddi->BeginPrims( GetShader()->GetShader(), PDDI_PRIM_LINES, PDDI_V_C, 2 );
+ if ( stream )
+ {
+ rmt::Vector start;
+ rmt::Vector end;
+ start.y = 0.0f;
+ end.y = 0.0f;
+
+ start.x = box.high.x;
+ start.z = box.high.z;
+ end.x = box.high.x;
+ end.z = box.low.z;
+ stream->Vertex( ( ( pddiVector* )( &( start ) ) ), colour );
+ stream->Vertex( ( ( pddiVector* )( &( end ) ) ), colour );
+
+ start = end;
+ end.x = box.low.x;
+ end.z = box.low.z;
+ stream->Vertex( ( ( pddiVector* )( &( start ) ) ), colour );
+ stream->Vertex( ( ( pddiVector* )( &( end ) ) ), colour );
+
+ start = end;
+ end.x = box.low.x;
+ end.z = box.high.z;
+ stream->Vertex( ( ( pddiVector* )( &( start ) ) ), colour );
+ stream->Vertex( ( ( pddiVector* )( &( end ) ) ), colour );
+
+ start = end;
+ end.x = box.high.x;
+ end.z = box.high.z;
+
+ stream->Vertex( ( ( pddiVector* )( &( start ) ) ), colour );
+ stream->Vertex( ( ( pddiVector* )( &( end ) ) ), colour );
+ }
+ p3d::pddi->EndPrims( stream );
+}
+
+
+/*
+==============================================================================
+Intersection::Render
+==============================================================================
+Description: Draw a circle representing the Intersection.
+ Call the road Render routine for each road.
+
+Parameters: ( void )
+
+Return: void
+
+=============================================================================
+*/
+void Intersection::Render( void ) const
+{
+ // Draw a circle representing the Intersection.
+ //
+ tColour intersectionColour;
+ if( mType == Intersection::N_WAY )
+ {
+ intersectionColour.Set( 0, 255, 0 );
+ }
+ else
+ {
+ intersectionColour.Set( 0, 0, 255 );
+ }
+
+ rmt::Vector center;
+ GetLocation( center );
+
+ if ( p3d::context->GetView()->GetCamera()->SphereVisible( center, 15.0f ) )
+ {
+ center.y += 1.0f;
+ DrawCircle( GetRadius( ), center, 8, intersectionColour );
+ }
+
+ unsigned int i = 0;
+ for ( i = 0; i < this->mnRoadsIn; i++ )
+ {
+ if ( mRoadListIn[ i ] )
+ {
+ mRoadListIn[ i ]->Render( tColour(255, 255, 255) );
+ }
+ }
+ for ( i = 0; i < this->mnRoadsOut; i++ )
+ {
+ if ( mRoadListOut[ i ] )
+ {
+ mRoadListOut[ i ]->Render( tColour(0, 0, 0) );
+ }
+ }
+}
+/*
+==============================================================================
+Road::Render
+==============================================================================
+Description: Draw a line along the inside edge of the road.
+ Call render for each roadsegment.
+ Call Render for each Lane.
+
+Parameters: ( const tColour& colour )
+
+Return: void
+
+=============================================================================
+*/
+void Road::Render( const tColour& colour )
+{
+ static tColour roadColour = colour;
+
+ if ( p3d::context->GetView()->GetCamera()->SphereVisible( mSphere.centre, mSphere.radius ) )
+ {
+ static bool bDrawRoads = true;
+ if ( bDrawRoads )
+ {
+ rmt::Vector start;
+ this->GetDestinationIntersection( )->GetLocation( start );
+ rmt::Vector end;
+ this->GetSourceIntersection( )->GetLocation( end );
+
+#ifdef TOOLS
+ DrawCircle( GetDestinationIntersection( )->GetRadius( ), start, 8, colour );
+ DrawCircle( GetSourceIntersection( )->GetRadius( ), end, 8, colour );
+
+#endif
+ // Render the roads.
+ //
+
+ // Draw a line from the start to the end.
+ //
+ pddiPrimStream* stream = p3d::pddi->BeginPrims( GetShader()->GetShader(), PDDI_PRIM_LINES, PDDI_V_C, 2 );
+ if ( stream )
+ {
+ stream->Vertex( ( ( pddiVector* )( &( start ) ) ), roadColour );
+ stream->Vertex( ( ( pddiVector* )( &( end ) ) ), roadColour );
+ }
+ p3d::pddi->EndPrims( stream );
+ }
+ static bool bDrawRoadBBox = false;
+// if ( BEGIN_DEBUGINFO_SECTION( "Draw Road BBox" ) )
+// {
+// ::DrawBox( mBox, roadColour );
+// }
+// END_DEBUGINFO_SECTION( "Draw Road BBox" );
+ static bool bDrawRoadBSphere = false;
+// if ( BEGIN_DEBUGINFO_SECTION( "Draw Road BSphere" ) )
+// {
+// // Render the roads bounding sphere.
+// //
+// ::DrawCircle( mSphere.radius, mSphere.centre, 8, roadColour );
+// }
+// END_DEBUGINFO_SECTION( "Draw Road BSphere" );
+ // Render the road Segments.
+ //
+ static bool bDrawRoadSegments = true;
+ if ( bDrawRoadSegments )
+ {
+ // Iterate through the segments.
+ //
+ unsigned int i = 0;
+
+ unsigned int colourStep = 255 / mnRoadSegments;
+
+ for ( i = 0; i < mnRoadSegments; i++ )
+ {
+ tColour colour = roadColour;
+ colour.SetRed( colourStep * i );
+ colour.SetGreen( colourStep * i );
+ colour.SetBlue( colourStep * i );
+ mppRoadSegmentArray[ i ]->Render( colour );
+ }
+ }
+
+ // Render the lanes.
+ //
+ static bool bDrawLanes = true;
+ if ( bDrawLanes )
+ {
+ unsigned int i = 0;
+ for ( i = 0; i < mnLanes; i++ )
+ {
+ this->mLaneList[ i ].Render( );
+ }
+ }
+ }
+}
+/*
+==============================================================================
+RoadSegment::Render
+==============================================================================
+Description: Outline the rectangular road segment.
+
+Parameters: ( const tColour& colour )
+
+Return: void
+
+=============================================================================
+*/
+void RoadSegment::Render( const tColour& colour )
+{
+ tColour roadSegmentColour = colour;
+
+ rmt::Sphere sphere;
+ GetBoundingSphere( &sphere );
+
+
+ if ( p3d::context->GetView()->GetCamera()->SphereVisible( sphere.centre, sphere.radius ) )
+ {
+ const int numPoints = 4;
+ rmt::Vector vertices[ numPoints ];
+ int i = 0;
+ for ( i = 0; i < numPoints; i++ )
+ {
+ GetCorner( i, vertices[ i ] );
+
+ vertices[i].y += 1.0f;
+ }
+
+ pddiPrimStream* stream = p3d::pddi->BeginPrims( GetShader()->GetShader(), PDDI_PRIM_LINES, PDDI_V_C, numPoints * 2 );
+
+
+ for ( i = 0; i < numPoints; i++ )
+ {
+ if ( stream )
+ {
+ stream->Vertex( ( ( pddiVector* )( &( vertices[ i ] ) ) ), roadSegmentColour );
+ stream->Vertex( ( ( pddiVector* )( &( vertices[ ( i + 1 ) % numPoints ] ) ) ), roadSegmentColour );
+ }
+ }
+ p3d::pddi->EndPrims( stream );
+
+ stream = p3d::pddi->BeginPrims( GetShader()->GetShader(), PDDI_PRIM_LINES, PDDI_V_C, GetNumLanes() * 2 );
+
+ unsigned int index;
+ for ( index = 0; index < GetNumLanes(); index++ )
+ {
+ if ( stream )
+ {
+ rmt::Vector pos, facing;
+ GetLaneLocation(0.0f, index, pos, facing);
+ pos.y += 1.0f;
+ stream->Vertex( ( ( pddiVector* )( &( pos ) ) ), tColour( 255, 0, 0 ) );
+
+ GetLaneLocation(1.0f, index, pos, facing);
+ pos.y += 1.0f;
+ stream->Vertex( ( ( pddiVector* )( &( pos ) ) ), tColour( 255, 0, 0 ) );
+ }
+ }
+ p3d::pddi->EndPrims( stream );
+ }
+}
+
+
+void RoadSegment::RenderAnywhere( const tColour& colour )
+{
+ tColour roadSegmentColour = colour;
+
+ rmt::Sphere sphere;
+ GetBoundingSphere( &sphere );
+
+ const int numPoints = 4;
+ rmt::Vector vertices[ numPoints ];
+ int i = 0;
+ for ( i = 0; i < numPoints; i++ )
+ {
+ GetCorner( i, vertices[ i ] );
+
+ vertices[i].y += 1.0f;
+ }
+
+ pddiPrimStream* stream = p3d::pddi->BeginPrims( GetShader()->GetShader(), PDDI_PRIM_LINES, PDDI_V_C, numPoints * 2 );
+
+
+ for ( i = 0; i < numPoints; i++ )
+ {
+ if ( stream )
+ {
+ stream->Vertex( ( ( pddiVector* )( &( vertices[ i ] ) ) ), roadSegmentColour );
+ stream->Vertex( ( ( pddiVector* )( &( vertices[ ( i + 1 ) % numPoints ] ) ) ), roadSegmentColour );
+ }
+ }
+ p3d::pddi->EndPrims( stream );
+
+ stream = p3d::pddi->BeginPrims( GetShader()->GetShader(), PDDI_PRIM_LINES, PDDI_V_C, GetNumLanes() * 2 );
+
+ unsigned int index;
+ for ( index = 0; index < GetNumLanes(); index++ )
+ {
+ if ( stream )
+ {
+ rmt::Vector pos, facing;
+ GetLaneLocation(0.0f, index, pos, facing);
+ pos.y += 1.0f;
+ stream->Vertex( ( ( pddiVector* )( &( pos ) ) ), tColour( 255, 0, 0 ) );
+
+ GetLaneLocation(1.0f, index, pos, facing);
+ pos.y += 1.0f;
+ stream->Vertex( ( ( pddiVector* )( &( pos ) ) ), tColour( 255, 0, 0 ) );
+ }
+ }
+ p3d::pddi->EndPrims( stream );
+
+}
+
+/*
+==============================================================================
+Lane::Render
+==============================================================================
+Description: Draw a line connecting the lane points.
+
+Parameters: ( void )
+
+Return: void
+
+=============================================================================
+*/
+void Lane::Render( void )
+{
+#if defined(RAD_DEBUG) || defined(RAD_TUNE)
+ static tColour laneColour( 255, 0, 0 );
+
+ rmt::Vector start, end;
+ GetStart( start );
+ GetEnd( end );
+
+ int numPoints = this->GetNumPoints( );
+ // Draw a line from the start to the end.
+ //
+ pddiPrimStream* stream = p3d::pddi->BeginPrims( GetShader()->GetShader(), PDDI_PRIM_LINESTRIP, PDDI_V_C, numPoints );
+
+ int i = 0;
+ for ( i = 0; i < numPoints; i++ )
+ {
+ if ( stream )
+ {
+ rmt::Vector point;
+ GetPoint( i, &point );
+ point.y += 1.0f;
+ stream->Vertex( ( ( pddiVector* )( &( point ) ) ), laneColour );
+ }
+ }
+ p3d::pddi->EndPrims( stream );
+#endif
+}
diff --git a/game/code/roads/roadrendertest.cpp b/game/code/roads/roadrendertest.cpp
new file mode 100644
index 0000000..d8619be
--- /dev/null
+++ b/game/code/roads/roadrendertest.cpp
@@ -0,0 +1,271 @@
+//=============================================================================
+// Copyright (C) 2002 Radical Entertainment Ltd. All rights reserved.
+//
+// File: RoadRenderTest.cpp
+//
+// Description: Implement RoadRenderTest
+//
+// History: 27/06/2002 + Created -- Cary Brisebois
+//
+//=============================================================================
+
+#ifndef RAD_RELEASE
+
+//========================================
+// System Includes
+//========================================
+// Foundation Tech
+#include <raddebug.hpp>
+#include <radmath/radmath.hpp>
+#include <raddebugwatch.hpp>
+
+//========================================
+// Project Includes
+//========================================
+#include <roads/RoadRenderTest.h>
+#include <roads/roadmanager.h>
+#include <roads/road.h>
+#include <roads/roadsegment.h>
+#include <roads/intersection.h>
+#include <worldsim/avatar.h>
+#include <worldsim/avatarmanager.h>
+#include <render/rendermanager/rendermanager.h>
+#include <render/culling/spatialtree.h>
+#include <render/culling/worldscene.h>
+#include <render/dsg/intersectdsg.h>
+#include <contexts/bootupcontext.h>
+#include <debug/profiler.h>
+
+//******************************************************************************
+//
+// Global Data, Local Data, Local Classes
+//
+//******************************************************************************
+
+//******************************************************************************
+//
+// Public Member Functions
+//
+//******************************************************************************
+
+//==============================================================================
+// RoadRenderTest::RoadRenderTest
+//==============================================================================
+// Description: Constructor.
+//
+// Parameters: None.
+//
+// Return: N/A.
+//
+//==============================================================================
+RoadRenderTest::RoadRenderTest() :
+ mDisplay( false ),
+ mDisplaySpawnSegments( false ),
+ mDisplayTerrainTypes( false )
+{
+ radDbgWatchAddBoolean( &mDisplay, "Display", "Roads" );
+ radDbgWatchAddBoolean( &mDisplaySpawnSegments, "Display Spawn Segments", "Roads" );
+ radDbgWatchAddBoolean( &mDisplayTerrainTypes, "Display Terrain Types", "Roads" );
+}
+
+//==============================================================================
+// RoadRenderTest::~RoadRenderTest
+//==============================================================================
+// Description: Destructor.
+//
+// Parameters: None.
+//
+// Return: N/A.
+//
+//==============================================================================
+RoadRenderTest::~RoadRenderTest()
+{
+ radDbgWatchDelete( &mDisplay );
+ radDbgWatchDelete( &mDisplaySpawnSegments );
+ radDbgWatchDelete( &mDisplayTerrainTypes );
+}
+
+//=============================================================================
+// RoadRenderTest::Display
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ()
+//
+// Return: void
+//
+//=============================================================================
+void RoadRenderTest::Display()
+{
+ DisplaySpawnSegments();
+ DisplayTerrainType();
+ if ( !mDisplay )
+ {
+ return;
+ }
+
+ BEGIN_PROFILE("RoadRenderTest");
+
+ Avatar* a = GetAvatarManager()->GetAvatarForPlayer( 0 );
+ rAssert( a );
+
+ rmt::Vector position;
+ a->GetPosition( position );
+
+ RoadManager* rm = RoadManager::GetInstance();
+
+ const Road* road = NULL;
+ RoadSegment* irs = NULL;
+ int index = -1;
+ float in = 0;
+ float lateral = 0;
+
+ if ( rm->FindRoad( position, &road, &irs, index, in, lateral, true ) )
+ {
+ irs->Render( tColour( 255, 255, 255 ) );
+ }
+ else
+ {
+ Intersection* intersection = rm->FindIntersection( position );
+ if ( intersection )
+ {
+ intersection->Render();
+ }
+ }
+
+ END_PROFILE("RoadRenderTest");
+}
+
+void RoadRenderTest::DisplaySpawnSegments()
+{
+ if ( !mDisplaySpawnSegments )
+ {
+ return;
+ }
+
+ if ( !mSegments.IsSetUp() )
+ {
+ return;
+ }
+
+ BEGIN_PROFILE("RoadRenderTest");
+
+
+ int i;
+ for( i=0; i<mSegments.mUseSize; i++ )
+ {
+ RoadSegment* segment;
+
+ segment = mSegments.mpData[i];
+ rAssert( segment != NULL );
+
+ segment->RenderAnywhere( tColour( 255, 255, 255 ) );
+ }
+
+
+ END_PROFILE("RoadRenderTest");
+}
+
+void RoadRenderTest::DisplayTerrainType( void )
+{
+ if( !mDisplayTerrainTypes )
+ {
+ return;
+ }
+
+ tColour terrainColours[ 9 ];
+ terrainColours[ 0 ].Set( 128, 128, 128 ); // Road.
+ terrainColours[ 1 ].Set( 0, 255, 0 ); // Grass.
+ terrainColours[ 2 ].Set( 255, 255, 0 ); // Sand.
+ terrainColours[ 3 ].Set( 32, 32, 32 ); // Gravel.
+ terrainColours[ 4 ].Set( 0, 0, 255 ); // Water.
+ terrainColours[ 5 ].Set( 250, 200, 150 ); // Wood.
+ terrainColours[ 6 ].Set( 200, 225, 250 ); // Metal.
+ terrainColours[ 7 ].Set( 64, 48, 32 ); // Dirt.
+ terrainColours[ 8 ].Set( 255, 0, 255 ); // Unknown.
+
+ Avatar* a = GetAvatarManager()->GetAvatarForPlayer( 0 );
+ rAssert( a );
+
+ rmt::Vector position;
+ a->GetPosition( position );
+ SpatialNode& rCurrentLeaf = GetRenderManager()->pWorldScene()->mStaticTreeWalker.rSeekLeaf( (Vector3f&)position );
+
+ pddiShader* testShader = BootupContext::GetInstance()->GetSharedShader();
+ testShader->SetInt( PDDI_SP_BLENDMODE, PDDI_BLEND_NONE );
+ testShader->SetInt( PDDI_SP_ISLIT, 0 );
+ testShader->SetInt( PDDI_SP_ALPHATEST, 0 );
+ testShader->SetInt( PDDI_SP_SHADEMODE, PDDI_SHADE_FLAT ); //PDDI_SHADE_GOURAUD
+ testShader->SetInt( PDDI_SP_TWOSIDED, 1 );
+
+ for( int i = rCurrentLeaf.mIntersectElems.mUseSize - 1; i > -1; --i )
+ {
+ for( int j = rCurrentLeaf.mIntersectElems[ i ]->nTris() - 1; j > -1; --j )
+ {
+ //rmt::Vector tmpVect, tmpVect2;
+ //float DistToPlane, ClosestDistToPlane = 20000.0f;
+ rmt::Vector triPts[ 3 ];
+ rmt::Vector triNorm;
+ rmt::Vector triCtr;
+ //float triRadius;
+ int terrainType;
+ bool interior;
+ //triRadius = rCurrentLeaf.mIntersectElems[ i ]->mTri( j, triPts, triNorm, triCtr, &terrainType);
+ terrainType = rCurrentLeaf.mIntersectElems[ i ]->mTri( j, triPts, triNorm );
+ interior = ( terrainType & 0x80 ) != 0;
+ terrainType &= ~0x80;
+ int colourIndex = rmt::Clamp( terrainType, 0, 8 );
+ tColour lineColour( terrainColours[ colourIndex ] );
+ if( interior )
+ {
+ lineColour.Set( lineColour.Red() >> 1, lineColour.Green() >> 1, lineColour.Blue() >> 1 );
+ }
+ tColour fillColour;
+ fillColour.Set( lineColour.Red() >> 1, lineColour.Green() >> 1, lineColour.Blue() >> 1 );
+
+ rmt::Vector center( triPts[ 0 ] );
+ center.Add( triPts[ 1 ] );
+ center.Add( triPts[ 2 ] );
+ center.Scale( 1.0f / 3.0f );
+ rmt::Vector toCenter;
+ triNorm.Scale( 0.1f );
+
+ for( int k = 0; k < 3; ++k )
+ {
+ toCenter.Sub( center, triPts[ k ] );
+ toCenter.Normalize();
+ toCenter.Scale( 0.1f );
+ triPts[ k ].Add( toCenter );
+ triPts[ k ].Add( triNorm );
+ }
+
+ pddiPrimStream* test = p3d::pddi->BeginPrims( testShader, PDDI_PRIM_TRIANGLES, PDDI_V_C, 3 );
+ test->Colour( fillColour );
+ test->Coord( triPts[ 0 ].x, triPts[ 0 ].y, triPts[ 0 ].z );
+ test->Colour( fillColour );
+ test->Coord( triPts[ 1 ].x, triPts[ 1 ].y, triPts[ 1 ].z );
+ test->Colour( fillColour );
+ test->Coord( triPts[ 2 ].x, triPts[ 2 ].y, triPts[ 2 ].z );
+ p3d::pddi->EndPrims( test );
+ test = p3d::pddi->BeginPrims( testShader, PDDI_PRIM_LINESTRIP, PDDI_V_C, 4 );
+ test->Colour( lineColour );
+ test->Coord( triPts[ 0 ].x, triPts[ 0 ].y, triPts[ 0 ].z );
+ test->Colour( lineColour );
+ test->Coord( triPts[ 1 ].x, triPts[ 1 ].y, triPts[ 1 ].z );
+ test->Colour( lineColour );
+ test->Coord( triPts[ 2 ].x, triPts[ 2 ].y, triPts[ 2 ].z );
+ test->Colour( lineColour );
+ test->Coord( triPts[ 0 ].x, triPts[ 0 ].y, triPts[ 0 ].z );
+ p3d::pddi->EndPrims( test );
+ }
+ }
+ testShader->SetInt( PDDI_SP_TWOSIDED, 0 );
+}
+
+//******************************************************************************
+//
+// Private Member Functions
+//
+//******************************************************************************
+
+#endif \ No newline at end of file
diff --git a/game/code/roads/roadrendertest.h b/game/code/roads/roadrendertest.h
new file mode 100644
index 0000000..78a4e22
--- /dev/null
+++ b/game/code/roads/roadrendertest.h
@@ -0,0 +1,60 @@
+//=============================================================================
+// Copyright (C) 2002 Radical Entertainment Ltd. All rights reserved.
+//
+// File: roadrendertest.h
+//
+// Description: Blahblahblah
+//
+// History: 27/06/2002 + Created -- Cary Brisebois
+//
+//=============================================================================
+
+#ifndef ROADRENDERTEST_H
+#define ROADRENDERTEST_H
+
+#ifndef RAD_RELEASE
+//========================================
+// Nested Includes
+//========================================
+#include <radmath/radmath.hpp>
+#include <roads/roadsegment.h>
+#include <render/Culling/ReserveArray.h>
+
+#include <p3d/drawable.hpp>
+
+//========================================
+// Forward References
+//========================================
+
+//=============================================================================
+//
+// Synopsis: Blahblahblah
+//
+//=============================================================================
+
+class RoadRenderTest : public tDrawable
+{
+public:
+ RoadRenderTest();
+ virtual ~RoadRenderTest();
+
+ void Display();
+ void DisplaySpawnSegments();
+ void DisplayTerrainType( void );
+
+ ReserveArray<RoadSegment*> mSegments;
+
+private:
+
+ bool mDisplay;
+ bool mDisplaySpawnSegments;
+ bool mDisplayTerrainTypes;
+
+ //Prevent wasteful constructor creation.
+ RoadRenderTest( const RoadRenderTest& roadrendertest );
+ RoadRenderTest& operator=( const RoadRenderTest& roadrendertest );
+};
+
+#endif
+
+#endif //ROADRENDERTEST_H
diff --git a/game/code/roads/roadsegment.cpp b/game/code/roads/roadsegment.cpp
new file mode 100644
index 0000000..e21c40a
--- /dev/null
+++ b/game/code/roads/roadsegment.cpp
@@ -0,0 +1,792 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: RoadSegment
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2002/02/25 Tbrown-John Created
+
+===========================================================================*/
+
+#include <roads/road.h>
+#include <roads/roadsegment.h>
+#include <roads/roadsegmentdata.h>
+
+RoadSegment::RoadSegment()
+:
+mRoad( NULL ),
+mSegmentIndex( 0 )
+{
+}
+
+RoadSegment::~RoadSegment( void )
+{
+}
+
+/*
+void RoadSegment::Init( RoadSegmentData* rsd, rmt::Matrix& hierarchy, float scaleAlongFacing )
+{
+ ////////////////////////////////////////////////////////////////
+ // Transform segment data based on given matrix & scale-along-facing
+ //
+ rmt::Vector vector;
+
+ // First, do the corners and the edgenormals
+ for( int i=0; i<4; i++ )
+ {
+ // transform the corner
+ vector = rsd->GetCorner( i );
+ vector.z *= scaleAlongFacing;
+ vector.Transform( hierarchy );
+ mCorners[ i ] = vector;
+
+ // transform the edge normals
+ vector = rsd->GetEdgeNormal( i );
+ vector.Rotate( hierarchy );
+ mEdgeNormals[ i ] = vector;
+ }
+
+ // Now, transform the segment normal
+ vector = rsd->GetSegmentNormal();
+ vector.Rotate( hierarchy );
+ mNormal = vector;
+
+ // Now, calculate and store segment length
+ rmt::Vector segStart = (mCorners[0] + mCorners[3]) * 0.5f;
+ rmt::Vector segEnd = (mCorners[1] + mCorners[2]) * 0.5f;
+ mfSegmentLength = (segEnd - segStart).Length(); // *** SQUARE ROOT! ***
+
+ // Now, calculate and store the bounding sphere
+ rmt::Box3D box;
+ GetBoundingBox( &box ); // find the box on the fly (based on extents of corners)
+
+ // compute & store the bounding sphere based on bbox
+ rmt::Vector vectorBetween;
+ vectorBetween = ( box.high - box.low ) * 0.5f;
+ mSphere.centre = box.low + vectorBetween;
+ mSphere.radius = vectorBetween.Magnitude(); // *** SQUARE ROOT! ***
+
+
+
+ //////////////////////////////
+ // TODO:
+ // This stuff is dubious. It won't be accurate given that we can no
+ // longer assume interior and exterior edges are parallel.
+ //
+ // Now, Calculate the width of the leading edge of the segment.
+ float fWidth = segStart.Magnitude();
+ mfLaneWidth = fWidth / (float)rsd->GetNumLanes();
+
+ // Calculate a turn radius.
+ //
+ float fCosTheta = mEdgeNormals[0].DotProduct( mEdgeNormals[1] );
+ if ( fCosTheta < 0.0f )
+ {
+ fCosTheta = 0.0f - fCosTheta;
+ }
+ if ( fCosTheta < 0.001f ) //Clamp me.
+ {
+ fCosTheta = 0.0f;
+ }
+
+ rmt::Vector temp;
+ temp.Sub( mCorners[0], mCorners[1] );
+ float fInteriorEdgeLength = temp.Magnitude( );
+ temp.Sub( mCorners[2], mCorners[3] );
+ float fExteriorEdgeLength = temp.Magnitude( );
+
+ if ( fCosTheta != 0.0f )
+ {
+ // take the shortest length.
+ float length = ( fInteriorEdgeLength < fExteriorEdgeLength )? fInteriorEdgeLength : fExteriorEdgeLength;
+ length = length / 2.0f;
+ mfRadius = length / fCosTheta;
+ mfAngle = rmt::PI_BY2 - rmt::ACos( fCosTheta );
+ //rmt::RadianToDeg( mfAngle );
+ }
+ else
+ {
+ // Not a curved segment.
+ //
+ mfRadius = 0.0f;
+ mfAngle = 0.0f;
+ }
+}
+*/
+void RoadSegment::Init( RoadSegmentData* rsd, rmt::Matrix& hierarchy, float scaleAlongFacing )
+{
+ ////////////////////////////////////////////////////////////////
+ // Transform segment data based on given matrix & scale-along-facing
+ //
+ rmt::Vector vector;
+
+ // store the unmodified values
+ for( int i=0; i<4; i++ )
+ {
+ vector = rsd->GetCorner( i );
+ mCorners[ i ] = vector;
+
+ vector = rsd->GetEdgeNormal( i );
+ mEdgeNormals[ i ] = vector;
+ }
+
+
+ //////////////////////////////
+ // TODO:
+ // This stuff is dubious. It won't be accurate given that we can no
+ // longer assume interior and exterior edges are parallel. AND
+ // somehow it's able to work quite accurately from the corner
+ // and edgenormal values that have not yet been transformed. *shudder*
+ //
+ // Now, Calculate the width of the leading edge of the segment.
+ float fWidth = ((mCorners[0] + mCorners[3]) * 0.5f).Magnitude();
+ mfLaneWidth = fWidth / (float)rsd->GetNumLanes();
+
+ // Calculate a turn radius.
+ //
+ float fCosTheta = mEdgeNormals[0].DotProduct( mEdgeNormals[1] );
+ if ( fCosTheta < 0.0f )
+ {
+ fCosTheta = 0.0f - fCosTheta;
+ }
+ if ( fCosTheta < 0.001f ) //Clamp me.
+ {
+ fCosTheta = 0.0f;
+ }
+
+ rmt::Vector temp;
+ temp.Sub( mCorners[0], mCorners[1] );
+ float fInteriorEdgeLength = temp.Magnitude( );
+ temp.Sub( mCorners[2], mCorners[3] );
+ float fExteriorEdgeLength = temp.Magnitude( );
+
+ if ( fCosTheta != 0.0f )
+ {
+ // take the shortest length.
+ float length = ( fInteriorEdgeLength < fExteriorEdgeLength )? fInteriorEdgeLength : fExteriorEdgeLength;
+ length = length / 2.0f;
+ mfRadius = length / fCosTheta;
+ mfAngle = rmt::PI_BY2 - rmt::ACos( fCosTheta );
+ //rmt::RadianToDeg( mfAngle );
+ }
+ else
+ {
+ // Not a curved segment.
+ //
+ mfRadius = 0.0f;
+ mfAngle = 0.0f;
+ }
+ ///////////////////////////////////////////
+
+
+
+ // Ok, so first, transform the corners and the edgenormals
+ for( int i=0; i<4; i++ )
+ {
+ // transform the corner
+ vector = rsd->GetCorner( i );
+ vector.z *= scaleAlongFacing;
+ vector.Transform( hierarchy );
+ mCorners[ i ] = vector;
+
+ // transform the edge normals
+ vector = rsd->GetEdgeNormal( i );
+ vector.Rotate( hierarchy );
+ mEdgeNormals[ i ] = vector;
+ }
+
+ // Now, transform the segment normal
+ vector = rsd->GetSegmentNormal();
+ vector.Rotate( hierarchy );
+ mNormal = vector;
+
+ // Now, calculate and store segment length
+ rmt::Vector segStart = (mCorners[0] + mCorners[3]) * 0.5f;
+ rmt::Vector segEnd = (mCorners[1] + mCorners[2]) * 0.5f;
+ mfSegmentLength = (segEnd - segStart).Length(); // *** SQUARE ROOT! ***
+
+ // Now, calculate and store the bounding sphere
+ rmt::Box3D box;
+ GetBoundingBox( &box ); // find the box on the fly (based on extents of corners)
+
+ // compute & store the bounding sphere based on bbox
+ rmt::Vector vectorBetween;
+ vectorBetween = ( box.high - box.low ) * 0.5f;
+ mSphere.centre = box.low + vectorBetween;
+ mSphere.radius = vectorBetween.Magnitude(); // *** SQUARE ROOT! ***
+
+
+}
+
+
+void RoadSegment::GetBoundingBox(rmt::Box3D* box)
+{
+ // get axis-aligned bounding box from vertices...
+ unsigned int numVertices = 4;
+ rmt::Vector vertex;
+ unsigned int i = 0;
+ for ( i = 0; i < numVertices; i++ )
+ {
+ vertex = mCorners[i];
+ if ( 0 == i )
+ {
+ // This is the first time.
+ // Initialize to some value.
+ //
+ box->low = box->high = vertex;
+ }
+ else
+ {
+ if ( box->low.x > vertex.x )
+ {
+ box->low.x = vertex.x;
+ }
+ if ( box->low.y > vertex.y )
+ {
+ box->low.y = vertex.y;
+ }
+ if ( box->low.z > vertex.z )
+ {
+ box->low.z = vertex.z;
+ }
+
+ if ( box->high.x < vertex.x )
+ {
+ box->high.x = vertex.x;
+ }
+ if ( box->high.y < vertex.y )
+ {
+ box->high.y = vertex.y;
+ }
+ if ( box->high.z < vertex.z )
+ {
+ box->high.z = vertex.z;
+ }
+ }
+ }
+}
+
+void RoadSegment::GetBoundingSphere(rmt::Sphere* sphere)
+{
+ *sphere = mSphere;
+}
+
+
+
+
+/*
+==============================================================================
+RoadSegment::CalculateUnitDistIntoRoadSegment
+==============================================================================
+Description: Adapted from GameGems Article by Steven Ranck. pp412-pp420.
+ Implements a fast and simple algm for determing where a point
+ in between the edges of a 2D quad (RoadSegment). The result
+ is a unit floting point number, where 0 indicates that the point
+ lies on the leading edge, and where 1 indicates that the point
+ lies on the opposite edge. The RoadSegment may be any 4 sided
+ 2D convex shape.
+
+Constraints: The RoadSegment must be convex and have 4 sides.
+ The RoadSegment must have a non zero area.
+ The point must lie within the sector. ***** What if it doesn't?
+
+Parameters: ( float fPointX, float fPointZ )
+
+Return: A scalar from 0 to 1.
+ 0 if point lies on the leading edge.
+ 1 if point lies on the trailing edge.
+ Smoothly interpolated value for all points in between.
+
+=============================================================================
+*/
+float RoadSegment::CalculateUnitDistIntoRoadSegment( float fPointX, float fPointZ )
+{
+ rmt::Vector VLP, VTP;
+ float fDotL, fDotT;
+
+ // Get and cache the leading edge top corner
+ // and the trailing edge bottom corner.
+ //
+ rmt::Vector vertices[ 2 ];
+ GetCorner( 0, vertices[ 0 ] );
+ GetCorner( 2, vertices[ 1 ] );
+
+ // Get and cache the leading edge normal
+ // and the trailing edge normal.
+ //
+ rmt::Vector unitNormals[ 2 ];
+ GetEdgeNormal( 0, unitNormals[ 0 ] );
+ GetEdgeNormal( 2, unitNormals[ 1 ] );
+
+ //for this to work, the normals must both point into
+ //the volume...
+ //so, I need to reverse the second edge normal
+ unitNormals[1] *= -1;
+
+ // Compute vector from point on Leading Edge to P:
+ //
+ VLP.x = fPointX - vertices[0].x;
+ VLP.y = 0.0f;
+ VLP.z = fPointZ - vertices[0].z;
+
+ // Compute vector from point on Trailing Edge to P:
+ //
+ VTP.x = fPointX - vertices[1].x;
+ VTP.y = 0.0f;
+ VTP.z = fPointZ - vertices[1].z;
+
+ // Compute (VLP dot Leading Edge Normal):
+ //
+ fDotL = VLP.x*unitNormals[0].x + VLP.z*unitNormals[0].z;
+
+ // Compute (VTP dot Trailing Edge Normal):
+ //
+ fDotT = VTP.x*unitNormals[1].x + VTP.z*unitNormals[1].z;
+
+ // Compute unit distance into sector and return it:
+ //
+ return ( fDotL / (fDotL + fDotT) );
+}
+
+float RoadSegment::CalculateUnitHeightInRoadSegment( float fPointX, float fPointZ )
+{
+ rmt::Vector VLP, VTP;
+ float fDotL, fDotT;
+
+ // Get and cache the leading edge top corner
+ // and the trailing edge bottom corner.
+ //
+ rmt::Vector vertices[ 2 ];
+ GetCorner( 0, vertices[ 0 ] );
+ GetCorner( 2, vertices[ 1 ] );
+
+ // Get and cache the leading edge normal
+ // and the trailing edge normal.
+ //
+ rmt::Vector unitNormals[ 2 ];
+ GetEdgeNormal( 1, unitNormals[ 0 ] );
+ GetEdgeNormal( 3, unitNormals[ 1 ] );
+
+ // Compute vector from point on Leading Edge to P:
+ //
+ VLP.x = fPointX - vertices[0].x;
+ VLP.y = 0.0f;
+ VLP.z = fPointZ - vertices[0].z;
+
+ // Compute vector from point on Trailing Edge to P:
+ //
+ VTP.x = fPointX - vertices[1].x;
+ VTP.y = 0.0f;
+ VTP.z = fPointZ - vertices[1].z;
+
+ // Compute (VLP dot Leading Edge Normal):
+ //
+ fDotL = VLP.x*unitNormals[0].x + VLP.z*unitNormals[0].z;
+
+ // Compute (VTP dot Trailing Edge Normal):
+ //
+ fDotT = VTP.x*unitNormals[1].x + VTP.z*unitNormals[1].z;
+
+ // Compute unit distance into sector and return it:
+ //
+ return ( fDotL / (fDotL + fDotT) );
+}
+
+
+/*
+float RoadSegment::CalculateYHeight( float fPointX, float fPointZ )
+{
+ // Get and cache the leading edge top corner
+ // and the trailing edge bottom corner.
+ //
+ rmt::Vector vertices[ 2 ];
+ GetCorner( 0, vertices[ 0 ] );
+ GetCorner( 2, vertices[ 1 ] );
+
+ float fDistance = CalculateUnitDistIntoRoadSegment( fPointX, fPointZ );
+ float y = LERP( fDistance, vertices[ 0 ].y, vertices[ 1 ].y );
+ return y;
+}
+*/
+
+void RoadSegment::GetPosition( float t, float w, rmt::Vector* pos )
+{
+ // Get and cache the corners.
+ //
+ rmt::Vector vertices[ 4 ];
+ GetCorner( 0, vertices[ 0 ] );
+ GetCorner( 1, vertices[ 1 ] );
+ GetCorner( 2, vertices[ 2 ] );
+ GetCorner( 3, vertices[ 3 ] );
+
+ rmt::Vector position;
+
+ // Interpolate the Normal vector across the Segment.
+ //
+ rmt::Vector leadingEdge;
+ leadingEdge.Sub( vertices[ 3 ], vertices[ 0 ] );
+ rmt::Vector leadingPoint = leadingEdge;
+ leadingPoint.Scale( w );
+ leadingPoint.Add( vertices[ 0 ] );
+
+ rmt::Vector trailingEdge;
+ trailingEdge.Sub( vertices[ 2 ], vertices[ 1 ] );
+ rmt::Vector trailingPoint = trailingEdge;
+ trailingPoint.Scale( w );
+ trailingPoint.Add( vertices[ 1 ] );
+
+ position.Sub( trailingPoint, leadingPoint );
+ position.Scale( t );
+ position.Add( leadingPoint );
+ *pos = position;
+}
+
+
+void RoadSegment::GetLaneLocation( float t, int index, rmt::Vector& position, rmt::Vector& facing )
+{
+ //
+ // Get the world space point and facing at time 't'.
+ //
+ // Interpolate the facing.
+ //
+ rmt::Vector facingNormals[ 2 ];
+ GetEdgeNormal( 0, facingNormals[ 0 ] );
+ GetEdgeNormal( 2, facingNormals[ 1 ] );
+ facing.x = LERP( t, facingNormals[ 0 ].x, facingNormals[ 1 ].x );
+ facing.y = LERP( t, facingNormals[ 0 ].y, facingNormals[ 1 ].y );
+ facing.z = LERP( t, facingNormals[ 0 ].z, facingNormals[ 1 ].z );
+
+ // [Dusit: July 6th, 2003]
+ // NOTE:
+ // This is the CORRECT way to produce the lane length value when
+ // the width of the roadsegment isn't guaranteed across its length.
+ // The only thing that it assumes (and is always correct) is that
+ // each lane is as wide as the other lanes at any given point along
+ // the length of the segment
+ //
+ float edgeT = ((float)(index<<1) + 1.0f) / ((float)(GetNumLanes()<<1));
+
+ // find start & end points of the lane
+ rmt::Vector vec0, vec1, vec2, vec3;
+
+ GetCorner( 0, vec0 );
+ GetCorner( 1, vec1 );
+ GetCorner( 2, vec2 );
+ GetCorner( 3, vec3 );
+
+ // lane indices go from 0 to n, right to left ( n <=== 0 )
+ rmt::Vector bottomEdgeDir = vec0 - vec3; // points frm 3 to 0
+ rmt::Vector topEdgeDir = vec1 - vec2; // points frm 2 to 1
+
+ // now we figure out the starting point and ending point of the
+ // lane segment
+ rmt::Vector start = vec3 + bottomEdgeDir * edgeT;
+ rmt::Vector end = vec2 + topEdgeDir * edgeT;
+
+ // now find the t position along the lane
+ rmt::Vector laneDir = end - start;
+ position = start + laneDir * t;
+
+ /*
+
+ // Get and cache the corners.
+ //
+ rmt::Vector vertices[ 4 ];
+ GetCorner( 0, vertices[ 0 ] );
+ GetCorner( 1, vertices[ 1 ] );
+ GetCorner( 2, vertices[ 2 ] );
+ GetCorner( 3, vertices[ 3 ] );
+
+ //There is an assumption here that the road does not get wider or thinner
+ //across its length...
+ // Scale unnormalized vector by normalized center of desired lane.
+ // ( ( index * fLaneWidth ) + ( fLaneWidth / 2.0f ) ) / roadWidth;
+ //
+ float fCentreOfLane = ( index * mfLaneWidth ) + ( mfLaneWidth / 2.0f );
+
+ //I call this parametric variable w;
+ float w = fCentreOfLane / GetRoadWidth();
+
+ // Interpolate the Normal vector across the Segment.
+ //
+ rmt::Vector leadingEdge;
+ leadingEdge.Sub( vertices[ 0 ], vertices[ 3 ] );
+ rmt::Vector leadingPoint = leadingEdge;
+ leadingPoint.Scale( w );
+ leadingPoint.Add( vertices[ 3 ] );
+
+
+ rmt::Vector trailingEdge;
+ trailingEdge.Sub( vertices[ 1 ], vertices[ 2 ] );
+ rmt::Vector trailingPoint = trailingEdge;
+ trailingPoint.Scale( w );
+ trailingPoint.Add( vertices[ 2 ] );
+
+ //This gives the point between the leading and trailing point by parameter t.
+ position.x = LERP( t, leadingPoint.x, trailingPoint.x );
+ position.y = LERP( t, leadingPoint.y, trailingPoint.y );
+ position.z = LERP( t, leadingPoint.z, trailingPoint.z );
+ */
+
+
+}
+
+
+/*
+//==============================================================================
+//RoadSegment::GetJoinPoint
+//==============================================================================
+//Description: RoadSegmentData pieces are always joined at the left corner
+// of the trailing edge. The normal of the leading edge of the
+// new piece is always the inverse normal of the trailing edge
+// of the previous piece.
+//
+// This function returns the join vertex and facing in world space.
+//
+//Parameters: ( rmt::Vector& position, rmt::Vector& facing )
+//
+//Return: void
+//
+//=============================================================================
+void RoadSegment::GetJoinPoint( rmt::Vector& position, rmt::Vector& facing )
+{
+ // All segments are joined at the left top corner.
+ //
+ position = GetRoadSegmentData( )->GetCorner( 1 );
+
+ facing = GetRoadSegmentData( )->GetEdgeNormal( 2 );
+ facing.Scale( -1.0f );
+}
+*/
+
+void RoadSegment::GetCorner( int index, rmt::Vector& out )
+{
+ rAssert( 0 <= index && index < 4 );
+ out = mCorners[ index ];
+}
+void RoadSegment::GetEdgeNormal( int index, rmt::Vector& out )
+{
+ rAssert( 0 <= index && index < 4 );
+ out = mEdgeNormals[ index ];
+}
+void RoadSegment::GetSegmentNormal( rmt::Vector& out )
+{
+ out = mNormal;
+}
+unsigned int RoadSegment::GetNumLanes( void )
+{
+ return GetRoad()->GetNumLanes();
+}
+float RoadSegment::GetLaneLength( unsigned int lane )
+{
+ // [Dusit: July 6th, 2003]
+ // NOTE:
+ // This is the CORRECT way to produce the lane length value when
+ // the width of the roadsegment isn't guaranteed across its length.
+ // The only thing that it assumes (and is always correct) is that
+ // each lane is as wide as the other lanes at any given point along
+ // the length of the segment
+ //
+ // The problem with using this is that it requires a Sqrt (because
+ // it's too late for us to rearrange the data so that we can avoid
+ // this). So we continue using the old way because we're never off
+ // by more than 5 centimeters anyway.
+ //
+ float edgeT = ((float)(lane<<1) + 1.0f) / ((float)(GetNumLanes()<<1));
+
+ // find start & end points of the lane
+ rmt::Vector vec0, vec1, vec2, vec3;
+
+ GetCorner( 0, vec0 );
+ GetCorner( 1, vec1 );
+ GetCorner( 2, vec2 );
+ GetCorner( 3, vec3 );
+
+ // lane indices go from 0 to n, right to left ( n <=== 0 )
+ rmt::Vector bottomEdgeDir = vec0 - vec3; // points frm 3 to 0
+ rmt::Vector topEdgeDir = vec1 - vec2; // points frm 2 to 1
+
+ rmt::Vector start = vec3 + bottomEdgeDir * edgeT;
+ rmt::Vector end = vec2 + topEdgeDir * edgeT;
+
+ float expectedLength = (end - start).Magnitude();
+ return expectedLength;
+
+ /*
+ float computedLength = 0.0f;
+
+ // TODO:
+ // Because we can't assume that a lane is constant-width, this
+ // code is totally bogus...
+ if ( mfAngle > 0.0f )
+ {
+ // 2*PI*r for a circle.
+ // Theta*r for arc of theta degrees.
+ //
+ float fLaneOffset = mfLaneWidth * lane + mfLaneWidth;
+ computedLength = 2.0f * mfAngle * ( mfRadius + fLaneOffset );
+ }
+ else
+ {
+ // it's not a curve, both edge lengths will be equal.
+ //
+ computedLength = mfSegmentLength;
+ }
+
+ //rAssert( rmt::Epsilon( computedLength, expectedLength, 0.01f ) );
+ return computedLength;
+ */
+}
+
+float RoadSegment::GetRoadWidth()
+{
+ return mRoad->GetNumLanes() * mfLaneWidth;
+}
+
+
+/*
+
+/////////////////////////////////////////////////////////////////
+// TransformRoadSegment
+/////////////////////////////////////////////////////////////////
+//
+TransformRoadSegment::TransformRoadSegment() :
+ RoadSegment( NULL )
+{
+ mTransform.Identity();
+ mfScaleAlongFacing = 0.0f;
+}
+
+TransformRoadSegment::TransformRoadSegment(
+ const RoadSegmentData* pRoadSegmentData,
+ rmt::Matrix& transform )
+ :
+ RoadSegment( pRoadSegmentData )
+{
+ mTransform = transform;
+}
+
+TransformRoadSegment::TransformRoadSegment(
+ const RoadSegmentData* pRoadSegmentData,
+ rmt::Matrix& transform,
+ float fScaleAlongFacing )
+ :
+ RoadSegment( pRoadSegmentData ),
+ mfScaleAlongFacing( fScaleAlongFacing )
+{
+ mTransform = transform;
+}
+
+TransformRoadSegment::TransformRoadSegment(
+ const RoadSegmentData* pRoadSegmentData,
+ const rmt::Vector& facing,
+ const rmt::Vector& position )
+ :
+ RoadSegment( pRoadSegmentData )
+{
+ rmt::Vector sApproximateUp( 0.0f, 1.0f, 0.0f );
+
+ mTransform.Identity( );
+ mTransform.FillHeading( facing, sApproximateUp );
+ mTransform.FillTranslate( position );
+}
+
+TransformRoadSegment::TransformRoadSegment(
+ const RoadSegmentData* pRoadSegmentData,
+ const rmt::Vector& facing,
+ const rmt::Vector& position,
+ float fScaleAlongFacing )
+ :
+ RoadSegment( pRoadSegmentData ),
+ mfScaleAlongFacing( fScaleAlongFacing )
+{
+ rmt::Vector sApproximateUp( 0.0f, 1.0f, 0.0f );
+
+ mTransform.Identity( );
+ mTransform.FillHeading( facing, sApproximateUp );
+ mTransform.FillTranslate( position );
+}
+void TransformRoadSegment::GetCorner( int index, rmt::Vector& out ) const
+{
+ out = GetRoadSegmentData( )->GetCorner( index );
+ out.z *= mfScaleAlongFacing;
+ out.Transform( mTransform );
+}
+void TransformRoadSegment::GetEdgeNormal( int index, rmt::Vector& out ) const
+{
+ out = GetRoadSegmentData( )->GetEdgeNormal( index );
+ out.Rotate( mTransform );
+}
+void TransformRoadSegment::GetSegmentNormal( rmt::Vector& out ) const
+{
+ out = GetRoadSegmentData( )->GetSegmentNormal( );
+ out.Rotate( mTransform );
+}
+
+//==============================================================================
+//TransformRoadSegment::GetJoinPoint
+//==============================================================================
+//Description: RoadSegmentData pieces are always joined at the left corner
+// of the trailing edge. The normal of the leading edge of the
+// new piece is always the inverse normal of the trailing edge
+// of the previous piece.
+//
+// This function returns the join vertex and facing in world space.
+//
+//Parameters: ( rmt::Vector& position, rmt::Vector& facing )
+//
+//Return: void
+//
+//=============================================================================
+void TransformRoadSegment::GetJoinPoint( rmt::Vector& position, rmt::Vector& facing ) const
+{
+ // All segments are joined at the left top corner.
+ //
+ facing = GetRoadSegmentData( )->GetEdgeNormal( 2 );
+ facing.Scale( -1.0f );
+ facing.Rotate( mTransform );
+
+ position = GetRoadSegmentData( )->GetCorner( 1 );
+ position.z *= mfScaleAlongFacing;
+ position.Transform( mTransform );
+}
+void TransformRoadSegment::GetBoundingBox(rmt::Box3D* box)
+{
+ GetRoadSegmentData()->GetBoundingBox( *box );
+ (*box).high.z *= mfScaleAlongFacing;
+ (*box).high.Transform( mTransform );
+ (*box).low.Transform( mTransform );
+}
+void TransformRoadSegment::GetBoundingSphere(rmt::Sphere* sphere)
+{
+ GetRoadSegmentData( )->GetBoundingSphere( *sphere );
+ (*sphere).radius *= mfScaleAlongFacing;
+ (*sphere).centre.Transform( mTransform );
+}
+
+void TransformRoadSegment::GetBoundingBox( rmt::Box3D& out ) const
+{
+ GetRoadSegmentData( )->GetBoundingBox( out );
+ out.high.z *= mfScaleAlongFacing;
+ out.high.Transform( mTransform );
+ out.low.Transform( mTransform );
+}
+
+void TransformRoadSegment::GetBoundingSphere( rmt::Sphere& out ) const
+{
+ out = GetRoadSegmentData( )->GetBoundingSphere( );
+ out.radius *= mfScaleAlongFacing;
+ out.centre.Transform( mTransform );
+}
+
+void TransformRoadSegment::GetTransform( rmt::Matrix &out ) const
+{
+ out = mTransform;
+}
+
+*/ \ No newline at end of file
diff --git a/game/code/roads/roadsegment.h b/game/code/roads/roadsegment.h
new file mode 100644
index 0000000..9adbe7a
--- /dev/null
+++ b/game/code/roads/roadsegment.h
@@ -0,0 +1,267 @@
+#ifndef ROADSEGMENT_H_
+#define ROADSEGMENT_H_
+
+#ifdef WORLD_BUILDER
+#include "../render/DSG/IEntityDSG.h"
+#elif !defined(TOOLS)
+#include <render/DSG/IEntityDSG.h>
+#else
+#include <p3d/entity.hpp>
+#define IEntityDSG tEntity
+#endif
+
+#include <string.h>
+#include <radmath/radmath.hpp>
+
+class Road;
+class RoadSegmentData;
+
+
+////////////////////////////////////////////////////////////////////////
+// class RoadSegment adapted from GameGems article by Steven Ranck. pp 412-420.
+////////////////////////////////////////////////////////////////////////
+// Concrete Base = 8 bytes.
+//
+class RoadSegment :
+ public IEntityDSG
+{
+public:
+ RoadSegment();
+ virtual ~RoadSegment( void );
+
+ void Init( RoadSegmentData* rsd, rmt::Matrix& hierarchy, float scaleAlongFacing );
+
+ /////////////////////////////////////////////
+ // ACCESSORS
+ /////////////////////////////////////////////
+ void GetCorner( int index, rmt::Vector& out );
+ void GetEdgeNormal( int index, rmt::Vector& out );
+ void GetSegmentNormal( rmt::Vector& out );
+
+ void SetSegmentIndex( unsigned int index );
+ unsigned int GetSegmentIndex();
+
+ Road* GetRoad();
+ void SetRoad( Road* road );
+
+ float GetSegmentLength();
+
+ // for DEBUG
+ const char* GetName();
+ void SetName( const char* name );
+
+ float GetLaneWidth();
+ /////////////////////////////////////////////
+
+
+ float CalculateUnitDistIntoRoadSegment( float fPointX, float fPointZ );
+ float CalculateUnitHeightInRoadSegment( float fPointX, float fPointZ );
+ //float CalculateYHeight( float fPointX, float fPointZ );
+ void GetLaneLocation( float t, int index, rmt::Vector& position, rmt::Vector& facing );
+
+
+
+ unsigned int GetNumLanes( void ); // ask its parent road for the number of lanes
+ float GetRoadWidth(); // number of lanes (obtained from parent Road) times lane-width
+
+ //void GetJoinPoint( rmt::Vector& position, rmt::Vector& facing );
+ void GetPosition( float t, float w, rmt::Vector* pos );
+ float GetLaneLength( unsigned int lane );
+
+ // Temp method to display.
+ //
+ void Render( const tColour& colour );
+ void RenderAnywhere( const tColour& colour );
+
+
+ //////////////////////////////////////////////////////////////////////////
+ // IEntityDSG Interface
+ //////////////////////////////////////////////////////////////////////////
+ void DisplayBoundingBox(tColour colour = tColour(0,255,0));
+ void DisplayBoundingSphere(tColour colour = tColour(0,255,0));
+ void GetBoundingBox(rmt::Box3D* box);
+ void GetBoundingSphere(rmt::Sphere* sphere);
+ void Display();
+ rmt::Vector* pPosition();
+ const rmt::Vector& rPosition();
+ void GetPosition( rmt::Vector* ipPosn );
+ ///////////////////////////////////////////////////////////////////////////
+
+
+protected:
+ Road* mRoad;
+ unsigned int mSegmentIndex;
+
+private:
+
+#ifdef RAD_DEBUG
+ enum { MAX_NAME_LEN = 40 };
+ char mName[ MAX_NAME_LEN];
+#endif
+
+ rmt::Vector mCorners[ 4 ]; // The rectangle with extra vertices at the leading and trailing edge midpoints.
+ rmt::Vector mEdgeNormals[ 4 ]; // The inward pointing edge normals.
+ rmt::Vector mNormal; // The surface normal.
+
+ float mfSegmentLength;
+ float mfLaneWidth;
+ float mfRadius;
+ float mfAngle;
+ rmt::Sphere mSphere;
+
+};
+
+inline const char* RoadSegment::GetName()
+{
+#ifdef TOOLS
+ return tEntity::GetName();
+#endif
+
+#ifdef RAD_DEBUG
+ return mName;
+#else
+ return NULL;
+#endif
+}
+inline void RoadSegment::SetName( const char* name )
+{
+#ifdef TOOLS
+ tEntity::SetName( name );
+#endif
+#ifdef RAD_DEBUG
+ strncpy( mName, name, MAX_NAME_LEN > strlen(name) ? strlen(name) : MAX_NAME_LEN );
+ mName[strlen(name)] = '\0';
+#endif
+}
+
+inline Road* RoadSegment::GetRoad()
+{
+ return mRoad;
+}
+inline void RoadSegment::SetRoad( Road* road )
+{
+ mRoad = road;
+}
+inline void RoadSegment::SetSegmentIndex( unsigned int index )
+{
+ mSegmentIndex = index;
+}
+inline unsigned int RoadSegment::GetSegmentIndex()
+{
+ return mSegmentIndex;
+}
+inline void RoadSegment::DisplayBoundingBox(tColour colour)
+{
+ rAssert( false );
+}
+inline void RoadSegment::DisplayBoundingSphere(tColour colour)
+{
+ rAssert( false );
+}
+inline void RoadSegment::Display()
+{
+ rAssert( false ); // deprecated
+}
+inline rmt::Vector* RoadSegment::pPosition()
+{
+ rAssert( false ); // deprecated; result unreliable
+ return &(mSphere.centre);
+}
+inline const rmt::Vector& RoadSegment::rPosition()
+{
+ rAssert( false ); // deprecated; result unreliable
+ return mSphere.centre;
+}
+inline void RoadSegment::GetPosition( rmt::Vector* ipPosn )
+{
+ *ipPosn = mSphere.centre;
+}
+inline float RoadSegment::GetSegmentLength()
+{
+ return mfSegmentLength;
+}
+inline float RoadSegment::GetLaneWidth()
+{
+ return mfLaneWidth;
+}
+
+
+
+/*
+
+///////////////////////////////////////////////////////////////////////////
+// class TransformRoadSegment
+///////////////////////////////////////////////////////////////////////////
+// Derived class = Base + 16*4 bytes
+//
+class TransformRoadSegment
+:
+public RoadSegment
+{
+public:
+ TransformRoadSegment();
+
+ TransformRoadSegment( const RoadSegmentData* pRoadSegmentData,
+ rmt::Matrix& transform
+ );
+
+ TransformRoadSegment( const RoadSegmentData* pRoadSegmentData,
+ rmt::Matrix& transform,
+ float fScaleAlongFacing
+ );
+
+ TransformRoadSegment( const RoadSegmentData* pRoadSegmentData,
+ const rmt::Vector& facing,
+ const rmt::Vector& position
+ );
+
+ TransformRoadSegment( const RoadSegmentData* pRoadSegmentData,
+ const rmt::Vector& facing,
+ const rmt::Vector& position,
+ float fScaleAlongFacing
+ );
+
+ virtual void GetTransform( rmt::Matrix& out ) const;
+ void SetTransform( rmt::Matrix& transform );
+ void SetScaleAlongFacing( float scale );
+
+ /////////////////////////////////////////////////
+ // Implements RoadSegment.
+ //
+ void GetCorner( int index, rmt::Vector& out ) const;
+ void GetEdgeNormal( int index, rmt::Vector& out ) const;
+ void GetSegmentNormal( rmt::Vector& out ) const;
+ //void GetJoinPoint( rmt::Vector& position, rmt::Vector& facing ) const;
+ virtual void GetBoundingBox( rmt::Box3D& out ) const;
+ virtual void GetBoundingSphere( rmt::Sphere& out ) const;
+
+ //////////////////////////////////////////////////////////////////////////
+ // IEntityDSG Interface
+ //////////////////////////////////////////////////////////////////////////
+ virtual void GetBoundingBox(rmt::Box3D* box);
+ virtual void GetBoundingSphere(rmt::Sphere* sphere);
+ void GetPosition( rmt::Vector* ipPosn );
+
+private:
+ rmt::Matrix mTransform;
+
+ float mfScaleAlongFacing;
+};
+
+inline void TransformRoadSegment::SetTransform( rmt::Matrix& transform )
+{
+ mTransform = transform;
+}
+inline void TransformRoadSegment::SetScaleAlongFacing( float scale )
+{
+ mfScaleAlongFacing = scale;
+}
+inline void TransformRoadSegment::GetPosition( rmt::Vector* ipPosn )
+{
+ *ipPosn = GetRoadSegmentData()->GetBoundingSphere().centre;
+ ipPosn->Transform( mTransform );
+}
+*/
+
+
+#endif \ No newline at end of file
diff --git a/game/code/roads/roadsegmentdata.cpp b/game/code/roads/roadsegmentdata.cpp
new file mode 100644
index 0000000..ff27bca
--- /dev/null
+++ b/game/code/roads/roadsegmentdata.cpp
@@ -0,0 +1,211 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: RoadSegment
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2002/02/25 Tbrown-John Created
+
+===========================================================================*/
+#include <memory/classsizetracker.h>
+#include <roads/roadsegmentdata.h>
+
+// System.
+//
+#include <raddebug.hpp>
+
+/*
+
+ Input parameters:
+
+ O----------> v0
+ | |
+ | |
+ | |
+ | |
+ v v
+ v2 v1
+
+ O = ( 0.0f, 0.0f, 0.0f ) LCS origin.
+
+ # of lanes.
+
+ create this:
+
+ |
+ N1 \ /
+ v0_________________________v1----> facing
+ | |
+ -> N0 | --> direction | -> N2
+ |_________________________|
+ v3 v2
+ N3 / \
+ |
+ N is UP
+ N0 is ->
+
+ N1 is |
+ \ /
+
+ N2 is ->
+
+ N3 is / \
+ |
+ */
+RoadSegmentData::RoadSegmentData() :
+ mnLanes( 0 )
+{
+ CLASSTRACKER_CREATE( RoadSegmentData );
+ unsigned int i;
+ for ( i = 0; i < 4; ++i )
+ {
+ mCorners[i].Set(0.0f, 0.0f, 0.0f);
+ mEdgeNormals[i].Set(0.0f, 0.0f, 0.0f);
+ }
+
+ mNormal.Set(0.0f, 0.0f, 0.0f);
+
+}
+
+RoadSegmentData::RoadSegmentData(
+ const rmt::Vector& v0,
+ const rmt::Vector& v1,
+ const rmt::Vector& v2,
+ unsigned int nLanes )
+{
+ CLASSTRACKER_CREATE( RoadSegmentData );
+ SetData( v0, v1, v2, nLanes );
+}
+
+RoadSegmentData::~RoadSegmentData()
+{
+ CLASSTRACKER_DESTROY( RoadSegmentData );
+}
+
+//=============================================================================
+// RoadSegmentData::SetData
+//=============================================================================
+// Description: Comment
+//
+// Parameters: ( const rmt::Vector& v0, const rmt::Vector& v1, const rmt::Vector& v2, unsigned int nLanes, bool hasShoulder )
+//
+// Return: void
+//
+//=============================================================================
+void RoadSegmentData::SetData( const rmt::Vector& v0,
+ const rmt::Vector& v1,
+ const rmt::Vector& v2,
+ unsigned int nLanes )
+{
+ mnLanes = nLanes;
+
+ // Calculate the up vector for this piece.
+ //
+ mNormal.CrossProduct( v0, v2 );
+ mNormal.Normalize( );
+
+ rmt::Vector origin( 0.0f, 0.0f, 0.0f );
+
+ mCorners[ 0 ] = origin;
+ mCorners[ 1 ] = v0;
+ mCorners[ 2 ] = v1;
+ mCorners[ 3 ] = v2;
+
+ rmt::Vector temp;
+
+ // Calculate the edge normals.
+ temp.Sub( mCorners[ 0 ], mCorners[ 3 ] );
+ mEdgeNormals[ 0 ].CrossProduct( mNormal, temp );
+ mEdgeNormals[ 0 ].Normalize( );
+
+ temp.Sub( mCorners[ 1 ], mCorners[ 0 ] );
+ mEdgeNormals[ 1 ].CrossProduct( mNormal, temp );
+ mEdgeNormals[ 1 ].Normalize( );
+
+ temp.Sub( mCorners[ 1 ], mCorners[ 2 ] );
+ mEdgeNormals[ 2 ].CrossProduct( mNormal, temp );
+ mEdgeNormals[ 2 ].Normalize( );
+
+ temp.Sub( mCorners[ 3 ], mCorners[ 2 ] );
+ mEdgeNormals[ 3 ].CrossProduct( mNormal, temp );
+ mEdgeNormals[ 3 ].Normalize( );
+
+
+}
+
+/*
+==============================================================================
+RoadSegmentData::GetCorner
+==============================================================================
+Description: Comment
+
+
+Parameters: ( int index ), which box corner are we interested in.
+
+Return: const rmt::Vector& - a copy of the vertex location in local space.
+
+=============================================================================
+*/
+const rmt::Vector& RoadSegmentData::GetCorner( int index ) const
+{
+ rAssert( index < 4 );
+ return mCorners[ index ];
+}
+/*
+==============================================================================
+RoadSegmentData::GetEdgeNormal
+==============================================================================
+Description: Return the normal to the edge. Define CW, starting
+ with leading edge. v4.Sub( v0 ) = leading edge.
+
+Parameters: ( int index )
+
+Return: const
+
+=============================================================================
+*/
+const rmt::Vector& RoadSegmentData::GetEdgeNormal( int index ) const
+{
+ rAssert( index < 4 );
+ return mEdgeNormals[ index ];
+}
+
+/*
+==============================================================================
+RoadSegmentData::GetSegmentNormal
+==============================================================================
+Description: Return the normal to the planar segment surface.
+
+Parameters: ( void )
+
+Return: const rmt::Vector&
+
+=============================================================================
+*/
+const rmt::Vector& RoadSegmentData::GetSegmentNormal( void ) const
+{
+ return mNormal;
+}
+
+/*
+==============================================================================
+RoadSegmentData::GetNumLanes
+==============================================================================
+Description: Return the number of lanes, on the left side if bIsLeft is true.
+ Else, the number of lanes on the right side.
+
+Parameters: ( void )
+
+Return: unsigned int, the number of lanes.
+
+=============================================================================
+*/
+unsigned int RoadSegmentData::GetNumLanes( void ) const
+{
+ return mnLanes;
+}
diff --git a/game/code/roads/roadsegmentdata.h b/game/code/roads/roadsegmentdata.h
new file mode 100644
index 0000000..0073748
--- /dev/null
+++ b/game/code/roads/roadsegmentdata.h
@@ -0,0 +1,61 @@
+#ifndef ROADSEGMENTDATA_H_
+#define ROADSEGMENTDATA_H_
+
+#include <radmath/radmath.hpp>
+#include <p3d/entity.hpp>
+
+#define LERP( fUnit, fV0, fV1 ) ( (1.0f-(fUnit))*fV0 + (fUnit)*fV1 )
+
+class RoadSegmentData
+{
+public:
+ RoadSegmentData();
+
+ RoadSegmentData( const rmt::Vector& v0,
+ const rmt::Vector& v1,
+ const rmt::Vector& v2,
+ unsigned int nLanes );
+
+ ~RoadSegmentData();
+ void SetData( const rmt::Vector& v0,
+ const rmt::Vector& v1,
+ const rmt::Vector& v2,
+ unsigned int nLanes );
+
+ const rmt::Vector& GetCorner( int index ) const;
+ const rmt::Vector& GetEdgeNormal( int index ) const;
+ const rmt::Vector& GetSegmentNormal( void ) const;
+ unsigned int GetNumLanes( void ) const;
+
+ void SetName( const char* name );
+ tUID GetNameUID() const;
+
+private:
+ // The rectangle with extra vertices at the leading and trailing
+ // edge midpoints.
+ //
+ rmt::Vector mCorners[ 4 ];
+
+ // The inward pointing edge normals.
+ //
+ rmt::Vector mEdgeNormals[ 4 ];
+
+ // The surface normal.
+ //
+ rmt::Vector mNormal;
+
+ unsigned int mnLanes;
+
+ tUID nameUID;
+};
+
+inline void RoadSegmentData::SetName( const char* name )
+{
+ nameUID = tEntity::MakeUID( name );
+}
+inline tUID RoadSegmentData::GetNameUID() const
+{
+ return nameUID;
+}
+
+#endif \ No newline at end of file
diff --git a/game/code/roads/trafficcontrol.cpp b/game/code/roads/trafficcontrol.cpp
new file mode 100644
index 0000000..8ef2908
--- /dev/null
+++ b/game/code/roads/trafficcontrol.cpp
@@ -0,0 +1,98 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: Traffic Control
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2001/02/02 Tbrown-John Created
+
+===========================================================================*/
+
+#include <roads/trafficcontrol.h>
+#include <roads/intersection.h>
+
+void TrafficLight::Update( unsigned int dt )
+{
+ m_uiElapsedTime += dt;
+
+ if ( m_uiElapsedTime > m_uiSwitchTime )
+ {
+ m_uiSwitchTime = m_uiElapsedTime + TrafficLightSwitchTime;
+ SwitchControl();
+ }
+}
+
+void TrafficLight::SwitchControl( void )
+{
+ m_tState++;
+
+ m_tState = m_tState % NUM_STATES;
+
+ if ( ADVANCE_GREEN == m_tState )
+ {
+ // we must have rolled through all the other states, so change the direction.
+ // do a bitwise not.
+ m_tRoadsToGo = ~m_tRoadsToGo;
+ // mask out the high bits, for clarity.
+ m_tRoadsToGo = m_tRoadsToGo & 0x0000000F;
+ }
+ // notify the intersection of the control change.
+ m_pIntersection->AdvanceTraffic( m_tRoadsToGo, m_tState );
+}
+
+
+
+
+void NWayStop::Update( unsigned int dt )
+{
+ //
+ // After elapsed time, tell next road to go. The road should tell all
+ // of its lanes to go.
+ //
+ Intersection* intersection = (Intersection*)m_pIntersection;
+ if( intersection->mWaitingRoads.mUseSize > 0 )
+ {
+ if( mTurnTimeLeft < 0 )
+ {
+ mTurnTimeLeft = NWAY_TURN_MILLISECONDS;
+
+ // tell the road to go...
+ //rAssert( m_pIntersection->GetType() == Intersection::N_WAY );
+
+ // damn constants
+ ((Intersection*)m_pIntersection)->AdvanceNextWaitingRoad();
+ }
+ else
+ {
+ mTurnTimeLeft -= dt;
+ }
+ }
+ else
+ {
+ mTurnTimeLeft = NWAY_TURN_MILLISECONDS;
+ }
+ /*
+ if ( m_pIntersection->IsIntersectionClear() )
+ {
+ m_tState++;
+
+ m_tState = m_tState % NUM_STATES;
+
+ // do a bitwise not.
+ m_tRoadsToGo = ~m_tRoadsToGo;
+ // mask out the high bits, for clarity.
+ m_tRoadsToGo &= 0x0000000F;
+
+ m_pIntersection->AdvanceTraffic( m_tRoadsToGo, m_tState );
+ }
+ */
+}
+
+void CourtesyStop::Update( unsigned int dt )
+{
+} \ No newline at end of file
diff --git a/game/code/roads/trafficcontrol.h b/game/code/roads/trafficcontrol.h
new file mode 100644
index 0000000..93cc4b5
--- /dev/null
+++ b/game/code/roads/trafficcontrol.h
@@ -0,0 +1,106 @@
+/*===========================================================================
+ Copyright (C) 2000 Radical Entertainment Ltd. All rights reserved.
+
+ Component: Traffic Control
+
+ Description:
+
+
+ Authors: Travis Brown-John
+
+ Revisions Date Author Revision
+ 2001/02/02 Tbrown-John Created
+
+===========================================================================*/
+
+#ifndef TRAFFICCONTROL_HPP_
+#define TRAFFICCONTROL_HPP_
+
+class Intersection;
+
+// An Object that controls the flow of traffic through an intersection.
+class TrafficControl
+{
+public:
+ enum
+ {
+ RED,
+ YELLOW,
+ GREEN,
+ ADVANCE_GREEN,
+ NUM_STATES
+ };
+ enum
+ {
+ ROAD_ZERO = 1 << 0,
+ ROAD_ONE = 1 << 1,
+ ROAD_TWO = 1 << 2,
+ ROAD_THREE = 1 << 3
+ };
+ // constructor.
+ TrafficControl() : m_pIntersection( 0 ) {}
+ // destructor.
+ virtual ~TrafficControl() {}
+ // returns which intersection this traffic control belongs to.
+ const Intersection *GetIntersection( void ) const { return m_pIntersection; }
+ // sets which intersection this traffic control belongs to.
+ void SetIntersection( const Intersection *pIntersection ) { m_pIntersection = pIntersection; }
+
+ // update the traffic control state. Each one follows different logic.
+ virtual void Update( unsigned int dt ) = 0;
+protected:
+ // the intersection this traffic control belongs to.
+ const Intersection *m_pIntersection;
+ // the state of the traffic light in the green direction. All other directions STOP.
+ unsigned int m_tState;
+ // a bitmask representing which roads the traffic control advance commands applies to.
+ unsigned int m_tRoadsToGo;
+
+};
+
+// Allows flow of traffic through a 4 way intersection in 2 opposing, non crossing roads at a time.
+class TrafficLight
+:
+public TrafficControl
+{
+public:
+ TrafficLight() : TrafficControl(), m_uiElapsedTime( 0 ), m_uiSwitchTime( 0 ) {}
+ void Update( unsigned int dt );
+private:
+ void SwitchControl( void );
+ enum eTrafficLightSwitchTime
+ {
+ TrafficLightSwitchTime = 10000
+ };
+ // the elapsed time.
+ unsigned int m_uiElapsedTime;
+ // the control signal should switch when the m_uiElapsedTime reaches this value.
+ unsigned int m_uiSwitchTime;
+};
+
+// Allows flow of traffic through an N way intersection, 2 lanes at a time in a CW order.
+class NWayStop
+:
+public TrafficControl
+{
+public:
+ NWayStop() : TrafficControl(), mTurnTimeLeft( NWAY_TURN_MILLISECONDS ) {}
+ void Update( unsigned int dt );
+ enum eTrafficTurnTime
+ {
+ NWAY_TURN_MILLISECONDS = 3500
+ };
+private:
+ int mTurnTimeLeft;
+};
+
+// advances cars when intersection is clear. stopped cars are advanced in a CW order.
+class CourtesyStop
+:
+public TrafficControl
+{
+public:
+ void Update( unsigned int dt );
+};
+
+#endif \ No newline at end of file