• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
  • entries
    11
  • comments
    28
  • views
    23549

Results! Yay!

Sign in to follow this  
Followers 0
TheChubu

1155 views

Hi again! I'm getting back on track with this terrain generator project since I have more time now biggrin.png Tried the recursive MDI and had some success with it, which means pictures obviously tongue.png

[font='comic sans ms']

Back in Time

[/font]

I'll try to reconstruct this paragraph since I deleted it by mistake (closed the browser without saving the changes tongue.png)

In the last entry I commented about the massive data ammounts that the Midpoint Displacement's Inverse process needed as it was on the paper, so I decided to try the recursive approach I found on another version of the paper. I was going to discuss why the previous method needed so much data but I forgot exactly what I was going to say (had a draft of only one paragraph) and I'm not looking forward to delve into that code again so I'll just jump over the issue completely.

[font='comic sans ms']Forever a Point[/font]


So, Midpoint Displacement's Inverse. This process comes from the idea that a Midpoint Displacement algorithm (which isn't the same as a Diamond-Square algorithm) result depends on the height data generated by the previous iterations of the same algorithm. Thus, each set of new points depend (more or less) on the points that preceded them.

With that in mind there could exist a MD algorithm that is aware of already existing data. The paper achieves this by having two arrays: One with the height data and the other with the state of each height value. There are various states that each point can have (river, ridge, done, null) but the most important part is differentiating between those already computed (river, ridge, done) and those that need to be computed (null).

I don't know exactly how the paper achieves this "awareness" but its probably with a check before calculating each point. If the state at (x,y) is NULL, then calculate the point normally, if it isn't null, then leave it as it is.

For simplicity I used a map with only ridge lines traced on it to begin the process:
recursiveInverseMidpointPassPreProcess.png

The state checks alone won't give you good results:
recursiveInverseMidpointPassMidpointOnly.png

You can see that the MD algorithm sort-of adapts to the ridge lines in some places but rapidly loses track and it gets ugly.

[font='comic sans ms']Inverse or Reverse?[/font]


To solve these issues, the paper introduces the Midpoint Displacement's Inverse process. It is an algorithm that steps through the data and places height values where the MD algorithm expects them and that make sense in the context of the present pre-computed data. That way the MD algorithm has more data to work with and can adapt better to the main features of the terrain. You can check it out on the alternate version of the paper that I found.

There are a few parts of the paper algorithm that I don't understand, for example:if nns>0 then;o a ?for each corner of square in DEM: the altitude average of all non-NUL cordinates;o for each corner (l, m)of square with a NULL coordinate: -altitude(CDEM[l][m])?a + s * ur() -state(CDEM[l][m])?DONE;
nns is the counter of non null states. That means, if we have at least one corner pre calculated in our square, make a rough assumption about the heights of the other corners. DEM is digital elevation model, your run off the mill heightmap. And ur() is an uniform random value between -1.0f and 1.0f. s is the current stepping of the MDI iteration and the square represents the subarea where we're working on.

Now, that "for each corner of square in DEM: the altitude average of all non-NULL cordinates" is kinda weird. I *think* it means that I have to average all the height values of the known corners. (ie, (corner1+corner2)/2 ) but I'm not sure.

Then, the next part I just don't have any idea what it means. "For each corner (1,m) of square" ? Where the "m" comes from? Why the constant 1? I guessed that it means that for each corner that has a null state, calculate it with the average of the non-null corners like it says in "a + s * ur()". Then set the state of that coordinate as DONE. But its just a guess based on what I'd expect it to do, I honestly have no idea what that "corner (1,m)" means.

[font='comic sans ms']Artifacts in my soup![/font]



I half expected it to burst into flames, but alas it kinda worked. Not only it wasn't awfully slow like my last attempt (70ms against like whole seconds for a 513^2 map), but it worked better, still ugly, but better:

recursiveInverseMidpointPass.png

You can see that the algorithm adapts way more to the ridge lines than before, misses a lot of terrain and has weird points around. I'm thinking I have issues with the sub-square sizes. This result is actually after arbitrarily creating each subsquare with square.width = stepping + 1. This is what happens if I leave it as square.width = stepping (like the paper suggests), albeit with a different base ridge network:

MDIBroken1.png

And this is what happens when I leave it as square.width = stepping - 1

MDIBroken2.png

I know the artifacts on the first image since I had them while implementing a regular MD algorithm, I was sizing my subsquares with a width off by 1. That's why the white points are spaced by long black lines. Now for the second image I have no idea what is going on. Probably missing all the corners or most of them, so barely any new point gets generated.

[font='comic sans ms']And the moral of the story is...[/font]



I'll try to find out what's happening with the squares. I'm pretty sure its some width/height/range issue. Maybe I'll attach some code next time biggrin.png (though I hope to have it complete and "readable" someday). Until then, have a good night! biggrin.png

1
Sign in to follow this  
Followers 0


2 Comments


Ah, the terrain generator. Those were the days! Months spent trying to understand a 4 page long paper.

0

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now