[Map Script] PerfectWorld.py

Ok, I had to go back to the drawing board for my starting area enhancements, so I made a mini-publish to eliminate the Mac bug and the multi-player bug. Seven05, Sto showed me how to detect a network game, so you shouldn't have to fool with UsePythonRandom anymore.

My starting area finder was interesting. I calculate a list of all the best possible city starts on a continent and made a table of the path distances between them all for easy lookups. This makes it easy to evaluate the value of each starting city when all players are placed. Then, I did an exhaustive search of every possible combination of city plots and starting locations for a fair result. The results are *exactly* fair. The processing time takes, on a small continent with a couple players just a few seconds. On a large 'pangea' type continent with 200 cities and 13 players I estimate the processing time to be about 1,000 years(not an exaggeration). Since people only live to around 80 or 90 years old, you can see that this technique is not entirely feasable.....*cry*

Even if they make some kind of medical breakthrough, by that time you could probably just pick up a copy of Civ 102 and play the world war 7 scenario, which would probably be waaaay better.

I will not give up! I have a cunning plan!

cephalo said:

My starting area finder was interesting. I calculate a list of all the best possible city starts on a continent and made a table of the path distances between them all for easy lookups. This makes it easy to evaluate the value of each starting city when all players are placed. Then, I did an exhaustive search of every possible combination of city plots and starting locations for a fair result. The results are *exactly* fair.

Click to expand...

Yeah, that's an NP complete algorithm. It has nasty scaling. I suggest some shortcuts.

-K

khuxtable said:

Yeah, that's an NP complete algorithm. It has nasty scaling. I suggest some shortcuts.

-K

Click to expand...

Here's a shorthand explanation of the problem.

1's are starting locations, and digits are possible cities on a continent.

111110000000000000000000000000000000000000000

I know the distance between each city, and I can use that to determine which starting location is closest to what cities. I also know the local value of each city, that way I can add the value of each city to the starting location that claims it by virtue of distance. I'm trying to avoid some starting locations being blocked into a bad peninsula like what I had posted earlier.

Any time I move one of those 1's, I have no idea how to predict how the value of the the other 1's will end up. I tried simply improving the 1 that had the worst value, but curing his problem was highly likely to ruin someone else's starting position. Stepping through a subset of the possibilities sometimes worked, but if the algorithm completed in failure I ended up with little better than random starting locations.

So I made this nifty little algorithm that slid the little bits like an abacus to every possible location exactly once. It was fun to watch it spin through the combinations. The problem is that every time you add a digit the time factor goes up about 20%, and each time you add a 1 it almost doubles. So unless you're using tiny maps with 4 players, worst-case behavior is a game breaker.

I didn't get a chance to actually test how often worst-case behavior happens, I would think that the larger the problem the more combinations that satisfy fairness would arise, but I can't count on that. I could set an iteration limit, but if that limit is reached then you've waited 10 minutes for bad starting locations that could have been better placed any old way.

It's a tough problem.

cephalo said:

So I made this nifty little algorithm that slid the little bits like an abacus to every possible location exactly once. It was fun to watch it spin through the combinations. The problem is that every time you add a digit the time factor goes up about 20%, and each time you add a 1 it almost doubles. So unless you're using tiny maps with 4 players, worst-case behavior is a game breaker.

Click to expand...

Do you have any algorithm books? Your problem is roughly equivalent to the "traveling salesman" problem, which is a canonical example of an NP complete problem, that is, one which has no polynomial time solutions, only exponential ones.

You're going to have to settle for less than optimal to get it to finish in quadratic time or better.

I'll check some texts I have lying around the house. I know some of my old books got moldy in a flood a few years back, but I think I have an algorithm book.

-K

khuxtable said:

Do you have any algorithm books? Your problem is roughly equivalent to the "traveling salesman" problem, which is a canonical example of an NP complete problem, that is, one which has no polynomial time solutions, only exponential ones.

You're going to have to settle for less than optimal to get it to finish in quadratic time or better.

