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…
-
Simulating Ant Colony
This is an optimization algorithm and is used to find optimum solutions in a complex graph. Ants or other agents are left to explore and discover good solutions. For a game world, I think A-star algorithm is better for shortest path finding. Ant Colony Optimization The Algorithm 1. We start with a grid. Each cell…
-
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
Cover image credits: https://github.com/udit/poisson-disc-sampling Poisson disk sampling is a technique for generating random points in the given space such that the points are distributed more evenly compared to purely random sampling, and it helps to avoid clustering or large gaps between points. In my old games, I used simple noise for procedural placement of trees…
-
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
Marching Cubes is a meshing algorithm, used to create mesh surface from a scalar field. The scalar field is just a scalar value associated with each point in a space. In simple words, visualize it as an algorithm to convert volume data into a mesh surface. This technique is often used in 3D procedural generation…
-
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
In a Nutshell A* algorithm for finding shortest path is, in simple words same as Dijkstra algorithm with a slight difference. In dijkstra, the algorithm considers edge cost only to determine which node to jump next. In A* however, the algorithm also considers (in addition to edge cost) an estimated value of cost from current…
-
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…