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

Is it wise to check all objects in a given state for collision every cycle?

18 posts in this topic

I am trying to write a collision detection system for my game and the only way I can see this working is if I check every object in a scene for a collision every time I call the update function. I don't really want to do this because it seem inefficient to me. Is this really that bad of an Idea? Is there a better way? Am I just stupid?

I am using XNA 4.0

thanks in advance,
Dartos
0

Share this post


Link to post
Share on other sites
I'm also coming up on this problem soon.

Only way I can think of doing it is declaring a counter variable. Each update increment the counter by 1 until it hits lets say 5 where we rest it back to 0. Certain objects absolutely required to be updated such as player and bullets you update every time the update function is called. Other objects such as crates only update if count = 1, enemies might only be updates on counts 2 and 4. Backgrounds on count 0.

I've not put this into practise yet so someone with more XNA experience than me might want to say yay or nay to that plan.
0

Share this post


Link to post
Share on other sites
[quote name='SimonForsman' timestamp='1340649954' post='4952742']
Store your objects in a tree structure based on location and you can avoid even looking at objects that are far away.
[/quote]

I am not that familiar with tree structures. Can you provide some explanation or direct me toward some documentation?
0

Share this post


Link to post
Share on other sites
You've got three types of tree structures (more correctly, spatial partitioning structures) to go look up:

- Quadtrees
- Octrees
- BSP trees

There are also KD-trees which might be useful depending on your game. Wikipedia has in-depth explanations of all of them :-)
2

Share this post


Link to post
Share on other sites
Im not too sure about implementing trees to prioritise collision detection, but what I will say is on an update, first check if the triggering object is moving or has moved. If true, then do a collision detection. This should cut down processing for stationary objects like barells, while constantly checking things like bullets. However if the barrel is moved at some point, then you would do collision detection for it to make sure it doesnt clip a wall for example.

6677's suggestion to check for collision on every Nth update is very risky. If you check for a collision on a bullet on every 5th update for example, then the bullet could have passed through a very thin wall in the time between every 5th update.
0

Share this post


Link to post
Share on other sites
Andrewoid, I think im going to use trees. I have heard about trees but I have no knowlage of their implementation.

Which brings me to this, I looked up those tree types on google but I can't find a good explination on how they can be applied to collision detection. Can anyone give me an example?
0

Share this post


Link to post
Share on other sites
It's a simple concept.

