Jump to content

  • Log In with Google      Sign In   
  • Create Account

#Actualserumas

Posted 21 July 2013 - 11:38 AM

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      


#2serumas

Posted 21 July 2013 - 11:25 AM

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 simple 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. 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.

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         


#1serumas

Posted 21 July 2013 - 11:23 AM

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 simple 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. No need to rebuild grid every loop. Becouse of prix and priy can be avoided dublicates and no need one cell be checked with neighbours.

 

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         


PARTNERS