From 187abe3f5e2219e0a80c0cdca4db362e223b60ae Mon Sep 17 00:00:00 2001 From: Mattes D Date: Sun, 26 Feb 2017 22:49:23 +0100 Subject: Gen: Moved PiecePool into a separate file. Also rewritten the PieceGenerator to use std::unique_ptr. --- src/Generating/PieceGeneratorBFSTree.cpp | 345 +++++++++++++++++++++++++++++++ 1 file changed, 345 insertions(+) create mode 100644 src/Generating/PieceGeneratorBFSTree.cpp (limited to 'src/Generating/PieceGeneratorBFSTree.cpp') diff --git a/src/Generating/PieceGeneratorBFSTree.cpp b/src/Generating/PieceGeneratorBFSTree.cpp new file mode 100644 index 000000000..0078d53c9 --- /dev/null +++ b/src/Generating/PieceGeneratorBFSTree.cpp @@ -0,0 +1,345 @@ + +// PieceGeneratorBFSTree.cpp + +// Implements the cPieceGeneratorBFSTree class for generating structures composed of individual "pieces" in a simple tree +/* +The generator keeps a pool of currently-open connectors, chooses one at random and tries to place a piece on it, +thus possibly extending the pool of open connectors with the new piece's ones (like breadth-first search). +*/ + +#include "Globals.h" +#include "PieceGeneratorBFSTree.h" +#include "VerticalStrategy.h" +#include "VerticalLimit.h" + + + + + +//////////////////////////////////////////////////////////////////////////////// +// cPieceGeneratorBFSTree: + +cPieceGeneratorBFSTree::cPieceGeneratorBFSTree(cPiecePool & a_PiecePool, int a_Seed): + m_PiecePool(a_PiecePool), + m_Noise(a_Seed), + m_Seed(a_Seed) +{ +} + + + + + +cPlacedPiecePtr cPieceGeneratorBFSTree::PlaceStartingPiece(int a_BlockX, int a_BlockZ, cFreeConnectors & a_OutConnectors) +{ + m_PiecePool.Reset(); + int rnd = m_Noise.IntNoise2DInt(a_BlockX, a_BlockZ) / 7; + + // Choose a random one of the starting pieces: + cPieces StartingPieces = m_PiecePool.GetStartingPieces(); + int Total = 0; + for (cPieces::const_iterator itr = StartingPieces.begin(), end = StartingPieces.end(); itr != end; ++itr) + { + Total += m_PiecePool.GetStartingPieceWeight(**itr); + } + cPiece * StartingPiece; + if (Total > 0) + { + int Chosen = rnd % Total; + StartingPiece = StartingPieces.front(); + for (cPieces::const_iterator itr = StartingPieces.begin(), end = StartingPieces.end(); itr != end; ++itr) + { + Chosen -= m_PiecePool.GetStartingPieceWeight(**itr); + if (Chosen <= 0) + { + StartingPiece = *itr; + break; + } + } + } + else + { + // All pieces returned zero weight, but we need one to start. Choose with equal chance: + StartingPiece = StartingPieces[static_cast(rnd) % StartingPieces.size()]; + } + rnd = rnd >> 16; + + // Choose a random supported rotation: + int Rotations[4] = {0}; + int NumRotations = 1; + for (size_t i = 1; i < ARRAYCOUNT(Rotations); i++) + { + if (StartingPiece->CanRotateCCW(static_cast(i))) + { + Rotations[NumRotations] = static_cast(i); + NumRotations += 1; + } + } + int Rotation = Rotations[rnd % NumRotations]; + int BlockY = StartingPiece->GetStartingPieceHeight(a_BlockX, a_BlockZ); + ASSERT(BlockY >= 0); // The vertical strategy should have been provided and should give valid coords + + cPlacedPiece * res = new cPlacedPiece(nullptr, *StartingPiece, Vector3i(a_BlockX, BlockY, a_BlockZ), Rotation); + + // Place the piece's connectors into a_OutConnectors: + const cPiece::cConnectors & Conn = StartingPiece->GetConnectors(); + for (cPiece::cConnectors::const_iterator itr = Conn.begin(), end = Conn.end(); itr != end; ++itr) + { + a_OutConnectors.push_back( + cFreeConnector(res, StartingPiece->RotateMoveConnector(*itr, Rotation, a_BlockX, BlockY, a_BlockZ)) + ); + } + + return cPlacedPiecePtr(res); +} + + + + + +bool cPieceGeneratorBFSTree::TryPlacePieceAtConnector( + const cPlacedPiece & a_ParentPiece, + const cPiece::cConnector & a_Connector, + cPlacedPieces & a_OutPieces, + cPieceGeneratorBFSTree::cFreeConnectors & a_OutConnectors +) +{ + // Get a list of available connections: + cConnections Connections; + int WantedConnectorType = -a_Connector.m_Type; + cPieces AvailablePieces = m_PiecePool.GetPiecesWithConnector(WantedConnectorType); + Connections.reserve(AvailablePieces.size()); + Vector3i ConnPos = cPiece::cConnector::AddDirection(a_Connector.m_Pos, a_Connector.m_Direction); // The position at which the new connector should be placed - 1 block away from the current connector + int WeightTotal = 0; + for (cPieces::iterator itrP = AvailablePieces.begin(), endP = AvailablePieces.end(); itrP != endP; ++itrP) + { + // Get the relative chance of this piece being generated in this path: + int Weight = m_PiecePool.GetPieceWeight(a_ParentPiece, a_Connector, **itrP); + if (Weight <= 0) + { + continue; + } + + // Try fitting each of the piece's connector: + cPiece::cConnectors Connectors = (*itrP)->GetConnectors(); + auto verticalLimit = (*itrP)->GetVerticalLimit(); + for (cPiece::cConnectors::iterator itrC = Connectors.begin(), endC = Connectors.end(); itrC != endC; ++itrC) + { + if (itrC->m_Type != WantedConnectorType) + { + continue; + } + // This is a same-type connector, find out how to rotate to it: + int NumCCWRotations = cPiece::cConnector::GetNumCCWRotationsToFit(a_Connector.m_Direction, itrC->m_Direction); + if ((NumCCWRotations < 0) || !(*itrP)->CanRotateCCW(NumCCWRotations)) + { + // Doesn't support this rotation + continue; + } + + // Check if the piece's VerticalLimit allows this connection: + if ((verticalLimit != nullptr) && (!verticalLimit->CanBeAtHeight(ConnPos.x, ConnPos.z, ConnPos.y - itrC->m_Pos.y))) + { + continue; + } + + if (!CheckConnection(a_Connector, ConnPos, **itrP, *itrC, NumCCWRotations, a_OutPieces)) + { + // Doesn't fit in this rotation + continue; + } + // Fits, add it to list of possibile connections: + Connections.push_back(cConnection(**itrP, *itrC, NumCCWRotations, Weight)); + WeightTotal += Weight; + } // for itrC - Connectors[] + } // for itrP - AvailablePieces[] + if (Connections.empty()) + { + // No available connections, bail out + return false; + } + ASSERT(WeightTotal > 0); + + // Choose a random connection from the list, based on the weights: + int rnd = (m_Noise.IntNoise3DInt(a_Connector.m_Pos.x, a_Connector.m_Pos.y, a_Connector.m_Pos.z) / 7) % WeightTotal; + size_t ChosenIndex = 0; + for (cConnections::const_iterator itr = Connections.begin(), end = Connections.end(); itr != end; ++itr, ++ChosenIndex) + { + rnd -= itr->m_Weight; + if (rnd <= 0) + { + // This is the piece to choose + break; + } + } + cConnection & Conn = Connections[ChosenIndex]; + + // Place the piece: + Vector3i NewPos = Conn.m_Piece->RotatePos(Conn.m_Connector.m_Pos, Conn.m_NumCCWRotations); + ConnPos -= NewPos; + auto PlacedPiece = cpp14::make_unique(&a_ParentPiece, *(Conn.m_Piece), ConnPos, Conn.m_NumCCWRotations); + + // Add the new piece's connectors to the list of free connectors: + cPiece::cConnectors Connectors = Conn.m_Piece->GetConnectors(); + for (cPiece::cConnectors::const_iterator itr = Connectors.begin(), end = Connectors.end(); itr != end; ++itr) + { + if (itr->m_Pos.Equals(Conn.m_Connector.m_Pos)) + { + // This is the connector through which we have been connected to the parent, don't add + continue; + } + a_OutConnectors.push_back(cFreeConnector(PlacedPiece.get(), Conn.m_Piece->RotateMoveConnector(*itr, Conn.m_NumCCWRotations, ConnPos.x, ConnPos.y, ConnPos.z))); + } + a_OutPieces.push_back(std::move(PlacedPiece)); + + return true; +} + + + + + +bool cPieceGeneratorBFSTree::CheckConnection( + const cPiece::cConnector & a_ExistingConnector, + const Vector3i & a_ToPos, + const cPiece & a_Piece, + const cPiece::cConnector & a_NewConnector, + int a_NumCCWRotations, + const cPlacedPieces & a_OutPieces +) +{ + // For each placed piece, test the hitbox against the new piece: + cCuboid RotatedHitBox = a_Piece.RotateHitBoxToConnector(a_NewConnector, a_ToPos, a_NumCCWRotations); + RotatedHitBox.Sort(); + for (cPlacedPieces::const_iterator itr = a_OutPieces.begin(), end = a_OutPieces.end(); itr != end; ++itr) + { + if ((*itr)->GetHitBox().DoesIntersect(RotatedHitBox)) + { + return false; + } + } + return true; +} + + + + + +void cPieceGeneratorBFSTree::PlacePieces(int a_BlockX, int a_BlockZ, int a_MaxDepth, cPlacedPieces & a_OutPieces) +{ + a_OutPieces.clear(); + cFreeConnectors ConnectorPool; + + // Place the starting piece: + a_OutPieces.push_back(PlaceStartingPiece(a_BlockX, a_BlockZ, ConnectorPool)); + + /* + // DEBUG: + printf("Placed the starting piece at {%d, %d, %d}\n", a_BlockX, a_BlockY, a_BlockZ); + cCuboid Hitbox = a_OutPieces[0]->GetHitBox(); + Hitbox.Sort(); + printf(" Hitbox: {%d, %d, %d} - {%d, %d, %d} (%d * %d * %d)\n", + Hitbox.p1.x, Hitbox.p1.y, Hitbox.p1.z, + Hitbox.p2.x, Hitbox.p2.y, Hitbox.p2.z, + Hitbox.DifX() + 1, Hitbox.DifY() + 1, Hitbox.DifZ() + 1 + ); + DebugConnectorPool(ConnectorPool, 0); + //*/ + + // Place pieces at the available connectors: + /* + Instead of removing them one by one from the pool, we process them sequentially and take note of the last + processed one. To save on memory, once the number of processed connectors reaches a big number, a chunk + of the connectors is removed. + */ + size_t NumProcessed = 0; + while (ConnectorPool.size() > NumProcessed) + { + cFreeConnector & Conn = ConnectorPool[NumProcessed]; + if (Conn.m_Piece->GetDepth() < a_MaxDepth) + { + if (TryPlacePieceAtConnector(*Conn.m_Piece, Conn.m_Connector, a_OutPieces, ConnectorPool)) + { + /* + // DEBUG: + const cPlacedPiece * NewPiece = a_OutPieces.back(); + const Vector3i & Coords = NewPiece->GetCoords(); + printf("Placed a new piece at {%d, %d, %d}, rotation %d\n", Coords.x, Coords.y, Coords.z, NewPiece->GetNumCCWRotations()); + cCuboid Hitbox = NewPiece->GetHitBox(); + Hitbox.Sort(); + printf(" Hitbox: {%d, %d, %d} - {%d, %d, %d} (%d * %d * %d)\n", + Hitbox.p1.x, Hitbox.p1.y, Hitbox.p1.z, + Hitbox.p2.x, Hitbox.p2.y, Hitbox.p2.z, + Hitbox.DifX() + 1, Hitbox.DifY() + 1, Hitbox.DifZ() + 1 + ); + DebugConnectorPool(ConnectorPool, NumProcessed + 1); + //*/ + } + } + NumProcessed++; + if (NumProcessed > 1000) + { + typedef cPieceGeneratorBFSTree::cFreeConnectors::difference_type difType; + ConnectorPool.erase(ConnectorPool.begin(), ConnectorPool.begin() + static_cast(NumProcessed)); + NumProcessed = 0; + } + } +} + + + + + +//* +// DEBUG: +void cPieceGeneratorBFSTree::DebugConnectorPool(const cPieceGeneratorBFSTree::cFreeConnectors & a_ConnectorPool, size_t a_NumProcessed) +{ + printf(" Connector pool: " SIZE_T_FMT " items\n", a_ConnectorPool.size() - a_NumProcessed); + size_t idx = 0; + + typedef cPieceGeneratorBFSTree::cFreeConnectors::difference_type difType; + + for (auto itr = a_ConnectorPool.cbegin() + static_cast(a_NumProcessed), end = a_ConnectorPool.cend(); itr != end; ++itr, ++idx) + { + printf(" " SIZE_T_FMT ": {%d, %d, %d}, type %d, direction %s, depth %d\n", + idx, + itr->m_Connector.m_Pos.x, itr->m_Connector.m_Pos.y, itr->m_Connector.m_Pos.z, + itr->m_Connector.m_Type, + cPiece::cConnector::DirectionToString(itr->m_Connector.m_Direction), + itr->m_Piece->GetDepth() + ); + } // for itr - a_ConnectorPool[] +} +//*/ + + + + + +//////////////////////////////////////////////////////////////////////////////// +// cPieceGeneratorBFSTree::cConnection: + +cPieceGeneratorBFSTree::cConnection::cConnection(cPiece & a_Piece, cPiece::cConnector & a_Connector, int a_NumCCWRotations, int a_Weight) : + m_Piece(&a_Piece), + m_Connector(a_Connector), + m_NumCCWRotations(a_NumCCWRotations), + m_Weight(a_Weight) +{ +} + + + + + +//////////////////////////////////////////////////////////////////////////////// +// cPieceGeneratorBFSTree::cFreeConnector: + +cPieceGeneratorBFSTree::cFreeConnector::cFreeConnector(cPlacedPiece * a_Piece, const cPiece::cConnector & a_Connector) : + m_Piece(a_Piece), + m_Connector(a_Connector) +{ +} + + + + -- cgit v1.2.3