Guest User

Tyler Howard - NPCs using A* navigation with GOAP strategy

a guest
Mar 4th, 2013
38
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×