Introduction

This document describes the issues that arise when designing a transport system for Widelands, and discusses how those issues can be handled. Important concepts are named and defined, to provide a useful common language for discussions. Examples are given for how the concepts may be implemented in games. Those examples are marked like this:

Example: This is an example of an example.

The examples are often taken from hypothetical games that are not, have never been and will never be implemented for Widelands, but are useful to illustrate some issue.

There are notes that inform about the actual implementation that currently exists Widelands. Such notes look like this.

Knowledge about Widelands or similar game engines help to understand this document.

This document is still very incomplete. There may be old parts that should be updated. Many issues are not enough described, such as interactions between players.

Goal

The goal is to design a system that performs transportation of objects across the map as good as possible. It is intended to help and serve the player that owns the objects. A fundamental requirement is that the player should not have to, or even be able to, directly control the movement of individual objects. But he sould be able to set general policies. The transport system should be able to handle any combination of different transport models that game designers want in games that they create for Widelands. Examples of such transport models are:

• The roadbased model on land.
• The roadless model on land.
• Ships travelling on oceans between the different ports around it.
• Different kinds of river transports, including floating (also called log-driving, Flößen).
• Roapway (Seilbahn).
• A model with driving men living in huts and having a working radius.

Surely someone wants some transport model that is not in the list.

An important question is how to define what it means that a transport system is good. It can be good in different aspects. Let us first consider the pure game logic aspect. A transport system that is good in this aspect is one that helps the player to achieve well in games by making rational decisions. It can be measured by letting a player (human or computer controlled) use different transport systems in games against other players and observing how the choice of transport system affects the outcome of the games. If a player performs well with a transport system, it means that that transport system is good for that player. If a player performs bad with a transport system, it means that that transport sytem is bad for that player. But it does not necessarly mean that that transport system is generally bad. It could also be caused by the player's inability to operate it. So care must be taken to teach the players to use their transport systems before making such measurements. In practice, such measurements could be carried out by letting computer controlled players using different transport systems play a lot of games on different randomly generated maps, against each other or against human players on public game servers.

Another aspect of transport systems is usability. It should be easy for the players to configure the transport sytem so that it works well to make it operate well. Providing good default values is an important part of aspect. A good interface (GUI for human players, API for computer players) is another part. A thirs aspect of transport systems is computational efficiency. The transport system should not use more than a fair share of the computational resources on the kind computer that users buy nowadays to play games. There should be enough resources left for game logic, computer players, graphics and sound.

Concepts

Node

A location on the map. Each node has a height. Each node has 6 neighbouring nodes and 6 neighbouring triangles.

Triangle

An area on the map, located between 3 nodes, where the 2 nodes of every pair that can be chosen among those 3 nodes are neighbours. The triangle is the basic area unit of the map. Each larger area is a set of triangles. Each triangle has a terrain type. Immovable objects can be on triangles. There are twice as many triangles as nodes on a map.

Widelands does not yet support immovable objects on triangles.

Search

There are different search algorithms that can be used in a transport system for Widelands:

