Overview:
As part of my research project on Multi-agent Systems and agent learning, I created a concept demonstrator to simulate a dynamic environment where agents can navigate and detect objects in their surroundings. It is a context-switchable environment, which means it can be customised for different scenarios by changing parameters defining the environment and agents. I implemented a 2D physics engine in Java language to approximate interactions and movements as they happen in the real world. A number of techniques have been implemented to facilitate agent navigation, including collision detection, flocking behaviour, and space partitioning. In this series of articles, I’ll go through these concepts and how I implemented them.
I needed a basic physics engine to incorporate the physics laws of motion into the virtual environment of my concept demonstrator in order to simulate the movements of agents in real-time. I used the Programming Game AI by Example by Mat Buckland. as the reference to write my own physics engine. I highly recommend this book, which demonstrates creating a simple 2D shooter game in C++ language. In this section, I give a brief overview of the physics engine elements I implemented. First look at Newton’s laws of motion.
The Physics Laws Theory
In order to simulate the laws of physics and movement of objects as in the real world, every entity in the simulation environment is given a supposed mass (m). Mass comes into play when forces are applied to the entity.
The velocity attribute is the measurement of the rate and direction change of an agent or moving object. It is represented using a 3D vector quantity containing the magnitude and direction of the velocity.
The direction attribute is a normalised 3D vector that points in the direction the entity is heading. It is calculated by normalising the velocity vector.
Force is a quantity 3D vector with magnitude and direction that changes the speed and direction of an entity. The motion of the entity depends on the accumulated force, which is the sum of all forces on it. Multiple forces may be applied simultaneously to a single entity. If the magnitude of the accumulated forces equals zero then the entity keeps its existing state, which will be either stationary or moving at a constant speed and in the same direction. Otherwise, the entity will accelerate in the direction of the accumulated forces applied to it.
The total acceleration (a) is proportional to the accumulated force (F ) applied to the entity and inversely proportional to m. Thus, a can be derived from Newton’s second law of motion as shown in the equation below.
a = F / m
The following equations in this section are obtained from Physics for Scientists and Engineers with Modern Physics.
Once the value of a is resolved the new velocity (v) of the entity can be calculated based on this equation:
v = a × t + v0
Where t is the time elapsed since the previous calculation and v0 is the previous velocity. The value of v is truncated to the maximum velocity that is predefined for the entity. This step is required to ensure that v does not exceed the maximum allowed velocity. The direction vector is also calculated by normalising the v vector.
After finding v, the new position (p) of the entity is determined using the equation:
p = v × t + p0
where p0 is the previous position of the entity.
At every time step, the above equations are used to calculate the forces applied to each entity and its acceleration, velocity and position in order to define its movement. Different forces might be applied to steer the entity to a specific point or direction.
The SteeringBehaviour class provides all the functions and movement tactics required for steering the entity. It applies different forces to the entity and calculates the accumulated force.
Some forces are applied by the environment and based on the laws of physics, which include gravity, friction, and inertia. For example, when the gravity force has applied the entities with a mass greater than zero will have a weight (w), which is defined as the mass of the entity times the acceleration of gravity (g):
w = m × g
The inertial force is another force that is also proportional to the mass of the entity. It is a tendency of entities to resist any change to existing motion. The higher the mass of the entity is, the greater its inertial force.
Coding the Physics Laws
Entities within the virtual environment are treated as bodies with defined mass to which Newton’s laws of motion are applied. An abstract class called an Entity is defined to represent the basic attributes of a body within the virtual world. An entity might be an obstacle, resource item, or the body of an agent (i.e. AgentBody class).
The body of a worker agent is defined by the AgentBody class, which extends the Entity class. It uses the SteeringBehaviour class, which is responsible for steering the agent based on the forces applied to it. This helps the agent to interact with its world. The simulated world is defined and created by the World-class.
The figure below shows a UML class diagram of these classes, their relationship, and some of the important methods they employ.
The Entity class holds information about the position of an entity along with its velocity, mass, scale, direction, and the accumulated force applied to it. The position attribute is a 3D vector with three axes (x, y, z), which is defined by the Vector3d object. It represents the position of an entity based on its three-dimensional Cartesian coordinates. The x and y values represent the position of entities on the x- and y-axis respectively of the 2D map. The z value is the altitude of the entity on the z-axis, which is perpendicular to the x and y planes.
The physical forces discussed previously are applied to the entity in order to steer it in the simulated environment.
These forces are applied based on the goals of the agent to perform different tasks including moving from one point to another, avoiding obstacles, and undergoing flocking behaviours. For example, the arriveAtPos() method of the SteeringBehaviour class gets a target position and calculates the forces required to help the agent reach its destination point.
At every update cycle, all relevant forces applied to each entity are added to find the accumulated force and calculate the velocity, direction, and position of the entity at the time.
In future articles, I’ll go through the code and classes that implement the physics laws to simulate movements.
Credits
- M. Buckland. Programming Game AI by Example. Wordware Publishing, Inc., Plano, Texas, USA, 2005.
- R. A. Serway and J. W. Jewett. Physics for Scientists and Engineers with Modern Physics. John Vondeling, 2000