Mini-engine progress

[Marla_Singer]

Technically speaking, a hex grid is a square grid with offset rows. And that's how the code interprets it under the hood:

<= square vs hex =>

Hexagon shapes are only cosmetic display. The only inherent mechanics with that layout is that it limits the number of neighboring tiles, and therefore possible interactions between tiles. Instead of being able to reach three tiles at each of the upper and lower rows, we can only reach two of them. Another downside is that hex grids are harder to subdivide cleanly: breaking a hex tile into smaller elements necessarily produces a different pattern than the original grid, unlike square grids which subdivide seamlessly. This limits flexibility for modular design.

It's surprising that hex grids have become the standard in 4X games given these constraints. Games such as Factorio, Prison Architect or Stardew Valley are all based on square grids, largely because they make it easier to represent elements of varying sizes and shapes.

 

[Mr Smith]

breaking a hex tile into smaller elements necessarily produces a different pattern than the original grid

I personally would highly prefer if hexes were split into triangles for battle or economic purposes, it would still be better than squares, especially if you keep permitting diagonal movement for the same cost as axis movement.

It's surprising that hex grids have become the standard in 4X games given these constraints

Zone of control is less punishing this way than if you were forced to, say, move 1 tile non-diagonally. The only implementation for Civ4 I remember required leaving ZOC completely to reenter, which is unreasonable. Also having 8 directions allows too much flanking to be possible, since 2-movers can cover 7 of them on flat terrain - it's a disaster in C2C. On hexes you can pack way more punch into flanking from 1 direction without it becoming ridiculous. Also rings of range instead of fat and morbidly obese crosses are much more natural with hexes.

 

[1SDANi]

My main issue with hexes is that you can't have a north, south, east, and west at the same time, it's all wiggly.

 

[<Nexus>]

I don't care whether it's squares or hexes but let's get a real spherical map

 

[Michkov]

You are going to need to cheat, because spheres are not hex tileable.

But yes, spherical maps please, I want to lob ICBMs over the poles.

 

[Blake00]

Technically speaking, a hex grid is a square grid with offset rows. And that's how the code interprets it under the hood:

View attachment 731037 <= square vs hex => View attachment 731039

Hexagon shapes are only cosmetic display. The only inherent mechanics with that layout is that it limits the number of neighboring tiles, and therefore possible interactions between tiles. Instead of being able to reach three tiles at each of the upper and lower rows, we can only reach two of them. Another downside is that hex grids are harder to subdivide cleanly: breaking a hex tile into smaller elements necessarily produces a different pattern than the original grid, unlike square grids which subdivide seamlessly. This limits flexibility for modular design.

It's surprising that hex grids have become the standard in 4X games given these constraints. Games such as Factorio, Prison Architect or Stardew Valley are all based on square grids, largely because they make it easier to represent elements of varying sizes and shapes.

Cheers for this.. I always wondered how the FreeCiv guys were able to develop an interchangeable Hex and Square system when Hex's seemed so different but I see now it's just an illusion. The result being you only need the touch of a button to switch your game between them.

Same game - Squares vs Hexes


