Mini-engine progress

[<Nexus>]

So what is ID allocation limit? Can it be increased?

 

[snowern]

So what is ID allocation limit? Can it be increased?

8K.

#define FLTA_ID_SHIFT                (13)
#define FLTA_MAX_BUCKETS        (1 << FLTA_ID_SHIFT)

I could either change it to 16 bits for both the index and ID (it's actually the index that's limited), or go 64-bit. 64-bit is your future proofing, but would require extra changes all around the DLL.

Don't need to do it yet. But once the AI starts defending thousands of cities, I might have to. If I get that far.

But optimisation is getting increasingly difficult. Got pirating under control, but it's still 16s for turn 522.

Pirating is really the worst case. Bunch of units pathing all around the map. Spy move is almost entirely mission execution. You'd need faster pathing, or path caching, or a better parallel unit update to speed that up.

Irrigation update and AI_updateRouteToCity are next, but getting mid-game turn times under control is not going to be possible for 10x Huge. The AI stuff will just need a whole rework. Or I extend the parallel unit update implementation to cover most AI, but... ehh... Maybe I should just find the biggest playable map size that doesn't require herculean parallel AI efforts.

 

[<Nexus>]

8K.

Wow! That's a lot. I guess we run out of city names much earlier.
And what's the limit on units? If it's also 8K than...

Maybe I should just find the biggest playable map size that doesn't require herculean parallel AI efforts.

Just wanted to ask about that.
Maybe limit the game to a map size that won't exceed the limits?

 

[devolution]

Let me start out by saying that I’m very impressed by your efforts and skill.

... before diving straight into the nerdy stuff:

What are the average- and worst-case sizes of your open list?

I’m asking because the K-Mod Pathfinder (refactored and improved by @f1rpo for the Advanced Civ Mod: https://github.com/f1rpo/AdvCiv/blob/1.12/CvGameCoreDLL/KmodPathFinder.h
) stores its open list in a std::vector. That means that the two (or three depending on your viewpoint) critical open list operations have the complexity:

