Loading

Paste #pl9h4mzsf

Wrap Raw Revise
  1. void THPathfinder::pathingInit(const THMap *pMap, int iStartX, int iStartY, int *piWidth, node_t *ppNode, int iGuessNumber)
  2. {
  3.     *piWidth = pMap->getWidth();
  4.     m_pDestination = NULL;
  5.     _allocNodeCache(*piWidth, pMap->getHeight());
  6.     *ppNode = m_pNodes + iStartY * *piWidth + iStartX;
  7.     pNode->prev = NULL;
  8.     pNode->distance = 0;
  9.     if (iGuessNumber == 1) MakeGuess1(*ppNode);
  10.     if (iGuessNumber == 2) MakeGuess2(*ppNode);
  11.     if (iGuessNumber == 3) MakeGuess3(*ppNode);
  12.     if (iGuessNumber == 4) MakeGuess4(*ppNode);
  13.     m_ppDirtyList[0] = *ppNode;
  14.     m_iDirtyCount = 1;
  15.     m_iOpenCount = 0;
  16. }
  17.  
  18. /** No need to check for the node being on the map edge, as the N/E/S/W
  19.    flags are set as to prevent travelling off the map (as well as to
  20.    prevent walking through walls). */
  21. THPathfinder::pathingNeighbours(uint32_t iFlags, int iWidth, int iTryNumber)
  22. {
  23.     uint32_t iPassable = iFlags & THMN_Passable;
  24.     if(iFlags & THMN_CanTravelW)
  25.     {
  26.         if (iTryNumber == 1) TryNode1(pNode - 1, 3, iTryNumber);
  27.         if (iTryNumber == 2) TryNode2(pNode - 1, 3, iTryNumber);
  28.         if (iTryNumber == 3) TryNode3(pNode - 1, 3, iTryNumber);
  29.         if (iTryNumber == 4) TryNode4(pNode - 1, 3, iTryNumber);
  30.     }
  31.     if(iFlags & THMN_CanTravelE)
  32.     {
  33.         if (iTryNumber == 1) TryNode1(pNode + 1, 1, iTryNumber);
  34.         if (iTryNumber == 2) TryNode2(pNode + 1, 1, iTryNumber);
  35.         if (iTryNumber == 3) TryNode3(pNode + 1, 1, iTryNumber);
  36.         if (iTryNumber == 4) TryNode4(pNode + 1, 1, iTryNumber);
  37.     }
  38.     if(iFlags & THMN_CanTravelN)
  39.     {
  40.         if (iTryNumber == 1) TryNode1(pNode - iWidth, 0, iTryNumber);
  41.         if (iTryNumber == 2) TryNode2(pNode - iWidth, 0, iTryNumber);
  42.         if (iTryNumber == 3) TryNode3(pNode - iWidth, 0, iTryNumber);
  43.         if (iTryNumber == 4) TryNode4(pNode - iWidth, 0, iTryNumber);
  44.     }
  45.     if(iFlags & THMN_CanTravelS)
  46.     {
  47.         if (iTryNumber == 1) TryNode1(pNode + iWidth, 2, iTryNumber);
  48.         if (iTryNumber == 2) TryNode2(pNode + iWidth, 2, iTryNumber);
  49.         if (iTryNumber == 3) TryNode3(pNode + iWidth, 2, iTryNumber);
  50.         if (iTryNumber == 4) TryNode4(pNode + iWidth, 2, iTryNumber);
  51.     }
  52. }
  53.  
  54. void THPathfinder::pathingTryNode(uint32_t iNFlags, uint32_t iPassable, node_t *pNeighbour, node_t *pNode, int iGuessNumber)
  55. {
  56.     if(iNFlags & THMN_Passable || iPassable == 0)
  57.     {
  58.         if(pNeighbour->prev == pNeighbour)
  59.         {
  60.             pNeighbour->prev = pNode;
  61.             pNeighbour->distance = pNode->distance + 1;
  62.             if (iGuessNumber == 1) MakeGuess1(pNeighbour);
  63.             if (iGuessNumber == 2) MakeGuess2(pNeighbour);
  64.             if (iGuessNumber == 3) MakeGuess3(pNeighbour);
  65.             if (iGuessNumber == 4) MakeGuess4(pNeighbour);
  66.             m_ppDirtyList[m_iDirtyCount++] = pNeighbour;
  67.             _openHeapPush(pNeighbour);
  68.         }
  69.         else if((pNode->distance + 1) < pNeighbour->distance)
  70.         {
  71.             pNeighbour->prev = pNode;
  72.             pNeighbour->distance = pNode->distance + 1;
  73.             /* Guess doesn't change, and already in the dirty list. */
  74.             _openHeapPromote(pNeighbour);
  75.         }
  76.     }
  77. }
  78.  
  79. bool THPathfinder::findPath(const THMap *pMap, int iStartX, int iStartY, int iEndX, int iEndY)
  80. {
  81.     if(pMap == NULL)
  82.         pMap = m_pDefaultMap;
  83.     if(pMap == NULL || pMap->getNode(iEndX, iEndY) == NULL
  84.         || (pMap->getNodeUnchecked(iEndX, iEndY)->iFlags & THMN_Passable) == 0)
  85.     {
  86.         m_pDestination = NULL;
  87.         return false;
  88.     }
  89.  
  90.     // As diagonal movement is not allowed, the minimum distance between two
  91.     // points is the sum of the distance in X and the distance in Y. Provided
  92.     // that the compiler generates clever assembly for abs(), this means that
  93.     // guesses can be calculated without branching and without sqrt().
  94. #define MakeGuess1(pNode) \
  95.     pNode->guess = abs(pNode->x - iEndX) + abs(pNode->y - iEndY)
  96.  
  97.     pathingInit(pMap, iStartX, iStartY, &iWidth, &pNode, 1);
  98.     node_t *pTarget = m_pNodes + iEndY * iWidth + iEndX;
  99.  
  100.     while(true)
  101.     {
  102.         if(pNode == pTarget)
  103.         {
  104.             m_pDestination = pTarget;
  105.             return true;
  106.         }
  107.  
  108.         uint32_t iFlags = pMap->getNodeUnchecked(pNode->x, pNode->y)->iFlags;
  109.  
  110. #define TryNode1(n, d, iGuessNumber) \
  111.         node_t *pNeighbour = n; \
  112.         uint32_t iNFlags = pMap->getNodeUnchecked(pNeighbour->x, pNeighbour->y)->iFlags; \
  113.         pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber)
  114.  
  115.         pathingNeighbours(iFlags, iWidth, 1);
  116.         if(m_iOpenCount == 0)
  117.         {
  118.             m_pDestination = NULL;
  119.             break;
  120.         }
  121.         else
  122.             pNode = _openHeapPop();
  123.     }
  124.     return false;
  125.  
  126. #undef MakeGuess1
  127. #undef TryNode
  128. }
  129.  
  130. bool THPathfinder::findPathToHospital(const THMap *pMap, int iStartX, int iStartY)
  131. {
  132.     if(pMap == NULL)
  133.         pMap = m_pDefaultMap;
  134.     if(pMap == NULL || pMap->getNode(iStartX, iStartY) == NULL
  135.         || (pMap->getNodeUnchecked(iStartX, iStartY)->iFlags & THMN_Passable) == 0)
  136.     {
  137.         m_pDestination = NULL;
  138.         return false;
  139.     }
  140.  
  141. #define MakeGuess2(pNode) pNode->guess = 0
  142.  
  143.     pathingInit(pMap, iStartX, iStartY, &iWidth, &pNode, 2);
  144.  
  145.     while(true)
  146.     {
  147.         uint32_t iFlags = pMap->getNodeUnchecked(pNode->x, pNode->y)->iFlags;
  148.  
  149.         if(iFlags & THMN_Hospital)
  150.         {
  151.             m_pDestination = pNode;
  152.             return true;
  153.         }
  154.  
  155. #define TryNode2(n, d, iGuessNumber) \
  156.         node_t *pNeighbour = n; \
  157.         uint32_t iNFlags = pMap->getNodeUnchecked(pNeighbour->x, pNeighbour->y)->iFlags; \
  158.         pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber)
  159.  
  160.         pathingNeighbours(iFlags, iWidth, 2);
  161.         if(m_iOpenCount == 0)
  162.         {
  163.             m_pDestination = NULL;
  164.             break;
  165.         }
  166.         else
  167.             pNode = _openHeapPop();
  168.     }
  169.     return false;
  170.  
  171. #undef MakeGuess
  172. #undef TryNode
  173. }
  174.  
  175. bool THPathfinder::findIdleTile(const THMap *pMap, int iStartX, int iStartY, int iN)
  176. {
  177.     if(pMap == NULL)
  178.         pMap = m_pDefaultMap;
  179.     if(pMap == NULL)
  180.     {
  181.         m_pDestination = NULL;
  182.         return false;
  183.     }
  184.  
  185. #define MakeGuess3(pNode) \
  186.     pNode->guess = 0
  187.  
  188.     pathingInit(pMap, iStartX, iStartY, &iWidth, &pNode, 3);
  189.     node_t *pPossibleResult = NULL;
  190.  
  191.     while(true)
  192.     {
  193.         pNode->open_idx = -1;
  194.         uint32_t iFlags = pMap->getNodeUnchecked(pNode->x, pNode->y)->iFlags;
  195.  
  196.         if((iFlags & THMN_DoNotIdle) == 0 && (iFlags & THMN_Passable) && (iFlags & THMN_Hospital))
  197.         {
  198.             if(iN == 0)
  199.             {
  200.                 m_pDestination = pNode;
  201.                 return true;
  202.             }
  203.             else
  204.             {
  205.                 pPossibleResult = pNode;
  206.                 --iN;
  207.             }
  208.         }
  209.  
  210.         node_t* pBestNext = NULL;
  211.         double fBestDistance = 0.0;
  212.  
  213. #define TryNode3(n, d, iGuessNumber) \
  214.         node_t *pNeighbour = n; \
  215.         uint32_t iNFlags = pMap->getNodeUnchecked(pNeighbour->x, pNeighbour->y)->iFlags; \
  216.         /* When finding an idle tile, do not navigate through doors */ \
  217.         switch(d) \
  218.         { \
  219.         case 0: \
  220.             if((iFlags & THMN_DoorNorth) == 0) { pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber); } \
  221.             break; \
  222.         case 1: \
  223.             if((iNFlags & THMN_DoorWest) == 0) { pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber); } \
  224.             break; \
  225.         case 2: \
  226.             if((iNFlags & THMN_DoorNorth) == 0) { pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber); } \
  227.             break; \
  228.         case 3: \
  229.             if((iFlags & THMN_DoorWest) == 0)  { pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber); } \
  230.             break; \
  231.         } \
  232.         /* Identify the neighbour in the open list nearest to the start */ \
  233.         if(pNeighbour->prev != pNeighbour && pNeighbour->open_idx != -1) \
  234.         { \
  235.             int iDX = pNeighbour->x - iStartX; \
  236.             int iDY = pNeighbour->y - iStartY; \
  237.             double fDistance = sqrt((double)(iDX * iDX + iDY * iDY)); \
  238.             if(pBestNext == NULL || fDistance < fBestDistance) \
  239.                 pBestNext = pNeighbour, fBestDistance = fDistance; \
  240.         }
  241.  
  242.         pathingNeighbours(iFlags, iWidth, 3);
  243.  
  244.         if(m_iOpenCount == 0)
  245.         {
  246.             m_pDestination = NULL;
  247.             break;
  248.         }
  249.         if(pBestNext)
  250.         {
  251.             // Promote the best neighbour to the front of the open list
  252.             // This causes sequential iN to give neighbouring results for most iN
  253.             pBestNext->guess = -pBestNext->distance;
  254.             _openHeapPromote(pBestNext);
  255.         }
  256.         pNode = _openHeapPop();
  257.     }
  258.     if(pPossibleResult)
  259.     {
  260.         m_pDestination = pPossibleResult;
  261.         return true;
  262.     }
  263.     return false;
  264.  
  265. #undef MakeGuess
  266. #undef TryNode
  267. }
  268.  
  269. bool THPathfinder::visitObjects(const THMap *pMap, int iStartX, int iStartY,
  270.                                 THObjectType eTHOB, int iMaxDistance,
  271.                                 lua_State *L, int iVisitFunction, bool anyObjectType)
  272. {
  273.     if(pMap == NULL)
  274.         pMap = m_pDefaultMap;
  275.     if(pMap == NULL)
  276.     {
  277.         m_pDestination = NULL;
  278.         return false;
  279.     }
  280.  
  281. #define MakeGuess4(pNode) \
  282.     pNode->guess = 0
  283.  
  284.     pathingInit(pMap, iStartX, iStarty, &iWidth, &pNode, 4);
  285.     uint32_t iTHOB = static_cast<uint32_t>(eTHOB) << 24;
  286.  
  287.     while(true)
  288.     {
  289.         uint32_t iFlags = pMap->getNodeUnchecked(pNode->x, pNode->y)->iFlags;
  290.  
  291. #define TryNode4(n, d, iGuessNumber) \
  292.         node_t *pNeighbour = n; \
  293.         int iObjectNumber = 0; \
  294.         const THMapNode *pMapNode = pMap->getNodeUnchecked(pNeighbour->x, pNeighbour->y);\
  295.         uint32_t iNFlags = pMap->getNodeUnchecked(pNeighbour->x, pNeighbour->y)->iFlags; \
  296.         if ((iNFlags & 0xFF000000) == iTHOB) \
  297.             iObjectNumber = 1; \
  298.         if(pMapNode->pExtendedObjectList != NULL)\
  299.         {\
  300.             int count = *pMapNode->pExtendedObjectList & 7;\
  301.             for(int i = 0; i < count; i++) \
  302.             { \
  303.                 int thob = (*pMapNode->pExtendedObjectList & (255 << (3  + (i << 3)))) >> (3 + (i << 3)); \
  304.                 if(thob == eTHOB)\
  305.                     iObjectNumber++; \
  306.             } \
  307.         } \
  308.         if(anyObjectType) \
  309.             iObjectNumber = 1; \
  310.         bool bSucces = false; \
  311.         for(int i = 0; i < iObjectNumber; i++) \
  312.         { \
  313.             /* call the given Lua function, passing four arguments: */ \
  314.             /* The x and y position of the object (Lua tile co-ords) */ \
  315.             /* The direction which was last travelled in to reach (x,y); */ \
  316.             /*   0 (north), 1 (east), 2 (south), 3 (west) */ \
  317.             /* The distance to the object from the search starting point */ \
  318.             lua_pushvalue(L, iVisitFunction); \
  319.             lua_pushinteger(L, pNeighbour->x + 1); \
  320.             lua_pushinteger(L, pNeighbour->y + 1); \
  321.             lua_pushinteger(L, d); \
  322.             lua_pushinteger(L, pNode->distance); \
  323.             lua_call(L, 4, 1); \
  324.             if(lua_toboolean(L, -1) != 0) \
  325.             { \
  326.                 bSucces = true; \
  327.             } \
  328.             lua_pop(L, 1); \
  329.         } \
  330.         if(bSucces) \
  331.             return true; \
  332.         if(pNode->distance < iMaxDistance) \
  333.         { \
  334.             switch(d) \
  335.             { \
  336.             case 0: \
  337.                 if((iFlags & THMN_DoorNorth) == 0) { pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber); } \
  338.                 break; \
  339.             case 1: \
  340.                 if((iNFlags & THMN_DoorWest) == 0) { pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber); } \
  341.                 break; \
  342.             case 2: \
  343.                 if((iNFlags & THMN_DoorNorth) == 0) { pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber); } \
  344.                 break; \
  345.             case 3: \
  346.                 if((iFlags & THMN_DoorWest) == 0)  { pathingTryNode(iNFlags, iPassable, pNeighbour, pNode, iGuessNumber); } \
  347.                 break; \
  348.             } \
  349.         }
  350.  
  351.         pathingNeighbours(iFlags, iWidth, 4);
  352.         if(m_iOpenCount == 0)
  353.         {
  354.             m_pDestination = NULL;
  355.             break;
  356.         }
  357.         else
  358.             pNode = _openHeapPop();
  359.     }
  360.     return false;
  361.  
  362. #undef MakeGuess
  363. #undef TryNode
  364. }
Posted by Anonymous at 20 Mar 2015, 15:34:42 UTC
Language: cpp • Views: 443

Comments