Differential D14 Diff 7228 source/simulation2/components/CCmpPathfinder_Common.h

Changeset View

Standalone View

source/simulation2/components/CCmpPathfinder_Common.h

* This file is part of 0 A.D. * This file is part of 0 A.D.

* *

* 0 A.D. is free software: you can redistribute it and/or modify * 0 A.D. is free software: you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by * it under the terms of the GNU General Public License as published by

* the Free Software Foundation, either version 2 of the License, or * the Free Software Foundation, either version 2 of the License, or

* (at your option) any later version. * (at your option) any later version.

* *

* 0 A.D. is distributed in the hope that it will be useful, * 0 A.D. is distributed in the hope that it will be useful,

Show All 20 Lines

#include "simulation2/system/Component.h" #include "simulation2/system/Component.h"

#include "ICmpPathfinder.h" #include "ICmpPathfinder.h"

#include "graphics/Overlay.h" #include "graphics/Overlay.h"

#include "graphics/Terrain.h" #include "graphics/Terrain.h"

#include "maths/MathUtil.h" #include "maths/MathUtil.h"

#include "ps/CLogger.h" #include "ps/CLogger.h"

#include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/components/ICmpObstructionManager.h"

#include "simulation2/helpers/LongPathfinder.h" #include "simulation2/helpers/LongPathfinder.h"

StanUnsubmitted

Not Done

#include "simulation2/helpers/Grid.h"

+ #include <atomic>

#include <vector>

class HierarchicalPathfinder;

Stan:

#include <thread>

#include <mutex>

#include <condition_variable>

class SceneCollector; class SceneCollector;

class AtlasOverlay; class AtlasOverlay;

#ifdef NDEBUG #ifdef NDEBUG

#define PATHFIND_DEBUG 0 #define PATHFIND_DEBUG 0

#else #else

#define PATHFIND_DEBUG 1 #define PATHFIND_DEBUG 1

#endif #endif

struct AsyncLongPathRequest struct AsyncLongPathRequest

{ {

u32 ticket; u32 ticket;

entity_pos_t x0; entity_pos_t x0;

entity_pos_t z0; entity_pos_t z0;

PathGoal goal; PathGoal goal;

pass_class_t passClass; pass_class_t passClass;

entity_id_t notify; entity_id_t notify;

}; };

struct AsyncShortPathRequest struct AsyncShortPathRequest

{ {

StanUnsubmitted

Not Done

Doxygen ?

Stan: Doxygen ?

u32 ticket; u32 ticket;

entity_pos_t x0; entity_pos_t x0;

entity_pos_t z0; entity_pos_t z0;

entity_pos_t clearance; entity_pos_t clearance;

entity_pos_t range; entity_pos_t range;

PathGoal goal; PathGoal goal;

pass_class_t passClass; pass_class_t passClass;

bool avoidMovingUnits; bool avoidMovingUnits;

StanUnsubmitted

Not Done

Doxygen ?

Stan: Doxygen ?

entity_id_t group; entity_id_t group;

entity_id_t notify; entity_id_t notify;

}; };

// A vertex around the corners of an obstruction // A vertex around the corners of an obstruction

StanUnsubmitted

Not Done

Doxygen ?

Stan: Doxygen ?

StanUnsubmitted

Not Done

Doxygen ?

Stan: Doxygen ?

// (paths will be sequences of these vertexes) // (paths will be sequences of these vertexes)

struct Vertex struct Vertex

{ {

enum enum

{ {

UNEXPLORED, UNEXPLORED,

OPEN, OPEN,

CLOSED, CLOSED,

}; };

CFixedVector2D p; CFixedVector2D p;

StanUnsubmitted

Not Done

Doxygen ?

Stan: Doxygen ?

fixed g, h; fixed g, h;

u16 pred; u16 pred;

u8 status; u8 status;

u8 quadInward : 4; // the quadrant which is inside the shape (or NONE) u8 quadInward : 4; // the quadrant which is inside the shape (or NONE)

u8 quadOutward : 4; // the quadrants of the next point on the path which this vertex must be in, given 'pred' u8 quadOutward : 4; // the quadrants of the next point on the path which this vertex must be in, given 'pred'

}; };

