Sunday, May 16, 2010

Graphics Final: Volcano Simulation

Adam Dziuk and Benjamin Finkel
CS 384G Final Project
Volcano Simulation

For our final project in CS384G we strove to emulate the effects of smoke from volcanoes, taking great inspiration from Eyjafjallajökull's prominence in recent news. This process was divided into the two components of lava and smoke, chosen for their distinctiveness as part of eruptions. We rendered the lava as a swarm of particles parametrized with time-dependent variables. The smoke was rendered using a 3D adaptation of Jos Stam's simulation of stable fluid dynamics, chosen as the best way to produce the distinctive vortexes which often characterize smoke.

The lava particles are assigned a random mass when they are generated, which affects their size, mass, velocity, and lifespan. This allows the smaller particles to act like spray which quickly vanishes from view, while the larger ones resemble proper globules of lava. These effects were chosen because they allow for a constant amount of particles to render what appears to be a constant eruption. This allows for much quicker simulation because it does not require resizing of the vector, which can quickly become very expensive.

Jos Stams "Real Time Fluid Dynamics for Games" paper contains source code and explanation for a high speed, good looking fluid dynamics simulation that requires relatively little overhead. Indeed, the simulation of the fluid dynamics itself is relatively minor compared to the rendering time for most relatively small sized simulations (56^3 takes about 5 minutes to render a 20 second movie).

Stam's simulation partitions a space into cells which hold densities of the fluid as well as velocity vectors for moving the fluid around. The vectors and densities are initialized and updated with each time step for factors like wind and the volcano's expulsion of the smoke. But each time step also updates those quantities by the process of advection, which simulates the momentum of the fluid. This process transforms the vectors along themselves.

Jos Stam released source code for how to simulate his fluids in 2D, so the tricky aspect of our project was adapting it to the third dimension. We decided to render the smoke as cubes, analogous to Stam's squares, with alpha blending to color it. By raising the resolution of the grid to a high degree, we got smooth looking smoke to issue from the volcano, with the expense of a massive rendering time.

The smoke simulation is highly sensitive to its settings allowing us to produce interesting effects by having powerful wind:
or by manipulating diffusion



In the end, by rendering overnight we were able to get some very nice looking eruption videos.
Here is our final result:


References:
Jos Stam's publications
Stable Fluids
Real-Time Fluid Dynamics for Games
Stam's code

Adam Dziuk and Ben Finkel

Tuesday, April 27, 2010

Mechanics Ideas for the Atrium of Ganeden

So, I've been thinking the past few days about some vectors for mechanics in an RPG combat system, particularly for the pipe-dream that is Atrium. I thought I'd share some.

One of the basic themes of the game is the Rule of Three; for example, there are three core choices to the game that each have three options (providing 27 finales). So I thought it would be nice to partition the basics of combat into three spaces, each of which is also partitioned into triplicate. The first division defines the "shape" of a character's power: how do they interact with the battlefield? The second division applies a sense of theme to the power, which matches the theme of the character most strongly associated with that avenue of combat. The final division... well, it's still up in the air, but it's looking like it will match the particular idiosyncrasies of the practitioner of the power.

So, what do I mean by "shape?"? I've been thinking of the three branches here as the following: the tree, the trellis, and the vector. Let's discuss these in detail:

The Tree:
A character has a bank of abilities of the following structure: (a) an initial effect, (b) a list of requirements for future moves, and (c) a reward effect for completing the list. In a given turn, a character has some requirement imposed on them from a previous turn: this requirement can be filled by a variety of options from his bank. He can choose to perform one of those options, which may in turn provide more requirements for later turns, or mulligan the tree he has constructed so far. Some options, called termini or leaves, provide no requirements; their initial effect is their reward effect, and they serve to help fill requirements out.

Many of you should of course recognize this to be isometric to the Tree data structure of computer science, among other fields. I think the interesting effects lie in the following aspects: choosing the bank of abilities, basing reward effects on how the requirements were fulfilled, and providing situations where taking a mulligan is an attractive option.

Here are some examples of flavorings of this mechanic: language trees, divide-and-conquer algorithms, Duty ethics, branching fractals

