FAQ Search
Memberlist Usergroups
  Forum Statistics Register
 Log in to check your private messages
Log in to check your private messages
Moonpod Homepage Starscape Information Mr. Robot Information Free Game Downloads Starscape Highscore Table
Hit Detection
Post new topic   Reply to topic    Discussion Pod Forum Index -> Starscape View previous topic :: View next topic  

Joined: 18 Apr 2009
Posts: 15

PostPosted: Thu Oct 22, 2009 2:43 am    Post subject: Hit Detection Reply with quote

What form of hit detection do you use in Starscape between two ships and between bullets and ships? I would appreciate a technical answer. It's for a game programming class I'm taking. We made a pinball game, but none of the students' hit detections work very well, and even the instructor's example doesn't work very well under certain conditions. Anyway, any answer would be appreciated.

Last edited by NoPetrol on Sat Oct 24, 2009 2:11 am; edited 1 time in total
Back to top
View user's profile
Poo Bear
Pod Team
Pod Team

Joined: 14 Oct 2002
Posts: 4121
Location: Sheffield, UK

PostPosted: Thu Oct 22, 2009 8:59 am    Post subject: Reply with quote

Handling collision is a tricky problem, but there are a lot of tutorials and books on the topic so it shouldn't be insurmountable.

Problem - a game update is performed at discrete time intervals (say once every 40mSec) and therefore objects are not smoothly moving through space, but jumping from one position to another. After each jump a check is made to see if any object has hit any other, resulting in an explosion or bouncing off a wall. However, a fast moving object could have gone quite far in 40mSecs so it might already be inside the other object or the wall. This could mean the simulation looks odd, objects stick together or the program crashes.

There are many different solutions to choose from which is kind of annoying, but I think these days an awful lot of developers go for one of the many physics middleware sdks available (havok, physx, bullet) and let the experts solve the problem properly.

Starscape didn't need such a sophisticated solution, so I hacked something together Wink

1. setup the current positions of all objects in the world and guarantee nothing is touching anything else.

2. save all current positions and velocities.

3. run the simulation and move everything.

4. go through every object in the world and use some method to quickly discard objects that have no chance of being in collision. I used an octree for this.

5. take pairs of objects one pair at a time and test to see if they are colliding.
5.1 Apply a collision response - this might bounce something off something else or make something blow up because it hit a wall or a bullet. It should tend to move things away from each other or blow them up - which is good.
5.2 If the two are still colliding then we have a problem. Look at the old positions we had - they were guaranteed good, so try to step back to that good position in small increments stopping as soon as we are no longer in collision i.e. tease the objects apart.

This approach is a heuristic - it won't get the correct result all the time, just most of the time. It works for Starscape because:

1. the code handling collision response works even if objects do end up inside each other i.e. that situation won't crash the game or make the simulation look crazy, the objects will just tend to move out of collision or explode as soon as they can, they won't sit at rest inside each other.

2. no object in the game is moving so fast that it will completely miss a collision. This is due to the time step in the simulation (it is kept small) and the size and speed of objects (nothing moves too fast, no object is too small). Remember, just because the screen updates at 25fps (or whatever) that doesn't mean the physics has to do the same, you could run the physics at 50fps for example which halves the distance objects move on an update and perhaps prevents anything looking wrong.

3. lots of testing was done to be 99.9% sure all these assumptions were correct and the game was stable.

Why not just use physX? A more "correct" solution would be to coincide an object's start position and its end position and its shape (a circle say) and then build a volume containing the space between i.e. a sausage shape Smile That would give more accurate results, but the implementation is a bit tricky. One of the hardest things about developing games is picking the right battles. The goal is to release a game. Nobody really cares how the game works just as long as it exists and plays properly. Plus, you won't improve as a developer unless you release a lot of games so you need to get cracking. Add to that a day job and suddenly you are really up against it. You have to decide what you want to focus on and how long you want the project to take and what is acceptable. That kind of scheduling and decision making is probably the toughest part of the whole process because it dictates what you can get done in the time available. So maybe it would have made more sense to spend some time learning how PhysX works and accept it will slow one project down but speed up future ones or maybe a simple quick heuristic approach is fine.
Back to top
View user's profile Visit poster's website

Joined: 18 Apr 2009
Posts: 15

PostPosted: Fri Oct 23, 2009 2:10 am    Post subject: Reply with quote

