In the past I had succeeded creating complex buildings out of L-Systems. While it was fast, it was for a different approach to world generation. It was for static game worlds like Skyrim's. I had the luxury of time.
In a world that generates as the viewer moves, most of the time I had for generation was already taken by the terrain and trees.
Architecture is something you cannot just instance. You want buildings to be different, even if they belong to the same class. I needed the actual grammar programs to run in real time, its polygonal output voxelized and then merged with the rest of the voxel data.
You may think going from polygons to voxels then back to polygons is an awful waste of time. It had been, except for the fact I needed changes made Minecraft-style to also work over buildings. When you are wielding that pickaxe you don't really care if that rock in front is a natural formation or a cathedral wall.
At the end I did manage to make it work. As usual most of the solution went into creating indices to accelerate the actual work.
I had to make compromises. For starters, the voxel resolution in the realtime engine is much coarser than what I had for the pre-computed worlds. This meant a lot of the detail in buildings had to go. This also applied to the following levels of detail. Detail had to be removed in all levels.
I also saw I needed simpler grammars just so the system could keep up in lower-end hardware. I found it common to have thousands of different buildings in a single scene. The solution I found was to pass the LOD parameter to the building grammar at evaluation time. It made it possible, but now the building programmer has to worry about creating different views for the same building.
I am still very happy with the results of something I feared almost impossible. There is room for improvement, and this is a good thing. The hard part is over.
I leave you with some screenshots of a single tower grammar that appears scattered everywhere. Please do not mind the lack of actual cities, or the fact it is the same tower over and over again. This is rather a test for the system. I will be posting some videos later.
Quite a tower you have there, would be bad if something *happened* to it...
ReplyDeleteJust kidding, that is awesome! That tower looks like it could come straight from a game =3.
Really cool stuff!
ReplyDeleteThough I generally get concerned when the word 'compromises' starts being thrown around - Understand you want to make this as real-time as possible. But I hope you'll leave it open and tweakable enough to bring back higher resolution options.
Personally I'd rather the 'server' spend 5 minutes prefetching existing world around the player start and storing the result. So when you travel the server is far enough ahead of the player that it doesn't have to procedurally create chunks in real-time.
How do you define "ahead" of the player?
DeleteWell, the most simple way is just to have a secondary and longer 'culling' region. So. For example lets assume you're generating and displaying map chunks 1x1x1 around the chunk the player is in.
DeleteWhilst the player is in the current chunk the server threads doing the generating are idle correct? So why not let them to continue to generate the chunks 2x2x2 or 3x3x3 out from the player. Just don't send them to the client and display them.
So that way the server, under most conditions, will have enough chunks ready to serve to be able to always spend some extra time generating higher quality chunks that take more than real-time.
The only time this should really fail is if there are gameplay elements that allow the player to teleport to areas of the world where nothing has been generated. But that is an edge-case that can be easily concealed using tricks (Teleport takes time to cast).
This is why I asked. To me a solution will be as good as how it performs on the worst case scenario. For an on-the-fly world, this is when the viewer keeps moving at maximum speed. When this happens you must assume the system (no matter server or client) will be utilized at 100%. There is no idle time.
DeleteYou can look at it this way. Even if you had great prediction and pre-computed a lot of chucks, very soon this cache of chunks will go empty as the viewer keeps moving. Then you are working at what the generation throughput is, pretty much like in the client-side scenario. The difference if you could have more CPUs assigned to a single viewer, but it would be very costly.
You may consider pooling CPU resources for all users in a server, so predicted chunks for a player on the move can be computed by the resources an idle viewer has released. This is a good idea, but should not be the base of your system. It means that by design you are allowing the system to slow down once enough viewers are on the move.
For real time generation the only real option I see is to increase the throughput of the algorithms so more content can be generated at the same viewer speed. Whether this is server or client side it does not matter much.
Prediction, caching and pooling can make a good solution a lot better. But they cannot make a good solution on their own.
I love this stuff so much I don't have words.
ReplyDeleteI want to climb it!
ReplyDeletePretending for a minute that you had an animated character running around the world, it seems like it would be fairly simple at this point to also start generating gameplay markers/points of interest too? Specifically at this point I'm thinking of the Assassin's Creed style tech of hand/foot-hold points, that are used to animate and IK the body as the character climbs up a surface.
I'd love to get my hands on some of your tech, it's amazing!! :)
Needs a big curved wall from tower to tower.
ReplyDeleteI've been wondering about cities. In a previous post you described iterating though a history simulation, to create countries and roads, etc: I'm guessing that doesn't happen any more?
ReplyDeleteIt does not happen in the realtime version of the engine. I am adapting those algorithms to realtime as well. I have not given up on cities. Although they will have to be simpler.
DeletePerhaps cities could be generated when the player gets aproperately close, but stiil out of visual range?
ReplyDeleteYes correct, also note the horizon is very far away. Something out of visual range would be more than 10 kilometers away.
DeleteNice job,
ReplyDeleteDo you plan to let users create new objects using the grammer?
Maybe not in the first game I do. However this same architecture system can be used by a game to generate new objects like weapons, jewels, etc. They are not very different than buildings if you write different grammars for each type of object.
DeleteStunning... truly. It is great to see architecture and interiors again. Integrating architecture into the new realtime engine was a huge jump, congrats! I know we've all discussed how caves could be improved... but don't both fiddling with them they already add a lot to the engine, and you can always tweak their algorithm later :)
ReplyDeleteI like how this version of VoxelFarm Realtime is deterministic, from a seed, and local, especially since you didn't have to trash the non-realtime engine work.
I have a similar question as others. Do you still envision being able to work in a deterministic form of your region/city/block/building generation?
I ask because I think that feature has always been a major standout of your work -- If you can combine that with everything you've shown in the realtime engine, it will launch your engine into the stratosphere, above all other sandbox games to date.
The ability to walk and interact/modify these worlds, with the natural grandeur you've created, filled with buildings, cities and roads addresses a huge hole in the procedural generated game universe.
My remaining personal wishlist items for your project (you've already done so much):
- Cities/Blocks/Roads/Buildings (even if more simplified in their algorithm than what you previously did. I think you will be able to find a way even in Realtime).
- Inhabitants (Basic, think GTA procedural instanced people and animals, based upon surroundings/rules. Not sure if your simulation background had you doing much of this, but I think you'd do this great, or could get help)
- Water... Some form of deterministic placement of static water bodies, I know there are many problems with procedural water paths. To start I think even a simple rule like "height -64 meters and below" is water.
Water is coming next. As you said generation of river and lakes in full terrain is tricky. Also imagine someone connects a river with an underlying cave by digging a hole. The cave has to flood. This is serious stuff again.
DeleteThat you are even contemplating water soon just made my 2012 :)
DeleteYeah, that's what I thought regarding dynamic water being difficult. Perhaps behind the scenes threads could prefetch unrendered data and make a locally stored water map based upon rules, like below, but would be driven by the seed's geometry for chunks you've come close to.
I know I'd be willing to live with quite lot of "un-realism" here. I.e. even if dynamic water only appears from "seed generated water spring" entities (to which you can weight to generate more or less by certain climates and topologies).
Dynamic water could then be limited to not flow far laterally, just a bunch of falling spray and effects when it hits a surface. Whenever falling water intersects geometry, test generating a local "pool" instance that only spawns/spreads to the extent there is enough fully concave geometry adjacent to it without spill over. Otherwise, it spawns a few local flowing water trickles that flows on geometry only a very short distance (15 in game meters?) and then appears to dry out, and never spawns more dynamic water springs.
Unrealistic yes, but then it can't flood the world, and we still get high waterfall filled mountain vistas :)
Anyway, I can't wait to see what you are able to work out, just don't forget about lakes and procedurally generated underwater flora on geometry where they appear :)
Excellent work as always!
Jonathan
I also think dynamic water would be a fantastic addition... being more art orientated and not so much of a programmer, I don't know if it would be too far fetched to consider a two-stage system for water - stage one would be to specify a finite rainfall volume (water per second if you like) over a biome. Each square would distribute its own water to neighboring squares depending on height geometry, and heavy rainfall would affect further away squares. After summing the water flow value for each square, a particular minimum value would have to be achieved for a stream to form. Once a stream has formed, we move onto stage 2 of water generation, and flow a minimum-depth stream in the direction of maximum negative incline. Each square could acquire a 'water flow in' and as long as the incline remains negative, the stream regenerates from that point. Where streams meet the stream depth would be increased until pooling. Or is this way out of the reach of realtime processing?
Deletefound some interesting work by Christian Lindequist Larsen on water simulation / hydraulic erosion over on ogre: http://www.ogre3d.org/forums/viewtopic.php?t=9383
Deletescroll about halfway down the comments, there's the binaries for a viewer you can download and try 'filling' the terrain with rain and watching it evaporate.
This might interest you:
ReplyDeletehttp://www.youtube.com/watch?v=CpHi0SORqAo&feature=player_detailpage
In this system we develop Shape Grammars using tessellation shaders to reach on-the-fly generation of buildings.
It is vey interesting. Do you guys have a paper?
DeleteThis technique cannot be applied in my case however. You guys do not need a voxelization stage, I guess you can instance the architecture.
In my case 99% of the time is spent voxelizing and then back countouring into polygons. Voxelization is expensive because I need to discover sharp features in the original mesh. Countouring takes time for the same reason, these sharp features have to be reconstructed.
All this trouble so we can have buildings you can break apart, or expand as you like.
Your tech looks impressive anyway. Do you have context sensitive rules in your grammars like occlusion tests and plane snaps?
Hi Miguel,
ReplyDeleteYou will find our publications there http://jmarvie.free.fr/
In the video I sent, there is no building instances, each building is unique according to a set of input rules. Each generated model is made of several levels of details and impostors that are generated by the grammar in the GPU. You will find a detailed description of the system in the related paper.
http://jmarvie.free.fr/Publis/2012_PG/gpuShapeGrammars.pdf
You can also have a look at an older publication, where we did the same thing but ray-tracing the grammars instead of using tesselation. Results were quite efficient also. Indeed we still use it for far buildings rendering in the most recent paper.
http://jmarvie.free.fr/Publis/2011_GI/renderTimeProceduralPerPixelGeometryGeneration.pdf
Regarding context sensitive rules we do not support snaps nor occlusion in a strict way (say it is not part of the language). However, we can send many kind of parameters to the grammar so we can use those for context sensitive developments. Anyway, we found that most of time, a carefull grammar construction is generally enough to get proper snapping and prevent most occlusions. I would say that context sensitive rules become quite usefull for growing trees near buildings without getting intersections.
Please, continue posting on the evolutions of the system, I really enjoy reading this blog, the techno is impressive (I would enjoy more technical details). I will pay strong attention to the voxel farm engine when you'll get it out.
Jean-Eudes
I would have cached a few dozen buildings, and tried to keep that cache filled up with new buildings with a background thread. If it ever runs out, just show a loading screen to the guy who ran too far too fast. And in five years time, CPUs are fast enough anyway.
ReplyDeleteMiguel, with regard to water and pouring rivers into caves, if I have my hydrogeology straight, a cave below the level of a river would almost always already be filled with water, since rivers are commonly at the level of the water table (the surface between the fully water-saturated ground and the partially saturated ground above it). I don't know if that makes the problem any easier, but it seems worth mentioning. I guess if players can place water sources you can't depend on anything.
ReplyDeleteHey Miguel,
ReplyDeleteI want to compliment you for the work you are doing. Its very interesting to read up your articles and posts every time.
At the moment, I try to use procedural generation of buildings for the game Terasology.
https://github.com/MovingBlocks/Terasology
Would you mind giving me some tips on how you simplified your grammar to make it feasible for Minecraft-like games?
Thanks in advance and best regards,
-- Skaldarnar
I did not change the grammar system. I just wrote new buildings knowing they would be used for the realtime engine. I made sure there were few occlusion and snap rules, also took care of instanced features never getting smaller than the voxel resolution.
DeleteIf you want to see a full reference of the grammar system you can check out this wiki:
http://voxelfarm.com/w/index.php/Architecture_System
This particular article covers how LOD and terrain integration is performed:
http://voxelfarm.com/w/index.php/Using_VoxelFarm.Realtime_program_arguments
I have plans to release Voxel Studio soon. For now there is no way for you to test the content of the Wiki.
Thank you so far, I'll have a look at these articles.
DeleteWhat is the name given to the game?
ReplyDeleteNo name for now...
DeleteI understand...
DeleteTell me, how to communicate with the developer, pleaze
You can use this contact form:
ReplyDeletehttp://voxelfarm.com/vfweb/contactus.php
Thanks!
DeleteI have another question: are you the admin?
Miguel your work is inspiring! I'm trying to use L-Systems myself to generate a Road system, as well as for simplified "skyscraper"-style architecture. You mentioned you had used this method in the past. Do you have any open-sourced stuff I can take a look at? Or do you have a reference for the grammars you used?
ReplyDeleteI saw the links you posted to the wiki in an earlier comment, but the site seems to be down.
http://voxelfarm.com/w/index.php/Architecture_System
http://voxelfarm.com/w/index.php/Using_VoxelFarm.Realtime_program_arguments
Thanks, and keep up the amazing work!
There is a full reference in the Wiki, which does go down often:
Deletehttp://voxelfarm.com/w/index.php/Statements
I do not use or have any open source tools. But the research is all public and not difficult to implement.