quadtree.java

java learn PPT java learn PPT java learn PPT java learn PPT

     package magic.scene;

     import java.awt.*;
     import java.awt.geom.*;
     import java.util.*;

     import magic.actor2d.*;

     // 四方树管理体系中的根节点
     public class QuadTree extends QuadNode
     {
          // 树的总体深度
          protected int globalDepth;

          // 叶子节点的全局链表
          public static LinkedList leaves = new LinkedList();

          // global linked list of objects that will be painted
          public static LinkedList paintList = new LinkedList();

          // creates a QuadTree with the sent depth, overall bounds, and viewable screen bounds
          public QuadTree(int depth, Rectangle2D r)
          {
               super(null, depth, r);

               // global depth must be greater than zero
               if(depth <= 0)
               {
                    throw new IllegalArgumentException("depth must be greater than zero");
               }

               globalDepth = depth;

               // initialize the overflow list
               objects = new LinkedList();
          }

          // adds a leaf node to the global leaf list
          public static void addLeaf(QuadNode node)
          {
               if(! leaves.contains(node))
               {
                    leaves.add(node);
               }
          }

          // adds a Moveable object to the global paint list
          public static void addToPaintList(Moveable m)
          {
               if(! paintList.contains(m))
               {
                    paintList.add(m);
               }
          }

          // QuadTree must override insert method to deal with objects that are not within
          // scene bounds
          public void insert(Moveable c)
          {
               // if the object is not within scene bounds, add it to the heap
               if(! bounds.contains(c.getBounds()) && ! bounds.intersects(c.getBounds()))
               {
                    if(! objects.contains(c))
                    {
                         objects.add(c);
                    }
                    return;
               }

               // add the object to the global paint list
               addToPaintList(c);

               // try adding the object to all child nodes
               for(int i = 0; i < 4; i++)
               {
                    if(nodes[i] != null)
                    {
                         nodes[i].insert(c, false);
                    }
               }
          }

          public void update()
          {
               // update the heap list
               if(objects != null && !objects.isEmpty())
               {
                    for(int i = 0; i < objects.size(); i++)
                    {
                         Moveable a = (Moveable) objects.get(i);
                         a.update();

                         // test if the object entered the tree; if so, insert it and remove it
                         // from the heap
                         if(bounds.contains(a.getBounds()) || bounds.intersects(a.getBounds()))
                         {
                              insert((Moveable) objects.remove(i), false);
                         }
                     }
               }

               //  update all leaf nodes for collisions and frame movement
               for(int i = 0; i < leaves.size(); i++)
               {
                    ((QuadNode) leaves.get(i)).update();
               }
          }

          // paints all objects in the global paint list
          public void paint(Graphics2D g2d)
          {
               Actor2D a;
               for(int i = 0; i < paintList.size(); i++)
               {
                    a = (Actor2D) paintList.get(i);
                    // only paint the object if it is in bounds
                    if(bounds.contains(a.getBounds()) || bounds.intersects(a.getBounds()))
                    {
                         a.paint(g2d);
                    }
               }
          }

          // paints gridlines showing the bounds of each leaf node
          public void paintBounds(Graphics2D g2d, Color color)
          {
               // paint all leaf nodes
               for(int i = 0; i < leaves.size(); i++)
               {
                    ((QuadNode)leaves.get(i)).paintBounds(g2d, color);
               }
          }

     }    // QuadTree