Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (710)
Games in Android Showcase (212)
games submitted by our members
Games in WIP (784)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Sprite collision detection  (Read 2877 times)
0 Members and 1 Guest are viewing this topic.
Offline appel

JGO Wizard

Medals: 80
Projects: 4

I always win!

« Posted 2005-10-26 20:32:49 »

What is the most effecient way to do this? Is there a way to store all the sprites coordinates in some data-structure that keeps track of all collision?

I find comparing each sprite with all sprites is a bad idea.
Offline Jeff

JGO Coder

Got any cats?

« Reply #1 - Posted 2005-10-26 23:35:41 »

Thre have been long discussions on this already. Try searching the boards.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!
Offline JAW

Senior Devvie

Medals: 2

« Reply #2 - Posted 2005-11-01 12:48:54 »

There are many tutorials in the web.
Search here, or or

The question is, how precise you need your collision.

The main way would be to do quick and easy tests first and to exact tests if the easy test shows a collision.

Easy tests are bounding box/rect or bounding sircle.

Bounding box/rect means you get a rect around your sprite, and another rect around the other sprite, and then you just check if they intersect.

Bounding circle means you have a middle of each sprite and a radius of its size. Then the distance between two middles must be greater than the sum of their radi, then they dont collide.

This tests are mathematically easy and fast, but not precise. But they will help to eliminate a hell lot of tests for objects that dont collide. All objects that DO collide run a second more precise test to test if they really do collode.

In many cases, the easy tests are all you need. One hint is to use a bounding circle and the set the radius to 80% of the real max radius. This 80% will give you the core area of your sprite while it leaves out some edges. While this isnt precise, its precise enough in most cases.

You can do a bounding polygon, which is also mathematically far faster than a pixel per pixel test.

When doing a pixel per pixel test, you should consider only to test border pixels, not the inside of the sprite. when the sprites intersect, their border should intersect on some point.

As I said, search the web. This topic is widely covered.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

« Reply #3 - Posted 2005-11-01 23:11:06 »

What is the most effecient way to do this? Is there a way to store all the sprites coordinates in some data-structure that keeps track of all collision?

I find comparing each sprite with all sprites is a bad idea.
I see you're also asking whether or not it is smart to test each and every sprite against each and every other sprite, because that has a BigO of n^2, which is pretty slow. Faster methods largely depend on what exactly your game is like. If you have a 2D grid-type game, you can of course simply check array locations, which is very efficient but not logical for most modern games.

Here is what I use and recommend for a top-down 2D grid-style game. I have no idea if it is the best way or not, I usually come up with my own ways of doing things.

Have a 2D array to represent all sprites that might need collision testing. Say you have a 30x30 grid to represent you entire level, each grid space being 50 pixels wide/tall. Your collision array should represent each block and the blocks surrounding it, so a 10x10 grid with each grid space being 150 pixels wide/tall. Then, every timestep, adjust every collidable sprite to the correct position within the grid. Say it is currently at 350,100 on the screen. That means it should be moved to [1][0] in the grid, because every 150 pixels it should move to different location. Then when calculating collision you only check within each sprite's collision grid space. The efficiency of doing it this way is BigO n, significantly faster than BigO n^2, although I doubt the fastest possible.

Understand what I mean?

See my work:
OTC Software
Offline Ask_Hjorth_Larsen

Junior Devvie

Java games rock!

« Reply #4 - Posted 2005-11-02 02:59:37 »

I think you expressed yourself clearly, Demonpants. Each tile stores a list of units presently inside it. However, assuming that sprites may at one point overlap several tiles in your collision grid, you will have to traverse all 9 tiles surrounding any unit and compare with all other units registered in those tiles. Also the size of a sprite must not be greater than half the size of a tile, which poses a hard-to-remember limit on unit size (remember to throw exceptions if too large units are made Smiley ).

In our current project we use a slightly diffferent approach. A sprite may be registered in any number of tiles (typically 1-4, but for large sprites the number could be arbitrarily large), and it checks for collision with every other sprite registered in any of those tiles. This adds some overhead here while removing overhead there. However it allows any sprite size, and on a side note it also allows us to easily implement a similar system for checking whether terrain needs to be re-rendered (which it doesn't, unless units are near). It would be bad to have other sprite size restrictions due to the different terrain tile size.
Offline Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

« Reply #5 - Posted 2005-11-02 07:11:58 »

Well, in order to eliminate overlap problems and large sprite issues you have to do some extra fringe cases I did not mention in mine, that I do have in my code. I was trying to have him understand the general gist of it.

Your method seems interesting. Does it basically do the same thing only it checks across multiple tiles if need be?

See my work:
OTC Software
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

theagentd (99 views)
2017-02-18 13:42:33

theagentd (103 views)
2017-02-18 13:35:16

h.pernpeintner (1268 views)
2017-01-24 22:39:11

h.pernpeintner (1257 views)
2017-01-24 22:38:32

Galdo (1816 views)
2017-01-12 13:44:09

Archive (1921 views)
2017-01-02 05:31:41

0AndrewShepherd0 (2459 views)
2016-12-16 03:58:39

0AndrewShepherd0 (2298 views)
2016-12-15 21:50:57

Lunch (2377 views)
2016-12-06 16:01:40

ral0r2 (2155 views)
2016-11-23 16:08:26
List of Learning Resources
by elect
2016-09-09 09:47:55

List of Learning Resources
by elect
2016-09-08 09:47:20

List of Learning Resources
by elect
2016-09-08 09:46:51

List of Learning Resources
by elect
2016-09-08 09:46:27

List of Learning Resources
by elect
2016-09-08 09:45:41

List of Learning Resources
by elect
2016-09-08 08:39:20

List of Learning Resources
by elect
2016-09-08 08:38:19

Rendering resources
by Roquen
2016-08-08 05:55:21 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!