69 – Creation mode

Snapshot 1 went over pretty smoothly. Still I greatly overestimated its stability on random machines so crashes were a lot more frequent than I expected. Not a stellar start but what do you expect from the first version obtained from merging two tech demo candidates over the weekend and stripping out all unnecessary stuff in a hurry. I already fixed some of the bigger offenders and snapshot 2 should be uncrashable on machines with correct specs. Famous last words? Probably! Anyway, to slightly make up for it snapshot 2 will feature a more reasonable item density making it run on a wider area of PCs. But stress test season is not over yet, so still no LOD switching. The GPU needs to feel the sweat! Work it! and stay tuned for some troubleshooting guide at the end of the post.

So what now? To reiterate, my goals is to make the 3D as feature rich as the 2D has been in record time, while still providing a snapshot progression that makes some sense. That tells a story. I figured the best way for that is to implement creation mode, like in Minecraft.

In creation mode you are given free reigns to build without pesky concerns like time, resources or the welfare of you dwarves. Even better, I should be able to pump out a working creation mode in a short period of time. On top of the creation mode then I can layer the rest of the features one by one and have a workflow that allows me to develop and test features in isolation.

Creation mode will have multiple stages. Stage one will allow the creation or destruction of any item in a map with infinite resources. Stage two will allow for the inspection and changing of all properties for objects. And stage three will allow natural interaction with the world: no longer will you place and destroy items, you can do stuff like harvest plants, use workshops and nature will run its course.

Further stages are possible but this is as far as I am planning right now. So basically LEGO without LEGO blocks. Don't sue me owners of the LEGO brand!

The first thing that creation mode needs is a way to select and destroy objects. Selection works as normally and you use the key "x" to issue a delete command.

The next step is going to be to allow the manual placement of objects on the map. More on that the next time.

While developing this I spent 95% of the time fiddling with the mouse selection. While preparing snapshot 1 I realized that the selection mechanism is not prepared to deal with the pure strain of the stress test and would crash, so I disabled item selection. Meanwhile I fixed it, but it was far too slow with so many objects. After a quick mouse gesture it would take a second or two for it to update. So I went about optimizing the hell out of it:

• I greatly optimized item population algorithm. It is at least an order of magnitude faster. This will have a global positive effect influencing everything, including LOD switching and simulation. The bad part is that a new cache was introduced. I can't cache the entire map because it would take too long and eat up far too much memory so I limited the cache tot he current level. Anyway, you can't select things from a different level with the mouse so this is a non-issue.
• Mouse update is a lot smarter and able to determine the section borders so it only updates as much as it needs. This also means that performance is directly proportional with the size of the area you select. So don't zoom out really really far and select the whole map and expect it to be instant, but it should still work.
• Mouse update is now able to determine if your screen relative mouse movement coincides with a coordinate change in the 3D environment, and if not it does nothing.
• Even with these changes mouse cursor movement was not perfectly smooth. So I implemented shallow update that is only used by the mouse system and does the minimal amount of work necessary to highlight an area.

As can be seen in the video, the contrast of the selected area is not great. I have some plans to improve this but this is not a task of urgency.

There are still tons to talk about, but I'll skip that for troubleshooting. Because of the snapshot system, I won't give troubleshooting advice for older snapshots, only things that are relevant for the next snapshot. So once snapshot N comes out, snapshot N - 1 ceases to be relevant:

• Performance is poor and/or visual artifacts, black boxes and other strange things are visible: if you are running on DirectX try OpenGL. And vice-versa. Also make sure your drivers and DirectX is up to date.
• Engine is unstable or sometimes it runs fine, other times it crashes on launch: stress tests are meant to really push the boundaries and up the system requirements. The engine is very sensitive and has a lot of RAM needs, both system and video. Since maps are random it can be that one time it generates a map that it is fine, one time it generates a map that ends up needing more resources than you have and it crashes. Scrolling and zooming can also have this effect. If the current map needs more resources that you have but you have scrolled to a less busy area of the map, once you scroll/zoom again new chunks of memory can be pulled in and it can crash. This will be less of an issue once system requirements are more precisely determined, stress tests are done and general system stability increases.
• Black screen on start up: either bullet point 1 or point 2, probably both.
• Some keys like "s" or "d" make the game stop working/screen go blank/do some other weird stuff: the GUI has not been removed, it is only superficially hidden. You actually opened up the inventory browser/dwarf browser/other dialogs but they are not visible. I won't fix this because I want those dialogs back ASAP. As a quick fix for snapshot 2 I disabled keyboard message forwarding to prevent these dialogs from opening (I probably disabled some useful shortcuts by this that you don't know about).
• Some areas of the screen (near the edges) don't react to mouse movement. As said, the GUI is only superficially and temporarily hidden. There is a window/panel at that given position that eats up you mouse events.