I figured most professional game developers used some kind of pre-made physics engine. I also guessed that you didn't do that (something gave me the feeling that someone who loves programming so much as to implement that cool swarming thing by themselves wouldn't use someone else's physics engine). That and Starscape's bug free (as far as I can tell) collision detection handled accurately for complicated shapes is why I came here to ask you this. It's comforting to know that you guys had to deal with the same problems we are dealing wiith. The class I am taking is a class in "game programming". Its purpose is to teach game design at the lowest levels (well, not assembler code. We use C# for everything).

You said one of the steps is to "take pairs of objects one pair at a time and test to see if they are colliding." This is what I am interested in. What test do you use? Did you use some kind of pixel-by-pixel hit detection, or did you create mathematical models for every single object in the game?

For the games we're making in class, the instructor's example uses a fairly complicated series of mathematical functions to determine whether a ball will intersect a line during some time between the frame that was just drawn and the next frame to be drawn. It seems it would be extremely complicated to do this if we were to test whether the ball would collide with some other shape, say, a Star Boss-shaped object for example.

A while ago I found this: http://www.ziggyware.com/readarticle.php?article_id=52
It works by checking every pixel, seeing if it is adjacent to a transparent pixel, and using this information to create an outline of every sprite which is updated every time the sprite is rotated. Another student at my university added a simple vector algebra function to this method to actually calculate normal angles based on the outline pixels. He did this for some other game he made to make bullets bounce off objects realistically. It this similar to what you did?
Back to top
View user's profile
Poo Bear
Pod Team
Pod Team

Joined: 14 Oct 2002
Posts: 4121
Location: Sheffield, UK

PostPosted: Fri Oct 23, 2009 8:24 am    Post subject: Reply with quote

Every game object implements a collision object. A collision object is created from an initialisation file loaded at startup for each type of game object. The collision data contains any number of primitive shapes: line, circles, square, rectangle, polygon. Plus their offset from the object. So even complex looking large objects can be expressed quite accurately through 1 to about 6 primitives.

I then have a set of functions that allow you to compare each primitve shape against all other possible shapes.

So I can say:

bool Has_hit( pObj1, pObj2, &collisionPoint, &collisionNormal)

and that will take every shape in pObj1->getCollisionObj() and test it against every shape in pObj2->getCollisionObj() and just call the appropriate collision test function. At the end I just get the closest collision point and normal and return that.

I'd be very impressed if this was slower than any algorithm based on per-pixel checking. Plus, reading pixels back from the graphics hardware is a very slow process indeed. Once again the high level question is important - is per pixel collision checking necessary? It's very game dependant, but I think something like my fast solution would be \\\"good enough\\\" in most games.

p.s. each game object also has a single rough collision shape for early rejection that is used in the octree.
Back to top
View user's profile Visit poster's website

Joined: 18 Apr 2009
Posts: 15

PostPosted: Sat Oct 24, 2009 2:09 am    Post subject: Reply with quote

Thanks. We might be able to use this. It is, at the very least, an idea we haven't thought of or talked about in class yet. I figure you can even build in normal angle detection into that too.

I think the minor details that are only possible (or economically feasible to implement) if game developers write all the code themselves, or at least "in-house", contribute to the fact that Starscape is the first or second best game I've ever played. Only Cave Story may be better. Well, maybe Earthbound too.
Back to top
View user's profile

Joined: 13 Jul 2018
Posts: 886

PostPosted: Tue Sep 11, 2018 11:40 am    Post subject: nike shoes and wigs Reply with quote

www.google.com online shopping human hair wigs and nike shoes for discount.wholesale lace front wigs and cheap nike air max shos online.where to buy high quality synthetic wigs and roshe run shoes is a best choice.
human hair wigs
cheap lace front wigs
full lace wigs
lace front wigs
cheap human hair wigs
cheap synthetic wigs
cheap wigs for women
cheap bob wigs
african american wigs cheap
afro wigs cheap
cheap full lace wigs
cheap curly wigs
cheap cosplay wigs
cheap wigs for men
cheap costume wigs
cheap hair extensions

cheap nike shoes
nike air max
nike air max 90
nike air max 90 womens white
white roshes mens
roshes women
cheap air max 90
air max 270 mens
nike air max 1 mens
cheap nikes online
nike sb janoski
nike skateboarding shoes
nike air force one men
nike air force 1 low
black huaraches
nike huarache women
air max 270
air max sale
nike air max sale
air jordan 4

Back to top
View user's profile
Display posts from previous:   
Post new topic   Reply to topic    Discussion Pod Forum Index -> Starscape All times are GMT
Page 1 of 1

Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group