Tuesday, November 11, 2008

VRWorlds: Procedural World Generation

Although my PhD has been put on the backburner while I'm completing my teaching qualifications, I've had a couple of interesting conversations with other developers regarding Temporal ROAM (which I'm now naming VRWorlds as it's less and less to do with ROAM nowadays).

With another discussion starting up I'm constantly trying to explain areas which I'd covered before, so it's about time to get it down in one spot. I probably should make a whole new section for this stuff, but here will do in the meantime (Ok, I'm lazy).


VRWorlds: Genesis
I've been studying random terrain generation techniques for ~15 years, even buidling an erosion model for my 3rd year Uni project. My ultimate goal was (is) to build a living, breathing world purely through procedural generation.

About 4 years ago I was working on a bifurcating river basin algorithm using the ROAM technique and stumbled on another idea entirely. Since ROAM uses the importance of a vertex as its criteria for deciding which ones to cull, what would happen if instead of vertexes being the atomic unit of a model, you used importance of events as the atomic unit of a whole world in a space-time graph? This would mean that at each bifurcation the system would generate the most important event for a whole chunk of space-time based off previous parent's events. The crucial part of the system is making sure that existing events constrain the generation of new events to create a consistent and coherent world.


PhD
After a number of discussions with Sandy and Andrew the idea had coalesced into my PhD Proposal. CQU passed the proposal in principle, but required a proof of concept for the application to proceeed.

I have had in mind a simple historymaker application that would generate a web page that reads like an index of a country's history book. You can then open each "chapter" to see the events belonging to that era, then dig down deeper and deeper. This should be relatively simple to implement, but complex enough to vet the process for breaks in causality.

Another proof of concept was to change the level generation of a simple procedural game like Moria. I then stumbled upon Andrew Doull's dissection of Random Dungeon Generation that he used for UnAngband and was gladdened to see the level generation technique almost mimicked what I wanted, but from a different tack.


