[Freeciv-Dev] Re: map generation

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

Hi Karen

Good to see you back in an active mode ...

At 08:48 PM 02/05/30 -0400, Karen Yeats wrote:
>Hi I haven't been following the mailing lists for many months now so I
>wasn't aware of what has been going on in map generation lately, but I am
>most definitely interested in climate based modelling and generators in
>general (as in the thread by the name of "I have written a new terrain
>generator").  Cameron Morland and I were at one point working on climate
>change for use throughout the play of the game (think of how the
>increasing desertification in the middle east has affected the history of
>civilisations).  I don't think I have any code hanging around from that
>attempt but I'm certainly intersted in related projects.

Good. I think map generation suffers from two main problems, critical mass
of (active) interested people, and a strong resistance to changing the
core map generators used by the competitive gaming servers.

Modular map generation may help on both those fronts by allowing for
selection of everyone's favorite generator style, and making it easier 
to develop and get new ones introduced.

>In response to <http://arch.freeciv.org/freeciv-dev-200204/msg00544.html>
>could someone point me to the threads on increasing the modularization of
>map generation?  I'm having trouble finding them.

There are scattered emails around Dec-Jan 2002, and another a few months
earlier, but there is no real "thread" - c.f. points 1 and 2 above.

>Also my fractal hightmap generator can easily do topologies (trivially the
>orientable ones and I could without difficulty modify it to any
>nonorientable ones that you might have implemented), is the topology work
>documented in a single place somewhere, or do I simply have to read all
>the past threads on it?

Jason and I have argued the main points out both online and offline up
until January or so. There are two prototypes, the corecleanups and the
general-topologies patches. The significant rearrangement of mapgen.c
functionality is still just in the corecleanups.

I would recommend installing a base Freeciv of appropriate vintage and 
patching it with either or both of these to experiment on until topologies 
gets going again with a current CVS patch after the release.

But in reality, mapgen is largely independent of most things, and work
on modularizing and developing components to it can be done without
topologies or any other precursor, and retrofitted without too much
effort. It helps to understand what changes are topology neutral, or
what macros build in this capability to make this step easier though.

I typically use the corecleanups patched with civworld and use its 
mapgeneration functions and parameter controls to drive mapgen when I 
am developing in this area. 

>On the subject of modularization I had some ideas of my own which I was
>planning to pass on until I noticed the above reference to an earlier
>discussion.
>
>Following is what I had planned to send on modularization, now it is
>certainly subject to changed based on whatever has already been discussed.

The field is still wide open, and any ideas like this are certainly welcome.

>Map generation ideas:
>
>Hello.  This is a vague proposition at the moment but I hope some of the
>other people interested in map generation in freeciv could give me some
>feedback on the idea

Ok, I'll try to give both comments and also see if I can recast your
ideas from a different perspective in some cases. My apologies if the
perspective shift is too big a jump. I will try to hang some examples
off things to see if that helps crystallize the concepts and 
relationships.

>First of all:  I would like it to be as easy to use a different map
>generator as it currently is to use different tilesets.  I think this is
>useful because different people like significantly different things in
>maps (as some comments from the thread "I have written a new terrain
>generator" from earlier this month point out) so it will be difficult to
>come to any consensus on what is a good generator, and also (the selfish
>reason)  because I play freeciv in part because I like exploring the
>worlds so having easy access to different map generators is important to
>me.
>
>My first question is whether this idea is generally agreeable to people?

I don't think anyone objects to more *free* choices. The implementation
or packaging of how it is delivered, specifically who loses in the
tradeoffs may provoke endless discussion.

Various maintainers have expressed neutral or positive sentiments about
these sorts of changes. I think there is room for both minor changes to
the current system and a major overhaul as long as it doesn't trigger
serious changes to or objections from the status quo. Concrete prototypes
or patches are probably the gating criteria.

But I will let the maintainers speak for themselves as the definitive
anser on this.

>The next questions concern how to do this.  Since generators are code it
>is not as obvious how to best implement such a system as it is for
>tilesets.

As a general response to this there are several main approaches.

1)  Design general purpose map generation modules that take ruleset 
    parameters. Fold all new generation elements into these as minor
    code extensions (to a generic interface) plus selection elements.

2)  Design a system for loading and selecting complete modules or 
    submodules, i.e. a high-level interface to get started only. This
    typically means including preset libraries, but might be extended
    to dynamic loading.
    Imbedded interpreters might be an intriguing extension for one
    type of module that would permit controlled customization through
    scripts.

