A simple collision approach

Collision is one of the core elements in game-development. Without collision we weren’t able to bring the most simple games to life. But there are a LOT of ways to start dealing with this particular problem since it’s not as simple as it sounds.

Possible complications:

  • We have to figure out who is colliding with each other
  • We have to specify who is allowed to interact with each other
  • We need a system which is not to complicated to expand
  • How detailed will our collision be?
  • How much performance can we sacrifice for convenience?

These are just some of the problems and questions you might face if you are dealing with this particular problem.

The big engines solved this very well with some interesting approaches, but this article is going to show, how one COULD!!! implement an own 2D collision approach.

I will try to focus on the theoretical part of the idea and how the idea works instead of coding everything into the last detail.

There will be a bit of code, some explanation, some code… aaand so on.

Ok let’s start. First of all I will implement a little helper class to deal with coordinates:

struct Vector2
{
 Vector2(int x = 0, int y = 0)
 : X(x), Y(y)
 {}

 int X;
 int Y;
};

static const Vector2 Origin;

Vector2 contains two int values, our X and our Y position. This class can be used to represent points as well as motions in a 2D space (I am going to presuppose that you guys are familiar with vectors in math). Our Origin is our base-Vector2 with a position of (0|0).

Now we need something which holds the info where our “collidable” begins/ends. We could save this information directly in our Actor (you will see later) but I prefer to outsource such kind of functionality to other components. We will implement a BaseCollisionBody from which we can inherit different CollisionBodies (like squares/circles) so we can easily change the collision body for our later Actors.

class CollisionBody
{
public:
 virtual bool IsCollidingWith(CollisionBody* target) = 0;
 virtual bool Contains(Vector2 pos)= 0;

 std::vector<Vector2>& GetBorderPositions()
 {
  return m_Points;
 }

 virtual ~CollisionBody(){}

 virtual void Move(Vector2 motion)
 {
  for (auto point : m_Points)
  {
   point.X += motion.X;
   point.Y += motion.Y;
  }
 }

private:
 std::vector<Vector2> m_Points;
};

This is our BaseBody. We got an IsCollidingWith() pure virtual function which will allow us to check if two Bodies are colliding with each other. We got a dynamic array which stores our border points so we can implement different forms with a different number of points. Futhermore we got a Contains() function which will later on implement the functionality to check if a point is contained by our body. Last but not least we got a Move() function which allows us to move our body.

Now we need at least one specified CollisionBody to cover the form of a sprite where we want to add collision to. I decided to go with a square.

class SquareCollisionBody : public CollisionBody
{
public:
 SquareCollisionBody(Vector2 position, int sideLength)
 {
 Vector2 pointA = position;

 pointA.X -= sideLength / 2;
 pointA.Y -= sideLength / 2;

 Vector2 pointB = position;

 pointB.X += sideLength / 2;
 pointB.Y -= sideLength / 2;

 Vector2 pointC = position;

 pointC.X += sideLength / 2;
 pointC.Y += sideLength / 2;

 Vector2 pointD = position;

 pointD.X -= sideLength / 2;
 pointD.Y += sideLength / 2;

 GetBorderPositions().push_back(pointA);
 GetBorderPositions().push_back(pointB);
 GetBorderPositions().push_back(pointC);
 GetBorderPositions().push_back(pointD);
 }

 bool IsCollidingWith(CollisionBody* target)
 {
  std::vector<Vector2>& targetPoints = target->GetBorderPositions();

  bool areColliding = false;

  for (unsigned int currentPoint = 0; targetPoints.size() > currentPoint; ++currentPoint)
  {
   Vector2 point = targetPoints.at(currentPoint);

   if (Contains(point)
   {
    areColliding = true;
    break;
   }
  }

  if(!areColliding)
  {
    bool condition1 = target->Contains(pointA) || target->Contains(pointB);
    bool condition2 = target->Contains(pointC) || target->Contains(pointD);

    areColliding = condition1 || condition2;
  }

  return areColliding;
 }

 bool Contains(Vector2 point)
 {
  Vector2 pointA = GetBorderPositions().at(0);
  Vector2 pointB = GetBorderPositions().at(1);
  Vector2 pointC = GetBorderPositions().at(2);
  Vector2 pointD = GetBorderPositions().at(3);

  if (point.X >= pointA.X && point.X <= pointB.X && point.Y >= pointA.Y && point.Y <= pointD.Y)
  {
   return true;
  }

  return false;
 }

private:
};

Ok, here we go, that’s our SquareBody implementation. In the constructor we are setting four points A(upper left), B(upper right), C(lower right) and D(lower left) and then we add them to our BaseBody::m_Points vector. We only need those four points to recognize if our square is colliding with something since we can simply check if one of the points is contained in our square. This leads to our simple two functions we are implementing for our BaseClass, Contains & IsCollidingWith. I don’t think I will have to explain those since they are quite simple. (And yes one could do this better, but this will suit our needs for this example)

The next class we will create is our Actor. I added some functions to the actor as placeholder which will give you a little view of how the class might work later. I won’t deal with these placeholders. Our Actor class will serve as base class for our other interactive classes like Character (Actors which have animations or can be moved around or which will be possessed by the AI later), EnviromentActors (Stones, Barriers etc…) or even projectiles.

class Actor
{
public:
 enum Type
 {
  actor,
  character,
  projectile,
  enviroment,
  background
 };