68 – Snapshots

Happy New Year! I already said it on Twitter but not everybody is on Twitter. So Happy New Year!

December sure was a month to my liking. I like to have my Decembers free. In 2010 I did not post too much on the blog. In 2011 I did not post at all, but at least this time you had a warning. Anyway, December was great and lazy. It is actually hard to get used again to working!

But I had time to do some thinking and plot a future for this project. Developing the 3D engine took a lot of time and it kind of became an endeavor in which I try to learn and incorporate as many 3D technologies I can without regards to the needs of the game. It also became a race to see how many fricking objects I can fit into a scene. Right now I have a relatively small portion of the code that is the 3D engine and a huge chunk of it that does nothing right now. Pathfinding, scheduling, plant growing, item management and all other things the 2D engine could do are basically dead code right now. It still works, but the 3D engine is not using these features. Time to fix that!

So I have two goals for the immediate future. The first one is to make the 3D engine capable of doing every single thing the 2D one could (that I posted about). This is a pragmatic and achievable goal. The second is to provide proof of concept that the formula of the genre could potentially transcend the limits of ASCII "graphics" and be feasible in a 3D environment. This goal is more symbolical than anything. I'll try my approach and reach a certain conclusion, but I'll leave others to be the judge.

So how are we going to achieve goal number one? Back to basics, that's how! The idea of larger tech demo and versions that have a lot of features and are perfect is dead. I'll do small incremental updates. I'll cut back all the GUI and fancy 3D engine stuff and create a fixed top down camera starting point. Extremely minimalistic.  After a few weeks I'll add back the isometric camera. And so on. But here comes the good part: incremental updates. Starting from this first version I'll keep reenabling and testing features, making sure I never break anything intentionally. And I'll try to achieve weekly updates. Even if an update only consists of some bugfixes or other minor stuff, if it brings me closer to my goal it is worthwhile to include in the weekly update.

And all updates will be public. Once a week I'll package a snapshot of my version (unless I break something and am unable to fix it in time) and upload it somewhere. As said, the first version is very minimalistic, so it won't feature the editor and launcher. There won't be a main menu. You'll boot it up and if it works you'll basically have a 3D visualizer. Also, because this is the first version and the first tech demo was supposed to be a stress test, snapshot 1 will be a stress test. It will be very resource intensive (relativity speaking compared to what the normal game load would be). Every single free cell will be occupied by a random object and LOD switching is disabled. I can't imagine a more stressful scenario. If this runs on your machine you are probably set for life.

And speaking of system requirements, here they are:

• CPU: A fairly modern but not necessarily powerful CPU is required. Snapshot 1 does not use a lot of CPU but future updates will bring tasks and path finding back.
• GPU: The engine needs a lot of pixel pushing power, but it does simple things, so most dedicated GPUs should work. Special note to integrated GPU users: the engine should work but it is not meant to on cheap integrated solutions. The worst case scenario I managed to get on the worst machine I could find was 8-12 FPS with snapshot 1 when zoomed out and camera scrolled to a busy portion of the map. Then again, integrated GPU has lower visual quality an can negatively impact game stability. Also the lack of dedicated GPU RAM makes the engine compensate with system RAM, increasing the RAM requirement.
• Memory: 1 GiB RAM dedicated for the game. Plus what you need for you OS. And integrated GPUs can increase this further.

So what is the snapshot system, and precisely snapshot 1 about:

• It marks the philosophical shift from developing until it is done and providing quality at the expense of nobody else seeing the game for years to release early, release often. Weekly (if possible) public snapshots. This also means bugs, stability issues and stuff sometimes breaking. It also means that people who are interested in the final game should not download any snapshots, or if they do once every few months is enough. For other people who want to try stuff and experiment, they can do so and the project is no longer a total secret, with 100% of the information you get cumming from me. 
• It marks the shift from developing something that is meant to at point be finished and become commercial to developing something and whatever. It may become commercial. It may not. I don't know and I don't care right now. Until I flip the coin again, this is a strictly "not in it for the money" thing. This is so I can develop at my own pace and without any pressure.
• Snapshot 1 is the "blank slate". An intentionally minimalistic and stripped down of all unnecessary distractions first version, a 3D visualizer if you will. From this blank slate, each update will carve out the game, reenacting the first year of 2D history in 3D and at a much brisker pace. So if you want to see the game grow up, snapshots are for you.
• Snapshot 1 is a stress test. System requirements are a lot higher. If snapshot 1 does not work at all, future snapshots that are no longer a stress test might.

