by date
IGHTC (In-Game Huge Terrain Creator) Part 1
IGHTC (In-Game Huge Terrain Creator) Part 1
| Name: | Darrel Cusey | |
|---|---|---|
| Date Posted: | Apr 14, 2006 | |
| Rating: |  4.2 out of 5 | |
| Public: | YES | |
| Comments: | YES | |
| RSS Feed: |  or Subscribe with  . | |
| Profile Page: | View profile page for Darrel Cusey |
Blog post
This blog was titled "Pseudo-Fractal In-Game Procedural Terrain Generation," but Vincent and I decided to change it to the "In-Game Huge Terrain Creator."
Whew! Now that TGE Simplification is done, I'm going to tackle doing a modification to the TGE 1.4 Terrain Engine :-D
I've been looking through terrData.cc and terrRender.cc and it seems to me that at some point along the line, the engine has to go through the steps shown below. I'm ignoring materials, textures, lighting, etc... in this summary because it's not pertinent to this discussion; nor would I have any need to modify functions that deal with these properties (I'm only interested in height data).
Now, I've seen tutorials on the dynamic generation of terrain data files -- but that's not what I'm after here. I'm really looking to calculate height data in-stream.
If what I'm seeing below is NOT what actually happens in the engine, please feel free anyone to correct me:
1. Recognize that the client camera has changed position, rotation, or zoom (either because the player moved or because the camera was manually moved).
2. Figure out if any terrain has come into view that is not currently being rendered. Create a list of all the new x,y points that are now in view but are not currently being rendered (height for those points is currently unknown).
3. For each terrain "point" (for lack of a better term) in the list, figure out which point(s) are missing to complete the new polygon by looking up the value in the Height map data -- this height data is added to the existing x,y data -- we now have all the data we need to draw new polygons.
4. Using the list created, render new polygons and a new "strip" of terrain data is now in view.
What I'd like to explore doing over the next weeks (or months) is to see if there's a way to circumvent Step #3 above and replace the Height map lookup with a deterministic algorithm or (more likely) a set of algorithms.
This is a pretty un-original idea, and I'm sure it's been "done a million time before"... but it's something I've done before using 2D mapping programs with terrain qualities (instead of height) and have gotten really good results. So I'm interested in applying it to TGE.
Using just the X and Y coordinates as input, it is possible to create a set of deterministic algorithms that will generate height data with the following qualities:
a) Deterministic - the same height result is always returned for any value X, Y
b) Unpredictable - patterns cannot be easily detected by the human eye
c) Evolutionary - as the magnitude of the input values change, either the number of passes or complexity of the algorithms applied changes so that you (literally) will never walk across the same terrain twice
Here's some advantages to doing things this way:
1. More or less eliminates the terrain limitations in TGE. I've moved my player out to location [3000000 3000000 320], though, and something in the renderer starts breaking down after around 100000... maybe that has something to do with this:
F32 minSubdivideDistance = 1000000;
... in theory, a system like this should allow for terrain generation for any arbitrary set of input coordinates - and, in theory, an infinite amount of terrain.
2. Since the terrain data is being generated procedurally, there are no restrictions on terrain data files since you don't have terrain data files. This eliminates the burden on the developer to take into consideration the amount of terrain data that can "fit" into the shipping product. This also eliminates the multiplayer restrictions that are evident in procedural generation of terrain data files (since terrain data is not sent over the network in a MP game). You only need to send a "random seed" to all players -- a single 32-bit integer that could be encapsulated in the mission file :-)
3. Arbitrary levels of complexity and tessellation of the height data can be used. You could, for example, apply an additional "layer" of complexity for every 2 orders of magnitude of the input values (x,y). Because there is no need to use cpu-intensive functions (simple algebraic functions will due), each additional layer of complexity adds a minimal amount of additional processing time.
4. LOD is "built-in" -- you simply tell the engine that for every n terrain blocks beyond center block (the one the player is currently on), perform only calculations 1 through (d - n) where d is the total number of calculations you are doing.
5. Each developer defines his/her own terrain for each mission using a unique random seed -- even if everyone was using the same algorithms, the terrains could be vastly different based on this random seed.
Disadvantages:
1. The in-game terrain height map editor (but not the texture editor) becomes useless. Although, you could instead store changes as "deviations" from the auto-calculated terrain. Instead of having a "terrain data" file, you would have a "terrain changes" file - which the engine should be able to store in-memory and apply as-needed once changed terrain comes into view before sending on for rendering.
Hmmm, that's all I can think of for now, but I'll add anything else I can think of in comments...
Whew! Now that TGE Simplification is done, I'm going to tackle doing a modification to the TGE 1.4 Terrain Engine :-D
I've been looking through terrData.cc and terrRender.cc and it seems to me that at some point along the line, the engine has to go through the steps shown below. I'm ignoring materials, textures, lighting, etc... in this summary because it's not pertinent to this discussion; nor would I have any need to modify functions that deal with these properties (I'm only interested in height data).
Now, I've seen tutorials on the dynamic generation of terrain data files -- but that's not what I'm after here. I'm really looking to calculate height data in-stream.
If what I'm seeing below is NOT what actually happens in the engine, please feel free anyone to correct me:
1. Recognize that the client camera has changed position, rotation, or zoom (either because the player moved or because the camera was manually moved).
2. Figure out if any terrain has come into view that is not currently being rendered. Create a list of all the new x,y points that are now in view but are not currently being rendered (height for those points is currently unknown).
3. For each terrain "point" (for lack of a better term) in the list, figure out which point(s) are missing to complete the new polygon by looking up the value in the Height map data -- this height data is added to the existing x,y data -- we now have all the data we need to draw new polygons.
4. Using the list created, render new polygons and a new "strip" of terrain data is now in view.
What I'd like to explore doing over the next weeks (or months) is to see if there's a way to circumvent Step #3 above and replace the Height map lookup with a deterministic algorithm or (more likely) a set of algorithms.
This is a pretty un-original idea, and I'm sure it's been "done a million time before"... but it's something I've done before using 2D mapping programs with terrain qualities (instead of height) and have gotten really good results. So I'm interested in applying it to TGE.
Using just the X and Y coordinates as input, it is possible to create a set of deterministic algorithms that will generate height data with the following qualities:
a) Deterministic - the same height result is always returned for any value X, Y
b) Unpredictable - patterns cannot be easily detected by the human eye
c) Evolutionary - as the magnitude of the input values change, either the number of passes or complexity of the algorithms applied changes so that you (literally) will never walk across the same terrain twice
Here's some advantages to doing things this way:
1. More or less eliminates the terrain limitations in TGE. I've moved my player out to location [3000000 3000000 320], though, and something in the renderer starts breaking down after around 100000... maybe that has something to do with this:
F32 minSubdivideDistance = 1000000;
... in theory, a system like this should allow for terrain generation for any arbitrary set of input coordinates - and, in theory, an infinite amount of terrain.
2. Since the terrain data is being generated procedurally, there are no restrictions on terrain data files since you don't have terrain data files. This eliminates the burden on the developer to take into consideration the amount of terrain data that can "fit" into the shipping product. This also eliminates the multiplayer restrictions that are evident in procedural generation of terrain data files (since terrain data is not sent over the network in a MP game). You only need to send a "random seed" to all players -- a single 32-bit integer that could be encapsulated in the mission file :-)
3. Arbitrary levels of complexity and tessellation of the height data can be used. You could, for example, apply an additional "layer" of complexity for every 2 orders of magnitude of the input values (x,y). Because there is no need to use cpu-intensive functions (simple algebraic functions will due), each additional layer of complexity adds a minimal amount of additional processing time.
4. LOD is "built-in" -- you simply tell the engine that for every n terrain blocks beyond center block (the one the player is currently on), perform only calculations 1 through (d - n) where d is the total number of calculations you are doing.
5. Each developer defines his/her own terrain for each mission using a unique random seed -- even if everyone was using the same algorithms, the terrains could be vastly different based on this random seed.
Disadvantages:
1. The in-game terrain height map editor (but not the texture editor) becomes useless. Although, you could instead store changes as "deviations" from the auto-calculated terrain. Instead of having a "terrain data" file, you would have a "terrain changes" file - which the engine should be able to store in-memory and apply as-needed once changed terrain comes into view before sending on for rendering.
Hmmm, that's all I can think of for now, but I'll add anything else I can think of in comments...
Recent Blog Posts
| List: | 05/25/06 - IGHTC (In-Game Huge Terrain Creator) Part 2 04/14/06 - IGHTC (In-Game Huge Terrain Creator) Part 1 03/08/06 - Engine Simplification - TGEB |
|---|
Submit your own resources!| Johnny Hill (Apr 14, 2006 at 02:26 GMT) |
| Darrel Cusey (Apr 14, 2006 at 03:28 GMT) Resource Rating: 5 |
| Vincent BILLET (Apr 14, 2006 at 09:06 GMT) Resource Rating: 5 |
Quote:
a) Deterministic - the same height result is always returned for any value X, Y
b) Unpredictable - patterns cannot be easily detected by the human eye
c) Evolutionary - as the magnitude of the input values change, either the number of passes or complexity of the algorithms applied changes so that you (literally) will never walk across the same terrain twice
Did you have a look to HTC? I was thinking about porting it to TGE. Do you need help to do this plan ?
| Geom (Apr 14, 2006 at 16:59 GMT) |
sounds neat and ambitious, but how would this affect operations like raycasting?
| Darrel Cusey (Apr 14, 2006 at 19:21 GMT) Resource Rating: 5 |
HTC is really incredible, and 2,749 square kilometers certainly qualifies as a huge area. I think if I was only looking for a way to create huge areas, I would use HTC. However, my real interest in doing this is to add more procedural, in-game generation capabilities into TGE. To me, the introduction of the fxShape- and fxFoliageGenerator are a sign that GG see the value of these techniques and (hopefully) we'll seem more of these sorts of things in TSE.
If I am understanding things correctly, HTC is a terrain editor and generator -- but in the end, I believe you still need a terrain file that needs to get loaded by the engine _before_ the mission starts when using HTC.
The technique I am trying to develop would generate the heightmap "on the fly" while the game is running as the player moves around the world. I have only read this page and this one concerning HTC, so maybe I am not correctly understanding what HTC does. If I am not correctly understanding what HTC does, let me know.
Vincent, if you'd like to assist me with this, I'd be... well (I know it's cliche'd) honored :-) Right now, I'm trying to find the location in terrData.cc and terrRender.cc where the heightMap structure is read (streamed?) to render terrain that is more than 1 terrain tile away from the player's current location. I have been able to follow the path of exection in these files pretty well, but it just seems like (somehow) this step is skipped and I cannot find the code that does it. Maybe I'm missing something. If you want to e-mail me, we can discuss this some more. Maybe I'm looking for the wrong thing -- that's a definite possibility :-)
@Geom
It's definitely ambitious, but to mediate the scope of this change, I'm using an approach that should have zero impact on any other systems. Basically, my approach is to simply replace the portion of code that populates the tiled terrain heightmaps using the "heightmap" structure with a series of algorithms to generate those heightmap values procedurally. So, instead of copying values over and over again for each terrain tile rep, new ones are generated on-the-fly. Everything else will still be left in-place, and as-is.
If raycasts are done in TGE against the original heightmap data (instead of the instantiated terrain tiles), yeah, then there's a problem :-) If TGE instead does the test against the instantiated terrain data, then no worries. I guess we'll see when we get there. But, I appreciate the heads up - that's getting added to my testing list :-)
| Vincent BILLET (Apr 14, 2006 at 21:25 GMT) Resource Rating: 5 |
Quote:
I would use HTC. However, my real interest in doing this is to add more procedural, in-game generation capabilities into TGE.
In fact, what's Atlas???
Atlas is a good way to generate terrain. It allow you to build a messh with fast rendering capability. It allow you to build Huge meshes available for rending very fast.
And HTC what's this?
It allow to have a deterministic approach of the global terrain. Merging global "terrain types" and yet vegetation kind for more realistic render. In resume, it's ONLY procedural...
Quote:
If I am understanding things correctly, HTC is a terrain editor and generator
No ! (sorry, It's no :( ) That's my fault.... HTC is ONLY a terrain GENERATOR. It's not an editor (even if I try to put some editor functionnalities).
.
Quote:
The technique I am trying to develop would generate the heightmap "on the fly" while the game is running as the player moves around the world.
That's THE quote ! Why developping a "On the fly" World generator? Because it's usefull !!! I'm working on 128x128 tile generation for HTC ! isn'it reavealent? If not so... Why?
We have similar project. And before considering who would help who... I prefer ask the question "In what direction are we going on ?" (sorrry for my poor english, I'm a frenchy guy....:) ) I Have a small Idea (due to experience) where small terrains can make HUGE terrains...
Quote:
so maybe I am not correctly understanding what HTC does. If I am not correctly understanding what HTC does, let me know.
HTC is a HexMap tile Editor allowing users to generate terrains of a great variety. It allow to have predictable results on wide range. It allow to blend variety of terrain (Hills, Mountains, swamps, etc...). It allow you to builld vegtation and minerals on it (even exceptionnal ressources to gather... :) )
Quote:
I cannot find the code that does it
For sure ! It's for sale! ;) (www.solu-si.com/dragonhead/index.php?c=en&a=products)
Quote:
Maybe I'm missing something. If you want to e-mail me, we can discuss this some more. Maybe I'm looking for the wrong thing -- that's a definite possibility :-)
Sorry, (I'm a frenchy guy:) ) I don't understand this sentance...:( (really sorry, I think there is something really strong behing that, But I don't understand what!!! could you explain?).
Final Words
I think we could work together (We have the same interest : Great Terrains). And I hope it's for nearly future and for a great anthousiasm for TGE and TSE owners...
EDIT : Some spelling issues (Sorry, I'm a frenchy guy)
Edited on Apr 14, 2006 21:35 GMT
| Vincent BILLET (Apr 14, 2006 at 22:12 GMT) Resource Rating: 5 |
Quote:
my approach is to simply replace the portion of code that populates the tiled terrain heightmaps using the "heightmap" structure with a series of algorithms to generate those heightmap values procedurally
Ooopppssss... I missed this this quote. :) It's nearly done ! contact me for further informations... :)
Edit : We realy have to work together. :)
Edited on Apr 14, 2006 22:13 GMT
| Darrel Cusey (Apr 15, 2006 at 15:15 GMT) Resource Rating: 5 |
I apologize for often "hiding" important distinctions in small sentences in the middle of very large blogs. After many many years of programming, my writing and thinking tends to work like a series of nested loops -- I must have been about 12 loops deep when I wrote that blog :-)
I think these are the primary differences between HTC and the technique I'm proposing -- let me know if you see this difference also:
HTC:
1. Generates a very large (and very good) terrain file.
2. Generates the terrain before the mission starts.
Cusey Technique:
1. Does not use a terrain file.
2. Generates the terrain while the mission is running as the player moves around.
I'm just posting this to make sure we are both understanding each other. I think we are, but I wanted to make sure to help overcome the language difference.
Yes, I do think we can work together on this -- and we should be able to develop something that can be used for both TGE and TSE (even though they handle terrain in vastly different ways).
I'm composing an e-mail right now with more information that I'll send to you.
Edited on Apr 15, 2006 15:16 GMT
| Vincent BILLET (Apr 15, 2006 at 17:38 GMT) Resource Rating: 5 |
Quote:
Cusey Technique:
1. Does not use a terrain file.
2. Generates the terrain while the mission is running as the player moves around.
Excellent ! That was my initial goal (far away in past). But I encounter some very huge lag when generating meshes in real time. Oh, of course for simple terrains it's easy, but for more realistic terrains, I always encounter "lag effect"... I turned the problem by many and many manners but I had always a lag in some precise points. So If you have ideas on this point, I can tell you OK, I have not tried this, or No it don't work. this may save time for you, and/or allow us to make a very powerfull terrain system.
In my opinion the best terrain take a space of 10-30 KB for fractal parameters, No more. But computation time is very important (because there is a very large amount of point in a terrain). So to find a middle technique, it's really not easy.
You know I work on terrain generation since december 2004. It sometimes drive me fool, and sometimes give me some really good results.
Quote:
Yes, I do think we can work together on this -- and we should be able to develop something that can be used for both TGE and TSE (even though they handle terrain in vastly different ways).
Do you own TSE? If yes, I think the first thing to do is to port Atlas on TGE. If you are not TSE owner, you can try to make a mesh directly from a "grayed heightfield bitmap", and see the time it take to build / render. If your results are fast enough, so you can add computation time for terrain generation.
Atlas is based on Ulrich Thatcher ChunkLOD algorithm. (I think it's the best Algorithm for real time rendering at the momment). HTC is based on Ken Perlin Noise algorithm. This algorithm give the more various results. I tested ten (more) algorithms for terrain generation. And Ken Perlin solid noise is, in my opinion, the best.
| Darrel Cusey (Apr 15, 2006 at 19:50 GMT) Resource Rating: 5 |
| Erik Madison (Apr 15, 2006 at 21:23 GMT) |
| Johnny Hill (Apr 16, 2006 at 00:57 GMT) |
Ben Garney pretty much said if that happens then whoever would use it would need to have the TGE as well as the TSE license in order to use such a marvelous combination. Simply because it conflicts with what TSE has that is a big part of its selling point. Massive terrain capabilities, for a starting point for whatever MMORPG/MMO or SMORPG you can think up. Its just business, nothing wrong with that.
But a system like Darrel describe one that is completely coded from scratch and not completely dependent on code from the TSE atlas system, but performs similiar is ok. Terrain Manager is a prefect example. it allow multiple terrain blocks built for the TGE codebase, but not enough coders to help it out killed it. But if Darrel and Vincent pull this off. :)) Iam not a coder, but Iam excited just thinking of the possiblities of a seamless TGE world to play with. Right now budget dont allow me to get TSE so Iam happy to work with what a I got too.
| Darrel Cusey (Apr 29, 2006 at 17:05 GMT) Resource Rating: 5 |
I've got a prototype up and running of what Vincent and I are calling the "In-Game Huge Terrain Creator" (IGHTC). Right now I'm using a very simple custom-made rendering engine to render the terrain data. I'm doing it this way instead of coding directly into TGE because build times are much much faster this way, and it allows me to focus 100% on the algorithms instead of the quirks and sometimes-strangeness of TGE/TSE.
Once I have the solution generating terrain the way I want it to, I'll post a screenshot here (using the test-harness renderer) and then start the task of "back-porting" it into TGE.
Here's some interesting tidbits about the IGHTC as it stands today (any and all are subject to change of course):
- Terrain can be generated procedurally "on-the-fly" while the game is running. I'm currently getting 500+ fps in my test harness (including terrain smoothing, texturing and lighting with shadows with a 50,000 meter view distance) -- so, it should be plenty fast still once it gets put back into TGE/TSE.
- Terrain generation is done by using real-world patterns. This is done _instead_ of using fractals, perlin noise, or the other similiar functions. This is done in order to create terrain that is _more_ realistic than what those formulas can create (and it's much much faster).
- Level of Detail is done automagically by the IGHTC. I haven't (yet) got the triangle count to remain 100% constant regardless of view distance -- but I'm getting very close.
- To give you an idea of the sheer volume of terrain the IGHTC can generate, imagine having a heightmap with a size of over 4 billion height and width (without actually needing a heightmap). I did a quick calculation and figured out that it would take a player moving at 1m/sec over 13 years (real time) of continuous play to go from the center of the terrain to any edge. Now, I'm using unsigned integers for my input values and TGE and TSE use float values, so this is likely to change -- but I wanted to give people an idea of the terrain sizes I'm targetting.
- The system currently uses 5 "terrain layers" (not to be confused with TGE's texture layers), but I should be able to get that up to over 20 "terrain layers". This is goodness because each layer makes the terrain more "rich" and more realistic.
My goal right now is to get all the layers working and then generate some terrain while standing at location 2 billion, 2 billion (just to show it can be done), and getting a screenshot up. After that, I'll try to see if I can't record a movie of the terrain being generated in real-time as I fly over it at 200 m/sec :-)
... so, that's all for now... more to come soon.
| Darrel Cusey (Apr 29, 2006 at 17:16 GMT) Resource Rating: 5 |
For those of you wondering about the whole Atlas issue with TGE. The system I'm coding I'm building 100% from scratch -- it's a fundamentally different approach (there is no terrain file) -- so, I don't see any reason why you'd need a TSE license to use it with TGE.
Hehee, everytime I tell people "there is no terrain file" I'm reminded of that scene in The Matrix where the little boy tells Neo, "there is no spoon." Or better yet, "These are not the terrain files you are looking for. You can go about your business. Move along." OK, I better stop now :-D
| Dave (May 02, 2006 at 08:10 GMT) |
What would happen with placing content in the world with this system? Is exactly the same terrain generated every time the game is run, so that you could position content at the right height and in the right place?
If the same content is generated every time with the same seed, will many people have the same terrain in their games? That is, will it not be unique or "hand crafted"? Will there be an editor to hand mod the terrain and to place content? I assume not as there is no terrain in existence except during run time. But then, how will this work?
Sorry, I'm just not sure how this will integrate with the dev pipeline. Appreciate a quick lesson :-)
Vincent - Don't get distracted from HTC+ please :-)
Thanks,
Dave.
Edited on May 02, 2006 09:02 GMT
| Darrel Cusey (May 02, 2006 at 12:55 GMT) Resource Rating: 5 |
Let me answer you questions 1 at a time:
(1) This is a procedural terrain generation technique, so, yes the terrain will be the same everytime the game is run. Think of it like generating the value of PI -- you get the same string of numbers everytime you do it.
(2) I've done some preliminary tests with a very simplified version of this system and these are the results so far:
-The AI (Kork) recongnizes the terrain and runs across it normally.
-You can place objects on the terrain just like you could with heightmap-generated terrain and save off a mission file recording the location of all those object just like you normally would.
- The advanced camera (Thomas') will not go under this terrain when you swing the camera really far down -- which tells me that ray and collision tests work just fine with it.
- Projectiles fired at the terrain explode when they hit the terrain just like they normally would
- In multiplayer mode, everyone sees the same terrain, just like you'd expect.
- In the racing demo, the car physics interact with the terrain just like you'd expect...
... so far tests are going really well.
(3) There's actually 2 parts to generation (so far) that can be used to modify and customize the terrain generation procedure. First, there's the random seed which I plan to store in the mission file, so you'll get the same base for your terrain every mission. Second, the terrain is based on "terrain patterns" applied in layers procedurally. Vincent has asked me to create a simple GUI in Torque that would allow for the editing of these terrain patterns -- so that's another way that you'd be able to customize the terrain to your liking. I've got a couple of other ideas for values that I could "surface" to the GUI to allow you to customize the algorithms further, but that'll be after I get everything compiled back into TGE.
Hope that answers your questions :-)
| Dave (May 02, 2006 at 19:15 GMT) |
OK, you now have another annoying fool added to the chain waiting to try this out!
Dave.
| Johnny Hill (May 11, 2006 at 18:20 GMT) |
| Darrel Cusey (May 11, 2006 at 22:16 GMT) Resource Rating: 5 |
In the Torque Game Engine, there is a value called "Terrain SquareSize" -- I have this currently working correctly with the IGHTC, and can set it to any value from 1 to 4294967295. Sixty-four, though, is probably the largest value anyone would ever want to use for this or else you severely limit the maximum slope that can be achieved. Terrain Squaresize effectively "multiplies" the amount of terrain that can be produced by the IGHTC. Right now I have this set to "8", so the amount of texels the system can produce right now is 34359738360 x 34359738360.
If I said that each texel was 1 inch (but this is arbitrary), then this would be 2863311530 feet = 872694766 meters = 872,694 km. So, just using Terrain SquareSize of 8, IGHTC can produce over 872,000 km width and depth of unique terrain... just for a comparison, the average circumference of the Earth is 6,374 km. So, you could effectively make a planet that was 136 times larger than the Earth, if you wanted to that is :-)
If a player was running at 1 m/sec, and was playing the game continuously for 24 hours a day and 7 days a week, it would take her a minimum of 13 YEARS (!!!) to get from the center of the terrain map to any edge -- all with no repeating patterns :-)
I currently have a Development Snapshot pending approval. Once it is approved, you'll be able to see it here:
IGHTC Development Snapshot
| Johnny Hill (May 15, 2006 at 02:47 GMT) |
You must be a member and be logged in to either append comments or rate this resource.