 class CollisionProperties
 {
 public:
  CollisionProperties(Actor::Type myType, CollisionBody* body, int n, ...)
  : m_CollisionBody(body)
  {
   va_list params;
   va_start(params, n);
 
   for (int currentArg = 0; currentArg < n; ++currentArg)
   {
     m_TypesToInteract.push_back(va_arg(params, Actor::Type));
   }
   va_end(params);
  }

  ~CollisionProperties()
  {
   if (m_CollisionBody != nullptr)
   {
    delete
    m_CollisionBody = nullptr;
   }
  }

  bool CanCollideWith(Type collisionType) const
  {
   return m_TypesToInteract.end() != std::find(m_TypesToInteract.begin(), m_TypesToInteract.end(), collisionType);
  }

  bool IsColliding(Actor* target) const
  {
   if (m_CollisionBody != nullptr)
   {
    const Actor::CollisionProperties& props = target->GetCollisionProps();

    if (CanCollideWith(props.m_CollisionType))
    {
     return
    }
   }
   return false;
  }

  void Move(Vector2 motion)
  {
   m_CollisionBody->Move(motion);
  }

private:
  Actor::Type m_CollisionType;
  CollisionBody* m_CollisionBody;
  std::vector<Actor::Type> m_TypesToInteract;
 };

 Actor(Actor::CollisionProperties* props, Vector2 position)
 : m_CollisionProps(props), m_Position(position)
 {}

 virtual ~Actor()
 {
  if (m_CollisionProps != nullptr)
  {
   delete m_CollisionProps;
   m_CollisionProps = nullptr;
  }
 }

 virtual bool IsColliding(Actor* actor)
 {
  return m_CollisionProps->IsColliding(actor);
 }

 virtual void Move(Vector2 motion)
 {
  m_CollisionProps->Move(motion);
  m_Position.X += motion.X;
  m_Position.Y += motion.Y;
 }

 virtual void Update()
 {
 //Some Stuff...
 }

 virtual void Draw()
 {
 //Some Stuff...
 }

 virtual const CollisionProperties& GetCollisionProps() const
 {
  return *m_CollisionProps;
 }

private:
 //...
 //Some Stuff...
 //...

 CollisionProperties* m_CollisionProps;
 Vector2              m_Position;
};

So this is our actor. Our actor contains a subclass CollisionProperties which will handle the collision for the actor. The properties class contains an Actor::Type member which specifies, which kind of actor we got (environment etc. see the enum) as well as the CollisionBody and a vector which contains the collision types, our actor can interact with. Our Actor is basically calling the functions we already implemented in our CollisionBody with the little difference that we can specify in our m_TypesToInteract which kind of collisions shall be ignored by our later implemented inherited subactors.

Let’s take a character for instance:

class Character : public Actor
{
 Character(const std::string& name, CollisionBody* body)
 : Actor(new Actor::CollisionProperties(Actor::character, body, 3, Actor::character, Actor::enviroment, Actor::projectile), Origin), m_CharacterName(name)
 {}

