[PLUGIN] GridTree (0.2)

Post and try out addons that are currently in development.

Post » Thu May 05, 2011 9:15 am

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?


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.


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.

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


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 -->:P<!-- 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!Arsonide2011-10-24 04:23:15
B
5
S
2
G
5
Posts: 221
Reputation: 2,272

Post » Thu May 05, 2011 12:36 pm

Interesting read. I can understand it now as it is, and I think it could be enough, if you'd make an commented example along with the release. From my experience, I usualy don't understand words and numbers, but when I see it in action I can translate it into my own language. Especially when there are also comments like - I did this because, this action will do this etc.
ImageImage
B
25
S
6
G
8
Posts: 773
Reputation: 6,643

Post » Thu May 05, 2011 12:43 pm

Wonderful mate.
Really nice.

I've spent the last couple of weeks using Lucid's "S" to give me reliable seeded numbers, and using them to create my worlds, but of course, this required me making sure that they all originate from the same seeded number.
This has worked well so far, but it's not finished yet, and I think I may have to halt work on that, as this seems to be perfect for what I need.

Really looking forward to this (I keep saying this about your plugins. :) )
I'm not going to ask how long before you release it........(taps fingers on desk)......[size=70:qwvvkajg][color=#FFBF80:qwvvkajg]How long?[/color:qwvvkajg][/size:qwvvkajg]

Krush.
B
2
S
2
G
3
Posts: 406
Reputation: 2,062

Post » Thu May 05, 2011 4:43 pm

I was just wondering are the generated numbers int's or can they be floats with decimals etc?

The recent Noise 2.0 plugin is really great, this seems to be used in combination with this new plugin soon to be released. So i am just wondering will there be examples also using the Noise 2.0 plugin that explain how to create these world style systems you describe here?

Also can this be used for other tasks than complex random worlds? Maybe quickly making a huge array of values etc? also when it is used for worlds is there much lag/slowdown while it's generating the values?
B
2
S
2
G
1
Posts: 121
Reputation: 1,092

Post » Thu May 05, 2011 8:32 pm

From what I understand there should be no lag, as all the data is based on the initial seed.
All you have to worry about is telling it where to look.
Image Image
B
161
S
48
G
90
Posts: 7,347
Reputation: 66,749

Post » Fri May 06, 2011 12:03 am

The algorithm is imperceptibly fast. However if you are polling it a LOT (such as for every pixel on the screen, in the aforementioned CaveEntrance example), then it's going to be slow no matter what, since you're running two long loops.

With Void Runner for objects on planets (rocks/trees/etc) rather than poll based on position, we use another one dimensional array. The first number signifies how many objects there are on the layout, and every even number after that signifies an X, and every odd one after that signifies a Y. This is kind of like storing the objects individually in an array rather than storing their positions. It's much faster.

You could also poll at a set grid rather than at each pixel. (So at every 100th pixel, or whatever).

I also would love to make it possible to poll a 2D area and have that return an array if possible - but I need to look up how to do that. That would make looping practically unnecessary.
B
5
S
2
G
5
Posts: 221
Reputation: 2,272

Post » Fri May 06, 2011 3:26 am

hey arsonide. I will definitely be using gridtree in my character and level generators, so thanks for the awesomeness. As a matter of fact, I have a bit of a feature request for you, if you don't mind (I could also add it myself to my local copy of gridtree when you're done, if you don't mind letting me borrow the source).
basically, defining the CallFunction and GetData functions at the bottom of Runtime.cpp, so I can control GridTree from another plugin.

but seriously. this is supremely awesome for procedurally generated obsessives like me :)
Spriter Dev
B
87
S
21
G
12
Posts: 3,240
Reputation: 16,461

Post » Mon May 09, 2011 1:48 am

Grid Tree release is imminent. I could probably release it now, but I'm going to spend the night searching for bugs and writing a better, less conversational guide. Also I've noticed releases always tend to go better if I don't do them at 3AM. :P Probably going to write an example cap as well. The example cap will not utilize Noise. Sorry. The benefits of using the plugins together are great but I want to display GridTree alone on its own merits.

The first release will probably be very unstable regardless of how much I test it. I want you guys to be brutally honest about any crashes you have. I am trying to make the plugin uncrashable - if you try to access data that doesn't exist yet or something, the plugin will simply refuse to do so. If you have debug mode checked, it will also alert you that you are trying to do something undefined.

Expect it tomorrowish!
B
5
S
2
G
5
Posts: 221
Reputation: 2,272

Post » Mon May 09, 2011 8:26 pm

Nice looking forward to testing this. :)

With the cap examples maybe you could just post some in the Your tutorials & example files forum area because then they would remain separate but you could just link to the plugin pages. From your descriptions of the new plugins these sound like they are all made to work well together as a set, so some examples that are using them together would be great.
B
2
S
2
G
1
Posts: 121
Reputation: 1,092

Post » Tue May 10, 2011 12:09 am

There's the release - be sure to read the last few paragraphs of the post. I updated them with a little more new information. PLEASE post any crashes you experience.

Any runtime funkiness can be reported as well, but please only report after you've checked it out in debug mode. Sometimes GridTree will return DEFAULT values if you are trying to reference things that don't exist or something, and this can cause runtime funkiness. This is to prevent your program from crashing, and it can be hard to identify, so if you are having some weird problems, click on debug mode. It'll tell you what's going on. If it does NOT tell you, then report a bug here.

Enjoy guys! ON TO MUSE! MY PATH OF DEVELOPMENT NEVER ENDS MWAHAHAHAHA.
B
5
S
2
G
5
Posts: 221
Reputation: 2,272

Next

Return to Work-in-progress addons

Who is online

Users browsing this forum: No registered users and 0 guests