Hello everyone!
I’m currently trying to create an ingame editor for the small project that I am working on, but I’ve stumbled upon a problem that I can use some advice on. A brief summary of the project to make it easier to understand the problem:
It’s a top-down 2D game in which the player controls a vehicle
In the grid-based editor, the player gets tools to construct his vehicle out of a selection of sprites (game objects) with specific game mechanics attached to them (weapons, wheels, etc.).
Parts can be freely added to any unoccupied space on the grid (certain rules apply, of course, but they are uninteresting for the problem)
Placed parts can be freely removed.
After the player is finished, he can save the vehicle and then later select that vehicle to play with.
Now, the problem that I have is establishing a fast and efficient way to dynamically calculate what exactly the “vehicle” in the editor is - meaning which parts placed on the editor’s grid to consider a part of the vehicle and which not. I will try to visualize this:
The green part is what I would consider the “valid” blob in this grid, because it is the biggest. As parts can freely be placed on any grid slot, going for the biggest blob as the main one seems practical to me.
The red parts are individual blobs of parts that may or may not have been connected to the green blob at some point. They are considered invalid, will not count towards vehicle data and not be saved as the vehicle is exported from the editor.
According to my research, I seem to be facing a fully dynamic connectivity problem, as in that my “graph”, which I assume would to contain all the part-holding grid elements of the editor, can be freely added to and removed from. Now, I’ve done a lot of reading, but I can’t seem to find a way to make it work in my head.
Can anyone point me into the right direction, e.g. with some code examples, or tell me if I’m overcomplicating things? Maybe there’s a much easier solution in Unity, which I am unable to find.
Thanks for reading - and any suggestion you may provide.
This reminds me of a British museum path finding algorithm I wrote long ago. It was terribly inefficient at large scale but was reliable.
Basically your problem breaks down into one I think of as shape identification.
In your example (provided the block count isn’t really high… mine lagged at 500x500 grid) you can walk the grid until you find a block that isn’t blank.
Then you recursively search for neighbors that are also not blank.
For each recursive call you store the list of returned non blank neighbors until there are only blank neighbors returned. Don’t follow neighbors that you’ve already added to the cell stack.
This is your shape definition… cache it for reference later on.
Continue to walk grid until no more shapes are found or reached end of grid. Again don’t follow cells that you’ve already marked.
Now that you have the individual shapes (arrays of cell numbers belonging to a given shape) you can decide which is the main one. In your example the one with the most cells would be the target shape.
If your shapes would not be considered part of the same part along diagonals (i.e block at 1,1 would not be in the same part as (2,2)(2,3)) your recursive list for neighbors would only need to return the adjacent blocks not ones on a diagonal.
Sorry I don’t have sweet sweet code for you. Best of luck.
BPPHarv, thank you for your reply and thoughts. I have considered such an approach, but at least my implementation of an idea like this caused unsustainable performance due to the way I want the editor to work.
Since you can keep the mouse button pressed and thus “spray” parts all over the grid, having to recalculate the validity of all placed parts every time for the entire grid using DFS or similar does not work.
I have now opted for an implementation using a Dictionary, which contains a List of my grid class as value and an integer ID as key. When placing parts on the grid, each blob of new items gets its own ID and is added to the respective list. Thus, referencing to my example above, the green part in the dictionary would sit at ID 0 as key, with a list of all the grid items in it as associated value.
That way, I have solved all the problems of adding new parts to the editor. If they do not have any neighbors, a new KVP for the Dictionary is created and if they find one (or multiple) - e.g. because I am connecting two part blobs by placing an new part - I can easily find the ID of the neighbors and thus the List they belong to and merge all of them into one.
Another story is going to be the deletion of parts from the grid, especially since it could cause blobs to separate, making it necessary to split lists. I have not yet tried it, but it must be doable as well. I think that here, I will have to use some sort of search through all members, but I have yet to figure out. If anyone reading this has an idea, I’m appreciative for any input.
