Advertisement Jump to content
Sign in to follow this  
nrgyzer

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.

If you intended to correct an error in the post then please contact us.

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?

Sorry for bad english...

 

Thanks in advance!

Share this post


Link to post
Share on other sites
Advertisement

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.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!