general issue with resource routing to buildings

[tlongstretch]

I saw an issue in one game where an iron mine wasn't being sent food despite having the highest mine-food priority and the nearby stock having tons of stored food. Upon investigation I think I found an issue with the core building resource requesting logic:

• every non-castle/non-warehouse building that can store and request resources has a stock[0] and possibly a stock[1] type.
• these internal stocks always have a maximum storage amount, usually 8 I think
• to avoid requesting more resources than a building can store, it stops requesting resources once requested resources + stored resources = max resources
• once a building requests a resource, if that resource never arrives it forever consumes a "slot" in that building's stock in terms of requesting resources
• there are probably many reasons why a requested resource may not arrive at a building (flag destroyed, serf carrying resource on road when road destroyed, warehouse/stock queue full?, probably others), and I don't think it is reasonable for the game to be able to detect every case where this happens and decrement the requested resource amount of the building
• once requested resources == max resources, the building stops requesting any resources at all for that resource type, meaning for most buildings they would stop working

If I modify this bit of code:

  case TypeIronMine:
    if (holder) {
      int total_food = stock[0].requested + stock[0].available;
      if (total_food < stock[0].maximum) {
        Player *player = game->get_player(get_owner());
        stock[0].prio = player->get_food_ironmine() >> (8 + total_food);
      } else {
        stock[0].prio = 0;
      }
    }
    break;

To this:

      case TypeIronMine:
        if (holder) {
          int total_food = stock[0].requested + stock[0].available;
          // stop requesting if the stock is full
          if (stock[0].available >= stock[0].maximum) {
            stock[0].prio = 0;
          }else{
            Player *player = game->get_player(get_owner());
            // prio shift is never less than 8 + 7
            stock[0].prio = player->get_food_ironmine() >> (8 + total_food -1);
          }
        }
        break;

It will start receiving food again. However, if I am understanding the 'prio' bit-math, it will still be (de)prioritized as if it were nearly full.

Something either needs to track and detect every resource en-route to a building and decrement the requested value if that resource is lost, or buildings need to be always requesting resources and if/when too many arrive they just let them be sent back. Maybe throttle the number of resources destined for each building so it doesn't get too many in-flight resources, or have some check that periodically resets the requested counter to zero?

I see there is a Building::fix_priority function

  for (int j = 0; j < kMaxStock; j++) {
    if (stock[j].type == res) {
      if (fix_priority) {
        int prio = stock[j].prio;
        if ((prio & 1) == 0) prio = 0;
        stock[j].prio = prio >> 1;
      } else {
        stock[j].prio = 0;
      }
      stock[j].requested += 1;
      return true;
    }
  }

that is called when schedule_unknown_dest_cb is used (routing "routable resources" directly from producers to requesting buildings, rather than pulling from a stock) but I am not sure if this is relevant to the issue I'm describing.

I don't know if this is a Freeserf issue, an original SerfCity/Settlers1 issue, or if I'm misunderstanding another issue.

[tlongstretch]

Maybe automatically decrement the requested counter by one every so often? And decrement it by two every time a resource is delivered??

Or, it may be possible to scan every single flag and serf to find resources in transit and update all building requested counts to match those destinations. It seems that the game does try to account for every resource, and if one is lost it calls cancel_transported_resource for dest.

@Vershner mentioned that in the original Settlers1/SerfCity game there is a known bug where building a warehouse can result in resources becoming unroutable from castle/warehouse to buildings, and only directly routable resources can then be moved (i.e. unknown_dest). I wonder if this is all related

Hmm... maybe the issue is that when flags fill all their resource slots, and serfs start moving those resources to the next flag over to clear space... that the requested resources are still technically en-route but so far backlogged as to be worthless?

I am going to try two things...

1. try to search for every resource in transit and try to settle up with the building requested resources and see if I can detect discrepencies
2. In the same game where I see this issue, demolish all resource producing buildings and let all resources be cleared from all flags, and see if the iron mine finally gets the food it requested

It seems reasonable to set some kind of fallback where if a resource was requested long ago and hasn't arrived yet, to assume it will never arrive and request it again. And if it finally arrives later, send it back if there is no room.

I was doing some testing with detecting missing transporters on flags, and realized that the only safe way to do it is to figure out how many tiles away the inventory dispatching the serf is, and adjust the acceptable wait time based on the distance. This approach would also work for requesting resources. If the castle is a hundred tiles away, the building should wait 5x longer before giving up than if the castle were twenty tiles away.

[tlongstretch]

I think the game really did lose track of the requested resources. I don't see a single dest = <flag of iron mine> anywhere in the save game file. And if I demolish all the roads and flags with piled up resources the iron mines still never get any food.

[tlongstretch]

I wrote some code to search all flags and all transporting serfs for food resources with transporting dest of a mine flag, and it rarely equals out. For the "broken" mine no resources are found, as I suspected. For a new mine I can find the resources, but often I see some are unaccounted for, or many more are destined for the mine than the requested count!

