Guest User

Tyler Howard - NPCs using A* navigation with GOAP strategy

a guest
Mar 4th, 2013
26
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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