// Obstruction edges (paths will not cross any of these). // Obstruction edges (paths will not cross any of these).

// Defines the two points of the edge. // Defines the two points of the edge.

struct Edge struct Edge

{ {

CFixedVector2D p0, p1; CFixedVector2D p0, p1;

}; };

// Axis-aligned obstruction squares (paths will not cross any of these). // Axis-aligned obstruction squares (paths will not cross any of these).

StanUnsubmitted

Not Done

Probably needs

#include <vector>

(likely included in its deps)

Stan: Probably needs ``` #include <vector> ``` (likely included in its deps)

// Defines the opposing corners of an axis-aligned square // Defines the opposing corners of an axis-aligned square

// (from which four individual edges can be trivially computed), requiring p0 <= p1 // (from which four individual edges can be trivially computed), requiring p0 <= p1

vladislavbelovUnsubmitted

Not Done

Why do you need std::atomic if it's private?

vladislavbelov: Why do you need `std::atomic` if it's private?

wraitiiAuthorUnsubmitted

Done

It's still called from 2 threads, as the main thread calls PrepareToKill(), which sets m_Kill = true, and it's checked for in the worker thread.

wraitii: It's still called from 2 threads, as the main thread calls PrepareToKill(), which sets m_Kill =…

StanUnsubmitted

Not Done

#include <atomic>

Stan: ``` #include <atomic> ```

struct Square struct Square

{ {

StanUnsubmitted

Not Done

#include <memory>

Stan: ``` #include <memory> ```

CFixedVector2D p0, p1; CFixedVector2D p0, p1;

}; };

// Axis-aligned obstruction edges. // Axis-aligned obstruction edges.

// p0 defines one end; c1 is either the X or Y coordinate of the other end, // p0 defines one end; c1 is either the X or Y coordinate of the other end,

// depending on the context in which this is used. // depending on the context in which this is used.

struct EdgeAA struct EdgeAA

{ {

CFixedVector2D p0; CFixedVector2D p0;

fixed c1; fixed c1;

}; };

/** /**

* Implementation of ICmpPathfinder * Implementation of ICmpPathfinder

*/ */

class CCmpPathfinder : public ICmpPathfinder class CCmpPathfinder : public ICmpPathfinder

