Friday, December 28, 2007

english muffin and egg

Serves one lazy bachelor, takes about 5 minutes, an egg, an english muffin, cheese and salsa.

  • Split an english muffin in half and start it toasting
  • While you wait, crack an egg into a bowl, and mix in roughly the same amount of salsa
  • Melt a little butter (for frying) and optionally cheese in a frying pan - low/medium heat on my range. If it starts sizzling before you're ready, turn the heat off or down.
  • When the muffins halves are done toasting, soak them in the egg batter, then drop them in the pan. The butter and cheese in the pan should be sizzling and bubbly by now.
  • Flip the soaked halves every few minutes. When they've browned a little on each side, pour in the leftover salsa-egg batter beside them in the pan - it will quickly fry into a sort of sloppy omelette. Flip it over once it's solid, let the other side cook, then take everything out of the pan together. I salt mine after I take it out - it's savory, not french toast.

Variations: If you don't have or want salsa, dilute the egg batter with something (milk worked for me) so it soaks into the english muffin better, and fries differently(?). Don't add spices to the egg mixture, because they'll just clump together in the liquid - put spices directly into the frying pan near the end (or else they'll burn in the hot oil while everything's frying). I used cayenne and ground ancho peppers.

Wednesday, September 19, 2007

hidden state vs. nondeterminism in games

In certain types of games like chess, go, and checkers, there's a clear definition of the game's complexity (wikipedia entry). It's a measure of the branchiness and depth of the choices-tree that the players are building and exploring. In games that aren't combinatorial (ie. without a completely-known game state by all players), does it make sense to talk about complexity in the same sense? With either nondeterminism or hidden state, what happens to the players' mental model of the game tree?

Hidden Information
It makes planning harder, because you need to account for all the possible outcomes that depend on things you don't know: imagine deterministic poker with a sorted deck. Hidden information only makes planning harder to a limit, because if you know nothing at all then you can't plan at all. It seems like having a fraction of your game state hidden maximizes depth (or at least the difficulty of planning). Why don't more classical games have hidden state? Is it because hiding cards is easy, but hiding pieces on a board is difficult? It's hard to think of how, physically, you'd play checkers-with-secrets with someone... without easy cheating, anyway.

Alternately, imagine known-state poker, with face-up cards only. Hidden information is slightly intertwined with nondeterminism, though, because in deterministic poker there are no secrets to keep - everyone knows what cards you have, even if they're face down. To have secrets in a deterministic game, you need to make your choices secret (like fog of war in a deterministic RTS).

There are lots of games that depend on randomness for a similar effect on planning to hidden state, ie. any game where you draw shuffled cards or roll dice. It makes planning harder, because you have to think of multiple potential outcomes independent of each of your decisions. Hidden information is exploitable by the player who's keeping the secret, and adds lots of meta-game depth like bluffing and information management. I'm really interested in games where information management plays a key role, like in RTS games with fog-of-war, where visibility or radar coverage comes at a cost, and so does keeping secrets ("I could defend my main base if I use my secret cache of tanks, but if he know about my secret tank-producing base, he'd attack it from the air..."). It's like betting strategies in poker - they matter mostly because they reveal information, and the tradeoff is money, you're paying for information.

Complexity in Design
Why does complexity matter to us? If you did make chess-with-secrets, would it be a deeper game? Even if it was theoretically harder to plan your moves, chess doesn't need more planning complexity - it already maxes out our abilities. Only trivially shallow games need to be given more planning complexity. Nobody plays Go on an enormous board, even though it would be incredibly deeper. (Even increasing a 19x19 board to 21x21 would have a huge impact on complexity, but nobody would say it makes the game more fun).

Even without caring about planning complexity, nondeterminism and hidden states add a lot to a game. The boundary between determinism and nondeterminism starts to get fuzzier with videogames, where you have analog input and reaction times matter... it only makes sense to talk about it with respect to the actual decisions the player makes about the game, not the nuts-and-bolts physical input and output. It's at this level where a little bit of planning complexity is nice - deciding whether to silently walk or loudly run in counterstrike, whether to hide behind a wall in bf2142 or have a better line of sight on your enemies, or deciding when to reveal your strategies in an RTS or take pains to keep secrets. I think in almost any case in multiplayer games where you can give the choices to the other players (instead of making it random), you should. Instead of playing their own private slot machines in parallel, players enjoy dealing with each others' choices. It adds a social dimension to dealing with unpredictable outcomes where people can scheme and plot, and that adds metagame feedback where people need to anticipate and predict others' strategies.

