vector graphics collision

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

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

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:


Have fun!

Neil

Now the problem becomes converting this:

                                                '       w(top)
	Method move(M:TMap)                         'l    x--------x    r   tank and               also sine and cosine
	  	Local sw1#,sh1#                     'e    |        |    i   gun are at             are precalculated.
		Local sw2#,sh2#	                    'f   h|        O----g   0 degrees 
		dx = cosine[angle]*speed            't	  |        |    h   radius to all four corners is calculated
	  	dy = sine[angle]*speed              '	  x--------x    t   from the center of the tank
		If speed									'       (bottom)
		For Local enemy:Ttank = EachIn tank_List
			If index <> enemy.index Then 'check collision against other tanks
				If ImagesCollide(tank_img,M.x+NODE.x+dx,M.y+NODE.y+dy,0,..
				             	 tank_img,M.x+enemy.NODE.x,M.y+enemy.NODE.y,0) 
					speed = 0.0
				  	If Not turning Then collided = True
				EndIf
			EndIf
		Next
		If 	speed > 0 Then 'locate front 2 corners of tank
			sw1 = cosine[(angle+rta) Mod  360]*radius 	'x of front top corner of tank
			sh1 = sine[(angle+rta)Mod 360]*radius 		'y of front top corner of tank
			sw2 = cosine[(angle+rba)Mod 360]*radius 	'x of front bottom corner of tank
			sh2 = sine[(angle+rba)Mod 360]*radius 		'y of front bottom corner of tank
		ElseIf speed<0 Then 'locate rear 2 corners of tank
			sw1 = cosine[(angle+lta)Mod 360]*radius 	'x of rear top corner of tank
			sh1 = sine[(angle+lta)Mod 360]*radius 		'y of rear top corner of tank
			sw2 = cosine[(angle+lba)Mod 360]*radius 	'x of rear bottom corner of tank
			sh2 = sine[(angle+lba)Mod 360]*radius 		'y of rear bottom corner of tank
		Else ' if tank is not moving dont calculate corners.
			sw1 = 0.0
			sh1 = 0.0
			sw2 = 0.0
			sh2 = 0.0
			
		EndIf
		'detect collition with wall 
		If  M.maze[(NODE.x+dx+sw1)/32][(NODE.y+dy+sh1)/32]< 50 And .. ' 50 refers to the tipe of tile being used 
			M.maze[(NODE.x+dx+sw2)/32][(NODE.y+dy+sh2)/32]< 50 Then
			If (NODE.x+dx)<(m.width-BITMAPWIDTH) And  NODE.x+dx > 0 Then 
				NODE.x:+dx
				If controlled = index
					'moving right along the x axis
					If  ((m.x+SCREEN_WIDTH) < (m.width-TANK_MAX_SPEED)) And ..
					    ((m.windowshiftx+NODE.x) > m.halfviewwidth) And  dx >0 Then m.x:+dx  
					'moving left along the x axis
					If  (m.x > TANK_MAX_SPEED) And ((m.windowshiftx+NODE.x) < m.halfviewwidth) And dx < 0 Then m.x:+dx	  
				EndIf
			Else
				speed=0.0
				collided = True
			End If
			'move up Or down
			If ((NODE.y+dy)<(M.height-HALFBITMAPHEIGHT)) And  (NODE.y+dy > 0) Then
				NODE.y:+dy
				If controlled = index
					'moving down
					If  ((m.y+SCREEN_HEIGHT) < (m.height-TANK_MAX_SPEED)) And ((m.windowshifty+NODE.y)>=m.halfviewheight) And dy >0 Then m.y:+dy
					'moving up
					If  (m.y > TANK_MAX_SPEED) And ((m.windowshifty+NODE.y) <= m.halfviewheight)And dy < 0 Then m.y:+dy	 
				EndIf	 
			Else 
				speed=0.0
				collided = True
			EndIf
	  	Else
			speed =0.0
			collided = True
	  	EndIf
		EndIf
		cannon.move(NODE.x,NODE.y,angle)   'this moves the cannon on the tank.
		If Bullet_list
			For Local bullet:ammo = EachIn Bullet_list
				bullet.move(m)
				If Not bullet.life Then Bullet_list.Remove(bullet)
			Next
		EndIf
	End Method

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".

Curious: Why are you porting BlitzMax code into BlitzPlus?

thanks for your help guys. ill have a go over the next few days. youve been a great help.


thanks again

neil

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.

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.

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.

hmmmm. tried to follow the link but it says "invalid download link".

neil

oh and btw, your barycentric coordinates are the bees knees. they work perfectly. thank you.

neil

try it again it should be accessible now. if not I can email it.

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

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.

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

interesting neil. it's even similar to how I started. I hope you finish it.