3)  Design standalone map generators that interact through the system
    via savegame maps. A simple commandline driver can run these
    from the server using fork and exec, or maybe as a more sophisticated
    interaction through an interactive pipe.
    Building this into a map editor like civworld is an obvious way to
    prototype and develop the basic system without disturbing the people
    addicted to the current core server functionality.

Note, none of these are really mutually exclusive, and reflect more a
different level at which things can be hooked in.

The various make_plains(), make_fair(), etc. elements of mapgen are a
crude example of 1). The tiny_isles shows selection techniques.

The basic mapgenerator1-4 selection is a crude form of 2).

Helge's program, and civworld generation is a start on 3) with manual
loading via civserver options the current interface. Adding an option
to run a shell command stored in the server startup file or wrappering
the server command in a shellscript to do map pre-generation isn't hard.

>Conceptually map generation currently and I think sensibly is divided up
>into 3 parts, hightmap generation, terrain placement, and assorted cleanup
>and game preparation (which as it stands includes putting on huts,
>assigning continent numbers and starting positions (if not already
>determined) and arguably adding specials, removing tiny islands and "make
>passable").  I think generic code for the last of these would be adequate
>(the current starting position algorithm is weak, but that doesn't mean a
>good generic starting position algorithm couldn't be developed, perhaps
>it has, or perhaps I will later), however I think it would be useful to be
>able for the user to specify their choice of hightmap generator and
>terrain placer.
>
>Does this division seem right to people?

This is a reasonable way to begin breaking down case 1) functionality,
and to start codifying the interfaces for the breaks.

Mapgenerator1 is actually pretty modular. The various steps have a few
interdependencies like needing a heightmap for any make_<terrain>
calls. But it is easy enough to start listing the global elements that
each current module requires, and what it outputs. Rough orderings as
A must come before B or should come before C will follow from this.

What is missing is a selection system for modules in the mapgenerator
core functions to replace the sequence of hardcoded calls. An option 
list for each selected module would be nice as well, though the general 
map parameters are probably good enough for the moment. They should 
probably always be there as core defaults if not overridden, anyway.

>Assume we have distinct entities doing these two things.  What should be
>the format and content of the information passed between them.

It depends on the level at which the hooks/interfaces go in.

General rule is to make the interface pass the minimum amount of info
or lowest common denominator set. Opaque data structs or references
to typed data suppliers keep the interface generic but flexible.

As a specific example, most of the current modules take no arguments
and read data from a well-known supplier (i.e. global memory :-), 
possibly through various well-known helper functions. Admittedly the 
latter is a rather poorly structured supplier or interface.

>The hightmap generator needs to be passed the size of the map, the
>topology (when that comes into effect), and the number of countries (only
>some generators use this).  It needs to return a hightmap and an optional
>list of starting islands.  This can be returned in a format not unlike
>the save game or scenario formats since code already exists for them,
>though if they are unideal for some reason something else could work too.

I suspect that every parameter visible in the savegame needs to be
reflected in one or more key in-memory map structures. Each of these
structures should ideally have a set of functions that one uses to
query and update the data for longterm encapsulation and flexibility.
But the definition of the structs can be part of the interface with
direct access used as a first pass.

This should be grouped (at least conceptually) as a "model data store"
that any modules can access or manipulate. The current data store can
be passed in as an environment structure collecting various references
rather than an undefined set of global references to start isolating
and codifying the key interfaces.

The model data store defines the globally known interface elements.

All module communication should largely go through this channel with
modules looking up the data they need, rather than being passed specific
instances. In type 3) cases the model data store is the savegame and/or
its in-memory cached representation.

What this means is that one module needs to update the global data
then call a second that reads what it wants from this source. Neither
module should need to know exactly what the other wants, only what it
wants and produces. Thus it is very easy to develop modules that only 
interact with the model store and yet have them mix and match in a 
wide variety of combinations. If you add a new module, you don't have 
to update the calling interface in any pre-existing ones.

For map generation, "temporary" elements like the heightmap, or a list
of island submaps (i.e. as generated by mapgenerator2-4) can be added
to this globally known interface and store. A civworld "module" or 
method might allow one to pick up one of these islands, rotate it,
and drop it into the main heightmap - or maybe merge it with a second.
This sort of mix and match capability would be quite easy.

Analyzing the input requirements and output results of modules as you 
are starting to do here will help produce a tentative set of the
elements they use or interact with that can be analyzed further for 
global nature (or only need be known to a sub-hierarchy of modules), 
init and cleanup factors, plus the various functions or updates one 
is allowed to perform on them.

This is starting to lead one to the idea of key objects with a given
lifecycle and set of permitted operations. Modules then manipulate
these in various constrained ways, in a given selection sequence to
complete a map generation cycle.

The other aspect here, is that by identifying these elements in the
existing code, or the places where they are missing or need work, one
can "evolve" the current system to this goal. Evolving for me means
one gets to play as one goes along, rather than waiting for the final
ultimate solution to be built from scratch.

>the terrain placer needs to be passed the hightmap and the land type
>percents and the topology.  It can return a map in the same format as a
>save game.

This is exactly the sort of analysis one needs to capture the global
elements and constraint conditions for the selection order. Doing a 
module list and index card description of each module's main 
requirements and features would really pin down things to practical
reality.

>Finally how exactly to implement.  Here I am particularly open to
>suggestion/correction since the interplay of different things in a large
>programming project is not an area of expertise of mine.  My thought is to
>have separate files which compile to separate binaries for the hightmap
>generators and terrain placers which can be referred to by name as server
>options and would be called by a function inside mapgen.  A clear
>interface specification could be created refining the basic ideas above.

Maybe some of the earlier examples will start to show the shape from one
perspective. There are suggestions of the next steps to start blocking
out and filling in the outlines of the general breakdown elements. 
Fractally applying the analysis and breakdown process to each element 
in turn will eventually fill in the whole picture :-).

>Does this make sense?  Would there be a better way to do it?
>
>I don't at the moment know how to make C programs talk to other programs
>in this way.  I am interested in having this sort of functionality though
>so I am willing to learn.  However if someone is interested who does have
>this expertise I'd be happy to let them do it.

If you want some academic background on a fairly straightforward way to
go about this that has lots of modular examples, the concept of a global
data store, a way to retrieve or view its data and a way to update or
schedule updates to the data, then this is the Model-View_Controller (MVC)
paradigm. I tend not to be pedantic, but like to borrow concepts or
analogies from well-known development pattens like this as ways to 
approach problems. Then I apply a very fuzzy practical implementation
to do what I think I need.

The key communication elements are data request and update operations, 
plus event or control signals to the master control loop. In a crude
way, all you need to do is read and write data structures from and to 
any particular data channel, with some idea of message target and/or
message type index headers.

Writing out a savegame==message to a file and sending a process signal 
to a given pid==target to have another program read it in fits this model.

Writing out a savegame==message to a pipe==implicit target that another 
program is listening on using its loadgame routine is another 
implementation.

int execvp(const char *file==target, char *const argv[]==message)
is a way to send a signal to a program with the given string args as
the message.

The Freeciv packet protocol used between client and server is another
example that handles a fairly rich set of messages containing events 
and data store updates.

When communication is needed, it shouldn't be too hard to fill in the
appropriate piece.

Cheers,
RossW
=====