psysal

So this almost definitely isn't a new kind of loop, except maybe to me and a few people that will read this. But I think it's cool! I'm sure somebody somewhere has thought of this, but in 15+ years of programming this technique has never occurred to me, and I've never seen it. It's legitimately neat-o!

Say You're Adding Particles...

A lazer beam strikes the air, crackling it and creating little bubbles of pure vacuum. EXCITING!

The lazer beam is going to extend from the space ship position Y to the top of the screen, 0. It's length, therefore, is L = |Y - 0|

Each frame of the lazer beam's update () cycle, we want to add some bubble particles. Each particle will be added at the lazer beam's X position and somewhere between the top of the screen and the space ship's position, Y.


P = new BubbleParticle ()
P.x = SpaceShip.x;
P.y = Math.random () * SpaceShip.y; // choose a point between 0..y


But How Many Particles?

Naievely, we could add 3 particles per frame, or we could add a particle every other frame. But there is a bit of a trick here, in that the beam is changing length each frame. So ideally, we'd like to add ParticleDensity * L new particles each frame.

That is, if the beam is longer, we should add more particles, in order to keep a uniform density relative to how long the beam is. If we always add the same number of particles per frame, a shorter beam will have more tightly clustered particles on it than a longer beam.


ParticleDensity = 1 / 100; // add 1 particle, per 100 pixels of lazer beam, per frame
AddBubbles = ParticleDensity * L; // L is the length of the lazer beam in pixels
for (i = 0; i < AddBubbles; ++i) AddBubble ();




The problem with this approach, is that if AddBubbles evaluates to less than 1, i.e. the lazer beam is less than 100 pixels tall, we won't add any particles at all when we should be adding maybe 1 particle per 2 or 3 frames in order to keep a consistent look.

We could ameleorate this by keeping a counter:


AddBubbles += ParticleDensity * L; // a running count, updated each frame
while (AddBubbles > 0) {
   AddBubble ();
   --AddBubbles;
}




This is my usual way of tackling this problem. Each frame, there might be a little bit "extra" left over, not enough to spawn a new particle (i.e., AddBubbles is < 1) but over three frames, let's say, it will add up to enough and we'll spawn one particle per 3 frames. Likewise, if we are supposed to spawn more than 1 particle per frame, that will be covered by this approach, too.

But Now... The P-Loop!

There is a much cooler way of making this work, that is stateless and awesome and easy, but in spite of the probably-hundreds of times I've solved this particular hitch, I hadn't seen before:


AddProb = ParticleDensity * L; // NOTE: this can be > 1! (that is the whole point)
while (Math.random () < AddProb) {
   AddBubble ();
   --AddProb;
}


MONEY

Imagine for a second that you made a database for great big evil Bank of America and part of it needed to transfer money between accounts. You write this code:


x = moneyAmount (10, 'USD') // x represent TEN U.S. DOLLARS
 
if (account1.hasAtLeast (x)) then
 
   account1.subtractAmount (x)
   // NO MANS LAND
   account2.addAmount (x)
else
 
   beep ()
end
 


Look at that weird line, "NO MANS LAND". What happens if the database CRASHES (a bug or a cosmic ray) on that line? The customer is out TEN U.S. DOLLARS! Dollars are serious business. And let's not comment on Bank of America's software writing abilities.


Fig 1. If this transaction fails at any point, we end up without our penny but ALSO WITHOUT DRACULA. Egads.

Atomic Cities

What you want is something that will either completely fail, or completely go through. That is called an atomic operation. You accomplish atomicity through something called transactions. There are different ways to do this depending on what system you are using, but generally it involves an "open transaction" command, followed by a bunch of operations (e.g., taking money out of some accounts, putting money in others) and then a "close transaction".

When you wrap something in a transaction this way, you give it atomicity. Real useful!


Fig 2. Transactions to the rescue! They can enclose any number of strange interactions, as is clearly demonstrated. With this, we shall always have our penny or our dracula.

Save Your Games

You know what I do not like? I do not like games that let you save everywhere. It shifts the thought process of the player away from engaging with the game world to managing their save states, making the whole thing more artificial.

I favour a zelda-style saving scheme, where basically your progess is always saved but there are certain sequences of tasks (traverse dungeon, defeat boss) that have to be done all at once.

You could almost view these sequences of tasks as gameplay transactions.

Save Your Save Games

Which brings us to my topic, finally. Suppose you have a bunch of gameplay variables, stored in a big array let's call it "Session". Session defines, for instance, how many coins the player has. When the player buys something, you give her an item and take some coins; the item is also stored in Session.

What often happens, however, is you create a certain sequence for the player. For instance: "enter this room, notice the statue of Goldair, it's magnetic field rips your sword away, and now you must do a complete boss battle with only bombs and your unicorn horn."

Here, we are taking the player's sword away, maybe a bit contrived but all things considered a pretty reasonable design choice (remember the cave of the Dark Elf from FF2?)

However, the player then has to beat the boss! What if the player does not beat the boss? What if... the player... DIES? Depending on what you do with Session after they die, they might ressurrect at the start of the dungeon, WITHOUT their sword. That is probably not what you want.

Session And Transactions

Here is what you do. You need to envision the entire boss sequence, starting with when the player notices the statue of Goldair, as a transaction. In your scripting code, you do this:


Session.lock ()
... code for noticin the statue of Goldair
... code for stealing the sword
... code for spawning the boss
... code for waiting until said boss is defeated
... code for returning the player's sword
Session.unlock ()
 


Session.lock should do two things:

1) It should save the player's current progress and write to disc. If they had 57 coins, the bronze armour, and so on, before the boss battle, they should respawn with those same items, even if some of them were gotten somewhere IN the cave.

2) It should set a flag that means the save game will not be written to disc. If some other code, somewhere (e.g., menu code, suspend event, whatever) hits Session.save, the game will actually NOT be saved.

Session.unlock should save the game to disc and unset the flag

There are variations on this as well, depending on the specifics of how your save system works (e.g., do you always allow the player to NOT save if they so choose, or do you just auto-save?)

Nice Game Designer

Using this methodology, you can simultaneously be nice and mean to the player, which is pretty much your whole job description as game designer.

You can be nice because you're giving the player a miniature space (the transaction) in which to freely experiment. They can use all their bombs and elixers and if they die, no biggie! They can re-try the boss battle with their same state.

You can be mean because it lets you have comparatively free reign to abuse the player temporarily. You can fairly make a boss that requires the player to drink elixers, because at the end of it they will have traded those elixers for defeating the boss. Elixers dranken don't count unless they win, but then after they win, they do. Perfect!

Other Save Systems

Older games use this kind of transactional system by only providing limited save points. This certainly frees you up as a designer but in my mind this is too punishing, especially for the modern age. Save anywhere doesn't have this problem, but goes too far for my liking, at least when it is in the sense of your whole state being saved.

Instead I prefer a save system based on transactions, where the player has to do certain things all at once but the save system is otherwise quite forgiving.

Note that you can also transaction-lock only SOME variables. For instance, one thing I often do is build transactions for only the player's position. So when they enter a dungeon, any money they collect IS auto-saved but their position is not saved until they return to the overworld somewhere; if they die they have to start back at the dungeon entrance (Zelda games introduced the idea of a dungeon lobby, for just this purpose, which I think is still somewhat underutilized today.)

You get the picture! Hopefully, framing certain design decisions in terms of transactions, both literally (e.g., in your Session class) and figuratively (e.g., in gameplay sequences) can be a helpful tool.

Part I: Thanksgiving

It was a dark and stormy night. Alison was on her way home to Maine, from her fancy New Hampshire private college and it's English Lit Major L'Escapades. The wiper blades went swooka-swooka across the window. Alison cursed: thanksgiving always had such shitty weather.

CRACKAA-BOOOM! Lightning struck close, temporarily blinding her, and she drove into the ditch. Luckily she was unharmed, but it looked like she'd be spending a night in that weird gothic castle she just spied...

Part II: Auto Updater

I'm almost ready to release an early version of a little game I called Bobsledder Spank Arena. I have some strange things planned for this, the least strange of them is adding tracks.

In Bobsledders, you race around a track and try to whack your opponent with a cricket bat. Typically you start off on opposite ends of the track, travelling in the same direction. You can reverse direction at will and there is no real right or wrong way to race around the track; you don't get any points at all for making laps, only a win by K.O.-ing your opponent. This setup is inspired by pursuit bike racing.

I'd like each track to be remarkable and interesting, so that may involve some extra code or other things added to them for visual effect, at least.

So I decided that what I really want is an auto-updater.

Part III: The Social Contract

