Ykkrosh

Should be easy to implement - all we need is for someone to do the research to describe exactly how names are constructed for each civilisation (and for each gender within that civ, and for each significantly-different social class within that gender and civ), and provide a list of probably at least a hundred choices for each component of each type of name (to avoid an excessive amount of duplication), which surely can't be that hard

Sounds good . I think pathfinding is interesting since it's a fairly simple-to-define problem (find a good path between two points on a grid) but there's no perfect solution, and there's always some benefit in making it faster, so there's a huge range of alternative approaches and tradeoffs to explore. I don't think memory usage is particularly important by itself - maps will rarely be more than maybe 512x512 tiles, and players have lots of RAM (>99% have at least 512MB, >95% have at least 1024MB, based on data from current users), so we can spend a few more bytes per tile without much worry. But speed is important, and memory usage is important in its indirect effect on speed due to cache usage - minimising the memory that the algorithm accesses is more relevant than minimising the total amount allocated. This reminds me slightly of HAA* - have you seen that before? The hierarchy stuff is probably more important than the clearance stuff, though I suppose we should still ideally support some notion of clearance to cope better with formations or unusually large units (and/or smaller tile sizes). That article seems less similar now that I look at it again, but might still be an interesting thing to compare - it splits the map into a regular grid of clusters, then finds the important links between clusters and the distances between those link points inside the cluster, and does that for each passability class independently then merges redundant data at the end. That sounds like it may work more efficiently than your proposal if there is a high density of different passability/cost classes, since it can still use the same cluster size regardless of terrain complexity, though it has a higher cost for computing distances within a region and it looks like the implementation may be a bit more complex.

What should they do instead, when they can't reach their assigned target? (bearing in mind that they might be blocked by e.g. a gate or another unit, and could get unblocked in the near future; or their target might be moving and come within range in the near future; so maybe immediately giving up would not be ideal). (I think the pathfinding responsiveness changes in the latest release made this problem much worse, because the units loop their pathfinding requests at least once (maybe more?) per turn, whereas they used to be much slower; we should at least add some rate-limiting delay when they fail to find a path, if they're going to retry it again.)

Helps a bit, but not enough (particularly at the crest of a hill where the flat line-segment quad sticks out over one edge). But the lines are too wide in any case, since they won't fit in one-tile-wide sections of terrain (which occur occasionally in practice), so I made them half the width, which seems to improve the problems with hills etc too. So Jan's suggestion of just lifting it off the terrain a little is probably sufficient. It's not really proper glow, it's just a white part of the texture with an alpha gradient, but hopefully that's close enough

Is this the right idea? (Currently the implementation is very rough and inefficient - it splits the spline into 3 straight line segments per tile, and converts each segment to a quad with the joining edges tilted to follow the terrain's normals and lifted upwards slightly. There's some glitches in the top right where it intersects the terrain and disappears; increasing the separation between line and ground improves those but the gap underneath becomes annoyingly visible. The terrain height/normal computations are a bit broken so fixing those might help. There's also some glitches at sharp corners where the inside edge of the line turns back on itself and overlaps itself; not sure what's the proper way to deal with that.)

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?

Yeah, most of it should be done once at the start of the game (probably during the loading screen, so it doesn't matter too much if it's a bit slow), then occasionally either recomputed or updated dynamically when the world changes (e.g. building walls or cutting down trees might affect the reachability of areas), and stored in some form which allows very quick runtime queries when the AI is deciding what to do.

