Some thoughts on map topology and navigable rivers

[Koshling]

First a slight apology for posting this here, since it's not strictly about C2C, though I know the audience here will be well-targeted.

Recently I started work on a modern game engine for a Civ-like game, into which I want to incorporate many of the great ideas that have been developed over the years in C2C. This is very early work, and likely to progress slowly - I'll probably be ready to start blogging about the design choices and early working code in a few weeks (at which point I'll post a suitable link to said blog).

As part of this I have abstracted the game engine over possible map typologies (and yes, it won't be restricted to one map, or one view in any way, though that's not relevant to this post), so it'll run happily with any cell arrangement that can be projected in 2 dimensions (including arbitrary connections for things like worm-holes, tunnels, inter-map links, ...). In particular I didn't want to totally bake in a commitment to squares or hexes, though I intend to default to hexes, and the first displays will probably be written to support explicitly hex-based maps.

I had only considered (at least for regular tessellations) hexes and squares (connected to all 8 neighbors or just 4 are both valid possibilities in the square case), but it occurs to me that there is another regular polygon that tessellates in 2 dimensions (on a flat map), which is equilateral triangles. In fact a hex-tessellation can be subdivided into equilateral triangle sub-cells by connecting the vertices to the center in each cell, yielding the equilateral triangle tessellation.

This got me thinking about the old navigable rivers problem in Civ. The problem is that you want to:

1. Allow movement along rivers by boats etc. (at least parts of a river)
2. Have a concept of river crossing for land units

For (1) you ideally want the rivers to flow through the center of cells so that the river units move on them. For (2) you want the rivers to flow along the edge of cells, so that as land units move between cells the act of crossing the river is well-defined. In existing Civ map layouts you cannot really achieve both without cell-wide rivers, which don't work for obvious reasons.

However, suppose we have a hex map, and then (logically, not necessarily in a user-emphasized way) sub-divide each cell into its constituent triangles. Then route the rivers along the sub-cell boundaries so that they flow from (hex) cell vertices to centers (i.e. - always through the middle of a cell). Now if we internally hold the position of a land unit as being in a particular sub-cell we can still display it as being in the parent hex cell (maybe we offset it slightly as a visual indication), and can have all the usual movement/combat rules (i.e. - the unit of movement is a full hex, and enemy units in the same hex fight). However, the concept of river-crossing is now well-defined, since the sub-cell arrangement tells us which side of the river a unit started on.

Best of both worlds...?

Opinions welcome - this only occurred to me as a possibility today.

 

[Harrier]

This got me thinking about the old navigable rivers problem in Civ. The problem is that you want to:

1. Allow movement along rivers by boats etc. (at least parts of a river)
2. Have a concept of river crossing for land units

For (1) you ideally want the rivers to flow through the center of cells so that the river units move on them. For (2) you want the rivers to flow along the edge of cells, so that as land units move between cells the act of crossing the river is well-defined. In existing Civ map layouts you cannot really achieve both without cell-wide rivers, which don't work for obvious reasons.

However, suppose we have a hex map, and then (logically, not necessarily in a user-emphasized way) sub-divide each cell into its constituent triangles. Then route the rivers along the sub-cell boundaries so that they flow from (hex) cell vertices to centers (i.e. - always through the middle of a cell). Now if we internally hold the position of a land unit as being in a particular sub-cell we can still display it as being in the parent hex cell (maybe we offset it slightly as a visual indication), and can have all the usual movement/combat rules (i.e. - the unit of movement is a full hex, and enemy units in the same hex fight). However, the concept of river-crossing is now well-defined, since the sub-cell arrangement tells us which side of the river a unit started on.

Best of both worlds...?

Opinions welcome - this only occurred to me as a possibility today.

That is a very good idea. To solve the river/land problem. Also with the relevant code the rivers would be more random in shape. Rather than up/down or left/right.

I like it.

 

[Dancing Hoskuld]

...and squares are just big squares with little squares inside them

 

[pepper2000]

I thought about this a while ago. My thought at the time was something like this:

A general representation of space would be a collection of points, pairs of points that constitute edges, and sets of 3+ points that define cells (as polygons). Edges would contain objects such as walls, rivers, national borders, fortifications, canyons, etc. Cells would contain objects such as cities, suburbs, farms, units, forests, mountains, etc. Then the domain of naval units would be edges with rivers and/or ocean cells.

This is part of a larger system I had in mind of map scaling as the game progress. In the Prehistoric Era, the map would be restricted to a single valley or island, with hills, forests, jungles, or rivers being the impenetrable barriers at the end of the world map. At various points throughout the game, multiple cells would be combined into one and the edges between them dissolved. Several small towns on adjacent cells would be fused into a larger city. Thus the map would expand from a single valley to a region 100s of kilometers to a continent to the whole world to various levels in space.