You divide the world up into chunks, based on whatever tree type you select. Then you look at which "chunk" each object is inside of. If you have a bullet in chunk A and a player in chunk B, and you know (based on the tree's properties) that chunks A and B can never overlap, then you don't have to do collision detection between the bullet and the player.
0

Share this post


Link to post
Share on other sites
I think partition trees are pretty much the archetypal method of filtering collisions in large engines, but in a more general sense, all you are trying to achieve is to filter down (or cull) pairs of potentially colliding objects. There are actually many ways to do this, so if you are uncomfortable with data structures you could certainly try a simpler method first. For instance, if use events to respond to collisions (i.e. collidable objects have an onCollide event or something) then one very easy optimization is to only check pairs where one or the other object has an event listener set. If neither object cares (as is often the case for level geometry) then don't bother checking them.
A slightly more complex optimization is to deactivate (Bullet library calls this sleeping IIRC) objects which haven't collided with anything for some time. This technique has some subtleties, because you need to be able to detect when to wake an object (if, say, a character is approaching a stack of sleeping boxes).
Another method of culling collisions is to cull based on dynamic bounding regions. For example, say I have a flock of birds that always tend to be close together, rather than check an airplane against each bird, I will check the airplane against a bounding sphere that contains all the birds, and only if it passes I'll check individual collisions.
Collision libraries (like Bullet) generally use all of these methods together. Basically, though, I'm just saying there are many valid methods to skip certain collision checks (sometimes called broad phase collision checking) so don't settle on one that is going to give you fits unless you're sure it's necessary. Edited by bimmy
0

Share this post


Link to post
Share on other sites
[quote name='andrewoid' timestamp='1340651170' post='4952754']
6677's suggestion to check for collision on every Nth update is very risky. If you check for a collision on a bullet on every 5th update for example, then the bullet could have passed through a very thin wall in the time between every 5th update.
[/quote]
Thanks, I won't be using that then.
Might be somewhere else its handy but not here then and not somewhere I can think yet. Edited by 6677
0

Share this post


Link to post
Share on other sites
Infectedbrain to break down what ApochPiQ stated simply create a class called node that contains a pointer to a node, contains a defined space either 2d or 3d, and contains a container of collidable game objects. Set a max number of game objects allowed per node. Define a node in which its defined space covers the entire scene then begin checking the number of Objects within it. If the number exceeds the max then evenly split the space with two new nodes each with thier parent set as the original node it spawned from. Then repeat that process untill the number of collidable objects is less than the max allowed with the node and add those game objects to that nodes game object list.

Then test which node your bullet is in and only check the collidable objects within that node.

That is the basis of a quad tree. For an Oct tree split the nodes by 4 instead of 2. Here is a link utilizing quad trees for terrain rendering. Its pretty much the same concept just replace vertices with enemies. [url="http://www.rastertek.com/tertut05.html"]http://www.rastertek.com/tertut05.html[/url] The code is in c++ but you shouldn't have difficulties making the change to c#.
2

Share this post


Link to post
Share on other sites
While the approach infectedbrain suggested is exponentially inefficient, there are a few questions that need answering before throwing him to the mess that can be a space partitioning algorithm.

How many objects would your current project have? if you know the answer, chances are you won't be needing any kind of optimization, if the answer is in the thousands or undefined, then we are in business.
As a general rule, unless you are making an educational proyect, unnecessary optimizations are undesirable. If you already have the optimization algorithm at hand you might as well use it, if you want to learn it, do it, otherwise you may be headed into one of the biggest time wastes in development.

If you need to optimize your collision detection you'll probably need to apply a couple of techniques, as others said, tree like structures are one of the most popular methods, they are different ways of applying the same technique, which is space partitioning, breaking down a large, possibly unlimited space into smaller parts where you can fit stuff in to get a certain knowledge of proximity.
If your game had rooms for example, it would be pointless to test for collision between two objects that you know are in to different rooms. That is a space partitioning, you define that rooms are separate spaces and objects cannot be in two of them at the same time.

Another good optimization is avoid checking collisions between static objects, since they usually make up for most of the population of a world. If two objects are truly static, even if they are in collision from the beginning, that is likely as designed by the level editor. If objects are subject to a physics engine, but do not move on their own, its good to flag them as being in static condition when they have found a resting spot. If your objects are mobile those are the ones you need to check all the time.

You can always dig deeper and there is no "best" optimization, they are all good for some cases and bad for others, and as I mentioned before, the cost of research and implementation HAS to be taken into consideration, even if it is the BEST optimization ever.
1

Share this post


Link to post
Share on other sites
[quote name='bglanzer' timestamp='1340690311' post='4952911']

Then test which node your bullet is in and only check the collidable objects within that node.

[/quote]

How do we know when to stop dividing and check for collision? If there is only one object in the node than nothing is colliding. Also what if an object is in more than one node at once?
0

Share this post


Link to post
Share on other sites
You stop dividing when you feel like it, basically. There are different rules of thumb for how far to go depending on the type of division structure you use; kd-trees automatically calibrate themselves, for example, but are a bit more intricate than quadtrees, where you might stop at 2x-4x the size of your game's average-sized objects. This is something that can take some fine-tuning to get optimal, so design your code in such a way that you can control how far the subdivision goes.


As far as objects which overlap multiple nodes: well, you simply check all the nodes it overlaps. Ideally this is a worst-case scenario so you're still saving a lot of calculation over checking everything in the world, and your average case should still be only checking 1-2 nodes tops.
0

Share this post


Link to post
Share on other sites
Some days ago I was compared quadtree and simple grid hashing techniques for dynamic objects collision in my game.
And stayed with grid, becouse of performance, simplier implementation(no recursian), much eficient space dividing (that means better collision checking filter), much faster object inserting to algoritm data list,easie getting result lists for colliding, and so on.
[url="http://www.gamedev.net/user/172531-infectedbrain/"][color=#284b72]infectedbrain[/color][/url] if you want i can share c++ code by email. its very simple, its not perfect and optimized, but it works for me great ... Edited by serumas
0

Share this post


Link to post
Share on other sites
That would be great if you could send me some code to work off of.
If you just want to email it to me my email is dartosgamer@gmail.com
Thanks a lot.
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