Now consider this: you've written some software, let's say the new Web Browser. The user chooses to trust you and install this on their system. This Web Browser then dials into a website to automatically download updates. This is the same software that was originally installed, but improved. So it's natural that the update would happen at least semi-automatically, if not totally.

There is a social contract between the developer and the user-- they want this particular software installed on their system.

Now, if you were to download and install other software onto their computer, or install an upgrade that was vastly different, they might consider this social contract broken.

Part IV: The Hacker

Now imagine you make a game about Bobsledders that is quite popular, and there are a thousand or more players. Social contract in effect, you have an auto-updater set up so that you can easily push out improvements to the software. Of course, you have to be careful not to downgrade (e.g., break) everyone's installation, since they won't expect THAT, but it seems reasonable if you add new tracks or other bonus content that they will be glad to have it updated automatically.

Part V: Melphisto

Melphisto cackled loudly. His dirty T-shirt had a picture of an alligator eating a kitten, and the words MY KIND OF PURSE below it. Cracking his knuckles, he leaned back at his computer desk, in the top chamber of his giant gothic castle in Maine set against the same dark and stormy night from Part I.

Melphisto had managed to hack into the Bobsledders website, and uploaded a Bad Program. This would download everyone's Credit Card information and use it to purchase expensive marble from Italy for his castle.

You see, Melphisto had a dream. A dark dream. A dark dream that can only be dreamt by a video game nerd turned evil hacker.

His dream was to recreate Castlevania: Symphony of the Night. And this was going to cost MONEY.

Part VI: Rijn Belmont

Just like you shouldn't store passwords plaintext or weakly-hashed in your database, you shouldn't have an auto-updater that does not involve a public-key crypto system.

What you do as a responsible developer:

- Set up a local encrypted file store/container specifically for containing your private key.
- Put the corresponding public key IN THE UPDATER CLIENT ITSELF. These will never change, and the updater will ignore anything that isn't signed properly. The updater will never change these values (i.e., the updater won't update the updater.)
- When you are doing a new release, you need to sign each file that will be updated using your private key, so that it acceptable by everyone's updater.

This protects the people who trust you against these possibilities:

- Your website is hacked (happens all the time, man...)
- Your computer is stolen (less likely) or somehow hacked (since you will normally not even have the container with the keys on it mounted)

Of course, the down side is that is a lot of infrastructure for a simple updater. But this should be standard practice. Does FireFox do this? Does google chrome? Adobe? (at least adobe still ASKS if I want to update...) What about Windows Update? Debian? Ubuntu?

Millions of installations. One security breach. Mayhem.

Think about it.

Part VII: RSA

I actually have an implementation of RSA that I wrote some years ago. I did this for Venture the Void, because I wanted strong key generation. What it does is take your username that you use to access your acount, adds a salt to it, MD5s it, and then creates a signature. That is your "registration code".

This way, there is at least no way for somebody to write a code generator that could pair up usernames with registration codes. Side note, I think this might be a reasonable approach to DRM because it doesn't require an internet connection, yet any leaked codes can be traced back to an individual customer, meaning it should be less likely that they are leaked. But whatev'.

Of course only in my wildest imagination are people somehow wanting to pirate Venture the Void. **Sigh** But, it looks like I'll have another use for my RSA implementation, which is cool!

Finally, having implemented RSA, do you know the hardest part? LONG DIVISION. Yes, by far, the hardest part was doing long division. You can avoid this if you have a BigInt class of some kind (I did not) but my actual point here is maybe it would be a fun exercise to try and code a long division algorithm. It's really surprisingly convoluted.

Did you learn about domains in high school? A domain of a function is "what it is defined over"; i.e., a function f(x) may be defined for x between 0 and 1, but not outside that. Or for instance f(x) = 1/x is defined over (-inf...0) and (0...+inf) but not actually AT 0.

A range of a function on the other hand is what it might output, for instance f(x) = x * 2 defined only over 0..1 can only return values in the range 0..2, so it's range is 0..2.

Circle Groups

Think about the function sin(theta). You could define this over all real numbers, but because the function repeats itself you could also define it over [0..2pi).


Note: this is actually cos(theta), sorry!

If we think about this domain, we might realize that is most intuitive to think of it as a circle. In this case, sin(theta) would be the y coordinate of a point on this circle, and cos(theta) would be the x.

