Multi-hex tiling

[Dave]

This is a proposal for a multi-hex tiling system, based on a simple constraints system.

The way the system would work is for terrain descriptions to describe sets of constraints for tiles, where if matched, that terrain would use an image other than the normal image for that terrain.

A new element, [tile] would be added as a child of the existing element, [terrain]. It would have a few basic attributes:

- id: a unique 'id' for this tile type
- image: the image to be displayed when this tile is used. May be a CSV list in which case one image will be chosen at random
- adjacent_image: the adjacent images to be displayed when this tile is used. By default, adjacent_image is equal to 'image'.

It would then have a number of [constraint] children. A [constraint] describes a requirement for this tile to be displayed. They contain the following attributes:

- direction: nw,n,ne,se,s, or sw. Describes the tile we are inspecting relative to this tile. If necessary, it could be possible to have directions that span multiple tiles. For instance, nnne to describe the tile two hexes north, and one hex north-east from the current tile.
- terrain: the list of terrains that this tile must be for the constraints to be satisfied. This is a simple list of the letters describing the terrain. e.g. terrain=gf to match 'grassland' and 'forests'. If the first character is a tilde ('~') then the constraint will match if the terrain is anything but the terrain listed.
- tile: the presence of this attribute is mutually exclusive to the 'terrain' attribute. It contains a CSV list of IDs of tiles which the terrain must match for the constraint to pass.

To decrease the verbosity of these declarations, it is also suggested that inside the [tile] attribute, the attributes nw,n,ne,se,s,sw be allowed such that,

Code: Select all

attribute=value

is equivalent to,

Code: Select all

[constraint]
direction=attribute
terrain=value
[/constraint]

While the constraints are being processed, it will be assumed that the tile being processed is the type it is being tested for. This is difficult to explain, so we will use a simple example:

Suppose we want to create a nice looking two hex hill terrain, that spans across two tiles from north-south. That is, if we have two hill tiles, one north of the other, with no other hills around either of them, then we want to use our two special images, hills-north.png and hills-south.png. Any other hills just uses the standard hills images.

Inside the hills [terrain] tag we add the following:

Code: Select all

[tile]
    image=hills-north
    id=hills_north
    sw=~h
    nw=~h
    n=~h
    ne=~h
    se=~h
    [constraint]
        direction=s
        id=hills_south
    [/constraint]
[/tile]
[tile]
    image=hills-south
    id=hills_south
    ne=~h
    se=~h
    s=~h
    sw=~h
    nw=~h
    [constraint]
        direction=n
        id=hills_north
    [/constraint]
[/tile]

The terrain builder will process all hexes on the board, in an arbitrary order (the order shouldn't change the result). When it comes to, suppose, the northern hex of such a hill formation, it will provisionally mark it as a 'hills_north' tile, and then it will inspect the surrounding hexes, and see that they all match the requirements for being non-hills.

It will inspect the hex to the south, which is a hill, but hasn't been assigned an id yet. It will test the south hill to see if it matches the constraints to be a 'hills_south'. Since the hill to the north has been marked as a 'hills_north', the constraint matches, and this tile can also be provisionally marked as a 'hills_south'.

If a constraint arises that cannot be matched, then all provisional markings are removed. Otherwise, once all constraints have been matched, all provisional markings are confirmed.

As far as I can see, this system should match all needs for multi-hex tiling. It should also be relatively simple to implement efficiently.

Comments are welcome.

David

[Boucman]

IIRC there is already a place in WML where you have list of terrains with char, but negation uses "!" instead of "~" you might want to be coherent

[Ayin]

Mhhh okay.

My idea, to implement the same thing, was this one: modifiy the syntax of the [built_terrain] element, to make it support tiles with an arbitrary number of hexes.
The main elements would be the on_terrains tag, which may contains terrain identifiers, or numbers (0-9) which should be matched by a terrain_tile element (my name for elements really suck, I should change them :) )

That should look like that :

Code: Select all

# A big multi-tile castle, hand-drawn. The built_terrain element may
# be present in a scenario.

[built_terrain]
        on_terrains="
*   C   *
  C   C
*   C   *
  C   C
*   C   *"
        background_image="special_castle_bg"
        foreground_image="special_castle_fg"
[/built_terrain]

# The "keep-inside-a-castle" tile, adapted to the new syntax.

[built_terrain]
        on_terrains="
K   C
  C"
        rotations="-ne -e -se -sw -w -nw"
        foreground_image="keep-inside"
[/built_terrain]

# A dragon corpse that may appear on grass or coasts, with a 1%
# probability.

[built_terrain]
        on_terrains="
1   1
  1   1"
        [terrain_tile]
                id=1
                type=gc
        [/terrain_tile]
        probability=1%
        background_image=dragon-bones
[/built_terrain]

Mhh, this is not a real explanation, but I am really tired today :)

[Christophe33]

I think Dave's version offer more flexibility even though I will probably need more example to fullt appreciate it. At first glance it will probably solve most if not all of the questions about the canyon, cliff and other impassable terrain. Will it allows "internal transition". Right now transition is in between two different terrains. When you have to canyon or two cliff terrain near each others, they will need to connect nicely in various way, specially if some people want to make special feature with bifurcation. A way to handle it would be to have some sort of transition between the canyon tiles. The other of course is to have an image for each type of connection and biffurcation. In the second case, will each image require its own character?

[Dave]

Okay, let's have a few examples of 'common usage' so that we can get a feel for Ayin and my proposals. Let's try an example already in the game: bridges. Bridges are done okay in the game now, but it'd be cool if you could just have a 'bridge' tile which automagically selects the correct graphic instead of needing a different terrain type for each direction.

This is actually quite a complex case, despite its apparent simplicity. The problem is that it's fairly difficult to decide exactly which direction the bridge should be going. There are basically four types of terrain possible around a bridge tile:

- water -- shallow water, deep water, merman village, swamp water (?). Canyon/Abyss could also be included in this. Basically the thing the bridge is going over. In this example we'll assume there's just one water type, 'w'
- ground -- all types -- grassland, hills, etc. In this example, 'g' will be the only ground type
- road -- dirt and stone, and other kinds we dream up. In this example, 'r'
- another bridge segment. 'b'

A bridge prefers to go from one road to another. If there's no road around, it'll go from one ground type to another.

Cases:

Code: Select all

  g
 w   w
  b
 w   w
  g

Clearly the bridge is meant to be going north-south in this case. There is ground to the north and to the south.

Code: Select all

  g
 g   g
  b
 w   w
  g

The bridge is meant to be going north-south. This solution makes land on both sides, while any other solution makes water on one side.

Code: Select all

  g
 w   g
  b
 g   w
  g

This is ambiguous. It could be either going north-south or sw-ne. An arbitrary solution would be acceptable.

Code: Select all

  r
 w   g
  b
 g   w
  r

Like the previous example, but with the road going north-south, this is the direction the bridge should also be going in.

Code: Select all

  g
 g   g
  b
 g   g
  g

A silly case, there should be no bridge here at all. A 'default' graphic may be used.

There are also cases with other bridge tiles. A bridge tile would be treated like a road tile iff it is going in the same direction as this bridge.

Implementation:

I realized when writing an implementation for this that my system requires an extension: the 'id' in [tile] tags may be repeated in different [tile] tags -- i.e. allowing multiple cases in which a single tile can be used. Also, [constraint] tags and terrain possibilities may appear in the same [tile] tag for the same direction, in which case if either of them match, the condition passes.

Also, if multiple [tile] tags pass a constraint, the first one appearing will be used.

Code: Select all

#if there is bridge going in the same direction or road to the north and south,
#then that is an automatic n-s bridge
[tile]
id=north_south
image=bridge-ns
n,s=r
    [constraint]
    direction=n,s
    id=bridge-ns
    [/constraint]
