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

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.

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.

Thanks for the reply ApochPiQ,

My only concern with that is as the map gets bigger, the duplication checks are going to grow very quickly.

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.

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

Only create edges in the ne,e,se,s directions as you iterate?

Though really I'd have to agree that one-way edges is probably better for usage, since you generally want to know what outbound edges are available for a specific node. If your edges are of uniform weight you can even just represent them as a vector of destination node pointers within each node.