1) Finding the minimum element requires a linear scan (O(n)). Quite a bit worse than the heap but extremely cache friendly.
2) Appending a new element is a constant-time push_back (O(1)).
3) Removing an element is just swapping with and popping the last element (ok since the list is not ordered and we're already committed to a linear scan)

I'm curious what numbers you are seeing. Also note this comment:

/* advc.opt: In a test over a few turns on a Giant map with 36 civs,
the mean list size at the start of processNode was 80, and the
maximal list size 333. In a longer test on a Huge map with 18 civs,
reserving memory for 128 nodes was faster than for either 32, 200 or 256
(power of 2 does seem to help). K-Mod didn't reserve any memory. */

However, it very likely that you are seeing much worse numbers considering your 1000x1000 map! Still it would be interesting to know the inflection point of a heap vs. a vector with respect to the open list.

See this as well

/* ^Looks like K-Mod has already tried a heap (std: priority_queue). Or maybe
it was abandoned w/o a test. Would have to re-heap after recalculateHeuristics.
And the functor should take m_stepMetric.getMaxPath() as a contructor argument
so that nodes within that limit can receive absolute priority. But, given the
modest number of open nodes, I doubt that a heap will be worthwhile. */

Finally, the linear find-min scan could itself be sped up by using branchless AVX2 code, effectively pushing the heap-vs-vector inflection point even higher. Have you (or anyone) actually measured where that sweet spot lies?

 

[snowern]

Let me start out by saying that I’m very impressed by your efforts and skill.

... before diving straight into the nerdy stuff:

What are the average- and worst-case sizes of your open list?

I’m asking because the K-Mod Pathfinder (refactored and improved by @f1rpo for the Advanced Civ Mod: https://github.com/f1rpo/AdvCiv/blob/1.12/CvGameCoreDLL/KmodPathFinder.h
) stores its open list in a std::vector. That means that the two (or three depending on your viewpoint) critical open list operations have the complexity:

1) Finding the minimum element requires a linear scan (O(n)). Quite a bit worse than the heap but extremely cache friendly.
2) Appending a new element is a constant-time push_back (O(1)).
3) Removing an element is just swapping with and popping the last element (ok since the list is not ordered and we're already committed to a linear scan)

I'm curious what numbers you are seeing. Also note this comment:


However, it very likely that you are seeing much worse numbers considering your 1000x1000 map! Still it would be interesting to know the inflection point of a heap vs. a vector with respect to the open list.

See this as well


Finally, the linear find-min scan could itself be sped up by using branchless AVX2 code, effectively pushing the heap-vs-vector inflection point even higher. Have you (or anyone) actually measured where that sweet spot lies?

The nerdy stuff. Open set size goes up to around 2300 for 1040x640 on turn 520. I have tried different types of heaps. Currently using a quaternary heap in an array. Popping is the problem, so I think it's slow because it has to bubble down an element from the top to the bottom. And it does it for each active element in the SIMD vector.

I think my complicated SIMD hybrid heap thingy was a little faster still. But I don't like it because it's complicated. I think I need to update it too. And it really needs Clang's SIMD optimisation. So the fastest heap depends on which compiler you use.

Another heap was the Radix Heap. This was slightly faster than the typical binary heap, but requires monotonic pops, which doesn't quite happen because Civ4's path costs are weird.

The best heap is no heap at all. Which you can do if you only have a small number of distinct F costs at any one time. Then you can bucket them. This is trivial for a uniform cost grid (SEA UNITS). And this is what you can do if you redo the AI. You could respecify path costs to let you use bucketing (and then use an expensive pathfinder for accurate nearby pathing).

Updating the heuristic doesn't show up on the profiler. I also don't have a heuristic right now anyway, so I could just remove that code. A good heuristic would help, but I don't know of one. The vanilla heuristic underestimates too much to be useful, and the 16x landmark heuristic was very good, but needed to be kept up to date. I might try it out again though. Or at least, use the simple distance heuristic for sea units.

Scanning the open set with AVX512 is an idea. Scanning it for the smallest 16 elements would be slow, but I could scan it for the smallest element in each lane. It would be an approximation, which is fine as long you get the true minimum in one of the lanes. Alternatively, SIMD "partial sort".

Anyway.

Trying 5x Huge and CvPlotGroup::recalculatePlots has started to show up on the profiler, at about 55% CPU time on the main thread. Turn times are reaching ~20s at turn 536.

Maybe limit the game to a map size that won't exceed the limits?

Limit!? Maybe there could be a warning message.

Also, parallelism idea. In case you have a gigantic map with a hundred AI players, you'd want to parallelise across players too. This may be possible by adding a vulkan command queue to your game update function. If you can specify every operation on game state in terms of tasks with read/write dependencies, you can then have some task graph lib maximise parallelism. The difficult part though will of course be unit updates, as units logically depend on the whole map. But what would possibly, be possible, is to specify unit update writes as the set of all possible moves, with plot danger radius, and when some unit (of any player) wants to do some pathfinding, it could co_await updated pathfinding plot info when a pending plot shows up at the top of the open set. This may be insanely complex to implement.

*Using arrays instead of linked lists for plot group plot lists took 4s off turn time. And they're still slow.
*Uninitialised variable. I'm gonna fix the hundreds of clang warnings now...

 

[1SDANi]

20 seconds? Dang, Civ 6 takes double that for turn 1 on a Huge map with 19 AI. You're putting Firaxis to shame!

 

[snowern]

I'm sure Firaxis has run their game through a profiler and it's so well optimised now that their flame graph is filled with slithers of code that can be optimised no more. And slow performance is merely the result of having highly advanced AI.

(could probably find out if you profiled it yourself, as long as the DLL has symbols, I think)

Turn 1 does tend to be a slow turn in Civ4 too though.

I'm still getting plot groups v2 implemented. Managing plot groups block-wise with localised connectivity updates should make single-plot updates disappear from the profiler, but it's fiddly code.

if i could suggest one thing that may need to be murdered, dissected and rebuilt, it's the plotgroup system (which is the system handling which tiles are connected for resource access and trade purposes).

From what i've had to interact with, it seems very innefficient, with groups being completely deleted and rebuilt tile by tile each time there's an effect that impacts it ( pillaged road or improvement, discovered resources, ....)

(storage of the network is the key part to make that work, as of now, it's just a list of all the tiles in the group, without better understanding of the links between them)

But to Firaxis' credit, they did try local updates. But in the case of disconnect, it may recount all plots in the group. And that group might include the whole ocean, I assume.

With block-wise plot groups, CvPlotGroup will store a list of block plot group indices. But, you'd still need to loop over plots in case of split/join, to call CvPlot::setPlotGroup. This could possibly be threaded. Or further accelerated by counting bonuses block-wise (so, plots would have a CvBlockPlotGroup* and that will have a CvPlotGroup*).

*Cities will be the bottleneck of plot groups. I think I can get rid of individual plot updates, but CvCity::changeNumBonuses has complex logic that can't just be refactored away. Mechanical redesign though could do all city bonus updates during a single parallel city update, maybe, possibly. At least for AI, things that invalidate plot groups and things that depend on city bonuses could be separated within the turn.

 

[1SDANi]

I'm certain they did optimize their game thoroughly, and while you raise a good point regarding the first turn, turn 2 is just as slow in Civ 6 on a huge map with 19 AIs. Turn 2 isn't exactly known for its gridlock in that game, so the dead horse can be ruled out.

 

[Chrischn89]

Hi,

I'm new here and I've battled with myself if I should really write this because I've read this entire thread and its predecessor multiple times by now and I'm in awe about how many smart people gathered here that it's kind of intimidating posting something myself (seriously are all of you guys professional software engineers??) but I just couldn't resist any longer.

First of all @snowern: your Mini-Engine is insane! The amount of work, dedication and skill that it takes to create something like that is truly mind-boggling! Hats off to you!

The Mini-Engine can definitely be a huge stepping stone for a 'proper' Civ4 reimplementation in the future and a lot of commenters here have already shared valuable knowledge and opinions on all sorts of topics concerning an open source project, so a big THANK YOU to all of you who contributed so far!

I feel bad for 'hijacking' this thread with talks about anything other than the Mini-Engine itself but this seems to be THE place where the talks about an open source reimplementation of Civ4 go further than mere wishful thinking.

Now, I realize there is no active project at this point in time and not even a team because people are busy and/or the burden of responsibility for starting such a project is just too large. Unfortunately I'm no different and ontop of that I don't even possess half the skills some of you guys have (I'm just a lowly IT systems administrator) but nevertheless, I believe that every tiny bit of progress helps, even if its only by motivating other people to do the same.

So, I've spent my entire vacation creating a Godot project and watching tons of tutorials with the aim to see how far I can make it (I have never in my life worked with a game engine) but this is what I've managed to do so far:



Now don't get fooled by the screenshot with the globe (never realized that it was an actual 3D object in Civ4), I haven't done anything further than 2D GUI stuff yet. That background is literally just a screenshot from the actual game that I put in there as a texture to replicate the menu as pixel-perfect as I could (if you zoom in you can see a few blue pixels above SID MEIER'S, where my GUI overlay didn't align perfectly). The GUI is functional so far and follows the same design principles as the original menu (I know...) but it doesn't go very deep into the submenus.

I've also added a check at the start of the app where you get asked to provide the path to a valid Civilization4.exe (vanilla, non-BTS for now. Also the path is stored in a config file for the next startup) and then hashed and compared to a hardcoded one from my copy in order to confirm its validity. After a successful validation, the relative path from the .exe is used to load a couple of textures and fonts.
Unfortunately I haven't managed to load everything dynamically/during runtime yet, so there's no way to share it without including copyrighted assets and also I have no clue about trademark law, which is why I'm kind of nervous about posting screenshots with the actual Civilization logo on display, but I guess it's fine for the time being.

Anyway, one of the reasons why I'm posting this is that I've hit a roadblock. A lot of assets are provided via the .fpk files, which I need to fully recreate the main menu with and also I figured a good start for entering the 3D aspect of Godot would be to get that globe to render in the menu.
"But the amazing @snowern already deciphered the .fpk files!", I hear you say and that's true and so I happily grabbed a hexeditor and started counting bytes, only to realize that even with the knowledge of ROT+1 encryption and armed with the actual unpacked files (thanks to PakBuild) I just couldn't figure out the data structure of those .fpk archives in their entirety.

I would love to call the .fpk assets from the app so that 1.) I can remove all of the copyrighted files from the project in order to maybe share it on GitHub (Git is another thing that I barely know) and 2.) I can prevent myself from adding one of those assets by accident in the future and 3.) to continue glueing something together as described above