Example:
Ovalia has abilities based on the language tree. In the Garden, the player chose a bunch of different context-free grammar rules to serve as the basis for her abilities. These are things like:

S -> NP VP:
a) Provides X damage to all foes within radius of Ovalia
b) Must provide a complete NP, then a complete VP to complete
c) Stun and do massive damage to all foes, as determined by the score of the sentence created
______________________________________

The Trellis:
A character establishes a space, or fortress, where they have considerable control. Their turn provides options to increase the space their power manifests, to apply powerful effects within their sphere of influence, and to sacrifice some of their territory for some gain. For many characters who follow this path, the stability of this fortress provides strong benefits: some actions may involve starting a process which has drastic effect upon completion, but which requires certain features of the fortress to remain stable throughout the process.

Flavors: circuitry, dynamic programming, "bottom-up" parsing, force fields, Virtue ethics.

Example:
Vursik has his basis in circuitry. During his turn, he can add a length of wire to his circuit in sequence or parallel. Instead, he could create a feature at some point in the circuit he has built, such as:

Bulb:
Damages opponents which come within a radius lightly based on the current flowing through the bulb. Prevents such opponents from leaving the radius until the bulb is destroyed.

Finally, Vursik could excise some wire to add to the voltage supplying the circuit.
______________________________________
The Vector:
A character has a small variety of abilities whose effects are strongly determined by attributes possessed by other objects in the battlefield. Many of these attributes are not able to be directly influenced by the character, but he may have some sort of method to transform the attributes of bulks or individual objects on the field. Characters who are shaped by the Vector are strongly influenced by character synergy, a value which depends on the proximity to other characters with whom he has a strong relationship.

Themes: public key encryption, probability distributions, Greedy algorithms, energy potentials, fluid dynamics, Consequentialist ethics.

Example: Tor's abilities are defined by a simple and skewed version of public key encryption. He is able to broadcast a message to all characters on the battlefield. This message is a damage value which ranges over some interval from, say, [-128, 127], which is then multiplied by the character synergy value. He can view all of the public keys of all actors in the field, as well as the private keys of his allies. He can change his own public and private keys. When the message is broadcast, it is encrypted and then each character decrypts it as per RSA rules . The resulting message that each character receives is the damage it takes - negative damage heals.
______________________________________

As I am sure you can see, this is all very rough and still way open to being changed. Some of the goals I have in this system are:

a) To be fun.
b) To encourage non-trivial tactical decisions
c) To educate players about real world concepts and reward mastery over those concepts.

Anyway, I felt I really had to get this jotted down. But I really want to hear some feedback! At the very least, say hello here. I miss you guys!

Ben

Saturday, January 2, 2010

The First of January

Well, it was a good day, wasn't it? The start of a new era, I should say. It'll be good, I trust. But beside the fun we have in arbitrating calendars, January 1st was a good day for me because I got to finish consuming no less than three widely disparate pieces of media, and not one of them was terrible.

In fact, most of them were pretty awesome.

The End of Time

Many of my few readers will be able to predict that one of those works I enjoyed was the season finale of Doctor Who: The End of Time. David Tennant and Russel T. Davies' final episode, it certainly had pomp and ceremony, in addition to the antics and "shenanigans" of any Davies piece. The worst bit of it was the entirely unnecessary and over-the-top Cult of Saxon, which was daft beyond measure. There were so many other throwaway bits and pieces throughout the two-parter, and I suppose that's a strong indication of rather terrible writing, but I don't feel like documenting them here - check out www.behindthesofa.org.uk for some adorably vitriolic fan response.

But it certainly was fun and that's the hallmark of a good Davies episode. And he did do a wonderful job in creating moments between characters - the Doctor's rant near the end, the celebrated cafe scene, the lie-down after confronting the Master; each was excellently emotional. But to be frank, I can't wait for Stephen Moffat to make this series better than it's ever been before.

Spirit Tracks

While I was waiting for that colossal second part of Who to download, I finished up my first and likely only playthrough of Legend of Zelda: Spirit Tracks for the DS. I think it will be a largely forgettable game for me, unfortunately. There were some really rather good mechanics and puzzles, but every piece of glitter had a ream of rust along its side.

