Jump to content
  • Advertisement


This topic is now archived and is closed to further replies.


Generating optimal graphs from node connections

This topic is 5524 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

Ok, I''m not sure of all the terminology here, so bear with me. I have a set of nodes, each of which has a link to other nodes... basically, a graph structure. The main problem is that I need a 2D representation of this structure, with the following constraints: - all links are of a roughly equal weighting and should attempt to reflect this in the 2D distance as far as possible. - where possible, links should not cross. I''m especially looking for a system that can fulfill both criteria, although separate algorithms for each one - even if mutually exclusive - may still be useful. One application of this is in producing an auto-mapper for text-based adventures, where the nodes are rooms connected by north/south/east/west links. This application needs both the constraints above in order to produce a reasonable-looking map. I expect the direction of the exit could be fed into the algorithm as well. I''m also interested in more abstract graphs, such as plotting links between websites or whatever. In this case I expect that initial node positioning might be random, and adjusted later. My first thought is to go with some sort of genetic algorithm, where I try a few random graphs, look at how well it fits the constraints, and then use that as the fitness for the genetic algorithm, eventually breeding the best graph. But I think there might be a more guaranteed way to achieve this. [ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post

Link to post
Share on other sites
I''ve seen a method, often called "force-directed layout", where you insert springs between each connected node and then simmulate the forces on the nodes until they reach an equilibrium. Here''s a web site with some Java applets (with source) that use this method. It results in pleasing results some of the time.

I''ve also seen refernce to heuristic algorithms being applied to this problem (simmulated anealing, genetic algorithms, etc.), but I have no experience along those lines.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!