 std::string m_CharacterName; 
};

This class get’s all its features like update, draw and move from our Actor class, but it specifies which kind of actor(Actor::character) we got and which classes can collide with our character (other characters, environment actors and projectiles). This class got close to all functionalities a character needs (motion, collision, updates etc) but it remains pretty slim by now.

Okay that was a whole lot of stuff. Now we got close to all components we need for our collision together. There are only a few little things missing:

A little event class and an inherited collision event.

class Event
{
public:
 enum Type
 {
 collision
 //...
 //Some Others...
 //
 };

Event(Type type)
 : m_EventType(type)
 {}

Type GetEventType()
 {
 return m_EventType;
 }

private:
 Type m_EventType;
};

class CollisionEvent : public Event
{
public:
 CollisionEvent(Actor* a, Actor* b)
 : Event(Event::collision), m_ParticipantA(a), m_ParticipantB(b)
 {}

Actor* GetPA()
 {
 return m_ParticipantA;
 }

Actor* GetPB()
 {
 return m_ParticipantB;
 }

private:
 Actor* m_ParticipantA;
 Actor* m_ParticipantB;
};

Since you are pretty smart guys, I am pretty sure I won’t have to explain this classes to you because they are actually pretty simple so I will go on with a simple usage example of the collision eco system we just created. I will leave or actor/character creation and focus on the collection of collision events per frame.

class Engine
{
public:
 void Play()
 {
 while (m_Running)
 {
 Collision();
 Update();
 Draw();
 Present();
 }
 }
private:
 void Collision()
 {
 for (unsigned int currentActorA = 0; m_ActorPipeline.size() > currentActorA; ++currentActorA)
 {
 if (m_ActorPipeline.size() < 2)
 {
 return;
 }

for (unsigned int currentActorB = currentActorA; m_ActorPipeline.size() > currentActorB; ++currentActorB)
 {
 Actor* a = m_ActorPipeline.at(currentActorA);
 Actor* b = m_ActorPipeline.at(currentActorB);

if (a != b && a->IsColliding(b))
 {
 m_EventPipeline.push_back(new CollisionEvent(a, b));
 }
 }
 }
 }

void Update()
 {
 std::for_each(m_ActorPipeline.begin(), m_ActorPipeline.end(), [](Actor* actor)->void{actor->Update(); });
 }

void Draw()
 {
 std::for_each(m_ActorPipeline.begin(), m_ActorPipeline.end(), [](Actor* actor)->void{actor->Draw(); });
 }

void Present()
 {
 //Some Stuff...
 }

 //...
 //Some Stuff...
 //...

