Nooo! More stuff about pseudo random numbers and computer games! Stop it. Stop it I tell you!

Ok, so maybe I'll take a break from it for now, and try not to be a total geek today...

It's hard when you do software development for a living, and stick with it's because you think it's almost more fun than the stuff you do in your spare time :-)

I DO actually have other interests as well. Maybe I'll post some of my poems one of these days (allthough then I'll probably scare the few of you actually reading this away with overly soppy and/or depressive stuff - I rarely write when I'm not in the process of falling in love with someone or insanely depressed, usually because of rejection(1)).

London can be such a depressing city. It's been raining on again off again all day, the traffic is horrible, the air disgusting... Been thinking off moving out of the city for a while, but will probably wait until next May when our lease expires.

Property prices here are just horrible now. I'm used to Norwegian levels, and thought that was ridiculous, but come on, 200.000 pounds is now the average cost of flats and houses sold in London...

It never seizes to amaze me how far up the prices can go here withouth a significant increase in building projects (except for Docklands, which seems to be mostly luxury complexes anyway, due to its proximity to the City).

Ah well, guess we'll get something slightly outside town.

Vidar

(1) But don't feel sorry for me about the rejection bit, I'm engaged to a woman I met more than two years ago, so feel sorry about my lost career as a poet instead, as I'm now too happy about things to write anything truly good - my depressive poems were always my best ;)

Expanding on my last idea, I'd like to write some more on events and viewpoints.

When a tree falls in the forest, and nobody is there to listen, does it make a sound? In the the pseudo-random or algorithmicly generated world, the answer should be no, because the tree doesn't fall. It only falls if someone is there, or when someone arrives and "observes" the past.

The point is this: If your world is generated algorithmically in a way that allow you to "visit" any point in space and time, then why waste computing power calculating something that isn't observed? If you need the information later (say your game has a "history book" somewhere, you can calculate it then).

Notice that "observed" here is a fairly wide term. Someone "observe" an event if they are directly affected by it, for instance because they're there, and watching, but they also observe it if they see the effects indirectly: They get the news relayed etc.

So events are only generated if observed. How do you determine if they would be observed?

Thats where viewpoints come in. You generate events based on viewpoints. Viewpoints are points in space and time. To generate events, you would take a set of viewpoints and move them through time, calculating changes in the world according to the algorithms you want to use, and use a rule set to emit events according to those changes.

A rule might say that a government change from democracy to military dictatorship happens only with the use of military power, so such a change will emit a set of events corresponding to a military takeover.

What about details?

In the real world, think about what you know, and how it corresponds to level of detail. You can likely see the room around you, and describe objects in it in detail, and conversations in it as well. You may hear noises from outside. You may see news on TV, or in a local newspaper. News about your local area may include details about the shop around the corner, but from other countries you only get events of importance or interest to a larger audience: Major political events, like an election, disasters and so on.

In other words, the level of detail drops of dramatically with distance, and this is important, since otherwise you'd be swamped.

Translated to a game, that would mean that you use the viewpoints not only to decide what parts of the world to actually calculate, but also what level of details the events should have. There's no reason to simulate the full level of details about a military coup on a planet lightyears away. It might be noted in the news, if the planet is important, or the coup bloody enough, but thats it.

But an attack on the planet the viewpoint is on would be noteworthy, and the event generator would need to expand, both by increasing the resolution of advances in time - smaller changes to the timeline must be done, and more events emitted -, but also by splitting events into stream of events, and handling deviations if someone interfere. It might include simulating troop movements, or introducing AIs to simulate individual objects, as well as generating more meaningful news.

A viewpoint can essentially be there for anything from passively observing the world, to an AI player, to a human player, or anything else that require information about the world at a time period at a given point in space.

Vidar

One thing that I've been thinking about recently is how useful pseudo-random numbers are in computer games.

Pseudo-random numbers are numbers that are being generated with some algorithm that makes it possible to repeat the sequence if you seed the generation algorithm with the same value as you used initially, but that still seem to be random in that it is incredibly hard to predict the sequence without knowing the algorithm, and that have statistical properties that closely mirror random numbers.