So now, let's think about the unit circle itself as a domain. Assuming the radius of the circle is r, and the point (1, 0) on this point is 0, then going counter clockwise we can trace out the distance from the starting point as theta, which will go from [0..2pi]. Once we reach 2pi, we are back at the start.

This is one (not very rigorous) way to define a particular group. A group is just a set of things (such as our domain above, a set of points) together with an operator, op(a, b) which has a domain and a range of the set of things. In our example, op(a, b) takes an angle a (in 0..2pi) and rotates it by b (also in 0..2pi) radians; it "adds" the two numbers, modulo (wrapping at) 2pi.

Collision

Suppose two bobsleds are travelling along the line -inf...inf, in the real numbers. Let's call bobsled A's position (in 1 dimension) A1, and bobsled B's position as B1; further, let's suppose that a moment ago bobsled A was at position A0, and bobsled B was at position B0. That is, in some small timeslice, bobsled A moved from A0 to A1, and B moved from B0 to B1.

Our task is to determine whether, during that recent timeslice, they would have run into each other. In fact, this is fairly simple to check: Suppose that they AREN'T colliding. Then either max(A0,A1) must be less than min(B0,B1), or min(A0,A1) must be greater than max(B0,B1). Otherwise, they are overlapping and so colliding. This is essentially a bounding box check in 1-D.

Collisions on the Circle Group

It is (to me) much less obvious how to detect this collision on the circle group. That is, suppose that our bobsleds are not moving along an infinite line, but on a circle. Their coordinates are still 1-D: each bobsled has only an A0 and A1, somewhere in between 0..2pi; they are not allowed a traditional 2-D "vector" representation.



The first complication is that it's not obvious, given only A0 and A1, which direction a bobsled is moving. In fact, it could be moving in either direction, as shown here:



But let's suppose, for a moment, that we can overcome this problem of direction. One "sensible" thing to do might be to check which of the two possible curve segments would be shorter; and indeed if T is small enough this will always work.

Even then, we are still left with the problem that the above inequality makes no sense. For instance, the number pi is greater than pi/2 on the real number line, but not on the unit circle. To see why this is so, think about starting at pi, and adding pi*3/2 to it, we will arrive at pi/2. I.e., we can start at either point, rotate counterclockwise, and end up at the other point. So there is no way to define which is smaller, at least not in a way that is consistent with our circle group.


Because you can add something to pi/2 to reach pi, and also add something to pi to reach pi/2, you can't define one as being greater than the other.

Naieve Approach

We might try and adapt our approach for the real number line by "unwrapping" the circle into a line segment. In some cases this will work without a problem. But what if our "unwrapping point" (i.e., where we take our scissors and cut the unit circle) cuts through one of the ranges in question, as well?

In this case we will have to do some additional checks. In practice, this will create ugly code with several conditionals. If this is the only solution we can immediately see, we might decide we don't have the energy to actually code it, and decide to write a blog post instead.


Now imagine TWO such line segments, possibly chopped in half, possibly overlapping, in all possible configurations. It's feasable to code that but not if you are lazy.

ACOS

A better solution would be to think about this problem natively; that is, try and work within a domain that is natural to it. This would mean treating theta as an angle. In fact, what we could do is find the midpoint of each angle A0->A1, B0->B1, and how far out they "sweep", and then check to see if there is overlap.



This might at first seem to be trivially similar to the collision solution on the real number line; it is not. The reason is that the collision solution above checks bounds, whereas here we are checking distances. One is the equivalent of an N-dimensional bounding box problem where N=1; this is rather the equivalent of checking whether two N-spheres collide.

In the first case, we are doing an ordering comparison. Is this greater than or less than that. But in the second case, we are computing distance between two points, which is not dependant on something being ordered. Realize that absolute value is the distance function on 1-D, just like sign(x) is the "normal vector" of x in 1-D.

There is one remaining detail, which is to compute the distance between two points on the unit circle. In general, we could say they have two different distances, depending on which way you go (A to B will be a different length than B to A.) In our case though it is pretty obvious that we want to the smaller of the two distances, because if the larger one collides then the smaller one will as well.

Native Representation?

Because our CPU does not have a native representation for these kind of values (it might be interesting to think what a native representation of this would look like, in binary!) we will at some point have to convert back to the real number line. However, it's a lot simpler task to convert just the resulting midpoints to the real number line than it would be to convert the entire ranges, as in our first "naieve" approach.