Maybe my approach is wrong, but I am thinking some kind of timeout is needed to cancel resource requests that are never fulfilled.

[tlongstretch]

In my fork I have implemented timeouts for resource requests, and transport prioritization of resources that are destined for a non-Inventory. This effectively fixes the issues described above with little change in the way the game plays.

I would prefer to make resource tracking perfect, if possible, so that this is not necessary. But I am not sure if it is possible. Maybe at some future time.

[sternenzaehler]

thank you for such a detailed analysis!
the thing is, the original game works the same - i.e. it counts the requested resource as "already delivered" and if the transport network is congested then it will starve the building for a (very) long time even if a nearby warehouse has plenty of the needed resource. if the transport prio went haywire (for example low priority raw materials on a congested road that delivers lots of high priority coal) it may starve the building forever.
BUT
the original game never goes into a deadlock here, it somehow resolves them, if the resource is lost on the way, it will eventually route a new piece of a resource to the building. (never learnt how they do this though)
actually I think that we need a new system of resource transport to make the game more fun and micromanagable:)
of course not tainting the original gameplay but making this an option. Micromanaging resources and more fine grained control over routing for example (like making routing rules for individual flags) would be fun to my mind and will allow for a nice gameplay on a map of 10.

as to the original bug, why not do a bookkeeping pass once a couple of seconds to see if real resources en route match to ordered resources for each building. Such a pass will not substantially harm performance. or this pass could be ordered only when a resource went missing or was derouted (taken back into a warehouse due to a congestion at the flag - I am not sure if the resource loses its original dest in this case, but I think it does)

There is actually a way of tracking the resources in real time with very little additional performance penalty by ensuring that the game has proper logic for "resource routed" and "resource destroyed or derouted".
I guess that Freeserf has some additional bugs due to which it loses tracking of the resources.
Like the battle bugs described by me, this resource bugs could only be found if you play a real game for some period of time, not a test game, and this is a difficult thing to do without the AI :)
I extensively tested the battles but never encountered this situation with resources in Freeserf (but again, the basic mechanism here is the same as in the original game).

[tlongstretch]

I believe that either one of two approaches will work

1. 100% accurate tracking of all resources, requests, etc. It is definitely possible, but may be hard to implement
2. acceptance of failure & retrying. I think this is a perfectly fine solution, because only in a computer program could you realistically cover all possibilities. It is fine, in my opionion, to say "I have no idea why I didn't get my resource/serf, but I still need one, gimme". In fact, I think this way is potentially more realistic and better, because who cares why your Plank or Food is tied up in some congested flag far far away, you still need more.

My retry logic so far seems to be working fine, because I have forgotten about its existence. Another option to retrying would e for all resource buildings to simply always demand more resources until they are full. Maybe somehow rate-limiting the request rate. This might make more sense if tracking all the resource timeouts becomes a bottleneck.

[p1plp1]

allready known for me, solution is rework of resource requesting-delivering loop:
buffer with delivery requests and counts + cycle them with priority handling, hmm many problems around ...

tlongstretch can u paste here what u did (if u) allready implement or link to filename/rows, ill update my code, ill try to use your solution as start point

[tlongstretch]

@p1plp1, the code to do this is scattered around across various functions, however I believe I've noted them all in the comments. If you check out the feature_addition branch of my code at https://github.com/tlongstretch/freeserf-with-AI-plus/commits/feature_addition and search the actual code for 'resource timeout' you'll see the resource timeout stuff.

the prioritization of non-stockpiled resources is simpler, inside Flag::prioritize_pickup :

