Mini-engine progress

[Tabris]

Definitely a priority on our side is to spread the word, especially to C2C devs. The gameplay in C2C is too overwhelming and too much to take in at once for me personally, but the user interface, such as the research screen, tech discovery window, etc., is absolutely top notch. There's already great talent out here, and plenty of it.

I mean... I assume spreading the word is something to do more once the code is online for people to contribute, no?

 

[snowern]

Practically, a graphical update would be an entirely new codebase or at least one giant fork that replaces whole swaths of code. The only use of my code at the start would be to init and get a map loaded. A lot of stuff does not need my code, like NIF loading and UI. Now, what could be done is a "libciv4", a common lib for TUI, graphics, servers (if somebody were to ever do that...), and headless AI training. That's out of scope for now though.

 

[Tabris]

Practically, a graphical update would be an entirely new codebase or at least one giant fork that replaces whole swaths of code. The only use of my code at the start would be to init and get a map loaded. A lot of stuff does not need my code, like NIF loading and UI. Now, what could be done is a "libciv4", a common lib for TUI, graphics, servers (if somebody were to ever do that...), and headless AI training. That's out of scope for now though.

Of course. I'm just excited here but I assume parity with the original engine should be the main focus with stuff like that only after that.

Edit: Fixed the quote. Lol

 

[<Nexus>]

W
@Tabris , you answered to yourself?

Will / should a new engine support more than just one dll? Is it desirable at all?

 

[Slaughter]

When it comes to terrain, because support for galactically sized maps would be ideal, more detailed terrain meshes would be possible, as terrain would have to be streamed anyway.

The potential for HUMONGOUS MAPS is a big part of what makes me giddy about this project.
I'm the kind of guy who always likes to play in the biggest map type available in strategy games.

I dream of a colossal Earth Map...

 

[snowern]

Turn 200 on Huge x10^2 Pangaea, Epic. Still haven't met anybody.
Also, physically-based hill rendering.

This map is so big that there's a vertical wall of tundra to the west. Takes about 37 seconds to end this turn on a 12600.

80% of time is spent on barbarians I guess. 93% on path finding.

Which is odd, because the only barbarian that entered my territory was a galley. Guess they're all having a party elsewhere. They did gradually whittle down all my tribal village scouts and warriors to one.

Apart from that, one lingering annoying thing is that auto moves need game ticks, and as this isn't a realtime UI, that means you need to press Enter to auto move each unit. I would like to find a solution. I was simply calling sendAutoMoves on every action, but that caused the game to become stuck unless you did something like click on a unit, for some reason. Need to find out how to detect pending auto moves and automatically tick the game.

 

[<Nexus>]

Turn 200 on Huge x10^2 Pangaea, Epic. Still haven't met anybody.

Am I reading it right??? It is 100 times bigger than Huge?

 

[Gameboy2396]

...because the only barbarian that entered my territory was a galley. Guess they're all having a party elsewhere. They did gradually whittle down all my tribal village scouts and warriors to one.

I think though that because the map size is 100 times larger than a Huge map, the code for this kind of size hasn't been altered to cater for these galactically sized maps. That's why the barbs are so sparse because I think the game is drawing from the python code that already exists for Huge map sizes.

 

[snowern]

Am I reading it right??? It is 100 times bigger than Huge?

It's big. Very big.

I think though that because the map size is 100 times larger than a Huge map, the code for this kind of size hasn't been altered to cater for these galactically sized maps. That's why the barbs are so sparse because I think the game is drawing from the python code that already exists for Huge map sizes.

There are indeed barbarian units. Something has to be eating up 80% of time.
Here's the stats ignoring visibility:

And remember how I said that path finding was inefficient. All those units are finding target cities and searching huge chunks of the map.
I wonder if they could be threaded, but the chances are that barbs can't be updated in parallel. But maybe they could be changed to retry their previous decisions.
Although... a huge majority of those barbs don't attack cities, so why is AI_targetCity taking up 80% of time? Something seems off, or those 48 warriors really are taking ~0.7s each to update.

I'll probably play again with no barbs and max AI.

Another thing is that with a map of this size, you could basically fit an MMO on it. Just have like a 100 players. Far less AI decisions to bog things down. If somebody wants that, they can try to get multiplayer working. Well, I suppose that would benefit from a realtime graphical implementation.

 

[<Nexus>]

Just a random thought: is it really good to test two revolutionary things at the same time? I mean a new engine AND a super big map size? Shouldn't the engine first work on more normal map sizes first? Can't it be that what works on normal sizes, won't work on humongous ones?
Just a layman's thoughts.

 

[1SDANi]

Just a random thought: is it really good to test two revolutionary things at the same time? I mean a new engine AND a super big map size? Shouldn't the engine first work on more normal map sizes first? Can't it be that what works on normal sizes, won't work on humongous ones?
Just a layman's thoughts.

Using a larger than normal map is a very solid way to test how the engine performs at scale, if it works for an absurdly sized map it will work for a normal sized map, it's sorta like how elevators are designed to be able to carry way more than they'll ever need

 

[Sephi]

Although... a huge majority of those barbs don't attack cities, so why is AI_targetCity taking up 80% of time? Something seems off, or those 48 warriors really are taking ~0.7s each to update.