And on to the content of snapshot 1, together with instructions:

• You will get a zip file that you must unzip anywhere. The location agnostic resourse locator is something I just finished a few minutes before starting this post, so it may fail under weird circumstances. Comment if it fails :). You launch the demo with "DH.exe". In a couple of seconds it should be loaded and functional.
• The engine launches by default using DirectX as a back end, with a resolution of 1280x720x32 in windowed mode with vertical synchronization turned on.
• "data/dh.ini" is you ini file where you can change settings. In the "screen" section you can find a few options that should be fairly self explanatory. You are about to download a strange piece of software from a stranger and are probably a DF player. You can handle it! The only option I'll talk about is "driver": 3 is Directx, 4 is OpenGl.
• A new random world will be generated each time. Completely random. Normally there are some geological rules governing layering. Not so in snapshot 1.
• The camera may be looking at stone section, so all you will see is a colorful checkerboard. Try scrolling and zooming.
• Use the cursor keys to scroll the map.
• F5/F6 zoom in or out. At minimal zoom you screen width will be enough to see around 4 cells. At maximal zoom you can see almost half the map.
• F7/F8 control the camera tilt.
• Try zooming in very close and increasing the tilt to maximum to get a floating camera. The scroll around. Zooming and tilting are interconnected and sometimes you get a nice transition when playing with both.
• , and . keys change the current level.
• Right click and drag to do a selection. For snapshot I disabled item selection because of a bug that only happens with such high item count as in this stress test, so it only works on walls right now. Right click on an unselected wall section and drag a selection. Right clicking on a selected section and dragging erases selection.

And now for known bugs:

• Some mip mapping errors. You'll find them if you know what to look for, otherwise it shouldn't bother you.
• Scrolling can sometimes be weird and jerky. I don't really know how to fix this, maybe I'll get some suggestions.
• On integrated GPU without dedicated video memory graphical quality can vary a lot and system stability is bad. On dedicated GPUs it should never crash but on integrated ones it is practically guaranteed that you will get some crashes.
• On one test system I have encountered some mouse lag. If this happens to you contact me.
• There is a small bug if you do right click selections and scroll the map at the same time.

I repeat: tech demo 1 was supposed to be very hardcore and of no interest to the general public. Snapshot 1 is even less of interest. I expect snapshot 5 to start becoming slightly interesting. But I do appreciate any feedback or bug reports.

And be very careful. As said, you are downloading something from a stranger on the Internet. If you have any suspicions or reason to be weary it is best that you leave it alone. Having up to date antivirus, antispyware and antimalware is a must. Also don't run on critical machines.

Needless to say, what you are running is provided as is without any warranty. You are solely responsible from any damage caused by the use or misuse, accidental or intentional of this software. By downloading you agree to these terms. If you don't, don't download.

The package is copyrighted to the Flavor Of The Month Group, the development group responsible with the creation of the package. And to DwarvesH with several incarnations across  different social media. A full list of members, materials and said aliases/incarnations is not necessary at this moment but will be provided.

I opted to use bold and color rather that upper case letters since people tend to dislike it. I also avoided copy pasted legal speak. Just and English explanation.

So that's it. Update days should be around Monday. So next Monday should be the next update. I'll continue to write about development process as usual, not just on Mondays, but now you will also have the chance to try out what I have written about.

So if you are interested in seeing this unremarkable 3D engine become capable of all the stuff you've read in the past, keep up with the snapshots. Starting with Dwarves & Holes (0.2-snapshot001), unceremoniously dumper to MegaUpload. I'll need a better place.

PS: I can has bugreports?

First generation 3D engine done!

Finally! 'Tis done! The first generation of my 3D engine is done! I fished it a couple of days ago but it has been a terribly busy week so I did not have time to post.

So I'll go over the final touches faster, but compensate by talking about next steps a little.

