30 days ago
Amit Patel’s article on procedural map generation is a real gem.
It even includes a flash application for creating your own procedural maps.
In one article he manages to tie together:
It’s part of a larger body of useful game programming links he maintains on his site.
31 days ago
Given an ordered string T of unique elements, consider an operation that takes k elements and permutes them randomly.
If you consider all the permutations of T, and you categorize them according to the minimum number of operations required to reach T, how many permutations are in each grouping?
For example, ABC, where an operation is swapping 2 elements:
0 operations: ABC (1 permutation)
1 operation: BAC, CBA, ACB (3 permutations)
2 operations: CAB, BCA (2 permutations)
So we could write this as
So what do these groupings look like?
h3.Swap 3
h3.Swap 4
32 days ago
Today I ran across an interesting paper. It gives a simple recurrence relationship to generate the elements of first n rows of a Stern-Brocot tree.
It’s surprisingly simple. To generate the first n+1 rows, take the values
where
given
where
for odd j and non-negative vi.
Put informally, vi is the number of trailing zeroes in the binary representation of i.
What’s surprising about this sequence is that it produces a list that is rational, increasing and unique.
242 days ago
Lindenmayer Systems, or L-Systems are not complicated. Take a string as a set of instructions in turtle graphics. “L” means “turn left”, “R” means “turn right”, and “F” means “go forward”.
Now imagine starting with a string “A” and a set of rules. You replace the characters in this string according to the rule a fixed number of times. Then for every type of character, you can either replace it with one of “L“, “R“ or “F“, or ignore/remove it.
For example, suppose you have one rule,
and a final rule
In this example, it takes 12 or 12
turns to turn completely around.
We start with and apply the rule to get
. We apply the rule again to get
, and so forth. In my example, I stopped when I got a string that would have 5000 forward moves in it.
Here’s what it looks like:
That’s one continuously traced path, all thanks to string rewriting. I’ve also created a page with a large number of random rules. It takes a lot of memory because of all the thumbnails, but if you’re curious about the rules used to generate a shape, simply follow the link to the SVG and “view source” to see what generated that shape.
261 days ago
I finally made to to 200 problems! Better yet, I picked two of the problems that had been pestering me for a while:
As I was working on “Robot Walks”, I figured out that I’d come very close to the solution last year. I had a lookup table, but it had an incorrect value for orientation in cases where the robot moved in a complete circle right or left.
