XNA Hit "prediction" instead of "detection"?

  • (2 Pages)
  • +
  • 1
  • 2

21 Replies - 4860 Views - Last Post: 07 February 2013 - 07:39 AM

#1 gummipalle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-January 13

XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 08:30 AM

Hello guys and gals here at dreamincode.net.

I've been learning c# and then XNA in my free time during the past few years,
browsing forums like this one and watching tutorials, and reading a bit in a few books here and there.

This is my first post anywhere asking for help, so please excuse (in advance) any noob-nes my post may contain.
I will try my best to adhere to forum guidelines.

Among many other small "learn-c#-projects" I made a fun little (win-forms!) breakout clone a year or so back.
My family enjoyed the little game, and it was rewarding at the time, to complete something that worked (almost!) as intended.

I've restarted the project in XNA, hoping to achieve a smoother, bit more advanced version.
I've got different ways of importing levels from text or pictures (or using a self made editor).
-an improvement to the last games "hard-coded" built in levels.
I've got multichannel sound for lasers and bricks breaking, as opposed to last games 1-sound-at-a-time scheme.
Things are looking good.

But I have an issue that's been bothering me for way too long now, and I seem to be stuck, losing motivation.
Its been a few months without progress...

The issue is hit-detection...

For my non-XNA version, hit detection was the standard "move, check collisions, move, check collisions" method.
As you all know, this results in occasional "overlap", where the ball in fact protrudes through things, before hit detection occurs...

For my XNA version however, I'm trying to implement "hit-prediction" (dont know a better term),
to avoid such overlap / semi-poor hit-detection.

The idea is, that every time a change occurs for the ball (i.e. its launched, or it bounces off something)
It scans ahead, considering direction and velocity, and predicts when collision should occur, instead of checking each frame...

Forgetting about bricks for now, (leaving only borders/walls and the ball), the idea I've been going with was
to define these objects in terms of lists of pixels (vectors for each containing position, and direction.)
And then testing these list items (ball-pixel-list and wall-pixel-list) against each other...

However, because power-ups and/or my preferences can change the size of the ball, The ball must have its "circumferance-pixels" defined by a method each time the game starts, or size is changed... (as only circumferance pixels are relevant to test for collisions).

So the sprite scales fine. However, compiling a list of these "circumference pixels" to be used in hit detection turns out... Hard.
I cant seem to get a complete list of pixels. There are "gaps" in the circle, allowing for "penetration".
The amount of pixels on the list does vary depending on ball diameter, but not in an immediately predictable manner.
A larger ball may claim to have fewer pixels on its circumference. hmmmm.

I've tried to adjust the tolerance levels for when a pixel is considered to be "on the line", but without much effect.
(something like "if a pixel is on the circle plus/minus one or two pixels")

Now, my methods work almost all the time (when ball diameter is 30!) , leading me to believe I'm close, but still some ball direction angle-ranges let the ball protrude through the walls a bit...

So, now that I've explained my situation, let me state the question I think I should be asking,
but please feel free to correct me...
How do I compile a complete list of ball circumference pixels, so that I get an impenetrable circle?

Here is what I started with, for circles in a coordinate-system. Basically testing each pixel in ball against this rule:
(x - x_0)^2 + (y - y_0)^2 = r^2\

I have a lot of code, the project is fairly big (by my standards) so I'm hesitant to start pasting code.
However, if you need it I could paste what I have for my "define_circle" method. -Just not sure what parts are relevant for you at this time.

Hope this makes sense to you, as mentioned, I'm not too used to posting... But I expect to be at this computer for a while, so feel free to ask even tiny follow-up questions, I should be able to respond fairly fast.

Is This A Good Question/Topic? 0
  • +

Replies To: XNA Hit "prediction" instead of "detection"?

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9366
  • View blog
  • Posts: 35,187
  • Joined: 12-June 08

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 08:40 AM

Quote