First, I finished the fine tuning and profiling for LOD switching. The problem was with the buffers: I have two arrays for each buffer, one for vertices, one for indices. Pretty standard stuff. In Irrlicht these arrays are instances of the standard Irrlicht array class and you use push_back to add items, which in turn calls a standard insert. Normally I am a huge proponent of using standard containers everywhere and amortized constant cost growing containers, but here it was performance bottleneck. Check out the code for insert. First is check if it needs to grow the container. Because of the volume of data I have to process I made sure ages ago that containers do not need to grow. Array capacity is computed and stored for future use and when you create a buffer the arrays are automatically set to required capacity. So insert will never enter the grow path. But still, this is a completely unnecessary if in my case. Then it checks if the item is inserted at the end or not. I always insert at the end, so this is a second unnecessary if. So basically, for every single vertex or index, I get two unnecessary branches and only after you fall though them you get to the desired code. Then, I have one extra if that is necessary and introduced on a higher level by me for each vertex/index. So why am I bitching about 3 ifs? Is this not a premature optimization? Well, no, since in the context of the volume of data processed and the requirement of real time camera movement, 3 ifs have a noticeable impact on the smoothness of movement. I eliminated these ifs and rewrote the insertion code to use pointers. The solution is less elegant, but it was worth it. The great part is that this code could work for (unmanaged only?) C#, which supports pointers. I couldn't implement something as computationally intensive in a managed environment because there arrays are checked both for insertion and access.

Then I managed to get XEffects - Reloaded to work. Had to chase down a new modified Irrlicht DLL, but in the end it worked as advertised. Only it does not fit my needs. You see, lighting is an art. More so that a lot of other things. And it is hard as hell to do. Lighting is single-handedly the most difficult task I have encountered in this project. I went over several iterations of it. A few night ago I spent two hours just tweaking lighting. Right now I am using a 3 light system: a spot light and two directional lights to simulate outside lighting conditions. Light only illuminates items, terrain is not illuminated because I can only get if very dark and not uniform or extremely bright. Lighting and stencil shadows are somewhat decoupled. but with XEffects and shadow mapping, lighting and shadows are very tightly coupled. So I was forced to illuminate terrain. In the end I almost managed to get illumination to look like and outside scene, but here is where I found the first big obstacle: realistic lighting came at the price of having to position lights very far away from the terrain. Shadow mapping is very dependent on the distance between the light and the object it illuminates because it works with a fixed resolution shadow map. So with the distance I was using shadows for objects were barely a few pixels wide in the shadow map.

The second problem is probably related to the complexity of the scene: it is so high that I had to modify Irrlicht in order not to crash. XEffects also crashes. I could only add shadows to terrain and other discrete meshes  like dwarves. When adding it to the item meshes, it would crash as vanilla Irrlicht does.

So in the end I did not manage to get XEffects to take over shadows for me. I did learn some important lessons and I think I know what can be done: either figure out a new lighting model that does not rely on distant lights, or create a special version of the XEffects shadow mapping tehnicques that decouples lights from shadows. Use the isolated lights to illuminate everything and a directional shadow with a fixed "reach", similar to the case where you would have shadows cast for every object by one light each that is very close, but follows the direction of a sun ray.

Needless to say, my skill level is no way near the level it needs to be in order to implement such lighting and shadows. And it would take me months to implement and test it. So I'll stick with stencil shadows for now. For Tech Demo 1, there will be two options, one controlling item shadows and one controlling terrain shadows. Low LOD objects do not cast shadows. With low item density performance is more than acceptable with stencil shadows, with medium density it is way to slow, so shadows must be turned off and with very high density the engine crashes.

The engine can also handle animations as long as the number of actors is low (hundreds at most). I am yet to find a good format to export meshes with skeleton animations from Blender, but meshes that are already exported work fine.

Reading this you may be wondering why I am not using an existing engine for this game. Well, first of all, Irrlicht is considered a 3D engine, so probably the discussion should be about higher level engines. Finding such and engine is not a trivial task. Even if I were to assume that porting to the new engine would take zero time and effort, I have very specific needs. I need a fairly high level engine that can do a lot without the standard overhead of high level engines, while being focused on supporting huge number of objects and destructible terrain. I am not aware of such and engine and if one exists, it would probably have steep licensing fees.

