quadnode.java

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

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

     // QuadTree结构中的一个节点
     public class QuadNode extends Object
     {
          // 分配给节点的下一个唯一id
          protected static int UNIQUE_ID = 0;

          // 标志这个节点的唯一整数
          protected int id;

          // 包含这个节点的父节点
          protected QuadNode parent;

          // 这个QuadNode的孩子节点数组
          protected QuadNode[] nodes;

          // 如果这个节点为叶子节点则为true (没有孩子节点)
          protected boolean leaf;

          // 这个节点所包含物体的链表
          protected LinkedList objects;

          // 节点边界
          protected Rectangle2D bounds;

          // 默认构造函数
          private QuadNode()
          {
               id = -1;
               parent  = null;
               nodes   = null;
               leaf    = true;
               objects = null;
               bounds  = null;
          }

          // 给定父亲、深度和边界构建一个QuadNode
          public QuadNode(QuadNode p, int depth, Rectangle2D r)
          {
               parent = p;
               bounds = r;

               id = UNIQUE_ID++;

               // 如果剩余的深度为零则这个节点为叶子节点
               if(depth == 0)
               {
                    leaf = true;
                    objects = new LinkedList();
                    nodes = null;

                    QuadTree.addLeaf(this);
               }

               // 否则这个节点包含4个孩子节点                
               else
               {
                    leaf = false;
                    objects = null;

                    nodes = new QuadNode[4];
                    double x = bounds.getX();
                    double y = bounds.getY();
                    double w = bounds.getWidth();
                    double h = bounds.getHeight();

                    // 创建孩子
                    nodes[0] = new QuadNode(this, depth - 1, new Rectangle2D.Double(x,       y + h/2, w/2, h/2));
                    nodes[1] = new QuadNode(this, depth - 1, new Rectangle2D.Double(x + w/2, y + h/2, w/2, h/2));
                    nodes[2] = new QuadNode(this, depth - 1, new Rectangle2D.Double(x + w/2, y      , w/2, h/2));
                    nodes[3] = new QuadNode(this, depth - 1, new Rectangle2D.Double(x,       y,       w/2, h/2));
               }
          }

          // 如果这个节点是叶子节点则返回true
          public final boolean isLeaf()
          {
               return leaf;
          }

          // 尝试将一个传入的物体插入到这个节点中
          public void insert(
               Moveable c,       // 要插入的Moveable物体
               boolean propagate // 如果为真,则在c不在这个节点的边界内时向上一级插
               )
          {
               // 尝试插入
               if(bounds.contains(c.getBounds()) || bounds.intersects(c.getBounds()))
               {
                    // 如果这个节点是一个叶子节点,则将物体插入链表中
                    if(isLeaf())
                    {
                         if(objects == null)
                         {
                              objects = new LinkedList(); 
                         }
                         if(! objects.contains(c))
                         {
                              objects.add(c);
                         }
                    }

                    // 如果这个节点不是叶子节点则继续向下一层插
                    else
                    {
                         for(int i = 0; i < 4; i++)
                         {
                              if(nodes[i] != null)
                              {
                                   nodes[i].insert(c, false);
                              }
                         }
                    }
               }

               // 否则,在允许的情况下向上一级插入物体
               else
               {
                    if(propagate)
                    {
                         if(parent != null)
                         {
                              parent.insert(c, true);
                         }
                    } 
               }
          } 

          // 将这个节点所包含的所有物体平移x,y         
          public void moveAll(double x, double y)
          {
               if(objects == null || objects.isEmpty()) return;
 
               Actor2D a;
               for(int i = 0; i < objects.size(); i++)
               {
                    a = (Actor2D) objects.get(i);
                    a.moveBy(x, y);
               }
          }

          public void update()
          {
               if(objects == null || objects.isEmpty()) return;

               // 更新链表,将不再被这个节点包含的物体删除
               Moveable m;
               for(int i = 0; i < objects.size(); i++)
               {
                    m = (Moveable)objects.get(i);
                    m.update();

                    // 测试物体是否离开这个节点;如果是的话,向上一级插
                    if(!bounds.contains(m.getBounds()) && !bounds.intersects(m.getBounds())) // 可以向上插
                    {
                         insert((Moveable)objects.remove(i), true);
                    }
               }

               // 因为可能有物体已经被删除,所以需要获得更新后的大小
               int size = objects.size();

               // 检测这个节点之内物体之间的冲突
               for(int i = 0; i < size-1; i++)
               {
                    Moveable a = (Moveable)objects.get(i);

                    for(int j = i+1; j < size; j++)
                    { 
                         Moveable b = (Moveable)objects.get(j);

                         if(a.collidesWith(b))
                         {
                              a.addCollision(b);
                              b.addCollision(a);
                         }
                    }
               }
          }

          public void paintBounds(Graphics2D g2d, Color c)
          {
               if(c == null) c = Color.RED;
               g2d.setPaint(c);
               g2d.draw(bounds);
          }

     }    // QuadNode