Gridmodule improvements

[Bliksem18 (cos2005)]

I recently made two modulescripts. A grid module that can create a Grid and a cell module that creates cells that the grid uses. Those two moduleScripts work together. Here is the code for both modules.

Gridmodule

local Cell = require(script:WaitForChild("CellTest"))

local Grid = {}
Grid.__index = Grid

local Grids = {}

function Grid:GetRow(RowY)
	local cells = {}

	for X, yTable in ipairs(self.Cells) do
		table.insert(cells, yTable[RowY])
	end

	return cells
end

function Grid:GetColumn(ColumnX)
	local cells = {}

	local yTable = self.Cells[ColumnX]

	for y, cell in ipairs(yTable) do
		table.insert(cells, cell)
	end

	return cells
end

function Grid:GetCellFromPosition(X, Y)	
	if self.Cells[X] and self.Cells[X][Y] then
		return self.Cells[X][Y]
	else
		return nil
	end
end

function Grid:GetAllCells()
	local cells = {}

	for x, yTable in ipairs(self.Cells) do
		for y, cell in ipairs(yTable) do
			table.insert(cells, cell)	
		end
	end

	return cells
end

function Grid:GetCornerDiagonal(Corner) -- gets the diagonal from one corner from a vector2 with (1,1) being the top right corner
	Corner = Vector2.new(math.sign(Corner.X), math.sign(Corner.Y))

	local XBegin = math.max(1, Corner.X * self.Size.X)
	local YBegin = math.max(1, Corner.Y * self.Size.Y)

	local X = XBegin
	local Y = YBegin

	local cells = {}

	for i = 1, math.min(self.Size.X, self.Size.Y) do
		table.insert(cells, self.Cells[X][Y])
		X += -Corner.X
		Y += -Corner.Y
	end

	return cells
end

function Grid:ConstructGrid(cellBlock)
	for _, yTable in ipairs(self.Cells) do
		for _, cell in ipairs(yTable) do
			local newCellBlock = cellBlock:Clone()
			newCellBlock:SetPrimaryPartCFrame(cell.WorldCFrame)
			cell.CellBlock = newCellBlock
			newCellBlock.Parent = workspace.Grid
		end
	end
end

return {
	new = function(GridSizeX, GridSizeY, Name, WorldCFrame, CellSize)
		local self = setmetatable({}, Grid)

		self.Size = Vector2.new(GridSizeX, GridSizeY)

		self.CellSize = CellSize
		self.Cells = {}

		self.WorldCFrame = WorldCFrame

		self.Name = Name

		for x = 1, GridSizeX do
			local XOffset = -(GridSizeX / 2) * CellSize + CellSize * x

			self.Cells[x] = {}

			for y = 1, GridSizeY do
				local YOffset = -(GridSizeY / 2) * CellSize + CellSize * y
				
				local Offset = CFrame.new(XOffset, YOffset, 0)
				local CellWorldCFrame = self.WorldCFrame * Offset

				self.Cells[x][y] = Cell.new(x, y, Offset, CellWorldCFrame, self)
			end
		end

		Grids[Name] = self

		return self
	end,
	GetGridFromName = function(Name)
		return Grids[Name]
	end
}

Cellmodule

local Cell = {}
Cell.__index = Cell

local directionModifiers = {
	Vector2.new(1, 1),
	Vector2.new(1, -1),
	Vector2.new(-1, 1),
	Vector2.new(-1, -1)
}

