solving pushpull puzzles

There's a little puzzle flash game called pushpull. Try playing a game of it to see what it's about - it's pretty straightforward.

So, imagine the game as this 3x3 grid of cells:
a b c
d e f
g h i

Here is how the different cells relate to each other. The number of times you need to press piece 'a' depends on the number of times you press piece 'b' and 'd', and it also depends on the initial state of 'a' as well. The relationship between them is that at the end of the game, you must have toggled the square's parity a number of times such that it's in the down state.

We can represent this by considering the variables a through i to be binary variables that count the number of times you click each grid cell (binary variables because adding 2 clicks to any cell is idempotent, so we can remove them), and also consider the initial states s[a] through s[i] to be binary variables - we could say that a, b, d, and s[a] must have an even parity all together, since after each of them is applied, the cell must be 'down', or 0.

We can represent these relationships with these equations, where the things on a line have their parity xor'ed:
0 = a b d s[a]
0 = b a e c s[b]
0 = c b f s[c]
0 = d a e g s[d]
0 = e d b f h s[e]
0 = f c e i s[f]
0 = g d h s[g]
0 = h g e i s[h]
0 = i h f s[i]

Those equations can be represented as a matrix A:
1 1 0 1 0 0 0 0 0
1 1 1 0 1 0 0 0 0
0 1 1 0 0 1 0 0 0
A= 1 0 0 1 1 0 1 0 0
0 1 0 1 1 1 0 1 0
0 0 1 0 1 1 0 0 1
0 0 0 1 0 0 1 1 0
0 0 0 0 1 0 1 1 1
0 0 0 0 0 1 0 1 1

Where if we take the vector s of the initial game state, and the vector x of how many times you click each cell (variables a-g in the equations above), then the solution to the game is Ax + s = 0. This is saying the same thing as the equations above - if we add together the initial state, along with each cell's influencing cells, it has to equal the zero vector because the game ends with a flat board.

Since I couldn't find any programs to do mod-2 matrix solving, it took some (python-assisted) work to solve for the pseudoinverse of the matrix A. Then modulo-2, that ends up being:
1 0 1 0 0 1 1 1 0
0 0 0 0 1 0 1 1 1
1 0 1 1 0 0 0 1 1
A-1= 0 0 1 0 1 1 0 0 1
0 1 0 1 1 1 0 1 0
1 0 0 1 1 0 1 0 0
1 1 0 0 0 1 1 0 1
1 1 1 0 1 0 0 0 0
0 1 1 1 0 0 1 0 1

Testing this matrix: if the input is [0 1 1 1 1 0 1 1 0] (which is a game I just got), multiplying by the "inverse" gives [3 3 3 2 4 3 2 3 4]. Since only the parity of number of clicks matters, we can take that vector mod 2, which is [1 1 1 0 0 1 0 1 0] - and clicking on those boxes yields a flat board.

dumb little robots!

Some little arduino robots I've made:

Pattern-copying clapping sockmonkey:


Automatic plant waterer:


