Tile-Based Movement?

Geomaster · January 22, 2022, 9:36pm

Hey, and thanks for reading in advance.

I’m attempting to add a function to a module that returns a list of all possible cells (assuming no obstructions occur) that are within range that the player can move to from a given cell, and for the given example, I’m assuming the player can move two cells in any combination of directions.

Trouble is, the number of permutations goes up exponentially as you add on more ‘movement points’ to the character, and I’m having trouble thinking of how to create a loop that goes through every single possibility.

Code:

local PS = game:GetService("PhysicsService")
local CS = game:GetService("CollectionService")

local TerrainParams = RaycastParams.new()
TerrainParams.CollisionGroup = "Default"

--
local TileLibrary = {}

TileLibrary.WORLD_HEIGHT = 0
TileLibrary.WORLD_OFFSET = Vector2.new(2, 2)
TileLibrary.TILE_AREA = Vector2.new(4, 4)
	
function TileLibrary:TileVector(x, y, height)
	local Plane = (Vector2.new(x, y) * TileLibrary.TILE_AREA) + TileLibrary.WORLD_OFFSET
	local Vector = Vector3.new(Plane.X, height or TileLibrary.WORLD_HEIGHT, Plane.Y)
	
	local FloorCheck = workspace:Raycast(
		Vector + Vector3.new(0, 495, 0),
		Vector3.new(0, -500, 0),
		TerrainParams
	)
	
	if FloorCheck and FloorCheck.Instance then
		Vector = Vector3.new(Plane.X, FloorCheck.Position.Y, Plane.Y)
	end
	
	return Vector
end

function TileLibrary:NearestTile(Vector)
	local snapTo = Vector2.new(
		math.floor(Vector.X / TileLibrary.TILE_AREA.X),
		math.floor(Vector.Y / TileLibrary.TILE_AREA.Y)
	)
	
	return TileLibrary:TileVector(
		snapTo.X, Vector.Y, snapTo.Y
	)
end

function TileLibrary:ConstructCircle(x, y, radius)
	local tileCoordinates = {}
	
	-- Code Here
	
	return tileCoordinates
end

return TileLibrary

Does anyone have any ideas I could try? Any help or advice is appreciated.

ThanksRoBama · January 22, 2022, 10:30pm

Any node reachable in N steps is one step away from a node that’s reachable from N - 1 steps. Following that logic, you can go from nodes reachable in 0 steps (the start node) to any number of steps away from the start node. I’m assuming the player can go back and forth in a move and that you’re also interested in nodes reachable by retreading steps, e.g. 2 moves allows going back to the start node.

function getNodeAt(position)
    --Implement this
    --Note: ensure that subsequent calls to getNodeAt(position) evaluate to references to the same object!
    --The returned value must be usable as a dictionary key!
    --    I.e. dictionary[getNodeAt(pos)] == dictionary[getNodeAt(pos)] must work!
end

function getNeighbors(node)
    return {
        --Add more for diagonal movement
        getNodeAt(node.Position - Vector3.new(1, 0, 0)),
        getNodeAt(node.Position + Vector3.new(1, 0, 0)),
        getNodeAt(node.Position - Vector3.new(0, 0, 1)),
        getNodeAt(node.Position + Vector3.new(0, 0, 1))
    }
end

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

function getReachableNodesInSteps(fromNodes, numSteps)
    if numSteps == 0 then
        return fromNodes
    else
        local reachableInFewer = getReachableNodesInSteps(fromNodes, numSteps - 1)
        local reachableDict = {} --Use a dictionary so that duplicates just overwrite with same value
        for _, r in ipairs(reachableInFewer) do
            for _, n in ipairs(getNeighbors(r)) do
                reachable[n] = true --Duplicates overwrite with same value
            end
        end
        return keys(reachableDict)
    end
end

getReachableNodes({startNode}, 10)

