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 outermostunexplored 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!
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.