dynamicnavrastercell.h

Go to the documentation of this file.

/*
* Copyright 2016 Autodesk, Inc. All rights reserved.
* Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
* or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
*/

#pragma once

#include "gwnavruntime/navmesh/navmeshtypes.h"
#include "gwnavgeneration/navraster/navrastertypes.h"

#include "gwnavgeneration/common/growinglistpool.h"
#include "gwnavgeneration/common/growingsmallbuffer.h"
#include "gwnavgeneration/raster/dynamicrastercell.h"
#include "gwnavgeneration/navraster/navrastercell.h"
#include "gwnavruntime/navmesh/celldesc.h"
#include "gwnavruntime/base/timeprofiler.h"
#include "gwnavgeneration/navraster/navrastercellscanlinepainter.h"

namespace Kaim
{

class GeneratorSystem;

class NavRasterWorkingPixel;

// used in NavRasterWorkingPixel and NavRasterPixelNeighborhood
class NavRasterNeighbor
{
public:
    NavRasterNeighbor() { Clear(); }

    void Clear()
    {
        m_neighborFloorIndex = NavRasterFloorIdx_Invalid;
        m_neighborType       = NavRasterNeighborType_CONNECT;
        m_neighborPtr        = nullptr;
    }

public:
    NavRasterFloorIdx      m_neighborFloorIndex;
    NavRasterNeighborType  m_neighborType;
    NavRasterWorkingPixel* m_neighborPtr;
};

// Dynamic version (non blob) of NavRasterPixel
class NavRasterWorkingPixel
{
    KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
public:
    NavRasterWorkingPixel() { Clear(); }
    void Clear();

    // remove the pointer to the neighbor pixel and make sure we update
    // the symmetric neighbor connections as well.
    void DisconnectFromNeighbors();

    void TagNeighborsFeatureMask(NavRasterFeatureMask feature);

    NavRasterWorkingPixel* GetNeighborPixel(CardinalDir dir) const { return m_neighbors[dir].m_neighborPtr;    }
    NavRasterNeighborType GetNeighborType(CardinalDir dir)   const { return m_neighbors[dir].m_neighborType; }

    void SetNeighborPixel(CardinalDir dir, NavRasterWorkingPixel* neighborPtr) { m_neighbors[dir].m_neighborPtr  = neighborPtr; }
    void SetNeighborType(CardinalDir dir, NavRasterNeighborType neighborType)  { m_neighbors[dir].m_neighborType = neighborType; }

    bool HasAtLeastOneValidNeighborLink() const;

    bool IsWalkable() const { return m_navTagIdx != NavTagIdx_Invalid; }

public:
    KyFloat32 m_altitude;
    KyUInt32 m_wallDist;
    KyUInt32 m_holeDist;
    NavRasterFloorIdx m_floorIdx;
    KyUInt32 m_navTagIdx;
    KyUInt32 m_featureBitField;

    // connections are indexed as follow:
    //  +-----------+
    //  |     1     |
    //  |           |
    //  |2    +    0|
    //  |           |
    //  |     3     |
    //  +-----------+

    // 0 corresponds to East (+1;0) and index increases CCW
    // Stores index of neighbor position if reachable, 0xFFFFFFFF otherwise
    NavRasterNeighbor m_neighbors[4];
};

// Working: Contains non-walkable pixels
class DynamicNavRasterWorkingColumn
{
public:
    DynamicNavRasterWorkingColumn() : m_floorCount(0), m_pixels(nullptr), m_hasNonWalkablePixels(false) {}

    void Init(KyUInt32 floorCount, NavRasterWorkingPixel* pixels)
    {
        m_floorCount = floorCount;
        m_pixels     = pixels;
    }

    void SetHasNonWalkablePixels(bool hasNonWalkablePixels) { m_hasNonWalkablePixels = hasNonWalkablePixels; }
    bool GetHasNonWalkablePixels() const { return m_hasNonWalkablePixels; }

    KyUInt32 GetFloorCount() const { return m_floorCount; }

    NavRasterWorkingPixel&       GetPixelAtFloor(KyUInt32 index)       { KY_ASSERT(index < m_floorCount); return m_pixels[index]; }
    const NavRasterWorkingPixel& GetPixelAtFloor(KyUInt32 index) const { KY_ASSERT(index < m_floorCount); return m_pixels[index]; }

private:
    KyUInt32 m_floorCount;
    NavRasterWorkingPixel* m_pixels;
    bool m_hasNonWalkablePixels;
};

// Final: Does not contain any non-walkable pixels
class DynamicNavRasterFinalColumn
{
public:
    DynamicNavRasterFinalColumn() : m_floorCount(0), m_pixels(nullptr) {}
    const NavRasterPixel& GetPixel(KyUInt32 index) const { KY_ASSERT(index < m_floorCount); return m_pixels[index]; }
    NavRasterPixel& GetPixel(KyUInt32 index)             { KY_ASSERT(index < m_floorCount); return m_pixels[index]; }

    bool HasPixelColor(PixelColor color, KyUInt32 ignored) const
    {
        for (KyUInt32 i = 0; i < m_floorCount; ++i)
        {
            if (i != ignored && m_pixels[i].m_floorColor == color)
                return true;
        }
        return false;
    }

    bool HasPixelColor(PixelColor color, KyUInt32 ignored1, KyUInt32 ignored2) const
    {
        for (KyUInt32 i = 0; i < m_floorCount; ++i)
        {
            if (i != ignored1 && i != ignored2 && m_pixels[i].m_floorColor == color)
                return true;
        }
        return false;
    }

    bool HasPropagationId(KyUInt32 propagationId, KyUInt32 ignored) const
    {
        for (KyUInt32 i = 0; i < m_floorCount; ++i)
        {
            if (i != ignored && m_pixels[i].m_propagationId == propagationId)
                return true;
        }
        return false;
    }

