Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Tyler Howard - NPCs using A* navigation with GOAP strategy

a guest Mar 4th, 2013 14 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #pragma once
  2.  
  3. #include <vector>
  4. #include <set>
  5. #include <fstream>
  6.  
  7. using namespace std;
  8.  
  9. typedef bool (*wprecond_fptr)(vector<int>&, vector<int>&);
  10. typedef void (*weffect_fptr)(vector<int>&, vector<int>&);
  11. typedef bool (*wendcond_fptr)(vector<int>&, vector<int>&);
  12. typedef int (*wcost_fptr)(vector<int>&, vector<int>&, vector<int>&, vector<int>&);
  13.  
  14. enum ObjectiveType
  15. {
  16.         WORLD_COIN = 0,
  17.         WORLD_WOLF,
  18.         WORLD_OVEN,
  19.         WORLD_TABLE,
  20.         WORLD_RESTAURANT,
  21.         WORLD_GENERAL_STORE,
  22.         WORLD_FUR_TRADER,
  23.         WORLD_NPC,
  24.         WORLD_WHEAT,
  25.         WORLD_MILL,
  26.         WORLD_DOCTOR,
  27.         WORLD_NONE
  28. };
  29.  
  30. struct WorldAction
  31. {
  32.         string name;
  33.         wprecond_fptr precondition;
  34.         weffect_fptr effect;
  35.         ObjectiveType objective;
  36. };
  37.  
  38. enum NPCHungerProblemEnums
  39. {
  40.         NPC_STATE_HUNGRY = 0,
  41.         NPC_STATE_COINS,
  42.         NPC_STATE_FLOUR,
  43.         NPC_STATE_BREAD,
  44.         NPC_STATE_PIZZA,
  45.         NPC_STATE_SKINS,
  46.         NPC_STATE_WHEAT,
  47.         NPC_STATE_SICK,
  48.         NPC_STATE_MEDICINE
  49. };
  50.  
  51. enum WorldHungerProblemEnums
  52. {
  53.         WORLD_STATE_COINS = 0,
  54.         WORLD_STATE_WOLVES,
  55.         WORLD_STATE_WHEAT
  56. };
  57.  
  58. static bool w_canHarvestWheat(vector<int>& NPCState, vector<int>& worldState)
  59. {
  60.         return worldState[WORLD_STATE_WHEAT] > 0;
  61. }
  62.  
  63. static void w_harvestWheat(vector<int>& NPCState, vector<int>& worldState)
  64. {
  65.         --worldState[WORLD_STATE_WHEAT];
  66.         ++NPCState[NPC_STATE_WHEAT];
  67. }
  68.  
  69. static bool w_canProcessWheat(vector<int>& NPCState, vector<int>& worldState)
  70. {
  71.         return NPCState[NPC_STATE_WHEAT] > 0;
  72. }
  73.  
  74. static void w_processWheat(vector<int>& NPCState, vector<int>& worldState)
  75. {
  76.         --NPCState[NPC_STATE_WHEAT];
  77.         ++NPCState[NPC_STATE_FLOUR];
  78. }
  79.  
  80. static bool w_canPickupMoney(vector<int>& NPCState, vector<int>& worldState)
  81. {
  82.         return worldState[WORLD_STATE_COINS] > 0;
  83. }
  84.  
  85. static void w_pickupMoney(vector<int>& NPCState, vector<int>& worldState)
  86. {
  87.         --worldState[WORLD_STATE_COINS];
  88.         ++NPCState[NPC_STATE_COINS];
  89. }
  90.  
  91. static bool w_canEatBread(vector<int>& NPCState, vector<int>& worldState)
  92. {
  93.         return NPCState[NPC_STATE_HUNGRY] > 0 && NPCState[NPC_STATE_BREAD] > 0;
  94. }
  95.  
  96. static void w_eatBread(vector<int>& NPCState, vector<int>& worldState)
  97. {
  98.         --NPCState[NPC_STATE_BREAD];
  99.         --NPCState[NPC_STATE_HUNGRY];
  100. }
  101.  
  102. static bool w_canEatPizza(vector<int>& NPCState, vector<int>& worldState)
  103. {
  104.         return NPCState[NPC_STATE_HUNGRY] > 0 && NPCState[NPC_STATE_PIZZA] > 0;
  105. }
  106.  
  107. static void w_eatPizza(vector<int>& NPCState, vector<int>& worldState)
  108. {
  109.         --NPCState[NPC_STATE_PIZZA];
  110.         --NPCState[NPC_STATE_HUNGRY];
  111. }
  112.  
  113. static bool w_canBuyFlour(vector<int>& NPCState, vector<int>& worldState)
  114. {
  115.         return NPCState[NPC_STATE_HUNGRY] > 0 && NPCState[NPC_STATE_COINS] >= 1;
  116. }
  117.  
  118. static void w_buyFlour(vector<int>& NPCState, vector<int>& worldState)
  119. {
  120.         --NPCState[NPC_STATE_COINS];
  121.         ++NPCState[NPC_STATE_FLOUR];
  122. }
  123.  
  124. static bool w_canBuyPizza(vector<int>& NPCState, vector<int>& worldState)
  125. {
  126.         return NPCState[NPC_STATE_HUNGRY] > 0 && NPCState[NPC_STATE_COINS] >= 2;
  127. }
  128.  
  129. static void w_buyPizza(vector<int>& NPCState, vector<int>& worldState)
  130. {
  131.         NPCState[NPC_STATE_COINS] -= 2;
  132.         ++NPCState[NPC_STATE_PIZZA];
  133. }
  134.  
  135. static bool w_canBakeBread(vector<int>& NPCState, vector<int>& worldState)
  136. {
  137.         return NPCState[NPC_STATE_FLOUR] >= 1;
  138. }
  139.  
  140. static void w_bakeBread(vector<int>& NPCState, vector<int>& worldState)
  141. {
  142.         --NPCState[NPC_STATE_FLOUR];
  143.         ++NPCState[NPC_STATE_BREAD];
  144. }
  145.  
  146. static bool w_checkForHungerProblemEndCondition(vector<int>& NPCState, vector<int>& worldState)
  147. {
  148.         return NPCState[NPC_STATE_HUNGRY] == 0 && NPCState[NPC_STATE_SICK] == 0;
  149. }
  150.  
  151. static int w_calculateHungerProblemH(vector<int>& currentNPCState, vector<int>& currentWorldState, vector<int>& desiredNPCState, vector<int>& desiredWorldState)
  152. {
  153.         //all other variables don't matter - only thing that really matters for this problem is if hunger is 0
  154.         return (currentNPCState[NPC_STATE_HUNGRY] - desiredNPCState[NPC_STATE_HUNGRY]) + (currentNPCState[NPC_STATE_SICK] - desiredNPCState[NPC_STATE_SICK]);
  155. }
  156.  
  157. static bool w_canKillWolf(vector<int>& NPCState, vector<int>& worldState)
  158. {
  159.         return worldState[WORLD_STATE_WOLVES] > 0;
  160. }
  161.  
  162. static void w_killWolf(vector<int>& NPCState, vector<int>& worldState)
  163. {
  164.         --worldState[WORLD_STATE_WOLVES];
  165.         ++NPCState[NPC_STATE_SKINS];
  166. }
  167.  
  168. static bool w_canSellSkin(vector<int>& NPCState, vector<int>& worldState)
  169. {
  170.         return NPCState[NPC_STATE_SKINS] > 0;
  171. }
  172.  
  173. static void w_sellSkin(vector<int>& NPCState, vector<int>& worldState)
  174. {
  175.         --NPCState[NPC_STATE_SKINS];
  176.         ++NPCState[NPC_STATE_COINS];
  177. }
  178.  
  179. static bool w_canSellWheat(vector<int>& NPCState, vector<int>& worldState)
  180. {
  181.         return NPCState[NPC_STATE_WHEAT] > 0;
  182. }
  183.  
  184. static void w_sellWheat(vector<int>& NPCState, vector<int>& worldState)
  185. {
  186.         --NPCState[NPC_STATE_WHEAT];
  187.         ++NPCState[NPC_STATE_COINS];
  188. }
  189.  
  190. static bool w_canBuyMedicine(vector<int>& NPCState, vector<int>& worldState)
  191. {
  192.         return NPCState[NPC_STATE_COINS] > 0 && NPCState[NPC_STATE_SICK] > 0;
  193. }
  194.  
  195. static void w_buyMedicine(vector<int>& NPCState, vector<int>& worldState)
  196. {
  197.         --NPCState[NPC_STATE_COINS];
  198.         ++NPCState[NPC_STATE_MEDICINE];
  199. }
  200.  
  201. static bool w_canDrinkMedicine(vector<int>& NPCState, vector<int>& worldState)
  202. {
  203.         return NPCState[NPC_STATE_MEDICINE] > 0 && NPCState[NPC_STATE_SICK] > 0;
  204. }
  205.  
  206. static void w_drinkMedicine(vector<int>& NPCState, vector<int>& worldState)
  207. {
  208.         --NPCState[NPC_STATE_MEDICINE];
  209.         --NPCState[NPC_STATE_SICK];
  210. }
  211.  
  212. static bool w_checkForSicknessProblemEndCondition(vector<int>& NPCState, vector<int>& worldState)
  213. {
  214.         return NPCState[NPC_STATE_SICK] == 0;
  215. }
  216.  
  217. static int w_calculateSicknessProblemH(vector<int>& currentNPCState, vector<int>& currentWorldState, vector<int>& desiredNPCState, vector<int>& desiredWorldState)
  218. {
  219.         return currentNPCState[NPC_STATE_SICK] - desiredNPCState[NPC_STATE_SICK];
  220. }
  221.  
  222. static bool w_checkForGreedProblemEndCondition(vector<int>& NPCState, vector<int>& worldState)
  223. {
  224.         return false;           //Greed is insatiable!
  225. }
  226.  
  227. static int w_calculateGreedProblemH(vector<int>& currentNPCState, vector<int>& currentWorldState, vector<int>& desiredNPCState, vector<int>& desiredWorldState)
  228. {
  229.         return desiredNPCState[NPC_STATE_COINS] - currentNPCState[NPC_STATE_COINS];            
  230. }
  231.  
  232. enum WorldPathType
  233. {
  234.         WORLD_PATH_EMPTY = 0,
  235.         WORLD_PATH_START,                               //functionally equivalent to empty
  236.         WORLD_PATH_END,                         //functionally equivalent to empty
  237.         WORLD_PATH_WATER,                               //double cost (H)
  238.         WORLD_PATH_BLOCKED,                     //closed from the get-go
  239.  
  240.         //visited nodes turn into these types:
  241.         WORLD_PATH_OPEN,
  242.         WORLD_PATH_CLOSED,
  243.         WORLD_PATH_WORLD_PATH
  244. };
  245.  
  246. struct WorldAStarNode
  247. {
  248.  
  249. public:
  250.  
  251.         WorldPathType type;
  252.         WorldAStarNode* parent;
  253.  
  254.         int G;
  255.         int H;
  256.  
  257.         int row;
  258.         int col;
  259.  
  260.         bool open;
  261.         bool travelled;
  262.  
  263.         ObjectiveType inhabitor;
  264.         int npc;
  265.  
  266.         WorldAStarNode()
  267.         {
  268.                 type = WORLD_PATH_EMPTY;
  269.                 parent = 0;
  270.         }
  271.  
  272.         WorldAStarNode(WorldPathType pt, ObjectiveType inh, WorldAStarNode* prnt = 0)
  273.         {
  274.                 type = pt;
  275.                 inhabitor = inh;
  276.                 parent = prnt;
  277.                 travelled = false;
  278.                 npc = -1;
  279.         }
  280.  
  281.         WorldAStarNode(char c, int r, int co)
  282.         {
  283.                 switch(c)
  284.                 {
  285.                 case 'D':
  286.                         type = WORLD_PATH_EMPTY;
  287.                         inhabitor = WORLD_DOCTOR;
  288.                         break;
  289.  
  290.                 case 'N':
  291.                         type = WORLD_PATH_EMPTY;               
  292.                         inhabitor = WORLD_NPC;
  293.                         break;
  294.  
  295.                 default:
  296.                 case '.':
  297.                         type = WORLD_PATH_EMPTY;
  298.                         inhabitor = WORLD_NONE;
  299.                         break;
  300.  
  301.                 case '/':
  302.                         type = WORLD_PATH_WATER;
  303.                         inhabitor = WORLD_NONE;
  304.                         break;
  305.  
  306.                 case '#':
  307.                         type = WORLD_PATH_BLOCKED;
  308.                         inhabitor = WORLD_NONE;
  309.                         break;
  310.  
  311.                 case 'O':                              
  312.                         //oven - bake bread
  313.                         type = WORLD_PATH_EMPTY;
  314.                         inhabitor = WORLD_OVEN;
  315.                         break;
  316.  
  317.                 case 'W':                              
  318.                         //wolf - kill wolf
  319.                         type = WORLD_PATH_EMPTY;
  320.                         inhabitor = WORLD_WOLF;
  321.                         break;
  322.  
  323.                 case 'C':                              
  324.                         //coin - pickup coin
  325.                         type = WORLD_PATH_EMPTY;
  326.                         inhabitor = WORLD_COIN;
  327.                         break;
  328.  
  329.                 case 'F':
  330.                         //fur trader - sell skin
  331.                         type = WORLD_PATH_EMPTY;
  332.                         inhabitor = WORLD_FUR_TRADER;
  333.                         break;
  334.  
  335.                 case 'G':
  336.                         //general store - buy flour
  337.                         type = WORLD_PATH_EMPTY;
  338.                         inhabitor = WORLD_GENERAL_STORE;
  339.                         break;
  340.  
  341.                 case 'P':
  342.                         //pizza hut     - buy pizza
  343.                         type = WORLD_PATH_EMPTY;
  344.                         inhabitor = WORLD_RESTAURANT;
  345.                         break;
  346.  
  347.                 case 'T':
  348.                         //table - eat bread, eat pizza
  349.                         type = WORLD_PATH_EMPTY;
  350.                         inhabitor = WORLD_TABLE;
  351.                         break;
  352.  
  353.                 case '*':
  354.                         type = WORLD_PATH_EMPTY;
  355.                         inhabitor = WORLD_WHEAT;
  356.                         break;
  357.  
  358.                 case 'M':
  359.                         type = WORLD_PATH_EMPTY;
  360.                         inhabitor = WORLD_MILL;
  361.                         break;
  362.                 }
  363.  
  364.                 parent = 0;
  365.                 row = r;
  366.                 col = co;
  367.                 H = G = -1;
  368.                 open = false;
  369.         }
  370.  
  371.         bool isEmpty()
  372.         {
  373.                 return (type == WORLD_PATH_EMPTY || type == WORLD_PATH_WATER) && (inhabitor == WORLD_NONE);
  374.                 travelled = false;
  375.         }
  376.  
  377.         int getCost() const
  378.         {
  379.                 return H + G;
  380.         }
  381. };
  382.  
  383. struct WorldAStarNodeComp
  384. {
  385.         bool operator() (const WorldAStarNode* lhs, const WorldAStarNode* rhs) const
  386.         {
  387.                 if(lhs->getCost() == rhs->getCost())
  388.                 {
  389.                         if(lhs->H == rhs->H)
  390.                         {
  391.                                 return lhs < rhs;
  392.                         }
  393.                         else
  394.                         {
  395.                                 return lhs->H < rhs->H;
  396.                         }
  397.                 }
  398.                 else
  399.                 {
  400.                         return lhs->getCost() < rhs->getCost();
  401.                 }
  402.         }
  403. };
  404.  
  405. struct NPC
  406. {      
  407.         int row;
  408.         int col;
  409.  
  410.         WorldAStarNode* objectiveLoc;
  411.         WorldAction* action;
  412.         string nameOfCurrentAction;
  413.  
  414.         vector<int> state;
  415.         vector<string> currentplan;
  416.         vector<string> takenactions;
  417.  
  418.         bool dead;
  419. };
  420.  
  421. class WorldGOAPNode
  422. {
  423.  
  424. public:
  425.  
  426.         WorldGOAPNode(vector<int>& vars)
  427.         {
  428.                 GOAPvars.resize(vars.size());
  429.                 for(unsigned int i = 0; i < vars.size(); ++i)
  430.                         GOAPvars[i] = vars[i];
  431.                 parent = 0;
  432.                 lastAction = -1;
  433.         }
  434.  
  435.         WorldGOAPNode(WorldGOAPNode* p, int a)
  436.         {
  437.                 parent = p;
  438.  
  439.                 const vector<int>& v = p->GOAPvars;
  440.                 GOAPvars.resize(v.size());
  441.  
  442.                 for(unsigned int i = 0; i < v.size(); ++i)
  443.                         GOAPvars[i] = v[i];
  444.  
  445.                 lastAction = a;
  446.         }
  447.  
  448.         ~WorldGOAPNode() {}
  449.  
  450.         const int getCost() const { return G + H; }
  451.  
  452.         int G;
  453.         int H;
  454.  
  455.         WorldGOAPNode* parent;
  456.  
  457.         vector<int> GOAPvars;
  458.         int lastAction;
  459.  
  460. };
  461.  
  462. struct WorldGOAPNodeComp
  463. {
  464.         bool operator() (const WorldGOAPNode* lhs, const WorldGOAPNode* rhs) const
  465.         {
  466.                 if(lhs->getCost() == rhs->getCost())
  467.                 {
  468.                         if(lhs->H == rhs->H)
  469.                         {
  470.                                 return lhs < rhs;
  471.                         }
  472.                         else
  473.                         {
  474.                                 return lhs->H < rhs->H;
  475.                         }
  476.                 }
  477.                 else
  478.                 {
  479.                         return lhs->getCost() < rhs->getCost();
  480.                 }
  481.         }
  482. };
  483.  
  484. struct WorldGOAPNodeStateComp
  485. {
  486.         bool operator() (const WorldGOAPNode* lhs, const WorldGOAPNode* rhs) const
  487.         {
  488.                 int cmpidx = -1;
  489.                 for(unsigned int i = 0; i < lhs->GOAPvars.size(); ++i)
  490.                 {
  491.                         if(lhs->GOAPvars[i] != rhs->GOAPvars[i])
  492.                         {
  493.                                 cmpidx = i;
  494.                                 break;
  495.                         }
  496.                 }
  497.  
  498.                 if(cmpidx == -1) ++cmpidx;
  499.  
  500.                 return lhs->GOAPvars[cmpidx] < rhs->GOAPvars[cmpidx];
  501.         }
  502. };
  503.  
  504. class World
  505. {
  506.  
  507. public:
  508.  
  509.         World(const char* szFilePath)
  510.         {
  511.                 //populate world map
  512.                 ifstream mapFile(szFilePath, ios::in | ios::binary);
  513.                 unsigned int row = 0, col = 0;
  514.                 //if character == 0D or 0A, charpointer += 2, reset column, and move to next row
  515.                 vector<char> d;
  516.  
  517.                 mapFile.seekg(0, ios::end);
  518.                 d.resize(static_cast<int>(mapFile.tellg()));
  519.                 mapFile.seekg(0, ios::beg);
  520.  
  521.                 mapFile.read(d.data(), d.size());
  522.  
  523.                 mapFile.close();
  524.  
  525.                 worldMap.resize(1);
  526.  
  527.                 bool sickToggle = false;
  528.  
  529.                 for(unsigned int i = 0; i < d.size(); ++i)
  530.                 {
  531.                         if(d[i] != 0x0D && d[i] != 0x0A)
  532.                         {
  533.                                 WorldAStarNode p(d[i], row, col);
  534.                                 worldMap[row].push_back(p);
  535.                                
  536.                                 if(d[i] == 'N')
  537.                                 {
  538.                                         NPC n;
  539.                                         n.row = row;
  540.                                         n.col = col;
  541.                                         n.dead = false;
  542.  
  543.                                         n.state.resize(9);
  544.                                        
  545.                                         n.state[NPC_STATE_HUNGRY] = 1;
  546.                                         n.state[NPC_STATE_SKINS] = 0;
  547.                                         n.state[NPC_STATE_PIZZA] = 0;
  548.                                         n.state[NPC_STATE_FLOUR] = 0;
  549.                                         n.state[NPC_STATE_BREAD] = 0;
  550.                                         n.state[NPC_STATE_COINS] = 0;
  551.                                         n.state[NPC_STATE_WHEAT] = 0;
  552.                                         n.state[NPC_STATE_SICK] = (sickToggle ? 1 : 0 );
  553.                                         n.state[NPC_STATE_MEDICINE] = 0;
  554.  
  555.                                         sickToggle = !sickToggle;
  556.  
  557.                                         npcs.push_back(n);
  558.                                 }
  559.                                
  560.                                 ++col;
  561.                         }
  562.                         else
  563.                         {
  564.                                 worldMap.resize(++row + 1);
  565.                                 col = 0;
  566.                                 ++i;
  567.                         }
  568.                 }
  569.  
  570.                 state_vars.resize(3);   //wolves, coins
  571.                 state_vars[WORLD_STATE_COINS] = countObjectives(WORLD_COIN);
  572.                 state_vars[WORLD_STATE_WOLVES] = countObjectives(WORLD_WOLF);
  573.                 state_vars[WORLD_STATE_WHEAT] = countObjectives(WORLD_WHEAT);
  574.  
  575.                 registerAction("pickup coin", w_canPickupMoney, w_pickupMoney, WORLD_COIN);
  576.                 registerAction("buy flour", w_canBuyFlour, w_buyFlour, WORLD_GENERAL_STORE);
  577.                 registerAction("bake bread", w_canBakeBread, w_bakeBread, WORLD_OVEN);
  578.                 registerAction("buy pizza", w_canBuyPizza, w_buyPizza, WORLD_RESTAURANT);
  579.                 registerAction("eat bread", w_canEatBread, w_eatBread, WORLD_TABLE);
  580.                 registerAction("eat pizza", w_canEatPizza, w_eatPizza, WORLD_TABLE);
  581.                 registerAction("sell skin", w_canSellSkin, w_sellSkin, WORLD_FUR_TRADER);
  582.                 registerAction("kill wolf", w_canKillWolf, w_killWolf, WORLD_WOLF);
  583.                 registerAction("harvest wheat", w_canHarvestWheat, w_harvestWheat, WORLD_WHEAT);
  584.                 registerAction("process wheat", w_canProcessWheat, w_processWheat, WORLD_MILL);
  585.  
  586.                 registerAction("sell wheat", w_canSellWheat, w_sellWheat, WORLD_GENERAL_STORE);
  587.                
  588.                 registerAction("drink medicine", w_canDrinkMedicine, w_drinkMedicine, WORLD_TABLE);
  589.                
  590.                 registerAction("buy medicine", w_canBuyMedicine, w_buyMedicine, WORLD_DOCTOR);
  591.  
  592.                 registerEndCondition(w_checkForHungerProblemEndCondition);
  593.                 registerHCost(w_calculateHungerProblemH);
  594.  
  595.                 currframe = 0;
  596.  
  597.                 desiredNPCState.resize(9);
  598.                 desiredNPCState[NPC_STATE_HUNGRY] = 0;
  599.                 desiredNPCState[NPC_STATE_MEDICINE] = 0;
  600.                 desiredNPCState[NPC_STATE_COINS] = 10000;
  601.                 //don't care about rest
  602.  
  603.                 desiredWorldState.resize(3);
  604.                 //don't care about rest
  605.  
  606.                 for(unsigned int i = 0; i < npcs.size(); ++i)
  607.                         setNPCObjective(npcs[i]);
  608.  
  609.                 resetPathDisplay();
  610.         }
  611.  
  612.         void randomlyMoveNPC(NPC& n)
  613.         {
  614.                 if(n.dead) return;
  615.  
  616.                 WorldAStarNode* npcLoc = getNode(n.row, n.col);
  617.                 WorldAStarNode* npcChild;
  618.  
  619.                 int i = rand() % 5;
  620.                 int x = 0;
  621.                 int y = 0;
  622.                 switch(i)
  623.                 {
  624.                 case 0:         //left
  625.                         x = -1;
  626.                         break;
  627.  
  628.                 case 1:         //right
  629.                         x = 1;
  630.                         break;
  631.  
  632.                 case 2:         //up
  633.                         y = -1;
  634.                         break;
  635.  
  636.                 case 3:         //down
  637.                         y = 1;
  638.                         break;
  639.                 case 4: break;
  640.                 }
  641.  
  642.                 npcChild = getNode( n.row + x, n.col + y );
  643.  
  644.                 if(npcChild && npcChild->isEmpty())
  645.                 {
  646.                         npcLoc->inhabitor = WORLD_NONE;
  647.                         npcLoc->travelled = true;
  648.                         npcChild->inhabitor = WORLD_NPC;
  649.                         n.row = npcChild->row;
  650.                         n.col = npcChild->col;
  651.                 }
  652.         }
  653.  
  654.         void setNPCObjective(NPC& n)
  655.         {
  656.                 //run GOAP with simulated variables here
  657.                 vector<int> simulatedNPCState = n.state;
  658.                 vector<int> simulatedWorldState = state_vars;
  659.  
  660.                 bool foundEnd = false;
  661.  
  662.                 WorldGOAPNode* curr = new WorldGOAPNode(simulatedNPCState);
  663.                 curr->G = 0;
  664.                 curr->H = cost(curr->GOAPvars, simulatedWorldState, desiredNPCState, desiredWorldState);
  665.  
  666.                 set<WorldGOAPNode*, WorldGOAPNodeComp> oNodes;
  667.                 set<WorldGOAPNode*, WorldGOAPNodeStateComp> cNodes;
  668.                 vector<WorldGOAPNode*> allNodes;
  669.  
  670.                 oNodes.insert(curr);
  671.                 allNodes.push_back(curr);
  672.  
  673.                 n.currentplan.clear();
  674.  
  675.                 while(!foundEnd)
  676.                 {
  677.                         curr = *oNodes.begin();
  678.                         oNodes.erase(curr);
  679.                         cNodes.insert(curr);
  680.  
  681.                         if(endcondition(curr->GOAPvars, simulatedWorldState))
  682.                         {
  683.                                 foundEnd = true;
  684.  
  685.                                 //set NPC objective and action here
  686.  
  687.                                 //get one-step-below-root node
  688.                                 WorldGOAPNode* firstActionNode = curr;
  689.                                 while(firstActionNode->parent->parent != 0)
  690.                                 {
  691.                                         firstActionNode = firstActionNode->parent;
  692.                                 }
  693.  
  694.                                 n.action = &action_defs[firstActionNode->lastAction];
  695.                                 n.objectiveLoc = findNearestNode(getNode(n.row, n.col), n.action->objective);
  696.  
  697.                                 //generate log
  698.                                 WorldGOAPNode* c = curr;
  699.                                 while(c->lastAction != -1)
  700.                                 {
  701.                                         n.currentplan.insert(n.currentplan.begin(), action_defs[c->lastAction].name);
  702.                                         c = c->parent;
  703.                                 }
  704.                                 n.currentplan.push_back("success");
  705.  
  706.                                 n.nameOfCurrentAction = n.action->name;
  707.                         }
  708.                         else
  709.                         {
  710.                                 for(unsigned int i = 0; i < action_defs.size(); ++i)
  711.                                 {
  712.                                         if(action_defs[i].precondition(curr->GOAPvars, simulatedWorldState))
  713.                                         {
  714.                                                 WorldGOAPNode* newNode = new WorldGOAPNode(curr, i);
  715.  
  716.                                                 action_defs[i].effect(newNode->GOAPvars, simulatedWorldState);
  717.                                                 newNode->G = curr->G + 1;
  718.                                                 newNode->H = cost(newNode->GOAPvars, simulatedWorldState, desiredNPCState, desiredWorldState);
  719.  
  720.                                                 if(cNodes.find(newNode) == cNodes.end())
  721.                                                 {
  722.                                                         oNodes.insert(newNode);
  723.                                                         allNodes.push_back(newNode);
  724.                                                 }
  725.                                                 else
  726.                                                         delete newNode;
  727.                                         }
  728.                                 }
  729.  
  730.                                 if(oNodes.empty())
  731.                                 {
  732.                                         foundEnd = true;
  733.  
  734.                                         WorldGOAPNode* c = curr;
  735.                                         while(c->lastAction != -1)
  736.                                         {
  737.                                                 n.currentplan.insert(n.currentplan.begin(), action_defs[c->lastAction].name);
  738.                                                 c = c->parent;
  739.                                         }
  740.  
  741.                                         n.currentplan.push_back("impossible");
  742.                                         n.dead = true;
  743.                                 }
  744.                         }
  745.                 }
  746.  
  747.                 for(unsigned int i = 0; i < allNodes.size(); ++i)
  748.                 {
  749.                         delete allNodes[i];
  750.                 }
  751.         }
  752.  
  753.         int countObjectives(ObjectiveType t)
  754.         {
  755.                 int count = 0;
  756.                 for(unsigned int i = 0; i < worldMap.size(); ++i)
  757.                 {
  758.                         for(unsigned int j = 0; j < worldMap[0].size(); ++j)
  759.                         {
  760.                                 if(worldMap[i][j].inhabitor == t)
  761.                                         ++count;
  762.                         }
  763.                 }
  764.                 return count;
  765.         }
  766.  
  767.         int getDistance(WorldAStarNode* curr, WorldAStarNode* end)
  768.         {
  769.                 return abs(curr->col - end->col) + abs(curr->row - end->row);
  770.         }
  771.  
  772.         WorldAStarNode* findNearestNode(WorldAStarNode* start, ObjectiveType t)
  773.         {
  774.                 vector<WorldAStarNode*> nodes;
  775.  
  776.                 for(unsigned int i = 0; i < worldMap.size(); ++i)
  777.                 {
  778.                         for(unsigned int j = 0; j < worldMap[i].size(); ++j)
  779.                         {
  780.                                 if(worldMap[i][j].inhabitor == t)
  781.                                         nodes.push_back(&(worldMap[i][j]));
  782.                         }
  783.                 }
  784.  
  785.                 if(nodes.size() == 0)
  786.                         return 0;
  787.                 else
  788.                 {
  789.                         WorldAStarNode* nodeToReturn = nodes[0];
  790.                         int smallestDistance = getDistance(start, nodes[0]);
  791.                         //int smallestDistance = getAStarDistance(start, nodes[0]);
  792.  
  793.                         for(unsigned int i = 1; i < nodes.size(); ++i)
  794.                         {
  795.                                 if(getDistance(start, nodes[i]) < smallestDistance)                                     //TODO: change from manhattan distance to reachable via A*
  796.                                 //int dist = getAStarDistance(start, nodes[i]);
  797.                                 //if(dist != -1 && dist < smallestDistance)
  798.                                 {
  799.                                         nodeToReturn = nodes[i];
  800.                                         smallestDistance = getDistance(start, nodes[i]);
  801.                                         //smallestDistance = dist;
  802.                                 }
  803.                         }
  804.  
  805.                         if(smallestDistance != -1)
  806.                                 return nodeToReturn;
  807.                         else
  808.                                 return 0;
  809.                 }
  810.         }
  811.  
  812.         //never actually called, I believe
  813.         int getAStarDistance(WorldAStarNode* start, WorldAStarNode* end)
  814.         {
  815.                 bool foundEnd = false;
  816.                 set<WorldAStarNode*, WorldAStarNodeComp> oNodes;
  817.                 set<WorldAStarNode*, WorldAStarNodeComp> cNodes;
  818.  
  819.                 oNodes.insert(start);
  820.  
  821.                 while(!foundEnd)
  822.                 {
  823.                         if(oNodes.size() > 0)
  824.                         {
  825.                                 WorldAStarNode* curr = *oNodes.begin();
  826.                                 oNodes.erase(oNodes.begin());
  827.  
  828.                                 curr->open = false;
  829.  
  830.                                 if(curr == end)
  831.                                 {
  832.                                         foundEnd = true;
  833.                                         int count = 0;
  834.  
  835.                                         while(curr != 0)
  836.                                         {
  837.                                                 ++count;
  838.                                                 curr = curr->parent;
  839.                                         }
  840.  
  841.                                         return count;
  842.                                 }
  843.                                 else
  844.                                         cNodes.insert(curr);
  845.  
  846.                                 for(int x = -1; x <= 1; ++x)
  847.                                 {
  848.                                         for(int y = -1; y <= 1; ++y)
  849.                                         {
  850.                                                 if((abs(x) == 1 && y == 0 || abs(y) == 1 && x == 0) && !foundEnd)
  851.                                                 {
  852.                                                         WorldAStarNode* surr = getNode(curr->row + x, curr->col + y);
  853.                                                         if(surr != 0)
  854.                                                         {
  855.                                                                 //reparenting
  856.                                                                 if( (surr->isEmpty() || surr == end) && cNodes.find(surr) == cNodes.end() )
  857.                                                                 {
  858.                                                                         if(surr->open)
  859.                                                                         {
  860.                                                                                 //if surr's G would lower if surr were connected to parent than if currently
  861.                                                                                 int newG = curr->G + (surr->type != WORLD_PATH_WATER ? 1 : 5);
  862.                                                                                 if(newG < surr->G)                              //no improvement, choose old parent
  863.                                                                                 {
  864.                                                                                         oNodes.erase(surr);
  865.                                                                                         surr->parent = curr;
  866.                                                                                         surr->G = newG;
  867.                                                                                         oNodes.insert(surr);
  868.                                                                                 }
  869.                                                                         }
  870.  
  871.                                                                         else
  872.                                                                         {
  873.                                                                                 surr->H = getDistance(surr, end);
  874.                                                                                 surr->G = (surr->type != WORLD_PATH_WATER ? 1 : 5) + curr->G;
  875.                                                                                 surr->open = true;
  876.                                                                                 surr->parent = curr;
  877.                                                                                 oNodes.insert(surr);
  878.                                                                         }
  879.                                                                 }
  880.                                                         }
  881.                                                 }
  882.                                         }
  883.                                 }
  884.                         }
  885.                         else
  886.                         {
  887.                                 foundEnd = true;
  888.                                 return -1;
  889.                         }
  890.                 }
  891.         }
  892.  
  893.         WorldAStarNode* getNode(unsigned int x, unsigned int y)
  894.         {
  895.                 if( x < 0 || x >= worldMap.size() || y < 0 || y >= worldMap[x].size() ) return 0;
  896.  
  897.                 return &(worldMap[x][y]);
  898.         }
  899.  
  900.         void resetPathDisplay()
  901.         {
  902.                 for(unsigned int i = 0; i < worldMap.size(); ++i)
  903.                 {
  904.                         for(unsigned int j = 0; j < worldMap[0].size(); ++j)
  905.                         {
  906.                                 worldMap[i][j].npc = - 1;
  907.                         }
  908.                 }
  909.         }
  910.  
  911.         void update()
  912.         {
  913.                 resetPathDisplay();
  914.  
  915.                 for(unsigned int i = 0; i < npcs.size(); ++i)
  916.                 {
  917.                         //hunger check over time
  918.                         if(currframe % 10 == 0 && npcs[i].state[NPC_STATE_HUNGRY] == 0)
  919.                                 npcs[i].state[NPC_STATE_HUNGRY] = (rand() % 2 == 0) ? 0 : 1;
  920.  
  921.                         //sickness check over time
  922.                         if(currframe % 20 == 0 && npcs[i].state[NPC_STATE_SICK] == 0)
  923.                                 npcs[i].state[NPC_STATE_SICK] = (rand() % 2 == 0) ? 0 : 1;
  924.  
  925.                         //if NPC hasn't satisfied their needs yet
  926.                         if(!endcondition(npcs[i].state, state_vars) && !npcs[i].dead)
  927.                         {
  928.  
  929.                                 WorldAStarNode* npcLoc = getNode(npcs[i].row, npcs[i].col);
  930.                                 if(npcs[i].objectiveLoc == 0 || npcs[i].action == 0)
  931.                                 {
  932.                                         setNPCObjective(npcs[i]);
  933.                                 }
  934.                                 else
  935.                                 {
  936.                                         if(getDistance( npcLoc, npcs[i].objectiveLoc ) <= 1)
  937.                                         {
  938.                                                 if(isActionValid(npcs[i]) && npcs[i].action->precondition(npcs[i].state, state_vars))
  939.                                                 {
  940.                                                         //change NPC state
  941.                                                         //already ran precondition when determining objective
  942.                                                         npcs[i].action->effect(npcs[i].state, state_vars);
  943.                                                         npcs[i].takenactions.push_back(npcs[i].action->name);
  944.  
  945.                                                         //change world state
  946.                                                         if(isObjectiveConsumable(npcs[i].objectiveLoc->inhabitor))
  947.                                                                 npcs[i].objectiveLoc->inhabitor = WORLD_NONE;
  948.  
  949.                                                         npcs[i].action = 0;
  950.                                                 }
  951.                                                 else
  952.                                                 {
  953.                                                         npcs[i].takenactions.push_back("plan invalid");
  954.                                                 }
  955.                                
  956.                                                 //              reformulate plan
  957.                                                 //                      observe world state
  958.                                                 //                      get new action by simulating NPC and world states, not by actually altering existing states
  959.                                                 if(!endcondition(npcs[i].state, state_vars))
  960.                                                         setNPCObjective(npcs[i]);
  961.                                         }
  962.                                
  963.  
  964.                                         moveNPCTowardObjective(npcLoc, npcs[i], i);
  965.                                         resetPaths();
  966.                                 }
  967.                         }
  968.                         else
  969.                         {
  970.                                 randomlyMoveNPC(npcs[i]);
  971.                         }
  972.                 }
  973.  
  974.                 for(unsigned int i = 0; i < npcs.size(); ++i)
  975.                 {
  976.                         if(!npcs[i].dead)
  977.                         {
  978.                                 if(getNumSurroundSickNPCs(getNode(npcs[i].row, npcs[i].col)) > 0)
  979.                                 {
  980.                                         npcs[i].state[NPC_STATE_SICK] = 1;
  981.                                 }
  982.                         }
  983.                 }
  984.  
  985.                 if(currframe % 5 == 0)
  986.                 {
  987.  
  988.                         //wheat repopulates and dies according to Conway's Game of Life
  989.  
  990.                         //first pass: mark tiles with their new result (i.e. die, live on, reproduce)
  991.                         //vector<WorldAStarNode*> wheatLives;           //encountered wheat that lives on to next generation - needs nothing done to it
  992.                         vector<WorldAStarNode*> wheatDies;              //encountered wheat that dies
  993.                         vector<WorldAStarNode*> wheatGrows;             //empty cells that touch exactly three cells
  994.  
  995.                         for(unsigned int i = 0; i < worldMap.size(); ++i)
  996.                         {
  997.                                 for(unsigned int j = 0; j < worldMap[0].size(); ++j)
  998.                                 {
  999.                                         if(worldMap[i][j].inhabitor == WORLD_WHEAT)
  1000.                                         {
  1001.                                                 //chance for wheat to die
  1002.                                                 int numwheat = getNumSurroundWheat(worldMap[i][j]);
  1003.                                                 if(numwheat < 2 || numwheat > 3)
  1004.                                                         wheatDies.push_back(&worldMap[i][j]);
  1005.                                         }
  1006.  
  1007.                                         if(worldMap[i][j].inhabitor == WORLD_NONE)
  1008.                                         {
  1009.                                                 //chance to grow wheat in this cell
  1010.                                                 if(getNumSurroundWheat(worldMap[i][j]) == 3)
  1011.                                                         wheatGrows.push_back(&worldMap[i][j]);
  1012.                                         }
  1013.                                 }
  1014.                         }
  1015.  
  1016.                         //second pass:
  1017.                         for(unsigned int i = 0; i < wheatDies.size(); ++i)
  1018.                         {
  1019.                                 wheatDies[i]->inhabitor = WORLD_NONE;
  1020.                         }
  1021.  
  1022.                         for(unsigned int i = 0; i < wheatGrows.size(); ++i)
  1023.                         {
  1024.                                 wheatGrows[i]->inhabitor = WORLD_WHEAT;
  1025.                         }
  1026.  
  1027.                         state_vars[WORLD_STATE_WHEAT] = countObjectives(WORLD_WHEAT);
  1028.                 }
  1029.  
  1030.                 ++currframe;
  1031.  
  1032.                 //"kill" dead NPCs
  1033.                 for(unsigned int i = 0; i < worldMap.size(); ++i)
  1034.                 {
  1035.                         for(unsigned int j = 0; j < worldMap[0].size(); ++j)
  1036.                         {
  1037.                                 NPC* n = getNPCAtLoc(i, j);
  1038.                                 if(n != 0 && n->dead == true)
  1039.                                 {
  1040.                                         getNode(i, j)->inhabitor = WORLD_NONE;
  1041.                                 }
  1042.                         }
  1043.                 }
  1044.  
  1045.         }
  1046.  
  1047.         int getNumSurroundWheat(WorldAStarNode& node)
  1048.         {
  1049.                 int numWheat = 0;
  1050.                 for(int x = -1; x <= 1; ++x)
  1051.                 {
  1052.                         for(int y = -1; y <= 1; ++y)
  1053.                         {
  1054.                                 if( !(x == 0 && y == 0) )
  1055.                                 {
  1056.                                         WorldAStarNode* testNode = getNode(node.row + x, node.col + y);
  1057.                                         if(testNode != 0 && testNode->inhabitor == WORLD_WHEAT)
  1058.                                                 ++numWheat;
  1059.                                 }
  1060.                         }
  1061.                 }
  1062.                 return numWheat;
  1063.         }
  1064.  
  1065.         NPC* getNPCAtLoc(int x, int y)
  1066.         {
  1067.                 WorldAStarNode* n = getNode(x, y);
  1068.                 if(n == 0 || n->inhabitor != WORLD_NPC) return 0;
  1069.  
  1070.                 for(unsigned int i = 0; i < worldMap.size(); ++i)
  1071.                 {
  1072.                         for(unsigned int j = 0; j < worldMap[0].size(); ++j)
  1073.                         {
  1074.                                 for(unsigned int k = 0; k < npcs.size(); ++k)
  1075.                                 {
  1076.                                         if(npcs[k].row == x && npcs[k].col == y)
  1077.                                                 return &npcs[i];
  1078.                                 }
  1079.                         }
  1080.                 }
  1081.  
  1082.                 return 0;
  1083.         }
  1084.  
  1085.         int getNumSurroundSickNPCs(WorldAStarNode* node)
  1086.         {
  1087.                 int numSick = 0;
  1088.                 for(int x = -1; x <= 1; ++x)
  1089.                 {
  1090.                         for(int y = -1; y <= 1; ++y)
  1091.                         {
  1092.                                 if( !(x == 0 && y == 0) )
  1093.                                 {
  1094.                                         NPC* n = getNPCAtLoc(node->row + x, node->col + y);
  1095.                                         if(n != 0 && !n->dead && n->state[NPC_STATE_SICK] > 0)
  1096.                                                 ++numSick;
  1097.                                 }
  1098.                         }
  1099.                 }
  1100.                 return numSick;
  1101.         }
  1102.  
  1103.         bool isObjectiveConsumable(ObjectiveType t)
  1104.         {
  1105.                 return t == WORLD_COIN || t == WORLD_WOLF || t == WORLD_WHEAT;
  1106.         }
  1107.  
  1108.         bool isActionValid(NPC& n)
  1109.         {
  1110.                 //returns true if objective is still present at that location
  1111.                 return n.objectiveLoc->inhabitor == n.action->objective;
  1112.         }
  1113.  
  1114.         void moveNPCTowardObjective(WorldAStarNode* npcLoc, NPC& n, int nindex)
  1115.         {
  1116.                 bool foundEnd = false;
  1117.                 set<WorldAStarNode*, WorldAStarNodeComp> oNodes;
  1118.                 set<WorldAStarNode*, WorldAStarNodeComp> cNodes;
  1119.  
  1120.                 oNodes.insert(npcLoc);
  1121.  
  1122.                 WorldAStarNode* npcChild = 0;           //next location to step to
  1123.                 WorldAStarNode* objective = n.objectiveLoc;
  1124.  
  1125.                 while(!foundEnd)
  1126.                 {
  1127.                         if(oNodes.size() > 0)
  1128.                         {
  1129.                                 WorldAStarNode* curr = *oNodes.begin();
  1130.                                 oNodes.erase(oNodes.begin());
  1131.  
  1132.                                 curr->open = false;
  1133.  
  1134.                                 if(curr == objective)
  1135.                                 {
  1136.                                         foundEnd = true;
  1137.  
  1138.                                         if(getDistance(npcLoc, objective) > 1)
  1139.                                         {
  1140.                                                 while(curr->parent->parent != 0)
  1141.                                                 {
  1142.                                                         curr->npc = nindex;
  1143.                                                         curr = curr->parent;
  1144.                                                 }
  1145.  
  1146.                                                 npcChild = curr;
  1147.                                         }
  1148.                                         else
  1149.                                                 npcChild = npcLoc;
  1150.                                 }
  1151.                                 else
  1152.                                         cNodes.insert(curr);
  1153.  
  1154.                                 for(int x = -1; x <= 1; ++x)
  1155.                                 {
  1156.                                         for(int y = -1; y <= 1; ++y)
  1157.                                         {
  1158.                                                 if((abs(x) == 1 && y == 0 || abs(y) == 1 && x == 0) && !foundEnd)
  1159.                                                 {
  1160.                                                         WorldAStarNode* surr = getNode(curr->row + x, curr->col + y);
  1161.                                                         if(surr != 0)
  1162.                                                         {
  1163.                                                                 //reparenting
  1164.                                                                 if( (surr->isEmpty() || surr == objective) && cNodes.find(surr) == cNodes.end() )
  1165.                                                                 {
  1166.                                                                         if(surr->open)
  1167.                                                                         {
  1168.                                                                                 //if surr's G would lower if surr were connected to parent than if currently
  1169.                                                                                 int newG = curr->G + (surr->type != WORLD_PATH_WATER ? 1 : 5);
  1170.                                                                                 if(newG < surr->G)                              //no improvement, choose old parent
  1171.                                                                                 {
  1172.                                                                                         oNodes.erase(surr);
  1173.                                                                                         surr->parent = curr;
  1174.                                                                                         surr->G = newG;
  1175.                                                                                         oNodes.insert(surr);
  1176.                                                                                 }
  1177.                                                                         }
  1178.                                                                
  1179.                                                                         else
  1180.                                                                         {
  1181.                                                                                 surr->H = getDistance(surr, objective);
  1182.                                                                                 surr->G = (surr->type != WORLD_PATH_WATER ? 1 : 5) + curr->G;
  1183.                                                                                 surr->open = true;
  1184.                                                                                 surr->parent = curr;
  1185.                                                                                 oNodes.insert(surr);
  1186.                                                                         }
  1187.                                                                 }
  1188.                                                         }
  1189.                                                 }
  1190.                                         }
  1191.                                 }
  1192.                         }
  1193.                         else
  1194.                         {
  1195.                                 foundEnd = true;
  1196.                                 randomlyMoveNPC(n);
  1197.                                 return;
  1198.                         }
  1199.                 }
  1200.  
  1201.                 if(getDistance(npcLoc, n.objectiveLoc) > 1 && npcChild->isEmpty()) //isEmpty for situations when another NPC is blocking path
  1202.                 {
  1203.                         npcLoc->inhabitor = WORLD_NONE;
  1204.                         npcLoc->travelled = true;
  1205.                         npcChild->inhabitor = WORLD_NPC;
  1206.                         n.row = npcChild->row;
  1207.                         n.col = npcChild->col;
  1208.                 }
  1209.                
  1210.         }
  1211.  
  1212.         void resetPaths()
  1213.         {
  1214.                 for(unsigned int i = 0; i < worldMap.size(); ++i)
  1215.                 {
  1216.                         for(unsigned int j = 0; j < worldMap[0].size(); ++j)
  1217.                         {
  1218.                                 worldMap[i][j].parent = 0;
  1219.                                 worldMap[i][j].open = false;
  1220.                                 worldMap[i][j].G = worldMap[i][j].H = -1;
  1221.                         }
  1222.                 }
  1223.         }
  1224.  
  1225.         void registerAction(const string& n, wprecond_fptr p, weffect_fptr e, ObjectiveType t)
  1226.         {
  1227.                 WorldAction a;
  1228.                 a.name = n;
  1229.                 a.precondition = p;
  1230.                 a.effect = e;
  1231.                 a.objective = t;
  1232.                 action_defs.push_back(a);
  1233.         }
  1234.  
  1235.         void registerEndCondition(wendcond_fptr e)
  1236.         {
  1237.                 endcondition = e;
  1238.         }
  1239.  
  1240.         void registerHCost(wcost_fptr c)
  1241.         {
  1242.                 cost = c;
  1243.         }
  1244.  
  1245.         vector<vector<WorldAStarNode>> worldMap;
  1246.         vector<NPC> npcs;
  1247.         vector<WorldAction> action_defs;
  1248.  
  1249.         vector<int> state_vars;                
  1250.         vector<int> desiredNPCState;
  1251.         vector<int> desiredWorldState;
  1252.  
  1253.         wendcond_fptr endcondition;
  1254.         wcost_fptr cost;
  1255.  
  1256.         unsigned int currframe;
  1257. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top