IGHTC (In-Game Huge Terrain Creator) Part 2
by Darrel Cusey · 05/24/2006 (10:25 pm) · 47 comments
So, the lesson learned is to wait until GG approves a resource before announcing it :-)
Here's just a quick update on the IGHTC project:
What I've Been Up To
All original pattern-layer code was successfully ported into TGE 1.4 HEAD, tested, and got a screenshot up. The test harness system will no longer be updated, and I'll be working strictly in TGE from this point forward.
I decided that it was going to be critical to have this as a wholly separate class, and so began development of the patternManager class, from which various other classes (like patternTerrain, for example) can be derived. For many of you out there, the Good Thing (tm) about this is that you'll be able to just drop a couple files into the /core directory and the /terrain directory, make a couple edits to some of the terrain classes and call it a day -- none of this mucking around with patch files. At least, that's my goal...
I've completed the implementation of the patternManager class, doing everything "the GG way" including figuring out how to instantiate the class without directly calling a new() method on it -- very nicely done, BTW. The first rendition of the patternManager has only these console variables available (since they are most critical): patternTerrainSeedX, patternTerrainSeedY, and patternTerrainLayers.
Currently, the system uses 5 terrain pattern layers by default, but you can go as high as 20 with minimal impact on performance. The vast majority of the getTerrainHeight() function uses bitwise operators and shift functions, so it's very fast -- it's about as close to Assembly code, I think, as possible. And is it ugly :-)
Unfortunately, if I want it to be possible to edit layer heights via the console, I'll have to create a separate variable for each ... it's either that or implement an ArrayType in the consoleTypes class, which I'm just not up for this year :-) So, you'll probably be seeing ugly variables like this patternTerrainLayerHeight1, patternTerrainLayerHeight2, patternTerrainLayerHeight3... etc :P ick
I've now got 3 slope functions that (a) work well in TGE and (b) create slopes that actually look nice in TGE. I was surprised at how much the rendering engine affects the look of the terrain being rendered. An identical terrain rendered as a mesh in DirectX 9.0c SDK looks a lot different than it does in TGE. Ideally, this will lead to something that will allow a developer to choose the types of slopes to use at the various layers. So, for example, you'll be able to select nice rounded hills for the lower layers, induction lines for the middle layers and jagged peaks for the top layers. No code behind this bit yet, but that's where I'm going with it. Of course, this means uglier console variables like patternTerrainLayerSlope1, patternTerrainLayerSlope2, patternTerrainLayerSlope3... ah well.
What's Soon
Re-building all the hooks to the various patternTerrain functions from a clean set of terrain source code files.
Clean up all the slope code.
Adding in the 20 patternTerrainLayerHeightX console variables (for now, I'll just use the same slope formulae for all layers).
Once I have the layer heights available to the console, it'll make it really easy to being tweaking the heights and the number of layers I'm using to make some better screenshots.
Posting and updated Development Screenshot, this time with more than 1 screenshot :-)
What's Next
Start working on the GUI to allow editing of the patterns and the layer heights. Dev Screenshot of that once it looks nice and is easy to use (and works).
Start digging into the process of "repurposing" the original heightMap array. My "crazy idea" at this point is to simply expand the size of the heightMap array (change BlockSize) so that it is equal to (viewDistance x 2) +1 so that only 1 rep of the texture is ever seen and then using setHeight to dynamically change the current heightMap to exactly match whatever happens to currently be on the screen. Then the various and sundry texturing, blending and lighting functions can do what they'd normally do -- not knowing that they are performing their functions on a heightMap that was just dynamically generated. That should get texturing, blending and lighting to work with IGHTC just like it works now with stock TGE -- at least, that's the theory.
Record a movie of flying across the terrain and another movie of doing standard height- and slope-based texturing to show how those editing functions now work normally with IGHTC.
... that's probably as far as I want to plan for now.
Thanks again everyone for your interest and support!
Here's just a quick update on the IGHTC project:
What I've Been Up To
All original pattern-layer code was successfully ported into TGE 1.4 HEAD, tested, and got a screenshot up. The test harness system will no longer be updated, and I'll be working strictly in TGE from this point forward.
I decided that it was going to be critical to have this as a wholly separate class, and so began development of the patternManager class, from which various other classes (like patternTerrain, for example) can be derived. For many of you out there, the Good Thing (tm) about this is that you'll be able to just drop a couple files into the /core directory and the /terrain directory, make a couple edits to some of the terrain classes and call it a day -- none of this mucking around with patch files. At least, that's my goal...
I've completed the implementation of the patternManager class, doing everything "the GG way" including figuring out how to instantiate the class without directly calling a new() method on it -- very nicely done, BTW. The first rendition of the patternManager has only these console variables available (since they are most critical): patternTerrainSeedX, patternTerrainSeedY, and patternTerrainLayers.
Currently, the system uses 5 terrain pattern layers by default, but you can go as high as 20 with minimal impact on performance. The vast majority of the getTerrainHeight() function uses bitwise operators and shift functions, so it's very fast -- it's about as close to Assembly code, I think, as possible. And is it ugly :-)
Unfortunately, if I want it to be possible to edit layer heights via the console, I'll have to create a separate variable for each ... it's either that or implement an ArrayType in the consoleTypes class, which I'm just not up for this year :-) So, you'll probably be seeing ugly variables like this patternTerrainLayerHeight1, patternTerrainLayerHeight2, patternTerrainLayerHeight3... etc :P ick
I've now got 3 slope functions that (a) work well in TGE and (b) create slopes that actually look nice in TGE. I was surprised at how much the rendering engine affects the look of the terrain being rendered. An identical terrain rendered as a mesh in DirectX 9.0c SDK looks a lot different than it does in TGE. Ideally, this will lead to something that will allow a developer to choose the types of slopes to use at the various layers. So, for example, you'll be able to select nice rounded hills for the lower layers, induction lines for the middle layers and jagged peaks for the top layers. No code behind this bit yet, but that's where I'm going with it. Of course, this means uglier console variables like patternTerrainLayerSlope1, patternTerrainLayerSlope2, patternTerrainLayerSlope3... ah well.
What's Soon
Re-building all the hooks to the various patternTerrain functions from a clean set of terrain source code files.
Clean up all the slope code.
Adding in the 20 patternTerrainLayerHeightX console variables (for now, I'll just use the same slope formulae for all layers).
Once I have the layer heights available to the console, it'll make it really easy to being tweaking the heights and the number of layers I'm using to make some better screenshots.
Posting and updated Development Screenshot, this time with more than 1 screenshot :-)
What's Next
Start working on the GUI to allow editing of the patterns and the layer heights. Dev Screenshot of that once it looks nice and is easy to use (and works).
Start digging into the process of "repurposing" the original heightMap array. My "crazy idea" at this point is to simply expand the size of the heightMap array (change BlockSize) so that it is equal to (viewDistance x 2) +1 so that only 1 rep of the texture is ever seen and then using setHeight to dynamically change the current heightMap to exactly match whatever happens to currently be on the screen. Then the various and sundry texturing, blending and lighting functions can do what they'd normally do -- not knowing that they are performing their functions on a heightMap that was just dynamically generated. That should get texturing, blending and lighting to work with IGHTC just like it works now with stock TGE -- at least, that's the theory.
Record a movie of flying across the terrain and another movie of doing standard height- and slope-based texturing to show how those editing functions now work normally with IGHTC.
... that's probably as far as I want to plan for now.
Thanks again everyone for your interest and support!
About the author
#23
Well, as you can imagine, the terrain system in TGE is bit complex. I've gotten help from a community member (and I'll leave it up to him if he wants to reveal his identity :D ) and we're building on top of the terrainManager code. Currently, we're still using terrain "blocks" since the entire engine is hardwired assuming the terrain blocks are there (and many parts of TGE access the block data directly instead of through an accessor method unfortunately). I don't want to yet say that we've got the terrainManager code doing 100% of what it was initially intended to do, but it seems very close. Plus, we've got the pattern layer system supplying the height data. Here's some highlights of the parts that _are_ currently working:
1. We can currently load up terrain that's 49 times larger than the stock TGE (a 7 x 7 grid of different terrain blocks). There are currently no issues with collision and no issues with the seams between terrain blocks (they are seamless and fit together perfectly). Also, the issue that I was experiencing earlier with "sawtooth terrain" has been solved. The plan is to use a 3x3 or 5x5 grid in the final version and "forward build" as you move across the terrain. This second part isn't in place yet, but that's the direction we're heading in.
2. The terrain that's built uses the pattern layer system I described in earlier posts so that no pre-generation of terrain is required (you just feed the system 2 pattern seeds and it does all the rest).
3. In-line smoothing of the generated terrain is working (it's not blocky anymore like you saw in the first DEV screenshots). I've got a couple algorithms in place that are very very fast (as you can imagine they have to be) and am working on a couple of other ones.
4. We can currently edit the terrain blocks built by the pattern layer system, save them, and re-load them. This includes editing textures, colors, heights, everything you can do in stock TGE. Edits that cross terrain block boundaries work fine as well.
So, things are going pretty good. It's taking awhile because every time we touch 1 part of the system, 20 different things break... but, we're working through it :)
11/30/2006 (3:28 pm)
Hey Jason and others,Well, as you can imagine, the terrain system in TGE is bit complex. I've gotten help from a community member (and I'll leave it up to him if he wants to reveal his identity :D ) and we're building on top of the terrainManager code. Currently, we're still using terrain "blocks" since the entire engine is hardwired assuming the terrain blocks are there (and many parts of TGE access the block data directly instead of through an accessor method unfortunately). I don't want to yet say that we've got the terrainManager code doing 100% of what it was initially intended to do, but it seems very close. Plus, we've got the pattern layer system supplying the height data. Here's some highlights of the parts that _are_ currently working:
1. We can currently load up terrain that's 49 times larger than the stock TGE (a 7 x 7 grid of different terrain blocks). There are currently no issues with collision and no issues with the seams between terrain blocks (they are seamless and fit together perfectly). Also, the issue that I was experiencing earlier with "sawtooth terrain" has been solved. The plan is to use a 3x3 or 5x5 grid in the final version and "forward build" as you move across the terrain. This second part isn't in place yet, but that's the direction we're heading in.
2. The terrain that's built uses the pattern layer system I described in earlier posts so that no pre-generation of terrain is required (you just feed the system 2 pattern seeds and it does all the rest).
3. In-line smoothing of the generated terrain is working (it's not blocky anymore like you saw in the first DEV screenshots). I've got a couple algorithms in place that are very very fast (as you can imagine they have to be) and am working on a couple of other ones.
4. We can currently edit the terrain blocks built by the pattern layer system, save them, and re-load them. This includes editing textures, colors, heights, everything you can do in stock TGE. Edits that cross terrain block boundaries work fine as well.
So, things are going pretty good. It's taking awhile because every time we touch 1 part of the system, 20 different things break... but, we're working through it :)
#24
Thanks soo much for your hard work!!!!
I am glad to hear the good news 5x5 or even 3x3 is better than what we have now :)
can't wait to see this working!!
11/30/2006 (4:17 pm)
@DarrelThanks soo much for your hard work!!!!
I am glad to hear the good news 5x5 or even 3x3 is better than what we have now :)
can't wait to see this working!!
#25
BTW, did you read John Carmack's interview about his megatexture thingy, where he disregarded the many years of research that went into adaptive terrain LOD as "wasted"? ;)
12/01/2006 (1:28 am)
Indeed, your work is very much appreciated. Torque's terrain code is, frankly, complicating things a lot.BTW, did you read John Carmack's interview about his megatexture thingy, where he disregarded the many years of research that went into adaptive terrain LOD as "wasted"? ;)
#26
Plus, adaptive LOD is definitely the direction Microsoft is heading with DirectX 10 -- you can see it's support has been expanded for vertex buffers, meshes, and even in some of the new curved geometry functions.
Also, maybe I'm just not seeing them yet, but I currently don't see any graphic cards (or upcoming ones) that will natively support texture sizes of 1 gigapixel -- so, you're still swapping textures into and out of the GPU -- but with the megatexture technology, you're just swapping in slices of 1 big texture that's (hopefully) in main memory. At least, that's the only way I can think of that they're accomplishing this. For example, if you look at the ATI Radeon X1650 (one their current top of the line models), it only supports texture sizes of 4k x 4k -- so, you wont' be loading that megatexture into the GPU anytime soon :D
I mean, ETQW looks great and all, but IMHO I think it's not the best direction for the industry to go in since it is making the coupling between your terrain geometry and your texturing even tighter than it already is.
Game worlds are only getting bigger (ie. Dark and Light), and the demand for larger and larger free-form exploration worlds is growing much faster than the technology to support it. And, the "clamping" effect that DirectX 10 is going to have on the introduction of new hardware features will only increase that gap. I predict that the demand for sophisticated procedural generation of terrain geometry, texture, lighting, even content is going to grow as the gap increases and the cost of content development increases.
But, that's all just my opinion, of course :)
12/01/2006 (8:27 am)
I read the megatexture thingy. I don't know why he's calling it "wasted" since the technology currently fuels several AAA game engines and several new games currently in development. Plus, adaptive LOD is definitely the direction Microsoft is heading with DirectX 10 -- you can see it's support has been expanded for vertex buffers, meshes, and even in some of the new curved geometry functions.
Also, maybe I'm just not seeing them yet, but I currently don't see any graphic cards (or upcoming ones) that will natively support texture sizes of 1 gigapixel -- so, you're still swapping textures into and out of the GPU -- but with the megatexture technology, you're just swapping in slices of 1 big texture that's (hopefully) in main memory. At least, that's the only way I can think of that they're accomplishing this. For example, if you look at the ATI Radeon X1650 (one their current top of the line models), it only supports texture sizes of 4k x 4k -- so, you wont' be loading that megatexture into the GPU anytime soon :D
I mean, ETQW looks great and all, but IMHO I think it's not the best direction for the industry to go in since it is making the coupling between your terrain geometry and your texturing even tighter than it already is.
Game worlds are only getting bigger (ie. Dark and Light), and the demand for larger and larger free-form exploration worlds is growing much faster than the technology to support it. And, the "clamping" effect that DirectX 10 is going to have on the introduction of new hardware features will only increase that gap. I predict that the demand for sophisticated procedural generation of terrain geometry, texture, lighting, even content is going to grow as the gap increases and the cost of content development increases.
But, that's all just my opinion, of course :)
#27
The basic idea is a fine one. The academics spending years refining their ROAM algorithms to support deferred updates on 16-CPU compute nodes are a little off track if their purpose is to advance the quality of terrain rendering. I want a terrain system that renders in < 10% of frametime and takes a minimal amount of RAM. It needs to be easy to debug and hard to break and it HAS to degraded gracefully on someone's shitty fragmented HD.
Multithreaded iterative LOD updates that can't deal with teleporting or warping cameras are great if you have 100% of CPU to burn, no misbehaved services in the background, and plenty of debugging time.
The techniques outlined here are a nice refinement on a pretty solid and VERY simple CLOD implementation, though I'm still not convinced they're sufficiently performant in a real game scenario.
Using DX10's programmability to implement more complex terrain schemes is a bit narrowsighted IMHO. :)
12/01/2006 (4:39 pm)
Quote:I don't know why he's calling it "wasted" since the technology currently fuels several AAA game engines and several new games currently in development.
The basic idea is a fine one. The academics spending years refining their ROAM algorithms to support deferred updates on 16-CPU compute nodes are a little off track if their purpose is to advance the quality of terrain rendering. I want a terrain system that renders in < 10% of frametime and takes a minimal amount of RAM. It needs to be easy to debug and hard to break and it HAS to degraded gracefully on someone's shitty fragmented HD.
Multithreaded iterative LOD updates that can't deal with teleporting or warping cameras are great if you have 100% of CPU to burn, no misbehaved services in the background, and plenty of debugging time.
The techniques outlined here are a nice refinement on a pretty solid and VERY simple CLOD implementation, though I'm still not convinced they're sufficiently performant in a real game scenario.
Using DX10's programmability to implement more complex terrain schemes is a bit narrowsighted IMHO. :)
#28
WOW! Hey, I'm not here to pick a fight with anyone. Josef just asked me if I'd read the Carmack interview, and I was just offering my opinion on it, that's all -- and who am I? Nobody. I don't believe I've ever insulted you, so I don't know where the "narrowsighted" comment is coming from. Man, this community is getting harsher and harsher every day :(
12/02/2006 (9:21 pm)
@Ben:WOW! Hey, I'm not here to pick a fight with anyone. Josef just asked me if I'd read the Carmack interview, and I was just offering my opinion on it, that's all -- and who am I? Nobody. I don't believe I've ever insulted you, so I don't know where the "narrowsighted" comment is coming from. Man, this community is getting harsher and harsher every day :(
#29
Well, OK, maybe I snapped a little bit on using DX10 for CLOD terrain. :) No harm meant. But I do have some strong opinions on terrain tech. ;)
12/03/2006 (2:17 pm)
I'm not being harsh at you, I'm being harsh at academics who don't have anything better to do than pursue useless technology paths. Have you seen the volume of research on ROAM-relatives vs. the volume on helpful things like practical LOD scemes, or effective texturing for large objects?Well, OK, maybe I snapped a little bit on using DX10 for CLOD terrain. :) No harm meant. But I do have some strong opinions on terrain tech. ;)
#30
12/03/2006 (4:55 pm)
Ahhh, yeah ok, I see what you're saying now. I brought up the DX10 example because I've been thinking a lot about the effect DX10/Vista is going to have on the gaming community lately - that's probably not the best example :) 
#31
I can't say how useful this code/product might be to TGE developers out there. I have been struggling to figure out how to give more terrain texture detail for our game. Since I am the only programmer and scripter and producer and level designer and game designer on my team, it makes it hard to spend any time at all try to figure something like that out. So far our solution has is to reduce the squareSize to 2 for now, which works for current starter levels but may pose issues with later levels. We have TSE, but don't want to use it as our game is a fairly simple one which should run on fairly lowspecced graphics cards(like my home Ti4200, which is my default MUST run well platform)
I am assuming there should be no issues using the default Terrain engine and/or IGHTC in the same CodeBase.
12/20/2006 (5:44 pm)
Darrel,I can't say how useful this code/product might be to TGE developers out there. I have been struggling to figure out how to give more terrain texture detail for our game. Since I am the only programmer and scripter and producer and level designer and game designer on my team, it makes it hard to spend any time at all try to figure something like that out. So far our solution has is to reduce the squareSize to 2 for now, which works for current starter levels but may pose issues with later levels. We have TSE, but don't want to use it as our game is a fairly simple one which should run on fairly lowspecced graphics cards(like my home Ti4200, which is my default MUST run well platform)
I am assuming there should be no issues using the default Terrain engine and/or IGHTC in the same CodeBase.
#32
There _shouldn't_ be any reason at all why you couldn't create a new class variable in the AreaManager class that you could use to wrap an if/else block around the old code and the new code calls. However, since the "terrain data" (deltas) under IGHTC are stored completely differently, you wouldn't be able to use IGHTC terrains under the default terrain engine or vice-versa.
12/24/2006 (11:48 am)
Our implementation strategy for IGHTC is to make as few changes to the existing codebase as possible and "farm out" new functionality to new classes (like the AreaManager and the PatternManager) wherever possible. There _shouldn't_ be any reason at all why you couldn't create a new class variable in the AreaManager class that you could use to wrap an if/else block around the old code and the new code calls. However, since the "terrain data" (deltas) under IGHTC are stored completely differently, you wouldn't be able to use IGHTC terrains under the default terrain engine or vice-versa.
#33
I saw your plan here in the resources and found it extremely interesting. I am curious as to how far along it is in relation to your planned design goals.
12/30/2006 (6:38 am)
Hey Darrel,I saw your plan here in the resources and found it extremely interesting. I am curious as to how far along it is in relation to your planned design goals.
#34
My initial design goals were to add a patternManager class to the engine, and from that derive a patternTerrain class, which would contain the getHeight() method to replace the getHeight() in the various terrain* classes suing the IGHTC pattern layer system. My initial design goal was to work on this for one month. This took me all of about a month to do in a very simplistic way (no console interface for the class variables or arrays for example).
Then I discovered the "dagger mountains" problem and found out that the non-primary terrain blocks aren't handled the same way as the primary (0,0) terrain block. That's when I started really digging into the terrain classes... and it was all "downhill" from there :) I started making a list of all the things that I'd need to change to fix this. It was like a stack of dominoes falling. The list kept growing and growing and growing....
At this point a community member with more experience in the terrain classes than I stepped in and volunteered to help and began to resurrect the AreaManager class which did things almost exactly the way we wanted. After a few weeks of work the "dagger mountains" issue was solved and full integration of the AreaManager system with the patternManager system began and we've been working on that every since.
Currently, we are still using "terrain blocks" to present the terrain data to the system, but we've solved the seam issues that were present in the original AreaManager system, and have the data being derived from the IGHTC pattern layer system. This is a huge accomplishment, but our final design goal is to do away with the "block" system altogether - which will greatly simplify things in the end, but will just take a lot of work to accomplish.
01/09/2007 (11:54 am)
Hehe, well considering I started in May, 2006 -- a bit slower than I initially planned. Of course, at the time I didn't think I'd have to re-write the terrain system from the ground up (which is pretty much what we're doing at this point). Looking at it another way, considering it's just me and another community member working on it in our spare time, faster than I could ever ask for :)My initial design goals were to add a patternManager class to the engine, and from that derive a patternTerrain class, which would contain the getHeight() method to replace the getHeight() in the various terrain* classes suing the IGHTC pattern layer system. My initial design goal was to work on this for one month. This took me all of about a month to do in a very simplistic way (no console interface for the class variables or arrays for example).
Then I discovered the "dagger mountains" problem and found out that the non-primary terrain blocks aren't handled the same way as the primary (0,0) terrain block. That's when I started really digging into the terrain classes... and it was all "downhill" from there :) I started making a list of all the things that I'd need to change to fix this. It was like a stack of dominoes falling. The list kept growing and growing and growing....
At this point a community member with more experience in the terrain classes than I stepped in and volunteered to help and began to resurrect the AreaManager class which did things almost exactly the way we wanted. After a few weeks of work the "dagger mountains" issue was solved and full integration of the AreaManager system with the patternManager system began and we've been working on that every since.
Currently, we are still using "terrain blocks" to present the terrain data to the system, but we've solved the seam issues that were present in the original AreaManager system, and have the data being derived from the IGHTC pattern layer system. This is a huge accomplishment, but our final design goal is to do away with the "block" system altogether - which will greatly simplify things in the end, but will just take a lot of work to accomplish.
#35
Great work on getting it this far!!!
Can we see an example of what it looks like now with the block system?
Just using the block system for now would be a great start for some of us :)
01/09/2007 (12:42 pm)
@Darrel Great work on getting it this far!!!
Can we see an example of what it looks like now with the block system?
Just using the block system for now would be a great start for some of us :)
#36
01/09/2007 (3:09 pm)
Currently, we're still working out a few bugs. It's not currently stable enough for a beta release or even a technology preview release.
#37
Essentially, the question goes like this: "Would it be possible to create a heightmap and then reduce it into a set of patterns, and therefore reduce those into a set of seed values?" Another version of this question concerns reducing terrain edits into seeds so that a delta file would be unnecessary (edits would only require changes to the seeds).
Unfortunately, the answer is no. It is so close to statistically impossible to reduce a given heightmap (or a single terrain edit) into a set of pattern layer patterns that is might as well be considered impossible.... To understand why, it may help to understand a little more about how the pattern layer system works.
Each terrain pattern is represented internally as a single 64-bit number (representing an 8x8 matrix). Currently the system uses just 64 such 8x8 patterns. The system takes as input two 32-bit numbers (the X and Y coordinates of the terrain for which you are requesting the height). From these 2 sets of 32 bits, the following are extracted: a pattern selection (6 bits representing a number from 0 to 63), and a pattern coordinate (3 bits for the x coordinate within the chosen pattern (0 to 7) and 3 bits for the y coordinate within the chosen pattern (0 to 7). The result is either a 1 or a 0 indicating whether the terrain is on or off at that coordinate at that layer. If it is on, the layerheight for that layer is added to the final height. The bits are then shifted right and the sequence is repeated until all the input bits are used up. As the input bits increase in significance, the layerheight values increase representing the fact that larger geographic feature cover more terrain.
So, what this means is that for every possible combination of 64 bits (1,844,674,407,370,9551,616 possible combinations), we are only using 64. Therefore, the probability that any given "terrain edit" (which would represented as a pattern change) or input terrain point matching one of the patterns defined in the system is exactly 1 in 288,230,376,151,711,744. So, there's a very slim chance that the change that is made (or an input terrain given) would match an existing pattern and could (therefore) be reprented by an existing pattern.
But that's just for one layer. The system currently uses 28 pattern layers. So, the probability that any given edit would find a match on all 28 layers is something like 1 in 7.4595556511816583890366001320902e+488 (note the e+488).
Now, one solution to this problem would be to greatly increase the size of the base patterns to increase the chance of a match. Taking this to the extreme, you would be left with only 1 available pattern layer, but 1,844,674,407,370,9551,616 base patterns each taking a DOUBLE of memory. So, if your system had 34,359,738,368 GIGS of RAM to store these patterns, and if you were "ok" with having a single layer terrain that looks terrible, you'd have a 100% chance to find a match. Since computers don't have this much memory, let's find what the probablility would be at a more reasonable solution. Let's say you devoted 1 GIG of RAM to your patterns. Doing so would bring your chance up to a "stellar" 1 in 536,870,912 :D
So, the answer unfortunately is no - a single set of seeds cannot be derived from a giving input terrain because the system only uses 64 patterns in 28 layers to build the terrain and the probability that the input terrain could conform to any given pattern combination is so minutely small that you'd never find a single input terrain that could be reduced as such even if you spent your entire life searching.
Paradoxically, the small number of base patterns is actually the system's true strength. Using just this small number of base patterns, the system is able to generate over 18,446,744,073,709,551,616 unique terrains that could theoretically cover an area of 4,294,967,296 x 4,294,967,296 terrain points with no repetition (if you had a rendering system that could render that much terrain all at once).
01/09/2007 (3:39 pm)
I've had enough people ask the "reverse engineer a terrain" question that I thought I'd better post a response before my e-mail responses start sounding like form letters :DEssentially, the question goes like this: "Would it be possible to create a heightmap and then reduce it into a set of patterns, and therefore reduce those into a set of seed values?" Another version of this question concerns reducing terrain edits into seeds so that a delta file would be unnecessary (edits would only require changes to the seeds).
Unfortunately, the answer is no. It is so close to statistically impossible to reduce a given heightmap (or a single terrain edit) into a set of pattern layer patterns that is might as well be considered impossible.... To understand why, it may help to understand a little more about how the pattern layer system works.
Each terrain pattern is represented internally as a single 64-bit number (representing an 8x8 matrix). Currently the system uses just 64 such 8x8 patterns. The system takes as input two 32-bit numbers (the X and Y coordinates of the terrain for which you are requesting the height). From these 2 sets of 32 bits, the following are extracted: a pattern selection (6 bits representing a number from 0 to 63), and a pattern coordinate (3 bits for the x coordinate within the chosen pattern (0 to 7) and 3 bits for the y coordinate within the chosen pattern (0 to 7). The result is either a 1 or a 0 indicating whether the terrain is on or off at that coordinate at that layer. If it is on, the layerheight for that layer is added to the final height. The bits are then shifted right and the sequence is repeated until all the input bits are used up. As the input bits increase in significance, the layerheight values increase representing the fact that larger geographic feature cover more terrain.
So, what this means is that for every possible combination of 64 bits (1,844,674,407,370,9551,616 possible combinations), we are only using 64. Therefore, the probability that any given "terrain edit" (which would represented as a pattern change) or input terrain point matching one of the patterns defined in the system is exactly 1 in 288,230,376,151,711,744. So, there's a very slim chance that the change that is made (or an input terrain given) would match an existing pattern and could (therefore) be reprented by an existing pattern.
But that's just for one layer. The system currently uses 28 pattern layers. So, the probability that any given edit would find a match on all 28 layers is something like 1 in 7.4595556511816583890366001320902e+488 (note the e+488).
Now, one solution to this problem would be to greatly increase the size of the base patterns to increase the chance of a match. Taking this to the extreme, you would be left with only 1 available pattern layer, but 1,844,674,407,370,9551,616 base patterns each taking a DOUBLE of memory. So, if your system had 34,359,738,368 GIGS of RAM to store these patterns, and if you were "ok" with having a single layer terrain that looks terrible, you'd have a 100% chance to find a match. Since computers don't have this much memory, let's find what the probablility would be at a more reasonable solution. Let's say you devoted 1 GIG of RAM to your patterns. Doing so would bring your chance up to a "stellar" 1 in 536,870,912 :D
So, the answer unfortunately is no - a single set of seeds cannot be derived from a giving input terrain because the system only uses 64 patterns in 28 layers to build the terrain and the probability that the input terrain could conform to any given pattern combination is so minutely small that you'd never find a single input terrain that could be reduced as such even if you spent your entire life searching.
Paradoxically, the small number of base patterns is actually the system's true strength. Using just this small number of base patterns, the system is able to generate over 18,446,744,073,709,551,616 unique terrains that could theoretically cover an area of 4,294,967,296 x 4,294,967,296 terrain points with no repetition (if you had a rendering system that could render that much terrain all at once).
#38
Ouch my brain hurts....
A 4,294,967,296 X 4,294,967,296 terrain that is insane!!!
Thanks for the lengthy explanation.
01/10/2007 (10:44 am)
@DarrelOuch my brain hurts....
A 4,294,967,296 X 4,294,967,296 terrain that is insane!!!
Thanks for the lengthy explanation.
#40
1) I'm at the point where I can release code to the community. The AreaManager is stable enough that it reliably loads/edits/save multiple terrain blocks. The PatternManager is 100% stable, but I wasn't able to successfully expose the layerHeight array or the pattern array to the console (hence the large number of class variables).
2) I'm at the point where any further development of this code is simply beyond my coding capabilities. This is, basically, the best that myself (and the community member who has been helping me) have been able to do given the available time to do it.
3) I'm at the point where I cannot develop the code any further given other responsibilities in my life, and available time.
So... this is what I'm going to do:
a) I'm releasing the full AreaManager code _FREE_ to the community. The 2 bugs that we have not been able to resolve are : Collission Detection on the outer edges of the terrain blocks sometimes doesn't work correctly and; Full Dynamic loading of terrain blocks is not yet complete, but the full framework is there.
b) I'm releaseing the full PatternManager code _FREE_ to the community. This is really incredibly simple code when you look into it. Let me apologize in advance for the sore foreheads that many people may get from all the ::palm-slapping-forehead:: that'll happen when people see how easy this was.
When this resource passes through moderation, you should be able to get it here:
IGHTC Code Release STABLE
IGHTC STABLE Sample mission files
...and...
IGHTC Code Release HEAD
IGHTC HEAD Sample mission files
02/10/2007 (1:11 pm)
Alright... I've reached 3 points with IGHTC:1) I'm at the point where I can release code to the community. The AreaManager is stable enough that it reliably loads/edits/save multiple terrain blocks. The PatternManager is 100% stable, but I wasn't able to successfully expose the layerHeight array or the pattern array to the console (hence the large number of class variables).
2) I'm at the point where any further development of this code is simply beyond my coding capabilities. This is, basically, the best that myself (and the community member who has been helping me) have been able to do given the available time to do it.
3) I'm at the point where I cannot develop the code any further given other responsibilities in my life, and available time.
So... this is what I'm going to do:
a) I'm releasing the full AreaManager code _FREE_ to the community. The 2 bugs that we have not been able to resolve are : Collission Detection on the outer edges of the terrain blocks sometimes doesn't work correctly and; Full Dynamic loading of terrain blocks is not yet complete, but the full framework is there.
b) I'm releaseing the full PatternManager code _FREE_ to the community. This is really incredibly simple code when you look into it. Let me apologize in advance for the sore foreheads that many people may get from all the ::palm-slapping-forehead:: that'll happen when people see how easy this was.
When this resource passes through moderation, you should be able to get it here:
IGHTC Code Release STABLE
IGHTC STABLE Sample mission files
...and...
IGHTC Code Release HEAD
IGHTC HEAD Sample mission files
Torque Owner Bill "Black Manatee" Pomidor
And the prospect of TorqueX is just icing on the cake (actually, more than that--it's the *presents* too!). Good luck!