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




Kill your darlings

9 02 2009

One of the most important tips I could give you in here is not in any AS3 area nor is it a 3D tweak but it’s a pretty common saying in many creative industries.

‘Kill your darlings’. The simple meaning of this is to try to be as objective as possible and don’t fall in love in some of your best functions, your nicest effects or you genius structures. The hardest thing you will face is when you show your work to the crowd/your friends/or even worse your children and they just say..  “Why did it act like that?” It’s so idiotic obvious and STILL they have the guts and ask such a question??? Or maybe: “So what am I going to do now then?”, “It feels like it’s warping”. But bugs, and bad playability can be dealt with. The WORST thing you will face is when things work terrific! When your effect is just heavenly and you have just created the smartest AI ever and then you’re audience is telling you that, “The effect is bringing the speed down”, or “The guys act too smart, remember it is meant to be casual game. Let them just jump out and be shot!”

I’ve worked with a couple of game publishers and game development has never been as hard as when it is chopped, sliced and stripped from all genius quality just because it need to be more accessible for a bigger audience. You’re genius gameplay is switched with an old overused controlscheme, just because people want what they always done…

Now, we are not all there and most of us will probably face that problem having to answer in front of a publisher BUT this is an important lesson to be learnt in everyday game development. Take this tank I created today:

flamethrower

This tank has been in my plans for a long time and when I finally created the flamethrower I think it looks just great to be Papervision. Still I know I cannot even consider using this weapon after creating it. Why? Well, when holding down the mousebutton, spraying out all that fire the fps drops under 22 fps. It’s a nice effect and I’m quite proud of the result but I know that in the end, I will cut off a lot of players if I let such a demanding effect be in the game. 22 FPS is no big deal but this is just one tank, what if both players use the tanks? Many players will have lesser performing computers than I have, there is still a HUD to be implanted, some collisiondetection, environmentart, sound etc…

Listing it up like this it sounds obvious not to use the effect but I see this over and over again. People fall in love in their physics, in their animated textures, in their multiplied blendmodes.. and in the end as the FPS drops they just can’t ‘kill their darlings’ and instead loose the interest.

Have I removed the idea of the flamethrower? No, not yet, I still have a couple of methods to try but Papervision is really a tight area and demands optimization and chokes immediatly at the slightest overuse of effects or bad coding. Just face it. Choose what few elements you want to have and stick with it. You cannot have shadows, particles and physics and in the middle of development include environmentmaps. You will have great screenshots but you will never be able to release the game to public.

Kill them. Move on.





Paint the paper

28 01 2009

My guess is that PV3D chose the word “paper” because the way to treat 3D objects is very much like folding paper in different ways. Even if a 3D-object in the end could look like a very solid rock it is built up with simple planes and triangles that is carefully bent and rotated (actually the building blocks gets smaller than that but let’s rest here for a while). The small sides (triangles) that are building up the world doesn’t even have two sides. If you are looking on the other side of a triangle you will actually see… nothing. Nothing at all! So to even create the simpliest sheet of paper you will need to create two planes and flip one and stick it to the other to make it look like in real life (have both a front and a back side).

Now, technically, Papervision have a lot to wish for when it comes to performance and no matter how amazing you might be codewise you won’t just be able to create detailed lifelike models because it will take you thousands and thousands of these triangles to fold and model the details of a reallife complex object. Here is where “texturing comes in”.

Instead of using all these resourcedemanding triangles to showcase something you can actually paint stuff right on the triangles. Say you want to create an orange. Instead of creating every single small bump on an orange you could just paint those bumps on an image and then ‘wrap’ this image around a more simple sphere still creating the illusion of an orange.

Now, I’ve started up creating a few of the models I want to use in my game. Below you will see my unit: “DEFENDER” – a smaller buggy-like car which later on will have a big ass cannon on the roof.

textures

To create such a model, you will need some kind of a 3D-program. I’ve been working with 3D Studio MAX for the last 10 years so that is choice of app. First of all you create the actual “folding” of the object. Placing all triangles where they should be, bending rotating and modelling out all planes will give you a model something like the untextured one above. The texture in the picture is what I draw on a regular image in Photoshop. Wrapping that image on the planes causes the textured model which gives an impression of a much more detailed model than it really is. Good textures are very very important to create a good looking game. Spend a lot of time on that!

