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




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!





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?)