vector graphics collision

BlitzPlus Forums/BlitzPlus Beginners Area/vector graphics collision

El Neil(Posted 2006) [#1]
hello all.
due to the fact that with rotateimage():

"This command is not fast enough to render rotations in real time!"

i am making a small game with a tank drawn in vector graphics using a series of points which are continuously calculated using sin and cos. ive got the tank moving and rotating but need to detect collisions with the body of the tank. is there a formula for checking whether or not a specified point falls within a rotated rectangle or not?

thank you for your help
neil


Jesse(Posted 2006) [#2]
I am working on a tank game also but mine is in blitzmax and is tile based. It seems to be fast enough for what I am doing. I am also using sine and cosine to move and to detect collition and that is taking a toll on speed. I am interested in figuring out how you do it. If you ever figure it out. I might be able to aply it on my game.

Jesse


neilo(Posted 2006) [#3]
I don't have time to Blitzify this for you right now, but consider this. Your "rectangle" consists of four points - call them (x1,y1), (x2,y2), (x3,y3), and (x4,y4). A rectangle is made up of two triangles - (x1,y1), (x2,y2), (x3,y3) and (x1,y1), (x3,y3), (x4,y4).

The problem now becomes finding if a point lies within a triangle; a rather common 3D operation. Microsoft Research came up with an interesting little beastie using Barycentric coordinates (don't even think to ask me what that means) which offers a foolproof, simple way to determine just that. The original page is gone, but the algorythm is discussed here and I've reproduced the essential bits below:

A fail-proof method is to compute the barycentric coordinates. For a triangle {(x1,y1), (x2,y2), (x3,y3)} and some point (x0,y0), calculate

b0 = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
b1 = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0
b2 = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
b3 = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0

Then if b1, b2, and b3 are all > 0, (x0,y0) is strictly inside the triangle; if bi = 0 and the other two coordinates are positive, (x0,y0) lies on the edge opposite (xi,yi); if bi and bj = 0, (x0,y0) lies on (xk,yk); if bi < 0, (x0,y0) lies outside the edge opposite (xi,yi); if all three coordinates are negative, something else is wrong. This method does not depend on the cyclic order of the vertices.

Have fun!

Neil


Jesse(Posted 2006) [#4]
Now the problem becomes converting this:


to that
I know it's the wrong place for this code but it's just being used as an illustration. I hope I won't have to finish this in an asylum.

thanks neil. I'll look up that definition in my oracle "google".


neilo(Posted 2006) [#5]
Curious: Why are you porting BlitzMax code into BlitzPlus?


El Neil(Posted 2006) [#6]
thanks for your help guys. ill have a go over the next few days. youve been a great help.


thanks again

neil


Jesse(Posted 2006) [#7]
I am not portint I just needed the math for my game. I just needed an alternative from sine and cosine. so I was reading this post and it provided a logic good for any programming language. I will still program in Bmax but I will use this Neil's ilustrated equations which is 100% language independant.


El Neil(Posted 2006) [#8]
jesse your game seems incredibly similar to mine (although you code is FAR neater), i just need to decide what im going to do with the tank once it is colliding with things. kind of the crux of the game, lol. my tank is made of 19 points which are all calculated as polar coordinates (distance and angle) from the centre point, depending on the current angle. i have also made it so you can rotate the turret independently. i can use neilo's method to calculate collision using the outer 4 points of my tank.


Jesse(Posted 2006) [#9]
if you are interested in an executable of the game you can download it from:
http://filebeam.com/b83435ad7a4db9ffebea4f2d524873bb
then tell me how similar its to yours. and maybe we can help each other.


El Neil(Posted 2006) [#10]
hmmmm. tried to follow the link but it says "invalid download link".

neil


El Neil(Posted 2006) [#11]
oh and btw, your barycentric coordinates are the bees knees. they work perfectly. thank you.

neil


Jesse(Posted 2006) [#12]
try it again it should be accessible now. if not I can email it.


El Neil(Posted 2006) [#13]
got it. yeah its cool, same sort of thing i was doing really, except mine is wireframe graphics. i like the AI too, i havent even thought about that yet. how did you rotate the tank image? did you use rotateimage()?

neil


Jesse(Posted 2006) [#14]
yes, the difference is that I am using bmax and uses hardware acceleration for the graphics so its a bit faster. the ai is a dumb random turn, and turn when a wall is reached. nothing major. I am trying to implement a path finding algorithm but I am having problems implementing it, I have the algorithm and it calculates the path, but when I try to apply it.... ??? I am braking my head trying to figure it out. I can't get them to follow the patter. another problem is that my a* pathfinder is taking up too much time to find a path that it pauses the game while it finds a path. so when you have twenty tanks it becomes quite annoying. I put the game to the side for a while while I figure out a way for the tanks to follow a pattern.


I am glad you like it. I would like to see a sample of your game too. if interested you can email me or you can put it in the same place where I put mine and I can grab it from there. yust don't forget to get the link address or we both won't be able to retrieve it.

If you thing it is nice, consider that it has taken me almost six months to get it here. and it will probably take me another 2 months to iron this bugs out.
Maybe it is taking me a bit too long but this is a hobby for me and I am learning at the same time.

if you are interested in the source code, let me know and I will email it to you.


El Neil(Posted 2006) [#15]
http://filebeam.com/67d8b05145a29b9be2463c4cfd030130

here is my demo. still very basic: about 5 hours' work. use arrow keys to move and A and D keys to rotate the turret. if you hover the mouse over the tank you will see the barycentric stuff in action.

neil


Jesse(Posted 2006) [#16]
interesting neil. it's even similar to how I started. I hope you finish it.