Sounds about right. Games with bigger maps these days usually use algorithms that are much faster than A* (but non optimal)

 

[Tabris]

Just a random thought: is it really good to test two revolutionary things at the same time? I mean a new engine AND a super big map size? Shouldn't the engine first work on more normal map sizes first? Can't it be that what works on normal sizes, won't work on humongous ones?
Just a layman's thoughts.

Not ap rogrammer as well but I imagine that is like a stress test. Easier to see what has the most effect on performance when you have a huge map like that.

 

[<Nexus>]

Using a larger than normal map is a very solid way to test how the engine performs at scale, if it works for an absurdly sized map it will work for a normal sized map, it's sorta like how elevators are designed to be able to carry way more than they'll ever need

Not ap rogrammer as well but I imagine that is like a stress test. Easier to see what has the most effect on performance when you have a huge map like that.

Yes, if it is meant to be a stress test.
Like, if the elevator is tested for loadability put more weight in it than it should normally carry.
But if it is a precision test, so the elevator should stop at the exact hight by milimeter, than you will test it first empty.

But @snowern surely knows better what he is doing, so I stop here and leave it to him

 

[<Nexus>]

Ohh, I started dreaming about really huge and beautiful maps with Natural Wonders taking place on several plots, like the Grand Canyon or the Dead Sea.

 

[AOS9001]

Here's the stats ignoring visibility:

1,397 lions, good grief. I can't imagine what a mess this map will be once empires get developed and the doomstacks start marching.

 

[f1rpo]

In mods that have reimplemented A*, or at least in K-Mod, I think a parameter that limits the maximal path length to consider has helped performance a good deal. In the city loop in AI_targetCity, a limit based on the closest city found so far could save time while preserving the BtS behavior. And maybe ordering the cities by air distance upfront. That is, if it's really the generatePath calls in that loop that take up so much time.

 

[snowern]

Okay, T200 without barbs and with 18 civs, it's ~11s to end the turn. Much faster, but still slow.

Most time is spent by AIs making decisions inefficiently:

• AI_explore loops over every plot on the map.
• AI_getEspionageTargetValue will path to most cities, but this is limited by a low max turns of 10.
• AI_merchantMove -> AI_trade paths to most cities I think. This has calculated threshold, but may not be all that useful.
• AI_spreadReligion (missionary) paths to most cities.
• AI_attackMove is the last 10%.
  • AI_group loops over all other units and conditionally paths to them.
  • AI_protect loops over every plot on the map to find owned plots.
  • AI_guardCity does a little bit of pathing.

In mods that have reimplemented A*, or at least in K-Mod, I think a parameter that limits the maximal path length to consider has helped performance a good deal. In the city loop in AI_targetCity, a limit based on the closest city found so far could save time while preserving the BtS behavior. And maybe ordering the cities by air distance upfront. That is, if it's really the generatePath calls in that loop that take up so much time.

And that would help.

Sounds about right. Games with bigger maps these days usually use algorithms that are much faster than A* (but non optimal)

Yes, the big problem currently is that the pathfinder assumes that there can be railroads anywhere that could create a much cheaper path. So it basically degenerates to Dijkstra, the heuristic is near useless.

It would be great if we could use some form of hierarchical pathfinding: https://factorio.com/blog/post/fff-317. Even better if it could remain optimal. Another idea is "differentials" or landmarks. The key is to use a better heuristic to produce a valid underestimate that is close to the true path cost.

 

[alberts8]

You are basically creating a completely new game using the original Firaxis Civ4 source code as a starting point. In the Caveman2Cosmos modding community we had discussed the same approach year's ago. Because of the legal aspects nobody started working on it seriously. Creating a re-implementation like UnCiv or FreeCiv instead seemd like the less problematic approach. But without anyone having the necessary game development experience this didn't go anywhere.

I'am hoping that you figured out the legal aspects because your project looks interesting even without fancy graphics

 

[snowern]

Many games have got reimplementations. But Civ4 will be different from most as you have the DLL source available. There's always the chance it might get nuked, but unlikely. They might not pay much attention to a mere console implementation.

Anyway, I want to make super huge maps practical by improving the pathfinder. Just like Factorio, I'm starting with a coarse heuristic to make A* not so much like dijkstra. Cut down on the visit set:

16x16 blocks. The coarse uniform-cost heuristic is itself a pathfinder, which starts from the goal. Even with this overhead, a basic min movement cost path search, using a std priority queue and a hash map of nodes, is much faster than vanilla. Some of that advantage will diminish though once I include all the pathing checks in pathCost and pathValid.

And that's without caching. I hope caching will be effective. Cache both the coarse heuristic and plot-wise block-local paths. One annoying thing though is that pathValid depends on enemy positions, including barbs, and there's a handful of animals running around in every block. What I would probably do is switch to a binary block-local validity check for distant blocks. Technically suboptimal, but such checks will become out of date anyway until you get close.

And on top of path caching, AI path requests could be improved with turn limits just like K-Mod, and use of the coarse heuristic when finding the nearest city. Only takes about half a millisecond to compute the coarse heuristic. And to help path caching, it would be better to start pathing from stationary targets rather than units. This is another slight sub-optimality as Civ4 movement is asymmetric: it can take a few extra turns to go in the opposite direction.