Wednesday, July 12, 2006

Settlers II has been remade for its 10th anniversary. I've tried out the demo and it reminded me of all the things I liked about Settlers. The game is somewhat unusual. It's a building+war game, like Age of Empires, Tropico, Command & Conquer, etc., but its emphasis is on building and not on war.

One of the unusual features is the transportation model. In most games of this sort, people walk around wherever they need to go, and you can build roads to speed up their movement. In Settlers, you must build roads, and every road segment has a settler assigned to it. That settler will move goods back and forth along the road. You have to carefully plan your roads to handle the traffic; roads can become bottlenecks. Making road segments long means you use up fewer settlers and allows faster travel; making them short means you get a higher capacity. Roads also become paved and can have donkeys to increase capacity.

The transportation model changes the implementation strategy for the game. Usually you run a pathfinder (like A*) for each of the peasants, and combine that with a movement algorithm to avoid local obstacles. This can get expensive when you have lots of peasants. Each peasant handles a single type of good, usually assigned by you. For example, you might assign a peasant to be a miner; the pathfinder will find a path between the mine and the warehouse. There is no further distribution of goods; it goes into a global store that can be accessed instantaneously from anywhere. In Settlers, the peasants are not using the pathfinder. Instead, the pathfinder is used for materials and goods. They are physical objects that have locations and can move around. They can be put in a warehouse, but they have to be moved to the location where they get used. The peasants and road segments serve as capacity restrictions. If a good needs to move from one place to another and the road it needs to travel on is “full”, it waits for the road segment (and associated peasant) to free up. This works somewhat like a packet-switched computer network.

How do the goods “decide” where to go? A local approach would be to make each good perform pathfinding to its destination. Pathfinding on the road graph will be much faster than pathfinding on a grid, because there are far fewer segments and connection points. But how do they find their destinations? We could either keep a list of points that require certain goods, or we could build an influence map. It's possible with an influence map to not even need pathfinding. I'm not sure what Settlers actually does.

Another difference between Settlers and other building games is that the Settlers economy has much longer chains of production. Forests can be cut to produce wood. Wood are milled into wooden boards. Boards are used to build farms and other buildings. Farmland is used to raise crops, yielding grain. Grain is milled into flour. Wells produce water. Flour plus water is baked into bread. Grain plus water is turned into beer. Fishermen use fishing poles to catch fish. Hunters use spears to catch animals. Animals taken to the slaughterhouse become meat. Meat, fish, and bread are fed to miners. Miners can mine for coal, iron, granite, and gold. Coal and iron can be smelted into steel. Steel is taken to the metalworks to make tools such as spears, and to the armory to make swords and shields. Granite is turned into stone. Stone is used to make new types of buildings. Gold is turned into gold coins. Gold coins, swords, and shields are given to soldiers. Soldiers are needed at watchtowers, which expand your territory. The economy is complex.

Also unlike other building games, you don't control any of your people directly. You can indirectly control them by building things. To go to war, you need soldiers, but you never explicitly recruit or place soldiers; they are produced whenever you have enough of the needed goods (gold, beer, sword, shield). You can influence what gets transported by choosing a transportation priority for each type of good (this is like QoS for TCP/IP), and you can set the priority of having soldiers vs. builders.

At the start of the game, you don't need to worry about the full economy. For example, you can't build tools without steel, which requires coal and iron, which requires miners, which requires bread and meat, which requires grain and water and animals, which requires flour, which requires farms, which requires wooden boards, which requires wood. Instead, your initial warehouse includes many types of goods, from which you can jumpstart your economy. You don't need to make rarely used items like tools until later in the game, when your settlement is large. It's a nice way to gradually introduce complexity to the player.

It would be nice to be able to see general trends, like whether I'm building up more bread than I need, or whether people are perpetually low on water. It's hard to manage everything in your head by checking manually. If I were in charge of a town like that, I'd hire some people to gather information and alert me when something's wrong. Overall though it's a very interesting game, and not like other games I've played, so I think it's worth exploring.

Update: [2006-07-21] Sören M points me to a design document about transportation in Widelands (a game much like Settlers II).



BuschnicK wrote at July 21, 2006 1:02 AM

Hey Amit,

Good of you to (re-)discover Settlers - in my eyes one of the greatest games of all time. The first two versions that is, i.e. the ones that had logistics as their primary game mechanic. The later ones suck.
I always wanted to do a game like the settlers and focus on cooperative multiplaer - though I guess that task is a bit too much for a one man operation like me ;-)

Anyways, check out this document for Widelands, an open source settlers clone. It's a very in depth description of how such a transport system might work.



Xiofen wrote at November 06, 2016 6:06 AM

"We could either keep a list of points that require certain goods, or we could build an influence map. It's possible with an influence map to not even need pathfinding. I'm not sure what Settlers actually does."

Thanks. The Settlers 'pathfinding' method has fascinated me since its release - I not yet found any information on what method they actually did use. Both an influence map or individual object pathfinding would work.

An issue I had with the influence map was that it seemed to need to be rebuilt every time the network changed. (maybe there's a way round..)

I toyed with the idea of the settlers carrying message packets about resource requirements (as settlers are confined to a single road stretch) - so a settler on a stretch connected to a empty road, stonemason, and smith might carry a single message to an node of either "settler needed SW", "stone needed NE" , "hammer needed SE" etc - these messages would be deposited (virtually) at nodes, to be carried onwards to other nodes - this method has many flaws - slow response being one - the settlers would then approximate to next-node querys in a pathfinding algorhtym.. (the game doesn't use this method, as evidenced by the immediate response to new building etc) This method has one side benefit of "self healing" in response to network changes.

Your packet/network analogy was most useful. Thanks again.

Amit wrote at November 07, 2016 3:19 PM

@Xiofen: in one project I found that I was able to incrementally update the influence map over time by using a "decaying" signal. For example suppose we just have the distance from the seed point, so the influence map in one row might be 3 2 1 0 1 2 3. Each step, we set a[i] to 1 + min(a[i-1], a[i+1]). If I instead set a[i] = max(0.9*a[i], 1 + min(a[i-1], a[i+1])) then what happens if one of the neighbors increases? then a[i] will increase right away. What happens if the neighbor decreases? Then a[i] will decrease slowly. Basically, everything is slowly going down unless there's a neighbor that keeps it propped up. This lets me update small portions of the map at a time without having to start over. I don't know if this is useful in all situations though.

The message packet idea is interesting. It seems similar to an influence map in some ways, but on a graph, and weighted by which edges are being used often.