I'll check some texts I have lying around the house. I know some of my old books got moldy in a flood a few years back, but I think I have an algorithm book.

-K

Click to expand...

I have another value system I could use that is more easily searchable, but does not eliminate the peninsula problem. I can use that for searching, and then also use the above evaluation method with a loose tolerance as a final check to make sure someone's not getting an extremely bad deal.

I can evaluate each city by getting the value of all other cities diminished by both distance and by the number of players to reflect competition. So the value added to a start location reflects the likelyhood that you will be able to grab that city. It's not as good, because in a way it assumes you will have open borders with all your neighbors and don't mind having a divided empire who's communication can be severed on the whim of other players. However, it is also a trivial search that might help me eliminate alot of legwork and still evaluate things the first way.

I need some searchable evaluation method that is strongly related to claiming by distance.

Some degree of inequality would be ideal, 'perfect fairness' would eliminate a good part of what makes Civ games fun (for me anyway). I think the best solution is to try to eliminate the worse case scenarios and leave everything that is acceptable alone even if it isn't perfect.

A good solution may be to simply re-write the 'bonus' placement around starting cities to ensure that each start has a roughly equal number of food, commerce and production potential. The current solution for starting area bonuses is poor, you either have something very good or very bad, seldom anything in between. Now, if you can already evalute starting plots compared to potential city placement all you really need to do is balance that with resource in the immediate area. A very good starting location (relative to future cities) can have few, if any bonuses in the area. A very bad starting location (relative to future cities) can have better resources. The best resources would be ones that you can access with 'tier 1' techs, so gold, silver, corn, wheat, crabs, clams, fish, etc. Resources that require calendar are nice later but if thats all you get to start with you're off to a rough start.

Starting on a small peninsula, blocked in by a close neighbor is not entirely bad. Even if you only have room for two cities you can do well if your starting city is strong, especially with easy access to copper and/or iron. Starting with nobody close but surrounded by desert and/or tundra (jungle to an extent) is probably worse since you'll have a very hard time fighting your way out of that mess.

So anyway... if your code says a starting plot is ideal, remove some resources. If you code says it's horrible, add (or change existing) some better resources. Rather than trying to make them all ideal just average them out.

I suppose that if I'm confident in my evaluation of map fairness, I don't necessarily have to limit myself to starting locations in juicing up places with bonuses. Of course, such a scheme would have to be optional.

Civ already does that, you just need to overrride it so you can manipulate it better

Seven05 said:

Civ already does that, you just need to overrride it so you can manipulate it better

Click to expand...

Really? I had only noticed what they placed in the immediate starting location areas.

I'm going to take a few days to study the proper ways to add resources. Yeah, I broke features, but I don't have to break bonuses too.

Also, my fairness evaluator relies heavily on getFoundValue. I suppose I should really get familiar with how it works.

It is only in the 'fat cross' of the starting plot, but that's the part that's critical in most games since a strong first city can carry a couple of weak ones into the mid-game. Likewise a weak first city needs a strong second and/or third city for the civ to do well. So by taking what you find to be a good spot and removing bonuses from there while taking a poor spot and adding bonuses should average them all out nicely.

For instance let's say you have three starting plots selected:

1) Small peninsula with room for three or four cities

2) Larger section of a continent with average terrain, room for around six or seven cities.

3) Lots of available land with room for several cities and early access to a second continent.

To even things out all you need to do is make sure the plot 3 doesn't get many (if any) resources, definately none of the good food & commerce ones like crabs, fish or clams (maybe move them away from the coast too). Then, take plot 1 and give it some extra bonuses and make sure its on the coast (of the main water area). Plot 2 can be left alone. Since plot 1 will have access to better resources the city built there will be better than the cities built on plot 2 or plot 3, plot 3 should be the worst of them. Since so much of the game is dependant on early expansion and growth the player at plot 1 should have an equal chance as the players at plots 2 and 3 because of the added resources. After all, a city with clams is basically getting one plot with a town on it without having to wait for the town to grow, a floodplain with a farm on it and a health bonus all wrapped up into one. If it has two or three clams, it's that much better.

The AI_foundValue assigns yield values at the following ratio:

food = 10
production = 40
commerce = 20

Do you guys agree with that ratio in determining value?

Because of some of the things that AI_foundValue does to the values in relation to other starting postions, like multiplying them if they are isolated, etc. I need to make my own value function to keep things consistent for normalization. Do you guys think I should try to evaluate the different yields against one another, or should I equalize them separately?

Separating them can guarantee fairness, but maybe it's more fun to pit one guys high production against another players high commerce and force them to use an appropriate strategy.

That's a tough one... I'd have to play around with different values to see the effects in game. I would also try separating them, although pitting high commerce vs. high production would be fun not all civs are set to properly deal with ever case due to their starting techs and traits. A financial leader, for instance will have higher commerce if they're simply on the coast and a civ without mining as a starting tech will need several turns before they can take advantage of any production bonuses.

FYI: PerfectWorld.py is 100% compatible with BTS 3.13

I didn't expect it not to be but I figured I'd let you know just in case.

Seven05 said:

FYI: PerfectWorld.py is 100% compatible with BTS 3.13

I didn't expect it not to be but I figured I'd let you know just in case.

Click to expand...

There's still that question regarding river rules. Where can you place a levy on other maps? See the above related posts about diagonal river mouths.

I registered just to log on and say that i think your map script is great, and that i play with it all the time.

i do have one question, does it take a while for you guys to generate maps as well? i noticed this one takes longer than other map scripts.

Yeah, it's a bit more complicated than most and doesn't use the standard map generation code. I'm in the process of moving large parts of it into my DLL to speed it up myself but it's not ready yet.

Turambar1337 said:

I registered just to log on and say that i think your map script is great, and that i play with it all the time.

i do have one question, does it take a while for you guys to generate maps as well? i noticed this one takes longer than other map scripts.

Click to expand...

Yeah this thing is a beast, and it's only going to get worse.

I've been working my butt off this weekend, and I've just discovered that the astar pathfinder that civ uses doesn't always find a path like one would expect. When two plots are fairly close to one another, with nothing in between that I can see, sometimes it reports no path. Since my starting plot finder requires to know the path length between possible cities, I'm not sure what to do. I can implement an a-star pathfinder in python, but I sure as heck don't want to.

Here's a head scratcher. I just learned that if CyMap.calculatePathDistance can't find a path between start and destination, you can usually find one from destination to start.

Hopefully that will solve my problem. Do I need to understand why? Naaaah.

Great Script! I really love the continents and mountain ranges shapes, but I have two small complaints:

- Too much forests.
- Because of the forests there is HUGE lack of agricultural bonuses.

Elhoim said:

Great Script! I really love the continents and mountain ranges shapes, but I have two small complaints:

- Too much forests.
- Because of the forests there is HUGE lack of agricultural bonuses.

Click to expand...

Thanks for the compliment. The thing about those forests though, is that they look so darn beautiful. They really did a nice job of making them mesh together in a natural way. It's very nice to have a wilderness feel before an area becomes settled. I confess I didn't really consider the gameplay changes.

I just figured if an area has enough rain to consider placing a jungle, then even in the temperate zone there should be a forest there unless someone chops it down.

I'll see what I can do about those ag. bonuses, I'm reworking my starting plot and normalization code and I may have to do something about bonuses in general. I also would like an option of dividing some resources between the old and new worlds.

cephalo said:

Do I need to understand why? Naaaah.

Click to expand...

Famous last words. It looks like CvPlot::getPathDistance returns the correct value only about 90% of the time. I'm not sure what it's intended use is. It's possible that some of the map data it needs is not initialized during map creation, but when it fails it really messes up my starting plot code. Unfortunately it's hard to research because the Astar code is not part of the DLL. I've implimented Astar a few times so I can do it in python, but it will delay the next publish if it comes to that.

I wonder at what point this script is going to be just too demanding in resources or processing time. I guess I'll just keep going till I hit the wall.