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 to represent the map
local maximumCoordinate = 20
local map = Grid.New(maximumCoordinate)
--[[
Set intraversable cells (walls) to true, leave all other cells as nil
]]
-- Mark cell (x, y) as a wall
local x, y = 0, 0
map:SetCell(Vector2.new(x, y), true)
-- Check if cell (x, y) is a wall
map:GetCell(Vector2.new(x, y))
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)
[details = “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
[/details]
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
[details = “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)
[/details]
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)
