Preventing stack overflows with recursive animation syncing system

Help and Feedback Scripting Support
#1

I’ve created an animation syncing system, but the issue is that it’s hard to prevent stack overflows due to the recursive nature of how these work.

Basically, one player can sync with another, and that player can sync with another, so when the third player does an animation, it will recurse its way down to the third player.

This is my code:

local Animations = {}
local AnimationsTable = require(game:GetService("ReplicatedStorage").Shared.Animations)

local PlayerAnimations = {} -- Dictionary of Animations. Key = Player, Value = AnimationTrack
local Tracks = {} -- Dictionary of AnimationTracks. Key = Player, Value = AnimationTrack
local Synced = {} -- Dictionary of Synced, Key = Player, Value = Array of Players


local ManipulationCache = {}
local AnimationCaches = {}

local function GetNumbers(Str)
	local FirstTry = tonumber(Str)
	if FirstTry then return FirstTry end

	local Cached = table.find(ManipulationCache, Str)
	if Cached then return Cached end

	local Final = tonumber(Str:match("%d+"))
	ManipulationCache[Str] = Final
	return Final
end

function GetAnimationIdByName(NameString)
	for _, AnimInfo in pairs (AnimationsTable) do
		if AnimInfo.Name == NameString then
			return AnimInfo.ID
		end
	end
end

function Animations.GetPlayerTrack(Player)
	return Tracks[Player]
end

function Animations.Sync(Player, PlayerToSyncWith)
	if not Player or not PlayerToSyncWith then return end
	if Animations.IsPlayerSyncingWith(PlayerToSyncWith, Player) then return end
	
	Animations.CompleteUnsync(Player)
	
	if Player == PlayerToSyncWith then 
		return 
	end

	if not Synced[PlayerToSyncWith] then
		Synced[PlayerToSyncWith] = {}
	end
	
	table.insert(Synced[PlayerToSyncWith], Player)

	local PlayerAnimation = Animations.GetPlayerTrack(PlayerToSyncWith)
	if PlayerAnimation then
		Animations.PlayAnimation(PlayerToSyncWith, GetNumbers(PlayerAnimation.Animation.AnimationId))
	end
end

function Animations.CompleteUnsync(SpecifiedPlayer, Stop)
	for Player, PlayersSyncedWithThem in pairs (Synced) do
		local Found = table.find(PlayersSyncedWithThem, SpecifiedPlayer) 
		if Found then
			table.remove(PlayersSyncedWithThem, Found)
			Synced[Player] = PlayersSyncedWithThem
		end
	end
	if Stop then
		Animations.StopAnimation(SpecifiedPlayer)
	end
end

function Animations.IsPlayerSyncingWith(PlayerToCheck, HostPlayer)
	if not Synced[HostPlayer] then Synced[HostPlayer] = {} end
	return table.find(Synced[HostPlayer], PlayerToCheck)
end


function Animations.PlayAnimation(Player, Id, Original)
	if Original then
		Animations.CompleteUnsync(Player)
	end

	if Id then	
		if PlayerAnimations[Player] and Original then
			if GetNumbers(PlayerAnimations[Player].AnimationId) == Id then
				Animations.StopAnimation(Player)

				local SyncedPlayers = Synced[Player]
				if SyncedPlayers and #SyncedPlayers > 0 then
					for i = 1, #SyncedPlayers do
						Animations.StopAnimation(SyncedPlayers[i])
					end
				end
				return true
			end
		end

		Animations.StopAnimation(Player)

		local New = Instance.new("Animation")
		New.AnimationId = "rbxassetid://" .. Id

		local Character = Player.Character
		if not Character then return end

		local Humanoid = Character:FindFirstChildOfClass("Humanoid")
		if not Humanoid then return end

		local Animator = Humanoid.Animator

		PlayerAnimations[Player] = New

		if not AnimationCaches[Player] then
			AnimationCaches[Player] = {}
		end

		local Track = AnimationCaches[Player][Id]
		if not Track then
			Track = Animator:LoadAnimation(New)
			AnimationCaches[Player][Id] = Track
		end
		Tracks[Player] = Track
		Track:Play()


		local SyncedPlayers = Synced[Player]
		if SyncedPlayers and #SyncedPlayers > 0 then
			for i = 1, #SyncedPlayers do
				Animations.PlayAnimation(SyncedPlayers[i], Id)
			end
		end
	end
end

function Animations.StopAnimation(Player)
	local Track = Tracks[Player]
	if Track then Track:Stop() end
	PlayerAnimations[Player] = nil
	Tracks[Player] = nil
end

function Animations.ClearCachedLoadedAnimations(Player)
	AnimationCaches[Player] = nil
end

return Animations

As you can see I have the function Animations.IsPlayerSyncingWith to use to make sure that a player can’t sync with someone who is syncing with them. However , this boolean isn’t always reliable because the player could be syncing with someone ELSE who is syncing with them, which makes it very hard to detect and abort these cases which will cause stack overflows. As you can see it’s happened before:

image
image2106×1708 1 MB

I’m looking for the best way to stop these cases. Any help is appreciated.

1 Like
#2

I would rewrite the logic. Instead of a player syncing with another player, have a table of “tracks” you keep track of.

A “track” represents an ongoing animation at a certain time location. (One way to setup tracks: each player has/owns a track and they control what the animation is)

Any number of players can be associated with a “track” that they are synced to.

This should remove your need for recursion altogether.

1 Like
#3

A lazy fix is to use your stack (which is not memory efficient and much much slower)
For example, my script that calls require on every child, and calls every child that that child has, until there is no more child:

local Traverse
local Loop = function(Object)
	for _, Object in next, Object:GetChildren() do
		Traverse(Object)
	end
end
Traverse = function(Object)
	require(Object)
	Loop(Object)
end
Loop(script)

Can be translated into a stack lazily by using:

local Stack = {}

for i, Module in next, script:GetChildren() do
    Stack[i] = Module --// Push the first items to the stack
end

repeat
    local Module = Stack[#Stack] --// Pop item from the stack
    Stack[#Stack] = nil --// set it to nil so wont' get the same item again.
    
    require(Module)
    
    for _, Module in next, Module:GetChildren() do
        Stack[#Stack + 1] = Module --// Pushes items to the stack
    end
until #Stack == 0 --// Empty stack means we are done!

However, this is not optimal and run much slower.
My test shows that a stack-based quicksort is about 60 -90% slower than the recursive implementation in lua. (Not to mention that the order has to be reverted since it is a last in first out structure and makes things a lot trickier)

As TheGreat_Scott has mentioned, you should be looking for an iterative approach that doesn’t use a queue/stack. (These are usually last resort)
But it is of course up to you.