Collision Detection Progress – 2

Am Currently still in phase 1 of implementing Collision Detection in my game engine – JustAnotherGameEngine.

Things marked have been done –

  • Design Collision Manager that will be handling all collision related stuff.
  • CD (Collision Detection) of AABB with Polygons (triangles making up objects in current scene , yes there are no simple primitives).
  • Sphere & Ellipsoid with Polygons.
  • Registration & CD of Static Objects
  • Registration & CD of Dynamic Objects (Moving objects like bullet etc)
  • Registration & CD of Height map Terrains (avoiding registration of whole terrain mesh if possible because that’s going to take allot of memory and unnecessary CPU time )
  • Update Player FPS Controller and Implement Response phase.
  • Registration of Static Hierarchal meshes loaded from 3ds Max as Static Objects.
  • Registration & CD of Models with animation loaded from 3ds Max (e.g. Walking character , etc).
  • Map Editor with collision detection support for making simple levels.
  • Or Implement the support for Loading Levels from 3ds Max and register it with Collision detection System and also make a provision to place some simple entities in 3ds Max and recognize it in engine while loading.
  • Make the whole Collision Detection System and Response phase of Player \ Character Independent of Default Co-ordinate Axes. (I will explain it later but it’s like using OABB instead of AABB. But thing am trying to do is beyond that and I can’t explain it without screenshots etc)

So i have completed the system for making Collision Detection and Response of Character Controller Independent of Default Coordinate Axes.

First let me explain what i actually mean in above line. Normally when we implement a Character Controller (Whether FPS, TPS ,etc) we choose direction of gravity mostly along one of the principal axes (-Y in my engine) and assume that it won’t change. Which in turn also fixes the Player’s UP axis (+Y in this case). This assumption greatly simplifies the process of writing the character controller. For let’s make one more assumption that length of character model is equal to its length (width = length) so its a circle on XZ plane. So that rotation of player about Y axis doesn’t matter. So we now can represent player as an AABB which will later easily converted to ellipsoid in detection phase.

Using above assumptions and using an ellipsoid for player’s collision detection, ellipsoid can easily be calculated once at loading time by determining length, width and height of Character Model. So our problem becomes the problem of collision detection of moving Ellipsoid and it’s response.

There are plenty of examples on the internet how to use ellipsoids for collision detection e.g. –

So using this method to make a character controller walking on a terrain here are the steps (its just a brief idea of how things work not a in depth description) for Collision Detection & Response –

  • Calculate Ellipsoid once from AABB at loading setup.
  • Send Ellipsoid and its current position in Collision Detection Phase. (Refer to links mentioned above on how to implement this phase)
  • Retrieve the final position & velocity of Ellipsoid and list of contact points as returned by the Detection Phase.
  • Compare the Y value of contact point if its smaller than a threshold value character / ellipsoid can slide over it else it’s velocity will be reflected to new direction as returned by response phase.
  • Also Camera system can be easily implemented.

This process is good enough for almost all games we make nowadays whether a First Person shooter, Third Person, Plat former, etc.

But i had an idea in my mind what if we can change the direction of gravity in real-time ? Also i wanted to overcome the drawbacks of above method (or eliminate all those assumptions mentioned above) –

  • Gravity can be along any arbitrary direction (e.g. (3,8,10), (5,7,1), etc instead of (0,-1,0))
  • We should be able to change direction of gravity at runtime.
  • Character can have different values for length, width or height.
  • Response phase should also be independent of principal axes and player should be able to walk over terrain at any orientation (given if gravity is normal to terrain).

So all the goals add a whole new level of complexity in Collision Detection and Response and some problems too. Here’s an idea of added complexity and extra work involved in steps discussed earlier –

  • We have to use OABB instead of AABB which will be calculated every frame. As a result ellipsoid have to be calculated every frame.
  • We can no longer use tricks to simplify calculations which assumed UP axis is always Y axis, increasing complexity and computing power required.
  • In detection phase we can no longer squeeze the world with ellipsoid to make it a sphere to make calculations easier. This is because ellipsoid is no longer aligned to principal axes.
  • In response phase we can no longer just compare Y values on contact points to determine if we can slide over object or not. We either have to
  • Increased complexity.
  • Increased compute power required for Collision Detection & Response.

Also not to mention there will be considerable changes in Camera System also –

  • We can’t use principle axis as X,Y,Z for Camera.
  • There’s no Fixed Up or +Y axis to normalize right and look vector.
  • I had to re – implement all types of cameras – First Person, Third person, Over the Shoulder, Free Look, etc in way that it’s no longer depends of principal axis instead depends on Character’s orientation.

(Note – I will try to post camera system in detail in a different blog post in future.)

So Is it worth it to do this extra effort and to make something that’s not only more complex but slower also ?

For me it was a good exercise for 3D Math and as a preparation step for some game play idea clicked to my mind .

Well I know these things can be explained better by a demo video but i don’t want post a video with boxes, wireframe, etc. So I am planning to make a tech demo later on after completing phase 1 of my collision system with some decent graphics and models. Some sort of a mini game or a game concept video. But for that am also working on a new model loading and animation system, loading scenes from 3Ds Max and bunch of other things.

So till then here are some screenshots –

1) Gravity along -Y Axes

2) Edit Mode – Changing Terrain Orientation and setting gravity direction as normal to terrain plane so its no longer -Y Axes

3) Resuming Game after Making changes to terrain and gravity.


About chetanjags

Game Developer

Posted on April 25, 2012, in Collision Detection, Game Development, JustAnotherGameEngine and tagged , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: