Saturday 26 April 2008

The spread of knowledge in a large game world

part of the role of Dandelion, in The Witcher games,
is to provide the player with news
These days we have television, and news. But in a late bronze age world there are no broadcast media. News spreads by word of mouth. If non-player characters are to respond effectively to events in the world, knowledge has to spread.

How to model this?

Some non-player characters - doesn't need to be many - are news-spreaders. News-spreaders need to travel. They have to travel even when there are no player characters in the vicinity. But, they don't have to travel very often - once or twice every game day. When a news-spreader is in the immediate vicinity of another character, the pair may (with some degree of randomness) exchange news. There needs to be a hierarchy in the exchange of news, so that 'I-saw' events need to be more likely to be passed on than 'I-heard' events; there needs to be a counter which counts the number of times a knowledge item has been passed on, and also an age counter so that knowledge items are less likely to be passed on as they get older.

One obvious class of news-spreader is a merchant. Merchant agents can either shuttle mechanically between a fixed group of markets or else possibly respond intelligently to supply and demand. Provided that there is a mesh of merchant routes covering the markets of the game world, and that a useful subset of non-merchant characters are required to visit a market every few game days, this should give a reasonably realistic framework for news spreading.

What else? What things qualify as news items? I think at least the following:
  • Deaths of sentient characters, especially if violent
  • Commodity prices
  • Changes of rulers in cities
  • Marriages of sentient characters
  • Plot events, flagged as events by the game designer
Obviously, news is more valuable if the people involved are important or notorious: the significance of a story is probably the product of the significance of the people concerned.

So a news item becomes a tuple

(days-old nth-hand significance action (actors))

for example

(54 2 10 'killed '(fred joe))

meaning 'I spoke to a man who'd spoken to a man who said he saw notorious fred kill well-liked joe on 54 days ago'. Obviously, the non-player character must be able to construct a natural language sentence from the tuple when speaking within the hearing of a player character, but there's no need for a non-player character to produce a natural language sentence for another non-player character to parse; instead they can just exchange tuples.

But if we're exchanging knowledge between agents, then agents must have a means of representing knowledge. This knowledge is an association between subjects and sets of statement, such that when the agent learns the statement

(54 2 10 'killed '(fred joe))

it adds this statement (with the 2 incremented to 3) to the set of statements it knows about fred and also to the set of statements it knows about joe. It's possible that the receiving agent could then challenge for further statements about fred and/or joe, the automated equivalent of a 'who's joe?' question.

There could be feedback in this. Fred's and joe's significance scores could be incremented for each character to whom the statement is passed on, increasing the likeliness that fred, at least, would feature in more news stories in future. There needs also to be some means of managing how the non-player character's attitude to the subjects of the statement are affected. For example, If fred kills joe, and the character (say bill) receiving the news feels positively towards joe, then bill's attitude to fred should become sharply more hostile. If bill feels neutral about joe, then bill's attitude to fred should still become a bit more hostile, since killing people is on the whole a bad thing. But it bill feels very hostile towards joe, then bill's attitude to fred should become more friendly.

Obviously the rate of decay, and the degree of randomness, of the news-passing algorithm would need to be tuned, but this schema seems to me to describe a system with the following features:
  • Non-player characters can respond to questions about significant things which happen in the world - without it all having to be scripted
  • If you travel fast enough, you can keep ahead of your notoriety
  • Characters on major trade routes will know more about what is happening in the world than characters in backwaters
This seems to me a reasonably good model of news spread.

Scaling of the algorithm

Let's work around the idea that a 'game day' equates to about two hours of wall clock time. Let's work around the idea that there are of the order of fifty markets in the game world, and that for each market there are two or three merchants whose 'home base' it is.

Obviously non-player characters who are within the vicinity of a player character have to be 'awake', in order that the player can see them interacting with their world and can interact with them. Those characters have to be in working memory and have to be in the action polling loop in any case. So there's no extra cost to their gossiping away between each other - around the player there's a moving bubble of gossip, allowing each character the player interacts with to have a high probability of having some recent news.

