Improving custom 2d grids & cell optimizations

Help and Feedback Code Review
#1

Hey guys, back here with my grid code again. I’m looking for some advice on any optimizations I could make and improvements in style. My main efficiency problems were solved here, Optimizing 2d array generation for flow fields, but since this is the foundation for a lot of what I plan to work on, I’ve posted the entire grid code + the cell code and some additional questions.

I have two main questions:

  1. Is it worth having a separate “cell” class if realistically my only cell functions are :GetNeighbors() and a basic constructor? I’m positive I could put these two classes together and have a simple grid.GetNeighbors(cell) type function.
  2. If I wanted to compute Cell.Direction values at the same time they are being generated, how could I go about that? The problem with my current implementation (not shown) is that I compute values based on the neighbors’ distance to the goal cell, which would mean that I would need to know the goal position and all of the cell neighbors prior to computation.
--// Modules

local Enumerations = require(game.ReplicatedStorage.Enumerations)

--// Variables

local cellDirs = Enumerations.CellDirection

--// Module

local Cell = {}
Cell.__index = Cell
	
--// Public

function Cell.new(grid, gridIndex, worldPos)
	local cell = setmetatable({}, Cell)
	cell.ParentGrid = grid
	cell.GridIndex = gridIndex
	cell.Position = worldPos
	cell.Grid = grid
	cell.Direction = Vector2.new()
	return cell
end

