From a question I posted, a gentleman suggested that I ask on the forums.
http://answers.unity3d.com/questions/882719/barnes-hut.html
Ok I found The Barnes-Hut Galaxy Simulator which actually is quite helpful. I am reading up on quad trees and im just wondering if unity has such a data structure?
Ok I honestly at this point have no idea how to implement this. I understand how it works however coding it seems to be a major problem (the quadtree). The force of gravity and center of mass part is very simple which I already done but brute forcing is causing it to be pretty inefficient (O(N^2))
How many objects are you aiming for?
Well if I have 1000 stars that is at most about 10000 planets and 50000 moons therefore, 61000 objects. This number would be much smaller of course but Barnes-hut should be able to easily handle that amount.
I think the confusion comes from the quad tree itself but I can’t find any code or good articles that I can study. They all seem to be conceptual or I’m not a good google searcher… I don’t want any exact implementation just some detailed articles or tutorials so I can learn the material by filling in the blank (for example pseudo code)
http://www.flipcode.com/archives/Octree_Implementation.shtml
You can easily convert this to c#
Does it have to work in real time? I suspect even with Barnes-hut it would be possible in real time for 61000 particles.
Ok I looked at a java implementation and rewrote the BarnesHut to work with my main NBody gravity manager for all of my objects. I get performance issues for a few seconds due to probably loading the tree and stack-overflow error at x>~700 objects(mono-develop points to the insert function of the BarnesHutTree class when overflow happens). I think the tree’s recursion might never end so its quickly using up all memory.
And Yes…Real Time
Im going to try out the link TiG, Thanks!
Code
using UnityEngine;
using System.Collections;
using BHTree;
namespace BHTree
{
public class BarnesHutTree
{
public double Theta = 0.1;
public Body body;
public Quad quad;
public BarnesHutTree NW;
public BarnesHutTree NE;
public BarnesHutTree SW;
public BarnesHutTree SE;
public BarnesHutTree(Quad quad)
{
this.quad = quad;
this.body = null;
this.NW = null;
this.NE = null;
this.SW = null;
this.SE = null;
}
public void insert(Body b)
{
if(this.body == null)
{
body = b;
return;
}
if(! isExternal())
{
body = body.plus(b);
putBody(b);
}
else
{
NW = new BarnesHutTree(quad.NW());
NE = new BarnesHutTree(quad.NE());
SE = new BarnesHutTree(quad.SE());
SW = new BarnesHutTree(quad.SW());
// recursively insert both this body and Body b into the appropriate quadrant
putBody(this.body);
putBody(b);
// update the center-of-mass and total mass
body = body.plus(b);
}
}
public void putBody(Body b)
{
if (b.inCheck(quad.NW()))
NW.insert(b);
else if (b.inCheck(quad.NE()))
NE.insert(b);
else if (b.inCheck(quad.SE()))
SE.insert(b);
else if (b.inCheck(quad.SW()))
SW.insert(b);
}
public bool isExternal() {
// a node is external iff all four children are null
return (NW == null && NE == null && SW == null && SE == null);
}
public void updateForce(Body b)
{
if (body == null || b.Equals(body))
return;
// if the current node is external, update net force acting on b
if (isExternal())
b.addForce(body);
// for internal nodes
else {
// width of region represented by internal node
double s = quad.getLength();
// distance between Body b and this node's center-of-mass
double d = body.distanceTo(b);
// compare ratio (s / d) to threshold value Theta
if ((s / d) < Theta)
b.addForce(body); // b is far away
// recurse on each of current node's children
else {
NW.updateForce(b);
NE.updateForce(b);
SW.updateForce(b);
SE.updateForce(b);
}
}
}
}
public class Quad
{
public double xmid;
public double ymid;
public double length;
public Quad(double xmid, double ymid, double length)
{
this.xmid = xmid;
this.ymid = ymid;
this.length = length;
}
public double getLength()
{
return length;
}
public bool contains(double x, double y)
{
double halfLen = this.length / 2.0;
return (x <= this.xmid + halfLen &&
x >= this.xmid - halfLen &&
y <= this.ymid + halfLen &&
y >= this.ymid - halfLen);
}
public Quad NW()
{
double x = this.xmid - this.length / 4.0;
double y = this.ymid + this.length / 4.0;
double len = this.length / 2.0;
Quad NW = new Quad(x, y, len);
return NW;
}
public Quad NE()
{
double x = this.xmid + this.length / 4.0;
double y = this.ymid + this.length / 4.0;
double len = this.length / 2.0;
Quad NE = new Quad(x, y, len);
return NE;
}
public Quad SW()
{
double x = this.xmid - this.length / 4.0;
double y = this.ymid - this.length / 4.0;
double len = this.length / 2.0;
Quad SW = new Quad(x, y, len);
return SW;
}
public Quad SE()
{
double x = this.xmid + this.length / 4.0;
double y = this.ymid - this.length / 4.0;
double len = this.length / 2.0;
Quad SE = new Quad(x, y, len);
return SE;
}
}
public class Body
{
public double G;
public double rx, ry; // position
public double fx, fy; // force
public double mass; // mass
public Body(double rx, double ry, double mass, double G)
{
this.rx = rx;
this.ry = ry;
this.mass = mass;
this.G = G;
}
public void update(double rx, double ry)
{
this.rx = rx;
this.ry = ry;
}
public double distanceTo(Body b)
{
double dx = rx - b.rx;
double dy = ry - b.ry;
return Mathf.Sqrt((float)(dx*dx + dy*dy));
}
public void resetForce()
{
fx = 0.0;
fy = 0.0;
}
public void addForce(Body b)
{
if(distanceTo(b) > 0.75f)
{
Body a = this;
double dx = b.rx - a.rx;
double dy = b.ry - a.ry;
double dist = Mathf.Sqrt((float)(dx*dx + dy*dy));
double F = (G * a.mass * b.mass) / (dist*dist);
a.fx += F * dx / dist;
a.fy += F * dy / dist;
}
}
public bool inCheck(Quad q)
{
return q.contains(this.rx, this.ry);
}
public Body plus(Body b)
{
Body a = this;
double m = a.mass + b.mass;
double x = (a.rx * a.mass + b.rx * b.mass) / m;
double y = (a.ry * a.mass + b.ry * b.mass) / m;
return new Body(x, y, m, a.G);
}
}
}
More Code
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using BHTree;
public class NBody : MonoBehaviour {
public GameObject planetPrefab01;
public double dt = 0.1;
public double radius = 1000;
public int N = 5;
public double G = 1;
private Body[] nBodies;
private GameObject[] pBodies;
void Start()
{
Initialize();
}
void FixedUpdate()
{
Quad quad = new Quad(0, 0, radius * 2);
BarnesHutTree tree = new BarnesHutTree(quad);
pBodies = GameObject.FindGameObjectsWithTag("Celestial Object");
for(int i = 0; i < N; i++)
{
if(nBodies[i].inCheck(quad))
{
tree.insert(nBodies[i]);
}
}
for(int i = 0; i < N; i++)
{
nBodies[i].resetForce();
tree.updateForce(nBodies[i]);
nBodies[i].update(pBodies[i].transform.position.x, pBodies[i].transform.position.y);
}
for(int i = 0; i < N; i++)
{
Vector2 force = new Vector2((float)nBodies[i].fx, (float)nBodies[i].fy);
pBodies[i].rigidbody2D.AddForce(force);
}
}
void Initialize()
{
List<int> places = new List<int>();
bool check = true;
for(int i = 0; i < N; i++)
{
check = true;
while(check)
{
int x = Random.Range(0,(int)radius);
int y = Random.Range(0,(int)radius);
if(!places.Contains(x + y))
{
places.Add(x + y);
Instantiate(planetPrefab01, new Vector3(x, y) , Quaternion.identity);
check = false;
}
}
}
pBodies = GameObject.FindGameObjectsWithTag("Celestial Object");
nBodies = new Body[N];
for(int i = 0; i < N; i++)
{
double px = pBodies[i].transform.position.x;
double py = pBodies[i].transform.position.y;
double mass = pBodies[i].rigidbody2D.mass;
nBodies[i] = new Body(px, py, mass, G);
}
}
}