C++ Data Structures Assignments
I'm a proud graduate of Rensselaer Polytechnic Institute's weedout C++ Data Structures course: A course that wasn't even required for my major!
HW8: Bounding Volume Heirarchy
Prompt: https://www.cs.rpi.edu/academics/courses/fall20/csci1200/hw/08_bounding_volume_hierarchy/hw.pdf
Creation of a BVH tree data structure enables efficient spatial queries for use in a variety of applications, such as a ray tracing and collision detection. This was by far my favorite assignment in the course, as it felt closer to my field of game development than any other. Additionally, I personally feel as though I went above and beyond in my implementation of an incremental BVH tree (where shapes are inserted into the structure one by one rather than generated all at once) as you will see below. The outcome of my incremental BVH tree is far more organized and cohesive than the faculty's example.
Their Solution (Non-Incremental)
My Solution (Non-Incremental)
My implementation of the non-incremental BVH tree results in an identical output as the prompt requested. But my incremental implementation is where it gets interesting.
Their Solution (Incremental)
The prompt's solutions for a BVH tree capable of inserting shapes on the fly yields much messier and less organized results than one generated with all the shapes. I decided to reverse engineer the solution and attempt to make the incremental approach yield trees more similar to the non-incremental method.
My Solution (Incremental)
Rather than generating the bounding boxes after the fact based on the order of the shapes added, my first iteration works backwards to decide a base set of bounding boxes that shapes will get organized into. These bounding boxes are not set in stone however, and are capable or morphing or shrinking based on other shapes that are added. Then, according to the desired depth of the tree, these initial areas are recursively divided once again into three approximately similar areas. This repeats until the desired depth is achieved. As you can see, it results in a much more organized and more efficient-to-query data structure, as there are less overlapping regions and each query has less data to sift through. If we were to query a location in their first circle example, we would have no choice but to check objects in the green tree every time because the entire region is considered to encompass the green objects. In my solution, the green region only covers about 60% of the provided area, resulting in less computation time in order to complete a query.
typedef unsigned int uint; template class BVH { ...omitted code for sake of length... (node and iterator class implementations) ///////////////////////////////// /* NOTE: BVH CLASS DECLARATION */ ///////////////////////////////// // Default Constructor BVH(int split_threshold_, int depth_limit_) : root(NULL), split_threshold(split_threshold_), depth_limit(depth_limit_) {} // Copy Constructor BVH(BVH& b) { copy_bvh(b.root); } ~BVH() { destroy_bvh(root); } BVH& operator=(const BVH& other) { copy_bvh(other.root); return *this; } // Member Functions void construct(const std::vector& elements); void insert(const T& element); bool collision(const T& other); // (public) user functions to gather statistics & print the tree visualization void statistics(bool print_tree) const; void render_recolor(std::ostream &ostr) { render_recolor(ostr,root,Color(128,128,128)); } // Accessor Functions iterator begin() const; // give node all the way to the left iterator end() const; // return NULL iterator. private: // (private) helper functions void ConstructEmptyBVH(); void BlankConstruct(Node* startingNode, int newDepth); Node* copy_bvh(Node* startingNode); void destroy_bvh(Node* startingNode); void insert_recursive(const T& element, Node* startingNode); void InitializeParentBoundingBoxes(Node* leafNode); void SplitIntoThree(Node* currentNode, int currDepth); void SortByAxis(std::vector& elements, std::vector& sortedElements, Axis direction); void SortByAxis_List(std::list& elements, Axis direction); int ChildrenWithBoundingBoxCount(Node* thisNode); Node* ClosestBoundingBox(const T& other, Node* node); void statistics(bool print_tree, Node* n, const std::string &indent, int &node_count, int &max_depth, double &inner_node_area, double &leaf_node_area) const; void render_recolor(std::ostream &ostr, Node *n, const Color &color); // REPRESENTATION Node* root = NULL; BoundingBox canvasSize = BoundingBox(); uint split_threshold; int depth_limit; int shape_count = 0; float insertDistanceThreshold = 200.0; }; // ===================================================================== // SHAPE COMPARISON FUNCTIONS template bool ShapeLessThan_X_PTR(const T* a, const T* b) { return a->getCenter().x getCenter().x; } template bool ShapeLessThan_Y_PTR(const T* a, const T* b) { return a->getCenter().y getCenter().y; } template bool ShapeLessThan_X(const T& a, const T& b) { return a.getCenter().x < b.getCenter().x; } template bool ShapeLessThan_Y(const T& a, const T& b) { return a.getCenter().y < b.getCenter().y; } // ===================================================================== // BVH CLASS IMPLEMENTATION // Given a vector of shapes, recursively split elements in groups, assigning into the // BVH structure until desired depth or shape count per group is achieved. template void BVH::construct(const std::vector& elements) { // Determine the min/max points of all these shapes // Sort by X and Y in order to get min/max Y values. std::vector allShapes = PointerCopy(elements); shape_count = allShapes.size(); std::vector shapes_sorted_X; SortByAxis(allShapes, shapes_sorted_X, Axis::X); std::vector shapes_sorted_Y; SortByAxis(allShapes, shapes_sorted_Y, Axis::Y); int minX = shapes_sorted_X[0]->getBox().getMin().x; int minY = shapes_sorted_Y[0]->getBox().getMin().y; int maxX = shapes_sorted_X[shapes_sorted_X.size() - 1]->getBox().getMax().x; int maxY = shapes_sorted_Y[shapes_sorted_X.size() - 1]->getBox().getMax().y; // Initialize overall canvasSize for entire BVH structure. canvasSize = BoundingBox(Point(minX, minY), Point(maxX, maxY)); // Begin split on X axis. if(canvasSize.dx() > canvasSize.dy()) { // Create root with all shapes, begin splitting. root = new Node(shapes_sorted_X); root->root = true; root->InitializeBoundingBox(); SplitIntoThree(root, 0); } // Begin split on Y axis. else { // Create root with all shapes, begin splitting. root = new Node(shapes_sorted_Y); root->root = true; root->InitializeBoundingBox(); SplitIntoThree(root, 0); } } template void BVH::insert(const T& element) { // See "insert_recursive" implementation for detailed explanation of insert algorithm. if(root == NULL) ConstructEmptyBVH(); insert_recursive(element, root); } // Some forward declaration helper functions bool OverlapsCompletely(BoundingBox& a, BoundingBox& b); bool EmptyBox(BoundingBox& a); Point BoundingBoxCenter(BoundingBox& a); template typename BVH::Node* ClosestCollidingBoundingBox(const T& other, typename BVH::Node* node); template typename BVH::Node* CollidesWithNode(const T& other, typename BVH::Node* currentNode); template void BVH::insert_recursive(const T& element, Node* startingNode) { // Algorithm goes as follows: // A. Node is a grouping node // == 1. Element Collides With Existing BBox. // == == : Recurse down to the node with the overlapped bbox that is closest to this shape. // == 2. Element Doesn't Collide With Any BBox. // == == 2a. All Node Slots Contain Bounding Boxes // == == == : Recurse down to node with closest bbox. // == == 2b. At least one node slot contains empty Bounding Box. // == == == 2b-1: Distance between "element" and "node->bbox.getCenter()" is greater than "insertDistanceThreshold" / "node->depth", // == == == == : Insert shape into node with empty bounding box. // == == == 2b-2: Distance is less threshold // == == == == : Recurse down existing node. // == == 2c. All node slots are empty. // == == == == : Push shape into list data at very bottom left of subtree. // B. Node is a shape node // == : Push shape into list data. // == : Reassert bounding boxes. // == : Terminate. if(startingNode->children[0] != NULL) // Node is a grouping node. { Node* collidingNode = ClosestCollidingBoundingBox(element, startingNode); // Element collides with existing bbox if(collidingNode != NULL) { // Recurse down into this node. insert_recursive(element, collidingNode); } // Element doesn't collide else { int nodesWithShapesCount = ChildrenWithBoundingBoxCount(startingNode); if(nodesWithShapesCount == 3) // all nodes contain bounding boxes, recurse into closest one. { insert_recursive(element, ClosestBoundingBox(element, startingNode)); } else if(nodesWithShapesCount > 0 && nodesWithShapesCount < 3) // at least one node doesn't have a bbox. { bool recursed = false; for(uint i = 0; i children.size(); i++) { float threshold = (insertDistanceThreshold / (startingNode->depth + 1)); float dist = distance(BoundingBoxCenter(startingNode->children[i]->bbox), element.getCenter()); if(dist < threshold) { recursed = true; } } if(recursed == false) { for(uint i = 0; i children.size(); i++) { if(EmptyBox(startingNode->children[i]->bbox) == true) { Node* insertingAtNode = startingNode->children[i]->LowestLeftNode(); shape_count++; insertingAtNode->data.push_back(element); insertingAtNode->InitializeBoundingBox(); InitializeParentBoundingBoxes(insertingAtNode); break; } } } } else if(nodesWithShapesCount == 0) // all nodes are empty, push shape into very bottom left. { Node* insertingAtNode = startingNode->LowestLeftNode(); shape_count++; insertingAtNode->data.push_back(element); insertingAtNode->InitializeBoundingBox(); InitializeParentBoundingBoxes(insertingAtNode); } } } else // This node contains shapes, push element to { shape_count++; startingNode->data.push_back(element); startingNode->InitializeBoundingBox(); InitializeParentBoundingBoxes(startingNode); } } // Driver function for collision detection. template bool BVH::collision(const T& other) { if(root == NULL) ConstructEmptyBVH(); return CollidesWith(other, root); } // Recursive Function for collision detection. // Does other's bounding box collide with any of shapes located in Node? template bool CollidesWith(const T& other, typename BVH::Node* node) { if(node->children[0] != NULL) { for(uint i = 0; i children.size(); i++) { if(EmptyBox(node->children[i]->bbox) == false && node->children[i]->bbox.overlaps(other.getBox())) { bool result = CollidesWith(other, node->children[i]); if(result == false) continue; else return true; } } } else { typename std::list::iterator itr = node->data.begin(); for(; itr != node->data.end(); itr++) { if(intersect(*itr, other)) return true; } } return false; } // Returns the node with the colliding bounding box that is closest to other's center point. template typename BVH::Node* ClosestCollidingBoundingBox(const T& other, typename BVH::Node* node) { int closestIndex = -1; float closestDistance = 9999; for(uint i = 0; i children.size(); i++) { if(EmptyBox(node->children[i]->bbox) == false && node->children[i]->bbox.overlaps(other.getBox())) // overlap check { float boxDistance = distance(BoundingBoxCenter(node->children[i]->bbox), other.getCenter()); if(boxDistance children[closestIndex]; } template typename BVH::Node* BVH::ClosestBoundingBox(const T& other, Node* node) { int closestIndex = -1; float closestDistance = 9999; for(uint i = 0; i children.size(); i++) { if(EmptyBox(node->children[i]->bbox) == false) // contains no overlap check { float boxDistance = distance(BoundingBoxCenter(node->children[i]->bbox), other.getCenter()); if(boxDistance children[closestIndex]; } template int BVH::ChildrenWithBoundingBoxCount(typename BVH::Node* thisNode) { int count = 0; for(uint i = 0; i children.size(); i++) { if(EmptyBox(thisNode->children[i]->bbox) == false) count++; } return count; } // Does "other" collide with "currentNode"? If so, iterates down currentNode's chain // and returns the lowest level node that "other" collides with. template typename BVH::Node* CollidesWithNode(const T& other, typename BVH::Node* currentNode) { if(currentNode->children[0] != NULL) { for(uint i = 0; i children.size(); i++) { if(currentNode->children[i]->bbox.overlaps(other.getBox())) { typename BVH::Node* result = CollidesWithNode(other, currentNode->children[i]); if(result == NULL) continue; else return result; } } } else { if(currentNode->bbox.overlaps(other.getBox())) return currentNode; else return NULL; } return false; } template void BVH::ConstructEmptyBVH() { root = new Node(); BlankConstruct(root, 0); } template void BVH::BlankConstruct(Node* startingNode, int newDepth) { startingNode->depth = newDepth; if(startingNode->children.size() == 0) startingNode->children = std::vector(3, NULL); if(newDepth < depth_limit) { for(int i = 0; i children[i] = newNode; startingNode->children[i]->parent = startingNode; newNode->childID = i; BlankConstruct(newNode, newDepth + 1); } } } template typename BVH::Node* BVH::copy_bvh(Node* startingNode) { Node* newNode = new Node(); typename std::list::iterator itr = startingNode->data.begin(); for(; itr != startingNode->data.end(); itr++) { newNode->data.push_back(*itr); } newNode->root = startingNode->root; if(newNode->root) root = newNode; newNode->bbox = startingNode->bbox; newNode->depth = startingNode->depth; newNode->childID = startingNode->childID; if(startingNode->children[0] != NULL) { for(int i = 0; i children.size(); i++) { Node* childNode = copy_bvh(startingNode->children[i]); childNode->parent = newNode; newNode->children[i] = childNode; } } return newNode; } template void BVH::destroy_bvh(Node* startingNode) { if(startingNode != NULL) { for(uint i = 0; i children.size(); i++) { destroy_bvh(startingNode->children[i]); } delete startingNode; } } // Given a leaf node that contains valid shapes, assert bounding box to all parents. template void BVH::InitializeParentBoundingBoxes(Node* leafNode) { leafNode->InitializeBoundingBox(); Node* node = leafNode; while(node->parent != NULL) // keep going up the chain. { if(OverlapsCompletely(node->parent->bbox, node->bbox) == false) // only keep going if bboxes dont completely overlap. { // if parent bbox is unitialized, just set equal to node's bbox if(EmptyBox(node->parent->bbox)) node->parent->bbox = node->bbox; // otherwise, extend parents bbox to encompass this bbox. else node->parent->bbox.extend(node->bbox); // Repeat with parent. node = node->parent; } else { // bboxes completely overlap, no need to keep updating. break; } } } // Given a node with N number of spatially ordered shapes, split into three groups // and recursively call on new groups until no more splitting is possible. template void BVH::SplitIntoThree(Node* currentNode, int currDepth) { // we have reached depth limit, stop here. if(currDepth >= depth_limit || currentNode->data.size() InitializeBoundingBox(); currentNode->depth = currDepth; return; } // keep splitting... else { currentNode->depth = currDepth; // Calculate number of shapes per group. Store uneven surplus shapes into third group. int originalSize = currentNode->data.size(); int shapesPerNode = std::floor((float)currentNode->data.size() / (float)3); int thirdRoundCount = (originalSize - (shapesPerNode * 3)) + shapesPerNode; // split three times... for(int i = 0; i data.size() > 0) { // Create new node. Node* newNode = new Node(); int shapeCount = shapesPerNode; if(i == 2) shapeCount = thirdRoundCount; // Take "shapeCount" number of shapes from parent node, popping front as we grab them. for(int j = 0; j data.size() > 0) { newNode->data.push_back(currentNode->data.front()); currentNode->data.pop_front(); } else break; } // new node has all desired shapes, initialize information. newNode->InitializeBoundingBox(); // Sort the new node's shape according to widest axis of bounding box. Axis direction; if(newNode->bbox.dx() > newNode->bbox.dy()) direction = Axis::X; else direction = Axis::Y; SortByAxis_List(newNode->data, direction); // Assign pointer variables currentNode->children[i] = newNode; newNode->parent = currentNode; newNode->childID = i; // Split new node. SplitIntoThree(newNode, currDepth + 1); } else break; } } } // Given a vector of shapes, sort from least to greatest position according to Axis specification. // Stores in sortedElements. template void BVH::SortByAxis(std::vector& elements, std::vector& sortedElements, Axis direction) { sortedElements.clear(); sortedElements = std::vector(elements.size(), NULL); for(uint i = 0; i < elements.size(); i++) { sortedElements[i] = elements[i]; } switch(direction) { case Axis::X: std::sort(sortedElements.begin(), sortedElements.end(), ShapeLessThan_X_PTR); break; case Axis::Y: std::sort(sortedElements.begin(), sortedElements.end(), ShapeLessThan_Y_PTR); break; } } // Given a list of shapes, sort from least to greatest position according to Axis specification. template void BVH::SortByAxis_List(std::list& elements, Axis direction) { switch(direction) { case Axis::X: elements.sort(ShapeLessThan_X); break; case Axis::Y: elements.sort(ShapeLessThan_Y); break; } } // Returns an iterator pointing to the first shape in the BVH. template typename BVH::iterator BVH::begin() const { Node* thisNode = root; while(thisNode->children[0] != NULL) { thisNode = thisNode->children[0]; } return BVH::iterator(thisNode); } // Returns a NULL iterator template typename BVH::iterator BVH::end() const { BVH::iterator itr = iterator(NULL); itr.SetSecretRootPointer(root); itr.SetShapeItr(itr.SecretRootPointer()->LastShape()); return itr; } ///////////////////////////////////////////// // helper functions for statistics & printing // This function walks over all nodes of the tree collecting // information about the count, type (inner or leaf), and area of // nodes in the tree. template void BVH::statistics(bool print_tree) const { int node_count = 0; int max_depth = 0; double inner_node_area = 0; double leaf_node_area = 0; // sweep over the tree and print the results statistics(print_tree,root,"",node_count, max_depth, inner_node_area, leaf_node_area); std::cout << "node count: " << std::setw(7) << node_count << std::endl; std::cout << "max depth: " << std::setw(7) << max_depth << std::endl; std::cout << "inner node area: " << std::fixed << std::setw(7) << std::setprecision(3) << inner_node_area << std::endl; std::cout << "leaf node area: " << std::fixed << std::setw(7) << std::setprecision(3) << leaf_node_area << std::endl; } // The core recursive function to collect the statistics above. If // the print_tree bool is enabled, we will also print data about the // tree for debugging and autograding. template void BVH::statistics(bool print_tree, Node* n, const std::string &indent, int &node_count, int &max_depth, double &inner_node_area, double &leaf_node_area) const { node_count++; if(n == NULL) return; max_depth = std::max(n->depth,max_depth); // scale the area by the area of the scene double area = n->bbox.getArea() / double(1000*1000); if (n->children[0] == NULL) { leaf_node_area += n->data.size() * area; if (print_tree) { std::cout << indent + "leaf area=" << std::setprecision(3) << area << " " <bbox << " elements:"; typename std::list::iterator itr = n->data.begin(); for (; itr != n->data.end(); itr++) { std::cout << " " <getBox(); } std::cout << std::endl; } } else { inner_node_area += area; if (print_tree) { std::cout << indent + "inner area=" << std::setprecision(3) << area << " " <bbox <children[0],indent+" ",node_count,max_depth,inner_node_area,leaf_node_area); statistics(print_tree,n->children[1],indent+" ",node_count,max_depth,inner_node_area,leaf_node_area); statistics(print_tree,n->children[2],indent+" ",node_count,max_depth,inner_node_area,leaf_node_area); } } //////////////////////////////////// // helper functions for rendering template void BVH::render_recolor(std::ostream &ostr, Node *n, const Color &color) { // draw the bounding box of this node as a transparent colored rectangle n->bbox.render(ostr,color); if (n->children[0] != NULL) { // prepare variations of this node color for the 3 children Color red(255,0,0); Color green(0,255,0); Color blue(0,0,255); // blend the colors if (color.r != 128 && color.g != 128 && color.b != 128) { float m = 0.33; red.mix(color,m); green.mix(color,m); blue.mix(color,m); } // recurse to the children render_recolor(ostr,n->children[0],red); render_recolor(ostr,n->children[1],green); render_recolor(ostr,n->children[2],blue); } else { // if this is a leaf node, modify the color of all elements to // match the transparent box color. typename std::list::iterator itr = n->data.begin(); for (; itr != n->data.end(); itr++) { itr->setColor(color); } } } // ===================================================================== // NODE CLASS IMPLEMENTATION // Searches through all shapes stored in data and computes // the bounding box of all shapes for this node. template void BVH::Node::InitializeBoundingBox() { float minX = 9999; float minY = 9999; float maxX = 0; float maxY = 0; // Begin iteration. typename std::list::iterator itr = data.begin(); for(; itr != data.end(); itr++) { float x_max = itr->getBox().getMax().x; float y_max = itr->getBox().getMax().y; float x_min = itr->getBox().getMin().x; float y_min = itr->getBox().getMin().y; if(x_max > maxX) maxX = x_max; if(y_max > maxY) maxY = y_max; if(x_min < minX) minX = x_min; if(y_min < minY) minY = y_min; } // Construct bounding box. bbox = BoundingBox(Point(minX, minY), Point(maxX, maxY)); } // Follows the tree downward and to the left from this starting node // and returns an iterator pointing to the first shape in the subtree. template typename std::list::iterator BVH::Node::FirstShape() { Node* otherNode = this; while(otherNode->children[0] != NULL) { otherNode = otherNode->children[0]; } return otherNode->data.begin(); } // Follows the tree downward and to the right from this starting node // and returns an iterator pointing to the last shape in the subtree. template typename std::list::iterator BVH::Node::LastShape() { Node* otherNode = this; while(otherNode->children[2] != NULL) { otherNode = otherNode->children[2]; } if(otherNode->data.size() > 0) return --otherNode->data.end(); else return otherNode->data.end(); } // Follows the tree downward and to the left from this starting node // and returns a pointer to the lowest left node in the subtree. template typename BVH::Node* BVH::Node::LowestLeftNode() { Node* otherNode = this; if(otherNode == NULL) return NULL; while(otherNode->children[0] != NULL) { otherNode = otherNode->children[0]; } return otherNode; } // Follows the tree downward and to the right from this starting node // and returns a pointer to the lowest right node in the subtree. template typename BVH::Node* BVH::Node::LowestRightNode() { Node* otherNode = this; if(otherNode == NULL) return NULL; while(otherNode->children[2] != NULL) { otherNode = otherNode->children[2]; } return otherNode; } // ============================================== // Helper Function // Creates an identical vector of "inVec" but out of pointers // that point to the items in the original vector. template std::vector PointerCopy(const std::vector& inVec) { std::vector returnVec(std::vector(0, NULL)); for(uint i = 0; i b.getMin().x && a.getMin().y > b.getMin().y && a.getMax().x < b.getMax().x && a.getMax().y a.getMin().x && b.getMin().y > a.getMin().y && b.getMax().x < a.getMax().x && b.getMax().y
HW3: Memory Diagram
This is a simple memory diagram illustrating the behind the scenes processes occuring on the stack and heap. I have a strong background in graphic design and illustration, and mainly included this simple assigment to demonstrate my ability to visually represent the ongoings of code in an organized and visually pleasing manner.
#include "undoarray.h" // helper testing function void SimpleTests(); void StudentTests(); void BatchTest(const char* filename, int num); int main(int argc, char* argv[]) { if (argc == 1) { SimpleTests(); std::cout << "Simple tests completed." << std::endl; StudentTests(); std::cout << "Student tests completed." << std::endl; } else { assert (argc == 3); BatchTest(argv[1],atoi(argv[2])); std::cout << "Batch test completed." << std::endl; } } void SimpleTests() { // create an undo array of chars of length 7 // Note: The ua UndoArray object is stored on the stack. // The dynamically-allocated substructures of ua are stored // on the heap. UndoArray ua(7); // confirm that an empty structure of the specified length was created assert (ua.size() == 7); for (unsigned int i = 0; i < ua.size(); i++) { assert (ua.initialized(i) == false); } std::cout << "constructor test completed" << std::endl; // some set & get operations ua.set(2,'a'); assert (ua.initialized(2) == true); assert (ua.get(2) == 'a'); ua.set(2,'b'); assert (ua.initialized(2) == true); assert (ua.get(2) == 'b'); ua.set(4,'c'); assert (ua.initialized(4) == true); assert (ua.get(4) == 'c'); ua.set(6,'d'); ua.set(1,'e'); ua.set(6,'f'); ua.set(6,'g'); std::cout << "set & get tests completed" << std::endl; // ======================================================= // // UNCOMMENT THE SECTIONS BELOW AS YOU // COMPLETE THE IMPLEMENTATION // // ======================================================= // print the structure (to help in debugging) ua.print(); std::cout << "print test completed" << std::endl; // some undo operations ua.undo(2); assert (ua.get(2) == 'a'); assert (ua.get(4) == 'c'); ua.undo(4); assert (ua.initialized(4) == false); assert (ua.initialized(2) == true); assert (ua.get(2) == 'a'); ua.print(); std::cout << "undo tests completed" << std::endl; // example of the copy constructor UndoArray another(ua); // the structures initially look the same assert (another.size() == ua.size()); for (unsigned int i = 0; i < another.size(); i++) { assert (another.initialized(i) == ua.initialized(i)); if (another.initialized(i)) assert (another.get(i) == ua.get(i)); } // but future edits show they are different! another.undo(6); assert (another.get(6) == 'f'); assert (ua.get(6) == 'g'); ua.set(4,'h'); assert (another.initialized(4) != ua.initialized(4)); std::cout << "copy constructor test completed" << std::endl; // example of the assignment operator ua = another; // again the structures look the same for (unsigned int i = 0; i < another.size(); i++) { assert (another.initialized(i) == ua.initialized(i)); if (another.initialized(i)) assert (another.get(i) == ua.get(i)); } std::cout << "assignment operator test completed" << std::endl; // Note: The UndoArray destructor is implicitly called for the // stack-allocated variables 'ua' and 'another' when we leave the // function and it goes out of scope. } void StudentTests() { std::cout << "\n/////////////////" << std::endl; std::cout << "/ STUDENT TESTS /" << std::endl; std::cout << "/////////////////" << std::endl; std::cout << "\n////////////////////" << std::endl; std::cout << "TESTING: OTHER TYPES\n" << std::endl; std::cout << "TYPE: int" << std::endl; UndoArray ua1(3); ua1.set(0, 6); ua1.set(1, 5); ua1.set(1, 7); ua1.set(2, 50); ua1.set(2, 99); assert(ua1.get(1) == 7); ua1.undo(1); assert(ua1.get(1) == 5); ua1.print(); std::cout << "Success" << std::endl; std::cout << "\nTYPE: string" << std::endl; UndoArray ua2(3); ua2.set(0, "cat"); ua2.set(1, "dogs"); ua2.set(1, "kittens"); ua2.set(2, "@@@@@@@@"); ua2.set(2, "shrek is an ogre"); assert(ua2.get(1) == "kittens"); ua2.undo(1); assert(ua2.get(1) == "dogs"); ua2.print(); std::cout << "Success" << std::endl; std::cout << "\n/////////////////////////" << std::endl; std::cout << "TESTING: COPY CONSTRUCTOR\n" << std::endl; UndoArray ua3(3); ua3.set(0, 1); ua3.set(1, 2); ua3.set(2, 3); std::cout << "UndoArray 1." << std::endl; ua3.print(); std::cout << "\nCopying UndoArray 1 into UndoArray 2." << std::endl; UndoArray ua4(ua3); std::cout << "\nUndoArray 2 at initial copy." << std::endl; ua4.print(); ua3.set(0, 2); ua4.set(0, 3); ua4.set(0, 5); ua4.undo(0); std::cout << "\nUndoArray 2 after modifications" << std::endl; ua4.print(); std::cout << "\nUndoArray 1 after UndoArray 2's modifications (Element 0 WAS set to 2)" << std::endl; ua3.print(); std::cout << "\n////////////////////////////" << std::endl; std::cout << "TESTING: ASSIGNMENT OPERATOR\n" << std::endl; std::cout << "UndoArray 1" << std::endl; ua4.print(); std::cout << "\nAssigning UndoArray 1 into UndoArray 2." << std::endl; UndoArray ua6 = ua4; std::cout << "\nUndoArray 2 after assignment." << std::endl; ua6.print(); ua4.set(0, 8); ua6.set(0, 12); ua6.set(1, 48); ua6.set(0, 3); ua6.undo(0); std::cout << "\nUndoArray 2 after modifications" << std::endl; ua6.print(); std::cout << "\nUndoArray 1 after UndoArray 2's modifications (Element 0 WAS set to 8)" << std::endl; ua4.print(); std::cout << "\n/////////////////" << std::endl; std::cout << "TESTING: POP BACK" << std::endl; UndoArray ua5(ua4); ua5.set(2, 4); std::cout << "\nInitial array." << std::endl; ua5.print(); std::cout << "\nPopping two elements" << std::endl; ua5.pop_back(); ua5.pop_back(); ua5.print(); std::cout << "\n/////////////////" << std::endl; std::cout << "TESTING: PUSH BACK" << std::endl; UndoArray ua12 = UndoArray(1); std::cout << "\nInitialize default constructor for UndoArray" << std::endl; ua12.print(); std::cout << "\nPushing 12 and 15 to array." << std::endl; ua12.push_back(12); ua12.push_back(15); ua12.print(); std::cout << "\nTESTING: DESTRUCTOR\n" << std::endl; UndoArray *ua7 = new UndoArray(3); ua7->set(0, 20); ua7->print(); std::cout << "Destructing" <print(); // ERROR TEST CASES // Operating on an UndoArray that doesn't exist, which means it contains all NULL pointers. Test one at a time. //ua7->undo(0); //ua7->get(0); //ua7->set(0, 0); //ua7->pop_back(); //ua7->initialized(0); // Setting an element out of range. /* UndoArray ua8(3); ua8.set(3, 1); */ // Getting an element out of range. /* UndoArray ua9(3); ua9.get(3); */ // Undoing an element out of range. /* UndoArray ua10(3); ua10.undo(3); */ // Undoing an element with NULL values. /* UndoArray ua11(1); ua11.undo(0); */ // Checking if element is initialized with out of range index. /* UndoArray ua11(3); ua11.initialized(3); */ // ======================================================= // // YOU SHOULD ADD YOUR OWN TEST CASES HERE // // be sure to rigorously test: // * invalid requests (comment out for final submission) // // ======================================================= } // Batch test will repeatedly load & process a file with UndoArray // operations. If the program's working memory does not grow when the // program is run many, many times on a large test case, the data // structure is probably free of memory leaks. void BatchTest(const char* filename, int num) { assert (num > 0); while (num > 0) { num--; // open the file stream for reading std::ifstream istr(filename); assert (istr); // read the size of the array to allocate char c; int i; istr >> c >> i; assert (c == 'a'); // here we dynamically (explicitly) allocate memory for the UndoArray object UndoArray *ua = new UndoArray(i); // read in and perform various operations on the array while (istr >> c) { if (c == 's') { istr >> i >> c; ua->set(i,c); } else if (c == 'g') { istr >> i; if (ua->initialized(i)) { char val = ua->get(i); assert (val >= 'a' && val > i; if (ua->initialized(i)) { ua->undo(i); } } } // Because the UndoArray memory was allocated dynamically (using new) // we need to explicitly deallocate the memory (using delete) delete ua; } }
Unity C# Components
Some of my more... organized... components that I've created for Unity Game Engine Projects.
Tutorial Manager
Orignally designed for solo project "Loot, Luck & Levels", see Game Engine Projects for more info.
I wanted to create a simple embedded tutorial manager that keeps track of player actions and assists players in performing actions as they become neccessary. I could see the light at the end of the tunnel, and wanted a system as easy as calling a singular function when some certain event occurs, with events organized in the form of enums.
The tutorial manager is made up of a list of Tutorial Prompts in no particular order, that contain two events: an Activation and Completion event. The prompt also stores the icon and text that are displayed when the activation event is invoked.
Prompts are displayed in a small area, with a max of 3 allowed to be visible at a time. Once a 4th prompt is spawned, the bottom most prompt is auto flushed out of the tutorial manager.
The code:
Interfacing with the tutorial system from any script is as easy as follows: TutorialManager.instance.InvokeTutorialEvent(TutorialEvents.OnFirstMovement); TutorialManager.cs: [System.Serializable] public class TutorialPrompt { public List ActivationEvent = new List(); // Events that the prompt spawns upon... Cannot be activated twice. // All activation events must be invoked before prompt is displayed. // If the completion event ocurrs before the activation event, the prompt is removed from activation. public TutorialEvents CompletionEvent = TutorialEvents.None; // Prompt disappears on completion... public Sprite icon = null; public Color iconColor = Color.white; public string text = ""; public GameObject spawnedPrompt; public bool Activated = false; [HideInInspector] public Vector3 position; } [System.Serializable] public class TutorialEvent { public TutorialEvents ID; public bool invoked = false; public UnityEvent Event; } public class TutorialManager : MonoBehaviour { public static TutorialManager instance; public List TutorialPromptEditorTool = new List(); private Dictionary TutorialEventDatabase = new Dictionary(); public List TutorialEventEditorTool = new List(); public GameObject PromptPrefab = null; public AnimationCurve dropCurve = null; public float DropSpeed = 150; private List spawnedPrompts = new List(); private List markedForDestruction = new List(); #if UNITY_EDITOR private void OnEnable() { instance = this; } #endif private void OnValidate() { instance = this; } private void Awake() { instance = this; InitializeDatabase(); } // Start is called before the first frame update void Start() { StartCoroutine(AnimatePrompts()); InvokeTutorialEvent(TutorialEvents.OnGameStarted); } // Update is called once per frame void Update() { } public static List GetEventsList() { return instance.TutorialEventEditorTool; } public void InitializeDatabase() { foreach (TutorialEvents _event in Enum.GetValues(typeof(TutorialEvents))) { TutorialEvent Event = new TutorialEvent(); Event.ID = _event; Event.Event = new UnityEvent(); Event.Event.AddListener(PushTutorialPromptsByEvent); TutorialEventDatabase.Add(_event, Event); } } public TutorialEvent GetEvent(TutorialEvents ID) { return TutorialEventDatabase[ID]; } // Pushes tutorial prompt to UI. // UI can hold up to 3..? 4?? tutorial prompts. exceeding that many and it will get booted off screen public void InvokeTutorialEvent(TutorialEvents ID) { print("Calling tutorial event " + ID.ToString()); // Check GetEvent(ID).invoked = true; GetEvent(ID).Event.Invoke(ID); } public void PushTutorialPromptsByEvent(TutorialEvents ID) { StartCoroutine(PushTutorialPromptsByEvent_Coroutine(ID)); } public IEnumerator PushTutorialPromptsByEvent_Coroutine(TutorialEvents ID) { for (int i = 0; i < TutorialPromptEditorTool.Count; i++) { if (TutorialPromptEditorTool[i].Activated == false && AllEventsFired(i)) { PushPrompt(i); yield return new WaitForSeconds(0.25f); } else if (TutorialPromptEditorTool[i].CompletionEvent == ID && TutorialPromptEditorTool[i].Activated == false) { TutorialPromptEditorTool[i].Activated = true; // don't do anything, we completed this action before it even popped up. Just activate the prompt so it doesn't come up in future } else if (TutorialPromptEditorTool[i].CompletionEvent == ID && TutorialPromptEditorTool[i].Activated == true) { if (TutorialPromptEditorTool[i].spawnedPrompt != null) TutorialPromptEditorTool[i].spawnedPrompt.GetComponent().FlushSelf(); } else { continue; } } } public bool AllEventsFired(int i) { bool fired = false; int f = 0; foreach (TutorialEvents Event in TutorialPromptEditorTool[i].ActivationEvent) { if (GetEvent(Event).invoked) f++; } if (f >= TutorialPromptEditorTool[i].ActivationEvent.Count) fired = true; return fired; } // Is the tutorial window at rest? // This means that there are 3 or less tutorial prompts active, and are resting at the bottom of the window. // Can be disrupted by disabling prompts. public void PushPrompt(int promptIndex) { //print("Prompt of index : " + promptIndex); GameObject notification = Instantiate(PromptPrefab); notification.name = "SpawnedPrompt"; notification.transform.SetParent(transform); TutorialPrompt_UI promptUICtrl = notification.GetComponent(); promptUICtrl.UpdateDisplay(TutorialPromptEditorTool[promptIndex].text, TutorialPromptEditorTool[promptIndex].icon, TutorialPromptEditorTool[promptIndex].iconColor); TutorialPromptEditorTool[promptIndex].Activated = true; TutorialPromptEditorTool[promptIndex].spawnedPrompt = notification; //promptUICtrl.attachedPrompt = TutorialPromptEditorTool[promptIndex]; //print("Pushing Prompt: " + TutorialPromptEditorTool[promptIndex].icon.name + ", " + TutorialPromptEditorTool[promptIndex].text); notification.transform.localScale = Vector3.one; (notification.transform as RectTransform).sizeDelta = new Vector2((transform as RectTransform).sizeDelta.x, 50); (notification.transform as RectTransform).anchoredPosition = Vector2.zero; spawnedPrompts.Add(notification); for (int f = 0; f < spawnedPrompts.Count - 3; f++) { if (f < 0) break; else { FlushPrompt(f); } } } // flushes spawnedPrompts[0] public void FlushPrompt(int index) { spawnedPrompts[index].GetComponent().Flushed = true; } // Conditions for moving: // 1. Is Flushed. spawnedPrompts[0] is set to flushed when a prompt is pushed which causes the number of prompts active to exceed 3. // being flushed allows the prompt to move beyond the lower limit. public IEnumerator AnimatePrompts() { while (true) { if (markedForDestruction.Count > 0) markedForDestruction.Clear(); for (int i = 0; i < spawnedPrompts.Count; i++) { bool exitAfterThisIteration = false; TutorialPrompt_UI promptCtrl = spawnedPrompts[i].GetComponent(); bool move = true; if (i == 0 && IsAtBottom(transform as RectTransform, spawnedPrompts[i].transform as RectTransform) && promptCtrl.Flushed == false) { (promptCtrl.transform as RectTransform).anchoredPosition = new Vector2(0, -(transform as RectTransform).sizeDelta.y); move = false; } else if (i != 0 && IsAboveView(transform as RectTransform, spawnedPrompts[i].transform as RectTransform) == true) { exitAfterThisIteration = true; } // If the element before this element is a certain distance below, move as well. else if (i != 0 && IsAboveView(transform as RectTransform, spawnedPrompts[i].transform as RectTransform) == false) { for (int j = i - 1; j >= 0; j--) // Loop through every tutorial prompt before this one { if (spawnedPrompts[j] != spawnedPrompts[i] && IsAboveView(transform as RectTransform, spawnedPrompts[j].transform as RectTransform) == false) { if (Vector2.Distance((spawnedPrompts[i].transform as RectTransform).anchoredPosition, (spawnedPrompts[j].transform as RectTransform).anchoredPosition) < (spawnedPrompts[i].transform as RectTransform).sizeDelta.y + 5) { move = false; } } } } /* else if(i != 0) { move = false; }*/ if (promptCtrl.Flushed) { move = true; } if (move && spawnedPrompts[i] != null) { TutorialPrompt_UI uiPromptCtrl = spawnedPrompts[i].GetComponent(); (spawnedPrompts[i].transform as RectTransform).anchoredPosition += new Vector2(0, -DropSpeed * dropCurve.Evaluate(uiPromptCtrl.motionTimer / uiPromptCtrl.maxMotionTime) * Time.deltaTime); } // Outside view zone, mark for destruction if (IsOutsideView(transform as RectTransform, spawnedPrompts[i].transform as RectTransform)) { markedForDestruction.Add(i); } if (exitAfterThisIteration) break; } if (markedForDestruction.Count > 0) { for (int j = markedForDestruction.Count - 1; j >= 0; j--) { Destroy(spawnedPrompts[markedForDestruction[j]]); spawnedPrompts.RemoveAt(markedForDestruction[j]); } markedForDestruction.Clear(); } yield return new WaitForEndOfFrame(); } } public bool IsAtBottom(RectTransform zone, RectTransform rect) { if (rect.anchoredPosition.y <= -zone.sizeDelta.y + 5) { return true; } return false; } public bool IsOutsideView(RectTransform zone, RectTransform rect) { if (rect.anchoredPosition.y = -rect.sizeDelta.y) { return true; } return false; } }
Pawns
Orignally designed for solo project "Loot, Luck & Levels", see Game Engine Projects for more info.
The pawns system for Loot, Luck & Levels entails a wide arching inheritance system that encompasses all objects in the game that are capable of moving with a pathing system, having health, taking damage, and being subjected to various elemental effects. Below is a diagram of all the various pawn types present in the project. Base class code is omitted only because it goes beyond 4000 lines, and isn't anything particularly unique. This is a good example of my understanding and application of inheritance within object oriented programming.
Shopkeeper.cs // An NPC variant that enables the shop UI upon interaction. public class Shopkeeper : NPC { public ShopInventory inventoryPreset; public Transform marketStall; public List inventory = new List(); private bool initialized = false; public override void Start() { base.Start(); marketStall.transform.SetParent(LevelManager.instance.ActiveLevel.transform); } public override void OnPlayerNearby() { base.OnPlayerNearby(); if(nearestPlayer != null) { SetLookAtTarget(nearestPlayer); } } public override void OnPlayerInteract() { base.OnPlayerInteract(); OpenShop(); } public void OpenShop() { if (initialized == false) InitializeInventory(GameplayCanvas.instance.thisPlayer.playerStats.playerInfo.characterClass); GameplayCanvas.instance.OpenShop(this); if (TutorialManager.instance.GetEvent(TutorialEvents.OnFirstStoreOpened).invoked == false) { TutorialManager.instance.InvokeTutorialEvent(TutorialEvents.OnFirstStoreOpened); } } public void TransferItem(PlayerController player, Item_Inventory item) { ItemSlot slotResult = null; player.Inventory.InsertItem(item, out slotResult); inventory.Remove(item); GameplayCanvas.instance.UpdateShop(this); GameplayCanvas.instance.UpdateInventory(); } public void ReceiveItem(Item_Inventory item) { inventory.Add(item); GameplayCanvas.instance.UpdateShop(this); } // Takes the inventory preset public void InitializeInventory(Class playerClass) { inventory.Clear(); foreach (ShopItem item in inventoryPreset.guaranteedItems) { Item_Networked itemInfo = item.itemPrefab.GetComponent(); Item_Inventory invItem = ItemDatabase.instance.NetworkItemToInventoryItem(itemInfo); for(int i = 0; i < item.quantity; i++) { // Randomize quality if (invItem.stats.randomizeQuality) { QualityModifier[] qualities = Enum.GetValues(typeof(QualityModifier)) as QualityModifier[]; int randIndex = UnityEngine.Random.Range(0, qualities.Length); invItem.stats.quality = qualities[randIndex]; } inventory.Add(invItem); } } DropTable dropTable = null; switch (playerClass) { case Class.Melee: dropTable = inventoryPreset.randomItems_Melee; break; case Class.Ranged: dropTable = inventoryPreset.randomItems_Ranged; break; case Class.Magic: dropTable = inventoryPreset.randomItems_Mage; break; } if(dropTable != null) { for (int i = 0; i
EnemyController_Skirmisher.cs // A simple variant of the enemy controller that runs away as players get close to it. public class EnemyController_Skirmisher : EnemyController { public float runAwayDistance; private float attackRange = 0.0f; public override void Awake() { base.Awake(); //runAwayDistance = autoTargetDistance; } // Start is called before the first frame update public override void Start() { base.Start(); if (isServer && preferredAbility != null) { attackRange = abilityStates_Dict[preferredAbility.data.abilityName].attackRange; } else if(isServer) { attackRange = runAwayDistance; } } [ServerCallback] // Update is called once per frame public override void Update() { base.Update(); if(currentTarget != null && targetDistance != -1f && debug == true) { Vector3 targetToOrigin = (transform.position - currentTarget.transform.position).normalized; Vector3 runawayPos = targetToOrigin * (runAwayDistance / 2); Debug.DrawRay(transform.position, runawayPos, Color.yellow, 0.01f); } } [ServerCallback] // Update is called once per frame public override void FixedUpdate() { base.FixedUpdate(); } [ServerCallback] public override void OnNavigateWithTarget() { targetDistance = Vector3.Distance(transform.position, currentTarget.transform.position); if (targetDistance >= 0 && targetDistance <= attackRange) { if(targetDistance attackRange) { SetDestination(currentTarget.transform.position); } } [ServerCallback] public void Runaway() { // Draws a vector from target to this enemy, and increases length of vector by 1.5. Vector3 targetToOrigin = (transform.position - currentTarget.transform.position).normalized; Vector3 runawayPos = targetToOrigin * (runAwayDistance / 2) + transform.position; if(debug) Debug.DrawLine(runawayPos, runawayPos + new Vector3(0, 5, 0), Color.magenta, 0.5f); SetDestination(runawayPos); } public override void OnDrawGizmosSelected() { if(debug) { base.OnDrawGizmosSelected(); Gizmos.color = Color.red; Gizmos.DrawWireSphere(transform.position, runAwayDistance); } } }
SoulController.cs // A Pawn variant that is an ally to the player during teleporter events, aiding in the destruction of the teleporter turret. public class SoulController : Pawn { [Header("Soul Settings")] public float Damage = 5f; public float FiringRange = 25f; public float FiringRate = 1.0f; [Header("References")] public GameObject AttackPrefab = null; [HideInInspector] public Turret target = null; private bool InFiringMode = false; // Start is called before the first frame update public override void Start() { base.Start(); animator.animator.speed = FiringRate; } // Update is called once per frame public override void Update() { base.Update(); if(target != null && InFiringMode == false) { if (Vector3.Distance(target.transform.position, transform.position) <= FiringRange) { SwitchToFiringMode(); } } } [ServerCallback] public void Server_Fire() { if (target == null) return; else { Rpc_Fire(target.gameObject); } } [ClientRpc] public void Rpc_Fire(GameObject target_) { GameObject spawnedAbility = Instantiate(AttackPrefab); spawnedAbility.transform.position = transform.position; AbilitySpawnable abilityCtrl = spawnedAbility.GetComponent(); abilityCtrl.damage = Damage; abilityCtrl.startLocation = transform.position; abilityCtrl.StartCoroutine(abilityCtrl.Initialize_TargetLock(target_.GetComponent().EjectionPoint.gameObject)); } // Must be spawned with a turret target public void OnSpawned(Turret target_) { target = target_; if(isServer) SetDestination(target_.transform.position); } public void SwitchToFiringMode() { if(isServer) SetDestination(transform.position); InFiringMode = true; animator.animator.SetBool("Firing", true); } [ServerCallback] public override void Server_OnDeath(GameObject dealtBy) { base.Server_OnDeath(dealtBy); } public override void Rpc_OnDeath(GameObject dealtBy) { base.Rpc_OnDeath(dealtBy); target.teleporter.soulsNearby.Remove(this); gameObject.SetActive(false); if (healthBar != null) Destroy(healthBar.gameObject); Invoke("Die", 5.0f); } private void Die() { if (isServer) NetworkServer.Destroy(gameObject); else { Destroy(gameObject); } } private void OnDrawGizmosSelected() { Gizmos.color = Color.green; Gizmos.DrawWireSphere(transform.position, FiringRange); } }