Jump to content
  • Advertisement
Sign in to follow this  
too_many_stars

algorithmicly connecting a graph

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

Hello everyone,

 

I can't quite wrap my head around this problem so I need a little help please.

 

Give a map represented by a std::vector<int> map that might look like this...

 

0 0 0 0 1 0

0 0 0 0 1 0

1 0 1 1 1 0

0 0 0 0 1 0

 

where '1' is an obstacle and '0' is a free moving space, and where the distances between the

values are arbitrary.

 

I would like the following,

 

one std::vector<Node> nodes;

two std::vector<Edge> edges;

 

I know potentially, that every 'node' in my graph (that being a 0) can have 8 possible edges.

 

What I don't know however, is how to iterate over my graph, and keep track of which edges have been already created.

 

For example, map[0] will have 3 edges to each of its neighbours. Now, when I move to map[1], and create the edges to its neighbours, how do I check, or keep track of, whether map[0] already has an edge to map[1].

 

 

Thanks,

 

Mike

 

 

 

 

 

 

Share this post


Link to post
Share on other sites
Advertisement
Just look into the container of edges while you're building it. If it already contains a matching edge, don't add a new copy.

Share this post


Link to post
Share on other sites

Is duplication that big of an issue?  Otherwise, I consider it a feature.  Take a node where the edge is actually the actor hopping down a cliff face, or entering a one-way teleporter, etc.  Or even going up vs. down a ladder.  Having separate edges for going from 0-->1 and 1-->0 means you can cost them out differently.

Share this post


Link to post
Share on other sites
You can store edges in an associative container instead of a vector to mitigate that. For example if you have:
 
std::multimap<EdgeID, std::pair<SourceNodeID, TargetNodeID>>
You can hold both one-way edges (as ferrous described) as well as having fast lookups for duplicates. Although if you do one-way edges then duplicates shouldn't ever appear if you're building the map correctly, i.e. one cell at a time with no backtracking. Edited by ApochPiQ
Corrected code snippet

Share this post


Link to post
Share on other sites

Thanks ferrous and ApochPiQ, I understand it now.

 

I am beginning to think that ferrous has a good point, duplicate edges are not a big deal and might come in handy. Since it's my first time considering this problem, it did not occur to me.

 

Thanks again,

 

Mike

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.

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!