If you are interested in special tutorials in modelling, texturing, UVW-mapping etc.. just give me a call and I’ll see what I can do. At the moment I just want to get my “defender” to be a part of the game. To use these kind of custom models you will have to save them into some format that PV3D recognizes like *.3ds or collada.  In this case I will save my model into the *.3ds format and use the inbuilt parser Max3DS in PV3D.

package
{
	import controllers.*;
	import flash.events.*;
	import interfaces.*;
	import org.papervision3d.events.FileLoadEvent;
	import org.papervision3d.lights.PointLight3D;
	import org.papervision3d.objects.DisplayObject3D;
	import org.papervision3d.objects.parsers.Max3DS;
	import org.papervision3d.view.BasicView;
	import transformers.*;
	import units.*;

	public class View3D extends BasicView
	{
		private var defender:AUnit
		private var defenderMesh:Max3DS
		private var light:PointLight3D

		public function View3D()
		{
			super();

			// set the camera in a nice position
			camera.y = 200
			camera.z = -1000
			camera.zoom = 90

			// place a light somewhere (just to get used to it, this one doesn't do much at the moment)
			light = new PointLight3D()
			light.x = 1000
			light.y = 5000
			light.z = -6000
			scene.addChild(light)

			startLoadMesh()

		}

		private function startLoadMesh()
		{
			// lets load our mesh
			defenderMesh = new Max3DS()
			defenderMesh.load("meshes/units/DefenderBody.3DS",null,"./meshes/units/")
			defenderMesh.addEventListener(FileLoadEvent.LOAD_COMPLETE,meshLoaded)
		}

		private function meshLoaded(e:Event)
		{
			// mesh has been loaded and is now put in as a parameter in this new object called Defender
			defender = new Defender(defenderMesh,new LocalController(),new CarTransform(7,0.85,0.3));
			scene.addChild(defender)

			// startRendering() must be called for the 3D-engine to actually start drawing each frame
			this.startRendering()

			// each time the 3Dengine redraws the screen, onFrameTick is called.
			this.addEventListener(Event.ENTER_FRAME,onFrameTick)
		}

		private function onFrameTick(e:Event)
		{
			// lets transform the unit due to the control-data it recieves.
			defender.transformUnit()
		}
	}
}

The code above actually loads my mesh and adds it on the scene in 3D. Not only that, the mesh is passed into my new class: Defender.as which is extended from AUnit so now FINALLY the chain is connected and I got a unit that do have a mesh, a control component and a transform component. I got my first primitive unit driving around on the scene!! Well.. almost, I just need to create that Defender class..

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

	public class Defender extends AUnit
	{
		public function Ball(mesh:DisplayObject3D,controller:IUnitController,transformer:ITransformer)
		{

			super(mesh,controller,transformer,0);
		}

	}
}

We need no more than that to create our unit. Remember now that we can create as many different components as we want to. Just combine them, reuse them and experiment with them to create new units.





Papervision3D – an introduction to the 3D world.

27 01 2009

Ok, lets take a small break from the game creating. I assume you already know about Flash and AS3 but if you haven’t worked with 3D programming before it would be good with some foundational theory.  Let’s start with the dimensions (no, kidding! a third??)

coordinatesystems

As you can see by the figures the 3D coordinate system differs in many aspects. First of all, there is a third axis showing the depth of the image. Imagine the screen as the 2D image a normal FlashMovie can project. Now think of the Z-axis as if you could put in your hand in the screen and push that movie further away or drag it closer to you. The movie would then move on the Z-axis. (I know this is not the whole truth but will you please pretend for a while, ok?)

Now, something is new with the other “normal” ones as well. It seems like the origo (0,0) has moved away from being in the topleft corner to the absolute middle of the screen. Ok, fair enough, so as soon as you want things to move to the left of the screen you will set the X-value negative. The last thing that might be easy to forget for you “Flashers” is that Y-axis is now pointing upwards meaning that negative values are below the 0,0,0 (origo). So whenever you want something to move upwards you increase the Y-axis.

There are many ways to use this 3D space but in my game I will look at the 3Dworld as if Y is the altitude of everything meaning that the flat arena we will create and all the units moving around will mostly be stretching out and move through the X and the Z-axis.

Today I will not dive deeper into 3D and how the models are built up rather then just present the core objects that are needed to even display something in 3D. Lets begin:

