City and unit objects

[Baldyr]

I was reading up on data structures in my trusty textbook on computer science, and come to think about how CivIV organizes cites and units, among other things. Are these objects ordered in a linked list, perhaps?

Because they retain their IDs even when entries (cities/units) are popped out (set to Nill/None). And then the game will backfill those empty slots with other instances of these classes later.

Also, obviously you iterate through the list of cities with the CyPlayer.firstCity() and CyPlayer.nextCity() methods. This would indicate a linked list to me, but what do I know?

 

[The_J]

Are these objects ordered in a linked list, perhaps?

Seems so .

And then the game will backfill those empty slots with other instances of these classes later.

Why do you assume this? Did you prove it?
Because i don't think, that there's later on a substitution, does not make sense at all.

 

[Baldyr]

Well, this is my experience. But I've been dead wrong on previous occasions...

Its how I probably would have designed it, anyway.

 

[davidlallen]

To learn programming, the civ data structures in the sdk contain a lot of good examples. However, in order to understand the way things like the unit iterators are built, you need to know a little bit about "freelist management", which is probably not a good introductory topic. They are stored in an array, which may have holes, which can be dynamically extended when needed.

 

[EmperorFool]

As davidallen said, they are stored in arrays (also called a vector in C++ to distinguish from a built-in array). Arrays operate like linked lists without being linked. Instead of having each element point to the next element in the list, they are all stored in a contiguous block of memory.

So that each item maintains its index (ID) once created, the array is allowed to have holes which are tracked, oddly enough, using a type of linked list. The list itself keeps the index of the first hole, and each hole keeps the index of the next hole. I might be wrong on this part; it's been a couple years since I looked at that code.

The first() and next() functions form a common pattern in programming called iteration which is just a fancy term for looping over all items in a collection in their "natural" order.

 

[Baldyr]

Ok, really interesting stuff, all of it. I read that anything that can be done in another programming language can also be done in Python - only less expediently.

So lets propose that we wanna create a new class of objects in CivIV, like mini cities that have no population value and only produce commerce. But we wanna do them in Python (for no real reason at all - this is just hypothetical). But we also want PyColony to have a similar API than the Cy classes inherited from Boost Python (or whatever).

How could we setup the PyColony class - with Python - so that they form an array/vector like CyCity and CyUnit? So the instances would have a reference to the next object in order, and they would have a ID field? Is there anything else to it, really? How would our firstColony() method know where to find PyColony.ID == 0? And what class would the method belong to? (Some PyContext class, probably.) And how do go about traversing the array with nextColony() then? (Or was this covered in the linked-list thing I read...? )

You don't have to actually make the class but an example is often the best way to explain these things...

 

[EmperorFool]

Ok, really interesting stuff, all of it. I read that anything that can be done in another programming language can also be done in Python - only less expediently.

Each language was created to serve some specific purpose that existing languages did not server as well. There are plenty of things that you can do in a couple lines of Python that would take pages of code in other languages and vice versa.

If the PyColony class is going to exist solely in Python and have no counterpart in the SDK, I see no reason to shoe-horn it into the SDK's method of exposure with firstColony() and nextColony(). To what end? Put them all into a list and be done with it. Python has built-in list iteration.

colonies = [PyColony("boston"), PyColony(Virginia"), ...]
for colony in colonies:
    ...

The first() and next() iteration functions were created to allow Python to iterate over the vectors in the SDK without forcing the SDK to create a PyCity wrapper around a CyCity wrapper around the actual CvCity for every city all at once. For one thing, you might only need the first couple cities, for example you're looking for the first city with at least 4 population.

Similarly, the only reason the cities and units need an ID to allow externally referencing them without a pointer.

Also, if you want this to live entirely in Python you need a way to store the data about the colonies, and the only place to do that is script data.

 

[Baldyr]

No, you're missing my point.

I'm not gonna do any PyColony class that mimics C++. I was wondering about how an array would look like in Python. What the data structure would look like, since it wasn't quite a linked-list as I thought it might bee.

So you're basically saying that an array is the equivalent to the list type in Python, then? Maybe the built-in list type is a better way of storing data than the array, so there really would be no reason to even contemplate it?

 

[EmperorFool]

Python's built-in list type is a resizable array very similar to the vector class from C++ (STL):

• Sequential storage.
• Accessible via integer index starting at zero.
• Grows as elements are added.
• Can shrink as elements are removed or leave holes (with value None) as you prefer.
• Provides bidirectional iteration over the elements in index order.

 

[davidlallen]

The main difference between C++ and python is how much they shield you from the details of memory allocation. C++ makes you go through every detail of memory allocation. Python and other scripting languages such as perl or tcl hide a lot of that from you. Both approaches are useful. If you have large, complex data structures, C++ allows you to write subroutines that manage the memory efficiently. If you have simple data structures, a scripting language lets you write a function quickly without worrying too much about allocation.

In Civ, each language is used for the appropriate reason. All the detailed data structures are in C++. Python is allowed to do some operations on these structures, and if you want some simple, temporary structure, you can add it in python. Most people who add any complex structure to civ, do so by adding a new class in C++ and then adding python access functions.

So the question, "How do I mimic the CvCity array type structure in python?" is not necessarily a good goal.

 

[Baldyr]

As I said before; interesting stuff. So thanks for all the good answers.