But the merchants who aren't in the vicinity of a player don't have to be in working memory all the time. Each merchant simply requires to be 'woken up' - loaded into memory - once per game day, move a day's journey in one hop, and then, if arriving at an inn or at a market, wake and exchange news with one resident character - an innkeeper or a gossip. So the cost of this algorithm in a fifty-market game is at worst the cost of loading and unloading two non-player characters from memory every minute, and copying two or three statements from the knowledge set of one to the knowledge set of the other. If you're dynamically modifying significance scores, of course, you'd need to also load the characters about whom news was being passed on; but this still doesn't seem unduly onerous.

Obviously, if memory is not too constrained it may be possible to maintain all the merchants, all the innkeepers and all the characters currently being talked about in memory all the time, further reducing the cost.

Friday 4 April 2008

Worlds and Flats

Of Compartmented Worlds

Playing The Witcher has got me thinking again about an algorithm for rendering a world which I first thought of twenty-five years ago. Then, it was a hack for dealing with the fact that the computers of the day didn't have much memory or horsepower. Now, it's a hack for dealing with the fact that - when considered against the complexity of a world - the computers of today still don't have enough memory and horsepower. Mind you, today I'm contemplating photorealistic scenes, whereas then simple line and wash would have been good enough, but...

The algorithm for rendering I'll call 'flats'. But before we get to discussing flats, lets discuss worlds.
The world of The Witcher (and other games based on the Aurora engine) is composed of areas. One area is loaded into memory at a time; when the player reaches an area boundary, the area is unloaded in toto, and the next area loaded, also in toto. The result is a noticeable interruption in game play. There's also, normally, a noticeable visual disjunction at the boundary; the new area uses a different 'tileset', which is to say, set of bits of scenery. When you look across a boundary, the scenery often appears different from what you find when you cross the boundary and arrive at the other side.

Finally, you can only cross boundaries at specific gateway points. For example, Chapter Four of The Witcher takes place in a continuous rural space composed of three main areas: the lakeside, the village, and the fields. Between the lakeside and the other two regions there's a wooded escarpment, which provides some logical justification for the fact that there are actually only two places you can actually cross it - from the lake shore, either up the road to the village or else through a series of glades to the fields. But between the village and the fields there's no such logic. There are a pair of gateposts, and you must cross between those gateposts - but the landscape appears continuous, with no visible barrier. It's an artifact of the game engine.

So, how to deal with this?

