Smarter Serves

[harold]

I'm sure you've all noticed serves doing something that you thought wasn't very smart. This project, if it can be called that, is to find good ways to address that.
Several ways, because there are different strategies, and different trade-offs to be made.
Main goals:
- find objective functions.
- find efficient ways to optimize them, either heuristically or, (not likely under the time-constraints), optimally.
- compare heuristic ways with optimal solutions (use external MIP solvers?) to determine their effectiveness.
- find anything else that might help
- discuss everything
- test many things to find out how well they work in practice in different situations

I'll be working (and have worked some already) on those things whenever I feel like it, input/help will be very much appreciated.

Situations to consider:

• too few serves
  high warehouse congestion
  disjoint villages
  under attack
  tasks so long the serve will starve

Proposed objective functions to evaluate&compare:

• 1) total walking distance to complete all outstanding tasks
  2) weighted version of (1) taking into account a notion of "importance" of a task
  3) total walking distance to complete tasks and the tasks known for certain to exist in the near future, also weighted
  4) total estimated time all buildings spend "waiting" either for a required resource or for space in their output buffer, also weighted
  5) a combination of (4) and (2), with (2) serving to assign tasks to serves that don't really need to do anything according to (4)
  6) a combination of (4) and (3)
  7) total wares delivered (weighted?) combined with serve idle-time

Weights, when applicable, would be something like a base-value of an item (eg iron more expensive than wood), optionally combined when a "destination importance" when applicable (eg putting a bread in your inn is more important than putting a bread in your storehouse).

"Waiting time" doesn't make sense for some buildings. Barracks, townhall and towers should just be stocked as much as possible. Schools should have at least 1 gold (normal rules can apply to the other golds). It might apply to inns, but modified: "waiting" would be "if there is not enough food for everyone in the inn to eat fully" I guess? Or it could just be stocked as much as possible.

Misc ideas that can be applied to just about any serve scheduling scheme:
Plan multiple tasks ahead, but only set the first one in stone (unless cancelled). The situation could have changed by the time it is completed.
Consider non-idle serves to be "idle at the end-position and estimated moment of arrival at the endpoint of the current task".
If the pseudo-task "go to inn" can not be scheduled at the end of a task x such that the serve s will reach the inn without starving, do not assign task x to serve s.

Misc note:
It may look like a Job Shop Problem, but it isn't. Machines (serves) have a notion of "location" that is affected by their last task, and Job Shop does not take that into account.
It looks even more like VRP, but it's not any known variation of VRP as far as I know. There is no real depot, tasks can begin anywhere. Tasks may require the vehicle (serve) to first go somewhere (or several alternatives) else. There are no limitations on how often a vehicle can be at one specific building withing a schedule.

So, let's discuss: is predicting future tasks too smart? It will mean that serves will start walking towards a building that isn't done producing an item yet, and he will arrive just in time. A bit magical.

[Krom]

In my understanding you need to rig a test simulation and be able to choose between algorithms and settings and see how they compare. One of such example can be found in Remake, I have made a test tool to simulate games logic at full speed, this was useful to compare fight outcomes and AI town building, e.g. I could test which settings allowed AI to train more warriors in under 60min. You can do the same thing - make a simulation (TKE has no townbuilding afaik?) based on a typical savegame (Cursed Ravie, 8 players, 75min) when the towns are at their fullest and simulate game for like 60min (at x100 speed) and see how many wares were delivered and serfs were idle - that is an indicator of delivery system effectiveness.

IMHO some smart behavior is okay, pretend that Baker announced that he will make those Breads in 40sec, so serfs CAN walk to Bakery in advance

[harold]

In my understanding you need to rig a test simulation and be able to choose between algorithms and settings and see how they compare. One of such example can be found in Remake, I have made a test tool to simulate games logic at full speed, this was useful to compare fight outcomes and AI town building, e.g. I could test which settings allowed AI to train more warriors in under 60min. You can do the same thing - make a simulation (TKE has no townbuilding afaik?) based on a typical savegame (Cursed Ravie, 8 players, 75min) when the towns are at their fullest and simulate game for like 60min (at x100 speed)

Yep, that's the plan, an objective test to see how to works. It could be done in (the old) TKE too - it doesn't really have building (it has parts of it, but it's not really enabled) but it does have mission loading, and that should do. There's just the problem that the serves are broken somehow, they get tasks but don't really carry them out. Reason unknown. I'd have to debug JBSnorro's code.. probably doable, but a little annoying since I don't know much about the structure.

and see how many wares were delivered and serfs were idle - that is an indicator of delivery system effectiveness.

Sounds interesting, a bit similar perhaps to objective function (5)? Minimizing wait time is good for "total wares delivered", but might be slightly different - minimizing wait time is directly good for "total wares produced", which might mean they're undelivered. Probably a tiny difference only. I'll add it to the list though, it's different and interesting.

IMHO some smart behavior is okay, pretend that Baker announced that he will make those Breads in 40sec, so serfs CAN walk to Bakery in advance

Ok, thank you for your opinion

[Krom]

We had similar problems with savegames. That was caused by not saving/loading ALL fields. One missing field means that whole game state is not identical to what it was and may be corrupt.