By complex data structures, I mean like groups of objects associated with an object, with full control and interaction and garbage collection. In Scratch, this would be utilizing clones in a hierarchical fashion.

The simplest example I can come up with is two kinds of clones, parents and children. A parent can have any number of children, but a child can only have one parent. You can delete a parent which will delete all children, and delete a child which will only remove the pointer from the parent. There also can be child-to-child interaction, child-to-cross-parent interaction, parent-to-parent interaction, and so on.

I've established already that in order for this all to work, there needs to be global lists to keep track of pointers. Let's say I have two global lists for parents, p.x and p.y, and two global lists for children, c.x and c.y. Parents' coordinates are absolute and children's coordinates are relative to a parent. Each parent must be able to keep track of which children are its own, so this means having a list of pointers to child objects, and each child must have a pointer to its true parent.

The simplest solution to this is to not delete items once you have made them. The biggest downside is your object lists will grow super huge with unused items after children and parents were deleted.

But I hate this solution because in the past, I have wound up with extremely large lists filled with “dead” objects. I want a solution that satisfies three constraints:

1. Use global lists to hold all public clone attributes, including a range of pointers to other clones
   
2. Garbage-collect unused objects in lists to avoid memory leaks
   
3. Must be efficient, i.e. no using broadcasts to swap IDs.
   

I've tried a lot of different solutions for a simple way for clones to do this, but I've given up. If not impossible, it's impractical. Can you do better?

Ugh, I absolutely hate the problem that you are experiencing. Items cannot be deleted, because all the pointers will point to the wrong location. My solution would be to use low-level memory management, chunking list elements into “free” and “used” sections. When children are deleted, their spaces are marked as “free,” and when children are allocated, the program goes through the lists keeping track of free and used memory, until it encounters a free space large enough to hold the child. If no free spaces are found, the appropriate amount of elements are added to the list. If the last block of memory in the list is free, it is deleted.

This approach doesn't eliminate “free” spaces between allocated parts of memory, but prevents the list from growing unnecessarily large. If you want, you could keep the list a fixed size, and instead of adding new elements if not enough contiguous free elements exist for a new clone, make the project give a “not enough memory” error.

P.S. I have written such a memory allocation system, for a scrapped virtual machine project. I can share it on a test account, if you would like to see it.

What you can do is keep a “free list”, which keeps track of where in memory is free space, and use that to allocate objects first. If you use the free space itself efficiently, you can actually store this free list without having the size overhead of another scratch list, by having a variable pointing to one free block and each free block pointing to another one.

Thanks for the responses, but I can't be sure if those ideas would work until I see a proof of concept. And remember, this is a lot more difficult because association must be full-duplex (parent points to child(ren) and child points to parent).

It would probably be a good idea to read about how existing memory management systems work, such as malloc. Once you understand that, implementing a parent/child hierachy system should be fairly simple.

Is the amount of attributes that each clone has fixed?

Chibi-Matoran wrote:

Is the amount of attributes that each clone has fixed?

Number of attributes doesn't change, but the size of the attributes does (i.e. an arbitrary-length list of pointers)

novice27b wrote:

It would probably be a good idea to read about how existing memory management systems work, such as malloc. Once you understand that, implementing a parent/child hierachy system should be fairly simple.

Okay, just give me a week or two to contemplate low-level memory management ._.

Make a garbage collector? Or manually allocate/free objects on a heap?

novice27b wrote:

It would probably be a good idea to read about how existing memory management systems work, such as malloc. Once you understand that, implementing a parent/child hierachy system should be fairly simple.

To add to this, I don't think clones are a good idea. Managed lists are the way to go.

novice27b wrote:

novice27b wrote:

It would probably be a good idea to read about how existing memory management systems work, such as malloc. Once you understand that, implementing a parent/child hierachy system should be fairly simple.

To add to this, I don't think clones are a good idea. Managed lists are the way to go.

+1 Clones are too labor-intensive, so they are not appropriate as data structures. Only use them if something needs to appear on the screen, and recycle clones when possible.

Plus there's a limit to how many clones you can make

Chibi-Matoran wrote:

novice27b wrote:

novice27b wrote:

It would probably be a good idea to read about how existing memory management systems work, such as malloc. Once you understand that, implementing a parent/child hierachy system should be fairly simple.

To add to this, I don't think clones are a good idea. Managed lists are the way to go.

+1 Clones are too labor-intensive, so they are not appropriate as data structures. Only use them if something needs to appear on the screen, and recycle clones when possible.

Clones aren't exactly labor intensive, they're just not well structured. I get where everyone is going with this, because as far as I'm concerned clones and local lists don't work together very well. I'll see how well parallel lists work for me.

