# Merged and isolated bases

This topic is 1905 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi guys,

I'm creating a small game where every user can have multiple bases and can connect them using power lines. Connecting multiple bases means that ressources are available between them. For example... the first base has 10 units building material and a second base 10 units water. Connecting them means that the water of the second base is also available in the first base. The same for building material. The units available depends on the buildings of each base.

The user should be able to connect or disconnect multiple bases. This means the user can create an unlimited number of such power lines between his bases but can also destroy all the lines where every base is isolated again.

My problem is that I don't know how I can realize something like this. I already thought about creating a new base when the player creates the first power line between two bases, but what happens when the player destroys the power line? How can I unmerge the bases to be isolated again with his own ressources? I also don't know if this is the right way...

Any suggestions or ideas how to solve the problem?

##### Share on other sites

Make a graph where each edge represents bases (vertices) which are connected.

The algorithm reduces to finding the connected components of the graph (which partitions the graph into separate connected components). Run the algorithm every time a connection is made or removed.

It's the first algorithm in this pdf

http://math.hws.edu/eck/cs327_s04/chapter9.pdf

EDIT: You probably want to keep hold of the queues of connected bases though (each IntQueue q is a connected network in the pseudocode, so store those somewhere). You can use a set instead of a queue.

EDIT2: The above edit was wrong, q becomes empty. You want to store in a set each vertex that is added to q for the set of bases in a connected component. You end up with N sets where N is the number of connected subgraphs.

##### Share on other sites

Alright, thanks for the explanation. I'll try to implement the algorithm...

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 10
• 9
• 37
• 16
• ### Forum Statistics

• Total Topics
634128
• Total Posts
3015688
×