For my non-XNA version, hit detection was the standard "move, check collisions, move, check collisions" method.

Really? I always took it as 'detect a possible collision then move' and not 'move and then check collisions'. Odd.
Was This Post Helpful? 1
  • +
  • -

#3 Kilorn  Icon User is offline

  • XNArchitect
  • member icon



Reputation: 1356
  • View blog
  • Posts: 3,528
  • Joined: 03-May 10

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 08:47 AM

You're right, modi123_1, if a collision would happen at the new location, then obviously the object doesn't move. Otherwise characters would move inside a wall, and then check to see if they moved inside a wall.

When doing collision detection, you always want to check for a collision at the new location based on the amount of movement of the object before you allow that object to actually move to that location. It's counterproductive to move the object, then check collision, and if a collision happens, move the object back to it's previous position.
Was This Post Helpful? 0
  • +
  • -

#4 gummipalle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-January 13

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 09:53 AM

Hello and thank you for such quick replies, that was a nice surprise!

Right, but lets say the ball moves say, 7 pixels per frame, And the distance to next obstacle is only 5 pixels.
(No speed variations, no user input affects the movement of the ball once launched)

Then If I understand you correctly, you would not move further, instead bounce before hitting the wall? Is that not the same level of inaccuracy?
Or do you move the 5, and then 2 in the new direction? (all within the same frame)

Anyway, that stuff I can fiddle with on my own for now, I Don't want to waste too much of your forum time/resources on that, as I do in fact intend to implement various methods of Col. detection, user-selectable from options menu. ( To test performance differences and learn various methods, without having to make a brand new game for each.).

What I'm stuck on at this time is accurately identifying and listing all the pixels that
form the perimeter of the circle, so I can do any kind of per-pixel detection at all,
without having to test all ball pixels, just the "surface".

You both seem surprised at my first post, but that's actually the way I've seen other amateurs and tutorials do things. (i.e. switch direction if new position is equal or past this border, or delete bullet if its position is equal or greater than wall surface position)

Thank you, and tell me if you need more info...
Was This Post Helpful? 0
  • +
  • -

#5 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9366
  • View blog
  • Posts: 35,187
  • Joined: 12-June 08

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 10:00 AM

Quote

Then If I understand you correctly, you would not move further, instead bounce before hitting the wall? Is that not the same level of inaccuracy?

Yes.. typically I have it where if the movement is X... and moving again would bring the object into the other I would just move the distance between the objects and not the full X.
Was This Post Helpful? 0
  • +
  • -

#6 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9366
  • View blog
  • Posts: 35,187
  • Joined: 12-June 08

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 10:06 AM

... though with respects to your question - how do you 'move' your image? Is it a rectangle? Some rectangle-ish shape, right? Why not just take that bounds and bump it out?
Was This Post Helpful? 0
  • +
  • -

#7 gummipalle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-January 13

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 10:29 AM

Thank you modi123_1

In regards to your first reply, I guess was hoping for something that felt more...
I don't know a good term... predictable , or repeatable maybe? Something constant...

But I see you have a lot of reputation and colourful badges, so I guess you know what your talking about :-)
...And after all, I'm not trying to land a lunar-lander, just bounce a tiny ball, so probably that method is accurate enough...

Yes, the image is just an actual square with a ball painted on it, transparent corners.
Its a sprite that I move by updating the draw-method with an updated position...

Unfortunately, I don't what it means to "just take that bounds and bump it out"...
If you can clarify a bit for me, I'll get back to you asap.
Was This Post Helpful? 0
  • +
  • -

#8 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9366
  • View blog
  • Posts: 35,187
  • Joined: 12-June 08

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 10:42 AM

It's not that hard of a concept. If your collision box is a rectangle.. with X,Y at the top left, width W, and height H you can f ind the bounds of the box, right? well make a secondary, temp rectangle, with the same location except shift everyone by some by your buffer N.

