How Civ V will handle workers ?

[gruther4]

I think this would be a really tough problem, harder than for example the well-known travelling salesman problem. A merger of locally optimal solutions for clusters of cities would usually not give an optimal solution for all cities. Each tile with a road on it can be thought as a separate node. Certainly good approximations exist with reasonable run times. Do you have a special interest for the topic?

I also suspect it is a difficult problem! The fact that each road is a node is definitely part of the solution. The hex distances also complicate it, and the fact that the city square itself doesn't really count towards the cost (ie, two adjacent cities have 0 cost, but 1 distance).

My interest is idle speculation, mainly. I learned these topics in university and it is fun to use them when I can. I doubt such an algorithm will be implemented, as the REAL tricky part is planning future city locations. I really doubt the AI would rip up old roads to re-optimize its network for each new city.

Why sure, I have this P=NP solution to the travelling salesman problem on my desk in front of me, would you like me to PM it to you?

Nobody said it had to be polynominal time! haha, but I suppose finding a exponential time solution is trivial... just test every possible combination of roads vs no roads for every single tile. So yeah, polynominal, I suppose..

This isn't exactly traveling salesman, though, and it is possible that it doesn't fall into the NP class (as traveling salesman does). In traveling salesman, you can only visit each city once. This is more like a graph connectivity problem, which I don't remember being NP (although it has been a very long time since I learned those concepts, so I might be wrong).

 

[ShaqFu]

High-level math aside, I'm sure it's orders of magnitude easier to find the shortest path between one point and another than finding the shortest total path along dozens of points.

That, or the AI in Civ5 is a bit more advanced than they're letting on.

 

[Brawndo]

Since roads cost money to maintain, I don't really see the point of legions of workers spamming road on every hex

 

[Ogrelord]

In today's broadcast, they mentioned that they had 1 guy in the team that just work on optimizing automated units for the entire project.

 

[SeismoGraf]

Anyway, civ has discrete distance and if you only have ~10 cities spread out over a 20x20 area a brute force solution won't take long. Not to mention that you'd have to restrict it massively because of the sea and choke points and mountains and all of that.

How would you do it? Take the most naive brute force method that ends up checking all possible ways to put an arbitrary number of roads on the 20x20 area. The number of combinations to put e.g. exactly 100 roads on 400 tiles, if I remember right, equals 400! / (100! * 300!) =~ 2.24*10^96. A more selective algorithm may find the solution quickly - but how to prove, that it is actually the optimum?

To make the whole thing more playful: connect all the cities with a minimum number of roads!

The winner will get exclusive ownership of the sole and only teapot orbiting Saturn.

 

[gunter]

I also suspect it is a difficult problem! The fact that each road is a node is definitely part of the solution. The hex distances also complicate it, and the fact that the city square itself doesn't really count towards the cost (ie, two adjacent cities have 0 cost, but 1 distance).

My interest is idle speculation, mainly. I learned these topics in university and it is fun to use them when I can. I doubt such an algorithm will be implemented, as the REAL tricky part is planning future city locations. I really doubt the AI would rip up old roads to re-optimize its network for each new city.



Nobody said it had to be polynominal time! haha, but I suppose finding a exponential time solution is trivial... just test every possible combination of roads vs no roads for every single tile. So yeah, polynominal, I suppose..

This isn't exactly traveling salesman, though, and it is possible that it doesn't fall into the NP class (as traveling salesman does). In traveling salesman, you can only visit each city once. This is more like a graph connectivity problem, which I don't remember being NP (although it has been a very long time since I learned those concepts, so I might be wrong).

Your nickname is way too similar to mine to be tolerated !

Therfore I urge you to pay 2000 gold in order to obtain from me a non agression pact which will last for the next 20 years.

Otherwise I am obliged to move my nuclear submarines close to your shores in order to kill your capitol city pathetic inhabitants.

What do you choose ?

 

[Ahriman]

To make the whole thing more playful: connect all the cities with a minimum number of roads!

27 roads, I think. Lots of different ways you can accomplish that.
Not bad, 2.25 roads per city.

Spoiler :

 

[Ihmemies]

I'd do something like this if I didn't give it much thought, 29 roads:

Spoiler :

Edit: and I lost already

 

[briley]

26 was the best I could do

Spoiler :

 

[Ahriman]

26 was the best I could do

Good call! I should have seen that. Feeling foolish now...

And welcome to CFC!

 

[iop]

How would you do it?

Depends a lot on the order in which the cities are founded. Basically, when I found my second city, I connect it via shortest path to the first city, possibly taking into account the next city I'll be placing, then I connect the third city by shortest path to the existing network etc.

In other words, the problem is A LOT simpler in real life than what you're proposing.

 

[Greizer85]

Depends a lot on the order in which the cities are founded. Basically, when I found my second city, I connect it via shortest path to the first city, possibly taking into account the next city I'll be placing, then I connect the third city by shortest path to the existing network etc.

In other words, the problem is A LOT simpler in real life than what you're proposing.

If you have idle workers in the late game though, you could raze your sub-optimal road network and replace it with an optimal one (once you know that you won't add extra cities on your continent anymore). Sure, it will be pennies compared to your total costs by then - but imo the word 'optimal' is among the most beautiful in the English language. And I like $crooge McDuck comics.

Money-making cities on the coasts could be left unconnected in order to cut costs, since they have little production for building units but will all have harbors. You'll have to watch for enemy navies though...

 

[Tibblers]

There's also something to be said for a few redundant pathways in case someone gets raze-happy!

 

[The_J]

Depends a lot on the order in which the cities are founded. Basically, when I found my second city, I connect it via shortest path to the first city, possibly taking into account the next city I'll be placing, then I connect the third city by shortest path to the existing network etc.

In other words, the problem is A LOT simpler in real life than what you're proposing.

That will not always work.

e.g. imagine you have a circle of mountains.
You have your 1. city in the west. Then you bild your second city in the east. 50% decission, you build your streets via the north route (which has the same length of the south route).
Then you found your third city. In the south. *boom*, optimization is gone.

 

[gibson1314]

The last but not the last I have always wished an option to poison and/or gas them all via a kind of virus weapon. Could you please confirm me that no such option will be available ?

I think someone has been waiting to long to play Civ 5!

 

[Schuesseled]

Spoiler :

27 hexes not bad.

Someone make another blank map, this time throw in some mountains and and lakes to avoid.

 

[SeismoGraf]

Due to overwhelming popular demand... one more puzzle to kill time with

Spoiler :

Connect all the cities with a minimum number of raods!

 

[gunter]

I think someone has been waiting to long to play Civ 5!

Enemy workers have always been my favorite raid targets in previous civ series.

That's a pity indeed that even in Civ V they can't be neither gassed nor poisoned.......and in addition they can't be burned with flamethrowers too !

I still have to get pleased bombing them or hit them with cannon balls or hit them with machine gun bullets only.

Anyway that's routine for me so no new way of killing them......pity indeed

 

[Schimmi]

In the Japan video Greg builds his roads to the front outside of his territory. I suppose you can avoid maintance cost that way.

 

[stealth_nsk]

In the Japan video Greg builds his roads to the front outside of his territory. I suppose you can avoid maintance cost that way.

It was said in the same video what the person who build the road pays for it.