[/tile]

{repeat previous for ne-sw and nw-se}

#next choice is if there is road or bridge on one side, and ground on the other
[tile]
id=north_south
image=bridge-ns
n,s=r,g
    [constraint]
    direction=n
    id=bridge-ns
    [/constraint]
[/tile]

#same thing but with the road or bridge to the south instead of north
[tile]
id=north_south
image=bridge-ns
n,s=g,r
    [constraint]
    direction=s
    id=bridge-ns
    [/constraint]
[/tile]

{repeat the previous two tags for ne-sw and nw-se}

#okay there is apparently no road or bridge for us to connect up to.
#the first direction where a ground connection can be made is used
[tile]
id=north_south
image=bridge-ns
n,s=g
[/tile]

{repeat the previous two tags for ne-sw and nw-se}

Admittedly that is an awful lot of code, but on the other hand, it's not a completely trivial thing we're specifying here. Ayin, would you like to show us how your system would specify this, so that we can compare?

David

[Christophe33]

The bridge is effectively a fair (and difficult) problem. From a graphic point of view it would be easier to have the bridge image alone overlapping on whatever land the bridge should be. Setting an automatic direction detector is certainly very usefull for the random map generator but should be overruled when people make/modify maps.
Right now there are two type of bridge: wood and stone (not officially used yet) that are somehow equivalent to dirt and paved road, each with 3 orientations.
Terrains that are usually overlapped with bridge are shallow water and ice. Deep water and swamp would be a good candidate too, as well as Abyss and canyon when they are finalised. So we would need in theory 2x3x6=36 different pictures to cover all the cases while only 6 (already done) will be required if the bridge picture is just overlapped on the terrain under. Is it possible to code, for example by having the bridge pictures as an object?
For example the n-s wood bridge over shallow water is "|": Could you get an automatic image display that would translate "I" into "s+bridge-n-s.png"

[Ayin]

Well, first, a better description of the system:

Tags:

terrains: a description on the terrain layout on which the current multi-hex image may be applied. See below for terrain description format.

dimensions: mutually exclusive with element tarrain. A 4-uple x,y,w,h representing the x and y coordinates, the width, and the height of the tiles where the current multi-hex image must be applied.

class: a class name for the current multi-hex image. There may be at most one image of the same class on a given multi-hex tile.

rotations: followed by a list of 6 characters strings. Specifies the current terrain-map must be rotated along the 6 directions; for each of the rotations, the given string must be appended to the image name.

probability: the probability the image is created, if the current other constraint match.

image_background: base name (without .png prefix) of a multi-tile image which will be applied to the background of the matching tiles

image_foreground: base name (without .png prefix) of a multi-tile image which wi
ll be applied to the foreground of the matching tiles

Elements:

* terrain

id : terrain id, from 0 to 9

type : list of terrain letters, eventually prefixed with a ! for negation

-----

In the test case you provide, there is basically no difference between your system and mine, except than the "rotations" tag may be used to shorten the code. The "rotations" tag is not specific to my solution, and could also be adapted to yours with a few modifications.

Here is it

Code: Select all

# Check for a bridge-bridge, road-road, or bridge-road on this terrain

[built_terrain]
terrains = "
  br 
*   *
  b  
*   * 
  br  " 
    class=road
    rotations= -n-s -ne-sw -nw-se -n-s -ne-sw -nw-se
[/built_terrain]

# Road/bridge to ground

[built_terrain]
terrains = "
  rb
*   *
  b
*   *
  !w  "
    class=road
    # Change rotations if the bridge has to be directional
    rotations= -n-s -ne-sw -nw-se -n-s -ne-sw -nw-se
[/built_terrain]

# Find the first 2 non-water tiles in front of each other.

[built_terrain]
terrains = "
  !w
*   *
  b
*   *
  !w  "
    class=road
    rotations= -n-s -ne-sw -nw-se -n-s -ne-sw -nw-se
[/built_terrain]

# if none matches, the default terrain image is used

As you may see, the only real difference between your solution and mine is that, in mine, the direction of adjacent bridges is not checked (my solution is based exclusively on terrain maps, and cannot, for now, recursively check for conditions as does yours). In my opinion, there is no point checking it (at least in the case of bridges); I did not find a single example where it would be useful (but I may be wrong)

By the way (I'mm just nitpicking, the case I'm presenting is not something common, and certainly something map designers should avoid), there is (IMO) a problem in your solution. If the terrain looks like the following*

Code: Select all

  .   .   .   .
    .   =   =
  =   1   =   =
    =   2   =
  .   .   3   =
    .   =   4   =
  .   .   .   .

The bridge marked 1 will match as a N-S, thus confusing the algorithm that will be unable to match bridge marked 2, then 3, then 4.

* Those who already played ADOM will recognize . as being dirt/road and = as being water ; )

[Dave]

As you may see, the only real difference between your solution and mine is that, in mine, the direction of adjacent bridges is not checked (my solution is based exclusively on terrain maps, and cannot, for now, recursively check for conditions as does yours). In my opinion, there is no point checking it (at least in the case of bridges); I did not find a single example where it would be useful (but I may be wrong)

