Simulated Architecture #2: The Concept of Distance
A core concept to architecture, town planning and 3d graphics is that of "distance" and what I want to talk about in this instalment.
In mathematics the concept of distance comes under the idea of a metric. Given two points in space, a metric gives you a number that correlates to its particular way of deciding distance. A metric as a function isn't any old function - it has certain properties that we intuitively think are intrinsic to distance. Distance is a property of the space between two points, not so much a property of one point in relation to another. In other words, we don't have an orientation, so we think of distance as non-negative. The oriented version is called displacement where the direction (point x to point y versus point y to point x) determines sign, depending on how you set things up. Also, since distance is a property of the space between the two points, the distance from x to y should be the same as the distance from y to x because it's the same space. We allow distance to be zero in the case (and only the case) where you're looking at the space between a point and itself. Finally we have what is called the "triangle inequality" which means if you have three points x, y and z, the distance between x and z is at least the distance from x to y plus the distance from y to z. Basically, you can't "cheat" distance by choosing to measure it by a tricky choice of the space in between. It gives us the concept of a "minimum distance" between points and any detour is definitely a detour.
We settle on this intuition of distance and sooner or later, we find there are funny ways of measuring distance that nonetheless coincide with base intuition. Here's a bunch of different types of "distance":
As artificial as these other distances initially sound, we use them. In a realistic environment, it turns out they are more applicable than the "familiar" Euclidean distance. I noticed when playing GTA San Andreas the other day that the designers exploit real-world distance for a psychogeographic effect, that is, to fool your Euclidean distance intuition. Often times in San Andreas two parallel roads might be quite close, but a tangle of buildings, walls or clutter objects separate them. When you move about the game world, you are funnelled into taking a longer path than the direct (Euclidean) path, or are made to take the shorter distance at a slower pace (on foot, through tight spaces or through rough terrain). Though these spaces are close, they feel further apart. In the book A Pattern Language, the authors talk about this with examples of building designs that require small changes to greatly increase the feeling of distance. You can get the feel for this via Tetris pieces. All Tetris pieces are made of 4 blocks. The square block feels small. The L block feels bigger. One explanation for this is that the Manhattan distance from blocks is generally smaller in the square block than the L block. But it's more than this. Tetris blocks are too small to explain, so imagine a U-shaped building. Then compare it with a building with the same floorspace, but in a straightened-out Z shape. The U building occupies less conceptual land space than the Z building (if you want to explain it in 3d graphics terms, the U building has a smaller bounding box than the Z building). By choosing particular simple details we can engineer a particular "feel" of distance in a game world.
Why would we want to make this any different to straight line distance? Processing limitations. A computer can only load, unload and process data at a particular rate. A modern hard-drive can read 80 megabytes of sequential data a second. This is under ideal circumstances. You don't have this luxury: you might be reading in non-sequential data, you might be reading in fragmented data, you might have to fight other processes (like paging) for the use of a hard-drive. Plus you have to do stuff with this data. As fast as computers are, they have very noticeable limitations. We would like measures to limit the user from requesting massive changes in memory. If we can slow their progress in the world, then this helps tremendously. A space that exploits the psychological understanding of distance can improve the impact of our data. That is, data as processed through a human depends on time of exposure rather than pure bit counts. If it exceeds a certain threshold of interestingness, then spending twice as long in that data feels equivalent to spending the same time in twice as much data. Interestingness depends a lot on how the geometrical forms play together, the textural details and gameplay utility.
Of course there are other solutions to the limited data rate problem. We can use more efficient algorithms or more powerful hardware. Alternatively one general method is to present a small set of data as psychologically representing a larger set. We can reuse data via tiling textures or cloning objects, though you have to watch for excessive repetition. You can present successive levels of detail to the user so a building up close might be a million triangles, but at a far distance it has a simple texture and uses only a handful of triangles. So long as the transition between detail levels isn't too dramatic and the overhead for the different levels of detail isn't too great, then we can get the same psychological impact for less data.
I find it interesting how you get this interplay of structure and algorithmics with psychology of the user. The processing capabilities ask you to make a trade-off which you do by exploiting perceptions, but if you push it too far, you sabotage your own efforts. But with the right balance, you not only get better computer performance, but better human performance. Presenting a human with a large amount of detailed data might make them pop and disorientate them. By playing to the human's limitations you can also play to the computer's limitations. What's even more interesting is giving the task of balancing these performance issues to a computer. Can they make sound judgements on how and where to mess with psychological distance to improve the speed they can deliver the world and how effectively a human can interact with that world? GTA San Andreas works because humans made the world and knew when to slow things down without being too much of an obstacle.
Ideas I've had that I'll explore later include the use of "flow" in a city (optimize data flow based on the likely flow of human traffic) and an electrical circuit analogy to region building where instead of electrical current you moderate space and time. A resistor is like replacing a straight street with a curvy one. These are duals of each other: the former optimizes content loading based on the geography, the other optimizes the geography based on the required data flow.
It'd be interesting to see how these different approaches to distance can be used in effective city building. Twisting it around you could map these things into the AI who run around in the city and tweak how they (and I guess, the player) interact with things.
Next time I can talk about methods to algorithmically form a city, an explanation on how graphics cards are used, and a grab-bag of methods to generate house plans. If you wanna hear about any of these in particular, or some related topic, put your hand up and be heard.
In mathematics the concept of distance comes under the idea of a metric. Given two points in space, a metric gives you a number that correlates to its particular way of deciding distance. A metric as a function isn't any old function - it has certain properties that we intuitively think are intrinsic to distance. Distance is a property of the space between two points, not so much a property of one point in relation to another. In other words, we don't have an orientation, so we think of distance as non-negative. The oriented version is called displacement where the direction (point x to point y versus point y to point x) determines sign, depending on how you set things up. Also, since distance is a property of the space between the two points, the distance from x to y should be the same as the distance from y to x because it's the same space. We allow distance to be zero in the case (and only the case) where you're looking at the space between a point and itself. Finally we have what is called the "triangle inequality" which means if you have three points x, y and z, the distance between x and z is at least the distance from x to y plus the distance from y to z. Basically, you can't "cheat" distance by choosing to measure it by a tricky choice of the space in between. It gives us the concept of a "minimum distance" between points and any detour is definitely a detour.
We settle on this intuition of distance and sooner or later, we find there are funny ways of measuring distance that nonetheless coincide with base intuition. Here's a bunch of different types of "distance":
- Euclidean or "straight line" distance: With our usual geometric setup this is Pythagoras' theorem (generalized to whatever dimension you're in). Diagrammatically, the distance is the length of the straight line between your two points. This is the familiar idea of distance - familiar because it uses nice, uncomplicated things like orthonormal bases (where the x-axis is at right angles from the y-axis, and one unit in the x-direction is the same length of one unit in the y-direction) and straightforward geometric features like parallel lines being constant distance from each other.
- Manhattan or "grid" distance: In a city where all roads are connected in a grid pattern, to measure the distance you have to walk to get from one point in a road to another is measured not in the straight line from point-to-point through the buildings, but along the roads. Distance is described in this way like "two blocks north and three blocks east" rather than 350 metres "as the crow flies".
- Graphical distance: Imagine a road network between towns. The towns are vertices and roads between them are edges, and so make a graph. Distance from x to y is the smallest number of towns you have to go through from x to y. Distance is described in this way like "That's two towns over". You can of course modify this to include a distance (or weight, in graph theory terminology) along each edge so a town might be two short jumps away rather than one long one.
- Discrete distance: This is what you get in mathematics by considering the most trivial idea of distance that still obeys the intuition. What we do here is measure distance by whether two points are the same or not. If they're the same, they're distance zero. If they're not, they're distance one. That's it. We still use this metric in everyday life: someone is from your town, or they're not. Or your state, or not. It's the "here" versus "everywhere else".
As artificial as these other distances initially sound, we use them. In a realistic environment, it turns out they are more applicable than the "familiar" Euclidean distance. I noticed when playing GTA San Andreas the other day that the designers exploit real-world distance for a psychogeographic effect, that is, to fool your Euclidean distance intuition. Often times in San Andreas two parallel roads might be quite close, but a tangle of buildings, walls or clutter objects separate them. When you move about the game world, you are funnelled into taking a longer path than the direct (Euclidean) path, or are made to take the shorter distance at a slower pace (on foot, through tight spaces or through rough terrain). Though these spaces are close, they feel further apart. In the book A Pattern Language, the authors talk about this with examples of building designs that require small changes to greatly increase the feeling of distance. You can get the feel for this via Tetris pieces. All Tetris pieces are made of 4 blocks. The square block feels small. The L block feels bigger. One explanation for this is that the Manhattan distance from blocks is generally smaller in the square block than the L block. But it's more than this. Tetris blocks are too small to explain, so imagine a U-shaped building. Then compare it with a building with the same floorspace, but in a straightened-out Z shape. The U building occupies less conceptual land space than the Z building (if you want to explain it in 3d graphics terms, the U building has a smaller bounding box than the Z building). By choosing particular simple details we can engineer a particular "feel" of distance in a game world.
Why would we want to make this any different to straight line distance? Processing limitations. A computer can only load, unload and process data at a particular rate. A modern hard-drive can read 80 megabytes of sequential data a second. This is under ideal circumstances. You don't have this luxury: you might be reading in non-sequential data, you might be reading in fragmented data, you might have to fight other processes (like paging) for the use of a hard-drive. Plus you have to do stuff with this data. As fast as computers are, they have very noticeable limitations. We would like measures to limit the user from requesting massive changes in memory. If we can slow their progress in the world, then this helps tremendously. A space that exploits the psychological understanding of distance can improve the impact of our data. That is, data as processed through a human depends on time of exposure rather than pure bit counts. If it exceeds a certain threshold of interestingness, then spending twice as long in that data feels equivalent to spending the same time in twice as much data. Interestingness depends a lot on how the geometrical forms play together, the textural details and gameplay utility.
Of course there are other solutions to the limited data rate problem. We can use more efficient algorithms or more powerful hardware. Alternatively one general method is to present a small set of data as psychologically representing a larger set. We can reuse data via tiling textures or cloning objects, though you have to watch for excessive repetition. You can present successive levels of detail to the user so a building up close might be a million triangles, but at a far distance it has a simple texture and uses only a handful of triangles. So long as the transition between detail levels isn't too dramatic and the overhead for the different levels of detail isn't too great, then we can get the same psychological impact for less data.
I find it interesting how you get this interplay of structure and algorithmics with psychology of the user. The processing capabilities ask you to make a trade-off which you do by exploiting perceptions, but if you push it too far, you sabotage your own efforts. But with the right balance, you not only get better computer performance, but better human performance. Presenting a human with a large amount of detailed data might make them pop and disorientate them. By playing to the human's limitations you can also play to the computer's limitations. What's even more interesting is giving the task of balancing these performance issues to a computer. Can they make sound judgements on how and where to mess with psychological distance to improve the speed they can deliver the world and how effectively a human can interact with that world? GTA San Andreas works because humans made the world and knew when to slow things down without being too much of an obstacle.
Ideas I've had that I'll explore later include the use of "flow" in a city (optimize data flow based on the likely flow of human traffic) and an electrical circuit analogy to region building where instead of electrical current you moderate space and time. A resistor is like replacing a straight street with a curvy one. These are duals of each other: the former optimizes content loading based on the geography, the other optimizes the geography based on the required data flow.
It'd be interesting to see how these different approaches to distance can be used in effective city building. Twisting it around you could map these things into the AI who run around in the city and tweak how they (and I guess, the player) interact with things.
Next time I can talk about methods to algorithmically form a city, an explanation on how graphics cards are used, and a grab-bag of methods to generate house plans. If you wanna hear about any of these in particular, or some related topic, put your hand up and be heard.