I suppose I'll start with what was enjoyable. The puzzles in the central dungeon, the Tower of Spirits, were as good as those in the rest of the dungeons - which is to say, excellent. Nintendo didn't fall for the bizarre mistake they made in Phantom Hourglass of making the whole thing too repetitive - even the recap-ish puzzles at the end of the dungeon seemed fresh and interesting. The DS's interface played more of a role in this game - notetaking was integral, the ability to use the stylus as an aiming method was indispensable, and block manipulation was pretty good with the stylus.

In terms of items, one shining beacon from this game I hope will illuminate future titles: the Snake Whip. You could use it like a hookshot of sorts to grab items and swing across gaps, but I really liked the fact that you could use it as a sort of half-power sword, and the fact that you could disarm enemies with it. My favorite mini-game was a race with the whip against the clock, swinging all the way up a cliff-face island. What made this item so grand was its versatility - from obstacle-passing to combat to item-manipulation from a distance. And it's a snake!

Most of the minigames were pretty good, but a goodly number of them were rather difficult to pull off well. There's a bow-and-arrow game, of course, but the trick is that this one's score is mostly based off of how many shots you hit in a row, which proved rather stressful. The many-floor-gauntlet-of-enemies-with-no-hearts minigame was rather frustrating because you were only likely to lose near the end - and then you'd have to start over from the beginning. Which I suppose would be fine if the mess didn't take at least fifteen minutes to traverse going at a regular pace.

But I guess it's time to segue into the shenanigans. The train thing was terrible, no exceptions. It was slow, minimally interactive, and (when it wanted to be challenging) entirely to ready to dish out the old "game over". Crashing into an enemy train - which can be easy, given how they seek to you once you're within their territory and how they are faster than you - sends you straight the Lose screen, do not pass Go, do not collect 200 rupees. Isn't that offensive? I honestly can't think of any feature of the train system that was redeeming. Just give us back Epona already.

I think the worst aspect of the game was the insipid delivery quests. Eventually you can take on passengers and cargo, and be a do-gooder in getting them where they need to go. Passengers need to be kept happy, which involves avoiding getting hit by enemies, avoiding slamming on the breaks, and obeying horn-tooting and speed limit signage. I suppose those ones weren't so bad - I think I never lost one unintentionally. But cargo delivery. UGH.