This is a pretty naive implementation, so there will almost certainly be faster/more clever solutions out there but it should work. I’m not sure, but I think the reachable nodes will always be in a pattern of diamonds alternating between reachable and not reachable, which might be one avenue of optimization.

If you don’t care about tiles reachable by retracing steps, you’ll want to use a different algorithm. Essentially just a breadth-first flood fill where you note for each node how many steps it took to get there, which you compute by adding 1 to however many steps it took to get to the previous node. Let me know if that’s more relevant and I can provide more details on that.

Geomaster · January 22, 2022, 11:03pm

If you don’t care about tiles reachable by retracing steps, you’ll want to use a different algorithm. Essentially just a breadth-first flood fill where you note for each node how many steps it took to get there, which you compute by adding 1 to however many steps it took to get to the previous node. Let me know if that’s more relevant and I can provide more details on that.

Hey, thanks for the response!

This is to re-create the movement system for a game called Horizon’s Gate. Orientation is mechanically relevant in it, and the game draws an arrow from your initial position that follows the path, showing your orientation after moving. This display updates per-tile as you move your mouse, essentially allowing you to ‘draw’ your movement path. Backtracking to a tile isn’t technically possible, as the game will re-calculate to produce the shortest path available to the selected tile in order to help you conserve your movement points.

Hope that clarifies things. Thanks for your help!

ThanksRoBama · January 23, 2022, 1:31pm

Yeah it clarifies it a bit, but I’m still not really sure what you’re going for. Could you pust an image or a diagram or something?

Geomaster · January 23, 2022, 11:29pm

Essentially, yes - the alternative breadth-first flood-fill algorithm you mentioned is relevant.

Sorry, I misremembered the ‘arrow’ part - that only applies to ship battles. Here’s an actual example of the ground combat we’re replicating:

As you can see, selecting a character shows you all the tiles you can possibly move to, and hovering over a space highlights the tiles you would need to traverse to get there.

ThanksRoBama · January 24, 2022, 12:15am

Cool, here’s how that can be implemented:

function getReachableNodesInSteps(fromNodes, numSteps)
    --Nodes we that we need to visit
    local openSet = fromNodes --You might want to make a copy of fromNodes, this function *will* modify it! --Reachable node -> distance dictionary
    local nodesDistances = {}
    --node -> reachable dictionary, where reachable is true of reachable or nil if not reachable
    local reachableNodes = {}
    
    while #openSet > 0 do
        --Taking the bottom node causes all subsequent nodes to be shifted down, which is slow. Gotta get the first-found nodes though, to ensure breadth-first!
        local node = openSet[1]
        table.remove(openSet, 1)
        
        --Register as reachable
        reachableNodes[node] = true
        
        --Check if we should visit neighbors
        local nodeDistance = nodesDistances[node] or 0
        if nodeDistance == numSteps then continue end --Don't include neighbors if we're already at numSteps distance
        
        --Register neighbors to be visited
        for _, neighbor in ipairs(getNeighbors(node)) do
            if not reachableNodes[neighbor] then --This neighbor might have been visited by some other node, so make sure we don't run any side effects twice (in this case prevent overwriting nodesDistances)!
                --This allows openSet to contain duplicates! It's OK though because of the previous if statement, preventing nodeDistances from being overwritten
                table.insert(openSet, neighbor)
                nodesDistances[neighbor] = nodeDistance + 1
            end
        end
    end

    return keys(reachableNodes) --Turn the node -> bool dict into a node list
end

I haven’t tested this so it might have some errors, let me know if there are any that you need help fixing ^.^

Geomaster · January 26, 2022, 12:09am

I think I might be mis-using this, here…

Here’s what I’ve got:

local PS = game:GetService("PhysicsService")
local CS = game:GetService("CollectionService")

local TerrainParams = RaycastParams.new()
TerrainParams.CollisionGroup = "Default"

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

--
local TileLibrary = {}

TileLibrary.WORLD_HEIGHT = 0
TileLibrary.WORLD_OFFSET = Vector2.new(2, 2)
TileLibrary.TILE_AREA = Vector2.new(4, 4)
	