{ {

protected:

class AsyncPathfinderWorkerThread

{

friend CCmpPathfinder;

private:

vladislavbelovUnsubmitted

Done

Sections should be in order: public > protected > private.

vladislavbelov: Sections should be in order: public > protected > private.

// takes care of what needs to be called to initialise the thread before calling WaitForWork();

void InitThread(size_t index);

public:

AsyncPathfinderWorkerThread(const CCmpPathfinder& pathfinder);

~AsyncPathfinderWorkerThread();

void PrepareToKill();

// Will loop until a conditional_variable notifies us, and call Work().

vladislavbelovUnsubmitted

Done

Why comments states that the function uses conditional_variable but in fact it uses a simple busy waiting.

vladislavbelov: Why comments states that the function uses `conditional_variable` but in fact it uses a simple…

wraitiiAuthorUnsubmitted

Done

Earlier version of the code used a condition_variable, I've changed it since. The thing is I need a m_Computing predicate anyways for the condition-variable, and possibly a mutex (I had issues which look a bit like this).
Again, I probably need a std::this_thread::yield() here, but I think the busy-waiting on an atomic variable is simpler and safer.

wraitii: Earlier version of the code used a condition_variable, I've changed it since. The thing is I…

StanUnsubmitted

Done

Should or is ?

Stan: Should or is ?

wraitiiAuthorUnsubmitted

Done

Should. It also is, but it should be and remain so in the future.

wraitii: Should. It also is, but it should be and remain so in the future.

void WaitForWork();

// Process path requests, checking if we should stop before each new one. Sets m_Computing to false on return.

void Work();

/**

* Compute a tile-based path from the given point to the goal, and return the set of waypoints.

* The waypoints correspond to the centers of horizontally/vertically adjacent tiles

* along the path.

void

ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret)

{

m_Pathfinder.m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);

}

/**

* Compute a precise path from the given point to the goal, and return the set of waypoints.

* The path is based on the full set of obstructions that pass the filter, such that

* a unit of clearance 'clearance' will be able to follow the path with no collisions.

* The path is restricted to a box of radius 'range' from the starting point.

* Defined in CCmpPathfinder_Vertex.cpp

void

ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance,

entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret);

private:

* General state

// read-only pathfinder, for getting required information (grids,…)

const CCmpPathfinder& m_Pathfinder;

// store our results, the main thread will fetch this

std::vector<PathResult> m_Results;

std::thread* m_Thread = nullptr;

bool m_Kill = false;

* Thread synchronisation

bool m_Computing = false;

// using deque: for simplicity the worker thread will pop_back, the main thread will push_front

std::deque<AsyncLongPathRequest> m_LongRequests;

std::deque<AsyncShortPathRequest> m_ShortRequests;

// the main thread may push new requests even when we are computing existing ones, so lock.

std::mutex m_Pause;

vladislavbelovUnsubmitted

Not Done

It'd be good to fix names (to follow CC). Also as it'd be good to use "cache" word as the variables are used inside const methods.

vladislavbelov: It'd be good to fix names (to follow CC). Also as it'd be good to use "cache" word as the…

wraitiiAuthorUnsubmitted

Done

These were simply moved, and I think I'll refactor this in a VertexPathfinder class anyways that this calls (like the LongPathfinder) instead of what I've done here.

wraitii: These were simply moved, and I think I'll refactor this in a VertexPathfinder class anyways…

* Memory optimisations: avoid recreating these vectors

std::vector<Edge> edgesUnaligned;

std::vector<EdgeAA> edgesLeft;

std::vector<EdgeAA> edgesRight;

std::vector<EdgeAA> edgesBottom;

std::vector<EdgeAA> edgesTop;

// List of obstruction vertexes (plus start/end points); we'll try to find paths through

// the graph defined by these vertexes

std::vector<Vertex> vertexes;

// List of collision edges - paths must never cross these.

// (Edges are one-sided so intersections are fine in one direction, but not the other direction.)

std::vector<Edge> edges;

std::vector<Square> edgeSquares; // axis-aligned squares; equivalent to 4 edges};

};

// Allow the workers to access our private variables

friend class AsyncPathfinderWorkerThread;

public: public:

static void ClassInit(CComponentManager& componentManager) static void ClassInit(CComponentManager& componentManager)

{ {

componentManager.SubscribeToMessageType(MT_Update); componentManager.SubscribeToMessageType(MT_Update);

componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays

componentManager.SubscribeToMessageType(MT_TerrainChanged); componentManager.SubscribeToMessageType(MT_TerrainChanged);

componentManager.SubscribeToMessageType(MT_WaterChanged); componentManager.SubscribeToMessageType(MT_WaterChanged);

componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged); componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged);

componentManager.SubscribeToMessageType(MT_TurnStart); componentManager.SubscribeToMessageType(MT_TurnStart);

} }

DEFAULT_COMPONENT_ALLOCATOR(Pathfinder) DEFAULT_COMPONENT_ALLOCATOR(Pathfinder)

// Template state: // Template state:

std::map<std::string, pass_class_t> m_PassClassMasks; std::map<std::string, pass_class_t> m_PassClassMasks;

std::vector<PathfinderPassability> m_PassClasses; std::vector<PathfinderPassability> m_PassClasses;

// Dynamic state: // Dynamic state:

std::vector<AsyncLongPathRequest> m_AsyncLongPathRequests; std::vector<AsyncLongPathRequest> m_AsyncLongPathRequests;

std::vector<AsyncShortPathRequest> m_AsyncShortPathRequests; std::vector<AsyncShortPathRequest> m_AsyncShortPathRequests;

u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests

u16 m_SameTurnMovesCount; // current number of same turn moves we have processed this turn u16 m_MaxSameTurnMoves; // How many moves to immediately compute.

// Lazily-constructed dynamic state (not serialized): // Lazily-constructed dynamic state (not serialized):

u16 m_MapSize; // tiles per side u16 m_MapSize; // tiles per side

Grid<NavcellData>* m_Grid; // terrain/passability information Grid<NavcellData>* m_Grid; // terrain/passability information

Grid<NavcellData>* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations Grid<NavcellData>* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations

// Keep clever updates in memory to avoid memory fragmentation from the grid. // Keep clever updates in memory to avoid memory fragmentation from the grid.

// This should be used only in UpdateGrid(), there is no guarantee the data is properly initialized anywhere else. // This should be used only in UpdateGrid(), there is no guarantee the data is properly initialized anywhere else.

GridUpdateInformation m_DirtinessInformation; GridUpdateInformation m_DirtinessInformation;

// The data from clever updates is stored for the AI manager // The data from clever updates is stored for the AI manager

GridUpdateInformation m_AIPathfinderDirtinessInformation; GridUpdateInformation m_AIPathfinderDirtinessInformation;

bool m_TerrainDirty; bool m_TerrainDirty;

// Interface to the long-range pathfinder. // Interface to the long-range pathfinder.

StanUnsubmitted

Not Done

Stan: <atomic>

LongPathfinder m_LongPathfinder; mutable LongPathfinder m_LongPathfinder;

// For responsiveness we will process some moves in the same turn they were generated in

u16 m_MaxSameTurnMoves; // max number of moves that can be created and processed in the same turn

// memory optimizations: those vectors are created once, reused for all calculations;

std::vector<Edge> edgesUnaligned;

std::vector<EdgeAA> edgesLeft;

std::vector<EdgeAA> edgesRight;

std::vector<EdgeAA> edgesBottom;

std::vector<EdgeAA> edgesTop;

// List of obstruction vertexes (plus start/end points); we'll try to find paths through // we Process paths in an asynchronous way, making sure to do it at times where it is safe.

StanUnsubmitted

Done

Initialization in Init ?

Stan: Initialization in Init ?

wraitiiAuthorUnsubmitted

Done

I think it's better to init in the definition whenever possible going forward. Not sure if that's a convention we have or not?

wraitii: I think it's better to init in the definition whenever possible going forward. Not sure if…

StanUnsubmitted

Not Done

Process worker maybe ?

Stan: Process worker maybe ?

// the graph defined by these vertexes std::vector<AsyncPathfinderWorkerThread*> m_WorkerThreads;

StanUnsubmitted

Not Done

#include <mutex>

Stan: ``` #include <mutex> ```

std::vector<Vertex> vertexes; bool m_UseThreading = true;

StanUnsubmitted

Not Done

#include <condition_variable>

Stan: ``` #include <condition_variable> ```

// List of collision edges - paths must never cross these.

// (Edges are one-sided so intersections are fine in one direction, but not the other direction.) // this variable will be set by the main thread. When going from true to false,

std::vector<Edge> edges; // the threads will define their own m_Computing to false. The main thread must wait until

std::vector<Square> edgeSquares; // axis-aligned squares; equivalent to 4 edges // all threads' m_Computing are false to proceed.

wraitiiAuthorUnsubmitted

Done

Forgot to use that in this diff, but it'll be in the next.

wraitii: Forgot to use that in this diff, but it'll be in the next.

bool m_MayComputePaths = false;

// we use a condition variable to wake the pathfinder threads when relevant

mutable std::condition_variable m_MainThreadSignal;

mutable std::mutex m_MainThreadMutex;

// HACK: the pathfinder is threaded but we will want to debug, so use mutexes and mutable to modify this.

bool m_DebugOverlay; bool m_DebugOverlay;

std::vector<SOverlayLine> m_DebugOverlayShortPathLines; mutable std::vector<SOverlayLine> m_DebugOverlayShortPathLines;

mutable std::mutex m_DebugMutex;

AtlasOverlay* m_AtlasOverlay; AtlasOverlay* m_AtlasOverlay;

static std::string GetSchema() static std::string GetSchema()

{ {

return "<a:component type='system'/><empty/>"; return "<a:component type='system'/><empty/>";

} }

virtual void Init(const CParamNode& paramNode); virtual void Init(const CParamNode& paramNode);

▲ Show 20 Lines • Show All 47 Lines • ▼ Show 20 Lines public:

virtual void FlushAIPathfinderDirtinessInformation() virtual void FlushAIPathfinderDirtinessInformation()

{ {

m_AIPathfinderDirtinessInformation.Clean(); m_AIPathfinderDirtinessInformation.Clean();

} }

virtual Grid<u16> ComputeShoreGrid(bool expandOnWater = false); virtual Grid<u16> ComputeShoreGrid(bool expandOnWater = false);

virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) virtual bool MakeGoalReachable(entity_pos_t x0, entity_pos_t z0, PathGoal &goal, pass_class_t passClass);

{

m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);

}

virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify); virtual u32 FindNearestPassableNavcell(entity_pos_t x, entity_pos_t z, u16& outI, u16& outJ, pass_class_t passClass);

void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass);

virtual bool NavcellIsReachable(u16 i0, u16 j0, u16 i1, u16 j1, pass_class_t passClass);

virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret); virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify);

virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify); virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify);

virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const;

virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)

{ {

m_LongPathfinder.SetDebugPath(x0, z0, goal, passClass); m_LongPathfinder.SetDebugPath(x0, z0, goal, passClass);

} }

virtual void SetDebugOverlay(bool enabled) virtual void SetDebugOverlay(bool enabled)

{ {

m_DebugOverlay = enabled; m_DebugOverlay = enabled;

m_LongPathfinder.SetDebugOverlay(enabled); m_LongPathfinder.SetDebugOverlay(enabled);

} }

virtual void SetHierDebugOverlay(bool enabled) virtual void SetHierDebugOverlay(bool enabled)

{ {

m_LongPathfinder.SetHierDebugOverlay(enabled, &GetSimContext()); m_LongPathfinder.SetHierDebugOverlay(enabled, &GetSimContext());

} }

virtual void GetDebugData(u32& steps, double& time, Grid<u8>& grid) const virtual void GetDebugData(u32& steps, double& time, Grid<u8>& grid) const

{ {

m_LongPathfinder.GetDebugData(steps, time, grid); m_LongPathfinder.GetDebugData(steps, time, grid);

} }

virtual void SetAtlasOverlay(bool enable, pass_class_t passClass = 0); virtual void SetAtlasOverlay(bool enable, pass_class_t passClass = 0);

virtual bool CheckMovement(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, pass_class_t passClass) const; virtual bool CheckMovement(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1,

entity_pos_t z1, entity_pos_t r, pass_class_t passClass) const;

virtual ICmpObstruction::EFoundationCheck CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool onlyCenterPoint) const;

virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass) const;

CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool onlyCenterPoint) const;

virtual void FinishAsyncRequests(); virtual ICmpObstruction::EFoundationCheck

CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a,entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass) const;

void ProcessLongRequests(const std::vector<AsyncLongPathRequest>& longRequests); virtual ICmpObstruction::EFoundationCheck

CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass, bool onlyCenterPoint) const;

void ProcessShortRequests(const std::vector<AsyncShortPathRequest>& shortRequests); virtual void FetchAsyncResultsAndSendMessages();

virtual void ProcessSameTurnMoves(); virtual void StartProcessingMoves(bool useMax);

/** /**

* Regenerates the grid based on the current obstruction list, if necessary * Regenerates the grid based on the current obstruction list, if necessary

*/ */

virtual void UpdateGrid(); virtual void UpdateGrid();

/** /**

* Updates the terrain-only grid without updating the dirtiness informations. * Updates the terrain-only grid without updating the dirtiness informations.

Show All 25 Lines public:

{ {

// Render navcell passability, based on the terrain-only grid // Render navcell passability, based on the terrain-only grid

u8* p = data; u8* p = data;

for (size_t j = 0; j < h; ++j) for (size_t j = 0; j < h; ++j)

{ {

for (size_t i = 0; i < w; ++i) for (size_t i = 0; i < w; ++i)

{ {

SColor4ub color(0, 0, 0, 0); SColor4ub color(0, 0, 0, 0);

if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int)i, (int)j), m_PassClass)) if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get(static_cast<int>(i), static_cast<int>(j)), m_PassClass))

color = SColor4ub(255, 0, 0, 127); color = SColor4ub(255, 0, 0, 127);

*p++ = color.R; *p++ = color.R;

*p++ = color.G; *p++ = color.G;

*p++ = color.B; *p++ = color.B;

*p++ = color.A; *p++ = color.A;

} }

}; };

#endif // INCLUDED_CCMPPATHFINDER_COMMON #endif // INCLUDED_CCMPPATHFINDER_COMMON