Category: algorithms
-
Simulating Boids
Boids are used to simulate bird flocks, animal herds, and fish schools & is an example of swarm intelligence. Swarm intelligence refers to the collective behavior of individual agents who interact locally with one another and their environment to produce global patterns or behaviors. Individual members exhibit simple behaviors, but together they create complex movements…
-
Procedural Generation Using L-Systems
Cover photo credits: https://www.shadertoy.com/view/XtyGzh Lindenmayer system (L-system) is a representation of how plants and some other biological structures grow. If we look at its text form, it is simply a sequence of simple characters called the initial state of the system. We also have a axiom (a rule) that defines what a particular character in…
-
Poisson Disk Sampling
In my old games, I used simple noise for procedural placement of trees in forest. This resulted in many trees clump together as the noise samples are generated too near in some cases. The solution to this is poisson disc sampling. Comparison of noise samples with poisson samples: Classical Algorithm for Poisson Disk The old…
-
Simulating Hydraulic Erosion of Terrain
Hydraulic erosion is a nature-based algorithm that simulates erosion caused by water on terrain. It is useful to make procedurally generated terrains look more realistic & interesting. Hydraulic Erosion Overview Water from mountains come down through slopes, forming creases along the way. This water is then accumulated as is travels, causing the formations of streams.…
-
Noise Functions
In a Nutshell Noise functions are used to add variation. It is useful for making procedural oceans, terrains, forests & vegetations and so on. 1. White noise 2. Value noise 3. Perlin noise 4. Voronoi (Worley) 5. Fractal Brownian Motion White Noise White noise is one of the simplest of the noises, made up of…
-
Marching Cubes Algorithm
A simple heightmap-based terrain works well for simple geometries in procedural generation, but when we have to make structures that should grow in any dimension, such as caves, cliffs, rocks; we need a better algorithm. For this the marching cube is a go-to algorithm but in my case, it was too slow for my game…
-
3D Procedural World Generation
I was making my bird game & the player should be able to fly tens of kilometers to any direction, above the rich forests & deserts. There should be different species of birds flying in beautiful patterns and should interact with the world in a good way. I knew that the answer is procedural generation,…
-
Pathfinding Using A* Algorithm
Red enemy chasing the player using A* algorithm, avoiding obstacles. GitHub link. You want your enemy to take the shortest path to the player in your game. You are aware of graph data structure & want to use it to represent the 2D world. Then you will apply this algorithm on the graph & use…
-
Pathfinding Using Dijkstra’s Algorithm
Today, you can use Dijkstra’s pathfinding algorithm to find the shortest path from the gate to cafeteria. After understanding what it is & how exactly it works, we’ll implement it using Python. Later, we’ll implement a more better variant of it called A* algorithm. But in this post, we’ll keep ourselves to Dijkstra algorithm. If you…