What about parallel bridges? E.g. someone wants to make a 'wide' bridge across a river, like this: (and some maps users have made have bridges like this; it's not just a contrived example)

Code: Select all

  .   .   .
=   |   |   =
  =   |   =
=   |   |   =
  .   .   .

Hmm..thinking about it, my algorithm isn't guaranteed to solve this case correctly either -- if it happens to process e.g. the north-western bridge tile first, and then it tries to see if a nw-se bridge is possible, it will end up concluding it is possible, and make a bridge extending from NW-SE, across the middle, and the tiles are the SW and NE will be left 'stranded'.

I think this would be solvable with further constraints though -- make it a bridge tile cannot have another bridge tile next to it unless that bridge is running in the same direction.

By the way (I'mm just nitpicking, the case I'm presenting is not something common, and certainly something map designers should avoid), there is (IMO) a problem in your solution. If the terrain looks like the following*

Code: Select all

  .   .   .   .
    .   =   =
  =   1   =   =
    =   2   =
  .   .   3   =
    .   =   4   =
  .   .   .   .

The bridge marked 1 will match as a N-S, thus confusing the algorithm that will be unable to match bridge marked 2, then 3, then 4.

This won't be a problem for my algorithm -- the bridge marked 1 will check if there is ground to the nw and a nw-se bridge to the se before it checks if there is ground north and south. When it checks for the nw-se bridge at '2', '2' will check if there is a nw-se bridge to the south-west of it, and the algorithm will recurse, and all four tiles will end up with nw-se bridge tiles.

David

[Darth Fool]

I think this may be a problem of trying to be too clever by half. An automated way of choosing bridge orientation is under certain circumstances bound to not be what a scenario designer wants. The scenario designer will want the ability to lay down bridges however he likes. Since we are moving to bridges being a terrain feature on top of another terrain type,
we might consider having map layers. This does make editing ascii map files by hand more difficult, but it would allow a "road" layer in which you specify the roads/junctions and then they get put on top of the underlying terrain. This would also allow roads to not take up a whole hex. Thus you could have a road on a mountain hex and get the benefit of both grassland or mountain defense whichever was better. This could also solve the castles lying across impassible terrain problem in random maps by just having random roads on the seperate layer connect all the castles to a given point.

Of course, we would need bridge junctions -< , Y , etc...

[Dave]

Terrains that are usually overlapped with bridge are shallow water and ice. Deep water and swamp would be a good candidate too, as well as Abyss and canyon when they are finalised. So we would need in theory 2x3x6=36 different pictures to cover all the cases while only 6 (already done) will be required if the bridge picture is just overlapped on the terrain under. Is it possible to code, for example by having the bridge pictures as an object?

The problem with this is that there is currently no way to specify what is under the bridge. I can understand that the way of doing it at the moment is somewhat awkward, but I think it's the best we've got, without quite an overhaul.

Also it's fastest computationally just to have them as single images, and it should be possible to write a script which easily overlays a bridge onto a new set of terrain.

I think this may be a problem of trying to be too clever by half. An automated way of choosing bridge orientation is under certain circumstances bound to not be what a scenario designer wants. The scenario designer will want the ability to lay down bridges however he likes.

IMO in most cases the scenario designer will be glad to be able to simply click on 'bridge', lay down the bridge, and see it come out in the logical orientation. I think this is alot better than having the scenario designer tediously select the type of bridge they want and lay it down, when in 99% of cases the auto-generated one is correct.

I also think it's more elegant to have fewer terrain types, with those terrain types 'smart' about how they are displayed.

Since we are moving to bridges being a terrain feature on top of another terrain type,
we might consider having map layers.

I think that map layers beyond the current aliasing system are something we might consider after version 1.0, but shouldn't be considered before. Among other things, this will complicate the editing of maps using a text editor to the point that a good map editor will be mandatory.

David

[Integral]

I like the basic idea, but what happens when the system of constraints has multiple solutions?

It's probably not trivial to just randomly pick one (generating all solutions is exponential in time and the odds that a random solution satisfies your constraints are probably low), although there might be a way to cleverly handle this.

btw, the reason it isn't obvious how to randomly pick a tiling is that the choice of tile for one hex may affect the available choices for another hex when there are multiple solutions. If you allow full Boolean expressions ("the northeast terrain is a hill and the southeast terrain is not sand, or the northeast terrain is a mountain and the southeast terrain is a hill..."), I'm almost certain the problem is NP-complete (although it might still be tractable for any sensible constraints). If you don't....it might be tractable, I'd have to think about it.

Another option is to detect and forbid multiple solutions...but I'm not sure that's a tractable problem either in general. (again, for the types of constraints you're likely to see, it probably is)

Or you could just pick a solution arbitrarily . That might be best, and it probably doesn't matter for the purposes of the game.

Daniel

[Ayin]

My opinion about the two different proposals:

Dave's proposal (recursive tile-by-tile validation) has a (IMO) a more elegant syntax. I would add two features to it, if it were adopted:
* rotations, to shorten syntax
* support for overlay images, necessary to replace the "built castles" system.
Its main drawbacks are:
* Quite complex to code
* Building large multi-tile drawn constructions may be quite complex.
* Would not really support scenario-specific tiles on standard terrains (but this can be changed)

My proposal is IMO much easier to code (but not completely trivial), and simplifies the graphics designers's task and the cfg files readability (no need to split tiles, and complex multi-tile images are easy to introduce, even on a per-scenario level).
Its main drawbacks are:
* Cannot recursively validate tiles. To solve the "parallel bridges" problem, 2-tile straight bridges, 3-tiles straight bridges, etc. may be introduced, but it cannot recursively create the n-tiled straight bridge.

[Dave]

My opinion about the two different proposals:

I concur with this analysis.

So which one to pick?

Well, rather than a 'design by committee approach', I think one of us should design and implement a system of their choosing. I think we're both technically competent and while we'd obviously choose different approaches in implementation, I think there are tradeoffs either way which are probably about equal.

Since you actually wrote the 'built tiles' system, you're probably more aware of the issues at this stage to extend it into a tiling system.

I think this discussion has served its purpose -- how about you go ahead and implement the system of your choosing? That's assuming you want to implement it -- if you don't, let me know and I'll go ahead and implement the system of my choosing.

David

[Ayin]

OK, I'll do that ; )

[Christophe33]

You could use the canyon problem as a test set since it will probably be the most complicated terrain around. I can send or post the completed version soon.