Perhaps the most notable example of use of pseudo random numbers is Elite. (If you've never played Elite, shame on you, and you have no excuse, since there's an open source remake).

Elite is almost entirely based around pseudo random numbers: The universes are generated by seeding a random number generator with a fixed value. The planet names, political and economical data are generated by seeding the random number generator with a seed extracted from the random number generator with the universe seed.

Change the universe seed, and the game changes, completely.

Thats what allowed the original Elite to run on machines like the C64, the BBC, and a ton of others - contrary to many modern games, they didn't have to store ANY data about the planets, only a few bytes for the universe seed and a small set of functions to generate the code.

More modern examples of pseudo random numbers in computer games is Civilization and all it's descendants, Sim City and it's descendants and many other map based games.

However randomness could be used so much further. Games like civilization only create a basis for the further game, then AIs take over. Elite conceptually went much further, by basing the entire structure of the universe, including it's civilizations, on randomness, allthough it manifested itself in the game rather crudely (it didn't really affect you that the planet you visited was inhabited by green felines)

The main appeal of pseudo random numbers, or for that matter any formula or algorithm that can reasonably quickly generate unpredictable but repeatable sequences is that it allows you to represent a much larger world than you could ever hope to design or store on the users system. It also allow you represent a world with much larger amount of detail than would otherwise be practical.

It's worth noting that pseudo random numbers is usually only used to seed specialized generation algorithms for generating various part of the world.

For a world that is so large and complex, it makes sense that you don't need to model all events via AI's either. Most complex games, including Civilization for instance, hide a lot of what is going on from you. In most Civilization style games, you can only see what's going on around your own units, and even then there might be further restrictions on what you see.

In Elite, you only see whats going on immediately around your ship.

These restrictions play right into your hand if you want to use a randomly generated world.

Many of the benefits of randomness go straight out the window if you need to keep track of changes to account for developments in the world. However, in many types of games you don't need to most of the time.

Take an Elite style game, for instance, and add detail: Government types changes, military control and dominance fluctuates, etc. For almost any kind of change, you can put together an equation that give fluctuations over time that are reasonable. Add a few elements to the equation where you can affect it by random variables, and you have a model for generating a world where you can generate not only every position in space, but also in time.

Depending on the level of detail you want, you can go in at an arbitrary time and an arbitrary point in space, and see roughly what went on (in a newspaper headline type of way - details of events, such as how a ship navigates, will likely seem weird to a human player).

Now you have a static world that can be regenerated from a small string of numbers. But what about the player and non player AIs? Instead of recording everything that happens, you can calculate most of it, and whenever a player does something, you store information about deviations from the randomly generated world.

Imagine that you as a player in a space strategy game, destroy a ship. The ship was part of a military fleet trying to conquer a world. As a result of your action, the fleet loses its advantage, and the game doesn't manage to compensate by weakening the opposition quickly enough (without making it too obvious for the player), so the invasion fails, and the timeline doesn't work out anymore.

What should the game do? Record a deviation, and determine a target time for returning to the timeline. The world is under government X instead of Y, but some time over time T, the game will create events that will bring things back to where it should be.

As long as it's done smoothly enough, the players won't notice. This model also has the advantage that if the player stays close, then the player keeps affecting the timeline and will see little of the effects of the game slowly compensating to bring things back in sync, and if the players move around a lot, the player won't see whats going on, and any logical flaws in the compensation that is being done will be hidden.

This idea is essentially based on one of many theories trying to resolve the problems of time travel: What if any changes you make to the past will be compensated for so that you can only cause disruption for a limited period of time, before at least most of the rough differences between the two timelines have been resolved. So the further back in time you go, the less effect you can have on the present.

Structuring a world via pseudo random numbers in both time and space indeed make the game itself time travel in a way: The entire timeline of the game was set before the game started, and you as the player travel back in time and are allowed to affect limited pockets of space time, but as soon as you turn your back, the game engine compensates away all your changes, making you just a ripple in the ocean...

