We have answer of your question!

100% solved queries, no empty question

0

I was working on massive collision detection for my game(more than 1000 sprites is massive for my game), and i was searching to find a way to implement this, then i reached to quad tree:

http://en.wikipedia.org/wiki/Quadtree

Well it's approach to reduce the number of objects that should be check for collision by dividing them to the groups of objects which have more chance to collide. I found a java version of quad tree here:

http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Then i change it and use it for my javafx game. but the performance wasn't really good for huge number of objects, so i made some optimisation on it.

Question author Eeliya | Source

Answer


1


Well i used AnimationTimer for each tree to check for collisions which has improved performance so much. i think Animation Timer use GPU to process because when i run my code CPU usage doesn't go hight(3% to 5% - 1640 sprites). but if i use Thread instead of AnimationTimer it use much more CPU(about 40% to 50% - 1640 sprites).

import java.util.ArrayList;
import java.util.List;
import javafx.animation.AnimationTimer;
import javafx.scene.layout.Region;
import javafx.scene.layout.RegionBuilder;
import javafx.scene.paint.Color;
import viwofx.sprit.Sprite;
import viwofx.ui.GameScene;

public class QuadTree
{

  private int MAX_OBJECTS = 10;
  private int MAX_LEVELS = 5;
  private int level;
  private ArrayList<Sprite> sprites;
  private ArrayList<Sprite> unAllocatedSprites;
  private Region bounds;
  private QuadTree[] nodes;
  private QuadTree parent;
  private AnimationTimer detection;
  private boolean detecting = false;

  private QuadTree getqt()
  {
    return this;
  }

  public QuadTree(QuadTree p, int pLevel, Region pBounds)
  {
    this.parent = p;
    level = pLevel;
    sprites = new ArrayList<>(0);
    unAllocatedSprites = new ArrayList<>(0);
    bounds = pBounds;
    nodes = new QuadTree[4];

    detection = new AnimationTimer()
    {
      @Override
      public void handle(long l)
      {
        // This for happens when this node has child nodes and there is some object which can not fit whitin the bounds of child nodes
        // these object being checked till they can fit inside the bounds of child nodes then they will be added to correspinding child node,
        // or object is out of bounds then it will be pushed to the parent node
        for (int i = 0; i < unAllocatedSprites.size(); i++)
        {
          if (!isInside(unAllocatedSprites.get(i)))
          {

            pushToParent(unAllocatedSprites.get(i));
            continue;
          }
          int index = getIndex(unAllocatedSprites.get(i));
          if (index != -1)
          {
            nodes[index].add(unAllocatedSprites.remove(i));
          }
        }
        for (int i = 0; i < sprites.size(); i++)
        {
          Sprite ts = sprites.get(i);
          if (isInside(ts))
          {
            int ii = 0;
            for (ii = 0; ii < sprites.size(); ii++)
            {
              Sprite ts2 = sprites.get(ii);
              if (ts != ts2)
              {
                Your collision detection logic
              }
            }
            if (parent != null)
            {
              for (ii = 0; ii < parent.getUnAllocatedSprites().size(); ii++)
              {
                Sprite ts2 = parent.getUnAllocatedSprites().get(ii);
                if (ts != ts2 && isInside(ts2))
                {
                  Your collision detection logic
                }
              }
            }
          }
          else
          {
            pushToParent(ts);
          }
        }
      }
    };
  }

  public int getLevel()
  {
    return level;
  }

  public ArrayList<Sprite> getUnAllocatedSprites()
  {
    return unAllocatedSprites;
  }

  // Split the node into 4 subnodes
  private void split()
  {
    double subWidth = (bounds.getPrefWidth() / 2);
    double subHeight = (bounds.getPrefHeight() / 2);
    double x = bounds.getLayoutX();
    double y = bounds.getLayoutY();

    nodes[0] = new QuadTree(this, level + 1, RegionBuilder.create().layoutX(x).layoutY(y).prefWidth(subWidth).prefHeight(subHeight).build());
    nodes[1] = new QuadTree(this, level + 1, RegionBuilder.create().layoutX(x + subWidth).layoutY(y).prefWidth(subWidth).prefHeight(subHeight).build());
    nodes[2] = new QuadTree(this, level + 1, RegionBuilder.create().layoutX(x).layoutY(y + subHeight).prefWidth(subWidth).prefHeight(subHeight).build());
    nodes[3] = new QuadTree(this, level + 1, RegionBuilder.create().layoutX(x + subWidth).layoutY(y + subHeight).prefWidth(subWidth).prefHeight(subHeight).build());
  }