Edit: I forgot to mention one very important detail. I'm supposed to use clones because I NEED them for click-on events.

I think that the data should be independent from the clones, and that clones can be rearranged and recycled to represent different nodes/elements/whatever in the data structure. Will more elements exist than the amount of clones on-screen at one time?

Chibi-Matoran wrote:

I think that the data should be independent from the clones, and that clones can be rearranged and recycled to represent different nodes/elements/whatever in the data structure. Will more elements exist than the amount of clones on-screen at one time?

I agree; I have separated clones from the data so that they're just for on-screen rendering. A separate sprite handles the heap of objects using my Jagged Array library.

Yes, there will definitely be more simulated objects in existence than are shown on-screen. Since there is a bottleneck inherent to clones, I may just have to abandon that part unless I restrict the maximum number of objects to 300.

Zro716 wrote:

The simplest solution to this is to not delete items once you have made them. The biggest downside is your object lists will grow super huge with unused items after children and parents were deleted.

But I hate this solution because in the past, I have wound up with extremely large lists filled with “dead” objects. I want a solution that satisfies three constraints:

1. Use global lists to hold all public clone attributes, including a range of pointers to other clones
   
2. Garbage-collect unused objects in lists to avoid memory leaks
   
3. Must be efficient, i.e. no using broadcasts to swap IDs.
   

I've tried a lot of different solutions for a simple way for clones to do this, but I've given up. If not impossible, it's impractical. Can you do better?

What's the problem? Why can't you just use garbage-collection? What do clones have to do with this?

Jonathan50 wrote:

What's the problem? Why can't you just use garbage-collection? What do clones have to do with this?

I am trying to use garbage-collection, but it's becoming a hassle, even in situations without clones. Consider an example with a simple 3d engine: there are lists for storing point data (x,y,z) and lists for storing face data / pointers to point data (p1,p2,p3). There are hundreds of points and hundreds of faces pointing to 3 random points. Let's say I decide to delete the first point: point 2 because point 1, point 3 becomes point 2, and so on. All faces are now referencing different points. To fix this, I have to:

And that's just for faces. If I were to delete a face and its points, that would require three calls to the refactor routine. If we scale this up to have simulated objects with references to faces, groups of objects, etc… it just gets so complicated that I'm better off not deleting single elements.

The fact is there is a compromise between garbage-collection and speed in Scratch. If I want to make a perfect garbage collector for my project, it would freeze up my project every time I have to delete a clone, depending on how complex the project is. If I decide to let a clone-spawning project go rampant without refactoring dead items, it would allow my project to always run smoothly at the risk of a memory leak.

Clones are awesome for a lot of things, but making sure they can interact correctly poses a huge problem with garbage collection. The only way to interact with a clone is through broadcasts and input events, but this will stipulate that the interaction takes twice as much time due to the slight broadcast lag. So for garbage collection to work with clones, there can be no forcing it to happen instantly, and that's why I'm unhappy with it.

Zro716 wrote:

I am trying to use garbage-collection, but it's becoming a hassle, even in situations without clones. Consider an example with a simple 3d engine: there are lists for storing point data (x,y,z) and lists for storing face data / pointers to point data (p1,p2,p3). There are hundreds of points and hundreds of faces pointing to 3 random points. Let's say I decide to delete the first point: point 2 because point 1, point 3 becomes point 2, and so on. All faces are now referencing different points. To fix this, I have to:

Doesn't that script solve the problem though?

Jonathan50 wrote:

Zro716 wrote:

I am trying to use garbage-collection, but it's becoming a hassle, even in situations without clones. Consider an example with a simple 3d engine: there are lists for storing point data (x,y,z) and lists for storing face data / pointers to point data (p1,p2,p3). There are hundreds of points and hundreds of faces pointing to 3 random points. Let's say I decide to delete the first point: point 2 because point 1, point 3 becomes point 2, and so on. All faces are now referencing different points. To fix this, I have to:

Doesn't that script solve the problem though?

Yes, but that's just one easy case without clones. A predictable number of points per face makes it easy peasy.

Okay okay, I may be misidentifying the problem. I've got a handle on simple garbage collection, but that's only for structures with predefined number of associations, like 3 points per face. How would one efficiently define a range of pointers in this case? Start to end or an actual list? When trying to garbage collect such lists or ranges, it can get stressful.

Oh, will just having one big heap with garbage collection work for you? (Like in this project)
It makes things a little harder and it sort of treats Scratch as if it were Assembly, but you can make custom blocks for convenience.

Or you could have a list of list names, like for a point it would have faces.p1, faces.p2 and faces.p3? It would require hacked blocks though. Would that work?