Same game - Isometric Squares vs Isometric Hexes (that's what the dev called it anyway lol)

 

[Thrasybulos]

Zone of control is less punishing this way than if you were forced to, say, move 1 tile non-diagonally. The only implementation for Civ4 I remember required leaving ZOC completely to reenter, which is unreasonable. Also having 8 directions allows too much flanking to be possible, since 2-movers can cover 7 of them on flat terrain - it's a disaster in C2C. On hexes you can pack way more punch into flanking from 1 direction without it becoming ridiculous. Also rings of range instead of fat and morbidly obese crosses are much more natural with hexes.

... which are all considerations for a tactical engine, which has no place at all in a strategy game.
The move to hexes does indeed seem to coincide with 4X designers deciding they're rather their games were tactical wargames rather than strategy games.

 

[Slaughter]

For hexes, what you'd do I think is just create a whole new renderer. And reuse some components like city billboards and symbols.

It is something I've wondered about. Take the hexes from modern civ and just force civ 4 onto a hex grid. But, not very easy. Maybe you'd need new map scripts. But at least, a lot of things in the DLL appear to be grid-agnostic.

Could probably do it with graphical civ 4 too. The art assets weren't made for it, but it could work.

Interesting...

What do you think about SMAC-like dynamic voxel squares? Would they be possible?

Yeah, but SMAC's turns represent weeks or months, not decades, rigth?

Every turn is an year, actually. Pretty sure that can be changed in a scenario, through.

How is it in Paradox games? And could those be used in Civ4, if possible at all?

Probably couldn't be used in Civilization IV. Perhaps in a new engine.

Essentially, most paradox games use a system which divides land into two categories:
Owned/Controlled. Owned Land belongs to a certain nation X, Controlled Land is land currently controlled by any nation, be it X or someone else. Usually, most nations both Own and Control a province, but when things like war happen, you can have a situation where one nation owns the province and another controls it. So for example, if during a war, an enemy force takes your province, it is controlled by that enemy, but you still own it. You can only transfer land ownership through a peace treaty, and if I recall it right, controlling but not owning doesn't give full advantages for having the land.

Compare this to Civilization, where owned = controlled City.

Paradox Games also have the concept of Core territories, in which a nation may have Cores in certain provinces, which are provinces it (or the world community) recognizes as possibly theirs. In some games, you can "create" cores or claims which legitimate conquest through casus belli.

Paradox games also often use the concept of Casus Belli, in which wars often require a cause to pursue - say, obtaining certain core provinces, forcing a Personal Union between two kingdoms, etc. In some games you can do no-CB wars, but that's usually punished somehow. In other games, certain groups (Pirates, Steppe Raiders, etc) have pretty much free CBs to raise hell.

Paradox games also often have deeper diplomatic relationships. Like, Civilization mostly tends towards Peace/Alliance/War. Paradox games have things like Vassalization/Puppets, Tributaries, Protectorates, etc. Depends on the game.

Some paradox games, like Crusader Kings games, also have non-Westphalian states.

Care to explain? I'm always looking for ideas for my mod what to add/improve/implement, if I can

Man, there's a lot. Top of my head:

Call to Power:
- Public Works (no workers to build tile improvements, tile improvements are built with the public works resource)
- Space Map
- Space and Undersea Colonies

SMAC:
- Unit designer (yeah yeah polemical feature I know)
- Dynamic Voxel Map - SMAC doesn't have "static terrain tiles", like, there's no such thing as a "grassland tile". Rather, every tile has dynamic values like Rockiness (which determines mineral production potential), Rainfall (which determines how much Nutrients it produces) and Altitude (which determine how much energy can be produced there, but can also determine the Rainfall of a tile if its East or West of a mountain range). All these values can be altered through terraforming and gameplay. This allows A LOT of terraforming that simply isn't seen in a civilization game, ever. You can make terrain higher or low, you can create more land and sink it, you can make a place more or less rainy, you can dig aquifers and create new rivers, etc. The way SMAC does terrain is absolutely vanguardist and is so beyond pretty much all civilization games and its clones, its not even funny.
- Social Engineering. Civilization IV picked it up but I feel like it didn't do as well.

Space Empires IV:
- Actually having to supply your ships
- Satellites and space bases
- Incredible levels of ship, space base and satellite customization

 

[snowern]

I always wondered how the FreeCiv guys were able to develop an interchangeable Hex and Square system

Hecking magic.

Anyway...

Done some things. I'm hoping to move onto general gameplay on a non-gigantic map to see if it holds itself together with the debug build.

---

New found value system integrated. Uses a quad-tree with 64x SIMD for city distances, which is very fast. 1-2ms, per player, for a whole-map distance field. Can be further improved by computing lazily.

This "v2" found value system is also much more simple than "v1". Just simple plotwise caching and a really fast evaluation function.

Using v2 and clang-cl, T209 time is down to just ~1.07s. It's getting there. Sub-second is on the horizon.

---

CvMap::calculatePathDistance was slow. T210 took ~2s because it's computing long inter-city distances, using the step pathfinder. CvMap::calculatePathDistance takes ~56% time on this turn (with my simple cache).

Luckily, this is uniform cost pathing, so you can use JPS or RSR to make it much faster (https://harablog.wordpress.com/tag/symmetry/). Except... it's not much faster. It's actually no faster than optimised simple A*. Which is very odd. But convenient, I like simple. With simple A*, CvMap::calculatePathDistance takes ~3.96% of time. Reduces T210 time down to ~0.84s.

Spoiler Performance test log :

(the FAStar+Simple A* test only did 200 paths because I don't want to wait for 1000 paths):
Total FAStar time: 11.9062s
Total Simple A* time : 0.174318s
RSR: 7999 rects.
RSR test successful.
Total Simple A* time: 1.1812s
Total RSR time : 2.48749s
Jump Point Search test successful.
Total Simple A* time: 1.21122s
Total JPS time : 1.35729s

This is JPS with some optimisation too to speed up the scanning.

Really, it seems that as long you can replace the A* priority queue with a bucketing approach, you'll make it much much faster. This could also be done with RSR and JPS with enough buckets, but simple A* is good enough for now.

---

Next, Landmarks. I've disabled them. The asynchronous background update makes the game non-deterministic, which is bad for debugging at least.
A deterministic asynchronous update is possible by simply using the previous turn's heuristic (for known movement types), and computing the next in the background, but that makes the heuristic part of game state.

Surprisingly, there's not much performance loss. T210 time goes up to ~0.9s.

---

Finally, terminal woes. The greatest problem of all time: You can't shift-click buttons on Windows Terminal or the Linux Terminal I'm using. So, um... who likes good ol' reliable Windows Console? I have no idea how to fix this problem properly. What magic ANSI sequence disables shift mouse selection? "Sticky shift" is a maybe.

*Mapped right-click to shift-left-click. It works for production queuing. But no more right click.

 

[Gameboy2396]

Hecking magic.

Anyway...

Done some things. I'm hoping to move onto general gameplay on a non-gigantic map to see if it holds itself together with the debug build.

---

New found value system integrated. Uses a quad-tree with 64x SIMD for city distances, which is very fast. 1-2ms, per player, for a whole-map distance field. Can be further improved by computing lazily.

This "v2" found value system is also much more simple than "v1". Just simple plotwise caching and a really fast evaluation function.

Using v2 and clang-cl, T209 time is down to just ~1.07s. It's getting there. Sub-second is on the horizon.

---

CvMap::calculatePathDistance was slow. T210 took ~2s because it's computing long inter-city distances, using the step pathfinder. CvMap::calculatePathDistance takes ~56% time on this turn (with my simple cache).

Luckily, this is uniform cost pathing, so you can use JPS or RSR to make it much faster (https://harablog.wordpress.com/tag/symmetry/). Except... it's not much faster. It's actually no faster than optimised simple A*. Which is very odd. But convenient, I like simple. With simple A*, CvMap::calculatePathDistance takes ~3.96% of time. Reduces T210 time down to ~0.84s.

Spoiler Performance test log :

(the FAStar+Simple A* test only did 200 paths because I don't want to wait for 1000 paths):
Total FAStar time: 11.9062s
Total Simple A* time : 0.174318s
RSR: 7999 rects.
RSR test successful.
Total Simple A* time: 1.1812s
Total RSR time : 2.48749s
Jump Point Search test successful.
Total Simple A* time: 1.21122s
Total JPS time : 1.35729s

This is JPS with some optimisation too to speed up the scanning.

Really, it seems that as long you can replace the A* priority queue with a bucketing approach, you'll make it much much faster. This could also be done with RSR and JPS with enough buckets, but simple A* is good enough for now.

---

Next, Landmarks. I've disabled them. The asynchronous background update makes the game non-deterministic, which is bad for debugging at least.
A deterministic asynchronous update is possible by simply using the previous turn's heuristic (for known movement types), and computing the next in the background, but that makes the heuristic part of game state.

Surprisingly, there's not much performance loss. T210 time goes up to ~0.9s.

---

Finally, terminal woes. The greatest problem of all time: You can't shift-click buttons on Windows Terminal or the Linux Terminal I'm using. So, um... who likes good ol' reliable Windows Console? I have no idea how to fix this problem properly. What magic ANSI sequence disables shift mouse selection? "Sticky shift" is a maybe.

*Mapped right-click to shift-left-click. It works for production queuing. But no more right click.

snowern's still doing amazing things 7 months on

 

[snowern]

Options, maybe some of them even work.

Some of them are forced though, mostly because there's no animations.

snowern's still doing amazing things 7 months on

It's held together by only the finest duct tape.

Like, how do options work. There's a player options net message you have to send. What does that (exactly) do I wonder. I can only guess. And when do the options get set in CvUserProfile? Before sending the message or when the message is executed? All engine-side stuff, it's not in the logs.

And everything is global. It's hell. I've got game loading implemented through the in-game menu, and I basically just tear down the entire UI scene and do *this = CvInterface() to make sure there isn't anything left over.

Interestingly though, this options dialog is owned by python code, afaik. As in, if you destroy the CyGTabCtrl, the dialog disappears. Screens aren't like that, they are persisted in the engine.

 

[Blake00]

Brilliant work mate.

 

[snowern]

Actually playing a game for once... Standard size, noble difficulty, debug build. Not doing particularly well for noble. This is a test save, so it didn't exactly have good play at the start. But should be able to win Lib at least, right?

 

[<Nexus>]

Wow!
It's a bit strange to look at the game like that
Maybe do a "Let's play video" sometime

 

[snowern]

What the... I hope there isn't some mysterious AI bug floating around that's my fault.

Maybe do a "Let's play video" sometime

Yes, I might. Just to at least show that the thing works when you struggle to compile or get it running yourself. No commentary though. Just listening to them Civ4 terrain soundscapes.

*Found a bug where the pathfinder was not being reset when it should

 

[snowern]

Half functional new game setup. A few extras added to the UI. I'll be getting back to this in a few days. Maybe I should move the player list to where the victory options are.

 

[<Nexus>]

At size I see two selections: Huge and 18x.
Does it mean that this setting is 18 times the size of Huge or just Huge is 18 times the size of Standard?

 

[snowern]

Huge, 10x in each dimension. The size hack multiplies the size of whatever is returned by the map script. I currently get some python error generating that map though, will have to fix.