This site is currently in read-only mode during migration to a new platform.
You cannot post questions, answers or comments, as they would be lost during the migration otherwise.
+1 vote

I have an Array that may eventually contain a reference to itself. The simplest case would be something like this:

var cyclic = [1, 2, 3]

Now I'd like to recursively process such structures without ending in an infinite loop, e.g. something like that:

func do_something(structure, already_visited):
    if typeof(structure) == TYPE_INT:
        print("do something with it")
    elif typeof(structure) == TYPE_ARRAY:
        if already_visited.has(structure):
        already_visited[structure] = true
        for item in structure:
            do_something(item, already_visited)

do_something(cyclic, {})

Unfortunately this doesn't work because

already_visited[structure] = true

seems to send GDScript into an infinite loop (it is probably trying to build a hash value for the Array and ends up in the cycle...). So I can't put a reference to the cyclic array itself into already_visited - but what else can I put in there that will uniquely identify the Array? Is there something like Python's id() function that would yield, for example, the memory address of the Array?

Godot version 3.2.3 stable official
in Engine by (297 points)

Have you tried using the Array hash() function to identify the array?

Unfortunately, this ends in an infinite loop - GDScript never comes back from:

var a = [1, 2, 3]
var h = hash(a)   # hangs
print("This never gets executed")

Makes sense, too: GDScript seems to implement hash() without safety checks for cyclic structures, which I can understand - it would be a waste of time for 99.9% of the time. This is most likely the underlying reason of why adding a cyclic structure as a key in a dictionary hangs - there's an implicit call to hash involved.

You could add a flag to the actual array.
Maybe at element 0

elif typeof(structure) == TYPE_ARRAY:
        if structure[0] == TYPE_ARRAY: 
            return   # element has already been visited
        # the first element type is irrelevant and I use bool here 
        # second element contains the actual first element of structure
        structure[0] = [true, structure[0]]   

1 Answer

0 votes

you can use map
then get map.keys() as a set

by (14 points)
Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read Frequently asked questions and How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to [email protected] with your username.