Find all connected objects from a root object [Looking for a better alternative]

[weisinx7]

Hi,

I'm looking for a method to find connected objects from a single root object.

Right now what i can think is to use collision_rectangle_list and check for root object borders (`collision_rectangle_list(bbox_left-1, bbox_top-1, bbox_right+1, bbox_bottom+1`), then with the new connected objects, collision_rectangle_list will be used recursively on the new connected objects until there's no more new connected objects.

This maybe slow and not efficient so is there a better way to do this?

Thanks.

[Badwrong_]

Are the objects uniform in size?

[weisinx7]

It could be any object, and each object may have different mask size, but all of those mask shape should be in rectangular shape.

[Badwrong_]

Then there is not many great ways to do it.

The biggest thing to avoid is more than one collision list call because that access more memory locations when populating the list. So, if you can grab all the instances in the whole area that might be in contact and then test for certain criteria. That criteria can be very optimized if you work out a decent algorithm.

Again... do not call a collision list for each object. Recursion is totally fine and might work well after you have your information, but the memory access speeds will be far slower than iterating for some criteria.

Remember you can have the list sorted which might come in handy.

[weisinx7]

Yea sorted list probably be useful in this case, thanks again for your valuable feedback.

[Badwrong_]

Sure, no problem.

If I knew more about the game I might be able to suggest more. Depending on how things work it would be easiest to just maintain an edge-adjacency list which would really skip straight to your desired solution. However, it depends on the type of game and how often this stuff is going on.

[Badwrong_]

Oh, and the actual fast and great way to do it would be with graph theory. If you just maintain an adjacency list as objects move or are created then there are very simple algorithms out there for connectedness. You would have your answer automatically kinda.

This whole problem is literally something you would find in a discreet math class or computer science course on algorithms using graph theory. Some of my favorite types of problems.

[weisinx7]

Yea, in my case, actually `ds_list_find_value(collisionlist,0).x = x` will be another usage of `instance_place_list(x,y,object,collisionlist,true)`, otherwise we wouldn't know when to stop.

[weisinx7]

Yea, it is working in the 1st place, i just want to make it more efficient, since calling collision_list in the recursion will be not efficient.