First and foremost, this blog is amazing and you should check it out. While checking it out myself, I was reminded of a simple, but cool concept. The Pigeonhole Principle. I'm going to use an example similar to the one on the blog.
Suppose there are 11 pigeons trying to roost in 10 pigeonholes. At least one of those holes is going to end up with 2 or more pigeons. Sounds obvious right? What if I told you there are at least two (non-bald) people in Seattle, Washington with the same number of hairs on their head? Doesn't sound so obvious, but that's exactly why the pigeonhole principle is cool!
Most, if not all people, have fewer than 200,000 hairs on their head. There are more than 600,000 people living in Seattle. There are more people (pigeons) than possible numbers of hairs (pigeonholes). The same is true for any city with enough people.
Showing posts with label math. Show all posts
Showing posts with label math. Show all posts
Tuesday, June 24, 2014
Tuesday, December 3, 2013
Of Groups and Other Things
My goal is to make a grid-based cube world, not unlike Minecraft. However, I don't want it to appear outright as boxy as that, so I'm going to include other shapes, not just cubes. Here's how I can to decide on which shapes to use.
The first shape that came to mind, other than a cube, was a slope. Naturally this led to corner slopes as well, both inner and outer. I then decided I wanted slabs, blocks that are only a portion of the height of a full block. This led to the idea of scaled slopes as well. I decided to divide the shapes into four possible heights. Not content to favor the vertical direction, I decided to include all rotations and reflections of these shapes.
At this point, the number of shapes had already climbed into the thousands. It became evident that if I wouldn't be able to handle each shape by hand on a case by case basis. I needed to to use math!
So I started thinking of mathematical ways to organize the different shapes. The easiest thing to do was to categorize each block by which slices you'd have to make to carve it out of a cube. For the slopes, that meant cutting diagonally. For the slabs, cutting flat across the middle.
Because I wanted four levels to my shapes, I just had to figure out all the slices that only cut across fourths on each edge. That way, there would be no awkward shapes that wouldn't match up with any other shape.
This actually turned out to be quite challenging. In 2D, the idea is pretty simple. You just pick any two points on the outside and draw a line through them. It's doesn't work out so nicely in 3D. There are lots of ways you can pick three points that don't result in a valid cut.
I spent a long time on that, but it seemed that no matter which way I organized the shapes, there'd be a couple of gaps full of invalid cuts. After many hours of trying to make that work out, I went with a somewhat simpler approach. I start with a tetrahedron made by slicing through three of the cube's corners. Then, I take that and scale it on each axis. Then I take those shapes and extrude them along each axis. Then, I also include the inversions of all those shapes.
When all is said and done, I end up with 54,000 different combinations. This way of doing it also has some nice properties. I can arrange the whole thing in a 30x30x30x2 grid, which allows me to look things up easily. I can encode the position of a shape within this grid using 5 bits for each axis and a bit for inversion (encoding each axis separately allows me to discern qualities of a shape easily). This is exactly 16 bits, which allows me to use 2 bytes per block rather than more, and doesn't waste them. I can also tell whether two shapes cover the same cross section along an axis by checking if they're in the same line in that grid.
To sum up a long story, here is a picture taken from within that grid of possibilities.
.png)
The first shape that came to mind, other than a cube, was a slope. Naturally this led to corner slopes as well, both inner and outer. I then decided I wanted slabs, blocks that are only a portion of the height of a full block. This led to the idea of scaled slopes as well. I decided to divide the shapes into four possible heights. Not content to favor the vertical direction, I decided to include all rotations and reflections of these shapes.
At this point, the number of shapes had already climbed into the thousands. It became evident that if I wouldn't be able to handle each shape by hand on a case by case basis. I needed to to use math!
So I started thinking of mathematical ways to organize the different shapes. The easiest thing to do was to categorize each block by which slices you'd have to make to carve it out of a cube. For the slopes, that meant cutting diagonally. For the slabs, cutting flat across the middle.
Because I wanted four levels to my shapes, I just had to figure out all the slices that only cut across fourths on each edge. That way, there would be no awkward shapes that wouldn't match up with any other shape.
This actually turned out to be quite challenging. In 2D, the idea is pretty simple. You just pick any two points on the outside and draw a line through them. It's doesn't work out so nicely in 3D. There are lots of ways you can pick three points that don't result in a valid cut.
I spent a long time on that, but it seemed that no matter which way I organized the shapes, there'd be a couple of gaps full of invalid cuts. After many hours of trying to make that work out, I went with a somewhat simpler approach. I start with a tetrahedron made by slicing through three of the cube's corners. Then, I take that and scale it on each axis. Then I take those shapes and extrude them along each axis. Then, I also include the inversions of all those shapes.
When all is said and done, I end up with 54,000 different combinations. This way of doing it also has some nice properties. I can arrange the whole thing in a 30x30x30x2 grid, which allows me to look things up easily. I can encode the position of a shape within this grid using 5 bits for each axis and a bit for inversion (encoding each axis separately allows me to discern qualities of a shape easily). This is exactly 16 bits, which allows me to use 2 bytes per block rather than more, and doesn't waste them. I can also tell whether two shapes cover the same cross section along an axis by checking if they're in the same line in that grid.
To sum up a long story, here is a picture taken from within that grid of possibilities.
.png)
Tuesday, November 19, 2013
Words, Words, Words
Salutations! So I bounced back a forth between a few things this week. I did a little more work implementing the programming language I designed. Bittersweetly, I encountered a few small problems I hadn't foreseen. While this was frustrating, it was also nice to have them called to my intention.
I also worked some more on the math library (see this post for relevant links). At one point, I modified the game to start using it, so now the game's kinda stuck until I either finish the math library or at least get it working well enough to function. My choice to include concepts from geometric algebra is making it difficult to complete. It's hard to find good reading material on the subject, and often even harder to wade through it. I love the subject, and I've enjoyed learning about it, but it can be a little overwhelming at times.
When I started the original library (years ago before I'd even heard of geometric algebra), I used templates to implement things (including some fancy recursion and inlining to avoid unnecessary loops). I continued that way for a while, but it quickly became more trouble than it's worth. So instead, I wrote a program to generate the code for me.
Another one of my interests, not mentioned till now, is language. Specifically, constructing languages. Years back, I started work on a conlang (short for constructed language). It went through many revisions, but I eventually stopped working on it. It's been gathering dust since. Fast forward to now, when I decide to drudge it up and start working on it again! The thing I always had the most trouble with was actually making up words. You might be thinking, "if you weren't making up words, then what were you doing?". Consider that making an interesting language (i.e. not just replacing English words with new ones) involves phonology, morphology, grammar, etymology, and a whole slew of other considerations.
For anyone who might be interested, this site has lots of good resources on language making. For breaking away from English pronunciation, you might want to look into the international phonetic alphabet. This site has interactive charts, complete with sounds. I recently learned about the Swadesh list. A short list of basic meanings. It's been very helpful, and has given me a good starting point for creating words. Here are some similar lists one can use.
Well, that's all I got for right now. See you next week!
I also worked some more on the math library (see this post for relevant links). At one point, I modified the game to start using it, so now the game's kinda stuck until I either finish the math library or at least get it working well enough to function. My choice to include concepts from geometric algebra is making it difficult to complete. It's hard to find good reading material on the subject, and often even harder to wade through it. I love the subject, and I've enjoyed learning about it, but it can be a little overwhelming at times.
When I started the original library (years ago before I'd even heard of geometric algebra), I used templates to implement things (including some fancy recursion and inlining to avoid unnecessary loops). I continued that way for a while, but it quickly became more trouble than it's worth. So instead, I wrote a program to generate the code for me.
Another one of my interests, not mentioned till now, is language. Specifically, constructing languages. Years back, I started work on a conlang (short for constructed language). It went through many revisions, but I eventually stopped working on it. It's been gathering dust since. Fast forward to now, when I decide to drudge it up and start working on it again! The thing I always had the most trouble with was actually making up words. You might be thinking, "if you weren't making up words, then what were you doing?". Consider that making an interesting language (i.e. not just replacing English words with new ones) involves phonology, morphology, grammar, etymology, and a whole slew of other considerations.
For anyone who might be interested, this site has lots of good resources on language making. For breaking away from English pronunciation, you might want to look into the international phonetic alphabet. This site has interactive charts, complete with sounds. I recently learned about the Swadesh list. A short list of basic meanings. It's been very helpful, and has given me a good starting point for creating words. Here are some similar lists one can use.
Well, that's all I got for right now. See you next week!
Subscribe to:
Posts (Atom)