When working with engines it is the small details that get to you. Let me give Ogre3D as an example. Ogre3D requires each scene node to be identified by an unique identifier. The documentation says that it checks the identifiers and gives an error if it finds duplicates. Identifiers are strings. Not let us consider my video about 300k barrels and let's consider that each barrel would be an unique scene node (in my implementation this was not true; I used batching for performance reasons). So I would need to create a fast algorithm that assigned 300k strings to nodes on the fly and pray that Ogre3D finishes the checking fast enough. You may think that this should be fast, but I had problems with 3 if statements. Even if this discussion is theoretical, who know what Ogre3D does behind the scenes and how fast it is. So before I can choose an engine, I would need to do a very thorough evaluation of each and make sure that such details are never and obstacle.

So what next?

I don't know about you, but I am getting tired of working on the engine and would very much appreciate a palette cleanse. A second generation 3D engine will be created, but I am sincerely hoping that I wont start working on it until March 2012 and spend that time on fishing workshops and crafting. Workshops will be my next focus, with some effort spent on the overworld map.

But December is not going to be a productive month. With 3 official holydays and at least two larger events I won't get that much work done. Still, updates will come. I'll put the code base on feature freeze for Tech Demo 1, iron out a few bugs and search for a good installer generator so I can make it available.

Since most of the changes are implementation details, I can't find a screenshot to summarize up the progress since it would look like previous screenshots. Or maybe I can:

Here's a lovely levitating land trout. A formidable foe indeed. A bane to the existence of any peaceful fortress! Thank you very much InfecteD for modeling this beast!

PS: I really need to add a test skybox, maybe something from here:

http://www.redsorceress.com/skybox.html.

So Random... - 02 - And a little bit of color

Good news everybody! The first generation 3D engine is nearing the end of its development process. I am so close! Still, I need a few more day so until then let's get some semi-filler going!

Last time I left you with a grayish height map generated with Perlin noise that could be considered a fair approximation of a section from a natural land mass. I concluded with some musings about merging several height maps, one used for giving shape and another for giving detail, but today I am going to continue in a new direction.

First, I chose a standard water level. Based on the relative distance to this water level I tried to assign colors to the resulting map to make it seem more "natural". Of course, only using height for coloring is less than ideal. You get a few cases where huge jumps in height generate some colors that don't really make that much sense geologically speaking, but we can get some nice results:

Blue is the water mass. The darker the blue, the deeper the water is. On the shore we have sand that is represented by shades of yellow. Then green and brown for different elevations, up to white as we get to snow. The snow also has a nice little "bloomish" effect. All color transitions except for sand and white snow are perfectly smooth, while sand and snow show some discrete color shifts. This was done to enhance the visuals and is purely cosmetic. The height change on these types of terrain is still smooth.

To test the generator I tried to make it render 10000 maps, but I grew bored after 1200+. Still, it works and can generate a pretty varied set of maps, like this mostly water based one:

I will probably have to exclude such maps because they have too much water. The algorithm is not capable of generating and infinite number of realistic maps (but can generate a huge number of maps, including ones that are ugly/unrealistic/undesirable based on integer/floating point max size) and currently it outputs 20000 unique maps. This one I really like:

So generating small maps in great numbers works fine. It is even fast enough that you can create an interactive map navigator. It won't be snappy, but it will work. But what about creating really big maps with high detail? Like I said last time, one of the great advantages of Perlin noise is that you don't need to create and store the entire map with high detail. Or low detail. You create just as much as you need, cache it if you think you'll need it for latter, discard otherwise. But still, it is a good experiment. I created 8192x8192 high detail image. This took over 4:45 minutes and ended up occupying 270 MiBs RAM. Saved on disk as a 10 MiBs PNG. Blogger won't allow me to embed such large images, so I will post a screenshot of the image:

I created and even larger image. This one is 13312x13312 and creating it, saving it and immediately trying to load it almost crashed my system. It took Windows a few minutes to recover:

But colorizing based on height is not the only thing you can do. You can also try to texture everything. To better illustrate, I'll show the before/after results, with before being just Perlin noise and after being the full textured result:

This post is already too long so I won't explain today how you texture this. Maybe next time. 