    bool HasPropagationId(PixelColor color, KyUInt32 ignored1, KyUInt32 ignored2) const
    {
        for (KyUInt32 i = 0; i < m_floorCount; ++i)
        {
            if (i != ignored1 && i != ignored2 && m_pixels[i].m_propagationId == color)
                return true;
        }
        return false;
    }


    KyUInt32 m_floorCount;
    NavRasterPixel* m_pixels;
};


class DynamicNavRasterCell
{
    KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
public:
    DynamicNavRasterCell(GeneratorSystem* sys, const DynamicRasterCell* inputRasterCell, const CellDesc& cellDesc, KyArrayTLS_POD<KyUInt32>* connexIdxToNavTagIdxArray);
    ~DynamicNavRasterCell() {}

    void CreateNavRaster();

    DynamicNavRasterFinalColumn GetFinalColumnFromLocalPixelPos(const PixelPos& localPixelPos) const
    {
        const KyInt32 idx = m_navPixelBox.GetRowMajorIndexFromLocalPos(localPixelPos);
        return m_finalColumns[idx];
    }

    DynamicNavRasterFinalColumn GetFinalColumn(const PixelPos& pixelPos) const
    {
        const KyInt32 idx = m_navPixelBox.GetRowMajorIndex(pixelPos);
        return m_finalColumns[idx];
    }

    // Write NavRaster file file if specified in the Generator RunOptions, for debug purpose.
    KyResult WriteIntermediateNavRasterFile();

    bool IsEmpty() const { return m_isEmpty; }
    bool HasMultipleNavTags() const { return m_hasMultipleNavTags; }

    DynamicNavRasterWorkingColumn* GetWorkingNeighborColumn(const PixelPos& pos, CardinalDir dir);

    NavRasterWorkingPixel* GetWorkingNeighborPixel(const NavRasterWorkingPixel& pixel, NavRasterCardinalDir dir) const;

private:
    void CreateUnpaintNavRaster();
    void InitFromInputRasterCell();
    void RemoveIsolatedNonWalkablePixels();
    void ComputeConnectedNeighbors();
    void EnforceSymetry();
    void EnforcePixelSymetry(NavRasterWorkingPixel* pixel, CardinalDir dir);
    void ComputeDistanceMap();
    void ErodePixels();

    void MakeFinalColumns();

    void ComputeManhattanDistanceMap();
    void InitBorderPixelDistance();
    void UpdateManhattanDistForPixelsOnDir(const PixelPos& posInRaster, CardinalDir dir1, CardinalDir dir2);
    void UpdateChessBoardDistForPixelsOnDir(const PixelPos& posInRaster, const NavRasterCardinalDir* navRasterDirs);

    void ComputeChessboardDistanceMap();

    void ReleaseWorkingColumns();

    NavRasterWorkingPixel* GetWorkingDiagonalNeighbor(const NavRasterWorkingPixel& pixel, NavRasterCardinalDir dir) const;
    NavRasterWorkingPixel* GetWorkingDiagonalNeighbor(const NavRasterWorkingPixel& pixel, CardinalDir dir1, CardinalDir dir2) const;

public:
    GeneratorSystem* m_sys;
    CellDesc m_cellDesc;
    KyUInt32 m_highestFloorCount;

public:
    const DynamicRasterCell* m_rasterCell;

    PixelBox m_enlargedPixelBox;
    PixelBox m_navPixelBox;

    NavRasterCellScanlinePainter m_painter;

    // final columns
    KyArrayTLS<DynamicNavRasterFinalColumn> m_finalColumns;
    GrowingSmallBufferPool m_finalColumnsPool;

    KyArrayTLS<DynamicNavRasterWorkingColumn> m_workingColumns;
    GrowingSmallBufferPool m_workingColumnsPool;

    bool m_isEmpty;
    bool m_hasMultipleNavTags; // extracted from the rasterCell
    bool m_hasNonWalkablePixels;

    KyFloat32* m_navRasterMs; // profiling
    KyFloat32* m_paintingMs;  // profiling

    friend class DynamicNavRasterCellBlobBuilder;
};


KY_INLINE NavRasterWorkingPixel* DynamicNavRasterCell::GetWorkingNeighborPixel(const NavRasterWorkingPixel& pixel, NavRasterCardinalDir dir) const
{
    return dir < 4 ? pixel.GetNeighborPixel(dir) : GetWorkingDiagonalNeighbor(pixel, dir);
}

KY_INLINE NavRasterWorkingPixel* DynamicNavRasterCell::GetWorkingDiagonalNeighbor(const NavRasterWorkingPixel& pos, NavRasterCardinalDir dir) const
{
    KY_ASSERT(dir >= 4 && dir < 8);

    switch(dir)
    {
    case NavRasterCardinalDir_NORTH_EAST:
        return GetWorkingDiagonalNeighbor(pos, CardinalDir_NORTH, CardinalDir_EAST);
    case NavRasterCardinalDir_NORTH_WEST:
        return GetWorkingDiagonalNeighbor(pos, CardinalDir_NORTH, CardinalDir_WEST);
    case NavRasterCardinalDir_SOUTH_WEST:
        return GetWorkingDiagonalNeighbor(pos, CardinalDir_SOUTH, CardinalDir_WEST);
    case NavRasterCardinalDir_SOUTH_EAST:
        return GetWorkingDiagonalNeighbor(pos, CardinalDir_SOUTH, CardinalDir_EAST);
    default: return nullptr;
    }
}

KY_INLINE void DynamicNavRasterCell::ReleaseWorkingColumns()
{
    m_workingColumns.ClearAndRelease();
    m_workingColumnsPool.Release();
}

}