My interest, let's be frank, is in story telling; and the nature of story telling is moderately constrained plots. In computer mediated story telling the reader/player can and should be able to explore the plot in his own way, make his own choices, take his own path through the environment, encounter the elements of the plot as he encounters them on that path, and it's the job of the story teller to make that engaging whatever path the reader takes. But if the reader chooses to ignore your hints and wander out of the area you've populated with plot altogether, there's two things you can do. One is put up physical barriers which stop him (although the silly field fences in Chapter One of The Witcher do /not/ count, as it's obvious that Geralt could simply hurdle them; they are just another artifact.

Of Finite and Infinite Worlds

But an infinite world is not required for the sort of stories I'm interested in; the sort of stories I'm interested in take place in, at best, regions of infinite worlds. Just because I don't choose to use all of it, of course, is not a reason that a world should not be infinite.

There are plenty of fractal mathematical equations which map an infinite three dimensional surface with landscape like features. If such an equation gives you land heights, then altitude, steepness and orientation will give you soil type and vegetation cover. There is no need to store a whole world in order to be able to reproduce it exactly when the player follows the same route through it for a second time; it is sufficient to start with the same seed. So a world need not take up vast amounts of disk space for pre-mapped scenery; scenery need only be mapped as it comes in sight. This is fundamentally the trick used by Elite to pack a large, reproducible universe into less than 32K of RAM, and it still works today.

Of River Systems

However, there are reasons to prefer that a world be pre-mapped, at least at coarse grain. One example of why is river systems. It's trivial that we render a river at the bottom of a valley, but it isn't trivial to compute how wide and deep that river should be. To calculate that we have to explore the extent of the watershed upstream of any given point, and sum the rainfall on it, which in turn is a factor of exposure to prevailing airflow and the proximity of ocean to windward. It's computable, but it's much more efficient to compute it once and cache the results, especially since for any given river system it's a recursive function.

Furthermore, rivers cause erosion, changing the landscape through which they pass, cutting gorges on steep slopes (especially if soft), building up flood-plains in flatter areas downstream. Some fractals are naturally extremely landscape-like, but it seems to me - better mathematicians might prove me wrong - to realistically render river systems requires some degree of post processing, and post processing which would be expensive to do repeatedly in realtime.

Of Human Settlement

Human settlement is a separate issue. Many years ago I wrote a program which modelled the spread of human settlement over a landscape.

Human settlement is not random. Human settlement follows rules and patterns. Pioneers settle in places which have a sufficient spread of resources to meet their year round needs; they settle near to easy routes from their parent settlement. Pastoralists need grazing land and water; they spread up river systems, but avoid marshy areas. They settle where there is open grazing, but often close to a forest edge for access to timber. Second wave settlers prefer to settle close to existing settlers, for mutual protection and help. Cereal growers join these settlements where the depth of soil is optimal for crops. As the settlement grows and pressure on land increases, the forest edge is cut back both for building material and to increase the available agricultural land. If a settlement fails, the forest may reclaim this land

Road networks develop. People travel between settlements by the easiest route - but the very fact a route is travelled makes it easier. A path gets cleared; later, people fill in boggy bits and bridge streams, to make their own passage easier or to encourage trade through their lands. Because as a road grows more important, so the settlements along it grow more important, and as the settlements along it grow more important so the roads between them grow more important. The road network, then, is a dynamic fractal which interacts with another dynamic fractal, the distribution of human settlement.
The program I wrote was a cellular automaton which modelled human settlement in only thirty states. It did a remarkably good job. Settlement would spread across a landscape; settlements in strategically beneficial areas would grow faster, develop temples and markets sooner, and thus become important foci of the roads system; other settlements would wax and wane, some falling into ruin; new waves of settlers might settle in slightly different areas.

More states would be better, give a richer, more subtle model, But this demonstrates that it's easy to design a program which will settle a landscape in a realistic way automatically. Once again, though I think it can be done more realistically if it is precomputed and cached rather than if it is generated from the landscape fractal.

In summary: yes, I think it's possible to have an infinite world which is satisfying and can be reproduced at will from a seed, but the stories I want to tell do not call for infinite worlds and if the world is finite I believe it can be made still more satisfyingly realistic by pre-computing and caching things like river systems, afforestation and settlement patterns. Either way, though, the world can be very large - much larger than the worlds of current near-photo-realistic games. The world of The Witcher, for example, is a few hundred hectares; I'm envisaging storing hundreds or thousands of square kilometres in similar data size and with a similar expenditure of artist's effort.

Rendering, and the Flats idea

Rendering a convincing distant view in computer-generated virtual environment is hard. There's an enormous amount of data in a distant view, and if the viewer is moving in real time it becomes computationally unaffordable, even on machines with a great deal of horsepower. Games typically work around this problem by either angling the camera downwards, or else rendering a high degree of atmospheric haze - it's always slightly foggy - so there is never a distant horizon.

Movies shot in studios often have wonderful, detailed backgrounds to their sets. Vistas of far mountains and great cities... of course, the far mountains and great cities don't exist in the set. They're painted on large canvases called 'flats'. The flats illusion depends on the camera not moving too much, because of parallax - nearer things should appear to move relative to further things, and on a flat they don't.

But. But.

For a player moving in a computer game the field of view is quite restricted - it's no more than thirty degrees, typically straight ahead as he moves. Parallax movements are less significant straight ahead. A single flat still isn't going to work, but in many animated films a system of multiple flats is used, with the nearer flat moved relative to the further flat to give an illusion of parallax. This can work very well.
Suppose one projects onto the world a hexagonal grid - it doesn't have to be hexagonal, but I think that is likely to work best - with a cell size of about 100 metres (the exact cell size depends a bit on the speed of movement of the player, for reasons which will become apparent). Cells are grouped into metacells of seven cells (if square, then metacells of nine cells). For each cell, there are six inner flats. Each inner flat consists of a rendering from the centre of the cell of everything more than one cell distant, but less than five cells distant, over a 60 degree arc of view.

For a given area of the world the distant view doesn't change very much. We don't, therefore, have to compute a set of outer flats for every cell, just for every metacell. The outer flats each consist of a rendering of the scenery more than one whole metacell away, from the centre of the metacell.
To render a scene, then, we first paint the outer flat for the metacell the player is in, in the direction the player is looking. Over that we paint the inner flat for the cell the player is in. Over that we render the actual objects in the adjacent cells which fall within the viewing area. Over that we render the objects in the current cell. Thus we only have to render in real time certainly no more objects than can already be rendered by systems which clip for distance either by angling the camera down or by using fog, and yet still manage a realistic distant view.

Rendering the Flats

OK, so when do the flats get rendered? After all, if you're going to pre-render six full colour full screen resolution flats for every hundred metre cell in the world, then either your data volume is going to get enormous or your world is going to get pretty constrained - which was just what we were trying to get away from. And if you're going to multiply that with flats rendered for every time of day and every weather condition - well, it's not feasible.

You cannot realistically pre-render the flats, in my opinion. Or if you can, you're going to have to give them so much real time post processing that you will lose the benefit. Pre-rendering the flats is not the idea. But if they are rendered in real time, where is the benefit...?

There's a middle way. Running straight forward at top speed a player crosses a hundred metre cell in about a minute, during which to give an illusion of continuous movement at least nine hundred full screen frames must have rendered. But the flats don't change in a minute. The flats don't change in five minutes. They don't need to. Even if rain clouds are sweeping across the landscape, it's OK for the distant view still to be sunny five minutes after the rain reaches you, or vice versa. If you can render a high proportion of the detail in a view only once every nine hundred frames, you've saved a lot of processing.

So there is a continuous background process running which renders flats. It does it all the time. It prioritises making sure that a flat exists for every direction the player may look in in the next minute - that is, every direction from the cells and metacells he's currently heading towards. Having done that, it renders flats for cells to either side which he might turn to. It maintains in memory a small stock of flats from recently visited cells, so that if the player turns back they don't have to be repainted in a hurry; and if a flat is more than about five minutes - 4,500 frames - old, it may repaint it to update time-of-day lighting or weather effects.

Obviously, quite a lot of the time the join between two adjacent flats will be in view. I don't see this as a problem. Just naturally, the rendering of the flats should essentially form segments of a hoop, so the join between two adjacent flats should not be perceptible.

Artifacts

Inevitably, there will be undesired artifacts of this system. Significantly, mobile objects - 'non-player characters', the avatars of other players, monsters and computer mediated creatures in the landscape - more than two cells away will not be visible. The flat is static, so it can't have moving characters on it. There may be some algorithmic way round this, since one hundred and fifty metres away is rather close for people to suddenly vanish; but it is not a problem I have a solution for.

Again, if the player is looking sideways as they cross a metacell boundary, there will be a jarring sudden shift in parallax. I acknowledge that and think it just can't be helped; that the benefits in terms of quality of view for given computer power, will render it acceptable.

Creative Commons Licence
The fool on the hill by Simon Brooke is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License