Wish I had time to do game programming :)

Over the weekend I've been fooling around with Protocol Extension. I first came across it in '95 or '96 after getting an interest in all the cool stuff going on at department of computer science at ETH Zürich thanks to the Amiga.

You might ask what the Amiga has to do with ETH. The answer is that in '94, after Commodore went bust, there were a lot of discussions in comp.sys.amiga.misc on Usenet about how to save the community, and ways to update the OS that at the time started looking dated (no virtual memory as standard, no memory protection as standard etc.). One of the things that came up was long term migrating to new CPUs, such as Apple did with the Mac. A guy called Edward Blevins posted this message (I love you Google Groups), as part of a HUGE discussion about what the new Amiga OS should look like.

The message points to a concept called Semantic Dictionary Encoding, introduced by Dr. Michael Franz in his doctoral dissertation at ETH. It's a method for encoding a semantic parse tree of an application in a hardware neutral form, and generate the final code at load time.

In a way it's JIT compilation as found in todays Java VMs, but instead of translating from bytecode to native machine code, Semantic Dictionary Encoding is based around translating directly from a simplified parse tree - you reduce the parse tree to a small subset of operators and data types, and optimize as much as you can, then you encode it in a way that at the same time compresses the file. When you load it, you do the final code generation step.

I loved the concept: You can instantly move binaries between systems with different CPUs. Code generators can be tuned to specific hardware combinations or specific CPUs instead of having to generate code for the lowest common denominator. Code generators can take command line arguments into consideration when generating code, allowing further optimizations. Generation can be done based on previous profiling data for YOUR system, etc.

This leads us back to protocol extension. Protocol extension is a way of extending class hierarchies at runtime. I read the report because I was impressed with Dr. Franz work on SDE. I implemented a C based prototype back in '96. I loved it, but didn't have time to go much further with it.

Same thing with SDE. I had a prototype Pascal compiler (because writing a Pascal compiler for basic Pascal is dirt easy) that generated SDE, and a dummy code generator for something pretty close to 68000 machine code. But I didn't have time to look closer at it.

Now, these are two examples of incredibly cool tech I've run into, that to this day is practically unknown in the tech world outside those of us geeky enough to read doctoral dissertations and technical reports from ETH...

Why is it that so few geeks seem to follow whats happening in the universities? Schools like ETH, and numerous universities around the world are spewing out great computer science work that you'd think open source developers would be jumping at instantly, but instead many of these technologies languish for years without anyone spending time on it. In SDE's case, Dr. Franz is still pursuing it to my knowledge, but seems to get little interest for it from people trying to reimplement his tech.

I could pull out dozens of examples of other great concepts that are also being ignored.

Why? Isn't people aware of the technologies? Or am I the only one who find them cool? Did they come at the wrong time?

I'd love to find out.

Ah well, as soon as I have time I'll start looking at protocol extension and SDE again... Hopefully it will be before I'm retired.

Vidar

It's interesting to see how size affects community. When I started reading Slashdot in '98, the size of it meant that while I didn't keep in touch with many people on the site "outside" of the comments section, I did recognize many names, and used to care whose messages I commented on, and care what certain people replied to me.

As the site grew, however, the sheer number of users means that I most of the time feel no connection to the person I'm replying to - most of the time it's a username I don't recognize, and someone I know nothing about. It doesn't help that, like many geeks, I'm not the most social person... :)

Maybe the introduction of the friends system and the journals will change that again, to some extent. Another thing might be chat (yeah, I know there's an IRC channel, but some of us are behind firewalls during the day - a proxied java irc client might be a nice thing :) and permanent discussion forums, more like news.

The user base of Slashdot contains a lot of extremely interesting personalities, and it would be great to be able to "connect" more with people than the current comments frenzy allows.

Anyway. If anyone reads this, feel free to e-mail me at vidar@hokstad.name if you have comments :)

Vidar