Especially since there is one more thing I must talk about right now: the above image, while it looks pretty good, has one huge obvious fault. Look at the top of the snow surface. It is perfectly flat. You see, these maps are generated 100% based on Perlin noise. It is just noise, nothing more. Luckily, you have a bunch of parameters and a random seed. After a lot of experimenting with these values (except for the random seed), I managed to turn noise into something that looks a little like a land mass. With looks being the key word here. These parameters were chosen based on aesthetics. I did not try to see a 3D render of the map and decide what is best for that. And what is best for that is not the best for the aesthetics of a color coded topdown map. Which is again not the best for the aesthetics for the textured map. Long story short: I have chosen a set of parameters that creates good looking maps, but sacrifices detail in parts that are less visible in favor of parts where this detail would make more of an impact. In the color coded map renders, you did not notice that the top of the snow are is flat. I used most of the detail information to render a more convincing set of low heights. The parameters will need to be rebalanced for this texture based rendering. The flatness is more apparent on a "colder" map:

As a first step I'll need to make oceans not take up any detail resolution and use the freed up resolution for mountain tops. If this is not enough, I'll try the combination method I wrote about last time. I'll leave you for today with a render of a larger section:

So Random... - 01 - Noise World

I have three more major things do before Tech Demo 1: first I must finish the LOD switching. Coding is done, but I have tons of profiling to do and this will not result in posts so it will be a longer but silent task. Then I need to decide what to do with the shadows. Stencil shadows work fast enough only with very low item density. I had zero luck with shadow mapping. For the Irrlicht solution I tried XEffects, but that package is far to old and can't be compiled with modern Irrlicht. XEffects - Reloaded has several problems, the largest beeing that it won't work with out of the box Irrlicht DLL. You need a special DLL. Of course, the link to the DLL is dead. I still got my hands on it though, but because I have also modified Irrlicht I get some weird failure in the creation of the 3D device. I do not have the sources for the modified Irrlicht  XEffects was created from in order to merge both. And the biggest problem is that XEffects requires GPUs that are more powerful and newer that the ones I am targeting. And speaking about dead links, at least 90% of all links when you google a topic like shadow mapping are either incredibly outdated, or more often just dead. The final thing I must do is the administrative tasks before the release, which again do not involve coding.

So I need some filler content that can occupy my time for the time being. I decided to do some very experimental stuff (even for me) while the above points are resolved, but while still following these rules:

• What I implement must potentially advance the project by adding features or at least improving existing features while adding new lines of code. I could spend days tweaking values and balancing stuff, but I am not allowed to do that.
• It must not be completely outlandish and unrelated, like e.g. simulating the movement of bird wings in thick mustard.
• Every session must add at least 200 lines of code.

For the first topic I though I'd start with one thing that is missing and is very apparent that it is missing: "owerworld" generation. I need a larger and fairly realistic land mass from where you can select you embark location.

Right now I am using midpoint displacement for the embark location, but I will switch over to Perlin noise. What is Perlin noise you ask? This:

It is coherent noise (smooth and without seems, optionally tileable) that has a bunch of interesting properties for world generation. I hear the big boys are moving away from Perlin noise to other types of noise that have even better properties, but I'll stick to what is clearly documented. Also, Perlin has a large number of advantages over midploint displacement:

• Midpoint displacement is slow. You are basically subdividing your area and randomly shifting the midpoint and then recursively repeating the process until you get a small (typically size of 1) square. So basically recursive computations with floating point numbers, where the size of the map directly influences the depth of the recursion. Slow. Perlin noise is no speedster, but by adjusting the number of octaves and interpolation method you can get some faster results for testing purposes. You can also do a fast calculation followed by a slower but higher fidelity calculation based on some information you have learned from the fast run.
• It is hard to control the shape of the midpoint displacement. You are dividing and randomly increasing the middle point. If you want better shape you use the square-diamond method, which makes it even harder to control. The dimension of the results is also kind of fixed. It is not a lot easier to control the shape of Perlin noise, but you get to discover some interesting tricks to compensate for this. Also, a good Perlin implementation is very customizeable.See what I can do with the same algorithm:

• Midpoint displacement must be computed down to the smallest unit and the end result must be kept in memory. Perlin noise does not need to be kept in memory. You can compute it on the fly for every point you desire. You can cache the results or just do it on the fly (as long as it is fast enough). So you can have virtually an infinite sized world. Diamond-square displacement on the other hand would require enough memory to be allocated for the generated area to fit inside and the value of a point is dependent on the point around it. Here is a nice comparison shot of the same "world" generated once with low detail, once with high detail (the twos sets were generated in complete isolation, one does not need to know about the other):

