diff options
Diffstat (limited to '')
-rw-r--r-- | src/Generating/PieceGenerator.cpp | 585 | ||||
-rw-r--r-- | src/Generating/PieceGenerator.h | 238 |
2 files changed, 823 insertions, 0 deletions
diff --git a/src/Generating/PieceGenerator.cpp b/src/Generating/PieceGenerator.cpp new file mode 100644 index 000000000..58ccaf2c2 --- /dev/null +++ b/src/Generating/PieceGenerator.cpp @@ -0,0 +1,585 @@ + +// PieceGenerator.cpp + +// Implements the cBFSPieceGenerator class and cDFSPieceGenerator class +// representing base classes for generating structures composed of individual "pieces" + +#include "Globals.h" +#include "PieceGenerator.h" + + + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Self-test: + +static class cPieceGeneratorSelfTest : + public cPiecePool +{ +public: + cPieceGeneratorSelfTest(void) + { + // Prepare the internal state: + InitializePieces(); + + // Generate: + cBFSPieceGenerator Gen(*this, 0); + cPlacedPieces OutPieces; + Gen.PlacePieces(500, 50, 500, 3, OutPieces); + + // Print out the pieces: + printf("OutPieces.size() = %u\n", OutPieces.size()); + size_t idx = 0; + for (cPlacedPieces::const_iterator itr = OutPieces.begin(), end = OutPieces.end(); itr != end; ++itr, ++idx) + { + const Vector3i & Coords = (*itr)->GetCoords(); + cCuboid Hitbox = (*itr)->GetHitBox(); + Hitbox.Sort(); + printf("%u: {%d, %d, %d}, rot %d, hitbox {%d, %d, %d} - {%d, %d, %d} (%d * %d * %d)\n", idx, + Coords.x, Coords.y, Coords.z, + (*itr)->GetNumCCWRotations(), + 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 + ); + } // itr - OutPieces[] + printf("Done.\n"); + + // Free the placed pieces properly: + Gen.FreePieces(OutPieces); + } + + ~cPieceGeneratorSelfTest() + { + // Dealloc all the pieces: + for (cPieces::iterator itr = m_Pieces.begin(), end = m_Pieces.end(); itr != end; ++itr) + { + delete *itr; + } + m_Pieces.clear(); + } + +protected: + class cTestPiece : + public cPiece + { + int m_Size; + public: + cTestPiece(int a_Size) : + m_Size(a_Size) + { + } + + virtual cConnectors GetConnectors(void) const override + { + // Each piece has 4 connectors, one of each type, plus one extra, at the center of its walls: + cConnectors res; + res.push_back(cConnector(m_Size / 2, 1, 0, 0, BLOCK_FACE_ZM)); + res.push_back(cConnector(m_Size / 2, 1, m_Size - 1, 1, BLOCK_FACE_ZP)); + res.push_back(cConnector(0, 1, m_Size / 2, 2, BLOCK_FACE_XM)); + res.push_back(cConnector(m_Size - 1, 1, m_Size / 2, m_Size % 3, BLOCK_FACE_XP)); + return res; + } + + virtual Vector3i GetSize(void) const override + { + return Vector3i(m_Size, 5, m_Size); + } + + virtual cCuboid GetHitBox(void) const override + { + return cCuboid(0, 0, 0, m_Size - 1, 4, m_Size - 1); + } + + virtual bool CanRotateCCW(int a_NumCCWRotations) const override + { + return true; + } + }; + + cPieces m_Pieces; + + virtual cPieces GetPiecesWithConnector(int a_ConnectorType) override + { + // Each piece contains each connector + return m_Pieces; + } + + + virtual cPieces GetStartingPieces(void) override + { + return m_Pieces; + } + + + virtual void PiecePlaced(const cPiece & a_Piece) override + { + UNUSED(a_Piece); + } + + + virtual void Reset(void) override + { + } + + + void InitializePieces(void) + { + m_Pieces.push_back(new cTestPiece(5)); + m_Pieces.push_back(new cTestPiece(7)); + m_Pieces.push_back(new cTestPiece(9)); + } +} g_Test; + + + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// cPiece: + + +Vector3i cPiece::RotatePos(const Vector3i & a_Pos, int a_NumCCWRotations) const +{ + Vector3i Size = GetSize(); + switch (a_NumCCWRotations) + { + case 0: + { + // No rotation needed + return a_Pos; + } + case 1: + { + // 1 CCW rotation: + return Vector3i(a_Pos.z, a_Pos.y, Size.x - a_Pos.x - 1); + } + case 2: + { + // 2 rotations ( = axis flip): + return Vector3i(Size.x - a_Pos.x - 1, a_Pos.y, Size.z - a_Pos.z - 1); + } + case 3: + { + // 1 CW rotation: + return Vector3i(Size.z - a_Pos.z - 1, a_Pos.y, a_Pos.x); + } + } + ASSERT(!"Unhandled rotation"); + return a_Pos; +} + + + + + +cPiece::cConnector cPiece::RotateMoveConnector(const cConnector & a_Connector, int a_NumCCWRotations, int a_MoveX, int a_MoveY, int a_MoveZ) const +{ + cPiece::cConnector res(a_Connector); + + // Rotate the res connector: + Vector3i Size = GetSize(); + switch (a_NumCCWRotations) + { + case 0: + { + // No rotation needed + break; + } + case 1: + { + // 1 CCW rotation: + res.m_Direction = RotateBlockFaceCCW(res.m_Direction); + break; + } + case 2: + { + // 2 rotations ( = axis flip): + res.m_Direction = MirrorBlockFaceY(res.m_Direction); + break; + } + case 3: + { + // 1 CW rotation: + res.m_Direction = RotateBlockFaceCW(res.m_Direction); + break; + } + } + res.m_Pos = RotatePos(a_Connector.m_Pos, a_NumCCWRotations); + + // Move the res connector: + res.m_Pos.x += a_MoveX; + res.m_Pos.y += a_MoveY; + res.m_Pos.z += a_MoveZ; + + return res; +} + + + + + +cCuboid cPiece::RotateHitBoxToConnector( + const cPiece::cConnector & a_MyConnector, + const Vector3i & a_ToConnectorPos, + int a_NumCCWRotations +) const +{ + ASSERT(a_NumCCWRotations == (a_NumCCWRotations % 4)); + Vector3i ConnPos = RotatePos(a_MyConnector.m_Pos, a_NumCCWRotations); + ConnPos = a_ToConnectorPos - ConnPos; + return RotateMoveHitBox(a_NumCCWRotations, ConnPos.x, ConnPos.y, ConnPos.z); +} + + + + + +cCuboid cPiece::RotateMoveHitBox(int a_NumCCWRotations, int a_MoveX, int a_MoveY, int a_MoveZ) const +{ + ASSERT(a_NumCCWRotations == (a_NumCCWRotations % 4)); + cCuboid res = GetHitBox(); + res.p1 = RotatePos(res.p1, a_NumCCWRotations); + res.p2 = RotatePos(res.p2, a_NumCCWRotations); + res.p1.Move(a_MoveX, a_MoveY, a_MoveZ); + res.p2.Move(a_MoveX, a_MoveY, a_MoveZ); + return res; +} + + + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// cPiece::cConnector: + +cPiece::cConnector::cConnector(int a_X, int a_Y, int a_Z, int a_Type, eBlockFace a_Direction) : + m_Pos(a_X, a_Y, a_Z), + m_Type(a_Type), + m_Direction(a_Direction) +{ +} + + + + + +cPiece::cConnector::cConnector(const Vector3i & a_Pos, int a_Type, eBlockFace a_Direction) : + m_Pos(a_Pos), + m_Type(a_Type), + m_Direction(a_Direction) +{ +} + + + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// cPlacedPiece: + +cPlacedPiece::cPlacedPiece(const cPlacedPiece * a_Parent, const cPiece & a_Piece, const Vector3i & a_Coords, int a_NumCCWRotations) : + m_Parent(a_Parent), + m_Piece(&a_Piece), + m_Coords(a_Coords), + m_NumCCWRotations(a_NumCCWRotations) +{ + m_Depth = (m_Parent == NULL) ? 0 : (m_Parent->GetDepth() + 1); + m_HitBox = a_Piece.RotateMoveHitBox(a_NumCCWRotations, a_Coords.x, a_Coords.y, a_Coords.z); +} + + + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// cPieceGenerator: + +cPieceGenerator::cPieceGenerator(cPiecePool & a_PiecePool, int a_Seed) : + m_PiecePool(a_PiecePool), + m_Noise(a_Seed), + m_Seed(a_Seed) +{ +} + + + + + +void cPieceGenerator::FreePieces(cPlacedPieces & a_PlacedPieces) +{ + for (cPlacedPieces::iterator itr = a_PlacedPieces.begin(), end = a_PlacedPieces.end(); itr != end; ++itr) + { + delete *itr; + } // for itr - a_PlacedPieces[] + a_PlacedPieces.clear(); +} + + + + + +cPlacedPiece * cPieceGenerator::PlaceStartingPiece(int a_BlockX, int a_BlockY, int a_BlockZ, cFreeConnectors & a_OutConnectors) +{ + m_PiecePool.Reset(); + int rnd = m_Noise.IntNoise3DInt(a_BlockX, a_BlockY, a_BlockZ) / 7; + + // Choose a random one of the starting pieces: + cPieces StartingPieces = m_PiecePool.GetStartingPieces(); + cPiece * StartingPiece = StartingPieces[rnd % StartingPieces.size()]; + rnd = rnd >> 16; + + // Choose a random supported rotation: + int Rotations[4] = {0}; + int NumRotations = 1; + for (int i = 1; i < ARRAYCOUNT(Rotations); i++) + { + if (StartingPiece->CanRotateCCW(i)) + { + Rotations[NumRotations] = i; + NumRotations += 1; + } + } + int Rotation = Rotations[rnd % NumRotations]; + + cPlacedPiece * res = new cPlacedPiece(NULL, *StartingPiece, Vector3i(a_BlockX, a_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, a_BlockY, a_BlockZ)) + ); + } + + return res; +} + + + + + +bool cPieceGenerator::TryPlacePieceAtConnector(const cPlacedPiece & a_ParentPiece, const cPiece::cConnector & a_Connector, cPlacedPieces & a_OutPieces) +{ + // Translation of direction - direction -> number of CCW rotations needed: + // You need DirectionRotationTable[rot1][rot2] CCW turns to connect rot1 to rot2 (they are opposite) + static const int DirectionRotationTable[6][6] = + { + /* YM, YP, ZM, ZP, XM, XP + /* YM */ { 0, 0, 0, 0, 0, 0}, + /* YP */ { 0, 0, 0, 0, 0, 0}, + /* ZM */ { 0, 0, 0, 2, 1, 3}, + /* ZP */ { 0, 0, 2, 0, 3, 1}, + /* XM */ { 0, 0, 3, 1, 0, 2}, + /* XP */ { 0, 0, 1, 3, 2, 0}, + }; + + // Get a list of available connections: + const int * RotTable = DirectionRotationTable[a_Connector.m_Direction]; + cConnections Connections; + cPieces AvailablePieces = m_PiecePool.GetPiecesWithConnector(a_Connector.m_Type); + Connections.reserve(AvailablePieces.size()); + Vector3i ConnPos = a_Connector.m_Pos; // The position at which the new connector should be placed - 1 block away from the connector + AddFaceDirection(ConnPos.x, ConnPos.y, ConnPos.z, a_Connector.m_Direction); + + // DEBUG: + printf("Placing piece at pos {%d, %d, %d}, direction %s\n", ConnPos.x, ConnPos.y, ConnPos.z, BlockFaceToString(a_Connector.m_Direction).c_str()); + + for (cPieces::iterator itrP = AvailablePieces.begin(), endP = AvailablePieces.end(); itrP != endP; ++itrP) + { + cPiece::cConnectors Connectors = (*itrP)->GetConnectors(); + for (cPiece::cConnectors::iterator itrC = Connectors.begin(), endC = Connectors.end(); itrC != endC; ++itrC) + { + if (itrC->m_Type != a_Connector.m_Type) + { + continue; + } + // This is a same-type connector, find out how to rotate to it: + int NumCCWRotations = RotTable[itrC->m_Direction]; + if (!(*itrP)->CanRotateCCW(NumCCWRotations)) + { + // Doesn't support this rotation + continue; + } + if (!CheckConnection(a_Connector, ConnPos, **itrP, *itrC, NumCCWRotations, a_OutPieces)) + { + // Doesn't fit in this rotation + continue; + } + Connections.push_back(cConnection(**itrP, *itrC, NumCCWRotations)); + } // for itrC - Connectors[] + } // for itrP - AvailablePieces[] + if (Connections.empty()) + { + // No available connections, bail out + return false; + } + + // Choose a random connection from the list: + int rnd = m_Noise.IntNoise3DInt(a_Connector.m_Pos.x, a_Connector.m_Pos.y, a_Connector.m_Pos.z) / 7; + cConnection & Conn = Connections[rnd % Connections.size()]; + + // Place the piece: + printf("Chosen connector at {%d, %d, %d}, direction %s, needs %d rotations\n", + Conn.m_Connector.m_Pos.x, Conn.m_Connector.m_Pos.y, Conn.m_Connector.m_Pos.z, + BlockFaceToString(Conn.m_Connector.m_Direction).c_str(), + Conn.m_NumCCWRotations + ); + Vector3i NewPos = Conn.m_Piece->RotatePos(Conn.m_Connector.m_Pos, Conn.m_NumCCWRotations); + ConnPos -= NewPos; + a_OutPieces.push_back(new cPlacedPiece(&a_ParentPiece, *(Conn.m_Piece), ConnPos, Conn.m_NumCCWRotations)); + + // Add the new piece's connectors to the list of free connectors: + // TODO + + return true; +} + + + + + +bool cPieceGenerator::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); + for (cPlacedPieces::const_iterator itr = a_OutPieces.begin(), end = a_OutPieces.end(); itr != end; ++itr) + { + if ((*itr)->GetHitBox().DoesIntersect(RotatedHitBox)) + { + return false; + } + } + return true; +} + + + + + +// DEBUG: +void cPieceGenerator::DebugConnectorPool(const cPieceGenerator::cFreeConnectors & a_ConnectorPool, size_t a_NumProcessed) +{ + printf(" Connector pool: %u items\n", a_ConnectorPool.size() - a_NumProcessed); + size_t idx = 0; + for (cPieceGenerator::cFreeConnectors::const_iterator itr = a_ConnectorPool.begin() + a_NumProcessed, end = a_ConnectorPool.end(); itr != end; ++itr, ++idx) + { + printf(" %u: {%d, %d, %d}, type %d, direction %s\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, + BlockFaceToString(itr->m_Connector.m_Direction).c_str() + ); + } // for itr - a_ConnectorPool[] +} + + + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// cPieceGenerator::cConnection: + +cPieceGenerator::cConnection::cConnection(cPiece & a_Piece, cPiece::cConnector & a_Connector, int a_NumCCWRotations) : + m_Piece(&a_Piece), + m_Connector(a_Connector), + m_NumCCWRotations(a_NumCCWRotations) +{ +} + + + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// cPieceGenerator::cFreeConnector: + +cPieceGenerator::cFreeConnector::cFreeConnector(cPlacedPiece * a_Piece, const cPiece::cConnector & a_Connector) : + m_Piece(a_Piece), + m_Connector(a_Connector) +{ +} + + + + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// cBFSPieceGenerator: + +cBFSPieceGenerator::cBFSPieceGenerator(cPiecePool & a_PiecePool, int a_Seed) : + super(a_PiecePool, a_Seed) +{ +} + + + + + +void cBFSPieceGenerator::PlacePieces(int a_BlockX, int a_BlockY, 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_BlockY, 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)) + { + 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) + { + ConnectorPool.erase(ConnectorPool.begin(), ConnectorPool.begin() + NumProcessed); + NumProcessed = 0; + } + } +} + + + + diff --git a/src/Generating/PieceGenerator.h b/src/Generating/PieceGenerator.h new file mode 100644 index 000000000..0e24510ae --- /dev/null +++ b/src/Generating/PieceGenerator.h @@ -0,0 +1,238 @@ + +// PieceGenerator.h + +// Declares the cBFSPieceGenerator class and cDFSPieceGenerator class +// representing base classes for generating structures composed of individual "pieces" + +/* +Each uses a slightly different approach to generating: + - DFS extends pieces one by one until it hits the configured depth (or can't connect another piece anymore), + then starts looking at adjacent connectors (like depth-first search). + - BFS 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 (like breadth-first search). +*/ + + + + + +#pragma once + +#include "../Defines.h" +#include "../Cuboid.h" +#include "../Noise.h" + + + + + +/** Represents a single piece. Can have multiple connectors of different types where other pieces can connect. */ +class cPiece +{ +public: + struct cConnector + { + /** Position relative to the piece */ + Vector3i m_Pos; + + /** Type of the connector. Any arbitrary number; the generator connects only connectors of the same type. */ + int m_Type; + + /** Direction in which the connector is facing. + Will be matched by the opposite direction for the connecting connector. */ + eBlockFace m_Direction; + + cConnector(int a_X, int a_Y, int a_Z, int a_Type, eBlockFace a_Direction); + cConnector(const Vector3i & a_Pos, int a_Type, eBlockFace a_Direction); + }; + + typedef std::vector<cConnector> cConnectors; + + /** Returns all of the available connectors that the piece has. + Each connector has a (relative) position in the piece, and a type associated with it. */ + virtual cConnectors GetConnectors(void) const = 0; + + /** Returns the dimensions of this piece. + The dimensions cover the entire piece, there is no block that the piece generates outside of this size. */ + virtual Vector3i GetSize(void) const = 0; + + /** Returns the "hitbox" of this piece. + A hitbox is what is compared and must not intersect other pieces' hitboxes when generating. */ + virtual cCuboid GetHitBox(void) const = 0; + + /** Returns true if the piece can be rotated CCW the specific number of 90-degree turns. */ + virtual bool CanRotateCCW(int a_NumRotations) const = 0; + + /** Returns a copy of the a_Pos after rotating the piece the specified number of CCW rotations. */ + Vector3i RotatePos(const Vector3i & a_Pos, int a_NumCCWRotations) const; + + /** Returns a copy of the connector that is rotated and then moved by the specified amounts. */ + cConnector RotateMoveConnector(const cConnector & a_Connector, int a_NumCCWRotations, int a_MoveX, int a_MoveY, int a_MoveZ) const; + + /** Returns the hitbox after the specified number of rotations and moved so that a_MyConnector is placed at a_ToConnectorPos. */ + cCuboid RotateHitBoxToConnector(const cConnector & a_MyConnector, const Vector3i & a_ToConnectorPos, int a_NumCCWRotations) const; + + /** Returns the hitbox after the specified number of CCW rotations and moved by the specified amounts. */ + cCuboid RotateMoveHitBox(int a_NumCCWRotations, int a_MoveX, int a_MoveY, int a_MoveZ) const; +}; + +typedef std::vector<cPiece *> cPieces; + + + + + +class cPiecePool +{ +public: + /** Returns a list of pieces that contain the specified connector type. + The cPiece pointers returned are managed by the pool and the caller doesn't free them. */ + virtual cPieces GetPiecesWithConnector(int a_ConnectorType) = 0; + + /** Returns the pieces that should be used as the starting point. + Multiple starting points are supported, one of the returned piece will be chosen. */ + virtual cPieces GetStartingPieces(void) = 0; + + /** Called after a piece is placed, to notify the pool that it has been used. + The pool may adjust the pieces it will return the next time. */ + virtual void PiecePlaced(const cPiece & a_Piece) = 0; + + /** Called when the pool has finished the current structure and should reset any piece-counters it has + for a new structure. */ + virtual void Reset(void) = 0; +}; + + + + + +/** Represents a single piece that has been placed to specific coords in the world. */ +class cPlacedPiece +{ +public: + cPlacedPiece(const cPlacedPiece * a_Parent, const cPiece & a_Piece, const Vector3i & a_Coords, int a_NumCCWRotations); + + const cPiece & GetPiece (void) const { return *m_Piece; } + const Vector3i & GetCoords (void) const { return m_Coords; } + const int GetNumCCWRotations(void) const { return m_NumCCWRotations; } + const cCuboid & GetHitBox (void) const { return m_HitBox; } + const int GetDepth (void) const { return m_Depth; } + +protected: + const cPlacedPiece * m_Parent; + const cPiece * m_Piece; + Vector3i m_Coords; + int m_NumCCWRotations; + cCuboid m_HitBox; + int m_Depth; +}; + +typedef std::vector<cPlacedPiece *> cPlacedPieces; + + + + + +class cPieceGenerator +{ +public: + cPieceGenerator(cPiecePool & a_PiecePool, int a_Seed); + + /** Cleans up all the memory used by the placed pieces. + Call this utility function instead of freeing the items on your own. */ + void FreePieces(cPlacedPieces & a_PlacedPieces); + +protected: + /** The type used for storing a connection from one piece to another, while building the piece tree. */ + struct cConnection + { + cPiece * m_Piece; // The piece being connected + cPiece::cConnector m_Connector; // The piece's connector being used (relative non-rotated coords) + int m_NumCCWRotations; // Number of rotations necessary to match the two connectors + + cConnection(cPiece & a_Piece, cPiece::cConnector & a_Connector, int a_NumCCWRotations); + }; + typedef std::vector<cConnection> cConnections; + + /** The type used for storing a pool of connectors that will be attempted to expand by another piece. */ + struct cFreeConnector + { + cPlacedPiece * m_Piece; + cPiece::cConnector m_Connector; + + cFreeConnector(cPlacedPiece * a_Piece, const cPiece::cConnector & a_Connector); + }; + typedef std::vector<cFreeConnector> cFreeConnectors; + + + cPiecePool & m_PiecePool; + cNoise m_Noise; + int m_Seed; + + + /** Selects a starting piece and places it, including the rotations. + Also puts the piece's connectors in a_OutConnectors. */ + cPlacedPiece * PlaceStartingPiece(int a_BlockX, int a_BlockY, int a_BlockZ, cFreeConnectors & a_OutConnectors); + + /** Tries to place a new piece at the specified (placed) connector. Returns true if successful. */ + bool TryPlacePieceAtConnector( + const cPlacedPiece & a_ParentPiece, + const cPiece::cConnector & a_Connector, + cPlacedPieces & a_OutPieces + ); + + /** Checks if the specified piece would fit with the already-placed pieces, using the specified connector + and number of CCW rotations. + a_ExistingConnector is in world-coords and is already rotated properly + a_ToPos is the world-coords position on which the new connector should be placed (1 block away from a_ExistingConnector, in its Direction) + a_NewConnector is in the original (non-rotated) coords. + Returns true if the piece fits, false if not. */ + bool CheckConnection( + const cPiece::cConnector & a_ExistingConnector, // The existing connector + const Vector3i & a_ToPos, // The position on which the new connector should be placed + const cPiece & a_Piece, // The new piece + const cPiece::cConnector & a_NewConnector, // The connector of the new piece + int a_NumCCWRotations, // Number of rotations for the new piece to align the connector + const cPlacedPieces & a_OutPieces // All the already-placed pieces to check + ); + + /** DEBUG: Outputs all the connectors in the pool into stdout. + a_NumProcessed signals the number of connectors from the pool that should be considered processed (not listed). */ + void DebugConnectorPool(const cPieceGenerator::cFreeConnectors & a_ConnectorPool, size_t a_NumProcessed); +} ; + + + + + +class cBFSPieceGenerator : + public cPieceGenerator +{ + typedef cPieceGenerator super; + +public: + cBFSPieceGenerator(cPiecePool & a_PiecePool, int a_Seed); + + /** Generates a placement for pieces at the specified coords. + Caller must free each individual cPlacedPiece in a_OutPieces. */ + void PlacePieces(int a_BlockX, int a_BlockY, int a_BlockZ, int a_MaxDepth, cPlacedPieces & a_OutPieces); +}; + + + + + +class cDFSPieceGenerator : + public cPieceGenerator +{ +public: + cDFSPieceGenerator(cPiecePool & a_PiecePool, int a_Seed); + + /** Generates a placement for pieces at the specified coords. + Caller must free each individual cPlacedPiece in a_OutPieces. */ + void PlacePieces(int a_BlockX, int a_BlockY, int a_BlockZ, cPlacedPieces & a_OutPieces); +}; + + + + |