The blimpbot was too heavy to fly :(

making puzzles by solving puzzles

Constraint Satisfaction Problems

Constraint satisfaction is a useful and very general approach to solving a wide class of puzzle-y problems. If you can phrase a kind of problem as "I need to choose some values (from finite sets) for a bunch of variables, but there are constraints that rule out some combinations of values", that kind of puzzle can probably be solved with constraint satisfaction.

Example puzzles would be things like sudoku (as a constraint problem: it's assigning a decimal digit value to each of 81 variables, subject to the row/column/3x3 uniqueness constraints), crosswords (assign a letter to all the boxes, such that all contiguous boxes spell out words in the dictionary), and the classic "dinner party seating problems" (eg. there are 8 seats at a round table and 8 guests. pick seats for everyone such that Alex can't sit next to Bob, Bob must sit next to either Cathy or Dave, Dave must sit next to Alex but not Edgar, etc). 

Possible Solutions

When there are a lot of variables to choose, it's intractable to exhaustively test every combination of values to find a solution, because there's an exponential number of combinations. Imagine the tree of choices we could potentially make, where at each depth D of the tree, when we've picked the first V values from a domain D, there will be |D|^V branches in the tree, which grows too quickly for brute-force searching.

Constraints as Pruning

However, we don't need to search through most of the tree, because once a constraint makes a tree node invalid, we don't need to explore any of its children. So applying constraints prunes off whole branches of the tree of value assignments*, which eliminates an exponential number of nodes with each pruning, which makes it feasible to explore the tree.

* That is, if you don't have to make many choices for them to apply. If the constraint was "the MD5 hash of your values is 0", you can't get out of doing the exhaustive work.

Recursive Backtracking

The straightforward way to recursively guess-and-test your way to a solution is to randomly pick a value, apply any constraints using that value (which rules out values for other variables), and bailing out if we ever violate a constraint. Eg. something like:

def solve(puzzle):

if any variable has no potential values: return False

if all variables have only one value: return puzzle
pick an undecided var (ideally the one with the fewest remaining values)

for each potential value in var (ideally in most constraints order):

set var to value

apply all constraints

found = solve(puzzle)

if found: return found

  return False

To be clever, you can keep track of the set of potential values for each variable, so that when a constraint rules out a value, you can remove it from the set. Furthermore, constraints can propagate transitively from variable to variable - that is, once you've limited the possible values of one variable, that can in turn limit other variables.

When a constraint is violated by making a bad random choice, then applying the constraint makes one of the set of potential values empty, which makes us fail and undo (backtrack) to the previous guess. There's a great writeup of this technique by Peter Norvig.

Find All Solutions

Some types of puzzle are only valid if they have exactly one solution (Sudoku is an example of this). How could we distinguish between under-constrained sudoku puzzles and valid ones? Our solver stops once it hits the first valid solution. What if it didn't and kept going? We could pretty easily modify our solver into a recursive generator function, ie one that returns all solutions:

def solve_all(puzzle):

if any variable has no potential values:
  return # nothing to yield

if all variables have only one value: 

yield puzzle # the one solution

return

for all undecided vars:

found_value = False

for each potential value in var:

set var to value (in a local copy of puzzle)

apply all constraints

for y in solve_all(puzzle_copy): # assign all other vars

found_value = True

yield y

# couldn't assign any value for v, this branch is dead

if not found_value:

return

So that eg. if we gave it this underconstrained puzzle to solve:
   |  6|
 59|   |  8
2  |  8|
-----------
 45|   |
  3|   |
  6|  3| 54
-----------
   |325|  6
   |   |
   |   |

It would find many solutions, starting with these two (note the last two rows are swapped).
178|236|495
359|147|268
264|598|137
-----------
745|962|381
813|754|629
926|813|754
-----------
481|325|976
592|671|843
637|489|512


178|236|495
359|147|268
264|598|137
-----------
745|962|381
813|754|629
926|813|754
-----------
481|325|976
637|489|512
592|671|843

To make the puzzle a valid one (with only a single solution), we'd have to add more digits to the puzzle. We can pick an arbitrary blank space to reveal a number. In a sense, we can use the solver to help turn incomplete puzzles (not enough information to be valid) into every valid puzzle that it could be.

So if our fancy solver can search for all solutions, what if we gave it the empty 9x9 sudoku grid? Here's the first and the ten thousandth solution (of a huge number!) of solutions to the empty sudoku board, in sorted order (trying the numbers in order, from left to right). In a sense, our solver is now a generator! If we left it running, it would eventually print every solved valid sudoku puzzle.
#1

123|456|789
457|891|236
689|237|145
-----------
214|365|897
375|982|461
896|174|352
-----------
531|628|974
748|519|623
962|743|518

#10,000
123|456|789
457|891|236
689|237|145
-----------
214|365|897
375|982|461
896|174|352
-----------
538|729|614
942|618|573
761|543|928

Too much Information

Of course, although those puzzles are now valid, they're also already solved, which makes them bad puzzles. Ideally, our generator would show only the minimal number of clues to a valid puzzle. Since our solver knows when a puzzle is solved, though, we already know when we've added enough information!

A Backtracking Generator

To turn a simple solver into a simple generator, instead of guessing at assigning variables, we actually assign them, and keep doing that until the puzzle is (uniquely) solvable. Like the solver, it has to backtrack if it hits a dead end (if we pick incompatible values). We can avoid giving away our completed solution by maintaining two copies of the puzzle - one that's minimal (ie. the puzzle we're going to return), and the other that's fully constrained (ie. what can be deduced from the minimal one without any guessing), and we're done when the constrained one is solved.

def generate(minimal, constrained):
if failed(constrained): return False
if solved(constrained): return minimal

