From efdd8f483157ceeb1bae535840934ac770126a28 Mon Sep 17 00:00:00 2001 From: David Gow Date: Sat, 4 Oct 2014 18:42:33 +0800 Subject: [PATCH] Panning for gold, with the Quadtree! Sulix celebrates the panning in the quadtree finally working* with the worst pun yet! * The segfault doesn't count. --- src/quadtree.cpp | 6 +++ src/view.cpp | 112 ++++++++++++++++++++++++----------------------- 2 files changed, 63 insertions(+), 55 deletions(-) diff --git a/src/quadtree.cpp b/src/quadtree.cpp index 3d5dbee..b84bb78 100644 --- a/src/quadtree.cpp +++ b/src/quadtree.cpp @@ -70,6 +70,12 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Do { if (!xdir && !ydir) return start; + if (addTo && (nodes[start].parent == -1) && nodes[start].child_type != QTC_UNKNOWN) + { + Debug("Adding parent of node %d...", start); + addTo->GenQuadParent(start, nodes[start].child_type); + } + QuadTreeIndex newNode; // Try moving to the right if that's easy. if (xdir > 0) diff --git a/src/view.cpp b/src/view.cpp index 53511d2..5acd860 100644 --- a/src/view.cpp +++ b/src/view.cpp @@ -207,11 +207,24 @@ void View::Render(int width, int height) m_cached_display.Clear(); #ifndef QUADTREE_DISABLED + // I'm going to write this out in comments, so hopefully then I'll understand it. :/ + // + // This code looks at the current bounds and tries to work out how they need to change + // to keep the view looking at the correct quadtree node. + // + // The idea is that the width/height of the view bounds are always 0.5<=wh<=1.0. We then always + // try to keep the bottom-right corner of the node on-screen, changing nodes to suit. Why bottom-right, + // you may ask. It's an excellent question, with a dubious, hand-wavey answer: because we're manipulating + // the bounds, it was easier to do it that way. (The top-left corner of the bounds are within the main + // quadtree node). if (m_bounds_dirty || !m_lazy_rendering) { + // If we're too far zoomed out, become the parent of the current node. if ( m_bounds.w > 1.0 || m_bounds.h > 1.0) { - //TODO: Generate a new parent node. + // If a parent node exists, we'll become it. + //TODO: Generate a new parent node if none exists, and work out when to change child_type + // away from QTC_UNKNOWN if (m_document.GetQuadTree().nodes[m_current_quadtree_node].parent != QUADTREE_EMPTY) { m_bounds = TransformFromQuadChild(m_bounds, m_document.GetQuadTree().nodes[m_current_quadtree_node].child_type); @@ -219,31 +232,34 @@ void View::Render(int width, int height) } } - // TODO: Support generating new parent nodes. - if (false && m_document.GetQuadTree().nodes[m_current_quadtree_node].parent != QUADTREE_EMPTY) + // If we have a parent... (This prevents some crashes, but should disappear.) + if (m_document.GetQuadTree().nodes[m_current_quadtree_node].parent != QUADTREE_EMPTY) { - if (m_bounds.x < -0.5) - { - m_bounds = Rect(m_bounds.x + 1, m_bounds.y, m_bounds.w, m_bounds.h); - m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, -1, 0, &m_document); - } - if (m_bounds.y < -0.5) - { - m_bounds = Rect(m_bounds.x, m_bounds.y + 1, m_bounds.w, m_bounds.h); - m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 0, -1, &m_document); - } - if (m_bounds.w + m_bounds.x > 0.5) + // If the current node is off the left-hand side of the screen... + while (m_bounds.x > 1) { + //... the current node becomes the node to its right. m_bounds = Rect(m_bounds.x - 1, m_bounds.y, m_bounds.w, m_bounds.h); m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 1, 0, &m_document); } - if (m_bounds.h + m_bounds.y > 0.5) + while (m_bounds.y > 1) { m_bounds = Rect(m_bounds.x, m_bounds.y - 1, m_bounds.w, m_bounds.h); m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 0, 1, &m_document); } + while (m_bounds.x < 0) + { + m_bounds = Rect(m_bounds.x + 1, m_bounds.y, m_bounds.w, m_bounds.h); + m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, -1, 0, &m_document); + } + while (m_bounds.y < 0) + { + m_bounds = Rect(m_bounds.x, m_bounds.y + 1, m_bounds.w, m_bounds.h); + m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 0, -1, &m_document); + } } + // Recurse into a node if we are completely within it. (If we're okay with having an invalid frame or two, we can remove this.) if (ContainedInQuadChild(m_bounds, QTC_TOP_LEFT)) { if (m_document.GetQuadTree().nodes[m_current_quadtree_node].top_left == QUADTREE_EMPTY) @@ -288,6 +304,20 @@ void View::Render(int width, int height) m_bounds = TransformToQuadChild(m_bounds, QTC_BOTTOM_RIGHT); m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].bottom_right; } + + // Otherwise, we'll arbitrarily select the bottom-right. + // TODO: Perhaps select based on greatest area? + if (m_bounds.w < 0.5 || m_bounds.h < 0.5) + { + if (m_document.GetQuadTree().nodes[m_current_quadtree_node].bottom_right == QUADTREE_EMPTY) + { + // We want to reparent into a child node, but none exist. Get the document to create one. + m_document.GenQuadChild(m_current_quadtree_node, QTC_BOTTOM_RIGHT); + m_render_dirty = true; + } + m_bounds = TransformToQuadChild(m_bounds, QTC_BOTTOM_RIGHT); + m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].bottom_right; + } } m_screen.DebugFontPrintF("Current View QuadTree"); @@ -299,6 +329,12 @@ void View::Render(int width, int height) overlay = m_document.GetQuadTree().nodes[overlay].next_overlay; } m_screen.DebugFontPrintF("\n"); + m_screen.DebugFontPrintF("Left: %d, Right: %d, Up: %d, Down: %d\n", + m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, -1, 0, 0), + m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 1, 0, 0), + m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 0, -1, 0), + m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 0, 1, 0)); + Rect view_top_bounds = m_bounds; QuadTreeIndex tmp = m_current_quadtree_node; @@ -355,6 +391,7 @@ void View::RenderQuadtreeNode(int width, int height, QuadTreeIndex node, int rem if (!remaining_depth) return; //Debug("Rendering QT node %d, (objs: %d -- %d)\n", node, m_document.GetQuadTree().nodes[node].object_begin, m_document.GetQuadTree().nodes[node].object_end); m_bounds_dirty = true; + m_render_dirty = m_buffer_dirty = true; QuadTreeIndex overlay = node; while(overlay != -1) { @@ -362,62 +399,27 @@ void View::RenderQuadtreeNode(int width, int height, QuadTreeIndex node, int rem overlay = m_document.GetQuadTree().nodes[overlay].next_overlay; } - if (m_bounds.Intersects(Rect(-1,-1,1,1))) + if (m_bounds.Intersects(Rect(1,1,1,1))) { m_bounds = Rect(m_bounds.x - 1, m_bounds.y - 1, m_bounds.w, m_bounds.h); m_bounds_dirty = true; - RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, -1, &m_document), remaining_depth - 1); + RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, 1, &m_document), remaining_depth - 1); } m_bounds = old_bounds; - if (m_bounds.Intersects(Rect(-1,0,1,1))) + if (m_bounds.Intersects(Rect(1,0,1,1))) { m_bounds = Rect(m_bounds.x - 1, m_bounds.y, m_bounds.w, m_bounds.h); m_bounds_dirty = true; - RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, 0, &m_document), remaining_depth - 1); - } - m_bounds = old_bounds; - if (m_bounds.Intersects(Rect(-1,1,1,1))) - { - m_bounds = Rect(m_bounds.x - 1, m_bounds.y + 1, m_bounds.w, m_bounds.h); - m_bounds_dirty = true; - RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, 1, &m_document), remaining_depth - 1); - } - m_bounds = old_bounds; - if (m_bounds.Intersects(Rect(0,-1,1,1))) - { - m_bounds = Rect(m_bounds.x, m_bounds.y - 1, m_bounds.w, m_bounds.h); - m_bounds_dirty = true; - RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 0, -1, &m_document), remaining_depth - 1); + RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, 0, &m_document), remaining_depth - 1); } m_bounds = old_bounds; if (m_bounds.Intersects(Rect(0,1,1,1))) { - m_bounds = Rect(m_bounds.x, m_bounds.y + 1, m_bounds.w, m_bounds.h); + m_bounds = Rect(m_bounds.x, m_bounds.y - 1, m_bounds.w, m_bounds.h); m_bounds_dirty = true; RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 0, 1, &m_document), remaining_depth - 1); } m_bounds = old_bounds; - if (m_bounds.Intersects(Rect(1,-1,1,1))) - { - m_bounds = Rect(m_bounds.x + 1, m_bounds.y - 1, m_bounds.w, m_bounds.h); - m_bounds_dirty = true; - RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, -1, &m_document), remaining_depth - 1); - } - m_bounds = old_bounds; - if (m_bounds.Intersects(Rect(1,0,1,1))) - { - m_bounds = Rect(m_bounds.x + 1, m_bounds.y, m_bounds.w, m_bounds.h); - m_bounds_dirty = true; - RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, 0, &m_document), remaining_depth - 1); - } - m_bounds = old_bounds; - if (m_bounds.Intersects(Rect(1,1,1,1))) - { - m_bounds = Rect(m_bounds.x + 1, m_bounds.y + 1, m_bounds.w, m_bounds.h); - m_bounds_dirty = true; - RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, 1, &m_document), remaining_depth - 1); - } - m_bounds = old_bounds; m_bounds_dirty = true; #if 0 -- 2.20.1