Skip to content

Instantly share code, notes, and snippets.

@rluders

rluders/ControlManager.cs

Last active June 22, 2025 19:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save rluders/444669a714842c2a722a84583f091227 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save rluders/444669a714842c2a722a84583f091227 to your computer and use it in GitHub Desktop.
Download ZIP
Godot Flow Field Experiment
Raw
ControlManager.cs
using Godot;
using System;
using System.Collections.Generic;
/// <summary>
/// Controls spawning and movement of a large number of units using Flow Field Navigation.
/// </summary>
public partial class ControlManager : Node
{
[Export] public PackedScene UnitScene;
[Export] public Node3D UnitsParent;
[Export] public MeshInstance3D GroundPlane;
[Export] public int TotalUnits = 13000;
[Export] public float CellSize = 1.0f;
[Export] public float StartDelay = 10f;
[Export] public float UnitSpeed = 4f;
private FlowField flowField;
private List<Node3D> movableUnits = new();
private int gridWidth;
private int gridHeight;
private float elapsedTime = 0f;
private bool canMove = false;
public override void _Ready()
{
InitializeFlowField();
SpawnUnits(TotalUnits);
}
/// <summary>
/// Handles unit movement once the start delay is over.
/// </summary>
public override void _PhysicsProcess(double delta)
{
if (!canMove)
{
elapsedTime += (float)delta;
if (elapsedTime >= StartDelay)
{
canMove = true;
GD.Print($"Units ({TotalUnits}) started moving using flow field!");
}
return;
}
foreach (var unit in movableUnits)
{
Vector2I cellPos = flowField.WorldToGrid(unit.GlobalPosition);
if (!flowField.IsValid(cellPos.X, cellPos.Y)) continue;
var cell = flowField.GetCell(cellPos.X, cellPos.Y);
Vector3 direction = new Vector3(cell.FlowDirection.X, 0, cell.FlowDirection.Y).Normalized();
unit.GlobalPosition += direction * UnitSpeed * (float)delta;
}
}
/// <summary>
/// Spawns a number of units randomly distributed on the ground plane.
/// </summary>
private void SpawnUnits(int count)
{
for (int i = 0; i < count; i++)
{
var unit = UnitScene.Instantiate<Node3D>();
Vector3 randomPos = new Vector3(
GD.Randf() * gridWidth * CellSize,
0,
GD.Randf() * gridHeight * CellSize
);
unit.Position = randomPos;
UnitsParent.AddChild(unit);
movableUnits.Add(unit);
}
}
/// <summary>
/// Initializes the flow field grid based on the ground plane's dimensions.
/// </summary>
private void InitializeFlowField()
{
// Get mesh size and scale it to world dimensions
Aabb meshAabb = GroundPlane.Mesh.GetAabb();
Vector3 scale = GroundPlane.GlobalBasis.Scale;
Vector3 size = meshAabb.Size * scale;
Vector3 origin = GroundPlane.GlobalTransform.Origin + meshAabb.Position * scale;
// Calculate grid dimensions
gridWidth = Mathf.CeilToInt(size.X / CellSize);
gridHeight = Mathf.CeilToInt(size.Z / CellSize);
// Create and initialize the flow field
flowField = new FlowField(gridWidth, gridHeight, CellSize, origin);
Vector2I goal = flowField.WorldToGrid(GroundPlane.GlobalTransform.Origin); // center of plane
flowField.GenerateIntegrationField(goal);
flowField.GenerateFlowField();
}
}
Raw
flow_field.cpp
#include "flow_field.hpp"
FlowField::FlowField(int p_width, int p_height, float p_cell_size, Vector3 p_origin) {
width = p_width;
height = p_height;
cell_size = p_cell_size;
origin = p_origin;
grid.resize(width);
for (int x = 0; x < width; x++) {
grid[x].resize(height);
for (int y = 0; y < height; y++) {
Vector3 pos = origin + Vector3(x * cell_size, 0, y * cell_size);
grid[x][y] = { pos, 1, INT32_MAX, Vector2i(0, 0) };
}
}
}
FlowField::Cell FlowField::get_cell(int x, int y) const {
return grid[x][y];
}
Vector2i FlowField::world_to_grid(Vector3 world_pos) const {
int x = static_cast<int>((world_pos.x - origin.x) / cell_size);
int y = static_cast<int>((world_pos.z - origin.z) / cell_size);
return Vector2i(x, y);
}
Vector3 FlowField::grid_to_world(int x, int y) const {
return origin + Vector3(x * cell_size + cell_size / 2.0f, 0, y * cell_size + cell_size / 2.0f);
}
bool FlowField::is_valid(int x, int y) const {
return x >= 0 && y >= 0 && x < width && y < height;
}
void FlowField::generate_integration_field(Vector2i goal) {
for (auto pos : iterate_grid()) {
grid[pos.x][pos.y].integration = INT32_MAX;
}
std::queue<Vector2i> queue;
grid[goal.x][goal.y].integration = 0;
queue.push(goal);
while (!queue.empty()) {
Vector2i current = queue.front();
queue.pop();
Cell &current_cell = grid[current.x][current.y];
for (const Vector2i &offset : neighbor_offsets) {
Vector2i neighbor = current + offset;
if (!is_valid(neighbor.x, neighbor.y))
continue;
Cell &neighbor_cell = grid[neighbor.x][neighbor.y];
int new_cost = current_cell.integration + neighbor_cell.cost;
if (new_cost < neighbor_cell.integration) {
neighbor_cell.integration = new_cost;
queue.push(neighbor);
}
}
}
}
void FlowField::generate_flow_field() {
for (auto pos : iterate_grid()) {
Cell &cell = grid[pos.x][pos.y];
int min_cost = cell.integration;
Vector2i best_dir = Vector2i(0, 0);
for (const Vector2i &offset : neighbor_offsets) {
Vector2i neighbor = pos + offset;
if (!is_valid(neighbor.x, neighbor.y))
continue;
Cell &neighbor_cell = grid[neighbor.x][neighbor.y];
if (neighbor_cell.integration < min_cost) {
min_cost = neighbor_cell.integration;
best_dir = offset;
}
}
cell.flow_direction = best_dir;
}
}
Vector<Vector2i> FlowField::iterate_grid() const {
Vector<Vector2i> positions;
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
positions.push_back(Vector2i(x, y));
}
}
return positions;
}
Raw
flow_field.hpp
#ifndef FLOW_FIELD_HPP
#define FLOW_FIELD_HPP
#include <godot_cpp/classes/ref_counted.hpp>
#include <godot_cpp/core/class_db.hpp>
#include <godot_cpp/variant/vector2i.hpp>
#include <godot_cpp/variant/vector3.hpp>
#include <godot_cpp/templates/vector.hpp>
#include <queue>
using namespace godot;
class FlowField : public RefCounted {
GDCLASS(FlowField, RefCounted);
public:
struct Cell {
Vector3 world_position;
int cost = 1;
int integration = INT32_MAX;
Vector2i flow_direction = Vector2i(0, 0);
};
FlowField() = default;
FlowField(int p_width, int p_height, float p_cell_size, Vector3 p_origin);
Cell get_cell(int x, int y) const;
Vector2i world_to_grid(Vector3 world_pos) const;
Vector3 grid_to_world(int x, int y) const;
bool is_valid(int x, int y) const;
void generate_integration_field(Vector2i goal);
void generate_flow_field();
private:
int width = 0;
int height = 0;
float cell_size = 1.0f;
Vector3 origin;
std::vector<std::vector<Cell>> grid;
const std::vector<Vector2i> neighbor_offsets = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0},
{1, 1}, {1, -1}, {-1, 1}, {-1, -1}
};
Vector<Vector2i> iterate_grid() const;
};
#endif // FLOW_FIELD_HPP
Raw
FlowField.cs
using System.Collections.Generic;
using Godot;
/// <summary>
/// Represents a flow field grid used to guide units toward a goal using vector directions.
/// </summary>
public class FlowField
{
/// <summary>
/// Represents a single cell in the flow field grid.
/// </summary>
public struct Cell
{
public Vector3 WorldPosition;
public int Cost;
public int Integration;
public Vector2I FlowDirection;
}
private readonly int width;
private readonly int height;
private readonly float cellSize;
private readonly Vector3 origin;
private readonly Cell[,] grid;
/// <summary>
/// Offsets used to access 8-connected neighbor cells.
/// </summary>
private static readonly Vector2I[] neighborOffsets = new Vector2I[]
{
new(0, 1), new(1, 0), new(0, -1), new(-1, 0),
new(1, 1), new(1, -1), new(-1, 1), new(-1, -1)
};
/// <summary>
/// Constructs a flow field grid.
/// </summary>
/// <param name="width">Number of columns in the grid.</param>
/// <param name="height">Number of rows in the grid.</param>
/// <param name="cellSize">Size of each cell in world units.</param>
/// <param name="origin">World-space position of the bottom-left cell.</param>
public FlowField(int width, int height, float cellSize, Vector3 origin)
{
this.width = width;
this.height = height;
this.cellSize = cellSize;
this.origin = origin;
grid = new Cell[width, height];
for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
{
Vector3 pos = origin + new Vector3(x * cellSize, 0, y * cellSize);
grid[x, y] = new Cell
{
WorldPosition = pos,
Cost = 1,
Integration = int.MaxValue,
FlowDirection = Vector2I.Zero
};
}
}
/// <summary>
/// Returns the grid cell at the specified coordinates.
/// </summary>
public Cell GetCell(int x, int y) => grid[x, y];
/// <summary>
/// Converts a world-space position to grid coordinates.
/// </summary>
public Vector2I WorldToGrid(Vector3 worldPos)
{
int x = (int)((worldPos.X - origin.X) / cellSize);
int y = (int)((worldPos.Z - origin.Z) / cellSize);
return new Vector2I(x, y);
}
/// <summary>
/// Converts grid coordinates to the world-space center position of the cell.
/// </summary>
public Vector3 GridToWorld(int x, int y)
{
return origin + new Vector3(x * cellSize + cellSize / 2f, 0, y * cellSize + cellSize / 2f);
}
/// <summary>
/// Checks if the given grid coordinates are within the grid bounds.
/// </summary>
public bool IsValid(int x, int y) => x >= 0 && y >= 0 && x < width && y < height;
/// <summary>
/// Initializes the integration field by propagating costs from the goal cell.
/// </summary>
public void GenerateIntegrationField(Vector2I goal)
{
foreach (var pos in IterateGrid())
{
grid[pos.X, pos.Y].Integration = int.MaxValue;
}
var queue = new Queue<Vector2I>();
grid[goal.X, goal.Y].Integration = 0;
queue.Enqueue(goal);
while (queue.Count > 0)
{
var current = queue.Dequeue();
var currentCell = grid[current.X, current.Y];
foreach (var offset in neighborOffsets)
{
var neighbor = current + offset;
if (!IsValid(neighbor.X, neighbor.Y)) continue;
ref var neighborCell = ref grid[neighbor.X, neighbor.Y];
int newCost = currentCell.Integration + neighborCell.Cost;
if (newCost < neighborCell.Integration)
{
neighborCell.Integration = newCost;
queue.Enqueue(neighbor);
}
}
}
}
/// <summary>
/// Generates the flow field by computing direction vectors for each cell.
/// </summary>
public void GenerateFlowField()
{
foreach (var pos in IterateGrid())
{
ref var cell = ref grid[pos.X, pos.Y];
int minCost = cell.Integration;
Vector2I bestDir = Vector2I.Zero;
foreach (var offset in neighborOffsets)
{
var neighbor = pos + offset;
if (!IsValid(neighbor.X, neighbor.Y)) continue;
var neighborCell = grid[neighbor.X, neighbor.Y];
if (neighborCell.Integration < minCost)
{
minCost = neighborCell.Integration;
bestDir = offset;
}
}
cell.FlowDirection = bestDir;
}
}
/// <summary>
/// Iterates through all valid grid positions.
/// </summary>
private IEnumerable<Vector2I> IterateGrid()
{
for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
yield return new Vector2I(x, y);
}
}
Raw
register_types.cpp
#include "flow_field.hpp"
#include <godot_cpp/core/class_db.hpp>
using namespace godot;
void initialize_flowfield_module(ModuleInitializationLevel p_level) {
if (p_level != MODULE_INITIALIZATION_LEVEL_SCENE) {
return;
}
ClassDB::register_class<FlowField>();
}
void uninitialize_flowfield_module(ModuleInitializationLevel p_level) {
if (p_level != MODULE_INITIALIZATION_LEVEL_SCENE) {
return;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment