Territories

[feneur]

Hmm, why not have stone walls for curtain walls, then palisades for freely placed walls? It's not really feature creep, since all it would be is swapping in new actors and meshes (and the consensus seems to be we want both types of wall placement anyway). I can whip up palisade objects easily, or use Pureon's palisades as a basis.

Hmm, now you're onto something (Though please, please, please can we have gates in the palisades? I always found the lack of that a bit silly in AoK.)

[errt]

If walls had a high weight but no range, that should be enough to have them stop the enemies expansion. At least if you can only build them in your territory and something is done to assure that no territory can be controlled where no building is in (so the territory can not reach over the wall, as it wouldn't be connected to the rest - territory-wise, not meant to be based on whether walking would be possible).

Btw.: Should impassable terrain stop territories? I think it should. Badly passable terrain (e.g. steel slopes) could also decrease weights on it's tiles, so borders would follow natural borders more often, creating a more realistic map division.

[Ykkrosh]

Did some experimenting on how to render territory borders. I think the default settings there aren't too bad - it computes the boundary points, smooths them to get rid of the staircase effect on 30/45-degree angles, then draws a simple spline through them, and offsets perpendicularly inwards to stop the boundary lines overlapping.

[Mythos_Ruler]

Did some experimenting on how to render territory borders. I think the default settings there aren't too bad - it computes the boundary points, smooths them to get rid of the staircase effect on 30/45-degree angles, then draws a simple spline through them, and offsets perpendicularly inwards to stop the boundary lines overlapping.

Yeah man, that looks super nice. Glad you could get rid of the stairsteps effect!

[historic_bruno]

Did some experimenting on how to render territory borders. I think the default settings there aren't too bad - it computes the boundary points, smooths them to get rid of the staircase effect on 30/45-degree angles, then draws a simple spline through them, and offsets perpendicularly inwards to stop the boundary lines overlapping.

Looks good. In fact all the smoothed lines look about the same to me, with the natural cubic and rounded nonuniform looking best IMO. Maybe do which ever is fastest?

[MrEmjeR]

nice job philip

the catmull fuctions does have some weird glitches at the sharp bends though

[Ykkrosh]

the catmull fuctions does have some weird glitches at the sharp bends though

That's because I implemented it wrongly . I've updated it so I think it's more correct now.

Looks good. In fact all the smoothed lines look about the same to me, with the natural cubic and rounded nonuniform looking best IMO. Maybe do which ever is fastest?

Natural cubic is way more complex (it involves solving some triadiagonal matrix expression, seemingly with Gaussian elimination, or rather finding someone's Java applet that already does it efficiently (which they probably copied from C book from the 1980s) then porting the code), so probably best to avoid that unless it has significant advantages (which it doesn't seem to - it provides C2 continuity (i.e. no sudden jumps in acceleration) while the others are only C1 (no jumps in velocity) but I don't think we care about that for this). With the smoothing thing, some of the spline's control points end up being very close together, so nonuniform splines are much better at that than uniform Catmull-Rom, and the rounded nonuniform thing is pretty trivial to compute.

I committed some code now as an attempt at the dynamic territories thing - create some civ centers and houses, assign to players, then it should show the territories and you can drag things around and see them interact. Is it basically right?

(The territory_block/territory_pull objects still work in this new approach; settlements don't. The <TerritoryInfluence> in template_structure_civic_{civil_centre,house}.xml can be changed, though the weights shouldn't be changed drastically - too high might cause overflow bugs (weight divided by radius should be no more than about 11586), too low might cause imprecision (weight divided by radius should be no less than about 64).)

[SMST]

I get the following error if I try to place a house or a civic centre:

[ 25.441.] error: CXeromyces: Parse error: structures/hele_civil_centre:1: Did not expect element Radius there

[ 25.441.] error: RelaxNGValidator: Validation failed

[Ykkrosh]

Sounds like you're running an old build - the latest autobuild should work.

[Ykkrosh]

Still need to work out how to actually render the spline, so that it follows the terrain heightmap. The only ways I can imagine are to do it kind of like decals (render terrain tiles with a special texture projected onto them), or construct new geometry (with x/z coordinates determined by the spline, and y coordinate determined by the terrain, split into enough triangles so it looks smooth and doesn't visibly float or sink under the terrain).

Assuming a 512x512 map with 8 players, they could each have a territory area of 26K tiles, which is a perimeter of at least 565 tiles each (more since they're not perfect circles), so say it's about 8K territory border tiles to render. If we created a unique 32x32 decal texture for each tile, that's a 32MB texture, so that's probably not good.

A potentially interesting observation is that a spline segment between two adjacent control points is only affected by a total of six control points (given RNS+smoothing); and since the control points are found by walking around the edge of the territory, and there's only 3 possible directions to walk in at each step, there's only 3^5 = 243 distinct spline segments (ignoring rotational equivalents), if I'm working it out right. Each segment touches usually 1 but up to 4 tiles, so we could pre-render the up to 972 distinct tile decal textures (with DXT1 so it's probably 0.5MB with 32x32-pixel tiles), though we'd have to render each terrain tile typically 2 and up to 4 times to get all the segments onto it. Joining up adjacent segments smoothly might be a problem, though.

Doing it with geometry instead, I guess we'd have to first construct a 2D polygonal approximation of the spline (with thickness), with some suitable margin of error, then clip the shape against each terrain triangle to get a load more polygons, then compute the y coordinates of each polygon based on the terrain, then offset upwards a bit to avoid z-fighting. That'll give at least one quad per terrain triangle, up to about 8 quads (4 spline segments, each split into 2 straight sections for adequate smoothness), so it'll be slightly more triangles than the decal approach, though less fill rate. It'd be higher resolution (since it's geometry instead of textures) and more flexible (we could easily use it for rendering more complex splines) and could probably cope with steep slopes without stretching (unlike decal textures).

I suppose I'm leaning towards the latter approach, but I don't really know yet, and maybe there's alternatives I haven't thought of.

[janwas]

hrm. I liked Michael's smooth lines, but it seems surpringly tough to render them in 3D.

There is a not so crazy alternative: we could just place some "buildings" along the contour -

think tiny marker stones or something.

Obviously they would have to be tiny and not hugely detailed, since there are lots of them,

but we could reuse the building placement logic (except for flattening terrain) and

kind of dance around the smoothing problem, since there are gaps between the stones anyway.

"Settlers" did something like this: http://www.settlers3.com/strategy/multiplayer/images/romans/060.jpg

[Mythos_Ruler]

"Settlers" did something like this: http://www.settlers3.com/strategy/multiplayer/images/romans/060.jpg

I think nice borders are a must have no matter if we have static or dynamic territories--just my opinion. I'm willing to make whatever art assets are required to make it happen. I'm a layman, so I didn't really understand all of Philip's post, but would it be possible to have a bunch of pre-rendered textures for all known tile shapes, like we do with terrain blending?

[historic_bruno]

It'd be higher resolution (since it's geometry instead of textures) and more flexible (we could easily use it for rendering more complex splines) and could probably cope with steep slopes without stretching (unlike decal textures)

I think this is an important point. The pre-rendered textures method sounds like we'd be painting ourselves into a corner, we shouldn't do that unless there's no other choice (mostly for performance reasons, I guess).

[janwas]

heh, sorry for that shock Die Siedler III is admittedly really old, like ~12 years, and 2D.

Assuming that no nicer boundary-stone type thingies can be devised, there is yet another alternative:

We can have OpenGL evaluate the spline for us! I think the magic word there is GL_MAP_VERTEX_3.

That can be used to implicitly generate geometry. Quake III was doing this in a similar timeframe,

so I wouldn't imagine hardware compatibility to be a problem. IIRC, this was for Bezier curves

(i.e. Bernstein basis functions), but as Philip's demo has shown, the exact type of spline

doesn't really make a big difference.

This would avoid the need for polygonal approximation. I'm also hoping we can avoid having to

clip vs. terrain tris by lifting it high enough off the ground and introducing enough points

that it wouldn't dip into the terrain often. Perhaps the texture can be made `blotchy' enough

that it wouldn't matter tooo much if it sometimes disappeared below terrain.

// edit: I agree with Ben that a geometry-based solution (which includes the abovementioned

OpenGL evaluators) is preferable.

[Ykkrosh]

we could just place some "buildings" along the contour - think tiny marker stones or something.

Interesting idea . Marker stones would be somewhat easier to implement, but I currently think the smooth continuous lines would be perfectly feasible too, so this should probably be driven by visual design rather than by implementation.

I'd expect one problem is that our game has relatively realistic non-cartoonish graphics, so if we draw some 3D mesh then people will think it's representing a real physical object, and they'll be confused as to how it magically moves around and might expect it to block unit movement. Also the boundaries can cross water so we'd need some kind of marker buoys as well as marker stones, and we probably want to do enough colouring so you can see who owns each side, so it sounds like it'd get quite visually complex. The smooth coloured lines are much more abstract so I think it's clearer that they're not a physical part of the world (just like selection circles and bandboxes etc), as well as being visually simpler. So I'm not sure I'm a huge fan of marker stones, but it'd be doable if other people prefer it.

would it be possible to have a bunch of pre-rendered textures for all known tile shapes, like we do with terrain blending?

That's basically what my third paragraph was about - we have 14 blend shape tiles whereas we'd need about 972 for reasonably smooth boundary lines (without zigzagging all over the place), but the concept is similar . But the thin lines would get stretched if they're crossing cliffs (like how terrain textures get stretched nowadays, but more obvious since the lines have sharp edges), and the textures might be visibly low-res if you zoom in enough, so they don't really seem ideal.

[Ykkrosh]

We can have OpenGL evaluate the spline for us! I think the magic word there is GL_MAP_VERTEX_3. That can be used to implicitly generate geometry.

Hmm, that seems to be one of the crazy complex features added in the earliest versions of OpenGL mostly for running CAD applications on SGI machines, and is deprecated in GL 3.0, and some old extension notes "evaluators have not been particularly popular" and "Many implementations never optimized evaluators". The GPU can only render triangles in any case, so all the API could do is shift the vertex setup work from the application into the driver (which can then offload it to special geometry hardware on those SGI machines), and we only need to compute it very rarely and stick it in a static VBO so that CPU cost doesn't matter. Since it's a rarely used feature it's probably buggy in various drivers too. So as far as I can tell it's obsolete and slow and unreliable and complex and doesn't do anything we can't already do by computing the triangles ourselves, so probably best avoided

[k776]

I've been thinking: Should the territory size by the factor used to determine they Line of sight?

Since at the moment, when you start a map, the civ center LoS is smaller than the territory size.

Ideally, if you have the territory, you can see everything within it.

We'd still have FoW/SoD on neutral and enemy territories.

Does that make sense? That we, we can get rid of any line of sight XML elements, and make the whole thing dynamic. Might work better.

[Mythos_Ruler]

I've been thinking: Should the territory size by the factor used to determine they Line of sight?

I think by general rule it should correlate, but they should still remain two separate stats so we can tweak them independently.

Since at the moment, when you start a map, the civ center LoS is smaller than the territory size.

Yeah, the current Civ Center (CC) territory effect (TE) is way too big, but I didn't complain because it's only in a proof of concept stage at this point.

I think at Phase I the CC's TE should be about 33% the radius that it is now, then when you research Phase II the CC's TE bumps up to about 66% of what it is now (then it lays down the curtain wall ring), then 75% at Phase III.

[Thorfinn the Shallow Minded]

The whole idea about the walls in the previous post, I like.

[Ykkrosh]

I've been thinking: Should the territory size by the factor used to determine they Line of sight?

I've always assumed the idea was that you'd see FoW (i.e. grey explored region and the initial state of trees etc) over the area of your territories, and full visibility in the normal circular LOS around all your buildings and units.

I think at Phase I the CC's TE should be about 33% the radius that it is now

Hmm, that's about the size of a single screen (at default zoom) - won't that be really annoying when e.g. you use up all the resources that are right next to your civ center, and can't build dropsites near the rest since they're far outside that area? or will the territory expansion effect of houses/etc be significant enough that you can easily stretch tentacles of territory out towards good resource locations?

[Sayyan]

I've been thinking: Should the territory size by the factor used to determine they Line of sight?

To my mind it makes more sense if the territory area is shrouded in FoW, until you have units there. Essentially you've mapped your territories, but unless you have units or outposts there you'd be unaware of what's actually happening.

Edited July 25, 2011 by Ross Bearman

[Mythos_Ruler]

I've always assumed the idea was that you'd see FoW (i.e. grey explored region and the initial state of trees etc) over the area of your territories, and full visibility in the normal circular LOS around all your buildings and units.

Hmm, that's about the size of a single screen (at default zoom) - won't that be really annoying when e.g. you use up all the resources that are right next to your civ center, and can't build dropsites near the rest since they're far outside that area? or will the territory expansion effect of houses/etc be significant enough that you can easily stretch tentacles of territory out towards good resource locations?

I'm just throwing numbers out there. Plus your territory will expand with houses and stuff, right?

[feneur]

To my mind it makes more sense if the territory area is shrouded in FoW, until you have units there. Essentially you've mapped your territories, but unless you have units or outposts there you'd be unaware of what's actually happening.

Agreed

(And I'll really have to check out the current version in-game, will have to do that tomorrow as I'm not working then but now it's almost midnight so too late today )

[Mythos_Ruler]

Above shows the current extent of the Civic Centre borders, along with my proposed Curtain Wall ring. I think something a little bit beyond the Curtain Wall ring (perhaps halfway between the ring and the green border) would be the Phase 2 borders, then the green border would be Phase 3 borders. A radius about 2/3 of the way from the CC to the wall ring would be the Phase 1 border (big enough to encompass the two closest groves of trees you see there). You can only build Mills within your territory, but you can still gather from items outside of your territory (I call this concept "poaching").

I think, as do others I believe, that the Shroud of Darkness should be lifted in your territory, but Fog of War should only be lifted by units and buildings.

[feneur]

Took some time today to play the game, and it sure feels promising There's something satisfying about expanding your borders on the expense of your enemies