function TileLibrary:TileVector(x, y, height)
	local Plane = (Vector2.new(x, y) * TileLibrary.TILE_AREA) + TileLibrary.WORLD_OFFSET
	local Vector = Vector3.new(Plane.X, height or TileLibrary.WORLD_HEIGHT, Plane.Y)
	
	local FloorCheck = workspace:Raycast(
		Vector + Vector3.new(0, 495, 0),
		Vector3.new(0, -500, 0),
		TerrainParams
	)
	
	if FloorCheck and FloorCheck.Instance then
		Vector = Vector3.new(Plane.X, FloorCheck.Position.Y, Plane.Y)
	end
	
	return Vector
end

function TileLibrary:GetTileAt(Vector)
	local snapTo = Vector2.new(
		math.floor(Vector.X / TileLibrary.TILE_AREA.X),
		math.floor(Vector.Z / TileLibrary.TILE_AREA.Y)
	)
	
	return TileLibrary:TileVector(
		snapTo.X, Vector.Y, snapTo.Y
	)
end

function TileLibrary:GetNeighbors(Tile)
	return {
		TileLibrary:GetTileAt(Tile - Vector3.new(TileLibrary.TILE_AREA.X, 0, 0)),
		TileLibrary:GetTileAt(Tile + Vector3.new(TileLibrary.TILE_AREA.X, 0, 0)),
		TileLibrary:GetTileAt(Tile - Vector3.new(0, 0, TileLibrary.TILE_AREA.Y)),
		TileLibrary:GetTileAt(Tile + Vector3.new(0, 0, TileLibrary.TILE_AREA.Y))
	}
end

function TileLibrary:GetReachableTilesInSteps(fromTiles, numSteps)
	local openSet = fromTiles
	
	local TilesDistances = {}
	local reachableTiles = {}

	while #openSet > 0 do
		local Tile = openSet[1]
		
		table.remove(openSet, 1)
		reachableTiles[Tile] = true

		local TileDistance = TilesDistances[Tile] or 0
		
		if TileDistance == numSteps then
			continue
		end

		for _,neighbor in ipairs(TileLibrary:GetNeighbors(Tile)) do
			if not reachableTiles[neighbor] then
				table.insert(openSet, neighbor)
				TilesDistances[neighbor] = TileDistance + 1
			end
		end
	end

	return keys(reachableTiles)
end

return TileLibrary

-- Separate ServerScript
local TileCalculator = require(game.ReplicatedStorage.Modules.WORLD_TILE_CALC)
local OriginTile = TileCalculator:GetTileAt(Vector3.new(2, 2, 2))

local tileSet = TileCalculator:GetReachableTilesInSteps({OriginTile}, 2)

for key,tile in pairs(tileSet) do
	local block = Instance.new("Part")
	block.Size = Vector3.new(4, 4, 4)
	block.Anchored = true; block.CanCollide = false
	block.Position = tile + Vector3.new(0, block.Size.Y / 2, 0)
	block.Parent = workspace
end

ThanksRoBama · January 26, 2022, 1:32am

Oh sorry, you should modify GetNeighbors to only return neighbors that are actually traversible, or otherwise have another check inside the neighbors loop to ensure inaccessible neighbors don’t get added to the open set.

Geomaster · January 26, 2022, 3:45am

Hey, good news - the misnomer was on my end.
Everything looks about as expected here!

One final question for you:
The idea is for (like in the sample image) the player to pick a legal cell with their mouse to move into, which is server-validated easily enough. When this happens, however, I’d like to make it so that the travel path will be highlighted - I.E. the blue cell display will brighten on each cell that is a member of the path.

Would I need to use Djikstra’s algorithm or something similar to accomplish this?

Windsonnes · January 26, 2022, 7:49pm

I did something like this before with the Dijkstra algorithm. I used welds as the edges connecting the vertices in the graph. There’s a very useful video about the algorithm here.