NPC LOGIC

/*
================
find_position

================
*/
bool find_position( float *start, float *end )
{
    size_t n, i, j;
    node_t tmp_node;
    float tmp_pos[ 3 ], end_pos[ 3 ];
    bool tmp_found;
    int id;

    bool found = false;

    int pw[ 4 ] = { -1, 1, 0, 0 };
    int ph[ 4 ] = { 0, 0, -1, 1 };

    // удаляем старые узлы
    if ( !nodes.empty() )
        reset_nodes();

    // добавляем первый узел
    VectorCopy( start, tmp_pos );
    tmp_pos[ 2 ] -= MAX_DIST_ROUTE;
    GetPositionBulletTrace( tmp_node.origin, start, tmp_pos );
    tmp_node.parent = -1;
    tmp_node.origin[ 2 ] += 20; // увеличиваем высоту узла, для предотвращения застреваний в текстуре
    nodes.push_back( tmp_node );

    // добавляем последний узел
    VectorCopy( end, end_pos );
    end_pos[ 2 ] -= MAX_DIST_ROUTE;
    GetPositionBulletTrace( end_pos, end, end_pos );
    end_pos[ 2 ] += 20;

    // сканируем местность вокруг первого узла
    for ( n = 0; ; n++ )
    {
        // для компилятора nodes.size() автоматически равен 1, исправлем это
        if ( n >= nodes.size() )
            break;

        if ( nodes.size() > MAX_NODES )
            break;

        // если уже нашли точку
        if ( found )
            break;

        // расширяем площадь узлов по всем 4 сторонам, учитывая подъемы/лестницы
        // [ С, Ю, З, В ]
        for ( i = 0; i < 4; i++ )
        {
            tmp_pos[ 0 ] = nodes[ n ].origin[ 0 ] + MIN_RANGE * pw[ i ];
            tmp_pos[ 1 ] = nodes[ n ].origin[ 1 ] + MIN_RANGE * ph[ i ];
            tmp_pos[ 2 ] = nodes[ n ].origin[ 2 ] + 40;

            if ( IsVisible( nodes[ n ].origin, tmp_pos ) )
            {
                VectorCopy( tmp_pos, tmp_node.origin );
                tmp_pos[ 2 ] -= MAX_DIST_ROUTE;

                GetPositionBulletTrace( tmp_pos, tmp_node.origin, tmp_pos );
                tmp_pos[ 2 ] += 10;

                if ( IsVisible( nodes[ n ].origin, tmp_pos ) )
                {
                    if ( tmp_pos[ 2 ] - nodes[ n ].origin[ 2 ] > 30 )
                        continue;

                    tmp_found = false;

                    // несколько узлов могут находится на одних и тех же координатах
                    // исключаем эту возможность
                    for ( j = 0; j < nodes.size(); j++ )
                    {
                        if ( GetDistance( nodes[ j ].origin, tmp_pos ) < 5 )
                        {
                            tmp_found = true;
                            break;
                        }
                    }

                    // если место свободное, то добавляем сюда узел
                    if ( !tmp_found )
                    {
                        VectorCopy( tmp_pos, tmp_node.origin );
                        tmp_node.parent = n; // записываем узел из которого стреляли лучи

                        nodes.push_back( tmp_node );

                        if ( IsVisible( tmp_pos, end_pos ) )
                        {
                            // мы нашли нужную координату, добавим ее и закончим искать
                            VectorCopy( tmp_pos, tmp_node.origin );
                            tmp_node.parent = nodes.size() - 1;
                            nodes.push_back( tmp_node );
                            found = true;
                        }
                    }
                }
            }
        }
    }

    if ( !found )
        return false;

    if ( !route.empty() )
    {
        for ( i = 0; i < route.size(); i++ )
        {
            route[ i ].arcs.clear();
            route[ i ].dists.clear();
        }

        route.clear();
    }

    // последний узел у нас является конечным
    // строим маршрут
    id = nodes.size() - 1;

    while ( nodes[ id ].parent != -1 )
    {
        route.push_back( nodes[ id ] );
        id = nodes[ id ].parent;
    }

    // удаляем другие точки, нет смысла их хранить
    reset_nodes();

    // разворачиваем маршрут в обратную сторону
    std::reverse( route.begin(), route.end() );

    if ( route.size() < 4 )
        return true;

    // фильтруем узлы, убираяя средние и оставляя крайние
    for ( i = 1; i < route.size() - 2; i++ ) // -2 чтобы не зайти за границы и не удалить последний узел
    {
        if ( IsVisible( route[ i - 1 ].origin, route[ i + 1 ].origin ) &&
            IsVisible( route[ i - 1 ].origin, route[ i ].origin ) &&
            IsVisible( route[ i ].origin, route[ i + 1 ].origin ) )
        {
            route.erase( route.begin() + i );
            i--;
        }
    }

    return true;
}