[MUD-Dev] 2d mapping in SQL

[Matt Chatterley]

Greetings All.

My current project is a multiplayer, web-based trading game. The
question of whether you will truly consider what I envisage as a Mud
or not is an interesting one - my design notes are certainly heavily
influenced by my experience in the mudding world, and I hope to
integrate social aspects into the game which will be reminiscent of
my favourite games. It will certainly be multiplayer, interactive
and fun (that's the point, after all), which to me are three key
attributes.

Anyway. Enough waffle. The current puzzle before me is one which
will be relevant to many of us: The creation and maintenance of a
two dimensional area map.

For my purposes, a static map is unsatisfactory, as it requires too
much maintenance work, too much planning, and because of the
complexity of my design. Also, since I will be "mapping" an area of
'Outer Space', I simply don't want to craft each star and planet by
hand!

On the technical front, all of my data is stored in SQL (MySQL-5 to
be precise, which is entertaining by itself), which gives me the
interesting challenge of representing my objects in a relational
database. So. Without further ado, my current approach:

The map is to be 2d. For the time being, a 3d map has been deemed
unnecessarily complicated (not technically, but from a game-play
point of view). Should the game grow beyond my current expectations,
a future implementation may involve 3d mapping, but for a primarily
textual web-page interface, it is overkill to start with.

Any object, therefore, has X and Y coordinates, markings its
position in space. An object can be anything in the map - a planet,
a star, a space station, or a vessel (fixed or mobile, doesn't
matter). To begin with, we can thus consider the map to be stored as
three columns of data: X, Y and ObjectID (the latter pointing to the
actual object). This is straightforward. What is less obvious is how
these objects should be placed, and the sizing of the map itself.

The map can start at a manually determined size, and I have chosen
to add parameters to the system defining 'limits' for instance
density limits: 'No more than N Planets per X^2 area', and also
distance limits: 'No two planets may be closer together than N'. As
new players join, the nature of the game player (interstellar
trading) will require fresh additions to the supply and demand chain
- essentially, in simple terms, meaning more planets. This
relationship will be non-linear, but I am currently planning to
include a 'Players to Planets' ratio as a further parameter
(defining the minimum number of planets which must be available per
player).

Let us say for arguments sake that Planets must be at least 10 units
apart, and no more than 4 planets are allowed in a 100sq unit
area. The system is configured so that there will be 1 planet per 3
players. An initial map generation routine is run, with a map-size
of 100sq units:

  Map range: (0, 0) to (10, 10) = 100sq units

  Map size = 100sq units, so max_total_planets
    = map_size/planet_limit_area * planets_per_limit_area
    = 100/100 * 4 = 4.


  Planet_1_position = random = (4, 2)

Planet_2 must be at least 10 units away from Planet_1 (let us assume
all minimums are represented by the shortest line from A to B) so:

  dist^2 = x_dist^2 + y_dist^2

  minimum dist^2 = 100

  so 100 - y_dist^2 = x_dist^2.

  If we assign a value of 36 to x_dist^2, y_dist^2 must be 64,
  giving us x+6, y+8, and putting the new planet at (10,10).

My first problem - not a master mathematician, and somewhat
unfamiliar with such routines for placing objects, but, it seems as
though not all the planets are going to fit every time - perhaps
simply the grid should be larger (in which case, a safety clause is
required to determine the minimum grid-size from the parameters,
rather than an admin-specified size).

That aside. Once the grid is created, it will contain four planets
and thus be capable of supporting 12 players. When Player 13 joins
the game, the system will automatically expand the grid, placing one
extra planet at a time until there are enough planets for all the
users (this routine will be run X times daily as a maintenance task,
so may have to cope with many new players at once).

Another parameter comes in here to govern expansion - preferred
density, indicating not just the MINIMUM density per area, but the
PREFERRED density after map creation. After all, we don't want the
entire map to contain clusters of planets at roughly the same
density and distance. The routine will search the map, and if it
finds a region with a density of planets lower than the preferred,
will check if a planet can be placed without violating this
parameter - if it can, it will do so. If this is not possible, the
boundaries of the map will be extended (by a defined growth factor,
either in units, or as a percentile of current size), and the
routine will run again.

I think this idea makes sense - however, it is simplistic, and begs
that I ask a question of you all:

  What about making this a proper model? How might I aim to create
  'clusters' of planets (e.g. solar systems)?

The solar system example is not too bad, I suppose. Parameters such
as those above could govern the placing of suns, and once a sun (or
group of) is placed, a certain density of planets would be permitted
in a given area around that sun-group. This would require a rather
different approach to map expansion, though, since new 'clusters'
would be created (you don't want a new planet to suddenly spring
into existence in an area populated by players - this would cause
mass confusion, and numerous arguments as to whose planet is
blocking the sunlight in whose garden!!).

Has anyone worked with such a concept before, modeling a playing
area in space, and if so, have they found any good reference
material on the topic?  I'm more interested in the playability of
the generated map than it's realism, but still, I don't think this
is going to be dealt with neatly by a simple mathematical routine..

Would some sort of fractal algorithm be more sensible?

Cheers,

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