1. C++ / Говнокод #20295

    +1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    82. 82
    83. 83
    84. 84
    85. 85
    86. 86
    87. 87
    88. 88
    89. 89
    90. 90
    91. 91
    92. 92
    93. 93
    std::deque<std::pair<int, int>> Pathing::findPath(int sx, int sy, int fx, int fy) const
    {
        std::list<Node> openNodes;
        std::list<Node> closeNodes;
    
        const Node startNode{nullptr, sx, sy, 0, 0, 0};
        openNodes.push_back(startNode);
    
        auto cells = gameMap->getCells();
    
        auto findNode = [](auto&& list, int x, int y)
        {
            return std::find_if(std::begin(std::forward<decltype(list)>(list)),
                                std::end(std::forward<decltype(list)>(list)),
                    [x, y](auto n) {return n.x == x && n.y == y;});
        };
    
        auto isNodeInList = [findNode](auto&& list, int x, int y)
        {
            return findNode(std::forward<decltype(list)>(list), x, y) != list.cend();
        };
    
        auto processNode = [&](auto iterCurrentNode, int x, int y)
        {
            const auto nx = iterCurrentNode->x + x;
            const auto ny = iterCurrentNode->y + y;
    
            if (cells[nx][ny].passable && !isNodeInList(closeNodes, nx, ny))
            {
                const auto G = iterCurrentNode->G + (x && y ? 14 : 10);
                const auto H = (std::abs(fx - nx) + std::abs(fy - ny)) * 10;
                const auto F = G + H;
    
                auto node = findNode(openNodes, nx, ny);
    
                if (node == openNodes.cend())
                {
                    openNodes.push_back({&(*iterCurrentNode), nx, ny, G, H, F});
    
                    if (nx == fx && ny == fy)
                        return true;
                }
                else
                {
                    if (G < node->G)
                    {
                        node->parent = &(*iterCurrentNode);
                        node->G = G;
                        node->H = H;
                        node->F = F;
                    }
                }
            }
    
            return false;
        };
    
        while (!openNodes.empty())
        {
            auto iterMinF = std::min_element(openNodes.cbegin(), openNodes.cend(),
                    [](auto n1, auto n2) {return n1.F < n2.F;});
    
            closeNodes.push_back(*iterMinF);
            auto iter = closeNodes.insert(closeNodes.cend(), *iterMinF);
    
            openNodes.erase(iterMinF);
    
            if (processNode(iter,  1,  0) ||
                processNode(iter,  1,  1) ||
                processNode(iter,  0,  1) ||
                processNode(iter, -1,  1) ||
                processNode(iter, -1,  0) ||
                processNode(iter, -1, -1) ||
                processNode(iter,  0, -1) ||
                processNode(iter,  1, -1))
                break;
        }
    
        auto finalNode = findNode(openNodes, fx, fy);
        if (finalNode == openNodes.cend())
            return {};
    
        std::deque<std::pair<int, int>> route{{finalNode->x, finalNode->y}};
        const Node* temp = finalNode->parent;
    
        while (temp)
        {
            route.push_front({temp->x, temp->y});
            temp = temp->parent;
        }
    
        return route;
    }

    Запостил: jangolare, 30 Июня 2016

    Комментарии (0) RSS

    Добавить комментарий

    Ошибка компиляции комментария:
    1. Гости могут высказаться только во вторник, пятницу или субботу
    ava Я, guest, находясь в здравом уме и твердой памяти, торжественно заявляю:
    А не использовать ли нам bbcode?
    • [b]жирный[/b] — жирный
    • [i]курсив[/i] — курсив
    • [u]подчеркнутый[/u] — подчеркнутый
    • [s]перечеркнутый[/s] — перечеркнутый
    • [blink]мигающий[/blink] — мигающий
    • [color=red]цвет[/color] — цвет (подробнее)
    • [size=20]размер[/size] — размер (подробнее)
    • [code=<language>]some code[/code] (подробнее)
    Проверочный код