local function IsSomethingInTheWay(CurrentPosition, Direction, Grid)
	local inTheWay = false

	if math.abs(Direction.X) == math.abs(Direction.Y) then
		local CurrentColumn = CurrentPosition.X
		local CurrentRow = CurrentPosition.Y

		for i = 1, Direction.X do
			CurrentColumn += math.sign(Direction.X)
			CurrentRow += math.sign(Direction.Y)

			local cell = Grid:GetCellFromPosition(CurrentColumn, CurrentRow)
			if cell.Occupied then
				inTheWay = true
				break
			end
		end
	elseif Direction.X == 0 or Direction.Y == 0  then
		if Direction.X == 0 then
			for i = 1, Direction.Y do
				local currentColumn = CurrentPosition.X
				local currentRow = CurrentPosition.Y + i

				if Grid:GetCellFromPosition(currentColumn, currentRow).Occupied == true then
					inTheWay = true
					break
				end
			end
		elseif Direction.Y == 0 then
			for i = 1, Direction.X do
				local currentColumn = CurrentPosition.X + 1
				local currentRow = CurrentPosition.Y

				if Grid:GetCellFromPosition(currentColumn, currentRow).Occupied == true then
					inTheWay = true
					break
				end
			end
		end
	else
		local X = Direction.X
		local Y = Direction.Y

		local XLeft = X
		local YLeft = Y

		local signedX = math.sign(X)
		local signedY = math.sign(Y)

		local initialProportion = X/Y

		local CurrentDirection = Direction

		while CurrentDirection.X ~= 0 or CurrentDirection.Y ~= 0 do --XLeft == 1 or -1 and YLeft == 1 or -1
			local CurrentX = XLeft - signedX
			local CurrentY = YLeft - signedY
			
			local currentProportionX
			local currentProportionY
			
			if CurrentY == 0 and CurrentX == 0 then
				local smallest = math.abs(X) < math.abs(Y) and "X" or "Y"
				
				if smallest == "X" then
					currentProportionX = initialProportion
					currentProportionY = math.huge
				else
					currentProportionX = math.huge
					currentProportionY = initialProportion
				end
			elseif math.abs(XLeft) + math.abs(YLeft) == 1 then -- there is one step left to do
				local Axis = math.abs(XLeft) == 1 and "X" or "Y"
				
				if Axis == "X" then
					currentProportionX = initialProportion
					currentProportionY = math.huge
				else
					currentProportionX = math.huge
					currentProportionY = initialProportion
				end
			elseif CurrentY <= 0 then -- swap the initialproportion so there is on infinite problem
				initialProportion = Y/X
				
				currentProportionX = YLeft / CurrentX
				currentProportionY = CurrentY / XLeft
			else
				currentProportionX = CurrentX / YLeft
				currentProportionY = XLeft / CurrentY
			end

			local difX = math.abs(initialProportion - currentProportionX)
			local difY = math.abs(initialProportion - currentProportionY)

			local closest = difX <= difY and "X" or "Y"

			if closest == "X" then
				XLeft -= signedX
			elseif closest == "Y" then
				YLeft -= signedY
			end

			CurrentDirection = Vector2.new(XLeft, YLeft)

			local currentColumn = CurrentPosition.X + CurrentDirection.X
			local currentRow = CurrentPosition.Y + CurrentDirection.Y
			local currPos = Vector2.new(currentColumn, currentRow)

			if cell.Occupied == true then
				inTheWay = true
				break
			end
		end
	end

	return inTheWay
end

function Cell:GetDirectNeighbours(Grid)
	local X = self.Column
	local Y = self.Row

	local cells = {}

	table.insert(cells, Grid.Cells[X + 1][Y])
	table.insert(cells, Grid.Cells[X - 1][Y])
	table.insert(cells, Grid.Cells[X][Y + 1])
	table.insert(cells, Grid.Cells[X][Y - 1])
	self.CellBlock.PrimaryPart.Color = Color3.new(1, 0, 0)

	return cells
end

function Cell:GetDiagonalNeighbours(Grid)
	local X = self.Column
	local Y = self.Row

	local cells = {}

	table.insert(cells, Grid.Cells[X + 1][Y + 1])
	table.insert(cells, Grid.Cells[X + 1][Y - 1])
	table.insert(cells, Grid.Cells[X - 1][Y + 1])
	table.insert(cells, Grid.Cells[X - 1][Y - 1])

	return cells
end

function Cell:GetAllNeighBours(Grid)
	local cells = {}

	for _, cell in ipairs(self:GetDirectNeighbours(Grid)) do
		table.insert(cells, cell)
	end
	for _, cell in ipairs(self:GetDiagonalNeighbours(Grid)) do
		table.insert(cells, cell)
	end

	return cells
end

function Cell:GetNeigbouringCellFromDirections(Grid, ...)
	local directions = {...}
	local cells = {}

	for _, direction in ipairs(directions) do
		assert(typeof(direction) == "Vector2", "must provide a vector2")

		direction = Vector2.new(math.sign(direction.X), math.sign(direction.Y))

		table.insert(cells, Grid.Cells[self.Column + direction.X][self.Row + direction.Y])
	end

	return cells
end