Even without multiple players, the big thing about randomness is training players about rewards, with the Diablo/WoW style loot drops and Skinner-box feedback. Everyone claims to hate it, but its been proven to be effective (lucrative ;) design. Randomness softens the impact of losses on the ego, and gives the occasional reward to bad players to keep them playing - we're suckers for it. Giving people the chance to gamble their valuable resources on longshots lights up some primitive part of our brains - it's innately fun, even if it's only slightly related to the rest of the game.

Saturday, June 30, 2007


Lots of games have alternate vision modes (nightvision, heat-vision), or use rumble unrealistically, for the sake of gameplay and tactile feedback. Even though these sensory outputs from the game aren't physically accurate, they map the player's senses directly onto the fiction of the game world - nightvision is still vision, tactile sensations rumble.

If you can give information through a different sensory channel, it opens up a lot of possibilities. Far Cry instincts showed smell as a particle trail, which you could use to track people. XIII showed position audio cues rendered in 3d with a "tap tap tap" comics-style cutout showing the location of footsteps (something I wish I have in Thief when I constantly look left and right to hear enemy footsteps switch L/R channels on my headphones). In both of these games, it ends up more like a UI indicator than an actual sense - the way the information's mapped from one sense to another is shallow.

Ideally a good mapping of one sense to another would give the player a kind of synesthesia (wiki). Rez is the closest I can think of to synesthetic, and although the gameplay is terrible, it's a unique experience to play Rez. It feels like guitar hero or DDR, where things on the screen (and your control inputs to the game) are synchronized to the music. Adding that sort of wackiness to a game should be pretty easy for us - grab a random stream of data from somewhere in your game (audio, player input, some important state from the game), and hook it up to a different sort of arbitrary output instead of showing it as a bar on the hud. Additionally, it's awesome if we can make sensory output from the game matter in ways it normally doesn't (eg. the "find the rumble direction" minigame, or the last Def Jam's crazy beat-matched fighting system). Instead of just being cosmetic output, make it part of the feedback loop the player needs to play the game.

Internalization of the laws of the world make you understand the game at a deep level - the character physics feel kinesthetic and "right", the tactics are all well-known to you and enemies so they turn into gambits and counter-moves, and you've learned to read the game's state from its output. Every little sensory channel we can feed the player helps.

What's even more interesting to me is giving the player senses he doesn't really have. Some new senses can be trivial for us and the player. "New senses" doesn't need to be difficult to implement or mentally alien (like trying to model smell diffusion, or vibration sensitivity depending on the ground's hardness, or echolocation bouncing off walls).

It would be trivial to make the player into a mindreader - make a prettier version of your AI's debug displays. The player could then see what the NPCs are aware of, and what they're about to do. If it had a cost in the game (eg. it's only available when the enemy's not hostile, or when the moon's full and visible), there's automatic gameplay. Preempt their feeble plans and feel like a mastermind.

Prescience is a little trickier than mindreading - you need fast prediction [oracle billiards] for objects (similar to what you already need for network play), and some rendering tricks to overlay that information on what's currently happening. (Does it make sense in turnbased games? I could see it working in a game like xcom, but it starts to overlap with the mindreading above).

A cheesy way to do it would be to render every moving object again a second or two predicted into the future. In an FPS this isn't useful in multiplayer (because of how players move, and how skilled players already predict simple movement really well), but against AI opponents (since the game knows what they'll do) and for predicting physics objects it could get pretty psychedelic.

Here's the cheesy future effect - rendering the object a few times over where we predict it's going. Planet orbits are easy to predict :) I rendered the 'futureness' in redder and alpha'd out colors, so it's clear which objects are predictions and which one is real. The future ones are also bigger, I was hoping to make it look like a spreading probability function.

Here's a continuous version, where the object gets stretched out towards its future position - it's kind of like the Donnie Darko spear-object extruded through time. You can see where the Earth is going to be for the next 1/4 orbit.

Wednesday, June 27, 2007

shot assistance

Remember that mortar-assistance thing in Tribes, where a friend could laser-spot a target, and you'd get a hud indicator of where to shoot your mortar (two possible heights) to hit the target?

Here's a landscape. The view is looking up this little hill. (Click for fullsizes).

Here's a landscape warped to show what your mortar would hit - you can see over to the far side of the hill.

