[MUD-Dev] Generating Cities

[John Arras]

Content generation has been beaten to death before, and I got
interested in trying to make it work about a year ago. I've finally
gotten something that's been in the back of my mind for a few years
has started to get into a working state:


   recursive generation of cities and buildings


In this system, the information about the world is sliced into
strips of meaning by representing objects and spaces of different
scales in such a way that each detail constructs itself, and then
adds more details to itself at smaller scales, until atomic details
are reached.

For example: Suppose that you want a spatula to appear on a cook
inside of a kitchen in a house in a neighborhood in a city.

  You generate a city grid in which you place large regions of
  rooms.

  You create a neighborhood object that will contain houses.

  You create a house object that will contain rooms, such as a
  kitchen.

  You create a kitchen object that will contain people such as a
  cook.

  You create a spatula object that can be held in a hand.

The spatula is considered atomic.

The neighborhood, house and kitchen represent regions of rooms and
the cook and the spatula are in-game mobjects.

Theoretically, you should be able to put as much detail into these
objects as you want, so as time goes on, you can get better
instantiations of these cities and buildings. It should also mean
that any time you get a good idea for something to put into a city,
you should be able to find the proper "place" for it and add it in
there, so it's available from then on whenever you want that idea to
be a part of a city or building.


The code starts with a 3D array of rooms. Several translated
rectangles are ORed in a single XY plane to form the base shape of
the city, and rooms are created on this "street" level of the city
in any coordinate touched by any rectangle. These rooms are set to
depth 1 to act as the target region for the recursion to follow.

Then, a sequence of other details, generally representing regions
like marketplaces, neighborhoods, religious grounds, arenas, or
towers or citadels are added at depth 2. All details inside of each
of these regions or buildings are added at higher depths until the
atomic objects at the bottom of the recursion tree are created.


The core of the code is a function called:

  citygen_add_detail (RESET *reset, THING *area, THING *to,
                      VALUE *dimensions, int depth);

The reset gives the number of the detail object that will be used to
generate the current detail. It is passed this way, because there
are other randomization procedures that allow the code could choose
any one of several detail objects to use as the foundation for this
detail. For example, if the current object is a "tree" object,
instead of making all trees the same, and just differing in name,
there could be several kinds of trees, such as fruit trees and such,
and one of those types could be picked with the corresponding fruit
being created on of the tree.

The area is the zone where all of the rooms and objects will be
stored.  It is checked when new rooms or mobjects are created to
make sure that is has enough space for the new things being created.

The to object is used to determine where this object will "reset"
within the game. It could be a room, such as the location where a
fountain will go, or it could be a magical treasure that gets placed
into a chest.

The dimensions are the min/max x/y/z coordinates within the global
city grid where this detail can be placed. If this is not specified,
there are cases where the object is placed in the "to" object, or
randomly someplace in the area.

The depth is how far we are into the recursion. It is used mainly
for determining how and when rooms can be connected to other
rooms. Generally, at depth N, rooms connect to other rooms at depth
N, and then a few attempts are made at connecting to rooms at depth
N-1, so that there are real divisions between rooms at different
detail levels.

citygen_add_detail has an outer loop that iterates over the number
of times the reset is set to happen. For each try, the reset percent
is checked to see if the reset is added. For example, this makes it
possible to reset 10 bar patrons at 50 percent, to have an average
of 5 bar patrons. Since each bar patron is checked and created
separately, you could generate 5 different bar patrons with one
reset command.

Then, the xyz size of the current object (in room dimensions) is
calculated to see how large the rectangle is that must be fit into
the target region. Mobjects and rooms without dimensions are
considered to be 1x1x1.

The dimensions of the detail can also specify other information
about its placement. If the detail is "stringy", like a road or
hallway, different code is used to determine how it is placed. If
the detail is set to "full" size, then the detail dimensions expand
to the size of the target region (in the x and y directions).

The detail can also be set to appear in the north, south, east, or
west region of its target coordinates. It could also be set to
appear in the "top" or "bottom" of the target area, such as an inn
that has a bar below, and rooms above, or it can be set to be
"above" the target area for things like steeples and towers, or
"below" the target area for things like basements or cellars.

Then, each possible coordinate in the region set out by the
dimensions is checked. Every place where the current detail could be
added "perfectly" with the above constraints is enumerated, and the
places where it could be added "imperfectly" are also
recorded. After all possible locations are chceked, if there are
"perfect placements", one of them is used, otherwise an imperfect
placeemnt is chosen, if possible. If no such place can be chosen,
then the detail fails to be generated.

If the detail is a block of rooms, then its data is generated into a
starting room, and then copied to other rooms in the region to be
taken up by the new detail rooms, as long as those rooms have a
depth equal to the current depth - 1. (So that we only place details
into things that wanted details in them in the first place. -- This
is not *quite* correct, but it's worked pretty well.) Then some
up/down links are added to the rooms contained in the detail.

If the detail is a mobject, then it gets created and set up, and a
reset is added to the "to" parameter for the new object. If no "to"
object is available, then use the randomly picked room from above.

After that, the dimensions of the current detail are recorded, and
citygen_add_detail() is called on the resets of this detail.

Now, if this is a set of rooms, all of the rooms at the current
depth (that didn't get overwritten by finer details) are linked to
each other. There is some code to deal with the case where finer
details split this block of rooms into several components, but it's
imperfect and there's a catchall connectivity algorithm that's
performed at the very end of city generation.  After the rooms at
this depth are connected to each other, some connections are made to
rooms at depth - 1. In this way, technically, the finer details
inside of the current block of rooms should have connected to each
other, then connected to the blocks of rooms at the current depth.

And it all works pretty well. I expect it will take quite a bit of
data entry and tweaking to get it working perfectly, but I'm pleased
with it.

If you're interested, the code's at

  http://www.sf.net/projects/genmud/

and you use the "citygen" command as an admin inside to play with
this.

Finally, although I haven't done 3D work with this, it seems that
these ideas will translate to 3D worlds with trees of blocks
representing explicit XYZ dimensions and positions of the details.

John
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev