3D-Collisions basics

13 02 2009

One thing that is absolutely vital in most games is the actual event when two objects somehow collides.

Be it bullets that collides with it’s target, wheels touching the floor, a paperMario reaching the end of the map or just a FPS-player that tries to walk through a wall, we just need to see whether something is touching something else (especially if inappropriate :) ) Now, there are several ways to detect this and as usual it’s all about processor vs quality. The absolute best and accurate way to do this is to let every single face check with every other single face out there if it has intersected and then dispatch that a collision has occured. Now, this (we call it face <-> face collision) is extremely demanding and even top notch 3D accelerated AAA-titles barely uses it so let’s just put that aside for the mathgeeks and dreamers and let’s look at some realistic aternatives.

Let us start in the other end. How fast can we go??? Well, I say (you can bash me as much as you want to, I have not studied this at all) that he fastest kind of collisiontest you can have is to just make a static numbercheck.

if (mesh.y < 0) { mesh.y = 0}

Yes, we all fid it extremely obvious but sometimes people make things WAY to difficult for them. Still in this game I have used this collisiontype many times where some people would have tried a more demanding approach just for the sake of being dynamic. Just because of the processorpower it takes to detect collisions I have purposely chosen to create a rectangular arena, opposite to the arena I used in my last game. It doesnt have any walls at the moment but when it get walls I don’t have to create some difficult collisioncheck, just a static numbercheck will make the job!

What about the ground?? Well I could have added bumbs in a sandy arena but now I choose a flat one for several reasons.

1. As soon as something like the grenade goes Z < 0 it will bounce up again.

2. When it’s flat and no units will be able to jump/have physics, I can remove all bottom faces of the unit. You should see them, they are all stripped and seethrough from underneath.

3. Putting obstacles on the arena (extra walls, barrels etc) is as easy as Z=0

Now you probably already knew this stupid collisioncheck but I still want you all to remember this simple solution when creating your design for the game. Maybe your 3D pong should go with square walls instead of your freakishly new plasmastyle.

Now, lets start with some “real” collisiontesting then. After the static one, I might be brave enough to say that the next least perfomancedemanding collisioncheck is a single distancecheck. “How far from this object is that object?? Is it to close? then BOOOM!” -style.

In Papervision we got the math already done with it’s  function: DisplayObject3D.distanceTo(otherObj:DisplayObject3D) .  (no it’s not rocketsciencemath either but it’s nice we don’t have to dig out mr.Pythagoras more than needed)

If the distance is lesser than your set value, then you consider it to be a collision. Now, this method is very rarely used but if we enhance it just a liiiiittle bit you will have one of the most common collisiontests in games…

Sphere-collision

When I was a kid, (yes, I promise i have been) I just couldn’t understand how spherecollision could be faster to use than ermm.. other that we will bring up in a short while. Spheres are complicated and as soon as round shapes are involved it means using PI and Sinus and maybe derivata. No, not this time. If you just think of it for a second: distanceTo() is really a sphere. It doesn’t have any direction but checks the distance in EVERY direction building a kind of a “sphere” around the object where the distance is actually the radius of the sphere. Look at this image:

spherecollision

Here I have set a distanceTo limit on the Defender and a distanceTo limit on the grenade so in code it is just:

if (defender.distanceTo(grenade)- (defender.collisionSphereRadius+grenade.collisionSphereRadius) < 0)  { trace(“defender is FUBAR!!!”)}

It’s all about the distance between the objects but we added some kind of radius to each object simulating it’s size. In my game I have set this radius manually and actually do have a “showCollisionSphere” function on each unit and bullet so I can see that it is somewhat correct with the size of the mesh. Still in Papervision3D DisplayObject3D you already have tis kind of collisiondetection in the function: hitTestObject( obj:DisplayObject3D, multiplier:Number=1 ):Boolean

This function takes the furthest pixels away and creates a radius out of that. This could create a collisionsphere that might not be the best for the whole object and therefor there is also a multiplier parameter if you would like to increase or decrease the size of your “sphere”. It works great (I just wanted to create my own flexible collisioncheck but I recommend using the inbuilt one).

Box Collision

What if my object is very flat? It might even be a plane! Creating a collisionsphere around that would just be stupic as it would, in worst cases, trigger collisions way beyond the actual planes location. The other single method that is used just as much as sphere collisions is the box collision. You have probably done it a thousands times already keeping something within a boundary or similar tasks.. does this looks familiar?

if (obj.x > MAX_WIDTH){obj.x = MAX_WIDTH;}

else if (obj.x < MIN_WIDTH){obj.x = MIN_WIDTH;}

if (obj.y > MAX_HEIGHT){obj.y = MAX_HEIGHT;}

else if (obj.y < MIN_HEIGHT){obj.y = MIN_HEIGHT;}

this is actually the technique to use with box collisions. Just check wether a box is within another box.

In every DisplayObject3D that contains a geometryobject you can somewhat easily achieve this as the geometryobject contains a variable with the freakedout name: aabb

This is actually the bounding box we need ( yes it is short for AxisAlignedBoundingBox). It holds all the MAX and MIN values of your mesh in all 3 dimensions so it’s just a matter of creating a lot of “If”‘ rows and you will have your own box collisiontest. Box collision is not as fast as spherecollision but is a very good alternativ for meshes with different proportions.

This was just some simple theory. I will try to stitch this up in some real code in the game to show you later on. Now already I can tell you that if you want to optimize collisioncheck you really should think about WHICH objects really do need to be checked with each other?? Can I remove some of the collisionchecks without harm? All geometry will probably not need to be checked against each other and even some units doesnt have to be checked with some bullets (eg the unit that shot the grenade doesn’t need to be collisionchecked with the nade). I am fond of lists in different ways so I will probably create one now again where objects subscribes to the list where it needs to check with other objects in that particular list.

59

The just-released StreetFighter IV went back from polygon collision to use classical box-collision just to speed up and recreate the classical feel of the game.

Also one small notice is that there are several other types of collisionchecks but thse are by far the most common ones. They are also very easy to mix together and it’s not unusual that game uses BOX <-> SPHERE collisions and POLYGON <->BOX etc.   Hope I could at least enlighten someone with this basic theoretical text. Have a great time creating things I can play!

Advertisements




Multiplayer in Flash – How to..

5 02 2009

The biggest reason I chose to start up this project at this current date is that before current date it has not been possible to create what I am trying to do , using Flash. In fact, it is not completely possible yet when it comes to some 3D features but I’m an optimist and would like to stay prepared for what both PV3D and Flash has to offer the years to come (yes, I count this project to be in progress for years). Still when it comes to fast paced multiplayer games where two users, sitting by each computer, plays against each other it has just become reality!

Adobe has just opened the (beta)doors to their new protocol (RTMFP) and very shortly it means that.. it can now be done.

If you’re interested right now to try it out wothout reading my oracle guidelines, just head over to Adobes dev. Centre and check out Stratus

Without getting too technical on the subject I want to introduce what the difference is at why we need it, because this article will be about how to think to even be able to create a mp-game using streaming datatransfers client-client.

Netcommunication for dummies

Yes, we have been able to connect 2 (or more) flashclients directly to each other and communicate but until now it has only been available using a TCP-IP like protocol. (if you don’t know what it is, never mind, it is just porn for netfreaks). TCP-IP is very good in the aspect that the same data being sent is actually winding up in the right order and shape that it was sent. So, it is secure and stable. Problem is that the if “recieving client” doesn’t properly get the data sent it will wait until it really really gets it. No other data can be transfered meanwhile and in worst case it can choke up the whole system. In the end TCP/IP assures that the exact data being sent is coming in in the correct order. Maybe great for turnbased games and similar but not for our hot actiongame.

So now, something different has come up.  Adobe’s RTMFP is a UDP-based protocol (porn again) and UDP does not really care if all the data comes in in the exact order. It just keeps on sending and recieving data. This means that no “doublechecks” needs to be done clogging up the system and no chokes happenes if one package gets lost along the way. Don’t you worry, there will always come another package ;)

So basically, finally we got fast and uncontrolled data streaming on Flash (good for cam-streaming and such as well). I will not in this article explain codewise how to set up a connection using this technique but it will surely come as this is very much needed for the game. Now how can we use this? What do we need to consider when building a game?

Movement and actions

Actually, without really telling you, I’ve already tried to think multiplayer when it comes to this aspect already in the game. The first approach every mp programmer tries before knowing better (me included) is to just send the transformationdata to the other gamer and believing that just by sending my position and rotation values should be enough to have a great multiplayer game. The problem you will see is that transfers of data does not sometimes sync with the framerate of the game. Sending a package each and every frame will probably get heavy on the system and there is no saying that all those packages will be recieved at the same rate as they were sent.

Also you must consider the fact that the user on the other side might have a worse computer than you with a much lower framerate. Also there is this horrible lag-issue as it takes time for data to be transferred etc etc.

So we can easily say that we could use some tips here.

Predict the future

If we just could predict the actions of the other gamer we could render his unit due to these predictions. Now we at least try, right? First of all, instead of sending coordinates and rotations only we should also send some controls-data.
Actually the controlsdata is more important than the transformdata. Say you recieve some controldata. You loop through all your units on the screen, first your and transform it due to your controls and then the remote unit using the controldata you just recieved. What happens if you dont get any data next frame??? Well if you based the remote units movement only on coordinates it would get stuck on the same position as before now instead you can assume that if he held the forward button in the last millisecond, the best guess is that he/she probably does that now as well, so you continue calculate a new position using his/her last controldata.

Now whenever you recieve new data, use the new data both to control the unit (using unit data) and “tween” towards the absolutely correct positions and rotations. The result will be something similar to these two pictures:

mp_movement1mp_movement2

As you can see, on the top picture, using only transformdata will keep the unit stuttering to new positions on the frames it recieved new data meanwhile using controldata makes the unit move each frame BUT you will have some misplacement on the unit as it continues cusing the same controldata til a new is recieved. Therefor the controldata needs to be mixed with transformationdata so the most realistic movement can be achieved.

Time is relative

Until now, we have updated the speed and rotation each frame equally. Fine, this might work well in a singleplayer game as you are the only one competing against yourself but what if two players have different capacity on their computers? One computer is an ultramachine updating the game at 35 fps meanwhile the other one is going slow on 5 fps. This means that the fast comp will update the frame 35 times = moving it’s vehicle 7 times more often than the other one. Result is that the guy on the fast computer will have a faster moving unit. Also will he see the other unit move very strange as his computer will calculate the movements on the remote unit faster than it is actually being calculated on the slow computer.

Well you hear where this is leading… people will yell “CHEATERS” at each other and we will not have that cozy, nice and social game that we want. There are a few different solutions to this but the one I really recommend is called Delta Timing.

Move by time, not by frame

Delta Timing is to calculate how much the unit is transforming through time, and not static through each frametick. To achieve this you need to check the timespan between each movement. Let me give you some theory (yes, Ive done that this whole article)…

Assume you want the unit to move 10 pixels each frame. That is if your framerate is 30 FPS constantly. Then we have two good variables to start with, now lets calculate the time it really takes between one movement to the other. My pseudocode would look something like this:


{

//...here goes a lot of gamecode and nice stuff ...

currentTime  = currentTimeInMilliSeconds

timeItTookSinceLastTime = currentTime - lastTime

timeItShouldTake = 1000 / 30  // this gives how many milliSeconds it takes for one frame in 30FPS

timeScaler = timeItTookSinceLastTime / timeItShouldTake // give you a number that should be close to 1 if FPS is good.

lastTime = currentTime

}

With above code (no it’s not working if you try it, it’s just pseudo-mumbo-jumbo) you will get a variable timeScaler that will be lower than 1 if the FPS is actually going higher than 30 and higher than 1 if the FPS is dropping so this exact timeScaler must be used to compensate all speeddrops or speedboosts a FPS could get. So whenever you update, say a movement, each frame. instead of

unit.x += speed

with deltatiming you will now always use

unit.x += speed*timeScaler

Same goes with rotation, weapons, animations, cameramovement and everything that is speeded up or slowed down with your current fps.

Yes I know I haven’t given you a real line of code but the theory needs to be there before we actually create something with it. Now, swap your browser with your favourite AS3 IDE and start playing around with these things. I will soon implent it in the game code.

Cya

/Andreas





And so the coding begins!

27 01 2009

I’ve sat down now and structured up some of my thoughts into basic Interfaces but to be able to visually organize everything I start up with setting up a little folder structure. Just like this:

folderstructure

I will be using Flex 3 as my IDE so some future screens will probably showcase that environment. If you do not know how to set up a Papervision project in Flex 3 this site is actually not the right one to find the answers in. I’ve seen plenty of great tutorials out there so I won’t dive into that here.

As you can see a lot more folders and structures will be needed later on but his will be perfect for the start I intend to write.  I know you are all eager to begin setting up a scene with Papervision but I actually will first create a few small classes first that will make it easier for me to explain how the units (as I will call all combat vehicles from now on) will behave. Let’s actually start with something as weird as the game controllers (!)

package interfaces
{
	// this is the Interface for all controllers, be it local, ai or remote via multiplayer.

	public interface IUnitController
	{
		// each Controller gives away a ControlMatrix-object containing at least the following parameters:
		// horizontal: , vertical: , newLastPosition:   if true then these values are used: , posX:, posY:, rotation:
		function getControl():Object
	}
}

I want to make sure that the network gaming will be a part of all planning from start and this is a great way to do that. Above is an interface that will make all controllers to behave in the same way. To show you a normal implementation of this interface, lets create a normal, local controller.

package controllers
{
	import flash.ui.Keyboard;
	import se.xcom.input.ArcadeKeyboard;
	import interfaces.IUnitController

	public class LocalController implements interfaces.IUnitController
	{
		private var key:ArcadeKeyboard
		public function LocalController()
		{
			key = new ArcadeKeyboard(Main.scope)
		}

		public function getControl():Object
		{
			var tVert:Number=0
			var tHoriz:Number=0

			if (key.isDown(Keyboard.UP))
			{
				tVert++
			}
			if (key.isDown(Keyboard.DOWN))
			{
				tVert--
			}
			if (key.isDown(Keyboard.LEFT))
			{
				tHoriz--
			}
			if (key.isDown(Keyboard.RIGHT))
			{
				tHoriz++
			}
			var Ob:Object = {vertical:tVert,horizontal:tHoriz,newLastPosition:false}
			return Ob;
		}

	}
}

This little class over here checks whether the arrowkeys has been pressed. Instead of sending a true for each direction, this class actually creates a Vertical axis where UP becomes +1 and DOWN becomes -1. On the Horizontal axis RIGHT becomes +1 meanwhile LEFT returns -1. I will later on show you how this can be useful in such arcade game. Also I’ve used a custom keyboard-class called ArcadeKeyboard that I created a while ago as AS3 does no longer contain the useful “isDown” features that AS2 had.  I’ve temporarly packed this class + a degreeconverter down for download here if someone would find it useful.

Now, let’s create a temporary Unit file just to see if we can control it with our controllers. But first I want to set up a decent Interface for our units as there are functions that all units to perform, eg. moving around, checking for collisions, attacking etc. For now, let us create this interface:

package interfaces
{
	public interface IUnit
	{
		function transformUnit():void
		function checkCollisions():void
	}
}

What this small interface just tells us is that: Every single unit that is even trying to implant me must have a transformUnit function and a checkcollision function. Sweet! But we will not stop there this time. We KNOW that all units will behave in a certain way when it comes to movement and collisioncheck. We also already know that each unit will be a DisplayObject3D (Papervisions own piece of DisplayObject), that each unit will carry a badass gun etc etc. So why create all this code over and over again for all units? Let us create an abstract class! You don’t know what that is? heck.. I’m just starting to learn myself, but to make it simple: an abstract class is a class that will never be instantiated on it’s own as it only contains parts of the code. That part is the code that is similar to ALL classes that will extend from that abstract class.

This is not supposed to be a lesson in OOP, but if you find the upcoming things weird and stupid I suggest you to find some tutorials or books that will cover the basics of OOP-programming, inheritance and design patterns as it will totally change your way of coding.  Now let’s get to business and maybe things will clear out a bit:

package units
{

	import interfaces.*;
	import org.papervision3d.objects.DisplayObject3D;

	public class AUnit extends DisplayObject3D implements IUnit
	{
		private var mesh:DisplayObject3D
		private var control:IUnitController
		private var transformer:ITransformer
		private var unitId:uint

		public function AUnit(mesh:DisplayObject3D, control:IUnitController,transformer:ITransformer, id:uint)
		{
			this.unitId = id
			this.mesh = mesh
			this.transformer = transformer
			this.control = control
			this.addChild(mesh)
		}

		public function transformUnit():void
		{
			// move and rotate the object due to the transformer.
			transformer.transform(mesh,control.getControl())
		}

		public function checkCollisions():void
		{
			// abstract , must be implanted later on!
		}
	}
}

Ok, lets see what we have now. This is an abstract class that will be the foundation of all Units hereafter. To create a unit we must therefor pass in a 3D-model (which I from now on will call meshes), we must also pass in a control which we alread happened to have created one. Good.
Then there is a new strange thing which I now call a Transformer. This is the component that will lie BETWEEN the unit and the controller. So from the controller comes data which buttons has been pressed (sort of). Now this TRANSFORMER turns that data into something visually splendid like moving the unit forward, rotating it, making it roll, float or shrink…
So even if we have the same controller for every unit they units might behave differenly as they have different transformers connected to them. Sounds intruiging, ey? Let’s create a transformer. After that I think we are ready to actually see something visual in 3D :)

package interfaces
{
	import org.papervision3d.objects.DisplayObject3D;

	public interface ITransformer
	{
		function transform(mesh:DisplayObject3D,control:Object):void;
	}
}

Each Transformerclass is now forced to have the function “transform” in them and also do they need to pass the parameters ‘mesh’ and ‘control’. Good, thats all we need! Let’s for starters make a simple Car-transform class (making the unit behave just like a car when controlled).

package transformers
{
	import interfaces.ITransformer;
	import org.papervision3d.objects.DisplayObject3D;
	import se.xcom.math.Degrees;	

	public class CarTransform implements ITransformer
	{
		// simple carsteering with no skid

		private var speed:Number	// current speed
		private var acc:Number		// accelerating force
		private var moveFric:Number // friction force (0 - 1.0)
		private var rotSpeed:Number // turning speed

		public function CarTransform(acc:Number, movementFriction:Number, rotSpeed:Number)
		{
			// setting up simple physics variables
			this.acc = acc
			this.moveFric = movementFriction
			this.rotSpeed = rotSpeed
			reset()
		}

		public function reset():void
		{
			speed = 0
		}

// now heres that most important part where the mesh will be transformed using the data from the controller.
		public function transform(mesh:DisplayObject3D, control:Object):void
		{
			// movement
			speed += control.vertical*acc
			speed *=moveFric
			mesh.x += Degrees.dCos(mesh.rotationY)*speed
			mesh.z -= Degrees.dSin(mesh.rotationY)*speed

			// rotation
			mesh.rotationY += rotSpeed*speed*control.horizontal
		}

	}
}

You wonder what that weird Degree class is? Well let’s put it like this. I’m selflearned in every way. I have not studied programming, nor game design and definitely not Math. So when the inbuilt Math class decides to use radians instead of degrees (which all displayobjects are using when rotating) I decided to create a simple class that lets you use Cos and Sin with degrees. There you go. If you’re a mathohman, please convert it to whatever you like. If you are like me, you can find the class with the other ArcadeKeboard class here.

Damn! This is becoming a huge post. I know we haven’t even compiled the code once yet and we got nothing to show so far but underneath the surface something really nice is about to happen. I stop his post right here and will soon be in again with our first 3D visuals. Yes I promise! Next time it’s time to dive into Papervision’s wonderful sea (space?)