Code organization to manage large number of units

The 4 last contests (MM, BotG, CR, CoK) are different from those in the past in a way that there can be many units to manage, sometimes of different type. I am having hard-time figuring out how to manage them well, especially how to organize my code so that it remains readable easily, but also so that I can keep the the “history” of these units, which can be useful to take heuristic decisions. For example, knowing the previous position of an entity (in order not to go back there for example), knowing if it has already struck me and now I am immune (e.g. YELL in CoK), knowing the past trajectory, etc. Sometimes these inputs are not given (normal, it would be too long), and it is necessary to keep track of what happened and not regenerate units/entities at each turn.

For example, in python (sorry it is the only language I know for now), here is a template of what I used to do:

# game loop
while True:
    entities = []  # creating a new empty list
    for i in range(number_units):
        id,x,y,team,... = input()
        entities.append(Entity(id,x,y,team,....)  # instantiating an entity class and appending it to the list
    # sorting units, by type, owner, distance to something...
    my_entities = [e for e in entities if e.team==my_team]
    enemy_entities = [e for e in entities if e.team==enemy_team]
    ... # heuristics and decisions

Unfortunately, as you can see, I re-create every units at each turn. It works and is readable, which is good for a start. However, I am afraid this is not very efficient and it does not allow to keep track of the history, as lists are emptied at the beginning of each turn. This also makes simulation impossible (or at least very difficult as far as I understand).

An improved version, but far from being perfect, would be:

entities = {}  # dictionary this time, with unique_id:class_instance
#game loop
while True:
    for i in range(number_units):
    id,x,y,team,... = input()
    if id in entities.keys():
        entities[id].update(x,y,team,...)  # assuming the class Entity has a method update
    else:
        entities[id] = Entity(id,x,y,team,....)  # instantiating an entity class and keeping track in the dict

    for e in entities.keys():  # find the dead at previous iteration and delete them
        if e.was_not_updated_at_this_iteration:
            del(entities[e])
    # sorting units, by type, owner, distance to something...
    my_entities = [e for e in entities.values() if e.team==my_team]
    enemy_entities = [e for e in entities.values() if e.team==enemy_team]
    ... # heuristics and decisions

When there are not many units (CSB, GoD, CotC, …), it is easy to update the entity correctly and keep clean code. But when there are many, I was not able to think of a better way than storing them in a dictionary with unique_id as the key and the instance as the value. This is probably not optimal either, as for example I have to go through all the dictionary several times in order to remove the dead, sort the new ones, etc.

I would be really interested in knowing other techniques, or how you cope with this difficulty, as I am really often pulling my hair to keep clean code in this kind of situation. Hope this was clear, please do not hesitate to change the category of the post. Thanks a lot.

2 Likes

Hum, I’m coding in C++ and this was a problem in my first contests. Now what I do is kind of dirty but it works.

Since memory is usually not a problem here, I have a base class “Entity” in which I have everything common and a magic bool “Initialized”, then all other entity classes derived from it. Then I usually have a “dummy” class that is derived from my Entity class and have some dummy member variables including my player character class (like the explorers in CoK) that is usually my biggest class. Then I make a gigantic C array of that dummy class.

Once I get an entity, I just us my id as an index to my gigantic C array and cast it as a Entity, if my little magic bool “initialized” is false, I call a placement new on my data based on my type, since my dummy class has dummy members in it, I’m assured that I have enough memory and not corrupting the next index.

I totally waste memory by doing it like that, but I can always use my Id as an index, no matter the type and I can keep data from turn to turn.

1 Like

I usually have an entity class for all types of units. I branch the base class into different types only some times, but only if it really feels necessary.
The entity class contains a init and an update function.

I only pre-initialize player controlled entities with default values. For these i might activate some extra features early on, such as wasYelledAt list - containing explorers that yelled at this explorer.

  • I also keep these in a different list and update them on their own during new turn input

The regular entity lists get emptied and recreated every turn. In regards to wanderers / oil trucks / lane units / / knights the past doesn’t matter that much.

But i don’t see any issue with having a long list with all the unit ids created. Didn’t have trouble with this thus far.

1 Like

In general I think you are describing a need for the Flyweight pattern ( https://en.wikipedia.org/wiki/Flyweight_pattern ).
But unless you’re going for some computation heavy algorithm like simulation I would rather focus on KISS. If you are unsure about your efficiency - measure! Either use timeit in your unit tests or line profiler. But don’t spend time on optimizing your code until it works within the time boundaries. Your time is better spent on improving the algorithm - it doesn’t help to drive faster in the wrong direction :wink:

In last two games (CR, CoK) I created in Python3 each turn an object Situation in which I kept all the entities and computation artifacts, e.g. closestEnemy, basically all the turn-specific context. Then I passed this object to my current Strategy object. This split was nice because I had all the situation assessment logic and helper variables in this Situation object and all the decision making logic in Strategy classes. You could also store Situation objects from previous turns or from different simulation branches. Such split facilitates unit testing as you can inject desired situation or modify it on the fly.

In Code Royale I would use different Strategy classes ( https://en.wikipedia.org/wiki/Strategy_pattern ) depending on initial queen health and different for end game.

4 Likes

Whoever wants to write longer about that (and potentially take an existing multi as an example) is more than welcomed.
I’ve been wanting to write an article and publish it in the blog for a while but

  1. I don’t find the time
  2. I think I can improve my approach and create a default skeleton which can work for most multis
1 Like

Thank you all for your quick answers. Very interesting to see that there are different strategies (big table, update only most interesting units, separation of the Situation/Strategy classes…), which also means that the subject is probably not so simple. I’ll try some of these solutions asap, and look forward the specific blog article of course :slight_smile: .

2 Likes

There’s multiple solutions and it depends of the used language.

For instance i can show a bit of my own code for Code of Kutulu. This is how i store entities:

Explorer explorers[4];
int explorersFE = 0;

Wanderer wanderers[100]; // 100 is clearly too much. Don't do that at home
int wanderersFE = 0;

Slasher slashers[4];
int slashersFE = 0;

And this is how i read inputs of CoK:

explorersFE = 0;
wanderersFE = 0;
slashersFE = 0;
for (int i = 0; i < entityCount; i++) {
    string entityType;
    int id;
    int x;
    int y;
    int param0;
    int param1;
    int param2;
    cin >> entityType >> id >> x >> y >> param0 >> param1 >> param2; cin.ignore();

    if (entityType == "EXPLORER") {
        explorers[explorersFE++].update(id, x, y, param0, param1, param2);
    } else if (entityType == "WANDERER") {
        wanderers[wanderersFE++].update(id, x, y, param0, param1, param2);
    } else if (entityType == "SLASHER") {
        slashers[slashersFE++].update(id, x, y, param0, param1, param2);
    } else {
        // Read the other stuff
    }
}
1 Like

Thanks Magus. Sorry, a few more noob questions:

  • Do you update the id at each turn? this means from one turn to another, a unit can be replaced by another, right?
  • what is the meaning of FE? I saw it also in some code shared yesterday in general_fr and was wondering.
  • when an explorer dies, do you reduce the size of your table to 3 instead of 4?

Yes. But for CoK i don’t need any historic on the units so it’s ok.

FE = FirstEmpty. It’s the first free index in the array. It’s because we don’t have O3 so i try to not use vectors.

But now i have a specific class for that and it’s far better:

template <typename T, int S>
class Array {
public:
    T data[S];
    int fe = 0;

    inline T& inc() {
        return data[fe++];
    }

    inline void reset() {
        fe = 0;
    }

    inline T& first() {
        return data[0];
    }

    inline T& last() {
        return data[fe - 1];
    }

    inline T* begin() {
        return &data[0];
    }

    inline T* end() {
        return &data[fe];
    }
};

You can use it like this:

Array<Unit, 100> units;
units.inc().id = 2;
units.inc().id = 3;

for (Unit& unit: units) { // It will only loop over indexes [0, fe[
    cerr << unit.id << endl;
}

units.reset(); // Now fe is 0

If an explorer dies in my simulation, i just a boolean dead = true. Don’t know if it’s the better way because everytime i loop over explorers (or wanderers) i must check if the unit is alive. But i can’t find any faster way for the moment.

When an explorer is dead in the game, you only receive 3 explorers in the inputs. So explorersFE will be 3.

2 Likes

Copain !

 template<class T, size_t N> struct Array {
     int FE{ 0 };
     T a[N]{};
     T& operator[](int i) { return a[i]; }
     const T& operator[](int i) const { return a[i]; }
     void pb(const T& val) { assert(FE < N); a[FE++] = val; }
     auto begin() { return a; }
     auto end() { return a + FE; }
     const auto begin() const { return a; }
     const auto end() const { return a + FE; }
     template<class U> void remove_if(U u) { FE = std::remove_if(a, a + FE, u) - a; }
     void reset() { FE = 0; }
 };
1 Like

Oh you implented more methods than me, thanks you. Copy/pasted :smiley:

I’m using C/C++ and for larger amount of units I usually keep a large array (base) of class/struct type which is updated during the initial phase, and then I create arrays of pointers to members of the base array. This way I have quick access to groups and UOI’s (unit of interest).

1 Like