Archived

This topic is now archived and is closed to further replies.

Random world generation idea

This topic is 5742 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have an idea that I will probably never get around to implementing, so I thought I''d mention it here and it might spark up some conversation. Basically, the world is made up of containers with a bunch of random child-containers. These children containers would also have children. And so on... As a simple example, say you''re modelling a flower-bed. The bed would randomly choose a selection of flowers to put down. Each of the flowers would randomly choose a placement of leaves and petals. The petals themselves would be randomly modelled as well, but would probably be the bottom of the heirarchy. If we could do this on a bigger scale, very complex environments could be created at the click of a button (and 1 random seed). How affective would an automatic LOD scheme go over? Has anything like this been done before? Do you see any major problems with the idea?

Share this post


Link to post
Share on other sites
Your idea is interesting, but doesn''t it take all the fun out of designing worlds on your own? A good game''s storyline and gameplay must reflect its environment, and I don''t see how a randomized environment could reflect anything. On the other hand, it sure would save a lot of money on development...

Share this post


Link to post
Share on other sites
I am also interested in world generation. I did a great deal of searching on the subject, the majority of hits consisted of something along the lines of dice rolling for various paper RPG''s. A few others would generate various statistics of a world, but nothing else. Aside from those, there were a few fractal algorithms to generate heightmaps for terrain from fractal and other algorithms, then do certain modifications to them for realism. Water levels, etc.

What I haven''t seen and would like to is something that can also:

Do vegetation levels and types based on predicted climates ( based on which you could employ another semi-random system to place actual objects )

Do some kind of processes to represent erosion, plate movement, mountain range formation, etc. ( natural geological processes )

Do simulation of bodies of water other than what would result from world-wide ocean levels. ( would possibly tie in with/be the same thing as a system to handle erosion ) IIRC, roads can be generated from repeated pathfinding and average paths, so, the same could probably done for rivers, using a heuristic that favors downhill travel instead of level travel, correct?

once you''ve done the above,a nd a few other things I''m sure..to figure out the geology of your world, you could use pathfinding to find where roads and paths would be, place cities at crossroads, etc.

Does anyone have suggestions on any of this? What programs to use, what processes would be necessary to do such things?


Share this post


Link to post
Share on other sites
quote:
Original post by Rian
Your idea is interesting, but doesn''t it take all the fun out of designing worlds on your own? A good game''s storyline and gameplay must reflect its environment, and I don''t see how a randomized environment could reflect anything. On the other hand, it sure would save a lot of money on development...

Although the world could be totally random, you can start at any level you want. If, say, you have a good house container, you could plop a bunch of them around and you have a town. Each house would look like it was pain-stakingly modelled. You could pass parameters to the house to get it in the style you want. When it''s close, they could be hand-edited. Plop a chimney container on the top, a fireplace inside, and voila! Obviously each of these containers would have to be created (no small task), but once completed there would be infinite configurations. Or, build a house out of wall containers, which have crack containers.
I''m thinking the worlds this could make would be vast. So vast that no small group of artists could model it all, unless they severely cut back on detail. Another way of explaining it is, if you were only going to use 15 houses, you could model them all individually and get good results. Making a house container may be a waste of time, and the results not as good. But if you had 1000 houses spread around your world, each one different and very detailed, that would be an interesting world to explore. Modelling them all to the same detail would be impossible.

Share this post


Link to post
Share on other sites
I have also put some thought into this subject. I personally feel that as for the idea that the randomness of the terrain wont respect the story line, it could if you implemented it right...

Take your average shooter scenario.

-Our hero runs into a room with gun totting.
-Every time ''whatever.level'' loads the furniture or your enemies and misc details like say a telephone are in the exact same place every time you attempt the level.
-The generic *structure* to the room could remain the same i.e. there will be the same exits in the same place every time, but the guy you thought was hiding round the corner or behind a door may or may not be there, may or may not be carrying the same weapon, and may or may not look the same.
-Story elements could be subtely tweaked i.e. a switch which you need to find could randomly cycle between locations specified at design time. (adding to the puzzle)
-Like it was mentioned earlier certain building structures could be customised yet remain faithful, i.e. you have an area full of buildings (trainyard/city/industrial area) and a specific building the player needs to navigate to. This building could be say a place where they need to cut the power. It could be moved to specfic or random points, rotated, transformed, internally randomised, and then every time you play that level it will need to be done so without any prior knowledge of the layout!

A good example is say (keepin'' it ol'' skool) DoomII Level1 on Ultra-Violence, I do know, will always know, will never not know that at the very end when I open that door there will be an imp there- it will give the almost qued growl and then its dead. (wheres the challenge?)

I think this will actually evolve the way levels are designed not handicap them. Developers will still mould detailed rooms but the rooms placement will need to be thought out harder and with greater consideration.


If i ever become any good at what is now just a hobby, I intend to take games further with this.

Share this post


Link to post
Share on other sites
Hi, I've been lurking on this forum a while, didn't get around to register until I saw this interesting topic and I got to thinking...

