• 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
Counciler

Advanced collision detection - lots of objects

7 posts in this topic

Okay, so right now, I have a character, and he just simply checks against everything that is on the screen. It works fine, but I'm reading a book on collision detection and it talks about a way to handle many more objects on the screen. It suggests creating sectors and only checking against objects that are in the same sectors. The book then proceeds to give a working example of collision detection, but doesn't seem to follow it's own method of creating the sectors. So my problem is with creating these sectors. The book says that doing this method can decrease the checks by half or more, depending on how many objects are being checked against however many objects. It gives numbers as an example of how many checks you can save. But what confuses me is the book counts putting an object into a sector as only one check. The only way I can think of to create these sectors is to create an array of rects to keep track of where each sector is, then checking each index of the array until it finds the appropriate sector that each object is in. But assuming there's 24 sectors, and 12 objects on the screen, that would mean 12 objects will check up to 24 times each, and therefore it would be more efficient to just check against the 12 objects directly. So how does a person put an object into a sector with only one check?
0

Share this post


Link to post
Share on other sites

The only way I can think of to create these sectors is to create an array of rects to keep track of where each sector is, then checking each index of the array until it finds the appropriate sector that each object is in.

 

The sectors would be stored in a static array corresponding to its position on the map. By having all of the sectors the same size, you can calculate which sector an object is in simply by knowing the position of the object and the fixed size of a sector.

0

Share this post


Link to post
Share on other sites

Actually you'll have multiple objects inside one "sector" so when you can discard a sector you can already discard all objects inside it without checking them.

Typically you create some kind of tree hierarchy like a quadtree, octree, kdtree to do these things.

Edited by LJ_1102
0

Share this post


Link to post
Share on other sites

I don't know if it will help you, but this is my class for hash grid which I use in my game.

 

public class HashGrid {
	
	/*
	 * allGameObjects variable is used to store same objects as an gridObjects arraylist, execpt it is all in one place,
	 * and it is faster to return it, than adding all lists from gridObjects, and then returning them.
	 */
	private ArrayList<GameObject> allGameObjects;
	private ArrayList<GameObject> nearObjects;
	
	private ArrayList< ArrayList< ArrayList< GameObject> > > gridObjects; // two-dimentional ArrayList of ArrayList<GameObject>
	
	private ArrayList<Id> currentIds; 
	private Rectangle [][] gridBounds;
	private int gridSizeX, gridSizeY;
	
	class Id{
		public int x;
		public int y;
		
