View Single Post
Old November 5, 2012, 21:41   #3
Derakon's Avatar
Join Date: Dec 2009
Posts: 9,002
Derakon is on a distinguished road
Okay, so, correct me if I'm wrong, but basically what you want to do is have an infinite playing area where you explore as far as you like in any direction, and then backtrack and have the area you came from be consistent, without actually having to store that area?

Unfortunately, to keep the world consistent, you have to store something about it. That can be the entire world, or it can be a seed of some kind, but it has to be stored.

Let's say you do store absolute world coordinates. For example, say you generate your world in 100x100 chunks. Each chunk has a position in X and Y; we combine those X and Y positions into a single 32-bit number (X * 2^16 + Y), and pass that as the random seed to your dungeon generator. Of course this isn't a truly infinite playing field, but in my example it's 6.5 million blocks on a side (2^16 * 100), which seems entirely adequate. If you needed more, then you could increase the chunk size (e.g. make the map in 1000x1000 chunks instead, now you have 65 million blocks on a side). Or you could use more than 32 bits to indicate position: 2^32 * 100 is about 430 billion. How much time do you plan to spend on exploring?

You mentioned a "tree" approach. Presumably in this method, each sector would lead to the next sector. You'd be saved from having to store world coordinates, but you'd have to remember the "breadcrumbs" that lead from one node to another. For example, you start at node A, then you go to node B, then to node C. You want to backtrack to B, well, B has to remember that it attaches to A. For every node the player visits, you must remember not just the seed to generate that node, but also the connectivities to the other nodes. Now, this isn't much of a memory requirement, but it means you can't make a truly infinite world.

It also has another, less pleasant consequence: the world has no loops in it. Each node is generated without knowledge of the structure or placement of other nodes, so they cannot connect (or, if they do connect, the connections are probably not Euclidean). When A was generated, it probably had several outbound connections, but we don't know what nodes those connections go to. When the player traveled down one connection, we said "Okay, this connection goes to B". Then we repeat that with B to get the player to C. Now, C might overlap A -- or it might be nowhere near A. We have no way of knowing, and thus no idea if it's sensible for C to connect to A.
Derakon is online now   Reply With Quote