void
Flag::prioritize_pickup(Direction dir, Player *player) {
//Log::Info["flag"] << "debug: inside Flag::prioritize_pickup";
int res_next = -1;
int res_prio = -1;

for (int i = 0; i < FLAG_MAX_RES_COUNT; i++) {
if (slot[i].type != Resource::TypeNone) {
/* Use flag_prio to prioritize resource pickup. */
Direction res_dir = slot[i].dir;
Resource::Type res_type = slot[i].type;
if (res_dir == dir && player->get_flag_prio(res_type) > res_prio) {
res_next = i;
res_prio = player->get_flag_prio(res_type);
// de-prioritize any resource that is destined for castle/warehouse reserves
// this should exclude resources that are "activated" by being in castle/warehouse,
// such as gold bars (morale), sword/shield (knights), or tools (professionals)
// priorities are 1-26 for flag_prio and inventory_prio, higher number == higher priority
// slot[x].dest is a Flag index, not a MapPos
// ranges are based on the const int routable[] array in Flag::schedule_slot_to_unknown_dest
// but instead of copying the table just check for FISH<>PLANK, STONE<>GOLDBAR
//
// if this resource has a known dest (flag index)...
if (slot[i].dest != 0){
// ... and is routable (meaning it CAN be delivered directly to a requesting building)...
//if (routable[res_type]){
if ((res_type >= Resource::TypeFish && res_type <= Resource::TypePlank) ||
(res_type >= Resource::TypeStone && res_type <= Resource::TypeGoldBar)){
Flag *dest_flag = game->get_flag(slot[i].dest);
if (dest_flag == nullptr){
Log::Warn["flag"] << "inside Flag::prioritize_pickup, got nullptr for flag";
}else{
// if dest is a castle/warehouse
if (dest_flag->has_inventory() && dest_flag->accepts_serfs()){
// ...this resource is going to pile up in a warehouse, do not adjust its priority
//Log::Info["flag"] << "debug: Player" << player->get_index() << " a resource of type " << NameResource[res_type] << " is destined for castle/warehouse";
}else{
// ...this resource is being sent directly to a requesting building, increase its priority
//Log::Info["flag"] << "debug: Player" << player->get_index() << " a resource of type " << NameResource[res_type] << " with dest pos " << dest_flag->get_position() << " and dest building type " << NameBuilding[dest_flag->get_building()->get_type()] << " is being directly routed, increasing priority";
res_prio += 26;
}
}
}else{
// this resource is not routable, meaning it is "activated" at castle/warehouse
// increase its priority
//Log::Info["flag"] << "debug: Player" << player->get_index() << " a resource of type " << NameResource[res_type] << " is not routable, increasing priority";
res_prio += 26;
}
}
// if this resource does NOT have a known dest, it will be assigned one when
// a serf picks it up from a flag, then then this check can run
}
}
}

other_end_dir[dir] &= 0x78;
if (res_next > -1) other_end_dir[dir] |= BIT(7) | res_next;
}

[tlongstretch]

@sternenzaehler, when I tried adding a function to track the resources en-route to a given building, it showed unpredictable results. I didn't spend a lot of time on it, but it made me think trying to track all resources using the current routing scheme is difficult

[sternenzaehler]

I believe that either one of two approaches will work

1. 100% accurate tracking of all resources, requests, etc.  It is definitely possible, but may be hard to implement

2. acceptance of failure & retrying.   I think this is a perfectly fine solution, because only in a computer program could you realistically cover all possibilities.  It is fine, in my opionion, to say "I have no idea why I didn't get my resource/serf, but I still need one, gimme".   In fact, I think this way is potentially more realistic and better, because who cares why your Plank or Food is tied up in some congested flag far far away, you still need more.

My retry logic so far seems to be working fine, because I have forgotten about its existence. Another option to retrying would e for all resource buildings to simply always demand more resources until they are full. Maybe somehow rate-limiting the request rate. This might make more sense if tracking all the resource timeouts becomes a bottleneck.

Of course both ways would work and your preferred way would work too.
What I was driving at is that not getting a resource because it got stuck on a congested road is a fair penalty according to the original gameplay. and fixing it by requesting more of that resource to enforce delivery from somewhere else for instance, would be a cheat to the gameplay. Or we can say it will be a different kind of gameplay, one where it is not so important to carefully plan roads and resource pathways/transport priorities. The original game requires one to constantly juggle with priorities to get some rare things (like tools) through the road, or temporarily boost the prio for metal, to supply weaponsmiths.

not getting a resource because of a bug is bad and must be fixed. But not getting a resource due to a congestion is part of a gameplay, we just need to be aware that fixing this would constitute a gameplay change.

[sternenzaehler]

@sternenzaehler, when I tried adding a function to track the resources en-route to a given building, it showed unpredictable results. I didn't spend a lot of time on it, but it made me think trying to track all resources using the current routing scheme is difficult

I agree that is not an easy task. But maybe it is easier if we only track the cases where a resource is destroyed - there are only so many such cases (flag deletion by user, flag deletion due to land acquisition by the enemy, flag with resources ceded to enemy, road deleted under the carrying serf (by user or by the enemy), warehouse burnt down with that resource already in the outqueue but not yet out). If all resource destruction is accounted for then a resource wont get lost (provided there are no other bugs).

[tlongstretch]

I believe that the game properly accounts for resources being lost, at least in most cases, and preperly re-sends them. I suspect Freeserf is more buggy than the original game and loses more resources.

And I agree with you that using resource prioritization to manage congestion is a gameplay feature, but in my eyes it seems to result in even more "cheating" in that the player can simply delete flags with resource congestion, and delete buildings that aren't getting built and re-place them.

My intent is to document all of these changes and make them checkbox-optional and not on by default. But when I play, I will be using them :)

[tlongstretch]

This makes me think of another possible "cheating" solution... have a "okay to dispose of these resources" list that Player can adjust much like other Res priorities. So if a Flag's slots are all full, and a Serf would otherwise have to carry those resources to a nearby flag to clear space, if the carried resource (or maybe even one already at the flag) is on the Purgeable list, the least important one will be disposed of.

Some micromanaging is fun, some is annoying... I'm going to try playing around with it and see