I think this is all related to the concept of terrain analysis - there's a vaguely useful overview in Game Programming Gems 3, and there's some details about Age games, though I'm not sure whether there's more articles elsewhere that are helpful. I'd expect we need it to automatically split the map up into smallish uniform regions, then compute which regions are reachable from each other (and an approximate distance), and also find regions representing forests and water and enemy towns etc, then the AI can use that region representation somehow to decide what's a good place to look for reachable resources and to realise when it needs to send ships to an island and to work out where to attack the enemy, etc. (Probably a fairly major design task, which is why the AI system doesn't attempt to support it yet )

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

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. 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.

No (or rather, not yet )

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.

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

That's because I implemented it wrongly . I've updated it so I think it's more correct now. 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).)

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.

Performance is hard since you probably need to compute LOS for every moving unit (potentially thousands) every turn (currently every 200ms or so). (Actually you have to do it twice, once to cancel the LOS effect from the previous turn and once to apply the new LOS effect from the current turn). The vision range might be ~20 tiles so its area is ~1000 tiles. So that's like ten million tiles processed per turn, most probably involving L2 cache accesses (which is maybe 10 CPU cycles each time) since the maps are quite large, and it can end up being a sizeable chunk of the total CPU cycles. So you generally want to minimise the amount of per-tile work you have to do, and searching for obstacles is probably too expensive. Precomputing data can make it faster, but storing that efficiently is hard if the visibility data is different for every tile. Maybe there's some clever way to make it work well, but I don't currently know of any From what I remember of SWGB, lots of people like doing RPG-like sections in their maps (particularly to add some variety to campaigns), so it'd probably be good to support a simple version of it as a proper part of the game. (Also I've always thought it'd be interesting to do a Diablo-like action RPG in the engine, but that's probably excessive feature creep ) It'd probably be better (and maybe easier) to implement a standalone inventory system rather than hacking the garrisoning system to support it - use the GarrisonHolder component as a template to create a new Inventory component or similar, and figure out how to integrate into the GUI (maybe using basically the same code as for displaying garrison status), then remove unneeded functions (ungarrisoning etc) and add whatever's still needed.

Sounds like the slowdown is mostly AI and/or pathfinding, and the changes in SVN have mostly been optimising graphics, so it's probably unlikely to make much difference.

The "unit motion overlay" option (I think) might make the behaviour in the screenshot clearer - I expect the tile-based pathfinder is finding a path through some gaps between the red (blocked) tiles, which should show up as a white-outlined string of tiles (I think) with that overlay, and then the short-range pathfinder (which does all the cyan rectangle stuff) is trying to follow it but gets stuck because it can't actually fit through those gaps. There's the fighter plane in the latest alpha release . No other unit should get past those obstructions, though.

Is this something like the idea? I made it so impassable tiles (cliffs/water) are effectively 4x as expensive as normal tiles, in terms of the influence falloff, though one consequence of the terrain-dependent approach is that it tends to form octagons rather than straight lines; I don't know if it's the best approach, or if pure terrain-independent circles would be better. With the isolated red house, there's no continuous path through red territory to a civ center so it can be determined to be cut off, but rather than immediately turning it all green it's maybe nicer for it to keep a bit of red territory around it while losing loyalty (due to being cut off) with the territory shrinking over time (i.e. make the weight proportional to loyalty (or health or whatever)). (I played RoN for the first time just now (just the demo version, in Wine which was quite buggy but basically worked), and it looks pretty much exactly like what's proposed here - cities make octagonal territories (affected to some extent by seas and maybe hills?), you can only build within friendly territory, there's a fixed minimum distance between cities, there's research to increase the weight and size of your territories (so they expand and also push back adjacent enemy territories). About the only difference I could see is that most buildings didn't affect the territories, only cities and forts (and maybe a handful of others), whereas the proposal here seems to be for most buildings to expand them.)

Clang says precompiled.h clang: warning: treating 'c-header' input as 'c++-header' when in C++ mode, this behavior is deprecated which I think means it wants "-x c++-header" on the command-line when compiling the .h file. (Our old Premake PCH modifications did that.)

Hmm, reminds me a bit of metaballs. I guess it should be implementable. How do foundations affect territories? If they have no effect, I can probably build a dozen civ center foundations right next to each other in neutral territory and then finish constructing them all. If they do affect territories, I can probably capture enemy buildings by placing loads of foundations around them and then later I can destroy all those foundations and get all my resources back, so they're effectively free. Maybe it'd work if they had the same range as completed buildings, but weight is proportional to construction progress? So they'd start with about 0 weight, which would still be enough to claim any neutral territory within range (so you couldn't build two adjacent civ centers), but wouldn't push back any enemy borders at all (so you couldn't cheat to capture enemy buildings for free); then their weight would increase up to maximum at build completion.

Follow-up to the how-should-territories-look question: How can we implement something like that? (In particular the input is a grid where each cell (tile) is assigned some territory ID, and cells with the same ID are always fully connected via adjacencies (horizontal/vertical/diagonal), and for each territory we somehow need to compute a smooth line that closely follows the boundary cells, then offset it inwards to get a thick band and some separation between adjacent territories. Currently I have no idea how to do that.) I committed the current work-in-progress version - the easiest way to test it is to open Atlas and create 2 or more gaia/special_settlement entities, and it should render the boundaries (it just reuses the minimap rendering on top of the terrain, which is ugly and needs replacing), and you can drag the settlements around and suchlike. Also there's special/territory_block and special/territory_pull which sort of influence the territory computation in a not hugely intuitive fashion.

Yeah, I thought it was better to keep it where the old premake.lua was, and to keep the premake4/ directory a clean copy of the Premake 4 sources rather than mixing in our own files.

Experimented a little with drawing territories on the minimap. I think the old implementation shaded the whole region in colour and drew boundaries in light grey, but I expect that's bad for readability of the minimap (there's already enough different colours to distinguish and we shouldn't make it worse by shading them all). I tried just drawing the boundaries in colour: but that looks ugly and unclear. It could probably be improved a bit by changing the texture resolution and/or doing antialiasing etc, but I'm not sure how much that'd help. I tried doing a thick alpha-gradient line thing too: which I think works better. (Alpha and thickness etc can be adjusted if desired, and maybe some blurring to improve the sharp edges between colours). Are there any better ideas to try? Separate question: How should territory boundaries be represented in the 3D game view?

I think precompiled.cpp is needed when compiling with MSVC (since that's what generates the PCH file), but not needed with GCC (since the PCH is generated directly from the .h), so preferably the .cpp should be ignored when using GCC.