how to collision check "teleported" stuff?

Talk about your skill passion! Ask questions, get feedback, post something cool!

Moderator: samw3

User avatar
bugala
Posts: 1279
Joined: Wed Oct 21, 2009 11:43 pm
Location: Finland
Contact:

how to collision check "teleported" stuff?

Postby bugala » Thu Sep 26, 2013 8:10 am

Theres a coding problem i have been thinking for couple of years perhaps every now and then, but have never really figured a good solution to it, so I decided to loan fellow CDN brains on this one.

C = Pacman
U = Ghost
. = empty space in screen

pacman chasing a ghost for example:

..CC...UU...

Noprmally it goes:

..CC..UU...

...CC.UU...

....CCUU...

.....CCU... A Collision! (which you figure out through collision check)


however, there are many different kind of instances, when it happens to be that one or other of the collision characters is so fast that it might transport past the enemy that you should figure out if it hit or not through collision check.

Lets for example take a bullet.

P = Player
E = Enemy
- = Bullet
. = empty space

P.....E....

P-....E.... (Bang!)

P...-.E....

P.....E.-.. (Enemy was supposed to get hit, but since you are using collision check to check for hits, bullet just went past the enemy and collision check returns false)


For, i guess, years, i have been trying to figure out good solution for checking this thing out, but have never figure out one.

Bullet would be one easy example of this, since bullet would go on straight line and you would have pretty good idea whom it can even hit.

But lets take for example my latest speedgame. In this one you were using Mouse to hit enemies, this resulted, that not only you had to move your mouse fast enough, you also had to move it accurate enough. For when you tried to hit one of the enemies, you were quite likely to move your mouse fast enough that the pointer moved past the enemy already. And since program was checking simple collision check based upon mouse pointers current position, this resulted in false being reported, when in fact, enemy should have been hit.

But this is also good example case. Bullet might always move straight to right for example, but in mouse movement case, it could have moved at any place to any direction.

This can result in several problems.

For example, one possibility would be to trace the most direct route from previous x and y to new x and y, and then for example every 20 pixles do a collision check with everything to see if it hits something, but in pracitce enemies and mouse pointers form might be such, that they would be mising some points.

As example,i had round bocing glove in my speedgame.

lets say movement is following:

...
...
x..


to

..x
...
...


Okay, now lets suppose the object is rectangle like in my speedgae, and now lets take a look at one possibility of doing collision checks before reaching the final destination:

......xxx
......xxx
...xxx...
...xxx...
xxx......
xxx......


As you can see, in this example idea is ha box is 3x3 size, and then you get check with little jump forward. But this results in some obvious blind spots where some areas might have only 1 pixel sized checking point, when it should be checking for 3.

And especially, if other object happens to be moving the same way, then this can be a very big problem already, as they might be obviously colliding to each other, but due to program, both are checking only 1 pixel sized area from each other, which dont happen to collide.

Of course this can be get around by checking through every pixel of movement, but then that is not a good solution either.


Anyone have any good solutions for this problem?
User avatar
samw3
Site Admin
Posts: 1239
Joined: Sun Dec 16, 2007 2:00 pm
Location: Toccoa, GA
Contact:

Re: how to collision check "teleported" stuff?

Postby samw3 » Thu Sep 26, 2013 11:09 am

I've found that the easiest way is to do a Line Segment to Axis Aligned Bounding Box collision test.

http://stackoverflow.com/questions/9935 ... ange-in-2d

Instead of testing for points, test the line segment between the current point position and the previous one.

God Bless!
User avatar
bugala
Posts: 1279
Joined: Wed Oct 21, 2009 11:43 pm
Location: Finland
Contact:

Re: how to collision check "teleported" stuff?

Postby bugala » Thu Sep 26, 2013 1:37 pm

Thanks from that one, that one sounds like an answer to most of the problems i have been thinking about.

However, there is still one thing. What if two rectangles are both moving atr high speed, and you need to check if these intersect at any point?

Looks like a lot more tests even with this method, making it difficult task again.
User avatar
PFC
Posts: 633
Joined: Sun Dec 16, 2007 5:57 pm
Location: Canada

Re: how to collision check "teleported" stuff?

Postby PFC » Fri Nov 08, 2013 10:04 am

In the case of two moving objects you can generate mid-frame collision boxes(or segments) to check if a hit may have occurred and either report a hit or run a more precise simulation from there.

two bullet case a->A, b->B:
.........B
........./
.a----/----A
......b

test line intersection:
......./
.----x-----
...../

We probably have a hit, now either report the hit(if low accuracy and some false positives are ok) or retest based on either a mathematical representation of the system or a finer time-step simulation which can also run smaller intersection tests:
f1)
.
.a
.....b

f2)
.
.a - /
.....b

f3)
......./
.a . -
.....b

In the second simulation we see that both bullets do not intersect. This may be a test that is too cpu-heavy to run on a large number of items all the time, but by only running this test if the first test returns true we save allot of CPU assuming most items aren't coliding non-stop. For other shapes replace the line intersection with a rectangular or other type of collision test.
TheLittleSettler
Posts: 120
Joined: Fri Nov 19, 2010 10:08 pm

Re: how to collision check "teleported" stuff?

Postby TheLittleSettler » Sun Nov 10, 2013 12:36 am

Just want to add in here a couple of things:

- I'd typically just iterate collision checks though fractions of positions. Granted, its horribly inefficient. Later I can find a good solution if I actually finish the game. Also, knowing I can find an elegant solution frees me to not have to try and prove myself in what I write. Hacky solutions with contentment is great gain. Note I'm not advocating bad coding practices. Readability is still key. I just get caught up looking for the perfect solution way too often.

- As mentioned one good solution would be to use line collision(s). If precision is needed, use multiple line collisions. Iterate through all boundary points on an object, checking line collisions with their new position. But that would not be totally precise. It could still miss things, for example if a large object moves through a tiny object. Checking lines for each boundary point could miss as one may move inside the other. So...draw the situation, model the collision checking to it. But then, you end up possibly adding more and more line collisions for more precision, which is just brute force. I'm sure there's a better way (ie. check area/volume based checking)...not going to work it out now though.

- There is allot of power in trigonometry...(forget most maths, but get familiar with trig and modulus). You could use trig for this (I'm thinking specifically of an area based check...that is, check all area that the moving object touches between this frame and the next).
humanError
Posts: 28
Joined: Tue Apr 03, 2012 5:09 am

Re: how to collision check "teleported" stuff?

Postby humanError » Fri Apr 04, 2014 6:29 am

Raytracing could help with bullets. If the ray hitvis registered then bullet hits. I would not use physics collider. Another option would be to use pixel collision. You can always increase the interwall of your physics update loop (fixed), but this is glutch fix and reduce your performance. Or you can make bullet having an overside collider that is balanced on front side and make sure your 3d mesh has really big trigger type collider (one that registers only collision but cant create forces) >> there is many ways to workaround this problem.

Who is online

Users browsing this forum: No registered users and 3 guests

cron