 std::vector<Actor*> m_ActorPipeline;
 std::vector<Event*> m_EventPipeline;

bool m_Running;
};

Okay, what do we got here. An Update() function, a draw function and our present function. Pretty basic if you ask me so I am going to leave them out. Collision().. well, that’s the interesting part. In this function we are handling our collision and there we will create our CollisionEvents and add them to our EventPipeline.

Basically we are iterating through out actor pipeline and we check our actors for collisions. If we detect a collision (remember, we specify which kind of actor may collide with which other types.), we will save a CollisionEvent with the two participating actors to our EventPipeline. What you will do with them from there on is no longer my concern since that is not part of this tutorial/article 😉

Puh, that was a whole lot of info I pushed out there. I hope some of you can get some helpful information out of this article. But hey, I know there is a lot of optimization potential in this code but optimal performance wasn’t the goal I wanted to archive with that.

The thing I like most about this approach is the little effort you will have to put into changing this one into a concurrent environment. Basically you have two ways of doing this:

First (and less effective way): You could create a task for every collision check and hand this task over to a thread pool to collect the results in future objects and process them later.

Second: You could add a pipeline for every type of collision object that you have a pipeline for environment actors, one for projectile actors and for each pipeline an own EventPipeline and so on. This way you could process one pipelines per thread and merge the events together in the end. (That’s how I would handle this, but I would handle the collision threads in a pool anyway.)

I hope you liked today’s post, that’s all for today. Have a nice day/evening whatever 😉

Advertisements

(C++) An interesting Container design

Okay, this will be one of my first programing posts. I won’t feature a lot of code since I don’t want this to be a how to tutorial. Basically I will present you an idea and give you some thoughts about it (and I will show a little test).

Some time ago I designed a container class (well I named it mango::vector) since the std::vector made a trade I was not willing to accept so I designed a little container class to suit my needs.

Well, here is the situation. A vector is a dynamic array. That means you have a pointer to an array of elements. if the array capacity is reached, the vector allocates a new array which is larger than the original one and copies/moves all the content to the new array. And there is the problem. A vector is fast as long as you won’t bust it’s initial (or reserved capacity) since allocating new memory and moving all the content takes “a lot” of time.

But that’s only on of a few problems. Another flaw comes with erasing or inserting values from/to the vector. If you erase a vector every element after the erased element have to be moved/copied one slot towards the erased elements index which also takes “a lot” of time. (inserting happens to be the other way around –> moving and index away from the insert-index)

Ok, where does that information lead us to you may ask? Well, that’s a damn good question. Some of you will say now “why don’t you just us a std::list?”. Well that’s also a damn good question.

For those who don’t know: If a vector in your memory looks like this:

vector_memory

Then a list can be imagined like this:

list_memory

Ok now you see a memory model, but why?

It’s easy if you want to access a vector element you just shift a pointer to the begin of the array index * elementsize “to the left”. One operation. If you want to add an element at the end (and we suggest we have enough space in our vector so we don’t have to reallocate memory) we just add it. Also one operation.

Let’s look at the list. If we want to add an element at the end we have to allocate memory for a new element and place the element there. Allocation isn’t the fastest thing on earth, that takes some time. If we want to access for example the 4th element we have to drag ourself along 4 pointers. That won’t take to long but it’s still slower than the vector. Inserting into a list is really interesting. If we want to insert an element in our list, we allocate a new one and add it into our list. That’s a lot faster than inserting into a vector as you may remember (no elements to move).

So basically we can break our conclusion into two points. Inserting, deleting or appending elements from/into a list works at a constant speed.

Inserting, deleting elements/from/into a vector is slow, appending elements to the end on the other hand is really fast.

Each of the above mentioned containers do have their ups and downs, so why no container wich is good at both? And that’s exactly the conclusion I came to when I started to think about that topic. This wouldn’t be an interesting post if I hadn’t a wonderful stupid idea to solve that particular problem (kind of)

semivector

That’s the idea I came up with. Simple said, I made a “vector” with 2 arrays, one with elements, one with pointers to the elements.

What is the advantage of that? Well that’s easy. If you want to access an element you access it over the array of element pointers. That’s not significant slower than accessing them the regular way since you just have to access the array of pointers.

Here comes the interesting part. If you want to delete an element for example (let’s take the second one) you only have to shift the pointer to the second element to the end of the pointer array.

semivector_deleted

Now if you want to access the “second” element in your vector you’re actually accessing the third element in your array, but the second pointer (you won’t spot the difference).

(that’s how the “vector” would look like after an insert)

semivector_inserted

So what is the benefit of this? Also easy: If you make an insert/erase you won’t have to shift the actual elements, instead of you are shifting the pointers to the elements. If you have a custom::vector you will see no improvement in performance compared to a std::vector (the performance will even get worse) since shifting int variable is as fast as shifting pointer. On the other hand if you got a custom::vector your performance will increase significant since shifting pointers is a lot faster than shifting std::strings.

Most likely you will ask now: If this is the holy grail of a container, why isn’t vector implemented that way?

Legit question. The answer is simple. This container has other flaws. Yes it is fast. But you pay the speed benefit by using more memory. On each element you add there comes a pointer to that element. Lets consider we have a 32 Bit system: If you have 200 elements with size 8 bytes we got 1600 bytes (+ ca 16 bytes for the actual std::vector object) for our std::vector. If we have 200 elements which 8 bytes in a custom::vector we will have 2400 Bytes of memory in use (if we consider a 32 bit pointer is 4 bytes). That’s a third more. I still like to use my custom container since in my opinion in the most cases the size difference won’t have to much of an impact since memory isn’t always the limiting factor. The standard container a build to be flexible and with things like embedded systems in mind. It’s not always the raw execution performance that matters.

Well now I threw around with a load of claims and proofed nothing by now, funny aye? But this wouldn’t be fun if I hadn’t tested this at least a bit. (Just for those of you who are curious, no I won’t provide the code for my vector since I did some ugly thing down there which I want nobody to know about, sorry. But you are clever guys and I am pretty sure you will be able to implement this one yourself)

This test only shows the insert capabilities of this container, erasing won’t perform much different. The test is not perfect but it will give you a relation of numbers which will at least give you a feeling for the speed improvement.

here is the test code:

vector_test_code

and here comes the result:

vector_test_result

These results are in seconds, maybe I should have written that. The custom::vector (in my case mango::vector) inserts 100x faster (if you believe this test). That’s a number isn’t it? Well, reality seems a bit difference. The number will change, but in both directions. The bigger the elements in your vector are, the faster your custom::vector will get in relation to the std::vector. The smaller the elements are… well you got it I think.

The test was built in release with activated optimizations.

If you actually made an implementation for this custom container which is clean enough to share it with the world feel free to link it in a comment.