恐龙进化论游戏解说（游戏中的数学与编程之一）
恐龙进化论游戏解说（游戏中的数学与编程之一）下面是具体的程序，是vs 2017 免费社区版的c 代码 ，其中已经采取了一些优化方法，排除了明显不可能产生最大弓手数的动作组合，尽量增加程序在有限时间内可搜索的深度。某个时刻可以采取的动作：建营地，建兵营，训练弓手，这三个动作的某种组合。然后计算采取每一种动作组合之后，经过八个小时以后的游戏状态：金币数，营地数，兵营数，弓手数，在建兵营数。然后循环。当时间到了预定时间，就在所有的状态中找到弓手最多的，就是结果。我们还是先简化一下，各种资源，金币，食物，电力，土地面积，人口，木材，石材等等，简化成一种：金币。各种建筑，营地，伐木场，田地，渔场，电厂，矿场，兵营，简化成营地，兵营两种。各种士兵，弓箭手，枪兵，狙击手，泰坦等等，简化成一种弓箭手。所有的地形，山地，荒漠，水塘，河流，都去掉全部用草地代替，所有僵尸去掉，不要僵尸了。看一下简化后的游戏：初始有100金币和基地200金币每8小时的
介绍一个游戏，叫亿万僵尸。是一个建基地，打僵尸的游戏。开局时4个弓箭手，一个基地，一些木材金币和粮食，基地自带一定电力，和居住空间。地图中有草地，荒漠，山脉，池塘，河流等地形。地图上还有很多僵尸。游戏就是不断的开采资源，建设基地，建造兵营，抵御一波波的僵尸大军进攻。坚持一定的时间就胜利了。
这样一个游戏，你占的地方越大，那么可以采集的资源就越多，就可以建造更多的兵营，能训练更多的士兵；但是占领的地方越大，要防守的地方也越多，同时士兵也需要工资，食物和居住地，很多东西都是相互制约的。
比如：士兵需要工资，单位时间要消耗一定金币和粮食，还要占用一个居住地。训练士兵需要训练营，训练营本身消耗一定木材，金币和电力。它单位时间可以消耗一定的金币可以训练一定的士兵。然后木材需要伐木场，电力需要发电厂，伐木场，电厂都需要消耗金币，木材和工人，工人由需要营地提供居住地，还需要田地提供食物，等等。可见金币，电力，食物，木材，矿石，人口等等都是循环依赖，相互制约的。
所以很难简单地分析，比如按圆形方式扩张，面积的增长肯定是快于周长的增长，也就是占领的资源增长快于需要防守的边疆的长度，于是得出结论地盘越大越好，是不是这样呢？真的不一定，因为各种资源互相制约下，资源的效益并不是等比于面积那么简单的。于是如何安排才能在一定的时间后拥有最大的兵力呢？
我们还是先简化一下，各种资源，金币，食物，电力，土地面积，人口，木材，石材等等，简化成一种：金币。各种建筑，营地，伐木场，田地，渔场，电厂，矿场，兵营，简化成营地，兵营两种。各种士兵，弓箭手，枪兵，狙击手，泰坦等等，简化成一种弓箭手。所有的地形，山地，荒漠，水塘，河流，都去掉全部用草地代替，所有僵尸去掉，不要僵尸了。
看一下简化后的游戏：初始有100金币和基地200金币每8小时的金币产量。30金币可以建立一个营地，营地建造需要8小时，建成后每8小时生产金币8块。450金币可以建立一个兵营，兵营修建要16小时，建成后每8小时可以消耗120块训练一个弓手，兵营本身每8小时消耗金币14块。弓手每8小时消耗1金币的工资。问一定的天数后，比如30天后，最多可以达到多少弓手，要如何安排建造和训练才能达成上述目标。
上面的简化，是不是简化的太过来呢，看似简化的太多了，甚至僵尸都没了。其实它的基本步骤和原来的问题是一样的。就是某个时刻可以采取某些动作，过一段时间整个游戏的状态就变化了，然后下一个时刻又可以采取另一些动作，如此循环。那么如何解决呢？好像没有什么思路，无法列出某种公式进行推导。那么我们就用最笨的方法，暴力搜索。
某个时刻可以采取的动作：建营地，建兵营，训练弓手，这三个动作的某种组合。然后计算采取每一种动作组合之后，经过八个小时以后的游戏状态：金币数，营地数，兵营数，弓手数，在建兵营数。然后循环。当时间到了预定时间，就在所有的状态中找到弓手最多的，就是结果。
下面是具体的程序，是vs 2017 免费社区版的c 代码 ，其中已经采取了一些优化方法，排除了明显不可能产生最大弓手数的动作组合，尽量增加程序在有限时间内可搜索的深度。
// theyAreBillions01.cpp :
#include "pch.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
using std::string;
using std::vector;
struct action {
string name;
int costGold;
int dGold;
int dHour;
int dTant;
int dBuildingBarrack;
int dArcher;
};
struct gameState {
int hour;
int gold;
int dGold;
int tant;
int barrack;
int buildingBarrack;
int archer;
int fromActionArray[3];//三个元素分别代表bTant，bBarrack，bArcher三个动作的个数。
int fromStateIndex;//父节点在vector中的下标序号。
};
int main()
{
gameState iniState = { 0 100 200 0 0 0 0 {0 0 0} -1 };
action bTant = { "bTant" 30 8 8 1 0 0 };
action bBarrack = { "bBarrack" 450 -14 16 0 1 0 };
action bArcher = { "bArcher" 120 -1 8 0 0 1 };
action actionArray[3] = { bTant bBarrack bArcher };
int gameTime = 0;
int workIndex = 0;
int max8hour = 15;//停止标记
int maxArcher = 0;
vector<gameState> states;
states.push_back(iniState);
do{
gameState workState = states[workIndex];
//先找出可能的行动组合
//先找出每个动作最大次数
int maxAction[3] = { 0 0 0 };
for (int i = 0; i < 3; i ) {
maxAction[i] = workState.gold / actionArray[i].costGold;
//archer可训练数还和军营数有关
if (i == 2) {
if (maxAction[i] > workState.barrack) {
maxAction[i] = workState.barrack;
}
}
}
int maxCount = 1;//最大可能组合数
for (int i = 0; i < 3; i ) {
maxCount *= ( maxAction[i] 1 );
}
//列出所有可能的动作组合，计算每种可能的花费，超出的是不可行的要去掉。
//多少个动作就需要多少重循环，用一个数字进行转换，就不用那么多重循环 注意不要超出最大整数范围
for (int i = 0; i < maxCount; i ) {
gameState newState = workState;
int tmp = i;
for (int j = 0; j < 3; j ) { //产生行动组合
newState.fromActionArray[j] = tmp % ( maxAction[j] 1 );
tmp /= maxAction[j] 1;
}
int sumCost = 0;
for (int j = 0; j < 3; j ) { //计算行动组合的花费
sumCost = newState.fromActionArray[j] * actionArray[j].costGold;
}
if ( sumCost <= workState.gold ) { //花费够用就是个合理的动作组合
//产生新的状态，然后加入states
newState.hour = 8;
newState.gold = newState.dGold - sumCost;
newState.dGold = newState.fromActionArray[0]*8 - newState.buildingBarrack*14 - newState.fromActionArray[2];
newState.tant = newState.fromActionArray[0];
newState.barrack = newState.buildingBarrack ;
newState.buildingBarrack = newState.fromActionArray[1];
newState.archer = newState.fromActionArray[2];
newState.fromStateIndex = workIndex;
//绝对差的不要了。
bool better = true;
for (int j = states.size() - 1; j >= 0 && states[j].hour == newState.hour; j--) {
if (states[j].gold >= newState.gold &&
states[j].dGold >= newState.dGold &&
states[j].barrack >= newState.barrack &&
states[j].buildingBarrack >= newState.buildingBarrack &&
states[j].archer >= newState.archer ) {
better = false;
break;
}
}
if (better) {
if (newState.hour < max8hour * 8) {
states.push_back(newState);
}
else {
if (newState.archer >= maxArcher) { //最大的都保留，因为barrack可能不同，路径不同
maxArcher = newState.archer;
states.push_back(newState);
}
}
for (int j = states.size() - 2; j >= 0 && states[j].hour == newState.hour; j--) {
if (states[j].gold <= newState.gold &&
states[j].dGold <= newState.dGold &&
states[j].barrack <= newState.barrack &&
states[j].buildingBarrack <= newState.buildingBarrack &&
states[j].archer <= newState.archer && (
states[j].gold < newState.gold ||
states[j].dGold < newState.dGold ||
states[j].barrack < newState.barrack ||
states[j].buildingBarrack < newState.buildingBarrack ||
states[j].archer < newState.archer) ) {
states.erase(states.begin() j) ;
}
}
}
}
}
workIndex ;
} while (workIndex < states.size() && states[workIndex].hour < max8hour * 8);
//输出最大的Archer的建造方案
vector<int> barrackCounts;
std::cout << states.size() << "\n";//输出空行
for (int i = states.size()-1; i >= 0 && states[i].archer == maxArcher; i--) {
if ( find(barrackCounts.begin() barrackCounts.end() states[i].barrack ) == barrackCounts.end()) {
barrackCounts.push_back(states[i].barrack); //记录此barrackCount
int tmpIndex = i ;
do {//输出此建造方案
std::cout << "时间:" << std::setw(5) << states[tmpIndex].hour
<< " 金币:" << std::setw(5) << states[tmpIndex].gold
<< " 收入:" << std::setw(5) << states[tmpIndex].dGold
<< " 营地:" << std::setw(5) << states[tmpIndex].tant
<< " 兵营:" << std::setw(5) << states[tmpIndex].barrack
<< " 弓手:" << std::setw(5) << states[tmpIndex].archer << "\n";
tmpIndex = states[tmpIndex].fromStateIndex;
} while (tmpIndex != -1);
std::cout << "\n";//输出空行
}
}
}
输出结果，此处有两种建造步骤，最后的弓手都是24个。第一种：
时间: 120 金币: 667 收入: 652 营地: 70 兵营: 6 弓手: 24
时间: 112 金币: 729 收入: 658 营地: 70 兵营: 6 弓手: 18
时间: 104 金币: 785 收入: 664 营地: 70 兵营: 6 弓手: 12
时间: 96 金币: 702 收入: 683 营地: 70 兵营: 5 弓手: 7
时间: 88 金币: 931 收入: 701 营地: 70 兵营: 4 弓手: 3
时间: 80 金币: 890 收入: 731 营地: 70 兵营: 2 弓手: 1
时间: 72 金币: 1164 收入: 746 营地: 70 兵营: 1 弓手: 0
时间: 64 金币: 854 收入: 760 营地: 70 兵营: 0 弓手: 0
时间: 56 金币: 620 收入: 744 营地: 68 兵营: 0 弓手: 0
时间: 48 金币: 522 收入: 608 营地: 51 兵营: 0 弓手: 0
时间: 40 金币: 408 收入: 504 营地: 38 兵营: 0 弓手: 0
时间: 32 金币: 360 收入: 408 营地: 26 兵营: 0 弓手: 0
时间: 24 金币: 294 收入: 336 营地: 17 兵营: 0 弓手: 0
时间: 16 金币: 224 收入: 280 营地: 10 兵营: 0 弓手: 0
时间: 8 金币: 210 收入: 224 营地: 3 兵营: 0 弓手: 0
时间: 0 金币: 100 收入: 200 营地: 0 兵营: 0 弓手: 0
第二种建造步骤：
时间: 120 金币: 683 收入: 626 营地: 65 兵营: 5 弓手: 24
时间: 112 金币: 652 收入: 631 营地: 65 兵营: 5 弓手: 19
时间: 104 金币: 654 收入: 628 营地: 64 兵营: 5 弓手: 14
时间: 96 金币: 621 收入: 633 营地: 64 兵营: 5 弓手: 9
时间: 88 金币: 640 收入: 611 营地: 59 兵营: 4 弓手: 5
时间: 80 金币: 822 收入: 628 营地: 59 兵营: 3 弓手: 2
时间: 72 金币: 868 收入: 644 营地: 59 兵营: 2 弓手: 0
时间: 64 金币: 684 收入: 664 营地: 58 兵营: 0 弓手: 0
时间: 56 金币: 920 收入: 664 营地: 58 兵营: 0 弓手: 0
时间: 48 金币: 522 收入: 608 营地: 51 兵营: 0 弓手: 0
时间: 40 金币: 408 收入: 504 营地: 38 兵营: 0 弓手: 0
时间: 32 金币: 360 收入: 408 营地: 26 兵营: 0 弓手: 0
时间: 24 金币: 294 收入: 336 营地: 17 兵营: 0 弓手: 0
时间: 16 金币: 224 收入: 280 营地: 10 兵营: 0 弓手: 0
时间: 8 金币: 210 收入: 224 营地: 3 兵营: 0 弓手: 0
时间: 0 金币: 100 收入: 200 营地: 0 兵营: 0 弓手: 0
可见暴力搜索能力很有限，游戏120小时范围内的计算就花费了近25分钟时间，游戏时间再加长就超出了我可以等待的时间上限了。不过此方法还是很有用的，因为其中的很多步骤其它更好的方法也可以用的，我们先做好暴力搜索，然后就有个很好的基础去找寻更好的方法。
同时通过查看程序输出，可以看出结果的基本模式。就是先建造营地，最后阶段再建兵营，训练弓手。
下一篇文章就要讲用另一种方法来解决这个问题，如果您有什么比暴力搜索更好的方法也欢迎在评论中留言告诉我，十分感谢！
