Data Structures
//////////////////////////////
// Singly linked list
//////////////////////////////
template<typename T>
class SingleLinkList
{
private:
struct Node
{
Node* next;
T data;
};
Node* head;
int size;
public:
SingleLinkList() : head(nullptr), size(0) {};
void addHead(const T& _data)
{
node* tmp = new node;
tmp->data = _data;
tmp->next = head;
head = tmp;
++Size;
};
void remove(Iterator<T>& index)
{
Node* tmp = head;
Node* tmp2 = head;
if (index.looker == nullptr)
return;
if (index.looker == head)
{
head = head->next;
index.looker = head;
index.headList = head;
delete tmp;
--Size;
}
else
{
for (int i = 0; i < Size - 1; i++)
{
if (tmp == index.looker)
break;
else
{
tmp2 = tmp;
tmp = tmp->next;
}
}
tmp2->next = tmp->next;
delete tmp;
--Size;
};
void clear()
{
Node* tmp = head;
while (head)
{
head = head->next;
delete tmp;
tmp = head;
}
Size = 0;
};
};
Rigidbody Physics
void HandleCollision(RIGIDBODY& body1, RIGIDBODY& body2, TCOLLISION& theCollision, float dt)
{
float e; // average coefficient of restitution
Vector3D J; // impulse vector
Vector3D impulseForce; // the impulsive force
Vector3D n; // the normalized vector of the collision normal vector
Vector3D Vr; // relative velocity in the collision normal direction
// contact vectors
Vector3D r1;// contact vector from body1
Vector3D r2; // contact vector from body2
Matrix3D I = Identity(); // identity matrix
// compute the coefficient of restitution(=e) of the 2 colliding bodies
e = max(body1.coefficientOfRestitution, body2.coefficientOfRestitution);
//compute collision Normal N= C1C2=C2-C1 where C1=ball1 center position ,C2=ball2 center position
theCollision.normal = body2.position - body1.position;
// normalize the collision normal
theCollision.normal = theCollision.normal.Normalize();
// assign n to the normalized collision normal computed above : n=(C2-C1)/||C2-C1||
n = theCollision.normal;
// compute body1 inverse Inertia tensor(=inertiaInv)
body1.inertiaInv = body1.inertia.Inverse();
// compute body2 inverse Inertia tensor (=inertiaInv)
body2.inertiaInv = body2.inertia.Inverse();
// calculate the collision contact point(=ContactLocation) of body1 in world space
body1.contactLocation = body1.position + body1.radius*n;
// calculate the contact vector of body1(=r1)
r1 = body1.contactLocation - body1.position;
// calculate the collision contact point(=ContactLocation) of body2 in world space
body2.contactLocation = body2.position - body2.radius*n;
// calculate the contact vector of body2(=r2)
r2 = body2.contactLocation - body2.position;
// compute the collision points relative velocity(=vr)
Vr = body1.velocity - body2.velocity + ((body1.angularVelocity ^ r1) - (body2.angularVelocity ^ r2));
//Set the Collision(=theCollision) relative Velocity equal to Vr
theCollision.relativeVelocity = Vr;
// Mass matrix or collision matrix
Matrix3D K;
//compute the collision matrix or mass matrix K
K = ((body1.massInv) + (body2.massInv))*I - ((Skew(r1)*body1.inertiaInv*Skew(r1)) + (Skew(r2)*body2.inertiaInv*Skew(r2)));
// Compute the impulse magnitude j
float j = (-(1 + e)*Vr*n) / (n*K*n);
// compute collision impulse vector(=J)
J = j * n;
// compute body1 impulse
body1.impulse = J;
// compute body2 impulse
body2.impulse = -J;
// compute body1 impulsive forces (=impulseForce)
body1.impulseForce = J / dt;
// compute body2 impulsive forces (=impulseForce)
body2.impulseForce = -J / dt;
// compute body1 velocity(=velocity) after collision: v1=v1+ J/m1
body1.velocity = body1.velocity + (J / body1.mass);
// compute body1 velocity(=velocity) after collision: v2=v2 - J/m2
body2.velocity = body2.velocity - (J / body2.mass);
// set the total force on body1 during collision time to be equal to the impulsive Force: totalForce= impulseForce
body1.totalForces = body1.impulseForce;
// set the total force on body2 during collision time to be equal to the impulsiveForce: totalForce= impulseForce
body2.totalForces = body2.impulseForce;
// compute body1 torque. remember torque= ContactVector X impulseForce
body1.torque = (body1.contactLocation - body1.position) ^ body1.impulseForce;
// compute body2 torque. remember torque= ContactVector X impulseForce
body2.torque = (body2.contactLocation - body2.position) ^ body2.impulseForce;
J = n = r1 = r2 = Vector3D();
}
Path Finding
///////////////////////////////////////////////
// A* path search through a 2d grid of tiles
///////////////////////////////////////////////
void PathSearch::enter(int startRow, int startColumn, int goalRow, int goalColumn)
{
Goal = NodeMap[tilemap->getTile(goalRow, goalColumn)];
node = new PlannerNode;
node->vertex = NodeMap[tilemap->getTile(startRow, startColumn)];
node->parent = nullptr;
node->heuristicCost = estimate(node->vertex, Goal);
node->givenCost = 0;
node->finalCost = node->givenCost + node->heuristicCost * hWeight;
VisitedMap[node->vertex] = node;
open.push(node);
}
void PathSearch::update(long timeslice)
{
while (!open.empty())
{
node = open.front();
open.pop();
//Is it the Goal?
if (node->vertex == Goal)
{
PrevNode = node;
while (PrevNode != nullptr)
{
endpath.push_back(PrevNode->vertex->tile);
PrevNode = PrevNode->parent;
}
}
//Get its children/edges and add them to the queue
for (int i = node->vertex->edges.size() - 1; i >= 0 ; --i)
{
suc = NodeMap[node->vertex->edges[i]];
tempNode = VisitedMap[suc];
tempGivenCost = node->givenCost + node->vertex->edges[i]->getWeight();
if (tempNode)
{
if (tempGivenCost < tempNode->givenCost)
{
open.remove(tempNode);
tempNode->givenCost = tempGivenCost;
tempNode->finalCost = tempNode->givenCost + tempNode->heuristicCost * hWeight;
tempNode->parent = node;
open.push(tempNode);
}
}
else
{
Newnode = PlannerNodeContainer.Get();
Newnode->parent = node;
Newnode->vertex = suc;
Newnode->heuristicCost = estimate(Newnode->vertex, Goal);
Newnode->givenCost = tempGivenCost;
Newnode->finalCost = tempGivenCost + Newnode->heuristicCost * hWeight;
VisitedMap[suc] = Newnode;
open.push(Newnode);
}
}
}
}
Timer
#pragma once
#ifndef TIME
#define TIME
#ifndef WINAPI
#define NOMINMAX
#ifdef APIENTRY
#undef APIENTRY
#endif
#include "Windows.h"
#endif // !WINAPI
#define TIME_MIN(a,b) (a < b) ? a : b
#define TIME_MAX(a,b) (a > b) ? a : b
///////////////////////////////////////////////////////////////////////
//ALL TIME IS IN SECONDS
///////////////////////////////////////////////////////////////////////
//Used for the number of past samples to keep for smooth delta time
#define TIME_NUMSAMPLES 10
//This class can be turned into a singleton if no other instance is needed
//
//This is how to do that
//
//Move the constructor and destructor into the private section
//Add this function in public
/*
static Time GetTime()
{
static Time instance;
return instance;
}
*/
class Time
{
private:
friend class Timer;
//For use in program
float _deltaTime;
double _doubleDeltaTime;
float _smoothDeltaTime;
double _doubleSmoothDeltaTime;
float _elapsedTime;
float _elapsedTimeWithScale;
float _fixedDeltaTime;
float _timeScale;
float _fixedTimeScale;
float _fixedTimeCounter;
float _maxDeltaTime;
//For use behind scenes
long long _prevTicksCount[TIME_NUMSAMPLES];
long long _firstTickCount;
long long _frequency;
unsigned char _signalCount;
unsigned char _elapsedSignals;
public:
Time()
{
ZeroMemory(_prevTicksCount, sizeof(_prevTicksCount));
_signalCount = _elapsedSignals = 0;
_doubleDeltaTime = _doubleSmoothDeltaTime = 0.0;
_firstTickCount = _frequency = 0;
_deltaTime = _smoothDeltaTime = _elapsedTime = _elapsedTimeWithScale = 0.0f;
_maxDeltaTime = 100.0f;
_fixedDeltaTime = 0.016667f;
_timeScale = _fixedTimeScale = 1.0f;
Restart();
};
~Time()
{
ZeroMemory(_prevTicksCount, sizeof(_prevTicksCount));
_signalCount = _elapsedSignals = 0;
_doubleDeltaTime = _doubleSmoothDeltaTime = 0.0;
_firstTickCount = _frequency = 0;
_deltaTime = _smoothDeltaTime = _elapsedTime = _elapsedTimeWithScale = 0.0f;
_fixedDeltaTime = 0.0f;
_timeScale = _fixedTimeScale = 0.0f;
};
//Time elapsed since last call to Signal() or Restart()
float deltaTime() { return _deltaTime; }
//Time elapsed since last call to Signal() or Restart() in double
double doubleDeltaTime() { return _doubleDeltaTime; }
//Average of the past 10 delta's. i.e smoother delta time
float smoothDeltaTime() { return _smoothDeltaTime; }
//Average of the past 10 delta's. i.e smoother delta time
double doubleSmoothDeltaTime() { return _doubleSmoothDeltaTime; }
//Complete elapsed time since last call to Restart()
float elapsedTime() { return _elapsedTime; }
//Complete elapsed time since last call to Restart() IS AFFECTED BY TIMESCALE
float elapsedTimeWithScale() { return _elapsedTimeWithScale; }
//Returns the time interval for fixed updates such as physics
float fixedDeltaTime() { return _fixedDeltaTime; }
//Returns the time multiplier for delta time
float timeScale() { return _timeScale; }
//Returns the time multiplier for fixed time
float fixedTimeScale() { return _fixedTimeScale; }
//Change the time scale more is faster less is slower
void timeScale(float TimeScale) { _timeScale = TimeScale; }
//Change the fixed time scale more is faster less is slower
void fixedTimeScale(float FixedTimeScale) { _fixedTimeScale = FixedTimeScale; }
//Change the rate at which fixed time functions are called lower is more called
void fixedDeltaTime(float FixedDeltaTime) { _fixedDeltaTime = FixedDeltaTime; }
//Called to see if its time to do fixed stuff
bool fixedTimeCall()
{
if (_fixedTimeCounter >= _fixedDeltaTime)
{
_fixedTimeCounter = 0.0f;
return true;
}
return false;
}
//Used to clamp the deltaTime to a max value -- Very helpful for debugging
void setMaxDeltaTime(float max)
{
_maxDeltaTime = max;
}
//Used at the beginning of each loop cycle
void Signal()
{
memmove_s(_prevTicksCount + 1u, sizeof(long long) * TIME_NUMSAMPLES, _prevTicksCount, sizeof(long long) * TIME_NUMSAMPLES);
QueryPerformanceCounter((LARGE_INTEGER*)_prevTicksCount);
_signalCount = TIME_MIN(_signalCount + 1, TIME_NUMSAMPLES - 1);
_doubleDeltaTime = double(_prevTicksCount[0] - _prevTicksCount[1]) / double(_frequency);
_elapsedTime += (float)_doubleDeltaTime;
_fixedTimeCounter += (float)_doubleDeltaTime * _fixedTimeScale;
_doubleDeltaTime *= _timeScale;
if (_doubleDeltaTime > _maxDeltaTime) _doubleDeltaTime = (double)_maxDeltaTime;
_deltaTime = float(_doubleDeltaTime);
_elapsedTimeWithScale += _deltaTime;
double totalWeight = 0, runningWeight = 1;
LONGLONG totalValue = 0, sampleDelta;
unsigned char size = TIME_MIN(TIME_NUMSAMPLES, _signalCount - 1);
// loop up to num samples or as many as we have available
for (unsigned char i = 0; i < size; ++i)
{
// determine each delta as we go
sampleDelta = _prevTicksCount[i] - _prevTicksCount[i + 1];
totalValue += LONGLONG(sampleDelta * runningWeight + 0.5); // this cast is expensive, need to look into optimizing
totalWeight += runningWeight; // tally all the weights used
runningWeight *= 0.75; // adjust the weight of next delta
}
_doubleSmoothDeltaTime = (totalValue / totalWeight) / double(_frequency);
_doubleSmoothDeltaTime *= _timeScale;
_smoothDeltaTime = float(_doubleSmoothDeltaTime);
};
//Used to clean up an start new
void Restart()
{
QueryPerformanceFrequency((LARGE_INTEGER*)&_frequency);
_signalCount = _elapsedSignals = 0;
_doubleDeltaTime = _doubleSmoothDeltaTime = _fixedTimeCounter = 0.0;
_deltaTime = _smoothDeltaTime = _elapsedTime = _elapsedTimeWithScale = 0.0f;
_timeScale = _fixedTimeScale = 1.0f;
QueryPerformanceCounter((LARGE_INTEGER*)&_firstTickCount);
_prevTicksCount[_signalCount++] = _firstTickCount;
};
};
class Timer
{
private:
const Time* _friendTime;
float _elapsedTime;
float _executeInterval;
bool _includeScale;
//For use behind scenes
long long _prevTickCount;
long long _thisTickCount;
long long _frequency;
public:
//This Constructor is basicly a smaller version on the Time class
//float executionInterval is the time interval in which you want something to happen... or not
Timer(float executionInterval)
{
_includeScale = false;
_frequency = 0;
_elapsedTime = 0.0f;
_executeInterval = executionInterval;
_friendTime = nullptr;
QueryPerformanceFrequency((LARGE_INTEGER*)&_frequency);
}
//Makes the Time class a parent so that we can get the delta information from it fast and easy
//This is an easy way to do the timer if you have access to the Time that is assotiated with it
//float executionInterval is the time interval in which you want something to happen... or not
//Time* parentTime is used to get the deltaTime/elapsedTime
//bool includeScale if you want the timer to be affected by the timeScale or not default is false
Timer(float executionInterval, const Time* parentTime, bool includeScale = false)
{
_includeScale = includeScale;
_frequency = 0;
_elapsedTime = 0.0f;
_executeInterval = executionInterval;
_friendTime = parentTime;
if (includeScale)
_elapsedTime = _friendTime->_elapsedTimeWithScale;
else
_elapsedTime = _friendTime->_elapsedTime;
}
~Timer()
{
_friendTime = nullptr;
_frequency = 0;
_elapsedTime = 0.0f;
_prevTickCount = 0;
_thisTickCount = 0;
}
//Used to check if the specified executeInterval has elapsed
//Can be called regardless of the constructor used
bool canExecute()
{
if (_friendTime)
{
if (_includeScale)
{
if (_friendTime->_elapsedTimeWithScale - _elapsedTime >= _executeInterval)
{
_elapsedTime = _friendTime->_elapsedTimeWithScale;
return true;
}
}
else
{
if (_friendTime->_elapsedTime - _elapsedTime >= _executeInterval)
{
_elapsedTime = _friendTime->_elapsedTime;
return true;
}
}
}
else
{
QueryPerformanceCounter((LARGE_INTEGER*)&_thisTickCount);
_elapsedTime += float(_thisTickCount - _prevTickCount ) / float(_frequency);
_prevTickCount = _thisTickCount;
if (_elapsedTime >= _executeInterval)
{
_elapsedTime = 0;
return true;
}
}
return false;
}
//Allows you to skip all quering of time and just directly pass in the deltaTime -- can be used regardless of constructor
//Returns true if the alloted time has passed
bool canExecute(float deltaTime)
{
_elapsedTime += deltaTime;
if (_elapsedTime >= _executeInterval)
{
_elapsedTime = 0;
return true;
}
return false;
}
//If the Time constructor was used then this will change wether or not timeSacle is used
void IncludeScale(bool useScale)
{
_includeScale = useScale;
}
};
#endif
/*
Example on how to use.
int main ()
{
App app;
Time timer;
timer.Restart() //Not needed but I like to make sure that its ready for useTime timer;
while(true) // Game Loop
{
timer.Signal(); // Just call Signal at the beginning of the game loop
app.update();//If its not a singleton then make sure you either pass in deltatime or have app(whatever your game stuff is) have a time member
if(timer.fixedTimeCall())
{
app.fixedUpdate();
}
app.render();
}
}
*/