		public Id(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	public HashGrid(float worldWidth, float worldHeight, float squareWidth, float squareHeight){
		this.gridSizeX = (int) Math.ceil(worldWidth/squareWidth);
		this.gridSizeY = (int) Math.ceil(worldHeight/squareHeight);
		
		gridObjects = new ArrayList< ArrayList< ArrayList<GameObject> > >();
		
		
		for(int x = 0; x < gridSizeX; x++){
			gridObjects.add(new ArrayList<ArrayList<GameObject>>());
			for(int y = 0; y < gridSizeY; y++){
				gridObjects.get(x).add(new ArrayList<GameObject>());
			}
		}
		
		currentIds = new ArrayList<Id>();
		gridBounds = new Rectangle[gridSizeX][gridSizeY];
		allGameObjects = new ArrayList<GameObject>();
		nearObjects = new ArrayList<GameObject>();
	
		for(int i = 0; i < gridSizeX; i++){
			for(int j = 0; j < gridSizeY; j++){
				gridBounds[i][j] = new Rectangle(i*squareWidth,j*squareHeight,squareWidth,squareHeight);
			}
		}
	}
	
	public ArrayList<GameObject> getNearObjects(Rectangle bounds){
		nearObjects.clear();
		
		setTouchedSquaresIds(bounds);
		int size = currentIds.size();
		
		for(int i = 0; i < size; i++){
			Id id = currentIds.get(i);
			nearObjects.addAll(gridObjects.get(id.x).get(id.y));
		}
		
		return nearObjects;
	}
	
	/**
	 * 
	 * @param obj Game object to test with
	 * 
	 * @return which grid squares the object is touching
	 */
	private void setTouchedSquaresIds(Rectangle bounds){
		currentIds.clear();

		for(int x = 0; x < gridSizeX; x++){
			for(int y = 0; y < gridSizeY; y++){
				if(CollisionTester.rectsCollided(gridBounds[x][y], bounds)){
					currentIds.add(new Id(x,y));
				}
			}
		}
	}
	
	public ArrayList<GameObject> getAllObjects(){
		return allGameObjects;
	}
	
	/**
	 * Adds game object to hashgrid
	 * 
	 * @param obj
	 */
	public void add(GameObject obj){
		for(int x = 0; x < gridSizeX; x++){
			for(int y = 0; y < gridSizeY; y++){
				if(CollisionTester.rectsCollided(gridBounds[x][y], obj.bounds)){
					gridObjects.get(x).get(y).add(obj);
				}
			}
		}
		
		allGameObjects.add(obj);
	}
	
	/**
	 * Removes all instances of speicifed object
	 * 
	 * @param obj
	 */
	public void remove(GameObject obj){
		
		for(int x = 0; x < gridSizeX; x++){
			for(int y = 0; y < gridSizeY; y++){
				gridObjects.get(x).get(y).remove(obj);
			}
		}

		allGameObjects.remove(obj);
	}
	
	/**
	 * Only clears GameObjects.
	 * 
	 */
	public void clear(){
		for(int x = 0; x < gridSizeX; x++){
			for(int y = 0; y < gridSizeY; y++){
				gridObjects.get(x).get(y).clear();
			}
		}
		allGameObjects.clear();
	}
	
}

0

Share this post


Link to post
Share on other sites

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

 

Not a bad reduction for a simple method of regrouping the data.  (NOTE: May have messed up the general descriptions, but it should be fairly close to correct I believe.)

 

More complicated solutions exist and can get better gains. But, as said, they are more complicated.  I did a system which sat on top of my sweep and prune implementation which did a very nice job (used for something not directly related to reducing interactions since I already had that in the sweep and prune).  But it was a considerable bugger to write and debug.  You probably want to stick to the simple suggestions.

Edited by AllEightUp
0

Share this post


Link to post
Share on other sites

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

Something wrong with your calculations  bruteforce of n objects will be n*(n-1)/2  12*11/2=66. ==  11+10+...+1=66

So its the number checks in worst case.

I cant undertand why everyone suggest to use quadtrees, in my experience its always slower and harder to implement than properly implemented grid or hashgrid.

Maybe it was good algorith in the past, but now its much slower becouse of cache missings.

And if you want even to speedup your grid , you can use sweap and prune inside each cell.

 

 

I don't know if it will help you, but this is my class for hash grid which I use in my game.

Sveiks,

I think its a simle grid implementation becouse there is no hash function smile.png

Edited by serumas
1

Share this post


Link to post
Share on other sites

Sveiks,

 

 

I think its a simle grid implementation becouse there is no hash function smile.png

 

I still need to learn many things :) 

0

Share this post


Link to post
Share on other sites

All found grid implementations I found, even in book are damw far away from perfectness

After lots of optimizations and experiments I found routine that works finiest and its stil on optimizations

but main loop would look like this:

 

loop
{

//objects update
for(all objects)  //dead,alive, and waiting to be inserted in game world
{
     if(obj.is_dead()){delete obj;continue;}
     if(obj.mut_insert())obj.set_acative();
     if(obj.active)
     {	
        obj.move_object();
        obj.find_bounding_box();
        bool update = obj.find_out_does_it_needs_to_be_updated_in_grid(); //not accessing grid data, maybe tricky or very easy, it depends
        if(update)
        {
            obj.update_id++;
            grid.add(obj);
        }
    }
}
//grid update and collisions
for(all cells in grid)
{
     for(all objects in cell)
     {
          if(cell_obj->obj->update_id!=cell_obj->update_id)delete cell_obj; //delete all elements with old id's
          
     }
     sort_cell_objects_by_box_left_up_corner_x(cell);
     do_collision_like_sweep_and_prune(cell);//with some tricks its easy to avoid dublicate checks so we dont need to check neighbur cells so even object size differences do not mater
}

}

So its main simple main loop.

Some of optimization could be done for example:

do cell objects delete sort and check for collision in one loop  (possible allmost done)

find bounding box without resuming all object vectors (done with only 2 vectors)

object insertation could be done in grid.collision routine() becouse on insert you must check if it lands on free space

Edited by serumas
0

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