while 1:
pick a random variable
pick a random value from the variable's set
assign the value for minimal

assign the value for constrained
run the constraints on constrained
if the constraints fail: 
then that random value isn't valid,
so remove it from the set of values Run the constraints again. If they fail (meaning there are now no valid values for that variable):
return False

if it succeeds, return generate(minimal, constrained)

The reason we have to remove invalid values (instead of just trying another number) is to stop us from getting stuck in an infinite loop - we need to be able to backtrack multiple times to back out of a dead end that started with a grandparent.

But this generates valid mostly-empty puzzles (and the solution at the same time). Sweet!

Eg. this guy:
 38| 5 |  4
   |8  |65
9 7|   |
-----------
 6 |48 |
 71|  6|3
   | 7 |
-----------
 4 |367|8 5
   |  1|79
 26|   |

Difficulty

We could generate harder puzzles by picking variables and values via some heuristics, rather than randomly (just like the ones that improve solvers, I like the similarity). we could also do a better job of noticing when we're done, by counting whether there are 0, 1, or multiple solutions to a puzzle, ie.

def count_solutions(p):
count = 0
for y in yieldall(p):
count = count + 1
if count == 2: break
return count

Then starting the generator with this instead:
def generate(minimal, constrained):
sols = count_solutions(constrained)
if sols is 0: return False
if sols is 1: return minimal

To get the really minimal puzzles (they're probably still not difficult, though!). 

avoiding collisions with pathfinding

We split bot navigation into two layers - pathfinding is run for each bot independently, which yields a path (which will persist for a long time), and we hand off that path to a more reactive system (eg. a steering system that uses velocity obstacles or something) which is responsible for dealing with surprises like other bots getting in the way. Even thought steering works well at preventing collisions between bots, it has to use the path it's given, and it can't avoid chokepoints that force it through other bots - paths that end up slowing everyone down and making them look dumb. 

Here's an example in my toy pathfinder: white squares are traversable, dark grey are blocked, and the colored plus signs are the paths of 4 different bots (they're taking paths that heavily overlap each other). All the paths go through the chokepoint in the middle. The purple bot could have easily avoided the traffic jam by going south a bit, but instead he's taking a (slower!) path that forces him to deal with everyone else.


If we increase the path cost of chokepoints by predicting heavily contested positions, A* will route us around those traffic jams. It's easy to predict where other bots will be - just look at their paths. To keep things fast, you can implement this with a per-position count of the number of paths that use each position (treated like a refcount) - that way, the cost of finding a path is independent of the number of other paths.

Here's my toy implementation: although the naive shortest path for all 4 bots would go through the same chokepoint, the bots now take paths that avoid each other. (their 'avoidance radius' falls off at 3 squares, so they're giving each other a wide berth). If the cost were higher, they'd worker harder to avoid each other - but some path intersection is unavoidable here.


This sort of system could be an improvement for style reasons, too - imagine a swat team spreading out to clear an apartment - although maybe they're ultimately going to the same place, you want them to explore as much as they can (kind of like a cheapo version of influence maps).

One complication is that paths become order dependent. The first bot to path in an area ignores everyone else, the second bot only ignores the first, etc. Finding truly 'correct' paths in this case would need to be done simultaneously for everyone (but I don't see how that would even work! Any ideas?).

A less tricky implementation would be to only approximately track positions - by keeping a per-area refcount (if your game spaces are hierarchically partitioned), or only attaching the cost to doorways, or only tracking bend points on the path rather than every position, etc.

A more tricky version would be time-indexed - meaning you care about the specific *time* that each bot will arrive in each position. This makes things more correct - a bot would be happy walking in single-file behind other bots. However, time-indexing has a few caveats:

• makes the bookkeeping more complicated, and makes the runtime slower (slightly)
• requires your pathfinding system to accurately predict the movement speed of a bot

I tried to implement time-indexing, but it introduced weird kinks in returned paths, where paths will intentionally waste time (running in a useless circle) to avoid a collision in the future (which makes sense in terms of pathfinding, but looks like a bug). I tried to fix this by adding a low-cost 'wait in place' action that bots can do (in addition to moving in their 8 directions), but that ended up being a giant can of worms - because it means A* needs to re-visit positions that are already in the closed set with a lower cost.


Maybe a simpler alternative to time-indexing would be to tag each position with a velocity - that way you'd get more cooperative groups without all the complexity of real time-indexing. Ie. you're saying "you can use this door without trouble if you're going north".

Here's a paper that does something kind of similar that got me thinking about all this: I think their videos show really impressive group dynamics, and I think a big part of what makes it look good is the planned-local-avoidance thing (more than the footstep planning animation synthesis, although that's pretty cool too!).

