Let’s start with something simple. We want to rotate a vector along x-axis at a certain angle. This is quite trivial to compute and you just need knowledge of rudimentary trigonometry to compute the resulting coordinates of vector. Let’s see if we can wrap around head around vector rotation intuition.
Let’s kick it up a notch and try to rotate Y-Axis in positive direction to get a new vector. This too can be easily computed with a few simple calculations. But! since we are considering counter-clockwise rotation to be positive(Left-Handed System), in our example, X’ should receive a negative value. How can we reason about this?
Here’s what’s happening: In out Left-Handed system, positive rotation around Z-Axis happens from +X -> +Y -> -X -> -Y -> +X. As we are rotating our Y-Axis, there’s an additional offset of PI/2 that needs to be added to rotation. This gives: X’ = Cos(90 + A) = Cos(90)Cos(A) – Sin(90)Sin(A) = -Sin(A) Y’ = Sin(90 + A) = Sin(90)Cos(A) + cos(90)Sin(A) = Cos(A) Now we see a negative sign showing up in the computation of X’. So, we ended up having to add an offset that would let us reach Y-Axis from X-Axis and then add the actual rotation that we want Y-Axis to rotate.
Viewing Through Y-Axis
This is great, but here’s another way of thinking about it: Let’s take a peek at how rotation looks from Y-Axis’ perspective. We are still in Left-Handed space and our Z-Axis hasn’t changed. In Y’s view, it is the positive axis that starts the rotation and on rotating counter-clockwise by 90 degrees, it reaches -ve X-Axis. Upon rotating some angle, it arrives at (YL, XL). This is what the Y-Axis sees and these coordinate are what we get in the local space of Y-Axis. Now that we have local coordinates, we just need a transformation matrix to compute the actual position in world space. Refer this for a refresher on local to world computation.
This matrix is quite easy to write as we just swapped X-Axis with Y-Axis and Y-Axis with -ve X-Axis.
0
-1
1
0
Transformation(Column-Major)
As an example, let’s rotate a vector along Y-Axis by 45 degrees. – (YL, XL) are (1/sqrt(2), 1/sqrt(2)) – On applying the transformation matrix to the vector above, we get (-1/sqrt(2), 1/sqrt(2)). These are indeed the world space coordinates that we desire.
I’ve been in the mood to do some physics simulations. I decided to start small and try to perform some Buoyancy simulation using unity. Do note that this post focuses only on simulating Buoyancy and it’s not the intention of this post to perform a complete simulation. So, let’s see how we can perform some 2D buoyancy simulation in unity. This is what I’ve ended up with
Let’s start by creating 2 scripts: “Buoyancy” and “Water”. Buoyancy script goes on the objects on which Buoyant force should act and Water script is attached to a liquid body. To keep the simulation simple, I’ve decided the circle to have a unit area. I’ve added the liquid object to layer “Water” and objects that can be collided with to layer “Floor”. As the liquid is static, we grab the min and max points in the Start(). These are the following variables declared in each of the scripts:
public class Buoyancy : MonoBehaviour
{
public float density = 750; // Kg/m^3
public float gravitationForce = 9.8f; // m/s^2;
[HideInInspector]
public float mass; // in KG
// 1 Unit = 1 Meter in Unity
// Forces that will act on body:
// Gravity : F = Mass * Gravity
// Buoyancy : B = density * gravity * (Volume to displaced fluid)
[HideInInspector]
public Vector3 currentVelocity = Vector3.zero;
[HideInInspector]
public Vector3 oldVelocity = Vector3.zero;
Vector3 externalForces = Vector3.zero;
// Start is called before the first frame update
void Start()
{
mass = 1 * density; // Considering unit volume
}
}
public class Water : MonoBehaviour
{
public float density = 997.0f; // KG/M^3
public float stickiness = 0.15f;
Vector3 minPoint = Vector3.zero;
Vector3 maxPoint = Vector3.zero;
// Start is called before the first frame update
void Start()
{
BoxCollider2D collider = GetComponent<BoxCollider2D>();
minPoint = collider.bounds.min;
maxPoint = collider.bounds.max;
}
}
Setup
In our simulation, there are going to be 2 forces acting on the body. One is the gravitational force(which is independent of mass) and buoyant force is the other one. We gather all the external forces that are acting on the body in the previous frame(using “RegisterExternalForce“) and add that to current acceleration of the body(A += F/M). It’s trivial to compute velocity if we have acceleration. We therefore use the computed velocity to update the position of the object in the “Update” loop (Disp = Vel * DeltaT).
void FixedUpdate()
{
SpriteRenderer renderer = GetComponent<SpriteRenderer>();
Vector3 acceleration = Vector3.zero;
acceleration.y = -gravitationForce;
acceleration += externalForces / mass;
currentVelocity = Vector3.zero;
currentVelocity = oldVelocity + (acceleration * Time.fixedDeltaTime);
currentVelocity.y = Mathf.Clamp(currentVelocity.y, -gravitationForce, gravitationForce);
Vector3 pos = gameObject.transform.position + currentVelocity * Time.fixedDeltaTime;
CircleCollider2D collider = GetComponent<CircleCollider2D>();
Collider2D otherCollider = Physics2D.OverlapCircle(pos, collider.radius, LayerMask.GetMask("Floor"));
if(otherCollider != null)
{
currentVelocity = Vector3.zero;
acceleration = -acceleration;
}
float gravity = mass * gravitationForce;
oldVelocity = currentVelocity;
//This should be reverted to 0 to gather all the forces again
externalForces = Vector3.zero;
}
public void RegisterForce(Vector3 externalForce)
{
externalForces += externalForce;
}
// Update is called once per frame
void Update()
{
gameObject.transform.position += currentVelocity * Time.deltaTime;
}
Buoyant force is acted on when an object comes into contact with a liquid surface. We use Trigger functions to perform these calculations whenever an object with “Buoyancy” component comes into contact with our trigger.
public class Water : MonoBehaviour
{
...
void OnTriggerEnter2D(Collider2D collider)
{
RegisterForceOn(collider);
}
void OnTriggerStay2D(Collider2D collider)
{
RegisterForceOn(collider);
}
void RegisterForceOn(Collider2D collider)
{
//Will be populated in next section
}
}
For unity to trigger collision events, one of the objects being partaking collision should have a rigidbody component. But we don’t want the rigidbody to move the object and perform any simulations. To fit our needs for this simulation, we can set the BodyType in rigidbody2D to “kinematic”.
Buoyancy Calculation
Now we can finally fill the final and most important function that actually calculates the Buoyancy. Whenever a body comes into contact with our liquid surface, we are going to apply the following forces on it:
Buoyant Force: acts in direction opposite to gravitational force [(density of liquid) * (acc. due to gravity) * (volume of liquid displaced)]
Drag: The resistance to motion of the object and it’s the force acting in opposite direction to relative motion of the object. It’s defined by (0.5 * liquidDensity * (relative speed of object)^2 * (dragCoefficient) * (Cross sectional Area)). For more information, please refer this wiki page.
Arrest Force: This is not conventional, but I had to apply an additional force to stop the objects from bouncing forever. This also acts in direction opposite to current velocity, but the calculated force attempts to halt the object. increasing the “Stickiness” variable reduces the resistance of the liquid. It seemed like a neat little effect, so I left it in. Please do post a comment if there’s a better way to prevent the eternal bouncing 🙂
Well, that’s all for this post. Please do post a comment if you figure out any improvements or better ways to approach this. Thanks for reading till the end!!
Motive of this article is to lay a foundation on how to quickly set-up dynamic platform generation for an infinite 2D side scroller. Since it’s a prototype, I’m going solely going to be working with a rectangle. And, I’ll be using Unity engine as it’s really well suited for anything 2D. So, let’s dive in and take a look at some dynamic platform generation. Check out this Youtube video to out to see this in action.
Getting Ready
We first need a platform with well defined dimensions. I created an extremely simple black rectangle prefab of 10 units wide. For Obstacles, I created two prefabs: a small red rectangle that player should avoid by jumping and an orange blocking platform that player must slide/duck under. For player itself, I’m using a very primitive green rectangle.
Everything is elementary, but I’ve employed a small trick when creating slide hazard prefab. The collider and sprite are at a slight offset so that the player can pass under it. Now that our game objects are ready, you can store them inside a class like GameManager to be accessible when generating platforms. My camera’s projection is set to orthographic and size to 15. Platforms start spawning from (0, 0, 0). So, I have the player sitting a few units above origin.
Coding IT!
Let’s first define a few constants and data structures for storing platforms. I’m going to call my script LevelGenerator.cs.
private readonly int TILE_DEACTIVATION_DISTANCE = 25; // Deactivate tile if distance to player is less than this
private float abyssLocation; // World X location of last spawned platform
private readonly int BLOCK_PADDING = 150; // Spawn a tile chain if (abyssLocation - playerPos) is less than this
private readonly int BLOCK_CHAIN = 10; // Spaws these number of tiles at once
public static LevelGenerator Instance;
[SerializeField]
private int numberOfLevels = 3; // This represents "floors". Limits how high platforms can be generated
public List<Tile> platforms; // List of all platforms "prefabs" used for spawning. Must be filled in editor
public List<Tile> hazards; // List of all available hazard "prefabs" used for spawning. Must be filled in editor
//object pool of type tiles
private List<Tile> tiles; // A cache of all active tiles(platforms and hazards) for object pooling.
private List<Tile> activeTiles; // Cache of active tiles
private PlayerMovement player;
private int currentLevel = 0;
private int previousLevel;
void Start () {
player = FindObjectOfType<PlayerMovement>();
//platforms = new List<Tile>();
tiles = new List<Tile>();
activeTiles = new List<Tile>();
previousLevel = currentLevel;
//Spawn a set of 10 blocks at the start of the game
InitialBlockSpawn();
}
void InitialBlockSpawn()
{
int BLOCK_CHAIN = 7;
for (int i = 0; i < BLOCK_CHAIN; i++)
{
Tile t = GetTile(0, true);
t.transform.position = new Vector3(abyssLocation, currentLevel * 7, 0);
t.transform.parent = this.transform;
abyssLocation += t.GetLength();
activeTiles.Insert(0, t);
t.Activate();
}
}
If everything is setup correctly, the code should spawn 10 blocks as soon as the game starts. The idea for platform initial generation is as follows:
“GetTile” gets a tile from the object pool. If it can’t find any suitable objects, it creates a new object and returns it.
“abyssLocation” is the position in the game beyond which no platforms exist. So, that’s where the player is headed and where the platform should be spawned next. Once we have the platform ready, we increment the “abyssLocation” with our platform’s length so that the next platform can go in that location.
“currentLevel * 7” lets us spawn platforms at varying heights(Y). If currentLevel is 0, all platforms take the position (X, 0). If currentLevel is 1, they take up (X, 7) and so on. It’s a simple, hacky and definitely not a production quality code. But, it gets the job done for this simple tut.
Once we have our X and Y, we have a location where we can spawn our platform.
We still haven’t looked at how to spawn tiles and get them from object pools. let’s do that now.
Tile GetTile(int id, bool platform)
{
//Debug.Log("Inside the get tile");
Tile t = null;
t = tiles.Find(x => x.Id == id && x.Platform == platform && !x.gameObject.activeSelf);
if(t == null)
{
GameObject g = Instantiate(platforms[id].gameObject);
t = g.GetComponent<Tile>();
t.Platform = platform;
t.Id = id;
tiles.Add(t);
tiles.Insert(0, t);
//Debug.Log("Tile is.......: " + t);
}
return t;
}
Tile GetHazard(bool hazard)
{
Tile t = null;
int id = Random.Range(0, hazards.Count);
t = tiles.Find(x => x.Id == id && x.Hazard == hazard && !x.gameObject.activeSelf);
if(t == null)
{
GameObject g = Instantiate(hazards[id].gameObject);
t = g.GetComponent<Tile>();
t.Hazard = hazard;
t.Id = id;
tiles.Add(t);
tiles.Insert(0, t);
//Debug.Log("Tile is.......: " + t);
}
return t;
}
void DeactivateTiles()
{
for(int i = 0; i < activeTiles.Count; i++)
{
if (activeTiles[i].transform.position.x - player.transform.position.x < -TILE_DEACTIVATION_DISTANCE)
{
activeTiles[i].gameObject.SetActive(false);
activeTiles.RemoveAt(i);
}
}
}
“GetTile” and “GetHazard” are pretty identical in their functionality. This is the basic idea:
If we have multiple platforms and hazard prefabs, select one randomly and see if a game object exists in the “tiles” pool with similar parameters.
If an object matches our requirements and it’s not currently active, return that.
If no such object exists or is currently active, create a new game object and return that.
We now have all the tools at our feet and only thing left to do is coding the platform generation.
void Update () {
if(Mathf.Abs(player.transform.position.x - abyssLocation) < BLOCK_PADDING)
SpawnBlock();
DeactivateTiles();
}
void SpawnBlock()
{
//Get the block instantiation chain
int chain = Random.Range(1, BLOCK_CHAIN);
for(int i = 0; i < chain; i++)
{
Tile t = GetTile(0, true);
t.transform.position = new Vector3(abyssLocation, currentLevel * 7, 0);
t.transform.parent = this.transform;
abyssLocation += t.GetLength();
activeTiles.Insert(0,t);
t.Activate();
//instantiate random hazard
if (i != 0 && i != chain-1 && abyssLocation > 75)
{
if (Random.Range(0f, 1f) > 0.8f)
{
Tile h = GetHazard(true);
h.transform.position = new Vector3(abyssLocation, currentLevel * 7, 0);
h.transform.parent = this.transform;
activeTiles.Insert(0, h);
h.Activate();
}
}
}
//Generate a gap after a series of blocks
float randomGapVariable = Random.Range(0f, 1f);
if(randomGapVariable < 0.3f)
{
//Generate a gap of a random length
int gapLength = Random.Range(5, 12);
abyssLocation += gapLength;
}
//Change the path level with a certain random value
if(Random.Range(0f, 1f) < 0.15f)
{
if(currentLevel == 0)
{
currentLevel++;
}
else if(currentLevel == numberOfLevels - 1)
{
currentLevel--;
}
else
{
currentLevel = Random.Range(0f, 1f) > 0.5f ? currentLevel+1 : currentLevel-1;
}
}
}
We check if the player is getting closer to the “abyssLocation” in update loop. If the distance crosses a certain threshold, SpawnBlock is called.
A platform chain of previously specified number is spawned at once.
When platform is spawned, there’s a 20% chance to spawn a hazard on it. I hardcoded this as “(Random.Range(0f, 1f) > 0.8f)” , but this can be exposed to editor to tweak around.
To not make things too monotonous, there are going to be breaks after platform chain. There’s 30% chance for a gap to apprear.
Finally, there’s ~15% chance to change the level(Y position) of platform spawns.
To insert a node into an RB-Tree, we first insert it the same way we insert a node into a binary-search tree. We start from root and compare it’s value against the value of node being added. If lesser, we compare it against the left sub-tree and right sub-tree otherwise. This is repeated until a NULL node is encountered, where this new node is inserted. After insertion, color it “Red” and perform an RB-Table fixup to maintain the properties of RB-Tree. Let’s look at the code for Red Black Trees Insertion:
Once we inserted new node and colored it RED, there are 2 possible violations to the properties of RB-Tree. First, if the inserted node is Root, we colored it red, when it should’ve been black. Second, if the parent of inserted node is red, then we have violated 5th property which states that both children of RED nodes should be BLACK.
Now that we have inserted a node into the tree, let’s look at implementing the fix-up function. For this, I consider the node’s parent to be a left-child and “uncle” as node->parent->parent->right. With that, we will have 3 scenarios: – If uncle is RED, we will color the uncle and inserted node’s parent BLACK. Then, make node’s parent as the next node to be processed in the loop. – If the uncle is black and node being checked is a right-child. In this case, we try to transform it into 3rd scenario by making the next node to be processed as current node’s parent and performing Left-Rotate operation on inserted node. – Finally, if uncle is black and node being checked is left child, we color node->parent as BLACK and node->parent->parent as RED.
Here’s the code snippet
void RBInsertFixup(RBNode* node)
{
while(node->m_parent != &sentinel && node->m_parent->m_isRed)
{
//If Node's parent is red, we have a violation in RB-Tree Property
if(node->m_parent->m_parent->m_right == node->m_parent)
{
//If the current node's parent is right child
//Case - 1: We know that node->parent->parent(NPP) is black. So, if NPP's left child is red,
//we can simply switch colors
RBNode* uncle = node->m_parent->m_parent->m_left;
if(uncle != &sentinel && uncle->m_isRed)
{
node->m_parent->m_parent->m_isRed = true;
uncle->m_isRed = false;
node->m_parent->m_isRed = false;
node = node->m_parent->m_parent;
}
// Now we know that NPP's left child is black or nullptr. Now, depending on whether current node is
// left or right child, we perform rotations
else
{
//The goal here is to make newly added node as a root to node's parent and parent's parent.
if(node->m_parent->m_left == node)
{
// We right rotate here to transform newly added node as parent.
// With this node's parent effectively becomes it's right-child
// and Node's parent's parent will become node's parent
node = node->m_parent;
RightRotate(node);
}
// Finally Left Rotate on node's parent.
// Newly added node will become the new parent.
node->m_parent->m_isRed = false;
node->m_parent->m_parent->m_isRed = true;
LeftRotate(node->m_parent->m_parent);
}
}
else if(node->m_parent->m_parent->m_left == node->m_parent)
{ //Same as the block above with left and right interchanged }
}
root->m_isRed = false;
}