So the top left isn't X, Y but X-N, Y-N... the height is now H+2N... width is W+2N..

It's pretty straight forward.
Was This Post Helpful? 0
  • +
  • -

#9 gummipalle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-January 13

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 04:08 PM

hmm... sorry to disappoint, but I must be misunderstanding you... Or just plain not getting it.

The way I understand your text, you are asking me to create a temp. rectangle N pixels left,
and N pixels up, from the original, and then expand its size by twice that amount, (2N)...

What I imagine happening then, is equivalent to this temp. rectangle expanding outward from the original in all directions...

But I fail to recognize what this accomplishes? - I cant even seem to connect that with
anything circular...

My new question perhaps should be: How does the above (if correct?) apply to listing the pixels that make up the outline of the ball?

-Maybe at this point you could also tell me if you think I am expressing my idea (about the per-pixel col. method) in a way that is understandable, and if so, is it just a bad way to go about it?
If not, I could write up a better explanation, and perhaps include a diagram.

I dont have much of a sense of how I'm coming across with my questions... I've only ever read or watched things, no-one I know wants to talk programming (or anything technical), so I have no experience in actually communicating my own thoughts on this stuff. This is literally my first time:-)

Again, any help or tips are appreciated...
Was This Post Helpful? 0
  • +
  • -

#10 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9366
  • View blog
  • Posts: 35,187
  • Joined: 12-June 08

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 05:21 PM

From what I understood, from you, is you wanted to have a bubble around your drawn image to throw up a warning that says 'hey - this image is about to collide with something but not yet'. What I suggested was to expand out your image's bound rectangle to a bit farther out to give that warning.

Example:

Posted Image



Quote

If not, I could write up a better explanation, and perhaps include a diagram.

Yes.. do that.

This post has been edited by modi123_1: 23 January 2013 - 05:29 PM

Was This Post Helpful? 0
  • +
  • -

#11 gummipalle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-January 13

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 10:04 PM

Wow, just woke up at my desk.
Ok, well I'm glad I understood what you were saying, your diagram was reassuring of that.
...And while I took something away from it, it was not quite what I was looking for, so I'll get working on a better post, with pictures! -Just need some sleep first, I think.

When done however, is this the best place for it, or should I start a new and improved thread? I have a feeling I got this thread started in the wrong direction... -And on that topic, if and when relevant, is there some way to mark a topic as "obsolete" or "old" or something? Or is that a moderator type action? (cant spot any controls for that sort of thing)

Thank you and goodnight!
Was This Post Helpful? 0
  • +
  • -

#12 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9366
  • View blog
  • Posts: 35,187
  • Joined: 12-June 08

Re: XNA Hit "prediction" instead of "detection"?

Posted 23 January 2013 - 11:02 PM

Keep it going.
Was This Post Helpful? 0
  • +
  • -

#13 gummipalle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-January 13

Re: XNA Hit "prediction" instead of "detection"?

Posted 24 January 2013 - 09:12 AM

Ok, Im done... Getting an error uploading pictures though.. "Error - The server returned an error during upload"
Tiny paint-drawn bmp files...
Do I need to register on 3rd party picture storage site, and upload there, then link to it?
Was This Post Helpful? 0
  • +
  • -

#14 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9366
  • View blog
  • Posts: 35,187
  • Joined: 12-June 08

Re: XNA Hit "prediction" instead of "detection"?

Posted 24 January 2013 - 09:13 AM

yeah.. that feature is disabled here for a short time.
Was This Post Helpful? 0
  • +
  • -

#15 gummipalle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 23-January 13

Re: XNA Hit "prediction" instead of "detection"?

Posted 28 January 2013 - 07:31 PM

Ok, here is my second try at explaining what I'm trying to accomplish:

I want to trace every pixel on the balls circumference in the
direction fired, and using the given velocity of the ball, determine
"time until impact" for each of these pixels, against whatever brick or wall pixels
that stand in the way.
The pixel with the least "time until impact" will then represent the
"point of impact" on the ball. (Red circle on picture 1)

Knowing the point of impact on the ball, because each pixel has a unique position on the circle,
and therefore also a unique "direction towards ball centre",
I can then determine the new travel direction for the ball. See picture 1....
Posted Image

Information about each pixel (both ball and bricks) is stored as vectors.
because the ball has a dynamic size, its "vector list" (list of pixels on circle) must also be dynamic.
However, when generating this list, on game load or size change,
I come up short... There are gaps in the circle.
See picture 2..

Posted Image

What I need is something like this: I put in a radius (or diameter) for the ball, (So the ball sprite is real-time scalable)
and the program generates a list of pixel-positions that completely cover the circle, without gaps,
or at least without gaps much bigger than 1 pixel, or else small bricks (I want that option) might pass through the ball, undetected.

Here is the code I've been using to generate this list of pixels.
Note: This is one of many similar models I've used in attempting this. It may not be the
most accurate variant, but it should convey the basic thought-process...
It basically lists all pixels in the rectangle, and tests each one for being in ther circle, adding
positives to a list, which I can use for collision detection...

//-----------------------------------------------------------------------------------------------
        //>>>>>>>>>>>>>>>>>>>>>>>>>>  Define Circle    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        //-----------------------------------------------------------------------------------------------

        //heights list is used internally by the code to count the height of the ball, and make
        //a row for each that is as wide as the ball.
        List<int> heights_list = new List<int>();

        //This is a list of all the border oixels of the ball...
        public List<Vector4> all_ball_pixels = new List<Vector4>();
        

        private void Define_Cirkel()
        {
            /* so ok... For every pixel in ball, make a vector...
             * of these vectors, check for "being on the cirkel"
             * Those one the cirkel are added to ball_pixel_list
             */

            //This is the amount of pixels that need a vector assigned...
            int ball_pix_counter = (int)ball_diameter * (int)ball_diameter;
            

            //First we create a list of heights, so that we can use a foreach loop on - each of them,
            //that adds a vector for every width.
            float heightcounter = ball_diameter;
            float widthcounter = ball_diameter;

            

            while (heightcounter >= 0)
            {
                heights_list.Add((int)heightcounter);
                heightcounter--;
            }

            //Now you have a list of ints, which in themselves represent each variance of height 
            //used by the ball. Now, for each of these items, create width amount of vectors.
            foreach (float heights in heights_list)
            {
                widthcounter = ball_diameter;

                while (widthcounter >= 0)
                {
                    if (((int)Math.Floor((widthcounter - ball_diameter / 2) * (widthcounter - ball_diameter / 2)) + ((int)Math.Floor(heights - ball_diameter / 2) * (heights - ball_diameter / 2))) >= (int)Math.Floor((ball_diameter / 2) * (ball_diameter / 2)) -4//-6f)
                     && ((int)Math.Floor((widthcounter - ball_diameter / 2) * (widthcounter - ball_diameter / 2)) + ((int)Math.Floor(heights - ball_diameter / 2) * (heights - ball_diameter / 2))) <= (int)Math.Floor((ball_diameter / 2) * (ball_diameter / 2)) +4)
                    {
                        float direction_to_center = MathHelper.ToDegrees( (float)Math.Atan2(widthcounter, ball_diameter - heights) );
                        //we only add the vectors that represent points on the circumferance of the ball...
                        //we dont need an ID# per say, we need an "angle to center", becouse this will be used to find new course.
                    all_ball_pixels.Add(new Vector4( ((int)widthcounter) + (int)Math.Floor( position_X) , (int)Math.Floor(position_Y) + ((int)heights), direction, direction_to_center ) );
                    }

                    widthcounter--;
                   
                }
            }

            is_defined = true;
            heights_list.Clear();
   
        }

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2