Circles Are Confusion

Hopefully this blog was interesting to read. If you are looking for a better understanding of some of the mathematics here, I would recommend reading about Group Theory. (wikipedia)

Read about Group Theory on Wikipedia.

TWEETER

Finally please let me share a funny twitter exchange (I have ordered it chronologically). Bask in my multi-layered puns:


Srsly, I'm on fire tonite!

Star Wars and Restraint
star wars, film techniques, wind waker, cutscenes

Today I am working on the final denoument cutscenes in The Real Texas.

Coincidentally I have been watching the amazing fan-made documentaries on the original Star Wars trilogy (Star Wars Begins, Building Empire and Returning to Jedi by Jambe Davdar.)

The Original Triogy, Ebert Was Right

Seeing how the Original Trilogy was put together in more detail has given me a lot more appreciation of film techniques. Last year Ebert said that games are not art, and the gist of his argument is that games cannot manipulate scenes as finely as films can.

Suicide-inducingly boring debate aside, the second part of this seems true to me. Each scene in A New Hope is absolutely filled with detail, carefully scripted. In film, the camera never wanders beyond very tightly proscribed bounds.

The Trash Compactor Scene

Consider the large metal bar in the trash compactor scene. Han picks this up and attempts to use it to brace the walls from closing in. It is very effective to see the bar bending: it shows us how powerful the compator really is, outlines their desperation, and creates a sense of panic as we can relate to it in a physical sense (we can imagine ourselves trying something similar, and understand how hard it might be to properly position it.)

In a game, the requirements for this simple prop are much deeper. If that bar braces the trash compactor, it should brace other things. We will need a physics engine that can somehow handle malleability and ductility. We have the ugly choice of letting the player carry it with them if they choose, and then making sure it can't break gameplay or cause strange glitches in other scenes, or of forcing them to leave it behind.

But it's actually worse than this: even if we implement such a prop, we can't force the player to use it, anyhow!

Restraint and Creativity

When I watch these documentaries, it creates in me a burning desire to imitate. This is by now a familiar feeling for me, maybe it is for you too. What I have come to believe is that this particular burning desire is the harbinger of creative suicide.

To create, we need to take ourselves out of this particular kind of inspiration to imitate, no matter how strong it is. In the case of making games, we need to take a deep breath when we watch great movies.

If we attempt for the same kind of tightly-controlled and yet varied effects that film makers have at their disposal, we will find ourselves creating a badly-scripted, weakly-interactive non-movie non-games.

Simplicity

Instead of trying to co-opt this power of tightly-framed scenes, let's examine our own constraints.

First, the player is not an actor. In fact, the player is the only element we explicitly do not direct. This is a difficult constraint to stick to when we are trying to imitate film effects. It's very tempting to have the player character stop and walk to a certain place, or perform a certain action at an opportune time, but we should stop and look for another solution.

Second, in place of varied effects put interesting rules. Rather than constructing elaborate scenes requiring a certain set of actions, build several flexible props and then experiment.

Recently I added a certain weapon to The Real Texas with a long reload. The player always has control over whether they want to reload, but they can't change that it takes a lot of time to get ready for another shot. It's a simple prop that in no way violates these rules, but it creates a lot of dramatic tension. Observing this, I put in another constraint (again, on the prop, not the player) which would highlight this tension (a minor spoiler, so I won't tell.)

Some Wind Waker Critique

I've also been playing through Wind Waker. I enjoy this game very much, but I have some funny criticisms. Basically, I think the game relies on too many different props that ultimately don't have very many uses. Most items can be used as a weapon in addition to one other effect. There is even significant overlap-- for instance the grappling hook ought to make the hookshot a nonentity.

I would have rather played a game with sword, shield, grappling hook, and maybe one other weapon, but which all interacted strongly with all props (e.g., grapple anything). Instead, it feels a bit scripted at times, because I know in many situations that I must use item X (say, the hookshot) because no other item will work.

   
Damn what a great game. However... why do we need both Grappling Hook and Hookshot?

Finally, It's Easier

Last thought before I wrap this up. It's easier to design games this way, because they are more natural constraints for our medium. It's fundamentally easier to work with just a few props and make them play with each other in interesting ways, than to relentlessly draw lines arond what the player can and cannot do.

When I find it hard to adhere to this, I take a deep breath. It just isn't film.