Modifying UnAngband?
One of the problems with the proposed system is that the event generation will be so intrinsic to the running of the generated world that it almost demands a total rewrite of the way games are made. I needed to find out if there was an easy way to go further with importance based level design without totally rewriting an angband system. This would mean that once a room is selected first as the most important room for a level, it should also influence the placement of the next room in accordance to the architectural style, or, as Andrew had highlighted, starting another important room with a different leader / style in a separate area to lock in the scope of the level. The other thing would be to look at introducing the monster insertion directly after the room insertion (even if it's in a virtual sense by testing the seed that the room would use for population) to gauge the relative importance of the room that can then be used for constraints against the rest of the level generation.

In essence it would simply require an even further refinement of the architectural and ecological structures that UnAngband had in place so that more meaning can be embedded into the level for a more consistent and coherent world. Thing like Orcs being happy to use groups of worgs or goblins as slaves to do their dirty work, but wouldn't share their level at all with elves. This is getting more akin to Dungeon Fortress, however the lack of open source precludes it from experimentation.

Andrew (Doull) had a more pessimistic view of the alterations having a hunch that the human brain is a lot better at determining importance than a computer. To rate importance, you'll end up writing a small expert system, which can be complex and hard to debug particularly in the context of a procedural environment.

That is certainly true. Since importance is a personal preference something that can be important to one person may not be important at all to another. MkII of the project will introduce additional dimensions to allow these preferences to propagate in 'alternate world' histories. This is especially true for systems involving more than one player. From the system's perspective though, it is enough to assume that it can generate a consistent and coherent scene by determining an importance level to itself. Since the system (through the design of the event templates) decides what is important at each stage it is a self-fullfilling algorithm. Important events in the history of the world are important because they were picked first and no events picked after that can have more importance by definition of the algorithm.

Yes, the end result is an expert system in the sense that each event template is defined by a developer with possible importance levels, required objects, possible contributing objects, related events and constraints that it would impose on the system once in place. The system needs to be able to interrogate existing objects to see if they are capable of participating in the chosen event as well as having container objects to represesent a group mentality of undefined object instances.

As an example imagine that the coronation of a king is the most important event chosen for a chunk of spacetime. This event will require a king, a country, a crown and possibly a crowd of witnesses. From important objects first, you check whether there is a country already defined for that chunk and if so interrogate it to see whether there is anything that contradicts a coronation at the chosen time and place. If there is no country the group container that represents countries is interrogated to see if there are any reasons why a new country could not exist for that event. If the check is successful the group container would then define a new instance of a country that will participate in the event. This new country is now also available for subsequent deeper events.

Next up the king is interrogated in the same manner. If there already is a king instanced for the total duration of the chunk then there is no possibility of coronating a new one. If a king exists, but there is enough unknown space for the existence of another, then the king container is interrogated for the possibility of a new king for the chosen country. The king container needs to interrogate other related objects and within itself to satisfy that no other objects or events known to this point will preclude the formation of a new king. This means both a check into the future to make sure there is enough possibility for the king's reign as well as checking the paast for the possibility of king candidates (heirs, general, etc). There is also a location check. If an heir exists but has already participated in an event on the other side of the country then there is no way that he can get to this event. This may mean the the whole event is contradicted if there are no other heirs that have the possibility of being generated. You can imagine these requirements as an event cone that extends back into the past to constrain all possible objects that can participate in the proposed event. The further back in time the further away the object can be to still contribute to the event. Even though this VRWorld technique sets a maximum rate of expansion (akin to the speed of light), the technology tree is interrogated to deliver a more reasonable slope for that time period. Once the event is completed it 'pins' the participating objects to that specific point in time and space, so it also limits their involvement to a cone of events in the future.

The crown continues this trend of object interrogation but is not slated as a requirement. This means that an existing crown may be used if it meets the spacetime requirements (in fact it may have been the trigger that elevated the coronation event to such importance), but either a new crown or no crown at all may be acceptable to the design of the coronation event. The event itself is implementation agnostic, however it would be natural to include a description generator that can build a description by combining the participating objects into a sentence similar to Andrew's room description generator or the Infinity Universe history generator.

The crowd of observers shows another aspect of the workings of the system. It would be easy to build in an average attendance into the coronation template that can be massaged through the existing population object to give a crowd of people. This may be a combination of existing person objects that have already been defined and can make it to the event (and want to be there) as well as a new container of people defined as the coronation witnesses. This container does not need to know who all the people are that attended, just that the number of attendees are locked to that point in spacetime. The system intentionally does not generate any more information than it has to. As long as the event is satisfied the other details are not important. The system will make them important in future divisions of that spacetime chunk.

(I managed to record a long chat with Andrew (Doull) discussing these ideas, but I'll need his permission before adding it here.)


Infiniverse
There was another interesting post onto the roguelike development forums regarding an attempt at a fully procedural universe from star systems all the way down to trees on planets. I initiated a discussion with Tapio regarding the methods he used to see whether his project may be suitable for adaptation to VRWorlds.

This is a different way of describing VRWorlds:
The crux of what I'm working on is to look at events first and foremost rather than visual attributes. Important events are created first for large areas of both space and time, then agorithmically work out next most important events as you break up the area into smaller and smaller chunks. From these events you not only have the development of a random world, but a causal history and a living, dynamic world on completion.

Tapio:
Could an event be, for example, a couple of tectonic plates colliding and therefore generating mountains? Perhaps you could give a practical example of those events...?

At the start, yes. Building a world starts with large events, then continues to refine itself from those events. Imagine looking at the whole world and asking yourself "what is the most important thing that has ever happened?". Possibly the creation of life, or an asteroid hit, or even tectonic plates colliding. This first event shapes the rest of the world. All other events cannot be as important as that one (by definition) and must not contradict that one. You can then divide space and time into segments where the main event occurs in one segment and you have a deterministic method of generating an event in the other segments.

Imagine the first event is Tectonic plates colliding. This event is rated at importance level 50,000,000 and occured at time 150,000,000 BC with specific coordinates. Because it involves 2 plates, those 'objects' are then created and given names (EG: 'Europe', 'Africa') as well as other attributes for whatever a plate object has (mass, size, direction, etc). The event also dictates certain attributes, such as the plates must have been moving toward each other, the size / mass must be larger than normal (because it is a very significant event), etc. The event itself is generated from a template that handles plate collisions, which in turn depends on a plate template to generate needed objects.

Once that collision event is in place, it now divides the unknown world into 2 states, before collision and after collision. Before collision, there should be no events that are allowable that rely on the 2 plates being together, and after the collision there should be no events that rely on the plates being apart. Everything else is fair game though.

Now we divide up spacetime into new segments, say everything that happened before 1,000,000 BC and everything that happened after that. The collision is the most important event before 1,000,000 BC, so we just need to generate an event after 1,000,000 BC that still abides by the collision occurring. Say we decide it is the end of the 2nd World War. A war template is used to generate an "end of war" event with importance 20,000,000 a time in 1945, and a specific place. the war event then builds a list of objects that participated in the war. Since plates are the only objects generated at a higher level than this one, there is nothing stopping us creating any type of country. The only limitation will be that the countries would have had some animosity before the event and may or may not exist after the event. We generate objects with names (England, France, Germany, etc). There can be many, many attributes for a country that are not needed to illustrate the event of the war ending, so they are not fleshed out until an event calls on them to do so. So we possibly only need the names of the countries and that they existed at that specific point in spacetime. Not developing all information allows more flexibility in what events are available and how they integrate. In this type of design, any attribute can be deterministically generated, so there is no need to generate anything that is not needed. It's like asking an NPC "do you like fish?". You don't care what answer he gives as long as it is consistent (if you asked him the same question again 5 minutes later he should answer the same way).

Tapio:
In my project the highest (galaxy) level is generated from one RNG seed and then the subsequent view levels (apart from starmap, which is one huge block) use a seed number calculated from its position in the upper level.

Yep, this is essentially random determinism. Since you are always using the same algorithm (X,Y coords) to generate the seed for each level, you are guaranteed of generating the same scene once supplied with the same initial seed. My method uses this extensively, however the algorithms are different. Once you start a world with a random seed, that seed determines the event that is first out of all the events available. Once it it set, other events are generated using the initial seed AND the existence of the first event to shape the events available. These are also done deterministically so that the world / universe will always be consistent, but you don't need to store every event itself as you can re-create them. It is dynamic in the sense that a star exploding event could occur after the user starts playing that totally changes the landscape of the universe, but it still is deterministic and available to be rolled up once the user is no longer in that area. Generating by events means that you have a living, breathing, world that can (and will) change from its initial starting state.

Tapio:
The problem is, of course, that the changes in the world have to be saved and the management of them adds a lot of overhead to the engine.

I've been mulling over using shadow AI's that I'd played with for Personal Learning Environments to track the only thing that isn't deterministic; the player's actions. To minimize these changes, you can have an AI that DOES abide by the framework that attempts to pick the same choices the player makes. That way once the player leaves the area, any important events that have been conducted (killing the king, blowing up a city) can be answered by interrogating the AI. So you can roll up those events, then when the player comes back, the system re-builds the event tree while also interrogating the AI as a proxy for the player's actions. It is then up to the AI to decide whether chopping a tree down is important after 2 minutes, 5 minutes, 2 days, or revisiting the planet in 5 year's time. It's not always going to get it right, but it minimizes the data needed to be stored on the player's movements and actions.

Tapio:
To limit the amount of data needed for storage, I plan to limit the players' ability to shape the world to the closest view level.

In a VRWorld system, even though the data for the world itself is deterministic and does not need to be stored, I would expect there to be far more data used in presenting event and object templates than normal. On the whole though, it allows you to have an infinite, dynamic world with a known memory footprint (just like ROAM allows a consistent frame per second regardless of the scene).

That, to me, is one of the key points and the reason I believe a VRWorld system will eventually work despite the exponential explosion of data it leans toward; you only need to build as much of the event tree that you want/need to. If you know that your system can handle a 10,000 event tree, those 10,000 events can be highly targeted to the time and place where your character is existing. Even if your system could only handle only 1,000 events, it's essentially the same place. The most important 1000 events are generated first, which means that the shape and context of the space you are in remain but without the added "ephemera" of a world presented with 10,000 events. As computer systems become more and more powerful, the VRWorld system can provide greater immersion by delivering greater and greater fidelity of events seamlessly.

Tapio:
The system your are depicting would be quite astonishing, but at a
first glance it seems quite a few events would need to be described
in order for it to work properly.

Exactly. The biggest hurdle is creating an event template system to run it all. I'm also working on a way for people to develop "libraries" of events that represent a certain field of interest. Eg you might want to create a medieval set of events, and I might create some more modern events. We both publish the libraries for use by others, so someone could play a game with both libraries in existence. Currently I'm going with a gentoo-like dependency tree to cover this and library updates (the engine also has to be able to merge libraries together into an existing game). To do this, events before the updated date use the old events for a consistent universe, but any new areas that have not been explored can use the updated set. This will allow a distributed workload to develop the event libraries with no hard time limits. I would fully expect there to be libraries to build alternate worlds that are not compatible with each other, which is where the dependency tree is brought in to help sort out the web of libraries.

Hopefully once the engine is up and there are a number of libraries for generating real worlds, this would be a compelling starting point for most games or virtual worlds. Imagine if you could have a world ready made where you could insert specific events to 'pin' certain events to always occur. You can do this by simply providing the event that must occur at the start of the event tree, and use that tree as a start point instead of a totally random one, or generate a random tree from a known seed, then tweak an unwanted event to change an area. Building scenarios this way would be much easier than the current method as everything else (the ephemera) you get for free. So saving one seed and, say, 15 events allows you to create a custom scenario inside a consistent and coherent random universe.

Hopefully the first demonstration of this system will be the HistoryMaker; a (possibly web) program that will give you the top 10 events of a country as described at the top of this article. This demo will simply need events to do with countries and major characters and I would expect only 20-50 event templates to give a sufficiently varied history. The test will be to look specifically for causality breaks and to test exploration paths that develop 'interesting' stories.


HistoryBuilder
I'm also working on a project to do almost the opposite. I want to track every single action that a player does in UnAngband or WoW and produce an XML file that can be parsed to produce a story of the character. The idea is to isolate what events are significant to make an interesting story upon reading back. You may not want to say that you went, left, left, left, or that you killed a monster each time it happened, but you might want to have a greater significance when you reach milestones (have gone 10,000 steps, killed 25 rats). This app will help get a bearing on all the events capable in a typical game that you would expect to be evident in a world and their relative weighting.


Creating "Fun" Maps
A new article by Steve Segreto placed up on roguebasin discusses a way to procedurally create levels based on 'Fun'. It turns out that he's developing the same type of algorithm, but from a different perspective again. This has certainly been the closest I've seen to design by importance, and with the binaries I'll be spending some time testing how this method fares in providing 'interesting' maps.