• Uniform-cost search (also known as Dijkstra'salgorithm).

• Enumeration of all possible destinations (or origins if searching backwards), followed by a guided search (A*) for each of them, and then choosing the shortest path that was found. Both algorithms give an optimal result, but they take different time.

Uniform-cost is good when there are many possible destinations (and they are evenly distributed).

Uniform-cost is bad when there are many nodes and few possible destinations. If there is no possible destination, the search will consider every node. This is the worst case.

The location-enumeration with A* approach is bad when there are many possible destinations, because it has to consider every possible destination. But it is possible to reduce the time by not making a search for every considered destination. If a destination is such that no path to (or from, if searching backwards) it can be cheaper than the currently best found path, then that location can be omitted. This omitting of locations needs to use the same heuristic as the A*-algorithm itself uses in each search. Such a heuristic would consider the distance, height difference and the movement cost rules of the game, including movement cost modifiers of terrain (if any). (Of course the heuristic has to be admissible.) Therefore the efficiency of this optimization depends heavily on the movement rules. It works best when movement cost is closely tied to distance, and it does not work at all when there are cases when movement is free (for example the railroads in Freeciv). The efficiency of the optimization also depends on the order in which the locations are considered. They should be sorted according to the heuristic.

The location-enumeration with A* approach is good when there are few possible destinations. It does not have to consider any nodes at all when there is no possible destination. This is the best case.

Note that the uniformed-cost search has its best case when the location-enumeration with A* approach has its worst case, and the other way around. Therefore it is tempting to try to combine them. This can be done by letting them work independently side by side. When one of them finishes, the other is stopped. If they get equal execution time, the worst case of the combined search would be 2 * min(worst_case_1, worst_case_2). If there would have been more than 2 alternatives, the worst case would be N * min(worst_case_1, worst_case_2, ..., worst_case_N). Parallell searches could probably be implemented without threads, although it could be complex, because the 2 parallell tasks are different. An impementation with threads would make it possible to reduce the worst case to ceiling(N / number_of_processors) * min(worst_case_1, worst_case_2, ..., worst_case_N) , which means that the worst case of 2 on a dual processor system would only be min(worst_case_1, worst_case_2).

Another approach is to chose one of the 2 approaches based on the size of the search space and the number of possible destinations.

Note that if it would be acceptable to only use the uniform-cost alternative, there would be one less reason use the economy concept, because the search would not need the list of destinations (which the economy provides). If there is a reachable destination, it will be found. Not needing the economy concept would make the impelementation of the transport system a lot easier, because managing ecomomies is complex, for example the handling of splits and merges.

Widelands uses A* for pathfinding between_flags (Economy::find_route). It uses a specialized queue implementation (FlagQueue), which has the specialized procedure boost. The heuristic is Map::calc_cost_estimate. IS THIS HEURISTIC REALLY ADMISSIBLE? If not, the search may return a suboptimal result.

Widelands uses location-enumeration with A* for finding the nearest supply when a ware is requested. It is implemented in Economy::find_best_supply. The optimization that nodes with higher estimated cost than the lowest cost found so far are dropped is implemented. But the supply locations are not sorted by estimated cost, so the optimization is probably not as efficient as it could be.

Wares and workers

Wares and workers are objects that can be produced, transported, stored and consumed. There are different types of wares and workers.

Example: Log is a type of ware.

Example: Woodcutter is a type of worker.

Wares and workers can be produced by buildings. This can require some inputs in form of wares, workers, map objects, natural resources, experience or time. Those inputs may or may not be consumed (if time is an input, it is of course consumed).

Example: Grain is a type of ware. It is produced by a building of type farm. This requires a worker input of type farmer (not consumed), a map object input of type grown-up grainfield (consumed) and time input when the worker walks to the field, harvests, walks back and rests.

Example: Farmer is a type of worker. It is produced at a building of type warehouse. This requires a ware input of type scythe (consumed) and a worker input of type carrier (consumed).

Example: Iron ore is a type of ware. It is produced at a building of type mine. This requires a ware input of type food (consumed), a worker input of type miner (not consumed), a natural resouce input of type iron (consumed) and time input.

Example: Master-brewer is a type of worker. It is produced at a building of type brewery. This requires a worker input of type brewer (consumed) and experience input (consumed).

In Widelands, carriers are workers. They are produced at a building of type warehouse. This requires no other input than a time of up to 2500 milliseconds. This is a special case, see the comment for the implementation of the procedure void Warehouse::act(Game*, uint).

Wares and workers can be transported through transport zones. For some combinations of ware/worker type and transport zone type, this requires a carrier. For other combinations, no carrier is needed. Certain combinations may be disabled, which means that the transport is not possible, with or without the help of a carrier.

Example: When a ware of type iron ore is transported through a transport zone of type land, a carrier is required.

Example: When ware of type log is transported through a transport zone of type river, no carrier is needed.

Example: When a worker of type baker is transported through a transport zone of type road, no carrier is needed.

Example: When a worker of type blacksmith is transported through a transport zone of type ocean, a carrier is needed.

Example: The transport of workers of type ferry through transport zones of type land, is disabled.

The restriction mentioned above that certain combinations of ware/worker type and transport zone type are disabled could be seen as an incompatibility between cargo type and carrier type. But seeing it that way may make transfer planning unnecessary difficult, because it has the consequence that not all carriers in a transport zone have equal capabilities as far as cargo types are concerned.

There seems to be some differences between wares and workers:

1. Workers can do things on their own. For example the geologist can work without a building. Carriers are also a kind of workers which can do work witout a building. But the geologist's work is associated with a flag and the carrier's work is associated with a road.
2. Workers can gain experience.

Since all of those differences are things that workers have, but wares do not have, it suggests that worker concept is an extension of the ware concept. So a worker is a ware with a little extra functionality.

Provider

A provider is something that provides wares or workers to an economy. It usually causes the existence of supply points in that economy.

Example: The set of provider types for the ware type meat consists of hunter and pig farm.

On-demand production

Sometimes there is reason to use on-demand production. This is how it works: when a provider has all the prerequisites for producing a particular type of wareware, it registers an on-demand capability for that ware type. The economy can then order the production when there is a demand.

Recipient

A recipient is something that receives (and uses) a particular kind of wares or workers. Recipients usually have some kind of storage capacity for the wares/workerss that they receive. Receiving is preceeded by requesting.

Example: The set of recipient types for the ware type grain consists of bakery, pig farm, donkey breeder and brewery.

Request

A request is an abstract object that represents a recipient's demand for a ware/worker. It is the recipient that can make requests for its needs or cancel requests. Recipients should tell the economy at what time the ware should be delivered so that the economy has a better chance to prioritize among requests from different recipients. The better the recipient is at estimating when it needs wares, the better the economy can prioritize, the more efficient the economy as a whole works, which benefits the player.

When the recipient requests the ware from the economy, it immediately answers in 1 of 2 ways:

1. A transfer has been arranged and the ware is expected to arrive at timestamp <n>.

   In this case the recipient can make another request for the same ware type.

2. No such ware is available. The request has been noted and a transfer will be arranged when a ware becomes available for the request.

   In this case the recipient is not allowed to make another request for the same ware type (until a transfer has been arranged for the first request).

Example: A tool factory uses 1 ware of type wood and 1 ware of type metal to produce 1 ware of type tool. The internal storage can hold up to 4 wood, 3 metal and 2 tool. A production cycle takes 10 time units. Suppose that a new tool factory begins to operate at time 1000. Then it will first request a wood. Since it has no metal, and does not know when it will get any, set the time for when the wood is needed to infinity. The economy will reply, and so on:	Game time: 1000 Wood: Metal: Tool:
Factory: I want a wood at time <inf>. Economy: Request #01: a wood is estimated to arrive at time 1014.	Game time: 1000 Wood: 01:<inf>:1014 Metal: Tool:
Factory: I want a metal at time 1014. Economy: Request #02: A metal is estimated to arrive at time 1018.	Game time: 1000 Wood: 01:<inf>:1014 Metal: 02:1014:1018 Tool:
Factory: I want order #01 to arrive a time 1018.	Game time: 1000 Wood: 01:1018:1014 Metal: 02:1014:1018 Tool:
Factory: I want a wood at time <inf>. Economy: Request #03: A wood is estimated to arrive at time 1016.	Game time: 1000 Wood: 01:1018:1014 03:<inf>:1016 Metal: 02:1014:1018 Tool:
Factory: I want a metal at time 1028. Economy: Request #04: No metal available.	Game time: 1000 Wood: 01:1018:1014 03:<inf>:1016 Metal: 02:1014:1018 04:1028 Tool:
Factory: I want a wood at time <inf>. Economy: Request #05: A wood is estimated to arrive at time 1018.	Game time: 1000 Wood: 01:1018:1014 03:<inf>:1016 05:<inf>:1018 Metal: 02:1014:1018 04:1028 Tool:
Factory: I want a wood at time <inf>. Economy:Request #06: No wood available.	Game time: 1000 Wood: 01:1018:1014 03:<inf>:1016 05:<inf>:1018 06:<inf> Metal: 02:1014:1018 04:1028 Tool:
Now the factory has made all requests it can, and it expects to begin working on its first tool at time 1018. Suppose that the time advances to 1012 and then the economy gets a metal to transfer to the factory. Then they will have this conversation: Economy: A metal became available for request #4 and is estimated to arrive at time 1041.	Game time: 1012 Wood: 01:1018:1014 03:<inf>:1016 05:<inf>:1018 06:<inf> Metal: 02:1014:1018 04:1028:1041 Tool:
Factory: I want order #03 to arrive at time 1041.	Game time: 1012 Wood: 01:1018:1014 03:1041:1016 05:<inf>:1018 06:<inf> Metal: 02:1014:1018 04:1028:1041 Tool:
Factory: I want a metal at time 1051. Economy: Request #07: No metal available.	Game time: 1012 Wood: 01:1018:1014 03:1041:1016 05:<inf>:1018 06:<inf> Metal: 02:1014:1018 04:1028:1041 07:1051 Tool:
The the conversation has ended for this time. The time advances to 1014 and the first wood arrives (on time). The factory now wants the first metal as soon as possible. Economy: Request #01: delivered. Factory: I want order #02 to arrive at time 0.	Game time: 1014 Wood: 03:1041:1016 05:<inf>:1018 06:<inf> Metal: 02:0:1018 04:1028:1041 07:1051 Tool:
The time advances to 1016 and the metal has been delayed for some reason. So the factory has to replan the prodution schedule. Economy: Request #02: new estimated arrival time is 1023. Factory: I want order #04 to arrive at time 1033.	Game time: 1016 Wood: 03:1041:1016 05:<inf>:1018 06:<inf> Metal: 02:0:1023 04:1033:1041 07:1051 Tool:
The time advances to 1023 and the metal arrives (on time). Economy: Request #02: delivered.	Game time: 1023 Wood: 03:1041:1016 05:<inf>:1018 06:<inf> Metal: 04:1033:1041 07:1051 Tool:
The factory now sees that it has all needed materials. Now it checks if there is a free output storage for the tool and reserves it. Since nothing can fail at this point (except for things like war), the factory can now announce that a tool will be produced. Depending on how intelligent the economy is, it may already use that information. It can then give the factory an estimated pickup time, so that the factory can plan for the usage of the storage space. If not, it replies with infinity. Factory: I consume a wood. Factory: I consume a metal. Factory: A tool will be produced at time 1043.	Game time: 1023 Wood: 03:1041:1016 05:<inf>:1018 06:<inf> Metal: 04:1033:1041 07:1051 Tool: reserved:<inf>

Note the clear separation between the recipient and the economy. The recipient does not bother where the wares are, how they will be transported, or in the case of a delay, the reason for it. The only thing it cares about is when the wares are expected to arrive. And the economy does not care about what the recipient does with the wares, how long it will process them or what internal storage capacities it has. The economy only cares about what time the recipient wants a ware and what time a ware will be created.

Economy

An economy is a set of nodes that are connected in a way such that transfers of wares/workers can be done between them. This means that a network of connected transport zones and exchange points is an economy. When a request for a ware is made, an economy algorithm will look in the economy datastructures for an available ware of the requested type. If such a ware is found, a transfer is arranged. Otherwise the status of the request is set to open. When a ware becomes available, another economy algorithm will look in the economy datastructures for an open request for a ware of that type. If such a request is found, a transfer is arranged. Otherwise the ware will stay available.

The reason to divide a player's land into economies is that it it would be in vain to search for ware supply points or requests in nodes that are not connected to the node where the search begins. And within an economy, every node is connected to every other node, so if there is a matching pair of supply and request, it will be possible to deliver. (Unless of course there is some kind of transport deadlock.)

Note: the following paragraph is newly written and needs to be developed further.

An important limitation of the economy concept as described here is that it is actually per ware type. Suppose that two nodes are connected so that most wares can be transported between them through a network of transport zones and exchange places. But what does it mean if some of the transport zones are of a type that can not transport a particular type of ware? Suppose that a ware of type catapult can not be transported betweent the two nodes. This means that the two nodes are not in the same economy as far as the ware type catapult is concerned. This means that one of the following design choices has to be made:

1. Each ware type must be transportable by each transport zone type. This means that even the biggest ships must be transportable across land, which is not desirable.
2. There are separate economies for each ware type. It may be complicated; the biggest problem may be the size of the map data structure. But already now, every data structure in the economy is already indexed by ware type at the top level, so maybe it is doable. This approach should be investigated further. (The different transport zone types will probably be more or less hardcoded, while the ware types will be completely configurable in the rulesets. So the ware types must specify which transport zone types they can be transported by. Datastructures may look like this: Map->Field->Transport_Zone->Ware-specific_Economy).

Classes of ware types that can move (by themselves or with the help of some persons or draught animals.

Ware class	Can move on	Least passage requirement	Includes for example
walking	land	narrow	persons, pack-animals
cart	land	medium	carts, small sleighs
waggon	land	wide	waggons, big sleighs, catapults
boat	calm waters and rivers	narrow	boats
ferry	calm waters	medium	ferries
floatable	rivers	wide	trunks

Classes of ware types that need some kind of carrier.

Ware class	Least carrier requirement	Includes for example
transportable_tiny	tiny	valuables (gold, gems, weapons, tools)
tranportable_small	small	bulk wares such as beer (in barrels), ore
waggon	land	wide	waggons, big sleighs, catapults
boat	calm waters and rivers	narrow	boats
ferry	calm waters	medium	ferries
floatable	rivers	wide	trunks
transportable_tiny

Supply Point

A supply point for a ware type is an abstract object associated with a node where it is currently possible to pick up a ware of that type. When a ware is assigned to a transfer, it is no longer available. So if it was the last available ware of its type at a supply point, the supply point is removed. When a ware is made available, a supply point for that ware's type is created (unless it already exists) for each node where the ware can be picked up.

Storage Point

A storage point for a ware type is an abstract object associated with node where it is currently possible to drop off a ware of that type to store it. If storage space is filled, so that it is no longer possible to drop off a ware at a storage point, the storage point is removed. If storage space becomes available to store a ware of a certain type, a storage point for that ware type is created (unless it already exists) for each node from which it is possible to drop off a ware to that storage space.

Exchange places and transport zones

A transport zone is a set of neighbouring nodes within which carriers can carry wares/workers. (Here set of neighbouring nodes means that every node in the set must be next to at least 1 other node in the set. This implies that the set can not have exactly 1 node. And since the concept of transport implies that there is a distance to cross, the empty set should also not be considred a transport zone. So at least 2 nodes are required to form a transport zone.) A transport zone has a set of carriers. Each carrier belongs to exactly one transport zone. A transport zone has a set of exchange places, which are connected to the transport zone. (This set may be empty.) An exchange place is a place where transport zones are connected so that they can exchange wares/workers. If a ware/worker that is carried is exchanged at an exchange place, the carrier unloads the ware/worker. Then it continues the transfer through the new transport zone. If it needs a carrier, it must wait until one picks it up. There can be different types of transport zones, that are compatible with differnt types of carriers.

Example: In the roadbased model, a flag is an exchange place. It has a set of roads that are connected to it. Those roads are transport zones of the type road, which are compatible with the carrier type road carrier.

Example: In the roadless model, a contiuous passable land area controlled by a player is a transport zone of type land. It is compatible with the carrier type land carrier.

Example: A port is an exchange place. It is connected the ocean, which is a transport zone of type ocean. The transport zone type ocean is compatible with the carrier type ship. In the roadless model, the port is also connected to a transport zone of type land. In the roadbased model, the port is connected to a transport zone of type road.

There can be different types of exchange places, that enable exchanges between different types of transport zones.

Example: An exchange place of type port enables exchanges between transport zones of types ocean and road.

Example: An exchange place of type airport enables exchanges between transport zones of types air and road.

Example: An exchange place of type floatway station enables exchanges between transport zones of types floatway and land.

The roadbased model

The roadbased model is based on the transport zone type road. Roads are build between landnodes. (A landnode is a node where at least one of the six triangles around the node is land). Each road is connected to least 2 different exchange places.

Widelands implements a roadbased model. One limitation is that there must never be 2 flags that are at adjacent nodes. This implies that each road has at least 2 sections. A second limitation is that each road has exactly 2 endpoints. This implies that a road can not have crossings (forks). (But of course the transport system as a whole can have crossings. They are at the exchange points.) A third limitation is that roads may not overlap except at exchange points. A fourth limitation is that a road can have at most 1 carrier. There is an important special rule that carriers leave the road that they work on and walk into buildings, when the carriers deliver wares to buildings.

The roadless model

In the roadless model, transport on land can be done without roads. A continous passable land area is a transport zone.

The roadbased model compared with the roadless model

A roadbased model can be less computationally demading than a roadless model, because it can be expected that in normal simulations, the network of roads and flags will be smaller and therefore faster to search in than the continous passable land area that it is located on. But the user may find it boring to build the roads manually. This situation might be remedied with a helping feature that automates the road building. It should connect disjunct road networks when possible and improve existing road networks. This feature is necessary anyway for the computer controlled players. But users who do not like the roadbased model should be able to play with roadless models.

But even in the roadless model, roads can have a prominent role, both logcally and visually. Idle diggers (the workers with the showels that prepare constructionsites) could spend their time building roads on the most walked sections. Sections with roads could be faster to move on.

To determine the roadbuilding priority of the sections, they could have counters for how many wares have passed there (maybe even weighted by ware prioritypriority). A decay function should be used to make recently trafficed sections more important than sections that were just trafficed a lot in the past.

Sections that have been walked a lot, but which the diggers did not yet have time to construct road on, could be marked visually as dirt paths, where the vegetation on the ground is worn off by the traffic.

This role of roads in the game would most likely be at least as entertaining as a roadbased model for a significant fraction of the potential userbase.

This kind of roads would cause an interesting behaviour that also exists in reality. Since the pathfinding would give paths that are optimal with roads instead of what would be optimal without roads, old roads are kept in use even if a hypothetical new road along a shorter path would have been more efficient, but that new road never gets a chance to compete, because the carriers use the old road, so the diggers never see the demand for the new road. Note that this is exactly what often happens in the real world. A solution to this (if it is considered a problem) could be to compute the 2 paths (the optimal considering roads and the optimal not considering roads) and mark the sections in the path that the ware would have taken instead of the sections in the actually taken path.

Because of the cost reduction of roads, they help to guide the pathfinding search. And since recipients are probably more likely to be close to than far from roads, this would make the patfhinding more efficient. But this is only a hypothesis that has yet to be tested.

Carrier

An object that can transport wares/workers within a transport zone.

Cost of transportation in pathfinding

When searching for a path for a transfer of a ware in an economy, each piece of road (in the roadbased case) or step between neighbouring nodes (in the roadless case) needs to be associated with a cost. The simplest approach would be to give all roads/steps the same cost. But it would be more realistic to make the cost depend on the height difference. Intution says that uphill would cost more than flat, and downhill would cost less than flat, but too much downhill would be difficult and perhaps cost more than flat. In the roadless case terrain type could affect the cost.

Cost can not be negative because cost is travel time and time can not go backwards.

Storage

A storage is an object that can store wares. It can be implemented in different ways:

1. An area on the map that is allocated for storing wares.
2. A building.
3. A combination of the 2 implementations above, where the player must build something on an area to allocate it for storing wares.

A store has a capacity. It can be infinite or limited.

Example: A storage area has the size of 6 map locations and each map location can store up to 8 wares of the same type. (Mixing wares of different types on a location is not allowed.)

Storage has a boolean setting for accepting each kind of ware. This can be set per storage or per economy (or both).

Example: An economy is configured to store gold and plank but not water.

Production deadlock

A production deadlock can occur if a ware type can only be produced at productionsites of a certain type, and the construction of such a productionsite requires more wares of the type in question than there are available in the economy.

Example: Wares of type trunk can only be produced at productionsites of type woodcutter's hut. The construction of a woodcutter's hut requires 3 trunks. There are less than 3 trunks in the economy. Thus a production deadlock has occured.

A production deadlock for an important ware type can make the game impossible to finish. This is of course very frustrating for the user. When designing games, it is important to avoid such production deadlocks. But there may be games where the handling of production deadlocks is intentionally a part of the challenge. This is the case when a user gets an initial supply of a ware type and can not produce any more of it. The same applies to games with finite resources. Every ware that can only be produced from finite resources is in fact deadlocked. A production deadlock that makes the game impossible to finish is called a fatal production deadlock.

A game designer may include elements intended to break fatal production deadlocks.

Example: There may be a way for players to generate some kind of magic points. Those could be used to cast a spell which will cause a few wares to magically appear. The types of wares that will appear is chosen by the game with a combination of need estimation (based on open requests) and an element of chance. There could also be spells to generate natural resources so that they can be harvested, or there could be spells to remove covers (like glaciers) to uncover natural resources.

Petrinet theory, especially reachability testing may be used to investigate the existence of production deadlocking.

Ware transformation

A ware transformation is a combination of ware consumtion and production of ware(s) of other type(s).

It is important to classify ware types by how they can be transformed. Suppose that we have the ware type stone. It is deadlocked because it is produced from the finite resource rock (I know that this is not a very realistic example). So stone has to be used with care. There are several recipient types for stone, including many types of construction sites. One recipient type is the gravel plant, which crushes stones to gravel. Gravel is sometimes needed, and it is necessary to crush stones to get gravel, but it should not be done more than necessary, because that could cause a fatal production deadlock. Now the question becomes how can this be avoided? The obvious way is to use on-demand production, which in this case would mean that stone is only crushed to gravel when gravel is requested. This works well when the transformation is fast, but what happens if suddenly a large quantity of gravel is needed and the crushing takes a lot of time? The delay could give a disadvantage to the player. It may even be enough to loose the game, if the margins are small. To fix this, a reasonable quantity of gravel could be held in supply. Let us call this quantity the target quantity. There would be a per-economy configuration setting for this; a natural number per ware type. The game designer should provide good default values for this setting. If having such a setting is considered to provide too much control of details, it could be done more implicit. There could just be a setting to not transport the gravel to storage . Then the gravel plant would stop the production when the output pile is full. (Of course there may be other reasons to have such no-store options for ware types, like limited storage capacity and limited transport capacity).

When using configured target quantities, there are 2 types of events where the setting is used:

1. When a ware is consumed in an economy, the remaining quantity of that ware type is compared with the target quantity in that economy. If the remaining quantity is lower than the target quantity and there is a productionsite that is ready to produce a ware of the type in question, that production site gets a notice that it should start production.
2. When a productionsite becomes ready to produce a ware of a certain type, the remaining quantity of that ware type is compared with the target quantity in that economy. If the remaining quantity is lower than the target quantity, the productionsite produces such a ware (and the remaining quantity is updated).

Priority

There are different kinds of priorities:

1. Priority among recipients of a particular ware.

   This priority can be set per provider or per economy. This priority needs to be considered when a ware becomes available, for example produced at a provider.

2. Priority among wares. This needs to be considered when a carrier becomes available.

The observer design pattern

Consider the problem with the idle woodcutter. How is he supposed to know when a tree in his working area becomes ready (fullgrown) for him? He could use timer-events to look at all locations at regular intervals. But this is an ugly solution, both because he will not find out about the tree as soon as it is ready and because he will make searches in vain when there is nothing to find. The elegamt solution to this as well as other problems is the observer design pattern. When the lumberjack becomes idle (because there is no ready tree within his working area), he starts to observe every node in his working area. When a node is changed, he can check if it now contains a fullgrown tree. If so, he stops observing every node and starts working.

In general, every productionsite that uses the commands findobject or findspace should use the observer design pattern. Another use is transport. A transfer could observe the transport zones and exchange places that it has to cross.

The object being watched is called the subject. There are two kinds of notifications that an observer can get:

1. That the subject has changed.
2. That the subject is destructed.

Read about the observer design pattern in a book about data structures and algorithms or on the world wide web.

Events in the economy

This section lists the events that make it neccecary to perform computations and take actions in the economy. Approaches to handle the events are discusssed. It is common that these events trigger some of the other events listed here.

A request is created

Example: The player orders the construction of a sawmill. 4 planks and 2 stones are requested. 3 construction workers are also requested.

Example: The construction of a sawmill is finished. The sawmil is taken into production so the log storage needs to be filled. 8 logs are requested.

Example: A sawmill takes a log from the internal storage to use it. 1 log is requested to compensate the reduction in the storage.

A ware becomes available

Example: A sawmill produces a plank.

When a ware becomes available, it must be decided if and what should be done with it. If there are requests for that ware type in the economy, one of them has to be chosen. There are some simple approaches for this:

1. Assign the ware to the oldest request.
2. Assign the ware to the newest request.
3. Assign the ware to the nearest request.
4. Assign the ware to the request that needs the ware soonest.
5. Assign the ware to the nearest request where the ware can be used immediately when it arrives.
6. Assign the ware to a random request.

Which approach is chosen determines which data structure is used to store requests. But let us first state something obvious; that the top level of the data structure should be an array indexed by ware type.

It could be the case that none of the simple approaches is good enough. Perhaps some recipient types are more important than others.

Example: It might be a good idea to give construction sites that are building woodcutter huts highest priority for trunks, since once they are completed, they will help to provide trunks.

Then priorities could be used. The set of all recipeints of a ware type could be ordered to form a priority array.

But this may not be good enough either. It could cause starvation, which means that a recipient type with low priority will never get any deliveries. To solve this, the player may have to change the priorities often. To avoid that, it may be a good idea to let some recipient types have equal priority, and distribute wares among them according to some other rule.

So the priority array should contain sets of recipient types. All recipient types in the first set in the array have highest priority, and so on.

But how should wares be distributed among the recipient types with the same priority? One of the simple approaches above may be used, or it could be done based on weights. Suppose that weight-based distribution is wanted. Then each recipient type should get a weight. Suppose that we want to store other data than a weight in the priority data structure. Thus we create a record with the weight and the other data. Each recipient type should be associated with such a record. This is easiest done with a map data structure.

Each recipient type that can receive the ware type in question must be in exactly 1 recipient record in the list.

The special recipient type storage must also be in the list. If it is, wares of the type in question will be stored if no recipeint with higher priority than the storage exists. If a recipient type is below the storage in the list, the wares of the type in question will be stored instead of delivered to the recipient with low priority. And the recipient will not get any wares from storage.

There is also a special recipient type called do-not-transport. If there are no requests with higher priority than do-not-transport, the ware will not be transported. Thus recipient types with lower priority than do-not-transport will not get any deliveries. This special recipient type is useful for turning off deliveries to certain recipient types. It is especially useful for turning off deliveries to storage, for example to avoid filling storage or transport capacity with wares of an abundant type.

Both special recipient types, storage and do-not-transport, must be alone in their priority groups.

Example:

(The sourcecode of the image is here.)

An economy's priorities for the ware type trunk. When a trunk becomes available it is handled like this:

1. Give the trunk to a constructionsite building a woodcutter hut that needs the trunk. If this fails,
2. give the trunk to a farm or to a charcoal burner. If there are recipients of both types, choose 1 recipient type according to the weights. If this fails,
3. give the trunk to a wood hardener. If this fails,
4. give the trunk to a shipyard. If this fails,
5. give the trunk to a constructionsite that is building a farm, or to a siege workshop. Do not chose a recipient type according to the weights. Instead treat all recipients of both types equal. If this fails,
6. Leave the ware at the provider's output location and remember it as available. (The ware is not transported to storage because store has lower priority than do-not-transport.

Choosing a recipient type according to weights is equivalent to choosing which partiy should get the next mandate (Abgeordnetensitz) when allocating mandates according to an election result. Here is a document that describes how it is (supposed to be) done in Sweden. (I hope that those who do not understand Swedish can find another document.)

When economies are merged, the settings the new economy will inherit the priority settings from one of the old economies. The question is which of them. This can be chosen as the one

1. with most requests,
2. with most recipients,
3. with most carriers,
4. with most available wares,
5. with most settings changes made or
6. most recently edited

or based on something else.

When an economy is split, all new economies inherit the priority settings from the old economy.

2 economies are merged

When 2 economies are merged, open requests need to be reevaluated to see if they can be fulfilled in the merged economy. Alternatively, available wares need to be reevaluated to see if they are needed in the merged economy. Note that it is not necessary to do this for each request/ware, because if a request for a ware of a particular type remains open, the other requests for wares of that type will also remain open.

An economy is split in 2

When an economy is split in 2, all requests in transfer where the ware is in one of the resulting economies and the recipient is in the other, must be cancelled and recreated.

The ownership of land changes

When ownership of land changes, it is first lost by one player, then gained by another player.

Land is lost

There are several things to consider when the land is lost:

• The player that looses the land may have buildings there. The player tries to destroy them to prevent them from falling into the enemy's hands. It could be decided that certain tribes have the ability to destroy buildings when loosing land, for example tribes that build mostly with wood could be able to do that, while tribes that build mostly with stone could not be able to do that. Such tribes would just stop the building and abandon it. (In any case, requests with such buildings as destination would be cancelled.)The enemy could then use the buildings that are left on the land. In that case the enemy has to provide a new worker and maybe do some quick repairs. Or the building could be disassembled and the materials recycled.
• Transport zones are shrunken, split or removed completely, which may cause economy splits.

Land is gained

There are several things to consider when land is gained (from another player or neutral):

• Transport zones are expanded, merged or created, which may cause economy mergers.
• There may be wares (or buildings) left behind on the land. They become available to the new owner.
• The player that gains the land may have workers that are passive because there were no objects to gather within their range. They may need to be activated. In Widelands, workers do not respect borders, so this case does not apply.