• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
FuraProject

Orbit (ellipse) collision detection between many many objects

8 posts in this topic

Afternoon

 

Back in University, in math classes, i remember studying something about defining ellipses in expressions, but i don't remember much of that.

 

Recently i had an idea and would like to test out some mechanics first, if its even possible to accomplish my goals.

 

Tho the trick is, i need loads (5k+) of spheres moving around other spheres and i want to check collision between them. Checking collision between each sphere will be... pain for cpu. Especially on tablet devices and phones.

 

So i thought that splitting them into regions, and then checking collisions in one region would be enough. But one object can pass through many regions.

 

Then i thought that maybe it would be possible to use such thing:

a) Create object

b) Define orbit ellipse in expression

c) Traverse tree of sphere objects to find potential collision targets

d) Calculate time when both will collide

 

Is such thing possible, or i am looking for an easy way?

 

0

Share this post


Link to post
Share on other sites
Two spheres moving on two elliptical orbits may collide even if the two orbits do not intersect. You thus have to somewhat compute the intersection of two tori (this is how mathematicians call donuts-like surfaces). Moreover, intersection "times" will be periodical and they will depend on the parametrization of both ellipses. It looks like you will have to maintain and work with a quite complicated data structure.

I think it is better to simply compute the intersections between the spheres (maybe using some kind of spatial acceleration structure or the GPU).
1

Share this post


Link to post
Share on other sites

As apatriarca said, two spheres may collide even if their orbits don't intersect (and in reality orbits in 3d, which are just lines, will rarely intersect, unless you impose restriction of being on the same plane).

 

But you can do a sort of hybrid approach with the region idea you mentioned originally. There's two ways I can think of, off the top of my head, depending on how much data overhead you can afford.

 

One is to separate your space into an imaginary rectangular grid, where each cell is size NxNxN. Then, at startup, traverse the orbit of each sphere using equations for an ellipse, my suggestions is using parametric form). Each little jump you make along the ellipse (make sure jumps are of size N/2 at maximum), record which cell your ellipse passes through. Then, account for the radius of the sphere travelling along the ellipse, and record the other cells which your sphere will fall into, if it were at that position on its elliptical orbit.

 

This way, for each cell, you'll have a list of spheres that can possibly pass through that rectangular cell, and you only have to check for collision with those, making sure you don't repeat collision checks (so if you're on sphere A, and just checked if it collides with sphere B in that cell, don't bother checking if sphere B collides with sphere A). The problem with this is that it requires a lot of overhead, especially if you make your grid too small. And if you make your grid too large, you'll start having to go through a lot more checks - so there's a sweet spot depending on your setup.

 

 

Note: I just realized that the next method assumes all your ellipses have one common (or very nearly so) orbiting point, like planets around the sun, which may not be what you meant