function Cell:GetAllDirectCells(Grid)
	local cells = {}

	for _, cell in ipairs(Grid:GetColumn(self.Column)) do
		if cell ~= self then
			table.insert(cells, cell)
		end
	end
	for _, cell in ipairs(Grid:GetRow(self.Row)) do
		if cell ~= self then
			table.insert(cells, cell)
		end
	end

	return cells
end

function Cell:GetAllDiagonalCells(Grid, StopIfOccupied)
	local cells = {}

	for _, cell in ipairs(self:GetAllCellsFromDirections(Grid, StopIfOccupied, Vector2.new(1, 1))) do
		table.insert(cells, cell)
	end
	for _, cell in ipairs(self:GetAllCellsFromDirections(Grid, StopIfOccupied, Vector2.new(1, -1))) do
		table.insert(cells, cell)
	end
	for _, cell in ipairs(self:GetAllCellsFromDirections(Grid, StopIfOccupied, Vector2.new(-1, 1))) do
		table.insert(cells, cell)
	end
	for _, cell in ipairs(self:GetAllCellsFromDirections(Grid, StopIfOccupied, Vector2.new(-1, -1))) do
		table.insert(cells, cell)
	end

	return cells
end

function Cell:GetAllCellsFromDirections(Grid, StopIfOccupied, ...)
	local cells = {}

	for _, Direction in ipairs({...}) do
		local Column = self.Column + Direction.X
		local Row = self.Row + Direction.Y

		while Grid.Cells[Column] and Grid.Cells[Column][Row] do
			local currentPosition = Vector2.new(Column - Direction.X, Row - Direction.Y)

			if StopIfOccupied and IsSomethingInTheWay(currentPosition, Direction, Grid) then
				break
			end

			table.insert(cells, Grid.Cells[Column][Row])
			Column += Direction.X
			Row += Direction.Y
		end
	end

	return cells
end

function Cell:GetAllCellsFromAllRotatedDirections(Grid, StopIfOccupied, ...)
	local Directions = {...}
	local cells = {}

	for _, direction in ipairs(Directions) do
		if direction.X == 0 or direction.Y == 0 then
			local Axis = direction.X == 0 and "Y" or "X"

			local rotatedDirections = {
				Vector2.new(direction[Axis], 0),
				Vector2.new(-direction[Axis], 0),
				Vector2.new(0, direction[Axis]),
				Vector2.new(0, -direction[Axis])
			}

			for _, cell in ipairs(self:GetAllCellsFromDirections(Grid, StopIfOccupied, table.unpack(rotatedDirections))) do
				table.insert(cells, cell)
			end
		else
			for _, directionModifier in ipairs(directionModifiers) do
				local rotatedDirection = direction * directionModifier
				
				for _, cell in ipairs(self:GetAllCellsFromDirections(Grid, StopIfOccupied, rotatedDirection)) do
					table.insert(cells, cell)
				end
			end
		end
	end

	return cells
end

function Cell:GetAllDirectAndDiagonalCells(Grid)
	local cells = {}

	for _, cell in ipairs(self:GetAllDirectCells(Grid)) do
		table.insert(cells, cell)
	end
	for _, cell in ipairs(self:GetAllDiagonalCells(Grid)) do
		table.insert(cells, cell)
	end

	return cells
end

function Cell:GetCellsFromDirections(Grid, StopIfOccupied, ...)
	local cells = {}

	for _, Direction in ipairs({...}) do
		if StopIfOccupied and IsSomethingInTheWay(Vector2.new(self.Column, self.Row), Direction, Grid) then
			continue
		end
		local Column = self.Column + Direction.X
		local Row = self.Row + Direction.Y

		table.insert(cells, Grid:GetCellFromPosition(Column, Row))
	end
	
	return cells
end

function Cell:GetCellsFromAllRotatedDirections(Grid, StopIfOccupied, ...)
	local cells = {}

	for _, direction in ipairs({...}) do
		if direction.X == 0 or direction.Y == 0 then
			local Axis = direction.X == 0 and "Y" or "X"

			local rotatedDirections = {
				Vector2.new(direction[Axis], 0),
				Vector2.new(-direction[Axis], 0),
				Vector2.new(0, direction[Axis]),
				Vector2.new(0, -direction[Axis])
			}

			for _, rotatedDirection in ipairs(rotatedDirections) do
				local Column = self.Column + rotatedDirection.X
				local Row = self.Row + rotatedDirection.Y

				print(Column, Row)

				table.insert(cells, Grid:GetCellFromPosition(Column, Row))
			end
		else
			for _, directionModifier in ipairs(directionModifiers) do
				local rotatedDirection = direction * directionModifier

				local Column = self.Column + rotatedDirection.X
				local Row = self.Row + rotatedDirection.Y

				if Grid:GetCellFromPosition(Column, Row) then
					table.insert(cells, Grid:GetCellFromPosition(Column, Row))
				end
			end			
		end
	end

	return cells
