summaryrefslogtreecommitdiffstats
path: root/src/Generating/PieceGeneratorBFSTree.cpp
diff options
context:
space:
mode:
authorMattes D <github@xoft.cz>2017-02-26 22:49:23 +0100
committerMattes D <github@xoft.cz>2017-05-04 09:49:30 +0200
commit187abe3f5e2219e0a80c0cdca4db362e223b60ae (patch)
treeb68eac26b892fa469ec5753d34d4fa8a35a53bd3 /src/Generating/PieceGeneratorBFSTree.cpp
parentAPIDoc: Removed non-existent functions and added missing return types (diff)
downloadcuberite-187abe3f5e2219e0a80c0cdca4db362e223b60ae.tar
cuberite-187abe3f5e2219e0a80c0cdca4db362e223b60ae.tar.gz
cuberite-187abe3f5e2219e0a80c0cdca4db362e223b60ae.tar.bz2
cuberite-187abe3f5e2219e0a80c0cdca4db362e223b60ae.tar.lz
cuberite-187abe3f5e2219e0a80c0cdca4db362e223b60ae.tar.xz
cuberite-187abe3f5e2219e0a80c0cdca4db362e223b60ae.tar.zst
cuberite-187abe3f5e2219e0a80c0cdca4db362e223b60ae.zip
Diffstat (limited to 'src/Generating/PieceGeneratorBFSTree.cpp')
-rw-r--r--src/Generating/PieceGeneratorBFSTree.cpp345
1 files changed, 345 insertions, 0 deletions
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<size_t>(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<int>(i)))
+ {
+ Rotations[NumRotations] = static_cast<int>(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<cPlacedPiece>(&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<difType>(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<difType>(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)
+{
+}
+
+
+
+