FastFlow
Fast flowfield generation for performant swarm pathfinding| Download Module | Play Demonstration (Uncopylocked) |
Introduction
Roblox’s built-in pathfinding service is great for the general use case. However, in RTS or zombie games, running the pathfinder for each individual unit can quickly become inefficient. A common solution is to use a flowfield, which tells units what direction to move in when given their location:
Regardless of how many units we move to the target, the flowfield only needs to be generated once, making it great in cases where a swarm is drawn to a single static goal.
Walkthrough
First, we need to represent the pathfinding environment as a grid. This must be done using FastFlow's built-in grid module:
local Storage = game:GetService("ReplicatedStorage")
local FastFlow = require(Storage.FastFlow)
local Grid = FastFlow.Grid
-- Create a new grid object with a given max coordinate (size)
local maximumCoordinate = 20
local map = Grid.New(maximumCoordinate)
-- Set the value of cell (x, y) (integer coordinates)
local x, y = 0, 0
local value = 0
map:SetCell(Vector2.new(x, y), value)
-- Get the value of cell (x, y) (integer coordinates)
map:GetCell(Vector2.new(x, y))
-- Set intraversable cells (walls) to true, leave all other cells as nil
For our example, we will use a map generated through perlin noise:
Note that the grid must have cells along its borders marked as walls
(FastFlow will do this automatically)
Here's how we could setup a grid representing the noisemap
local seed = Vector2.new(0, 3)
local resolution = 10
for x = -maximumCoordinate, maximumCoordinate, 1 do
for y = -maximumCoordinate, maximumCoordinate, 1 do
if math.noise(x / resolution + seed.X, y / resolution + seed.Y) > 0 then
map:SetCell(Vector2.new(x, y), true)
end
end
end
Now, we can use this grid to create a pathfinder and generate a simple full-map flowfield:
-- Create a pathfinder using our newly constructed grid
local pathfinder = FastFlow.NewPathfinder(map)
-- Generate a flowfield leading to a given goal
local goal = Vector2.new(1, 1)
local flowfield = pathfinder:GenerateFlowfield(goal)
-- Obtain the direction of the flowfield at a given cell
local position = Vector2.new(0, 0)
local direction = flowfield:GetDirection(position) -- returns a unit vector
-- Generate a pruned flowfield using a table of starting cells
local goal = Vector2.new(1, 1)
local start = Vector2.new(-15, -15)
local flowfield = pathfinder:GenerateFlowfield(goal, {start})
The start cell is marked as blue (look at the bottom left corner)
Grid lines now show chunks rather than cells
Here's how the size of chunks can be adjusted
The grid lines have been adjusted to outline chunks rather than cells. The width of these chunks can be adjusted in a pathfinder’s constructor:
-- Create a pathfinder with a chunk width of size * 2 + 1
local chunkSize = 5
local pathfinder = FastFlow.NewPathfinder(map, chunkSize)
Now imagine that a pathfinding agent is pushed out of the flowfield zone. We can extend the flowfield to neighboring chunks:
-- Generate a pruned flowfield
local flowfield = pathfinder:GenerateFlowfield(goal, {start})
-- Sample the flowfield at an out-of-bounds position
local position = Vector2.new(-10, -10)
if not flowfield:GetDirection(position) then -- returns nil
pathfinder:MergeFlowfield(flowfield, position)
end
Documentation
Grid
GridStatic FastFlow.Grid
Grid GridStatic.New(int maxCoordinate, any fill = nil)
void Grid:SetCell(Vector2 pos, any value)
any Grid:GetCell(Vector2 pos)
boolean Grid:IsCellInBounds(Vector2 pos)
void Grid:ClearGrid()
Pathfinder
Pathfinder FastFlow.NewPathfinder(Grid walls, int chunkSize = 4, boolean omitPreprocessing = false)
Flowfield Pathfinder:GenerateFlowfield(Vector2 goal, {Vector2} startPositions = {})
Flowfield Pathfinder:MergeFlowfield(Flowfield Path, Vector2 start)
Vector2 Pathfinder:FindOpenCell(Vector2 pos)
void Pathfinder:Visualize(number cellWidth = 1, number yLevel = 0, boolean showWalls = false, boolean showCellGrid = false, boolean showChunkGrid = false, boolean showHPA = false)
void Pathfinder:SetupBorders()
void Pathfinder:SetupPruning()
Flowfield
Vector2 Flowfield:GetDirection(Vector2 pos)
number Flowfield:GetDistance(Vector2 pos)