exploring more dimensions with A*

When you're running A*, you're searching over the edges and vertices of a graph, where the graph's vertices represent some kind of state, and the edges between vertices are the state changes. In pathfinding, the states are positions, and edges are the smallest movements you can do to get between neighboring positions, like "move +X", or "move +Z".
State = {x, z}
State Transitions = { +x, -x, +z, -z }

You end up with a resulting path like this: Grey tiles are blocked, white are unblocked, and red shows the resulting path found by a pretty vanilla A*, going from upper right to lower left.
Blue shows the nodes we visited during the search.


This can be kind of crappy for games where you want to model more complex mechanics of motion: characters in games can't really just "move +Z". For an example, imagine a car - they can take several seconds to accelerate up to full speed, or to make a 90 degree turn. If we build a shortest-length path for the car to follow, he'll have to drive really slowly to make all the tiny fiddly sharp turns (or in the worst case, be completely unable to make them at all). This might be the shortest distance, but it's not the shortest duration path. And even in games with just human characters (which I work on), you can sometimes spot guys running at full speed trying to follow a shortest-distance path, which makes them look robotic. It can also cause bugs if we try to satisfy physical constraints about limited acceleration or turn speeds, and the path violates those contraints (eg. making 90 degree turns around corners).

If we can more accurately model the state space, we'll get a more accurate shortest-duration path:
State = { x,  z, vel_x, vel_z }
State Transitions = { +vel_x, -vel_x, +vel_z, -vel_z }  // the driver only controls acceleration, not position
Then if we also have an appropriate interface for A* to know about this more complex state (so get_neighbors(state) needs to return the result of acceleration in each direction, and heuristic_cost(state) takes velocity and acceleration into account to derive a minimum arrival time), we get something like this instead:


For this image, our dude can move at a top speed of 10 tiles/sec, but can only accelerate at 1 tile/sec^2 (which is a roughly car-ish ratio of top speed to acceleration).
What's cool about this is:
- it's indeed a shorter-duration path even though it's longer
- the driver avoids navigating around all the little obstacles
- you can see the faster path "swings wide" around that corner to be able to go faster
- you can see the explored region (in blue) finds the few quick paths through the obstacles

Neat! It makes me want to make an all-terrain driving obstacle course game. I think to be really accurate, you'd want to feed something close to the game's real rules/simulation into A* - so that it could explore the accurate consequences of its choices. In that case, the inputs for a car would probably be something like:
State Transitions = { rotate steering left, rotate steering right, more gas, less gas (or brake) }
(or whatever the inputs to a car are for your AIs).

The big downside, of course, is the cost of computing this stuff, since we're exploring in more dimensions. For the blue region shown on the map, in the worst case there can be up to 200 "visited" nodes overlapped on each tile position (because of how I quantized my velocity - I don't know how you'd do this with a more analog velocity space). Practically it wouldn't be so bad, but in my test code, paths were about 20x more expensive to find - and certain clever optimizations to A* (like jump point search) don't work anymore.

My pipedream, though is to write a bot for "quake done quick" that has the player's inputs as the state space:
State Transitions = { w, a, s, d, jump, aim delta, fire, switch weapons }
But that sounds impossibly slow, right? If that bot could discover rocket jumping, I'd be ecstatic.

Spelunky

Spelunky is difficult, but not in the style of technical platformers (VVVVVV or N+ or whatever). It’s difficult in the same way roguelikes are – lots of things will kill you, so you have to be attentive, and learn how the game mechanics can combine in unexpected ways. The levels are procedural, so there are no hand-crafted puzzles to solve. I feel like my deaths are always my fault, which is good in a game with permadeath and a life expectancy of a few minutes.

