# How can I incrementally generate an graph?

I just started a new project in which I'd like the game world to consist of procedurally-generated locations connected by teleporters. After a bit of research, I've discovered this to be called either "graph theory" or "bloody complicated", depending on who is discussing it. Unfortunately, I've found very little information on generating graphs; most of the tools I've seen are directed toward examining existing graphs.

Assuming I have the terminology correctly sorted out, my requirements are that the graph be:

• simple — no location (vertex) should have a teleporter (edge) which connects back to itself, nor should two vertices have multiple edges connecting them
• connected — it should be possible to travel between any two vertices in the graph (though I don't foresee ever needing to find the path; simply knowing the player could find one if they chose to is sufficient)
• cyclic — there should be more than one path between any two vertices
• undirected — all edges can be traveled in either direction
• infinite — if the player so wishes, they should be able to travel indefinitely, with the graph continuing to generate incrementally as they approach its outermost unexplored vertices
• locally finite — a vertex's degree should never change after the player has visited it
• stably labelled — each vertex represents a location which will itself be procedurally generated from a seed; the same seed must be assigned to a vertex regardless of what path the player used to travel there or how large the graph is when they do

I've had some ideas (which I've not yet tried to implement) regarding using the local maxima of 2D perlin noise as vertices (the input x and y could then be used as its label), but that feels clunky and overcomplicated.

Is there a better way to generate a graph like this? I'm developing in Python 2.6 using Panda3D and numpy, and would of course be willing to look at including other libraries if they'll help with this problem!

Edit

I think I've done a poor job explaining some of my requirements, so it's illustration time! Hopefully, this will clear things up.

What I mean by having stable labels is that I want, for example, Player A to be able to do a bunch of exploring and find, among other things, a cyclic path back to their starting location and a mountain that looks like a cat. His game now looks something like the following (vertices are numbered with their seed and edges with the order in which the player traversed them). He started on vertex 8329 (green) and Happycat Mountain is in vertex 6745 (blue).

Player A's good friend Player B is a fan of cats, so he wants to show it to her. He gives her the root seed for his world and directions along the shorter route to the mountain of interest. Her game should now look like this:

The problem I'm currently having the most difficulty with is "How do I generate the same seeds for Player B when her exploration hasn't followed the same path?" That's what led me to the idea of using Perlin noise — as long as the same root seed is used, the maxima won't move, so their coordinates could be used as stable vertex seeds.

• Why would a connected graph not suit this? mathworld.wolfram.com/ConnectedGraph.html I may be missing the point though. If a user wants to go from one location to the other and they're all connected, give them a list of locations and move their position on the world map to the new location. – brandon Feb 22 '12 at 2:11
• @brandon — "Connected" is the second property I list. :-) – Ben Blank Feb 22 '12 at 4:15
• my point is, if you can go from one node to any other. When they visit a teleporter, give them a list of all nodes they have visited except this one. There's no need to have a graph, you keep a list of all visited nodes and their locations and you just teleport to the location they pick. Am I misunderstanding? – brandon Feb 22 '12 at 19:48
• almost all of your descriptions of those terms are correct, except for "cyclic" and "locally finite". The first restricts your graphs to be what they sound like - a circle. A term you could use for the requirement that there be more than one paths from one vertex to another is "2-connected". "Locally finite" just means that each vertex has a finite number of edges. – Harry Stern Feb 22 '12 at 22:02
• @Harry Stern — My understanding is that cyclic graphs are graphs containing at least one graph cycle. It sounds like you're talking about a cycle graph, which is a graph consisting of a single graph cycle and nothing else. I'm specifically not looking for graphs which are "2-connected" (see "simple"). And yes, that's what I meant by "locally finite". – Ben Blank Feb 22 '12 at 22:21

You can't make an infinite graph. Your memory is finite, thus the numbers of vertices and edges are also finite. What you can do is make a finite graph then add more to it. You seem to have realized this but I think it is important it be explicitly stated so you don't go down a dead end path.

You must be very careful when talking about "outermost vertices". A graph is a set of vertices, a set of edges, and a function that relates the two. There is no set geometric interpretation unless you apply one. For example: both of these pictures show the exact same graph. In the first image, vertex 2 could be considered an "outermost" vertex, yet in the second image vertex 2 would not be considered "outermost". If you considered three dimensions, you could say all vertices are "outermost".

This means you must have some other information for you to be able to know what an "outermost" vertex is. You could use (x,y) pairs as that would give you an easy to visualize geometric representation, however I don't think you need to go that far. From what you say, all you need to know is what vertices are in the graph already.

If you ran this every time you visited a vertex:

if(this.needsNeighbours)
{
List<int> connections = genRandomNumbers(n);
foreach (int connection in connections)
{
//Simple graph
if(connection == this.seed || this.hasNeighbour(connection))
{
continue;
}
//Connections to already existing, unvisited vertices
else if(nodeMap.containsKey(connection) &&
nodeMap.getByKey(connection).needsNeighbours)
{
}
//Grow graph with new vertices
else
{
}
}
this.needsNeighbours = false;
}


your graph would satisfy all your requirements except for being cyclic. I don't know if you actually need a guarantee. If you do then you could specifically select an unvisited node and make a connection, that would guarantee a path between the current node and an already visited node as all unvisited nodes are connected to at least one visited node and since you had to have visited a visited node to get where you are there are now at least two paths.

It is simple because there is an explicit check for it, connected because all new nodes get at least one connection, locally finite because edges are only added before you visit or on your first visit, and only to unvisited nodes. Technically its not undirected, but functionally it is the same as you create a directional edge in both directions. You can label the node anything you want, I use the random number generated, but you could add other parameters to the constructor, one being your seed.

• You perceive exactly what I meant by "infinite" and your point about "outermost" is well taken — I've tweaked the verbiage in my question. However, either I'm not understanding your generator correctly or I explained my needs poorly, as this looks like this would not generate the same seeds for different paths to the same vertex. I've added some illustrations to my question which will hopefully make more clear what I'm trying to accomplish. :-) – Ben Blank Feb 22 '12 at 21:32
• I see what you mean now. That is a bit harder. What you would need to do is change the genRandomNumbers call to a function which always returns the same set of numbers for its input, and use the node's seed as the argument. This would guarantee that you would get the same connections and seeds no matter which path you take or which node you start with. You would have to be careful that the set of numbers for node B which A connects to also contains A so you get your undirected graph property. If you don't do this then you get a directed graph. – Chewy Gumball Feb 22 '12 at 23:11

One method:

init:
root = generateLocation using random seed
store root's seed
place player in root location

when the player enters a new location:
release the memory used by locations that are further than 1 edge away, but keep their seeds
generate some neighbors for the new location. for every neighbor n:
gen.seed(getSeed(n))
n = generateLocation using n's random seed
numCyclicEdges = gen.randint(0, 1)
create numCycleEdges edges to existing locations

getSeed(n):
if(n already has a seed) return n's seed
else return randomSeed()


There are lots of details I left out, but this should capture the general idea. You may want to keep neighbors in memory that are more edges away from the current location, depending on how much world-distance there is between portals, much available memory there is, etc.