• Perlin noise offers "infinite" detail as you zoom in. As you increase zoom level you need to increase the detail parameters, but theoretically the only limits are given on how fast you want to generation to be. The memory consumption is constant (and zero if you decide not to cache anything; not a good idea). Using the above high detail map, let me show how it looks when zoomed in 20 times to a point near one of the middle darker spot:

As you can see, the zoomed in portion is smooth and still detailed. Generating the zoomed in portion takes the same amount of time as generating the zoomed out one. If you consider these results the values in a height map, you can begin to see how this could be used for world generation: the darker a pixel is, the lower the elevation.

But the above patch does not look realistic at all. What piece of land looks like this? Maybe a section full of hills somewhere in the middle of a big continental map, but such maps are boring. I'll present a very intuitive way that can be discovered by experimentation to give some fair results.

First, one might argue that you can't really tell what is going on because of the smooth transition in the shades of gray. So one might be tempted to render the same "map" with some form of edge detection/strengthening algorithm. Or just simply increase the amplitude:

Wow! Is that it? That's the result we get by simply increasing the amplitude? The image on the right is the same map, but rendering at a zoom of 20 while centered on a random point. This gives an interesting clue: the zoomed out map is still too busy to be realistic, but the zoomed in looks like a section from a continental mass. Maybe we need to start with such a high zoom level and zoom in even more to get to expedition section. But before I talk about that, let me prove that the two maps are identical and also demonstrate some interesting composition properties. Let me show you what happens if we take the two previous pictures and place then on top of each other, with white used for transparency (please ignore the picture on the right; only the one on the left is important; but still, the right section looks very interesting if you imagine it with selectively inverted heights):

Back to the use of zoom for more realistic land masses! By applying the zoom factor of 20 for the normal map, and again 20 (so 400 total) for the zoomed in section and after adjusting some parameters to make edges more pronounced at such zoom levels, we get this:

The image on the left is our section of the continental map and it looks fairly realistic. One could choose the coordinates to zoom in randomly, do some computation to achieve some ratio of water/land or some desired height average or just do what I did: take coordinates (0, 0). The local map on the other hand does not look that good. It is very hard to find a coordinate in which we don't get an image similar to the one on the right: a clear and relatively straight separation of water and land.

I tried to compensate for this by lowering the zoom factor and making edges even harder. Also, choosing a starting location that is more interesting and has a lake also helps:

The problem with this approach is that you loose detail. So I tried to generate two maps. One with an amplitude of 10 and one with an amplitude of 100. Overlaying the two gives this result:

Hmmm, not great, but we have some detail in the elevation progression. Let's try different parameters:

Well, obviously this is going to take a lot more fine tuning. Here is another blending, but this one is more advanced because it is done in Photoshop. If I were to add some kind of normalization to make sure the border between water and land is more smooth, I could get (hopefully) better results:

Total number of lines of code: 267. One question before I leave: do you thing it would provide some value if I were to post the source code for the example above?

67 – Frosting Culling

If you don't want to read this post but are interested in Tech Demo 1 then check out the end of the post. Or just read though it!

Check out this screenshot:

We only get 37 FPS. But it is a full map view, with 5,507,481 vertices and 10,040,364 triangles (assuming I did not make a mistake in the code that computes these values). That is 371,493,468 triangles a second. My GPU is working really hard trying to pump out this volume of triangles and it is understandable that performance is low. Now let's get a little bit closer:

What! We now have 46 FPS! A little bit closer:

What? 64! What is happening? What!! Even closer:

Uuuuuu! What? 159? Ooooo! What? What is happening? Must get closer:

Ooooo! Uuuuuu! What is happening? What? What is happening? Uuuuuuuuu! 318? Ooooo! What? What is happening? What is happening? Uuuuuu!

I wish you were here besides me because I am making the most obnoxious and annoying "u" and "o" sounds humanly possible. And a Stifler face.

You may have guessed what is happening: then engine now supports frustum culling. When all the scene components are in view you have no choice but to render them. But as they get out of view they are eliminated and rendering performance increases. Actually, they are only hidden. The buffers still take up resources. Frustum culling is dependent only on camera position and direction and camera movement can be very twitchy. Imagine a first person shooter when you can swipe your mouse around very fast. Doing a few axis aligned bounding box frustum collisions is doable. Building and destroying buffers on the other hand is not because it would make your mouse less responsive. So the bottom line is better performance, same resource use.