  private int getIndex(Sprite s)
  {
    int index = -1;

    double verticalMidpoint = bounds.getLayoutX() + (bounds.getPrefWidth() / 2);
    double horizontalMidpoint = bounds.getLayoutY() + (bounds.getPrefHeight() / 2);
    double spriteMaxX = (s.getNode().getTranslateX() + s.getWidth());
    double spriteMaxY = (s.getNode().getTranslateY() + s.getHeight());

    // Object can completely fit within the top quadrants
    boolean topQuadrant = (spriteMaxY < horizontalMidpoint);
    // Object can completely fit within the bottom quadrants
    boolean bottomQuadrant = (s.getNode().getTranslateY() >= horizontalMidpoint);

    // Object can completely fit within the left quadrants
    if (s.getNode().getTranslateX() >= bounds.getLayoutX() && spriteMaxX < verticalMidpoint)
    {
      if (topQuadrant)
      {
        index = 0;
      }
      else if (bottomQuadrant)
      {
        index = 2;
      }
    }
    // Object can completely fit within the right quadrants
    else if (s.getNode().getTranslateX() >= verticalMidpoint && (s.getNode().getTranslateX() + s.getWidth()) < (bounds.getLayoutX() + bounds.getPrefWidth()))
    {
      if (topQuadrant)
      {
        index = 1;
      }
      else if (bottomQuadrant)
      {
        index = 3;
      }
    }

    return index;
  }

  public boolean isInside(Sprite s)
  {
    double maxX = bounds.getLayoutX() + bounds.getPrefWidth();
    double maxY = bounds.getLayoutY() + bounds.getPrefHeight();

    // Object can completely fit within the left quadrants
    if (s.getNode().getTranslateX() >= bounds.getLayoutX() && (s.getNode().getTranslateX() + s.getWidth()) < maxX && s.getNode().getTranslateY() >= bounds.getLayoutY() && (s.getNode().getTranslateY() + s.getHeight()) < maxY)
    {
      return true;
    }
    if (parent != null && parent.getUnAllocatedSprites().contains(s))
    {
      return true;
    }
    return false;

  }

  public void pushToParent(Sprite s)
  {
    sprites.remove(s);
    unAllocatedSprites.remove(s);
    if (parent == null)
    {

      //System.out.println("parent");
      if (!unAllocatedSprites.contains(s))
      {
        unAllocatedSprites.add(s);
      }
      return;
    }

    parent.add(s);
    if (sprites.size() < 1 && unAllocatedSprites.size() < 1)
    {
      stopDetection();
    }
  }

  public void add(viwofx.sprit.Sprite sprite)
  {
    // if sprite is not fit in the bounds of node, it will be pushed to the parent node.
    // this is a optimization for when child node push a object to this node and object still is not fit in the bounds this node, 
    // so it will be pushed to the parent node till object can be fited whitin the node bounds
    // this if prevent of out of bounds object to being added to unAllocatedSprites and then being pushed to parent
    if (!isInside(sprite))
    {
      pushToParent(sprite);
      return;
    }
    // if tree has been splited already add sprite to corrosponding child
    if (nodes[0] != null)
    {
      int index = getIndex(sprite);
      if (index != -1)
      {
        nodes[index].add(sprite);
        return;
      }
      else
      {
        unAllocatedSprites.add(sprite);
        return;
      }
    }

    sprites.add(sprite);
    if (!detecting)
    {
      startDetection();
    }

    if (sprites.size() > MAX_OBJECTS && level < MAX_LEVELS)
    {
      if (nodes[0] == null)
      {
        split();
      }
      int i = 0;
      while (i < sprites.size())
      {
        int index = getIndex(sprites.get(i));
        if (index != -1)
        {
          nodes[index].add(sprites.remove(i));
        }
        else
        {
          unAllocatedSprites.add(sprites.remove(i));
        }
      }
    }
  }

  public List<Sprite> retrieve(List<Sprite> returnObjects, Sprite pRect)
  {
    int index = getIndex(pRect);
    if (index != -1 && nodes[0] != null)
    {
      nodes[index].retrieve(returnObjects, pRect);
    }
    returnObjects.addAll(sprites);
    return returnObjects;
  }

  public void startDetection()
  {
    detecting = true;
    detection.start();        
  }

  public void stopDetection()
  {
    //detecting = false;
    //detection.stop();
  }
}

I hope this will be helpful for you.

Answer author Eeliya

Tickanswer.com is providing the only single recommended solution of the question JavaFX: Massive collision detection optimization (Quad Tree) under the categories i.e javafx-2 , collision-detection , game-engine , quadtree , . Our team of experts filter the best solution for you.

Related Search Queries:


You may also add your answer

Thanks for contributing an answer to Tick Answer!