Viewport

There is no real 3D. You know that, right? I mean, we’re only simulating a 3D environment but in the end it will be projected on a 2D surface (the screen). The viewport is exactly that. It’s the 2D area where all this simulating will take place. For now, just think of it as a small rectangular MovieClip that you will just add to the displaylist just as normal. It’s what will be within this rectangle that is the cool stuff.

Camera

A camera is nothing else but your eyes in the 3D world. Think of it as an object in this 3D environment I just explained above that could move around in all axis and also rotate around. Wherever it is located, from that angle all objects in the scene will be projected.  The projected image will be visible in the Viewport explained above. (aaaah so the camera is the camera, and the viewport is like the TV showing whats catched be the camera?? … yes)

DisplayObjects3D

Now this is the objects that will be visible in the 3D-world. Damn, you know this already. It’s just like using DisplayObjects in flash. Actually, the PV3D team has worked hard for you to be as comfortable with this new technique giving you almost the same methods to work with 3D as with 2D. Want to add a DisplayObject3D in the scene?  use addChild(). Want to move it to the right?   Increase the X parameter. It’s that simple :)

Also, while we at it. DO3D is very much a container just like it’s cousins DisplayObjectContainers. This means that you can put other DO3D’s into other DO3D’s just like you would add a Sprite into a MovieClip etc. Works like a charm (because charms work, right?)

Light

Now this one is somehow new to some of you 2Dguys. Creating 3D projections is a lot about fooling the eye and mind with small tricks just to come closer to the “real thing” and what we expect to see in a 3D environment. One crucial thing that adds to the illusion of depth is light. If all sides of a green shape were litten equally, the viewer have a really hard time both getting the feeling of 3D-depth and to make out the correct form of that shape. See the image below:

lightsource1

We will work with PointLights (Pointlight3d) that as the word hints is a light placed in a point in the world. This means that you will be able to move that light just as you move objects and cameras around. With a good light you can enhance a 3D-environment to extreme standards!

Now that you are introduced to the basic components of a 3D-world, lets start the engines up and create our first bad ass scene!

First, lets create a FLA. Just create a new AS3 FLA in Flash and set the document class to ‘Main’

Now let’s create our Main.as   class and make it as simple as possible. I’ve always liked to keep the document class as clean as possible and as soon as it gets cluttery I move most of the code into a new class, cleaning Main up again.

package {

	public class Main extends Sprite
	{
		private var view:View3D

		public function Main()
		{
			view = new View3D()
			addChild(view)
		}
	}
}

View3D will be our class with all fancy 3Dstuff. To make it very (VERY) simple I will now extend a class called ‘BasicView’ and turn it into my View3D.as . Basicview’s only purpose is to take one viewport and one camera and put it all in one scene so that you are ready to go immediatly. Let’s have a look at it:

package
{

	import org.papervision3d.lights.PointLight3D;
	import org.papervision3d.view.BasicView;

	public class View3D extends BasicView
	{
		private var light:PointLight3D

		public function View3D()
		{
			super();
			createSomeObjectsOnTheScene()
			this.startRendering()
		}

		public function createSomeObjectsOnTheScene()
		{
			light = new PointLight3D()
			light.x = 1000
			light.y = 5000
			light.z = -6000
			scene.addChild(light)
			var tSphere:Sphere = new Sphere()
			scene.addChild(tSphere)
			}
		}
	}
}

Now let me take you through what just happened. First when View3D is created, I call super() meaning I call the BasicView constructor. BasicView class creates a ‘scene’ and puts a ‘camera’ on that scene. It also places the camera on z:-1000 so that it can view all objects from a fair distance (camera is by default “looking” towards 0,0,0). I then call my own function ‘createSomeObjectsOnTheScene’ where I first create a light and locates it somewhere fairly random. In the end I create the first really visible object and puts it in the displaylist using addChild. As i don’t locate it somewhere it will be placed on 0,0,0 (where camera is looking). taddaaa… but when running you will find the sphere looking kind of .. wireframed. Yes, and thats actually the correct term for that look as well.
It is as simple as if you havent specified HOW the surface will look on the sphere it will draw it in wireframe mode (as a sign of not having any material wrapped around itself. Tomorrow I’ll show you how to set some materials and then we will also head back to the game. Otherwise I will never be able to finish it!