end

return {
	new = function(Column, Row, OffsetCFrame, WorldCFrame, Grid)
		local self = setmetatable({}, Cell)

		self.Column = Column
		self.Row = Row

		self.Occupied = false
		self.OccupiedBy = nil

		self.OffsetCFrame = OffsetCFrame
		self.WorldCFrame = WorldCFrame

		return self
	end
}

Although I would love some feedback on both modulescripts, I understand that you don’t have the time or that you don’t want to read everything, so I mostly want feedback on this function, because I think it is a mess:

local function IsSomethingInTheWay(CurrentPosition, Direction, Grid)
	local inTheWay = false

	if math.abs(Direction.X) == math.abs(Direction.Y) then
		local CurrentColumn = CurrentPosition.X
		local CurrentRow = CurrentPosition.Y

		for i = 1, Direction.X do
			CurrentColumn += math.sign(Direction.X)
			CurrentRow += math.sign(Direction.Y)

			local cell = Grid:GetCellFromPosition(CurrentColumn, CurrentRow)
			if cell.Occupied then
				inTheWay = true
				break
			end
		end
	elseif Direction.X == 0 or Direction.Y == 0  then
		if Direction.X == 0 then
			for i = 1, Direction.Y do
				local currentColumn = CurrentPosition.X
				local currentRow = CurrentPosition.Y + i

				if Grid:GetCellFromPosition(currentColumn, currentRow).Occupied == true then
					inTheWay = true
					break
				end
			end
		elseif Direction.Y == 0 then
			for i = 1, Direction.X do
				local currentColumn = CurrentPosition.X + 1
				local currentRow = CurrentPosition.Y

				if Grid:GetCellFromPosition(currentColumn, currentRow).Occupied == true then
					inTheWay = true
					break
				end
			end
		end
	else
		local X = Direction.X
		local Y = Direction.Y

		local XLeft = X
		local YLeft = Y

		local signedX = math.sign(X)
		local signedY = math.sign(Y)

		local initialProportion = X/Y

		local CurrentDirection = Direction

		while CurrentDirection.X ~= 0 or CurrentDirection.Y ~= 0 do
			local CurrentX = XLeft - signedX
			local CurrentY = YLeft - signedY
			
			local currentProportionX
			local currentProportionY
			
			if CurrentY == 0 and CurrentX == 0 then  --XLeft == 1 or -1 and YLeft == 1 or -1
				local smallest = math.abs(X) < math.abs(Y) and "X" or "Y"
				
				if smallest == "X" then
					currentProportionX = initialProportion
					currentProportionY = math.huge
				else
					currentProportionX = math.huge
					currentProportionY = initialProportion
				end
			elseif math.abs(XLeft) + math.abs(YLeft) == 1 then -- there is one step left to do
				local Axis = math.abs(XLeft) == 1 and "X" or "Y"
				
				if Axis == "X" then
					currentProportionX = initialProportion
					currentProportionY = math.huge
				else
					currentProportionX = math.huge
					currentProportionY = initialProportion
				end
			elseif CurrentY <= 0 then -- swap the initialproportion so there is on infinite problem
				initialProportion = Y/X
				
				currentProportionX = YLeft / CurrentX
				currentProportionY = CurrentY / XLeft
			else
				currentProportionX = CurrentX / YLeft
				currentProportionY = XLeft / CurrentY
			end

			local difX = math.abs(initialProportion - currentProportionX)
			local difY = math.abs(initialProportion - currentProportionY)

			local closest = difX <= difY and "X" or "Y"

			if closest == "X" then
				XLeft -= signedX
			elseif closest == "Y" then
				YLeft -= signedY
			end

			CurrentDirection = Vector2.new(XLeft, YLeft)

			local currentColumn = CurrentPosition.X + CurrentDirection.X
			local currentRow = CurrentPosition.Y + CurrentDirection.Y
			local currPos = Vector2.new(currentColumn, currentRow)

			if cell.Occupied == true then
				inTheWay = true
				break
			end
		end
	end

	return inTheWay