You buy some cargo, often for a fairly pricey sum, like 200 rupees. Then you set out on your train with a quantity of the stuff, which is the maximum quantity you can carry (so you can't make the following part easier for more rupees, if you wanted to...). If you get hit, you lose some. For many goods, that's it - which is made difficult by the fact that you might be carrying the minimum you need to fulfill the quest, like the single-urn delivery. But with a goodly number of goods, there's another "feature" - melting. Ice, fish, and dark ore all disappear over time on your train, so now you have to go full speed (which is still slooooow), while avoiding being hit and following the perfect route. For dark ore, you have to pretty much do this without mistake, while also fending off the second-hardest fight-on-the-rails in the game. This is also the most expensive such delivery quest in the game.

When you lose, the game doesn't even have the decency to send you back to start. You may have just spent a goodly number of rupees and minutes doing absolutely nothing in terms of game progress. Daft. The rewards aren't much better - usually a few new rails, maybe a teleporter gate (which forms a two way link and is the only significant way of moving appreciably across the world [what ever happened to teleporter songs?]), perhaps a new station to visit. But! In order to get the rewards from the two collect-them-all quests, you have to do every single one of these delivery quests in the game.

Back in, you know, the good Zelda games, the powerful rewards of Hurricane Spin, sword beams, and the like were found roughly two-thirds of the way through the game if you were focused on earning them. I do not exaggerate when I tell you that it's only possible to get these rewards when they are no longer useful - when the only enemies left in the game are the ones which won't really be affected by those abilities. Stupid.

In short, I don't really recommend this game. There are a lot of nice things - Zelda playing a more integral and cool role, wonderful music, innovative puzzles - but I don't think that they outweigh the frustration or stunning mediocrity of the parts that don't work. Oh, and there are points in the game that are impossible to pass while in a car due to finicky use of the microphone by the game.

The God Delusion

Here we go! This Richard Dawkins book was nothing less than wonderful to read. I got it from Dad for Hannukah, and read it on our trip to New Orleans last week (which I guess I should also write about at some point). I'm sure you've heard of the book - the seminal piece on Atheism: its logic, its advantages over religion, its role as a vector to free people from extravagant waste and ignorance. I would highly recommend every English speaker in the world to read it, honestly. But there are parts of it I take a little bit of issue with.

Firstly, he excuses pantheism, the awe and wonderment at the entirety of the universe and the naming of it "God", as the sole exemption from his imminent siege on the illogic of religion. That's not really objectionable; after all, he makes clear that pantheism is just another interpretation of "the universe", which is indeed awesome and wonderful, whereas deism and theism both invoke supernatural intelligences, which Dawkins handily disposes of as so improbable that they should be treated as impossible.

So, no objection there except what he's omitted: what about my own "religion" of panentheism? Note the "en" in the middle - "All in God" as opposed to "All God". Yes, God is the universe in all its ugliness and glory; God is the feces in the sewer and the fledgling star in the nebula; God is the bewildering complexity of a single cell and is the rigid simplicity of a solid crystal; God is time and God is humanity. All of these tenets of pantheism are agreeable to me, but I fear that that philosophy makes God a synonym, which isn't that useful to me. I'd rather have God be a word that describes a different concept, which has no other word and is yet more spectacular. There is no word for the thing which combines our universe, the potential multiverse that we may discover to be verifiable, the phase-space of possibilities for everything, thoughts and ideas and patterns, emotions and knowledge, logic and math, and the things our minds physically cannot model at this stage in our development. By nature this entity is omnipotent, omniscient, and omnipresent. I think that's a pretty good God.

I suppose, though, that the book wasn't about what is worth it to find awe in, but rather what isn't. But there's another point to discuss here. Dawkins describes the traditions of religion as extravagantly wasteful, and I suppose I'll have to agree. But an awful lot of good things have come from it: literature, cathedrals, holidays - they are the embodiment of religion, and while without religion we would have equally acceptable alternatives to them, we certainly do have the ones we've won from history here, with us, today. Does Dawkins want us to phase out prayer, holiday traditions, and religiously inspired art?

Because those things aren't solely about God. For me and many people I know and love, prayer and traditions are almost entirely not about God. Prayer is about the self - it's partially to express awe, partly to reorganize life's priorities, partly to communicate to the self what he desires to see changed about his world. Both prayer and other traditions, like fasting, keeping kosher, and eating Jewish foods (goodness, I'm clearly hungry) also have another role, one which I find even more important.

When I read Torah, I know that thousands of years of Jews have read just about the same words across the world. I know my ancestors did. I would very much like to hope that my descendants will. These traditions are in a sense a method of communication throughout time - a way to commemorate our forebears and the future of our extended family. By definition, no other tradition, not even a masterfully poignant secular hymn in praise of nature and the nigh immortality of the gene can function the same way, because I know for a fact my great-grandparents never sang it, and my grandparents likely never will. I would love such a work, and I'm sure my parents would, too, but it doesn't function the same way religious tradition does. And unless a damn fine argument suggests that following the traditions we've chosen today is too harmful to be continued, we will continue them for the sake of previous and future generations, and for solidarity across the world.

To be perfectly honest, I think I may be putting a few words in Dawkins mouth that he may not actually espouse. Following a brief jaunt to his website, I see he considers pantheism and panentheism synonymous (I certainly don't), and while there were a few examples in The God Delusion of him chiding traditions (like his quiet disapproval of Edgardo Mortara's parents not converting to Catholicism to be reunited with him) I don't really get the feeling that he advocates the total disappearance of the cultural treasures that religion has produced.

What it comes down to, though, is that a personal God is extraordinarily unlikely phenomenon to exist, and the ways we humans have historically acted to appease it tells us fascinatingly frightening things about ourselves. The sooner we turn our backs from ignorance forever, the better.

Ben