#003 – Collision Detection & Steering Behaviour

A change to the design.

After much thought on the current direction of the game I have decided to make two major changes to the design plan on Zombieeub53:

Removal of humans

The humans were planned to be added to have an extra layer of AI showcasing, having different goals and behaviours to the zombies and to add some risk / reward to the game play with them turning into zombies, or for the player to kill them either accidentally or intentionally.

They turned out in early testing to be an annoyance to have to navigate around and took away from the core focus of killing zombies and felt like I had included just to expand AI possibilities – so I have taken the decision to remove them, at least for now, which will enable me to really refine the AI of the zombies.

Change of environment

The original environment was to have large open spaces with sub spaces similar to a shopping mall in homage to some other works in the zombie genre – but this also had a detrimental effect in early game play as sometimes a player would be forced to wander around the map in search of zombies – breaking the flow and ensuring that any possible tension is broken.

So, on reflection I will also expand the environments to consist of large spaces, and smaller interconnected spaces that create bottlenecks, being backed into a corner and other possibilities that will seriously ramp up the tension.

Collision Detection

This week I have implemented two classes `Circle` and `Rect` which form the basis of the collision detection system in Zombieeub53. These form either a circular or axis-aligned-bounding-box (AABB) with a position and a size, and contain two functions, one overloaded to be able to detect collision:

bool intersects(const Rect& aabb);
bool intersects(const Circle& c);
bool contains(const sf::Vector2f& vec);

In this implementation we use the following principles for collision:

When when we put into code the functions look like:

bool Circle::intersects(const Rect& aabb)
{
float dx = xPos() - std::max(aabb.xPos(), std::min(xPos(), aabb.topRight().x));
float dy = yPos() - std::max(aabb.yPos(), std::min(yPos(), aabb.bottomLeft().y));
return (dx * dx + dy * dy) < (radius() * radius());
}

bool Circle::intersects(const Circle& c)
{
float dx = c.xPos() - xPos();
float dy = c.yPos() - yPos();
return sqrt(dx * dx + dy * dy) <= (radius() + c.radius());
}

Note that Circle – AABB collision looks for the closest point of the rectangle to the circle centre and then checks the distance against that point.

Steering Behaviour

Proposed by Craig W. Reynolds, steering behaviours are simple to implement and understand algorithms that produce complex behavioural patterns.

In Zombieeub53 there are two types implemented so far, Seek and Wander – See the below video for the results of the implementation.

Seek

This behaviour involves the gradual directional change of an entity towards a target, avoid unnatural sudden changes in direction.

This is calculated by taking a target position and calculating a desired velocity by subtracting the current velocity from that target position, normalising it and scaling it to our entities maximum speed, giving us a new vector that is our steering force which we can apply to the velocity and position of the object to steer it.

However as it stands that will apply the entire steering vector to the object making it just turn instantly – what we can introduce is a new variable that we will use to limit the steer by a certain amount via multiplication, which over the course of many frames will smooth out the motion of the entity.

Here is the implementation (without optimisation) of this:

float dx = steer_Target.x - mPos.x;
float dy = steer_Target.y - mPos.y;
float mag = sqrt(dx * dx + dy * dy);

desired.x = (dx / mag) * mSpeed;
desired.y = (dy / mag) * mSpeed;

steer.x = (desired.x - mVel.x);
steer.y = (desired.y - mVel.y);

steer.x = (steer.x * steer_Max) * mSpeed;
steer.y = (steer.y * steer_Max) * mSpeed;

mVel.x = std::min(mVel.x + steer.x, mSpeed);
mVel.y = std::min(mVel.y + steer.y, mSpeed);

mPos.x += mVel.x;
mPos.y += mVel.y;
}

Wander

This behaviour attempts to create naturalistic random movement.

This is simulated by projecting a line from the centre of the entity a set distance and using that point as a centre of a circle.

From here we choose an angle and calculate a point on the circle’s radius known as the displacement, which we will use as our target to use for the calculation in the seek behaviour. We can parameter the distance the circle begins, the radius of of the circle and the angle range used to create differing behaviours.

sf::Vector2f cCenter = mPos + (mVel * wander_CIRCLE_DISTANCE);

sf::Vector2f displacement;
displacement.x = cCenter.x + (wander_CIRCLE_RADIUS * cos(wander_Angle));
displacement.y = cCenter.y + (wander_CIRCLE_RADIUS * sin(wander_Angle));


float a = Utility::RandomFloat(-wander_ANGLE_CHANGE, wander_ANGLE_CHANGE);
wander_Angle += a;

steer_Target = displacement;

Next Steps

In the coming week I will be implementing a finite state machine to be able to control the zombies behaviour, and will be the jumping off point for more complex behaviours.