So if one of you guys maybe knows something that could help me close those gaps, so that I can start working on an import script, that'd be awesome!

What I gathered so far about .fpk archives (no guarantee that it's factual):

• Starts with a byte
• Then 16 bytes of header
• Then a list of all of the files that are stored further below in the archive (each entry ends with FF FF FF ?) (the file list is the only place where the ROT+1 encryption is used and nowhere else right?)
• Haven't figured out how the transition from the file list to the actual files is marked yet
• Then come the different types of files (.kf / .kfm / .nif / .dds) (each with their own end-of-file byte signature? For .kf files it seems to be 03 00 00 00 65 6E 64 01 00 00 00 00 00 00 00)?
• And then the archive reaches its end

I really hope that maybe some day we all get to play Civ4 with 64-bit memory addressing, galactically sized maps, performance increases that make late-game turns bearable and maybe even a mode where it's possible to colonize other planets from earth. Maybe Firaxis is going to release a remaster on the 20th anniversary of Civilization 4 in October? Well, guess that too falls under wishful thinking...

 

[Walter Hawkwood]

Take a look here: https://github.com/NicholasMoser/Naruto-GNT-Modding/blob/main/gnt4/docs/file_formats/fpk.md

While the game is different, from what I understand it's the same fpk format.

 

[Nightinggale]

armed with the actual unpacked files (thanks to PakBuild) I just couldn't figure out the data structure of those .fpk archives in their entirety.

Don't we have the source code for PakBuild somewhere? I will admit I never bothered to look into it because we have PakBuild and mods becomes less stable when using fpk files. Better to just release mods with all the files "unpacked".

Maybe Firaxis is going to release a remaster on the 20th anniversary of Civilization 4 in October? Well, guess that too falls under wishful thinking...

Never say never, but I find it unlikely. On top of the workload in doing so, remember how people got upset when they added support for multiplayer through steam. The problem was not the new feature, but that it stopped being network compatible with non-steam versions and it became less mod compatible. Kind of hard to make a remaster, which is modern and at the same time supports the old mods. The backlash was big enough for them to release the previous version as a beta in steam, so they certainly noticed. It's possible Firaxis will see a remaster as expensive and it just won't sell because people get upset about changes. Also from a pure business perspective, it might be more cost effective to produce random DLCs for the newest version.

It's a nice idea with a remaster, but I won't hold my breath for that to happen, certainly not one, which will benefit modding. Also did they ever release a remaster of any of the other civilization games? I don't remember them ever doing that.

(seriously are all of you guys professional software engineers??)

I can confirm that there are indeed engineers in this thread (yes plural) and while I'm not aware of any confirmed non-engineers, I have to say that I don't know the education level of most people. Personally I'm not too concerned with titles. Skills are more important and that's certainly present here.

 

[<Nexus>]

Better to just release mods with all the files "unpacked".

...and load time dramatically increases.
Maybe it's not this way with Col but it is with Civ4. Just try loading Quot Capita Majesty mod. It takes around 15 minutesto get to the main menu.

 

[snowern]

a Godot project

I get to see what Civ4 in Godot would be like!

A lot of assets are provided via the .fpk files

Yes, you just need to load a NIF. Sounds like a Fun thing to do.

It's referenced through CIV4MainMenus.xml.

And hook up a VFS into however Godot loads resources I guess. Can you memory-map the FPKs?

FPK format is:

• u32 version?
• u32 magic
• u8 unk
• u32 numFiles
• for each file,
  • char[u32] path ROT-1
  • u8[align path to 4 bytes] padding
  • FILETIME (I think)
  • u32 size
  • u32 file address

Then you need NIFs. Without actual DLL integration, you'd just be testing NIFs I suppose. With animations.

With DLL integration, you could maybe do what I did. Just load a game straight away inside main(), init your CvInterface implementation, and within your "world view", show the most basic representation of plots that shows it works. I think this is mostly a giant heightmap actually, pieced together from lots of little textures. And you'd have one global light. You'll zoom out, and say it finally works.

In-game UI will be something else. How will you do that. The DLL and scripts have expectations. The DLL wants controls that trigger specific actions, it reads modifier key state. And scripts handle screens, and build screen UIs.

Main menu UI wouldn't be so annoying. It's definited in the application. So I suppose you'd just do whatever the normal Godot UI stuff is.

It's possible Firaxis will see a remaster as expensive and it just won't sell because people get upset about changes.

We'll have to do it ourselves. Combine the DLL of Civ4 and the assets of the prettiest Civ game. It will be beautiful.

Anyway... I've got a plot groups reimplementation going finally. Need to integrate it into the DLL and test it.

 

[Nightinggale]

...and load time dramatically increases.
Maybe it's not this way with Col but it is with Civ4. Just try loading Quot Capita Majesty mod. It takes around 15 minutesto get to the main menu.

It's the same with Colonization, but at the same time We The People won't work when packed. I had issues with Medieval Conquest too (another colo mod) back when it had the files packed. Usually problems means some people have consistent crashes prior to the main menu and making the game in general more prone to random crashes. Sure slow startup isn't great, but it's better than crashing.

Pure speculation is that the exe indexes all the files in the mod and since startup time increases seemingly exponentially with the number of files, odds are that the exe failed to follow tip 5 from this thread (so basically it sorts everything in std::map whenever something is added). This is something we can and should avoid with an exe remake.

M

Post in thread 'Some C++ Tips to make CvGameCoreDLL to run faster'

Nov 25, 2023

Tips5: Use stdext::hash_map instead of std::map
In vc7.1(vc 2003), the performance of std::map is poor because it needs sort, and it's speed is O(N)
use the stdext::hash_map can have the O(1) speed to search because it use hash function.

• mediv01

• 

Anyway... I've got a plot groups reimplementation going finally. Need to integrate it into the DLL and test it.

I did a reimplementation in Medieval Conquest years ago because there is no plot group support in the colonization exe. It's actually not that hard to do, through I admit my goal was to get it working and not try for my current performance goals.

In-game UI will be something else. How will you do that. The DLL and scripts have expectations. The DLL wants controls that trigger specific actions, it reads modifier key state. And scripts handle screens, and build screen UIs.

It probably needs some sort of "translation layer". I wrote a python file to try to get an overview of what python expects when getting an input from the exe. Not all features mentioned in this file are available in pedia when opened from the main menu, but they are if opened after loading a game. Overall it's not a good system, so the goal should likely be to make a new system and add something to make it backward compatible to avoid having to rewrite all UI in all mods.

Mod/Assets/Python/XmlEditor/xmlInput.py at develop · We-the-People-civ4col-mod/Mod

This is the repository where the mod resides. . Contribute to We-the-People-civ4col-mod/Mod development by creating an account on GitHub.

github.com

 

[Chrischn89]

Take a look here: https://github.com/NicholasMoser/Naruto-GNT-Modding/blob/main/gnt4/docs/file_formats/fpk.md

While the game is different, from what I understand it's the same fpk format.

Thank you for the link! Unfortunately it doesn't seem to be the same type of .fpk archive but it helped me understand file archives in general!

Don't we have the source code for PakBuild somewhere? I will admit I never bothered to look into it because we have PakBuild and mods becomes less stable when using fpk files. Better to just release mods with all the files "unpacked".

I've tried googling and found two or three community-made "Pakking" Tools for CivIV, but none with source code as far as I can tell.

And hook up a VFS into however Godot loads resources I guess. Can you memory-map the FPKs?

From what I understand you can pretty much do anything with Godot. There seems to be a virtual filesystem, where resources can be imported via Drag&Drop but also via script during runtime: "res://" (read-only, during runtime) and "user://" (write-access during runtime).
I've written a GDscript that serializes .fpk archives but only in order to understand better how they're structured and not for doing much with the data inside... yet! I haven't looked deeply into how the filesystem works because of that.

FPK format is:

• u32 version?
• u32 magic
• u8 unk
• u32 numFiles
• for each file,
  • char[u32] path ROT-1
  • u8[align path to 4 bytes] padding
  • FILETIME (I think)
  • u32 size
  • u32 file address

Thank you so much! That list helped immensely! With that I could finally understand the structure for the most part:

Still no clue what the byte at 0x08 does but at least it's always consistent. The yellow line is more troublesome. It varies in length and there seems to be some logic behind it, but I can't for the life of me figure out what it's for and I've tried a lot (hashes, filetime, compression etc.). I've compiled a spreadsheet with all the 'signatures' of the four official CivIV .fpk archives and one from the RoM:AND2 for comparison: cryptpad.fr Link
For accessing the files the variable length 'signature' is no problem for now, because I can always check where the next file path begins (in the official archives the next entry always starts with "art"/"bsu" (de-/encrypted)) or if the End of File List Marker is ahead.

Then you need NIFs. Without actual DLL integration, you'd just be testing NIFs I suppose. With animations.

Yep, that's the step I'm currently working on but struggling.

With DLL integration, you could maybe do what I did. Just load a game straight away inside main(), init your CvInterface implementation, and within your "world view", show the most basic representation of plots that shows it works. I think this is mostly a giant heightmap actually, pieced together from lots of little textures. And you'd have one global light. You'll zoom out, and say it finally works.

That's definitely a goal for a later phase. For phase 1 I want to show that we can load official assets during runtime and spawn 3D objects in the game world, like a tech-prototype in Godot to show people that it's doable. It's going to take a while but I'm very motivated and I'm spending my entire free time on it.

In-game UI will be something else. How will you do that. The DLL and scripts have expectations. The DLL wants controls that trigger specific actions, it reads modifier key state. And scripts handle screens, and build screen UIs.

That's good to know and once we can load all the official assets and draw all kinds of 3D objects we can start merging those two worlds together!

Main menu UI wouldn't be so annoying. It's definited in the application. So I suppose you'd just do whatever the normal Godot UI stuff is.

I think so too, although the theme files .thm for Scaleform are all there. It would take quite a while to figure out what every config entry does, so a main menu based on just Godot would be far quicker but in the end, if we wanted to achieve 100% compability with all the existing mods that modify the menu, we would have to understand Scaleform and load the values from the theme files anyway, so that mods could overwrite them (I know that C2C does this for example)

It's the same with Colonization, but at the same time We The People won't work when packed. I had issues with Medieval Conquest too (another colo mod) back when it had the files packed. Usually problems means some people have consistent crashes prior to the main menu and making the game in general more prone to random crashes. Sure slow startup isn't great, but it's better than crashing.

Maybe it has to do with the compression or the way PakBuild works? I've noticed differences in the 'signature' part of .fpk archives that were created by using PakBuild versus the offical ones. Maybe there's a bug hidden somewhere? Creating single file .fpk archives via PakBuild's CLI helped me greatly with understanding them but that is probably no news for you since you've posted in the exact same thread where I learned this from haha

It probably needs some sort of "translation layer". I wrote a python file to try to get an overview of what python expects when getting an input from the exe. Not all features mentioned in this file are available in pedia when opened from the main menu, but they are if opened after loading a game. Overall it's not a good system, so the goal should likely be to make a new system and add something to make it backward compatible to avoid having to rewrite all UI in all mods.

100% agree!


--------


So, I've been trying to get into drawing models in the 3D world world and stuff, to learn the ropes, so that I can load the civ4mainmenubg.nif from the Assets3.fpk, which also means that I had to deal with .nif files. So the main menu background .nif has upwards of 2000 'blocks/nodes' while a simple axeman unit has 14... so I present to you:

I haven't drawn this model via script yet though. I've just exported the .nif as an .obj via NifSkope and then imported it manually as resource and dropped it into the game world. I think the reason why he's all red is, because of the 'TeamColor.bmp' that sits ontop of the actual unit texture but at least the axe is fine. Anyway I started looking into what 3D formats Godot can actually handle: Link -> gITF 2.0 (recommended) ; .blend (Blender) ; DAE (COLLADA) ; OBJ (Wavefront) ; FBX (via FBX2gITF integration).

So from what it reads like, the Godot team clearly recommends gITF 2.0 as the other are either older, feature limited or proprietary. So I guess gITF 2.0 is the way to go? Converting a .nif to a gITF 2.0 format during runtime is going to be quite the task. I've looked through a lot of knowledgebases and GitHub projects to see if someone already did exactly this but I guess not. The closest thing that I found, which has already been mentioned here before by @oldbay, is niflib (C++) and nifxml from the creators of nifskope, which would allow us to at least read a .nif before converting it to something else.:

For NIF support i'm found:
* Editor (https://github.com/niftools/nifskope)
* C++ lib (https://github.com/niftools/niflib)
* Python lib (https://github.com/niftools/pyffi)
* Pprogram code OpenMW - They also imitate Gamebryo work (https://gitlab.com/OpenMW/openmw)

Update: oh, after some further reading I realized that maybe we don't need to convert .nif files to gITF 2.0, because we don't want to store converted assets in the project permanently. I think it might be possible to put together 3D objects entirely via GDscript with functions like MeshInstance3D (Properties: Mesh, Skeleton, Skin)...


So yeah I guess actually using the .nif files in Godot is going to take a while, but at least I can now start working on loading the more simple files like .dds and .ttf first, so that I can replace the imported resources entirely.

 

[snowern]

I think so too, although the theme files .thm for Scaleform are all there.

I entertain that thought too. You could probably create an exact UI replication if you build your own UI system and use the theme files. And make it scalable. This is basically making your own CEGUI. I'm not quite sure how it works exactly though.

So yeah I guess actually using the .nif files in Godot is going to take a while

Yes, that's what an engine reimplementation would have to do. It would need a NIF loader. And NIFs are not simply meshes. They are parts of a full scene. They have materials, animations, lights, particle systems, a camera, and maybe other things.

You would need to load these NIFs into a traditional OO scene hierarchy, and somehow have these objects control things in Godot.

 

[Nightinggale]

I've tried googling and found two or three community-made "Pakking" Tools for CivIV, but none with source code as far as I can tell.

Looking around, it seems people claim PakBuild is released by Firaxis themselves as a service to mod creators. Google's AI states the source code has never been released and sure enough there is no trace of it.

While being able to read the format would be good, we could consider the option to include PakBuild and hence extract fpk files prior to reading files using a new engine. This means it's a less critical part compared to reading/converting the graphics. If we need to unpack fpk files anyway, it would be a fair argument that converting graphics to a modern format using external tools would be an option, through it is important to remember that we can't distribute vanilla meaning any conversion will have to be scripted for the end user. Being able to read the files and convert in memory at startup for both would be preferable, which means we shouldn't drop that goal. It's more like it's a matter of priorities.

1. load converted graphics
2. load original graphics and convert on load
3. extract fpk at startup

We should likely do it in this order because if a step can't be done, then the following steps becomes pointless.

 

[Chrischn89]

While being able to read the format would be good, we could consider the option to include PakBuild and hence extract fpk files prior to reading files using a new engine. This means it's a less critical part compared to reading/converting the graphics. If we need to unpack fpk files anyway, it would be a fair argument that converting graphics to a modern format using external tools would be an option, through it is important to remember that we can't distribute vanilla meaning any conversion will have to be scripted for the end user. Being able to read the files and convert in memory at startup for both would be preferable, which means we shouldn't drop that goal. It's more like it's a matter of priorities.

1. load converted graphics
2. load original graphics and convert on load
3. extract fpk at startup

We should likely do it in this order because if a step can't be done, then the following steps becomes pointless.

I have played with the idea of letting the user extract the .fpk files prior to starting the game but that would be a huge inconvenience for most. The idea of including PakBuild is really good but in the end, I don't think either of these options are necessary, since I've already completed the script to read the archives and load the contents into a key-value dictionary in Godot, so that I can call the contents up whenever I need them. The project folder is consequently completly clean!
Guess that leaves me with loading the graphics...
I'm currently reading and researching a lot about graphics and 3D models as it's an enigma to many, me included. My intermediate goal is to load and draw a very simple .nif file (like a road, "roada00.nif" for example, way easier than units with skeletons or the main menu.nif with its 2k+ nodes) but even for that I need to understand how .nif files work. From what I've gathered those NiNodes? are not too different from scenes in Godot.

My immediate problem though is that .nif files can be hugely complex inside and deciphering all of that would take ages for me alone. There is indeed a lot of spread out information about .nif files out there but I couldn't find an easily digestible source. The best I have is the niftools-project. (https://www.niftools.org/) but that's where my lack in software developing experience makes things difficult. They have different libraries full of functions that deal with .nif files for every major game that uses them in all their different versions (https://github.com/niftools/nifxml/blob/master/nif.xml - line 172) but the documentation assumes you already know a considerable amount about the topic.
Ontop of that I need to add one of those libraries (I think niflib C++ is the best fit) to the Godot project in order to play around with them some more but in order to do so I had to spend the past two days dealing with GDExtensions, which is Godot's way of adding C++ code to a project. I'm going to have to spend more time with that this week, as sooner or later the CvGamecoreDLL would have to be tacked on the same way anway, so I might aswell put in the work now.

In any case, I've also started using Git and GitHub to track my progress. The repository is private for now until I figured out the legal aspect of a project like this before I go public but I think I'm pretty close to having it figured out (I'm gravitating towards a GPLv3 license, so that any potential derivates are going to stay open-source aswell).

 

[snowern]

Plot group system finally replaced and (minimally) tested. Good lord.

How this thing works​

PlayerTradeNetworkSystem is the top-most class. It takes cities, bonuses, CvPlot::isTradeNetwork and CvPlot::isTradeNetworkConnected, and feeds them into a generic TradeNetworkSystem.

TradeNetworkSystem is a blockwise dynamic connectivity implementation.

• Within blocks, uses union-find to group plots and build block plot groups (BPGs).
• Across blocks, uses union-find to group BPGs into civ plot groups (CPGs).
• Tries to locally update BPGs and CPGs.
• Stores plot groups in a TradeNetworkCore.

TradeNetworkCore is a dumb class, or the bonus distribution class, that simply stores the BPGs, CPGs, bonuses, and cities. It at least tries to minimise city updates given the membership changes.

Integration​

When loading a save, the original CvPlotGroups are thrown out and replaced by the new system. City bonus counts are reset.

When saving, plot groups are saved in the original format. This means that the save will be compatible, but may not match due to plot group reindexing.

All references in code to original plot groups are changed to refer to the new system. There is no longer a CvPlot::getPlotGroup when using the new system.

The new plot group system can be enabled independently of gigantic map optimisations, which is useful for testing. Config macro is ENABLE_PlayerTradeNetworkSystem currently.

Testing​

Testing was done with a Huge/Normal map from turn 0 to victory.

On init, the system can check that city bonuses are unchanged compared to the original CvPlotGroup bonuses.

On every turn, the system can verify itself. It will check the cached plot properties and perform global union-find.

And that's the simple stuff, easy to get right. What took a long time was stopping game state divergence between CvPlotGroups and the new plot group system.

It took a long time because there's all these vanilla code bugs, which really screws with testing because you just assume Firaxis' code is bug-free, right?

I tested by comparing verbose checksum logs as usual. The process is like https://straypixels.net/wwag-divergence/.

Initially with a per-turn checksum from a python script, then I moved onto a DIVERGENCE_CHECKPOINT macro for even more logging, and the ability to change logging frequency and range. This allows you to efficiently narrow in on the source of a bug.

Bugs tended to involve city updates. As the new plot group system does not update cities as often, this exposes missed city update bugs.

So now there's a new config macro, ENABLE_GAMECOREDLL_FIXES, that fixes a whole bunch of bugs:

• Various things that change YIELD_PRODUCTIONforgot to update commerce rates (presumably, when producing commerce).
  • You can see this in-game. If you have a city with a forge, factory, and ironworks, and no power, and it's producing research, then you link up coal. It's research output won't change until you trigger an update.
• City maintenance depends on GET_PLAYER(getOwnerINLINE()).calculateInflationRate(), which depends on game turn and era. So I added updates when those change.
• CvCity::init/kill forgot to update city maintenance of the master, when city maintenance depends on vassal city count.
• CvPlayer::acquireCity intentionally skips some plot group updates. I added a few more in to at least satisfy log comparisons.
• Vanilla plot group system does not correctly handle the case where a single-plot plot group becomes !isTradeNetwork. The plot group path finder will still count the plot because the start node is always valid.
• CvTeam::setOpenBorders invalidates CvPlot::isCity but was missing a plot group update.
• CvPlot::isTradeNetworkConnected is not symmetric, but the vanilla plot group system appears to assume it is symmetric (an undirected graph instead of a directed graph). This is the biggest mechanical change:

bool CvPlot::isTradeNetworkConnected(const CvPlot* pPlot, TeamTypes eTeam) const
{
    // ...

#if ENABLE_GAMECOREDLL_FIXES
    if (!isOwned() || !pPlot->isOwned())
#else
    if (!isOwned())
#endif
    {
        if (!isRevealed(eTeam, false) || !(pPlot->isRevealed(eTeam, false)))
        {
            return false;
        }
    }
    
    // ...

Originally, if plot A is unowned and either is not revealed to the team, then plot A is not connected to plot B.

When symmetric, if either plot is unowned and either is not revealed to the team, then plot A is not connected to plot B.

I presume there will be no problems with that.

When loading a save, city maintenance and commerce rates will now be updated, just in case.

Performance​

Yes, actually get back to testing that 540x320 map...

With MSVC, with the original plot group system (with faster plot counting), and with fixes: CvPlotGroup::recalculatePlots took 38.14% of main thread time. T532 took 22.3s.

Without fixes: CvPlotGroup::recalculatePlots took 50% of main thread time. T532 took 26.1s.

With the new plot group system: T532 took 14.6s.

With clang-cl and the new plot group system: 8.4s.

Game progress:

705 cities (25 barbarian)
17324/50633 plots owned on biggest land area (34%)

The difference in time with the original plot group system, with and without fixes is odd. I would have expected a reduction as fixes adds more plot group updates. Maybe AI did something different, but checksums at the end match.

Well, the new system obviously improves things. Turn times... I wish they were better. You can see the effect of clang-cl in profiling though. With MSVC, 64% of main thread time is pathing. With clang-cl, it's 31%. Clang is pretty good. Makes my plot groups system look worse. CvPlayer::updatePlotGroups takes 11.6% of main thread time now. All those whole-map invalidations. Almost all time in there is actually spent just updating plot properties, and it's multi-threaded. So what else do you do... It seems though that my fixes are causing CvPlayer::acquireCity to invalidate the whole map more than once. I'll have to see if that's necessary.

And after the above testing, I found another vanilla bug! CvRandomEventInterface.applyInfluenza2 does a non-deterministic sort, so it selected different cities on different runs. So that's now been patched. And once again, the Huge/Normal map produces consistent results.

I have also fixed a bunch of fast pathfinder bugs and another plot group bug in my code. With optimisations, the huge map runs at about 0.9s per turn on average with clang-cl.

And here's a map dump of a different run to T535 of the Huge 5x save:

Blue plots are roads.

718 cities (21 barbarian)
18438/50633 plots owned on biggest land area (36%)

 

[snowern]

My immediate problem though is that .nif files can be hugely complex inside and deciphering all of that would take ages for me alone. There is indeed a lot of spread out information about .nif files out there but I couldn't find an easily digestible source. The best I have is the niftools-project. (https://www.niftools.org/) but that's where my lack in software developing experience makes things difficult. They have different libraries full of functions that deal with .nif files for every major game that uses them in all their different versions (https://github.com/niftools/nifxml/blob/master/nif.xml - line 172) but the documentation assumes you already know a considerable amount about the topic.

The header starts at <struct name="Header" module="NiMain"> in the XML, I think. The header contains the class types, and then you start deserialising them after the header. And then once you've deserialised, you then link up the pointers. Lookup <basic name="Ptr" and <basic name="Ref". If in doubt, use nifskope to check what fields a class has. The "footer" of the file contains a list of roots, normally one.

And I'd just do it myself, unless a NIF lib will do all the graphics for you too. You can have fun with this in some console C++ project.

*What would be complicated though is animations.