Your mention of flowers made me remember screenshots I saw of the game Republic (several years ago, and it still isn't published). The first shot was an overview of a big complex-looking city, the next shots zoomed in on one particular multi-storey building, until only a windowpane on one of the upper floors and a rather detailed potted plant was visible. Cool!

IAMNAGD, but I think a randomly generated, recursively defined world could solve the problem of increasingly expensive level-design. When id made the first Wolfenstein, I think they were about 10 people incl. coders and artists, that game had 60 huge floor. Return to Wolfenstein took a much bigger team several years to develop and from what I've heard there's about 15 levels, each of which can be completed in average half an hour. (I never completed more than about 1/4 of the original Wolfenstein 3D, in case you wonder :-). It's of course due to the much higher level of detail required in games today, so some way to autogenerate detail would go a long way. A level designer could generate a random city, tweak some parameters until it fits the broad outlines of whats needed, then manually edit the places most relevant to the narrative of the level.

One way I could think of to represent objects from which to autogenerate a world:

class Object {
Array<triangle> triList;
// Our object consists of a bunch of textured triangles...
Array<ChildObject> childList;
// ...and a bunch of component objects.
float size;
// Width on screen in pixels when in view and camera is 1000 units away.
// So if an object is z pixels from the camera it will be *approximately* size*(1000/z) pixels across.
// Used to determine which children are too small to see
// The distance of 1000 units is kind of arbitrary. But it should be >> any objects size.
}

class Triangle {
Point p1,p2,p3; // Coords relative to parent origin.
Texture t;
}

class ChildObject {
Matrix m;
// Displacement, scaling and rotation relative to parent origin
int limit;
// when parent is less than limit pixels across, this child is ignored.
Object *o;
// Could theoretically point to parent :-)
}

An Object for generating a city would have a triList only containing a big flat grass-textured square, and a childList containing one thousand buildings. Alternatively a city could be a list of 10 neighbourhoods, which each has a list of 10 blocks, which each has a list of 10 buildings.

The one thousand ChildObjects could point to the same building Object, just with different translation matrix , but about fifty different building Objects should provide enough variety. The fifty different Buildings could share a lot of components. A building should have a triList describing walls and roof, and a childList containing doors, windows, chimney, rooms. A window Object would have a childList containing frame, panes, and the flowerpots. A flowerpot object would contain several flower ChildObjects, the flowers several petal ChildObjects (most probably pointing to the same petal Object) etc.

An element of randomness could be introduced with some more elaborate classes. The position of a house can be used to generate a seed to a random number generator. The generated random number 0 < x < 1 .

class Object; // is now an abstract class
class SimpleObject : Object { // same as old Object declaration
Array<triangle> triList;
Array<ChildObject> childList;
float size;
}
class StochasticObject : Object {
Array<SimpleObject> soList;// List of Objects that could appear as a component here.
Array<Float> p; // Probability for which of these objects to pick. If p[i-1]<=x then soList[i] is used.
// Eg if p=(0.25,1.0), theres 1/4 chance that soList[0] will be used and 3/4 for soList[1].
}

class ChildObject {
Matrix m;
int limit;
Vector jitter; // The position of this component will be translated by x*jitter.
// Eg if jitter=(1,0,0) the position of this child can vary 1 unit along the x axis, but is fixed on y and z.
Object *o;
}

This way each rendering of the same house Object will subtly change depending on where in the city it is. One house will have a window with a flowerpot, another defined by the same object wouldn't, one flowerpot will be in the center of the window and full of geranium, another would be to the left and with parsnip. Instead of a "white noise" random number generator one giving corelated values could be used, houses close to each other would tend to look alike, which could be used to create "affluent" areas of the city, and "poor" areas.

If the designer has manually edited some of the houses, their definition (a normal BSP or whatever) is stored in a hashtable with its position as index. Each time a house Object are to be rendered, it will check this table. If it's there, the custom-edited house is used, else the normal definition.

Now rendering this datastructure... Traversing the graph of each visible house and generating world coordinates for all Objects will be too slow, I think. The other extreme is generating and storing triangles in world coordinates for the whole city, and will take too much memory. Some in-between approach should be possible, caching calculated triangles and inserting them into some octree-like structure, doing garbage collection to free memory that store triangles no longer in view. Yeah I know, I'm handwaving.

Ideally such an engine should be able to render a fractal definition of the world.

Say, a 3-dimensional analog (2.5-dimensional actually) to the snow-flake curve: take a equilateral triangle. Create a tetrahedron of 4 triangles, each half as big, with normals pointing outwards, one side (the base) resting on the big triangle, the tip formed by the other three pointing in the direction of the big triangles normal. Now render each of these three triangles the same way...

---------
"It's always useful when you face an enemy prepared to die for his country. That means both of you have exactly the same aim in mind." -Terry Pratchett


[edited by - deformed rabbit on March 23, 2002 3:01:52 PM]

Share this post


Link to post
Share on other sites
Such a technique can be easily used for landscapes.

You start with an empty plane, and choose a height for the four corners, and a height for the center.

_______________
| |
| |
| |
| X |
| |
| |
|_______________|


Now interpolate between the corners, each time adding or substracting a random value.
Continue interpolating, until you have the required detail.

Programs exist that make entire landscapes like this. But I don''t think it''s used in games.

Share this post


Link to post
Share on other sites
Generating random worlds is great, but I don''t really see how you can make a generic random object generator. You can make systems that will generate specific random objects like:
Random plants, random houses, random planets, random universes (just generating the positions of stars though), random towns/cities etc
But having a system that will allow you to create a random anything, would be very hard - interesting idea though - it''d be great if you could get it to work.

John B

Share this post


Link to post
Share on other sites