function Cell:GetNeighbors()
	local cell_x, cell_y = self.GridIndex.X, self.GridIndex.Y
	local grid = self.Grid
	-- neighbors
	local neighbors = {}
	for _, dir in pairs(cellDirs) do
		neighbors[#neighbors+1] = grid:GetCell(cell_x + dir.X, cell_y + dir.Y)
	end
	return neighbors
end

--// Return

return Cell

local Cell = require(script.Cell)

--// Module

local Grid = {}
Grid.__index = Grid


--// Public

local function getXY(n, rows)
	return (n-1) % rows + 1, math.floor((n-1) / rows) + 1 
end

local function getIndex(x, y, rows)
	return (x + rows * (y - 1))
end

function Grid.new(size, cellSize, origin)
	-- constructs and returns a new grid
	-- size: Vector3
	-- cellSize: Int
	-- origin: Vector3
	local area = size.X * size.Y
	local grid = table.create(area)
	grid.Origin = origin or Vector3.new()
	grid.Size = size
	grid.CellSize = cellSize
	for cellNum = 1, area do
		local x, y = getXY(cellNum, size.X)
		grid[cellNum] = Cell.new(
			grid,
			Vector2.new(x, y),
			Vector3.new(x * cellSize, 0, y * cellSize) + grid.Origin
		)
	end
	setmetatable(grid, Grid)
	return grid
end

function Grid:Traverse(toX, toY, call, ...)
	-- gets cells between [toX][toY]
	-- passes each cell into call function first argument
	-- this cannot be used as a setter, only as a getter
	if toX > self.Size.X then
		warn("Tried to traverse beyond X reach.")
	elseif toY > self.Size.Y then
		warn("Tried to traverse beyond Y reach.")
	end
	local area = toX * toY
	local rows = self.Size.X
	for cellNum = 1, area do
		local x, y = getXY(cellNum, rows)
		local cell = self:GetCell(x, y)
		if cell then
			call(cell, ...)
		end
	end
end

function Grid:GetCell(x, y)
	-- get a cell at x, y
	-- may return nil
	local rows = self.Size.X
	if x > rows or x <= 0 then
		return nil
	end
	return self[getIndex(x, y, rows)]
end

function Grid:RemoveCell(x, y)
	-- remove a cell at x, y
	local rows = self.Size.X
	self[getIndex(x, y, rows)] = nil
end

function Grid:GetRandomCell()
	-- recursively run :getCell() at random(x, y) 
	-- until a cell is found
	local cellN = math.random(1, self.Size.X * self.Size.Y)
	local x, y = getXY(cellN, self.Size.X)
	local cell = self:GetCell(x, y)
	if cell then
		return cell
	else
		return self:GetRandomCell()
	end
end

function Grid:GetWorldPosition(index)
	-- converts cell index to world position
	-- returns Vec3
	local cellSize = self.CellSize
	return Vector3.new(index.X * cellSize, 0, index.Y * cellSize)
end

function Grid:GetIndex(worldPos)
	-- converts worldPos to cell index
	-- returns Vec2
	local cellSize = self.CellSize
	local origin = self.Origin
	if cellSize and worldPos then
		return Vector2.new(
			math.floor((worldPos-origin).X/cellSize), 
			math.floor((worldPos-origin).Z/cellSize)
		)		
	end
end

--// Return 

return Grid

Feel free to check out the post I linked above as it’s possible my implementation is not entirely in line with the solution.

1 Like
#2

If you wanna squeeze out a tiny bit of performance per cell without much work, I’d recommend replacing your Vector2 usage with Vector3s since Vector2s don’t yet have native engine support. Vector3s can be interacted with quite a lot faster than Vector2s (for now, the idea I got when the announcement post was made is that Roblox might support Vector2s in the future but still even recommend Vector3s for 2D calculations for speed). Leaving the Z component as 0 will mean that all things such as .Unit, .Magnitude, etc will still work as you want, and .X and .Y will function the same. As long as you convert to Vector2 when setting, for example, Roblox properties, you really don’t have to change anything and can even leave the last argument blank: Vector3.new(x, y)

It depends. Doing so everywhere you could potentially get a decent bit better performance with big grids, for example, rather than allocating new cell objects, using data oriented design and indexing the data for each cell from one big entry:

local grid = {
	-- Any other grid properties
	CellPositions = table.create(area, Vector3.new()),
	CellDirections = table.create(area, Vector3.new())
}

Then when you create your cell data, rather than making a new cell object you insert your data for the cell into the table for the entries:

grid.CellPositions[cellId] = worldPos
grid.CellDirections[cellId] = Vector3.new(x, y)

The reason why this helps is that each time you call Cell.new() you’re allocating a new table, and, really you’re allocating gridWidth * gridHeight new tables. By using multiple big tables for each position you reduce the number of allocations you do, and likely speed up lookups a little bit, since array lookups are fast.

Whether or not its worth it is a tough question and it sort of depends on how big you want to go. The bigger your flow grid is, the more benefit you get, so, if you have a very very large flow grid you’re much more likely to benefit than you are from a small, say, 10x10 grid where you’d only be saving 100x that small amount.

It may actually benefit you enough that you’d want it in a case like this, and probably would compact your code a little if anything, so, I would maybe say if it doesn’t seem to hard to go data oriented, it might be worth just going for whether it does or doesn’t significantly help.

Since the amount of time its gonna take is proportional to the flow grid’s area, a grid of w & h side lengths lets you estimate a total time of w * h * averageTimePerCell, which applies to when you want to do stuff to the entire grid at once. If you were to shave about 1ms off an operation on each cell, and you’re using a grid that’s 100x100, you’d effectively be saving 100*100 ms or 10 entire seconds, so, you can see how that can add up. This is typically the only time micro optimizations will matter, since your complexity can scale so aggressively.

This problem is basically a matter of figuring out the X and Y position of each neighbor. Since each cell has an integer XY position in your grid, you can actually just figure out the positions of the neighbors of the cell using some loops like so, which pretty much is just like looping over a 3x3 square of positions to use as offsets, except you can just ignore the center position:

local x, y = ... -- Position of the cell
-- We start at -1 (left) from the cell, and go up to 1 (right)
for xOffset=-1, 1 do
	-- We start at -1 (top) from the cell, and go up to 1 (bottom)
	for yOffset=-1, 1 do
		-- We make sure we're not at the center cell
		if not (xOffset == 0 and yOffset == 0) then
			local neighborX, neighborY = x + xOffset, y + yOffset
			-- I remember this as (to - from) or (big - small), so how much to add to 'from' to get to 'to' which is helpful for direction calculations
			local goalDifference = goalPosition - Vector3.new(neighborX, neighborY)
			local distanceToGoal = goalDifference.Magnitude
			local directionToGoal = goalDifference.Unit
			-- Stuff
		end
	end
end

You could also use the same calculations as mentioned in my previous post to get the cell number from the position if you wanted it.

As for your code overall, I think it’s very neat (both clean and a cool piece of code), and you’ve definitely done a very good job with it in my opinion.

2 Likes
#3

Once again, thanks a lot. I’ve learned much from your insights.
I felt particularly stupid for looking over this,

This problem is basically a matter of figuring out the X and Y position of each neighbor. Since each cell has an integer XY position in your grid, you can actually just figure out the positions of the neighbors of the cell using some loops like so, which pretty much is just like looping over a 3x3 square of positions to use as offsets, except you can just ignore the center position:

I have used that same method in other parts of my code but didn’t think to apply it here. Thanks for your time!

1 Like