Normally I would do a LL3DLGLD on frustum culling, but most of the job I did with the capabilities provided by Irrlicht. Irrlicht automatically culls, but it uses a computationally very fast but not very effective in getting nodes out of the rending pipeline approach by default. I suspected for long that culling was on by default because every time I messed up bounding box creation some nodes started disappearing randomly. Changing the culling criteria to box vs. frustum insides generated the above results. I only wish that Irrlicht would remember the results of its previous frustum check so I can use it latter, but I can repeat the check manually if I need it at another time for some other things, like not switching LOD for nodes that are out of view.

Frustum culling scales well with almost all camera modes and should give you and extra substantial boost in performance. It even makes the game run on poor Intel integrated chips that would have no busyness rendering millions of polygons. As long as you keep the camera very close to the action.

Only a first person view is not ideally served by frustum culling. I will need to add an additional camera distance check.

I can't wait to see the performance data after LOD switching is working as intended. As explained last time, LOD switching is fully implemented, but I do not have low poly models yet for most objects, so the low LOD mesh points to the high LOD mesh, making LOD switching generate a constant level of detail.

But still, I just can help it and feel that the view in the screenshot bellow is just epic with the sheer amount of objects visible:

Frustum culling was a worthy addition to the engine and to the feature set of Tech Demo 1. Useful LOD switching and some better camera movement will also make it into the first version.

And here is my question to you, my loyal readers: what else would you like to see in Tech Demo 1/the engine as a whole. Keep in mind that Tech Demo is designed to test if the engine runs on the targeted spec and provide information on how to make it run better. It is all about the engine. So Tech Demo 1 will not have any of the following (and more): GUI, dwarves, actions, property inspectors, time compression, path finding, etc. It is going to be a pure engine test, so it will have rendering of one or more random levels, different densities of objects, level switching, camera modes, camera movement, etc. And of course all the technology behind it, like buffer lifetime management, frustum culling, lighting, LOD switching, etc.

So keeping the above constrains in mind, what else would you like to see in TD1?

PS: This is not for TD1, but I have an idea that would assure that a future TD would be tried by a lot of people: making the tech demo able to load DF and/or Minecraft maps. It won't be the primary or secondary function of it, but it would work at a satisfactory level. This is a task I think I will need help on :).

66 – Not about Nyan Cat

Today I will be documenting my most recent failure. A very pretty failure. 

Using what I learned yesterday about lighting effects I created a new lighting model. Together with stencil shadows this creates considerably prettier scenes:

The lighting model is far far faaaar from perfect, but already it is very useful at helping you figure out what the content of the scene is when zoomed out. Here is a close-up:

There is just a little bit of shinnyness to objects as it should be when they are outside in the sunlight. The column, chest and through are not textured and without the lighting effect they would look like a white outline filled with white, a completely uniform surface, but with the effects I have applied the shape of the object gives it shading so you can tell what it is:

When compared to how it looked in my last video, the though is much more pronounced. The shadows helps but even without it the object looks much better:

Here we have a chair:

Another composite shot:

And finally a column showing shading and a shadow cast on the wall:

It looks very good. 

But you may have noticed a problem: the object density is very low. Normally I create absurdly dense scenes to demonstrate what big cojones my engine has. Not only that, but check out the framerate: it is very low on most shots.

It is not because of lighting. I could not find any performance decrease caused by the lighting effects and it is probably almost free. The slow down is caused by the stencil shadows. This is the maximum object density I could afford with shadows and it still runs very poorly.

Using a custom world population algorithm that is not longer random and flexible, but generates a pseudo-random (more like pseudo-pseudo-random) distribution that has some random elements in it but is is specially designed to make shadow creation as fast as possibly I managed to raise the performance to slightly over 30 FPS with he same very low density.

So I think that stencil shadows are out of the question. First I'll do an experiment to see if I can make Irrlicht throw shadows for some dummy low poly objects instead of the real objects. Maybe this can help. If this fails I'll abandon stencil shadows and try shadow mapping. Irrlicht does not support shadow mapping but there are some third party packages and information on this subject so I'm hopping I'll have no problem implementing it. The question is if it will handle a huge amount of objects with good performance?

Using the above mention population algorithm I recorded a short video showing a very sparse world in action. 

Some of you will be happy to hear that I get it. I really do. I see now why you do not like the "fly" camera movement, how you would like it to behave and why it is confusing to you. I have no problems with it personally, but I'll add the option for a more "natural" camera movement that does not roll. 

But not now, because I have bigger fish to fry, so enjoy the video with the old camera: