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] (подробнее)
    Проверочный код