Tech Demos
Here are some of my technical demonstrations showcasing various algorithms, tools, and techniques I've worked on.
A* Pathfinding Algorithm
Description: This demo showcases a pathfinding algorithm implemented in cpp. The algorithm finds the shortest path between two points in a map,considering unreachable nodes.
Technologies Used: C++, easyx
/* Astar path finding algorithm
* return a vector of nodes
* empty vector means no path was found
*/
vector> PathFinder::FindPathAstar(pair start, pair end) {
vector> path;
if (node_matrix[end.first][end.second].flag == NOPASS) {
//unreachable
cerr << "failed to find path" << endl;
return path;
}
priority_queue, CompareNode> open_list = {};
vector> astarNodes(ROW_TOTAL, vector(COL_TOTAL));
//initialize all nodes with x,y,z value
for (int i = 0; i < ROW_TOTAL; i++) {
for (int j = 1; j < COL_TOTAL; j++) {
astarNodes[i][j].row = i;
astarNodes[i][j].col = j;
astarNodes[i][j].pass = node_matrix[i][j].flag;
}
}
//game map node matrix
AstarNode* curr = &(astarNodes[start.first][start.second]);
curr->row = start.first;
curr->col = start.second;
curr->close = false;
curr->open = true;
curr->G = 0;
curr->H = Manhattan(start.first, start.second, end.first, end.second);
curr->F = curr->G + curr->H;
open_list.push(curr);
while (!open_list.empty()) {
curr = open_list.top();
open_list.pop();
curr->open = false;
curr->close = true;
//end loop if reach destination node
if (curr->row == end.first && curr->col == end.second) {
break;
}
TheGameMap::Instance()->HightlightGrid(curr->row, curr->col);
/*FlushBatchDraw();
Sleep(50);*/
//get all neighbors
vector> neighbors = GetNeighbors(curr);
for (auto it = neighbors.begin(); it != neighbors.end(); it++) {
AstarNode* node = &(astarNodes[it->first][it->second]);
//pass node which is unreachable or in close list
if (node->close || node->pass == NOPASS) {
continue;
}
else if (node_matrix[it->first][it->second].x == 0) {
continue;
}
//if in open list
if (node->open) {
//Calculate the G value from the start point to the node, passing through curr.
int G = curr->G + 1;
if (G < node->G) {
//if new G is little , update G value
node->G = G;
node->F = G + node->H;
// set curr to node's parent
node->parent = curr;
}
}
else {
//in neither close list nor open list
//calculate G\H\F , add to open list
node->G = curr->G + 1;
node->H = Manhattan(node->row, node->col, end.first, end.second);
node->F = node->G + node->H;
node->open = true;
node->parent = curr;
open_list.push(node);
TheGameMap::Instance()->HightlightGrid(node->row, node->col);
}
}//end for
}//end while
//generate path vector
while (curr) {
path.push_back({ curr->row,curr->col });
curr = curr->parent;
}
//reverse path
reverse(path.begin(), path.end());
return path;
}
3D Simulation
Description: This demo showcases a simple 3D simulation using C++ and the olcPixelGameEngine. It simulate a cube rotation, it rotates around x-axis and z-axis
Technologies Used: C++, olcPixelGameEngine
#pragma once
#include "olcPixelGameEngine.h"
#include
//#include
#include
using namespace std;
using std::vector;
class vec3d {
public:
float x;
float y;
float z;
vec3d() = default;
vec3d(float x,float y,float z):x(x),y(y),z(z){}
};
class Triangle {
public:
vec3d p[3];
Triangle() = default;
Triangle(vec3d p0,vec3d p1,vec3d p2);
void draw();
};
class Mesh {
public:
vector tris;
};
struct Mat4x4 {
float mat[4][4];
};
void multiplyMatVec(const vec3d& inVec, vec3d& outVec, Mat4x4& mat4x4);
class Shape3D : public olc::PixelGameEngine
{
public:
Mesh meshCube;
Mat4x4 projectMat = { 0 };
float fTheta;
Shape3D()
{
sAppName = "3D Cube";
}
bool OnUserCreate() override{
//initgraph(ScreenWidth(), ScreenHeight(), EX_SHOWCONSOLE);
fTheta = 0;
float zNear = 0.10f;
float zFar = 1000.0f;
float theta = 90.0f;
float fTan = 1.0f / tanf(0.5f * theta / 180.0f * 3.1415f);// degree to radian
float aspectRatio = ((float)ScreenHeight() / (float)ScreenWidth());
projectMat.mat[0][0] = aspectRatio * fTan;
projectMat.mat[1][1] = fTan;
projectMat.mat[2][2] = zFar / (zFar - zNear);
projectMat.mat[2][3] = 1.0f;
projectMat.mat[3][2] = -zNear * zFar / (zFar - zNear);
projectMat.mat[3][3] = 0.0f;
//初始化栅格正方形
meshCube.tris = {
{{0.0f,0.0f,0.0f},{0.0f,1.0f,0.0f},{1.0f,0.0f,0.0f}},
{{0.0f,0.0f,0.0f},{1.0f,1.0f,0.0f},{1.0f,0.0f,0.0f}},//SOUTH
{{0.0f,1.0f,1.0f},{1.0f,0.0f,1.0f},{0.0f,0.0f,1.0f}},
{{0.0f,1.0f,1.0f},{1.0f,1.0f,1.0f},{1.0f,0.0f,1.0f}},//NORTH
{{1.0f,1.0f,0.0f},{1.0f,1.0f,1.0f},{1.0f,0.0f,0.0f}},
{{1.0f,1.0f,1.0f},{1.0f,0.0f,1.0f},{1.0f,0.0f,0.0f}},//EAST
{{0.0f,1.0f,1.0f},{0.0f,0.0f,0.0f},{0.0f,1.0f,0.0f}},
{{0.0f,1.0f,1.0f},{0.0f,0.0f,1.0f},{0.0f,0.0f,0.0f}},//WEST
{{0.0f,1.0f,1.0f},{1.0f,1.0f,0.0f},{0.0f,1.0f,0.0f}},
{{0.0f,1.0f,1.0f},{1.0f,1.0f,1.0f},{1.0f,1.0f,0.0f}},//TOP
{{0.0f,0.0f,1.0f},{1.0f,0.0f,1.0f},{0.0f,0.0f,0.0f}},
{{0.0f,0.0f,0.0f},{1.0f,0.0f,1.0f},{1.0f,0.0f,0.0f}},//BOTTOM
};
return true;
}
bool OnUserUpdate(float elapsedTime)override {
// Erase previous frame
Clear(olc::DARK_BLUE);
fTheta += 1.0f * elapsedTime;
Mat4x4 matRotZ = { 0 };
Mat4x4 matRotX = { 0 };
matRotZ.mat[0][0] = cosf(fTheta);
matRotZ.mat[0][1] = sinf(fTheta);
matRotZ.mat[1][0] = -sinf(fTheta);
matRotZ.mat[1][1] = cosf(fTheta);
matRotZ.mat[2][2] = 1.0f;
matRotZ.mat[3][3] = 1.0f;
matRotX.mat[0][0] = 1.0f;
matRotX.mat[1][1] = cosf(0.5f * fTheta);
matRotX.mat[1][2] = sinf(0.5f * fTheta);
matRotX.mat[2][1] = -sinf(0.5f * fTheta);
matRotX.mat[2][2] = cosf(0.5f * fTheta);
matRotX.mat[3][3] = 1.0f;
for (const auto& tri : meshCube.tris) {
Triangle triRotatedZ;
Triangle triRotatedZX;
multiplyMatVec(tri.p[0], triRotatedZ.p[0], matRotZ);
multiplyMatVec(tri.p[1], triRotatedZ.p[1], matRotZ);
multiplyMatVec(tri.p[2], triRotatedZ.p[2], matRotZ);
multiplyMatVec(triRotatedZ.p[0], triRotatedZX.p[0], matRotX);
multiplyMatVec(triRotatedZ.p[1], triRotatedZX.p[1], matRotX);
multiplyMatVec(triRotatedZ.p[2], triRotatedZX.p[2], matRotX);
Triangle triTranslated;
triTranslated = triRotatedZX;
triTranslated.p[0].z = triRotatedZX.p[0].z + 3.0f;
triTranslated.p[1].z = triRotatedZX.p[1].z + 3.0f;
triTranslated.p[2].z = triRotatedZX.p[2].z + 3.0f;
Triangle projectedTri;
multiplyMatVec(triTranslated.p[0], projectedTri.p[0], projectMat);
multiplyMatVec(triTranslated.p[1], projectedTri.p[1], projectMat);
multiplyMatVec(triTranslated.p[2], projectedTri.p[2], projectMat);
//scale to view
projectedTri.p[0].x += 1.0f; projectedTri.p[0].y += 1.0f;
projectedTri.p[1].x += 1.0f; projectedTri.p[1].y += 1.0f;
projectedTri.p[2].x += 1.0f; projectedTri.p[2].y += 1.0f;
projectedTri.p[0].x *= 0.5f * (float)ScreenWidth();
projectedTri.p[0].y *= 0.5f * (float)ScreenHeight();
projectedTri.p[1].x *= 0.5f * (float)ScreenWidth();
projectedTri.p[1].y *= 0.5f * (float)ScreenHeight();
projectedTri.p[2].x *= 0.5f * (float)ScreenWidth();
projectedTri.p[2].y *= 0.5f * (float)ScreenHeight();
DrawLine(projectedTri.p[0].x, projectedTri.p[0].y, projectedTri.p[1].x, projectedTri.p[1].y, olc::YELLOW);
DrawLine(projectedTri.p[1].x, projectedTri.p[1].y, projectedTri.p[2].x, projectedTri.p[2].y, olc::YELLOW);
DrawLine(projectedTri.p[2].x, projectedTri.p[2].y, projectedTri.p[0].x, projectedTri.p[0].y, olc::YELLOW);
}
//EndBatchDraw();
return true;
}
};
Rigid-Body dynamics simulation
Description: This demo showcases a simple Physics simulation using C++ and the olcPixelGameEngine. Player can play ice hockey with an AI.
Technologies Used: C++, olcPixelGameEngine
collision algorithm code from [Physics for Game Developers: Science, math, and code for realistic effects CHAPTER 10]
int CheckForCollision (pRigidBody2D body1, pRigidBody2D body2)
{
Vector d;
float r;
int retval = 0;
float s;
Vector v1, v2;
float Vrn;
r = body1->ColRadius + body2->ColRadius;
d = body1->vPosition - body2->vPosition;
s = d.Magnitude() - r;
d.Normalize();
vCollisionNormal = d;
v1 = body1->vVelocity;
v2 = body2->vVelocity;
vRelativeVelocity = v1 - v2;
Vrn = vRelativeVelocity * vCollisionNormal;
if((fabs(s) <= ctol) && (Vrn < 0.0))
{
retval = 1; // collision;
CollisionBody1 = body1;
CollisionBody2 = body2;
} else if(s < -ctol)
{
retval = −1; // interpenetrating
} else
retval = 0; // no collision
return retval;
}
void ApplyImpulse(pRigidBody2D body1, pRigidBody2D body2)
{
float j;
j = (-(1+fCr) * (vRelativeVelocity*vCollisionNormal)) /
( (vCollisionNormal*vCollisionNormal) *
(1/body1->fMass + 1/body2->fMass) );
body1->vVelocity += (j * vCollisionNormal) / body1->fMass;
body2->vVelocity -= (j * vCollisionNormal) / body2->fMass;
}
My implementation, include collsion detection and response
void IceHockey::CollisionResponse(Paddle& paddle) {
olc::vf2d vPaddle = paddle.v;
olc::vf2d vRelative = puck.velocity - vPaddle;
olc::vf2d vDis = puck.position - paddle.pos;
olc::vf2d vNormal = vDis.norm();//normalize of collision
float vRn = vRelative.dot(vNormal);
float dis = vDis.mag();
float sumR = paddle.outerR + puck.radius;
// Distance is less than the sum of the radius, and relative speed is positive.
if (dis < sumR && vRn<0.0f) {
float j = -2.0f * vRn / vNormal.dot(vNormal);
j /= (1.0f / paddle.mass + 1.0f / puck.mass);
puck.velocity += j * vNormal * 1.0f / puck.mass;
paddle.v -= j * vNormal * 1.0f / paddle.mass;
PlaySound(NULL, 0, 0);//stop all sound
PlaySound(bound_sound_file, NULL, SND_FILENAME | SND_ASYNC);//play bound sound
//set a new position
paddle.pos -= (sumR-dis)*vDis.norm();
}
}