Here's the same shot with a lower barrel velocity - the terrain lifts up sooner, because the mortars fall shorter. If you look upwards at 45 degrees (which maximizes your range), the middle of the screen is on the further spot you could hit. The terrain warping is a parabola of how much your shot will fall at each distance.

If you tilt the camera up further, the terrain starts stretching back down - your mortars lob so high they land closer to you than they would at 45 degrees. Look at the grey pattern on the terrain to see what I'm talking about.

I think to get the effect technically correct, I should render the terrain twice, with two different warpings. Just like how tribes would show two points on the hud, we'd want to draw a point in the world at two points in viewspace. I can't figure out what the other warping is. If you look straight up, you should see yourself upside down above you, and the whole world should be mirrored vertically around the circle (at 45 degrees) that defines your maximum range.

A neat side effect is any mortars enroute to hit you will render as fixed in viewspace (unless they're travelling at a different barrel velocity than yours). If you had a game of mortars vs. lasers, there would be cases where visibility only goes one-way in each direction betwee(eg. the mortar dude you can't see can see you over the hill, but he can't see you when you're under an overhang, hitting him with your laser). A straight-line laser would render as curving upwards to the mortar player.

Rendermonkey :D

Tuesday, June 26, 2007


Noi Albinoi is a great movie. I love the sound of icelandic.

Italo Calvino's "Invisible Cities" is a great book, halfway between meaningless and deep.

Monday, May 28, 2007


Ants raise catepillars, and grow antibiotics to control mold infestations(!) in their agricultural farms(!). I will never get tired of seeing complex behavior without fat brains. And they haven't changed since Gondwanaland.

Bonus link: robot movie.

optimization challenge

Here are today's unsharable links: a collection of links on optimization, and an optimization challenge.

I'm working on my solution to the challenge. The previous challenge (#6) depended on assembly - hopefully my lack of ASM skills won't be a problem, #7 seems to be algorithm-constrainted. I wish I had visual assist at home, I feel crippled without it. Sadly, paying for a full version of VS2005 just for VA compatability (on top of the price of VA) seems like overkill for hobby programming (I'm currently using VS express for free).

First pass: 15x speedup from the brute-force "you can do better than this" reference implementation. I was hoping to do something like sweep and prune, giving each point a 'radius' of the minimum pair distance I've seen so far, but it didn't reject *any* points, because the distance between points on the other axes is always greater than the minimum on the sorted axis, and I don't have real AABBs for the points. It seems like it should work, though, or something else very similar to it.

Update: 45x faster, with sweep and prune on one axis. You don't need to reject points - just reduce the number of point-point pairs that need testing. Each is tested against ~20 others.

Update 2: 125x faster by not fully sorting the points - just partition down to 32ish-sized groups, and compare against all your neighbors inside those (since you'd be looking at about that many neighbors anyway) - they don't need to be sorted.

Messy update 3: I don't think I should on all 3 axes... sorting on 1 axis then testing the overlapping pairs on only that axis is faster than the time it takes just to sort on 2 axes. [Then why is it worth doing 3-axis SAP in physics?] I think I could probably be clever and do recursive partitions on alternating axes, so it would be as cheap as a single sort but with better partitioning (you're more likely to see close neighbors if it arranged into shrinking neighborhoods of X, Y, Z, X, Y, Z... instead of X, X, X, X...).

It would be kind of like a KD tree, I guess, where the points near the boundaries will be a hassle (like my current solution, only worse), but everything inside each partition is guaranteed to fall inside a small range of X, Y, and Z values (sorting on one of the axes to reject most neighbors, like the 'first pass' solution). The alternating-axis partition will have most of the benefit of 3 sorts but only costs as much as 1. A rough version of the KD tree sorting seems to be going about twice as slowly, and I don't think I'll bother figuring it out tonight, it's late and it since it looks like contest #7 was supposed to be finished months ago - it looks abandoned by Hejl, the dude who ran it.

Unexplored solution: put everything in a hashtable, hashing 3d space to a list of points.

Update 4: Results: I would have come in 7th (aka 3rd last :) with the solution in update 2. Update 3's unimplemented idea was close to the winning solution - "Essentially, it's a quicksort based algorithm that's modified to traverse an implicit kd-tree".

Sunday, May 27, 2007

Google reader is almost perfect

Do RSS feeds typically only show the most recent posts? I want to share other people's old blog posts in google reader, but they often don't show up in the RSS feeds. I wish google reader would let me share links that aren't part of RSS feeds - it's the only thing that bothers me. And since I'm not on the Reader development team, I can assume it would be really easy to implement :)