I can only play for about an hour at a time, though – even though I’m still enjoying playing, I can’t stay focused and cautious for that long :( 

Get it at http://spelunkyworld.com/

graph optimization

Is there a well-known method to simplify a nav graph? From what I've seen most people have a nav mesh (made of triangles), not a graph (made of edges). But assume you have a graph - is there a well-known method to remove the edges that wouldn't significantly shorten the paths found on the graph? I wonder if this is a well-known problem (I don't know what to search for on google - "graph simplification" turns up a bunch of weird topology papers).

I wrote up a little solution for it that I think works pretty well. Here's my sweet-ass visualization: http://i.imgur.com/XMOaM.png
It's a graph made of random edges in 3d. Black lines were rejected from the original graph, white lines were kept in the simplified graph.

The method is to keep candidate edges from the original graph only when they're shorter than some fraction of the shortest existing path between those vertices. Like building a minimum spanning tree, visit the candidates in length order.

The tricky part is you need to know those shortest path lengths (for all pairs of verts in the graph as they're added). To do that, you can propagate shortest-path updates each time you add an edge (a newly shortened path AB adds new potential shortened paths from A to each of B's neighbors and from B to each of A's neighbors too).

All paths in the shrunk graph are guaranteed to be within an arbitrary threshold of optimal. (if the threshold is small, you get a minimum spanning tree, which is neat!). In the picture, it's a <2x optimal path length guarantee.

Performance is weird, something like O(#verts * #edges)? The shortest-path-update ordering (stack vs. queue for the to-visit list) has a huge impact on performance and I'm not really sure why :o It handles graphs up to about 500-1000 edges instantly, but barfs on bigger inputs. The aspect that could be improved is the shortest path propogation - depending on the edge add order, a lot of the path shrinking is wasted effort.

I think a further improvement would be start with the minimum spanning tree (which is decently fast), compute the all-pairs shortest paths, then start adding the remaining candidate edges. This skips the majority of the shortest-path updating, since the graph is mostly connected.

Let me know if you want me to post the code somewhere, it's pretty simple.

spacechem!

Spacechem is my game of the year so far (either that or terraria!): Introductory video.

It’s in the weird little genre of engineering games, where you design a machine that performs some task, like “fantastic contraption”, “the incredible machine”, or “armadillo run”. They’re never really that popular, but they’re like catnip to me - puzzle games where you invent a solution instead of discovering it.

Here's an interview with the developer that I really liked.

Although it’s called spacechem, it’s only fictionally about chemistry (you’re physically manipulating atoms to perform chemical reactions... in space!). It’s really a programming game – you design a machine on a 2D grid of component machine parts, and the parts have different interaction rules. It’s kind of like visual scripting, kind of like designing a circuit. You watch the machine run, then tweak your design until your machine can perform some task.

The game does a great job of building up complexity gradually – at the beginning of the game you’re given simple components and tasks, and by the end of the game you’re doing things that would have been completely impossible for you in the beginning. It’s the good kind of mind-bending – you feel yourself getting better at the game, and you see your designs getting more efficient and elegant.

The game has a demo if it seems like your kind of thing!

Tiny multiplayer RTS

I made a tiny multiplayer RTS for XNA. You don't get direct control over your units, you only get an abstract kind of strategic choice - a balance between higher-level strategies. In a real RTS, being able to micro your units is critical, but so is knowing the higher-level strategies, and this is a toy model of those higher level strategies. In almost every RTS (with the exception of myth?), you have to maintain a constant balance between defending, attacking, and expanding - and there's an RPS relationship between them. (Turtle beats rush, rush beats expand, expand beats turtle). In this tiny RTS, instead of having direct control over your units, all you get is control over that production balance (choosing to produce more offense, defense, or econ units), and choosing how to time attacks.

Here's a screenshot of some of my attackers (the swords) on their way from my base (upper left) to the enemy base (lower right).


Design: I like the RPS relationship between the three strategies, and how your opponent's strategy is hidden from you - you have to scout out the enemy, since there's a fog of war.

I like the exponential economic growth, I think that nicely captures the quick economic ramp-up you find in RTSs. It doesn't plateau as naturally as in real RTSs, where your growth is quickly limited by various bottlenecks (like having a cap on simultaneous peon units extracting resources, or tying economic growth to expanding over the whole map).

I don't like how scouting is "free" - normally in RTSs you're sacrificing the units to do scouting. I also don't like how geography doesn't really matter - you can't position your attackers and defenders in a way that protects your base, or fighting over one resource instead of another. In an earlier version of the game, I made it so that the attackers couldn't kill econ units until all the attackers and defenders were dead, but that ended up being pretty broken.

Technical details: It's using GFWL for the matchmaking - although I hate it as a gamer, it's is super easy to code with it and XNA. However, unless you're a registered Indie/Community/AppHub developer, you're limited to playing LAN games, which is sucky. I made the game automatically host if no games are available, and automatically connect to any games that are waiting for players - so run a copy of the game on two machines on a LAN and you're set to have the most fun possible! You *may* have to create a new "offline" GFWL profile to make it not search for games on the internet :(

It's a clickonce installer, which is pretty slick (although the installer UI can be a little janky, it's cool that it automatically installs and updates itself with barely any work on my part). The source is available on the codeplex project page, but it's nothing special.

As for networking, it's a lockstep/deterministic simulation that sends user input over the network before it's used in the simulation (in the style of starcraft), so it's really low bandwidth, at the cost of a fixed 250ms latency on your input. It's been forever since I've done any networking code, and I'm glad this was relatively straightforward (with a couple desyncing bugs).

I stole the barycentric-allocation-triangle idea from simant :)

how to make bechamel sauce the first time

* melt butter in saucepan
* begin panicking
* with one hand on the tippy saucepan and the other hand whisking, use another hand to add flour, milk, bay leaves, allspice, salt and pepper, and another hand to adjust the heat to keep it between getting too hot and drying out, and getting too cold and coagulating
* be suprised it's not a lumpy burned mess, optionally stop panicking
* put on moussaka

hire me!

I'm a game programmer looking for work, in LA and willing to relocate. I'd like to do gameplay, audio or general programming. Here's my resume as a word doc.




I've been working on a little game demo, a roguelike. You can download the installer (run the setup first, it's a ClickOnce installer). Mike Tipul (a coworker) and I started it a year ago, and we collaborated on it then abandoned it until recently, where I dusted it off for release. There's a codeplex project for it, or you can download just the source (no project files, no artwork).



Features:
* Tile based pseudo-ascii rendering
* Visibility/lighting and shadows
* Procedural dungeon and forest generation
* Location-based damage and severed limbs affect gameplay
* Weapons and multiple damage types
* A tiny little mission where you clear out a forest of wolves, then a dungeon of goblins
* Lots of tutorials that walk you through the game (which is about 5 minutes long)

gravitybone

I am so impressed by gravitybone. Clever, funny, artful - and I'm not just saying this because Brendon's in this building. This is the sort of thing I wish our industry (and me specifically :) would produce.

I'll probably think of it every time I hear 'perfidia' (that and Wong Kar-wai) then play it again. It's worth your time (it's short and very friendly) and the hassle of fileplanet's download service.

C++ is so baroque

Because of stuff like this. What's so crazy is that webpage is all good advice - a page of code to make a type safely cast to bool.

And here I am reading it all.

natural intervals in programming

Don't read this, it's boring. I sometimes run into bugs dealing with the edges of intervals. Most of these bugs are because some code assumed an interval was inclusive at the top, and some other code assumed it was exclusive.

Most people seem to understand the convention for array sizes (ie a function called int getSum(const int* a_Array, a_Count) wouldn't touch a_Array[a_Count], and a two-parameter version getSum(int* myArray, int start, int count) would touch a_Array[start] but not a_Array[start + count]), but we don't always get it for floats / real numbers.

I think the "natural" way to split intervals is half-open, like [a, b). To include the bottom and exclude the top, and to do it this way for integers and real numbers. All your "is this number in this range" checks should be of the form fMin <= x && x < fMax, and this should be a convention you can use without really thinking about it.

The important part is consistency. If different parts of code assume a different convention, you're boned. There are a few reasons I think the best convention is the interval [min, max). It's the closest to how division and quantization work - an object at 20.0 gets put into bin 2, because 20/10 = 2. Any logic and math is consistent no matter how we're storing the positions (if they were meters in integers, floating point numbers, or 10s of meters in integers, whatever). The reason the interval has to be half-open is so that only one of two adjacent intervals gets the point (this is important for partitioning groups of things).

Most functions that deal with ranges of numbers exclude the top. Random usually returns [0,1), arrays can be accessed from [0, count), this is how quantization works (representing RGB with char values gives you the range [0, 1<<num_bits) for each channel), etc. This is so boring, so don't think about it - just use min <= x < max.

boogs

This bug:


Looks kind of like this cellular automaton.

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.

hidden state vs. nondeterminism in games

Complexity
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).

Nondeterminism
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.

senses

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.

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

disconnected

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.