Alternatively,  instead of making a rectangular grid, make spherical shells, of certain thickness (again, varied depending on your setup, and again having a sweet spot of being neither too thick, nor too thin). You can easily calculate the perihelion and aphelion of each elliptical orbit (and add/subtract the sphere's radius) so you will know which of these spherical shells your sphere can pass through. Then when performing collision for a sphere check which other spheres pass through the same spherical shell in which your sphere currently is. 

 

The upside is that you'll need a lot less data storage here, than in the cubical grid method. The downside, as I mentioned in the note, is that this will really only work well when all your elliptical orbits have a common, or nearly common, orbiting point. 

1

Share this post


Link to post
Share on other sites

There's this thing called the KD Tree I think? It can get quite complex, but basically puts every object in to a list of AABB's and objects only check collision in the surrounding AABB's.

 

You can define the size of your AABB's yourself obviously. And there's no limit to how big you can make this tree, there's alot of overhead for it, but it's extremely useful when you have a large amount of objects like that.

Edited by Muzzy A
1

Share this post


Link to post
Share on other sites

5k very small objects in limited space i think is not a problem at all.

i think much more time will took to move objects compared to collision broadphase algorithm and collision response.

Have you made objects to move properly allready?

1

Share this post


Link to post
Share on other sites

5k very small objects in limited space i think is not a problem at all.

i think much more time will took to move objects compared to collision broadphase algorithm and collision response.

Have you made objects to move properly allready?

 

I had done this many months ago, checking collision between each was slow. 

 

 

Thank everyone for tips! Ill try them out.

0

Share this post


Link to post
Share on other sites

So you need a broadphase algorithm. For all moving objects one of the best and simple algorithm would be uniform(limited space) or hash(unlimited spaces) grid (than most of objects are small according to space).

I could give you good source code for that, its grid with sweapandprune, and it takes just ~50 lines of code .

0

Share this post


Link to post
Share on other sites

I have implemented a uniform grid broad phase algorithm in a SPH fluid simulation, and it ran very smoothly with around 5-10k particles even though there were many collisions to handle all the time. I'd definitely recommend going that way, as serumas also mentions.

Just out of curiosity, I'd like to see your source too :-)

 

Cheers,

Mike

0

Share this post


Link to post
Share on other sites

Object (mechanism) routine:

void mechanism::do_loop()
{
	//move object
	vec==...;
	
	//satisfy constrains
	
	//find AABB object bounding box
	box.bbox[0]=...;//min
	box.bbox[1]=...;//max
	
	//needs update if box leevs last cells ragions  // cellw cellh - cells width and height
	if(	box.bbox[0].x<fminx || 
		box.bbox[0].x>fminx+cellw ||	
		box.bbox[0].y<fminy || 
		box.bbox[0].y>fminy+cellh || 
		box.bbox[1].x<fmaxx || 
		box.bbox[1].x>fmaxx+cellw || 
		box.bbox[1].y<fmaxy || 
		box.bbox[1].y>fmaxy+cellh)
	{
		//appears that object must be updated in grid
		upid++;       //update id
		machina.add(this); //readd to grid with new id
	};
}

Grid routine:

void GRID::add(mechanism * m)
{
	mech_data md; //object info
	md.mech	=m;
	md.upid	=m->upid;

	//convert bounding box coords to cells indexes - float to integer
	int iminx=f_to_i(m->box.bbox[0].x*inv_cellw);//inv_cellw=1/cellw;
	int iminy=f_to_i(m->box.bbox[0].y*inv_cellh);
	int imaxx=f_to_i(m->box.bbox[1].x*inv_cellw);
	int imaxy=f_to_i(m->box.bbox[1].y*inv_cellh);

	m->fminx=(float)(iminx)*cellw;//maybe fmodf
	m->fminy=(float)(iminy)*cellh;
	m->fmaxx=(float)(imaxx)*cellw;
	m->fmaxy=(float)(imaxy)*cellh;

	//insert object infos to to cells lists
	for(int i=iminx;i<=imaxx;i++)
	for(int k=iminy;k<=imaxy;k++)
	{
		md.prix=i==iminx;//these prix and oriy is needed to avoid dublication collision checks
		md.priy=k==iminy;
		node[i][k].mechs.push_back(md);
	}
};
void GRID::collisions(int d)
{
	collision_list.clear();
	for(int i=0;i<width;i++)
	for(int k=0;k<height;k++)
	if(node[i][k].mechs.size()>0)
	{
		//delete old id objects and sort
		_loop(its,it,ite,mech_data,node[i][k].mechs)  //  it - iterator for all node[i][k].mechs 
		{
			if(it->mech->upid!=it->upid)
			{
				//old id
				_erase(its,it,ite,mech_data,node[i][k].mechs,it); //safe erase
				it--;
			}else
			{
				//sort
				mech_data* s2it=it-1;
				if(it > its && it->mech->box.bbox[0].x < s2it->mech->box.bbox[0].x)
				{
					const mech_data tmp = *it;
					*it = *s2it;
					mech_data * s2it_1=s2it-1;
					while (s2it > its && s2it_1->mech->box.bbox[0].x > tmp.mech->box.bbox[0].x)*(s2it--)=*(s2it_1--);
					*s2it = tmp;
				}
			}
		}
		//find possible collisions with sweapandprune and fill collision_list
		if(node[i][k].mechs.size()>1)
		{
			_loop(its,it,ite,mech_data,node[i][k].mechs)
			{
				mech_data * it2 =it+1;
				while(it2<ite)
				{
					if(it->mech->box.bbox[1].x <= it2->mech->box.bbox[0].x)break;
					if(it->prix || it2->prix )  //one of two objects has primary column
					if(it->priy || it2->priy )  //one of two objects has primary row
					if(it->mech->box.intersect_y(&it2->mech->box))  //box intersection check 
					{
						//push it->mech and it2->mech to collision_list
						collision_list.push_back(...);
					}
					it2++;
				}
			}
		}
	}
};

Thats the simplest but I think better performance than usualy googled implementation. Becouse grid it self deletes old id objects , so there is no need to delete object manualy, object can be deleted in 2 loops: update id  and finally delete. No need to rebuild grid every loop. Becouse of prix and priy can be avoided dublicates and no need any cell be checked with neighbours. Objects must stay in the same memory address from creation to deletion.

This code is JUST for all moving objects.

Checking dynamic objects with static there are ~20 additional lines of code.

 

Sory for macros found in source code I just copy/paste..

_loop(its,it,ite)       ==                   it=its;while(it<ite){it++;}

_erase(its,it,ite)    safe erase than using <vector> container  

 

testing application with statistics:

http://serumas.gamedev.lt/temp/testing.zip      

Edited by serumas
1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0