I've been talking about Infiniscapes and Combobulators and GridTrees now for a long time. Now the plugin is getting close to release, so I figure that I should post a thread. It's not quite ready yet. I'm still trying to make it as user friendly as possible, but for the moment I thought a simple guide on how you can use GridTree to help you generate infinite worlds would suffice as an introductory thread - so here it goes. This might get very conceptual and confusing, so bear with me till the end - it WILL be worth your while. I promise.
GridTree is a data structure. It is a nested tree of grids that represent data that already exists. You can use this data to create persistent worlds that don't have to be stored in memory. With GridTree you start with a grid, and you choose a point on that grid and move down - and that point expands into another grid. A grid of WHAT you say - a grid of seeded pseudorandom numbers that define what you are trying to represent - be that a small island, a city, a world, a universe, or whatever. This will make more sense as I explain it - I hope.
The example I'm going to be using frequently throughout this thread is CaveEntrances on Planets. Say I would like to place cave entrances randomly on each one of my planets in my game. There is a 50% chance that at any given point on the Planet layout, a CaveEntrance will spawn. (That's a lot of cave entrances, but bear with me for the sake of example.) There are a lot of planets - and each planet is stored in a System, which in turn is stored in a Sector, which in turn is stored in a Universe. That's a LOT of planets to store - and a hell of a lot more cave entrances! How can GridTree help me out here?
<img src="http://content.screencast.com/users/Arsonide/folders/Jing/media/39b17d8c-a48b-423c-b630-eccbfaabd83a/2011-05-05_0319.png" border="0">
When you first create a GridTree - you will be staring at the properties. Here you will define your top grid. The top grid is static, and represents the BIGGEST representation of your area - worlds, universes, etc. The size is how many points are in that grid - so for this example each one of those points would be a Sector. But wait Arsonide! You said this would help me generate INFINITE worlds you liar! Why is the top level sized?! Well, due to memory constraints, we can only poll out for data about 4,294,967,295 in either direction (positive or negative) before things start to loop. Every game has this limitation, including Minecraft. The cool part about GridTree is that you can go down to subgrids to expand your worlds exponentially. In Void Runner our top level is only 100x100, but each one of those points is full of sectors...and each sector full of subsectors. You can keep subdividing it as long as you like in this way. You could theoretically reach the end of the universe, and if you did I would personally send you a cookie, if you hadn't died of old age at that point. Back to the subject - before we can actually read data from a Planet, we need to define all of the grids between where we are now (Universe), and where we want to be (Planet). We do that at runtime with an action.
<img src="http://content.screencast.com/users/Arsonide/folders/Jing/media/a42d991b-c526-44df-a142-2cf6ea4043b7/2011-05-05_0321.png" border="0">
You will notice a new term here: "depth". Depth is how far below the top level you are digging into the tree. The only time you ever need to think about this is when you are setting up your grids, but it is pretty self explanatory. Notice how the depth rises as we go down. You can probably guess that our top level (Universe) is at depth 0.
So now our grids are set up and ready to use! Huzzah! However, before we can pull data from any of the grids below the top level, we have to set our position on each grid. This is very simple to visualize - and is done with a second action.
<img src="http://content.screencast.com/users/Arsonide/folders/Jing/media/6f1592dd-2cdd-4327-8939-36e106d75bf5/2011-05-05_0323.png" border="0">
That is your position on each grid. So now we know where we are looking at for every single layer down to the planet. It would read kind of like this: Sector (3903, 390235), System(5, 4), Planet At (5005, 3533), Planet Position: (3356, 3363). Now in Void Runner we actually only use one dimension of System - to define the orbital pattern. So to define each planetary orbit ( [0,1] first from the sun, [0,2] second from the sun, [0,3] third from the sun, etc.) I say that because a grid does not have to be two dimensional if you don't want it to be. It can represent whatever you like. In this particular example those numbers are high because those are the position on the layout that that planet occurs at.
Now that our positions are set up correctly, we can pull data from any of these grids! Any of them. If we wanted to view a sector map, we could pull a list of all the sectors around the one we are at. If we wanted to check and see if a cave was at a particular position, we would do it like this with an expression...
<img src="http://content.screencast.com/users/Arsonide/folders/Jing/media/1a462dc4-022a-4d08-995d-43958bf873c1/2011-05-05_0327.png" border="0">
So at that particular point we check if there is a cave entrance. There is a 50% chance of this occurring. Keep in mind if the player moves up a grid, that you will have to reset positions. polling any grids below the positions you have set will not work.
So WHY is all of that necessary, you ask. Well some things are just too large to store in memory. GridTree automatically gives each grid its own seed, and every grid seed is based on the one above it...all the way up to the top grid...in this case the universe. That means that any time you come back to a particular planet and check that position - the cave will always be there. You're not storing the entire universe on a hard drive or in memory - you are letting GridTree worry about all of that for you. All you do is set up the grids, maintain your positions on them, and pull data. Your world will remain persistent. If you change the seed, the world will change with it.
These numbers remain persistent, but what can you use them for? Well imagine that we seeded Noise 2.0's planetary noise with the top level seed of GridTree. At that point we could use the camera position of Noise to poll GridTree for information about things like bushes and trees within each screen on the planet. You could also have a small chance that each screen could have a city in it. Buildings in a city could be their own grid, and GridTree could hand out seeds to each building that designate where the furniture inside that building should be arranged. GridTree seeds could determine the weather of a particular planet, or what sort of animals spawn there, or what factions spawn there and if they are at war - and in that particular planet these things will NEVER change despite being completely procedural.
GridTree expands your horizons. Alright, this might be a bumpy release, because there is a lot of experimental stuff in this at the moment. Until I'm satisfied with the testing it's gone through, I'm not going to dress it up very much. No readme, just the plugin and the example cap. I'm also keeping this in the Work In Progress forum until I consider it stable, which probably won't be until all of my projects are complete, so expect the WIP forum to fill up a bit. <!-- s:P --><img src="SMILIES_PATH/icon_razz.gif" border="0" alt=":P" title="Razz"><!-- s:P -->
By the way, if some of you are confused about the "Auxilliary Generator" that is simply a seeded random number generator. It is in no way associated with GridTree, it's just there as a utility.
I tried to make this uncrashable, but in all likelihood you guys will find ways to crash Construct with it. IF YOU DO - POST WHAT YOU DID HERE. I will fix it. Debug mode is there to help you figure out why things are acting funky for you if they are. Most of GridTree's problems happen at runtime, and if you enable debug mode, it'll pop up messageboxes at runtime telling you what's up.
UPDATE: I have released a new version of this plugin with some exciting new, slightly experimental options. There are four new actions that will assist you in changing the GridTree. Allow me to explain.
Imagine you have a grid representing a forest of trees, but your player wants to chop one down. Before, you'd have to keep track of this change the player made, save it somewhere, and overlay it on top of GridTree's procedural data. Now, GridTree can do all of this for you.
There are two actions: set value at, and revert value at. These actions will ask you what grid you're referring to, what data type you're referring to, and what position you are referring to. If you set the value there, GridTree will now output that value that you set there instead of it's procedural data. This will allow you to "cut down a tree" so to speak. If you want to revert the change, that action is there as well.
There are two more actions available as well that save the entire GridTree to a file, including all of your manual changes...and another to load this file into the GridTree.
This expands the possibilities of the plugin quite a bit. I hope you guys like it. There is a new "advanced" example in the zip that shows off these features, with comments and stuff. The example actually is a procedural forest with trees you can chop down. Keep in mind this is still in alpha, but is now back in active development. Please reply with any gripes, complaints, or praise, or bugs, or whatever. It will help me as I continue to develop this.
Download GridTree!
Donate!