diff options
Diffstat (limited to 'game/code/roads')
-rw-r--r-- | game/code/roads/allroads.cpp | 10 | ||||
-rw-r--r-- | game/code/roads/geometry.cpp | 1024 | ||||
-rw-r--r-- | game/code/roads/geometry.h | 448 | ||||
-rw-r--r-- | game/code/roads/intersection.cpp | 1374 | ||||
-rw-r--r-- | game/code/roads/intersection.h | 312 | ||||
-rw-r--r-- | game/code/roads/lane.cpp | 187 | ||||
-rw-r--r-- | game/code/roads/lane.h | 187 | ||||
-rw-r--r-- | game/code/roads/road.cpp | 830 | ||||
-rw-r--r-- | game/code/roads/road.h | 249 | ||||
-rw-r--r-- | game/code/roads/roadmanager.cpp | 2565 | ||||
-rw-r--r-- | game/code/roads/roadmanager.h | 318 | ||||
-rw-r--r-- | game/code/roads/roadrender.cpp | 401 | ||||
-rw-r--r-- | game/code/roads/roadrendertest.cpp | 271 | ||||
-rw-r--r-- | game/code/roads/roadrendertest.h | 60 | ||||
-rw-r--r-- | game/code/roads/roadsegment.cpp | 792 | ||||
-rw-r--r-- | game/code/roads/roadsegment.h | 267 | ||||
-rw-r--r-- | game/code/roads/roadsegmentdata.cpp | 211 | ||||
-rw-r--r-- | game/code/roads/roadsegmentdata.h | 61 | ||||
-rw-r--r-- | game/code/roads/trafficcontrol.cpp | 98 | ||||
-rw-r--r-- | game/code/roads/trafficcontrol.h | 106 |
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 |