end

I probably need to do some explaining with this function. With this function, I want to get all the cells in a straight line and check if they are occupied. If they are, return false.

In this picture, I would want to get all the cells the line crosses. (the line is supposed to be straight). The direction in this example would be (7, 3)

A Grid is a Grid of X by Y cells.
first I check if the direction is something simple, like only X or only Y is not zero or X and Y are the same. If the direction is something else, I take the initialproproportion of Direction.X and Direction.Y:

local initialProportion = Direction.X / Direction.Y

in the example that would be 7 / 3 which is about 2,3
Than I subtract 1 from Direction.X and 1 from Direction.Y. I calculate the new proportions and determine which is closest to the original proportion. I check the new cell and move on:

local difX = math.abs(initialProportion - currentProportionX)
local difY = math.abs(initialProportion - currentProportionY)

local closest = difX <= difY and "X" or "Y"

if closest == "X" then
	XLeft -= signedX
elseif closest == "Y" then
	YLeft -= signedY
end

This approach works fine, but it becomes wonky when you reach zero. Is there a better way to do my approach, or should I do something else?
I hope I explained will what I am trying to do. If you have any questions, don’t hesitate to ask.

[ThanksRoBama (Emma)]

Sorry, I didn’t read all your code. To see if anything is “in the way” in any of the cells along a line segment, you can first get all the cells along the line segment, and then check if any of them “have anything in the way”. Here’s how you can get all the cells along a line segment:

Start from point A, then move towards point B 1 cell size at a time (the circles show 1 grid size distance from each point). The points you land on (shown as green circles) will be inside the cells that form the straight line. This is the same kind of line you’d get from a non-anti-aliased 1px line in a pixel art drawing program. If you want a “fat” line, or all the cells that the line crosses, you can instead go towards B in half cell steps at a time:

You can figure out the coordinates of the cell that a given point is inside by rounding off the coordinates to the nearest cell size.

Here’s a code example:

function round(n, to)
    return math.floor(n/to + 0.5) * to
end

function roundToGrid(point, gridSize)
    return Vector3.new(
        roundTo(point.X, gridSize),
        roundTo(point.Y, gridSize),
        roundTo(point.Z, gridSize)
    )
end

function dictKeys(dict)
    local keys = {}
    for k, _ in pairs(dict) do
        table.insert(keys, k)
    end
    return keys
end

function getCellsBetweenPoints(pointA, pointB, gridSize, isLineFat)
    local dir = (pointB - pointA).Unit
    local magnitude = (pointB - pointA).Magnitude
    local step = isLineFat and gridSize / 2 or gridSize
    
    local resultDict = {}
    for progress = 0, magnitude, step do --starting from 0 means we count pointA
        local point = roundToGrid(pointA + dir * progress, gridSize)
        resultDict[point] = true
    end
    resultDict[pointB] = true --pointB would only be counted otherwise if magnitude is *exactly* divisible by gridSize, which almost never happens.
    
    return dictKeys(resultDict)
end

This uses a dictionary to easily make sure that even if two points land inside the same cell, the cell is only “counted” once.

[D0RYU (nici)]

@ThanksRoBama

math.floor(n/to + 0.5)

only problem I see with this code is the fact that you don’t use math.round() here

[Bliksem18 (cos2005)]

Thank you so much for replying. Your method is simpler than mine, which is good, but after a benchmark, it seems to work slower than mine. (although the difference is not much) I modified the code a little.

	local unitDirection = Direction.Unit
	local magnitude = Direction.Magnitude
	local step = 0.5
	
	local result = {}
	
	for progress = 0, magnitude, step do
		local point = CurrentPosition + unitDirection * progress
		local position = Vector2.new(math.round(point.X), math.round(point.Y))
		result[position] = true
	end
	
	local inTheWay = false
	
	for position, _ in pairs(result) do
		local cell = Grid:GetCellFromPosition(position.X, position.Y)
				
		if cell.Occupied then
			inTheWay = true
			break
		end
	end
	
	return inTheWay

Direction and CurrentPosition are both Vector2.

[TheLegendaryDragon99 (TLD99)]

This is organized just need some optimizations.