Without going to something as abstract as a polygonal complex (a 2-dimensional C-W complex for the mathematicians out there, though I wouldn't dare try to implement a 3-dimensional C-W complex for space maps), we could just say that the cells are squares, the points are an integer lattice, and the edges are the obvious North-South and East-West edges.

Obviously this scheme leaves a lot of detail to be worked out. I don't know if it bears any similarity to what you are trying to do.

If we want to be even more radical, we could dispense of the cells and allow cities, units, terrains, and other objects on the map define their own spatial boundaries, with defined rules on how they interact.

Anyway, I remember reading about the AXXXXE project years ago and being very excited about it. Is that what you are doing now? I very much want to know more.

 

[Thunderbrd]

First a slight apology for posting this here, since it's not strictly about C2C, though I know the audience here will be well-targeted.

Recently I started work on a modern game engine for a Civ-like game, into which I want to incorporate many of the great ideas that have been developed over the years in C2C. This is very early work, and likely to progress slowly - I'll probably be ready to start blogging about the design choices and early working code in a few weeks (at which point I'll post a suitable link to said blog).

As part of this I have abstracted the game engine over possible map typologies (and yes, it won't be restricted to one map, or one view in any way, though that's not relevant to this post), so it'll run happily with any cell arrangement that can be projected in 2 dimensions (including arbitrary connections for things like worm-holes, tunnels, inter-map links, ...). In particular I didn't want to totally bake in a commitment to squares or hexes, though I intend to default to hexes, and the first displays will probably be written to support explicitly hex-based maps.

I had only considered (at least for regular tessellations) hexes and squares (connected to all 8 neighbors or just 4 are both valid possibilities in the square case), but it occurs to me that there is another regular polygon that tessellates in 2 dimensions (on a flat map), which is equilateral triangles. In fact a hex-tessellation can be subdivided into equilateral triangle sub-cells by connecting the vertices to the center in each cell, yielding the equilateral triangle tessellation.

This got me thinking about the old navigable rivers problem in Civ. The problem is that you want to:

1. Allow movement along rivers by boats etc. (at least parts of a river)
2. Have a concept of river crossing for land units

For (1) you ideally want the rivers to flow through the center of cells so that the river units move on them. For (2) you want the rivers to flow along the edge of cells, so that as land units move between cells the act of crossing the river is well-defined. In existing Civ map layouts you cannot really achieve both without cell-wide rivers, which don't work for obvious reasons.

However, suppose we have a hex map, and then (logically, not necessarily in a user-emphasized way) sub-divide each cell into its constituent triangles. Then route the rivers along the sub-cell boundaries so that they flow from (hex) cell vertices to centers (i.e. - always through the middle of a cell). Now if we internally hold the position of a land unit as being in a particular sub-cell we can still display it as being in the parent hex cell (maybe we offset it slightly as a visual indication), and can have all the usual movement/combat rules (i.e. - the unit of movement is a full hex, and enemy units in the same hex fight). However, the concept of river-crossing is now well-defined, since the sub-cell arrangement tells us which side of the river a unit started on.

Best of both worlds...?

Opinions welcome - this only occurred to me as a possibility today.

I'm very pleased to hear you are working on this. I desperately hope you intend to bring us in once the foundation has been established.

Curious what you've decided regarding the front end... I found a very interesting freeware company that provides a graphic engine that may be extremely useful - they work with both 2d and 3d engines for game designers.

It's interesting to see you're basically picking up where we left off. If you're intending to make it possible to switch between hex and square mid-game I'm not sure how you could manage the paradoxes that would arise so I presume you'd be making it a game setup option basically?

I get your solution and find it fascinating. But it's all a matter of scale. I've always liked the idea of zooming in to tactical combat for actual conflicts. And in a lot of ways what you suggest supports this nicely.

In the game phase sequences, the rule could be, if your unit/stack moves into a plot held by an engageable enemy unit, its movement phase freezes. This doesn't freeze the whole game. Units elsewhere should still be moved until all units are either resolved or frozen in such a conflict resolution pending state. Once all units have resolved, the other players take their movements (imo even better if this is all simultaneous) and once all movements for all players are exhausted (even though movement points may remain on units after being frozen in place due to a pending conflict) then the game progresses to cycling through the conflict spots.

At each point of conflict, the plot opens up into a larger, zoomed in map. On THIS map, units, even friendly ones, generally cannot share the same mini-plots, and you have something more like the strategies of Chess or Civ V+ as it plays out round after round until resolved. Then cycles to the next conflict and repeats until all conflicts are resolved and THEN we go back to wrapping up any potential additional movements that can be made AFTER battle by the units that had engaged. And we keep cycling through conflicts and large scale map movements until the full round has exhausted itself completely.

In such an approach, the rivers would play out nicely just as you described, the direction of entry determining the initial entry zone onto the zoomed in map. However, those starting zones on the tactical map would not be just cut into triangles, there would also be a mini slice of a hex shape in the center to denote where to place those units that hadn't moved into the space but were there at the beginning of the round already, and it would also be where the 'city' would be if we are looking at trying to capture.

For spaces on the tactical mini map, you could then repeat your method to work with both combat modifiers for case situations and movement, and it would be brilliant imo.

I thought about this a while ago. My thought at the time was something like this:

A general representation of space would be a collection of points, pairs of points that constitute edges, and sets of 3+ points that define cells (as polygons). Edges would contain objects such as walls, rivers, national borders, fortifications, canyons, etc. Cells would contain objects such as cities, suburbs, farms, units, forests, mountains, etc. Then the domain of naval units would be edges with rivers and/or ocean cells.

This is part of a larger system I had in mind of map scaling as the game progress. In the Prehistoric Era, the map would be restricted to a single valley or island, with hills, forests, jungles, or rivers being the impenetrable barriers at the end of the world map. At various points throughout the game, multiple cells would be combined into one and the edges between them dissolved. Several small towns on adjacent cells would be fused into a larger city. Thus the map would expand from a single valley to a region 100s of kilometers to a continent to the whole world to various levels in space.

Without going to something as abstract as a polygonal complex (a 2-dimensional C-W complex for the mathematicians out there, though I wouldn't dare try to implement a 3-dimensional C-W complex for space maps), we could just say that the cells are squares, the points are an integer lattice, and the edges are the obvious North-South and East-West edges.

Obviously this scheme leaves a lot of detail to be worked out. I don't know if it bears any similarity to what you are trying to do.

If we want to be even more radical, we could dispense of the cells and allow cities, units, terrains, and other objects on the map define their own spatial boundaries, with defined rules on how they interact.

Anyway, I remember reading about the AXXXXE project years ago and being very excited about it. Is that what you are doing now? I very much want to know more.

I think to enforce that maps could be kept simple enough in individual scope to optimize processing and yet maximum expandability, you could work with a theoretically unlimited number of zooming layers.

In this way you could compartmentalize the data such that it only loads what it needs at a particular level of resolution, which would never be too overwhelming to the load or the overall picture.

For example, say 24 or so hexes fits into one large hex and that large hex would be the 'viewport' the game currently works with. As the game complexifies you keep having to shift out to get a bigger, less detailed resolution view, where that one large hex is now a part of 24 other same size hexes within an even larger hex 'viewport'. This allows you to zoom in and out on other hexes down to the tactical level as the base platform.

And this could then all be stored in neat 'save packets'. You could truly develop your cities in a far more 'sim city' style at the most zoomed in strategy layer while playing a more interconnected 'civ' style large scale strategy game. In this way, the size and reach of a cities borders has more to do with the microcosmic developments than it does generalized mathematical algorithms. Key positions could be held and/or destroyed, giving combat much more life.

The mechanism I'm proposing to narrow down to eventual tactical map play could start at the highest level currently established as the farthest we've needed to zoom out to first and narrow in cycle after cycle until we reach conclusions at the tactical levels.

Make sense?

 

[pepper2000]

Make sense?

Yes, and that actually sounds a lot like I was envisioning it. Though truth be told, I still prefer squares over hexes, and they are much easier to program with.

Ah, this discussion makes me want to break out Visual Studio again. If only I had 48 hours in a day. The last time I attempted to design a game with a complex map (similar to the polygonal complex idea described above), it looked rather ugly, had glitches I was never able to figure out, and took a huge amount of time to design, but for all its flaws I thought it was an idea that has potential.

And while we're on the whole brainstorming ticket, a hierarchical map might made trade and property diffusion much more efficient. Most location-specific properties, such as goods, education, pollution, population, buildings (e.g. factory capacity as a number rather than binary), etc. would be a vector attached to each cell. Trade, property diffusion, immigration, etc. would only go from a cell to its subcells or supercell. A sparse trade matrix could be built which would update properties each turn. Not only that, this framework would be highly flexible in implementing economic simulation, climate changes, supply lines for units, or any number of things.

 

[AIAndy]

Civ originally has a very simple discretization of space time. One regular grid of 2d space on which everything is located and one grid of time, the turn, on which all systems run.

As rightly noticed above, neither is a must.
There is no inherent need for all units to move along the same grid. Land units could move along the centers of plots while water units could move along the edges.
There could also be multiple grids layered atop on each other, either as hierarchical or for different purposes.

Not everything needs to run on a turn either. In EU4 and similar Paradox games, the smallest unit of time is a day but not everything is calculated every day, many things are calculated once per month or once per year.

The points that need to be considered are:
- Renderability: Can it be displayed properly for the player?
- Interactability: Can the player interact with it in a good way?
- Understandability: Can the average player understand it?
- Efficiency: Can it be calculated efficiently for the computer?
- Rule-friendly: Can game rules and systems be defined easily?
- AI-friendly: Can AI understand it with limited effort?

 

[Koshling]

It's premature really, but I'll start a blog this weekend with some thoughts outlining what I have in mind/am working on.

The salient points for now are:

1. Support for very large maps (ideally up to 1000 X 1000 or so)
2. Arbitrary topologies supported in the game engine (a topology is just a collection of neighborhoods, and a neighborhood is just a location plus a list of connections to other locations). Rendering is another matter, so I'll initially be sticking to simple regular topologies to make the client side easier
3. No restriction on the number of maps, or the number of open windows onto any particular map (to answer an earlier question, I would see the base topology of a map being fixed, but not necessarily fixed between maps - however, each new base topology likely amounts to not insignificant client work, so the first cut will probably all be hexes)
4. Client-server, with the client being browser-based so that it supports a wide variety of platforms. While the intention is to support cloud-based servers for multi-player (see below) it is also a goal to make the server simple to install locally to support 1-player mode without a connection
5. Internal mechanics heavily based on something like the property system (essentially a cellular automata to handle state evolution)
6. Some changes to support much more efficient multi-player mode to replace PBEM (so s to guarantee a fixed turn time in essence, given the issues we've seen with serial play in our own ongoing PBEMs)
7. Modern programming architecture (I'm writing the server in (fairly) pure functional scala)
8. Initial reference client (UI) will probably be a bit rough around the edges, but the idea oif the client-server split is to easily allow other clients to be constructed if anyone gets on board

It's FAR too soon to really be able to spread any useful work between more people than currently (me doing server, my wife doing client), but I'll certainly be open to help if/when we get a bit further down the line. Everything is open-source and the code is publicly available (but as I don't recommend trying to do anything to/with it yet, until a bit more progress has been made on basics): https://github.com/SteveDraper/automata

Also, the functional approach may make the (server) codebase a bit less accessible unless you happen to have some FP experience, as its really a rather different way of thinking about program construction, but ultimately a better one I believe (I started a new job last year and got dropped into very deep FP waters, which I'm just surfacing from now, but they really are rather refreshing!)

 

[Thunderbrd]

Fascinating. For those of us unaware of FP (Does this stand for something?)... could you guide to some overview resource material there?

 

[AIAndy]

FP = Functional Programming

 

[tmv]

FP has been interesting for universities for quite some time, but in recent years it has become a really hot topic. Two important reasons for that are:

• It makes for easily testable program code.
• It can easily be parallelized.

This is mainly achieved by the "no side effects" paradigm. The following java-like code is not FP:

static final int HEATER_THRESHOLD = 55; // degrees F

void check_temperature() {
  int temp = read_sensor();
  if (temp < HEATER_THRESHOLD) activate_heater();
}

This function does two things: reading the sensor and activating the heater, and the latter obviously changes some kind of "state". Edit: The latter effect is also not mentioned in the function name. Testing such a function requires setting up a proper state, and if you have concurrency in mind, code like this can become a nightmare (if it is a bit more complicated).

There are already a few good sites around for learning FP. Some information can be found by googling "closure", which is a very important aspect of FP.

2nd Edit:

Of course, it can be even worse. The following Java-like code is mostly alright regarding OOP paradigms:

private static final int HEATER_THRESHOLD = 55;

private Heater heater;

private int temp;

public int getTemp() {
  if (readSensor() < HEATER_THRESHOLD)
    heater.increaseTempTarget();
  return temp;
}

This side-effect is nasty (side-effects in a getter, changing a target value without checking it first, no thread safety, no mentioning of the side effect and no way to avoid it) and if used in a closed-source library the consequences could be severe. FP paradigms would completely banish this kind of programming because FP programming is stateless and even users of a closed-source library usually know what they are doing as long as the function names are fitting.

Of course, this is just one thing done differently in FP, but arguably the most important one.

 

[Koshling]

For someone with a traditional imperative programming background coming at it for the first time, the two most striking things would be:

1) No mutable variables (that is, once a variable is assigned a value it cannot be changed)
2) Eschewing side effects (that is functions only return values, they do not do other stuff 'on the side')

There are idiomatic ways of handling effects (for example outputting a message is an 'effect') without it being a 'side effect' (a totally effect-free program after all could do nothing apart from heat your CPU up!). Also there are usually some 'get out' clauses where you REALLY need mutability (sometimes in highly optimized parts of the code), but generally these are (should be) wrapped up in something that is pure from the outside perspective.

A major property that is achieved by following the above two rules is 'referential transparency', which basically means any expression (whatever function calls it involves) will always evaluate to the same result for a given set of parameters, which means it can be reordered, memoized (cached), etc. and makes reasoning about the code much easier. It also means concurrency is oiften much easier to handle, since no values can be changed by one thread under another's feet.

The lack of mutable variables in normal use means that imperative constructs like loops tend to be replaced with recursion, and side-effecting control flow (like exceptions) with more complex types that can handle (for example) holding a result or an error, so that all cases can be represented as just a functional 'result'. Generating effects (e.g. - disk writes, screen output, network communications) is handled via constructs called monads (well strictly monads are much more general than that, but one of their uses is effect-handling) - you can think of the way this works as having part of the code generating a set of work to do in it's execution (this set is its functional 'result') which the monad executes 'eventually' (idiomatically this is often called 'at the end of the world'), which generally means at some completion point for that thread.

 

[Thunderbrd]

If you can't change a variable, how do you calculate?

 

[tmv]

By introducing new variables.

 

[Thunderbrd]

So you always have to calculate into a new variable? That sounds exceedingly limiting.

 

[Koshling]

So you always have to calculate into a new variable? That sounds exceedingly limiting.

Not really. Here's a super-simple example (if you have other reasonably simple examples of traditional code you think would be hard without mutability, post them and I'll post a functional version as illustration):

Suppose we want to add up the numbers from 1 to N. In C++ you might write something like:

int addUp(int N) {
  int total = 0;
  for(int i = 1; i <= N; i++) {
    total += i;
  }
  return total;
}

In Scala (written functionally) the direct nearest equivalent would be something like:

def addUp(N: Int) = {
  if (N == 0) 0
  else N + addUp(N-1)
}

In fact, functional languages tend to have extremely rich libraries for manipulating collections, ranges etc., and we could actually just write:

(1..N).sum

but that would be a slight cheat. Once you allow functions themselves to be first class values and pass functions around as parameters, you can go much further. Analogous to the above there is a general concept called a monoid, which is basically something that has a 'zero' value and an operator to allow two values to be combined (with the constraint that any value combined with zero is itself). Hence integers with the combination operation of addition are a monoid. Using some functional trickery it's then easy to define 'sum' generally, to work on any monoid. An example of this (which is actually a real case in the game engine code) is the idea of a Region (of a map) (in my case defined as a set of rectangular areas, but the exact representation does not matter) - Regions form monoids with the combination operations of either union or intersection, so to find the common overlap of a list of regions, all I have to do is:

def intersection(regions: List[Region]) = regions.sum(Region.intersectionMonoid)

This sort of highly general abstraction, combined in very short functions, is typical of the functional style.

It takes a while to get your head around, but that's mostly because we have all got so used to imperative thinking. It's not really any harder - just different.

 

[Thunderbrd]

Of course, I'm not following ALL of that, but aside from some std style functions, you're pretty much needing to write a new function for any given calculation? On one hand that sounds laborious as hell. On the other, if you're REALLY good at remembering what functions have been defined for what calculation purpose, you can build a calculation library of your own for all processes. It just makes something very trivial otherwise become not so trivial. The difference between simply typing out a word you know and having to struggle to remember every word that exists every time you need to use one.

As you say, it can get easier once the mind gets used to it but wow...

Then again I probably don't understand it all very well.

 

[BigThinker]

That's what commenting is for.

 

[Harrier]

That's what commenting is for.

As far as I can see - nothing to do with comments. More to do with learning and remembering all the pre-defined bits of code.

Otherwise - you keep re-inventing the wheel.

You then end up with lots of: (1..N).sum

If it is taught at Uni. - it will no doubt eventually become standard. As students move into the real world. Has happened before and will happen again.

 

[tmv]

It will certainly become more popular, there is already one rather popular OOP language that introduced elements of FP (Java in V8). And it solves many issues with concurrency in an almost trivial way (no side effect means the compiler can parallelize the code pretty much all by itself).