Few real world objects retain their shape and structure when subjected to real world forces. Simulating these changes in shape will inevitably lead to more realistic games and more interesting gameplay mechanics. This field of physics simulation isrefered to as soft body dynamics. This is the field of physics simulation that focuses on objects that change in shape or size (are deformable). In normal rigid body dynamics this does not occur, and any two points on the body will always be the same distance from one another. This is not true in soft body dynamics, though bodies are expected to keep their shape to some degree.

Deformable objects are defined by their undeformed shape (the equilibrium shape) and by a collection of parameters it owns that define how it deforms when forces are applied to it. If we think of a shape as being made up of a collection of points in space, we can devise a set of rules to act on each of these smaller points that will provide the deformation of the whole shape. There are various ways to generate this set of rules; I will describe two techniques in this article.

First we will look at the finite element method (FEM). This method was first described in 1943 to describe the dispersion of vibrations through objects, it was then expanded to allow more general applications in engineering and stress testing in 1956. Due to a lack of computing power FEM was limited to the expensive mainframe computers of the aeronautic, civil engineering and defence industries. Because of the increase in computing power and optimisations to the technique, FEM is now at a point where it is cheap enough to begin to put them into real-time applications [4]. But how do these methods work? FEM will divide an object into a complex system of points, creating a grid called a mesh. Each node in this mesh contains the structural properties of the shape which define how the object will react when forces are applied [1]. These properties can include:

- Mass, volume
- Strain energy, stress strain
- Force, displacement, velocity, acceleration
- Any problem specific user defined attribute

When creating the mesh, the nodes can be assigned in different ways to help with performance and define how an object will be deformed. Areas with lots of nodes will be subject to more complex deformations than areas with few. How these nodes are generated is totally dependent on the material being simulated, cloth for instance would require an even spreading of nodes across the whole object to ensure that the deformations look as natural as possible. When this technique is being used to test the structural integrity of an object for engineering purposes, node density is usually high around places that are prone to fracture, fillets, areas of complex details and high stress areas. Once we have a complete set of nodes and edges between adjacent nodes we perform the mathematics on each node that will translate it. Because each node is connected to the 3D representation of the object beneath it, pulling and pushing the nodes will pull and push the object with it, creating a visual representation of the deformation that can be seen by a user [2].

In an attempt to briefly describe the mathematics that is performed on each node in the grid we can look at a simple problem that can be solved by FEM, a three-member truss in two dimensions [5]. Each corner of the triangle formed can be treated as a node. To find the displacement of each node we must find how it is being pushed by each node it is connected to. This gives us a bar with a node at either end, each of which have displacements in the X and Y dimensions, giving four different displacements over all. Each of these displacements will then have a corresponding force, the relationship between force and displacement is:

Force = Displacement * “Stiffness”

For one bar, this gives the following equations:

F_{1} = k_{11}u_{1} + k_{12}u_{2} + k_{13}u_{3} + k_{14}u_{4}

F_{2} = k_{21}u_{2} + k_{22}u_{2} + k_{23}u_{3} + k_{24}u_{4}

F_{3} = k_{31}u_{1} + k_{32}u_{2} + k_{33}u_{3} + k_{34}u_{4}

F_{4} = k_{41}u_{1} + k_{42}u_{2} + k_{43}u_{3} + k_{44}u_{4}

Or the matrix:

This matrix is known as the “stiffness matrix”, it defines the properties of the bar between the two nodes and how it will act when subjected to outside forces. The stiffness matrices of the whole mesh made by the nodes is calculated in the same way for every connection and depends upon the properties given to the nodes. The stiffness matrix for a bar at an angle “theta” to the x-axis can be found using:

Where *A* = Area of the rod (volume in three dimensions)

*E* = Young’s Modulus of the rod

*L* = Length of the rod

*c* = cos ”theta”

*s* = sin “theta”

Now we can derive a set of equations that describe the forces acting on a node when it is at rest. The nodal forces must be equal and opposite to any outside forces. How many nodal forces act on each node depend on the amount of other nodes the node is connected to. For equlilibrium at any node we have one externally applied force in each direction, we know that subtracting each nodal force acting in the same direction (given by the stiffness matrix) will give zero. Therefore each external force (number of dimensions * number of nodes) at equillibrium is the equal to the sum of the nodal forces acting upon it.

Where *R* = Total external force

*n* = Number of dimensions * number of nodes

*x* = Coefficient of displacement direction

When a load is applied we need to know how the external forces change. This is where the constraints of the system are key, if a node is fixed then it can be disregarded, we also need to decide if a load can act on an external force. The more external forces effected by loads, the more deformable the object. A resultant force will be zero if it is not effected by a load or positive or negative depending upon the direction of the load. We can then solve the above matrix to find the total displacement in every direction.

Another common method for soft-body physics is the mass-spring system [3]. These systems are widely regarded to be the simplest and most intuitive of all the various soft-body physics systems. This method models an object as a collection of point masses connected together by a grid of massless springs. To find the shape of an object at any given time we only need the position and velocity of every one of these masses, then the forces acting on each mass is computed using the force of all the spring connections with its neighbours, as well as other external forces such as gravity. The motion of each particle can then be simply expressed using Newton’s second law. These methods were first used for the modelling of faces in 1987; soon, the methods were expanded to be used in the modelling of skin, fat and muscle. They were also used to simulate the movement of snakes worms and fish, creatures that bend as they move. In these systems, the rest-length of the springs varied over time to simulate muscle actuation.

Springs are commonly modeled as being linearly elastic; the force acting on mass *I, *created by the connection between particle *I *and particle *j *is given by:

Where Xij = The difference between the two masses positions ( - )

Ks = The spring’s stiffness

Lij= The springs rest length

However, physical bodies are not perfectly elastic and dissipate energy during deformation. To account for this, viscoelastic springs are used to damp out relative motion. Thus, in addition to the equation above, each spring exerts a viscous force. This is given by:

Where Kd = The spring’s damping constant

These equations are derived from Hooke’s law, a useful approximation of how real-life springs act when compressed or expanded by external forces. Always attempting to return to its original length, with a greater force the further from this restitution length the spring becomes.

Mass-spring systems are known to be much less accurate than finite element methods [1], mass-spring models only seek to approximate deformations whereas TEM has the advantage of being built from the ground up on elasticity theory. Mass-spring systems are crucially not convergent; as the mesh is refined the simulation does not approach the correct solution. Spring constant are commonly chosen arbitrarily, and it is impossible to draw any conclusions about what material is supposed to be being modelled. For games this may not be an issue as the lack of accuracy may be perfectly acceptable and indeed many convincing simulations have been produced using this method. However, because the behaviour of a simulation is totally dependent upon the mesh of masses, the lack of generalisation may make people wary upon putting much effort into getting this system working. So we know that FEM creates much more realistic results, but this of course comes at the expense of computing power. Many small meshes can be easily simulated in real-time and this may be more than is needed for most situations, however, with bigger meshes comes better results but by the time an acceptable result is reached the cost may have become prohibitively high.

As for their current use in real-time applications, most video game developers shy away from implementing too many deformable objects because of their high cost. Deformable objects are mostly used when they play a central role in the mechanics of a game and it is worth the developer getting them right. One dimensional mass-spring systems have seen a lot of use in real-time cloth simulation. The relative simplicity of cloth compare to objects with more dimensions means that models have been created that are convergent and create very realistic looking and behaving cloth [1]. Finite element methods have been used to simulate stresses and small deformations on rigid objects just before they break. This method means that because the objects usually break very quickly, the results do not have to be incredibly convincing and they do not mean a sustained load on computation time. Using FEM in this way also means that the shapes never have to return to their initial rest shape so this does not have to be accounted for in the model [6].

Implementing both of these methods into a rigid-body simulator requires the implementation of a way of representing objects separate to the graphical representation of the objects themselves. For FEM this would be the placing of nodes and the creation of the grid from them or placing the network of masses-and springs. The placing of nodes and masses should stick to the network of vertices that already make up the representation of the shape, the connections between these points could then be described in ways suitable for the object which is being modelled. For FEM these connections should be contained to the surface of the object, however for mass-spring networks, springs could go through an object to create a more rigid shape. Once these networks are set up, it must be possible to have forces act on separate parts of it and allow the mathematics to handle the deformation of the shape. Once the points are moving the vertices of the shape beneath them must then be moved with them to give the deformation of the shape.

References:

[1]Nealen, A., Müller, M., Keiser, R., Boxerman, E. & Carlson, M. (2005) ‘Physically Based Deformable Models in Computer Graphics’ .CiteSeerX: 10.1.1.124.4664.

[2] Muller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. (2002) ‘Stable real-time deformations’. *In SCA02: Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation*, ACM, NewYork, NY, USA, 49–54.

[3] Liu, T., Bargteil, A., O’Brien, J., Kavan, L. (2013) ‘Fast Simulation of Mass-Spring Systems.’ *ACMTrans. Graph.* 3(6), 7 pages.

[4] Widas, P (1997) *Introduction to Finite Element Analysis *Available at: http://www.sv.vt.edu/classes/MSE2094_NoteBook/97ClassProj/num/widas/history.html (Accessed: 19 May 2014)

[5] Widas, P. (1997) *Theory of Finite Element Analysis *Available at: http://www.sv.vt.edu/classes/MSE2094_NoteBook/97ClassProj/num/widas/history.html (Accessed: 19 May 2014)

[6] Baudet, V., Beuve, M., Jaillet, F., Shariat, B. and Zara, F. (2007) ‘Integrating Tensile Parameters in 3D Mass-Spring System’ *LIRIS *

In this paper we seek to investigate the effects of different breeding strategies on the performance of an evolutionary algorithm. The strategies we explore can be split into two different categories, those that effect when an agent reproduces and those that decide which two agents are selected to reproduce. The different strategies that define when an agent reproduces are well explored and defined in evolutionary biology whereas the strategies we use for partner selection are less based on natural systems. This means that our areas of investigation will be see what partner selection strategy is most beneficial for each “when” strategy. To measure the performance of the system, each agent has a “fitness” which increases whenever they collect a piece of food, of which a fixed number are placed in the environment. We define the performance of a system as the average fitness of all agents in

the world.

Read the whole report here: Third Report

I made a game! Woo, go me, happy times.

Delta-V is a turn-based space dog-fighting game, it was made for Venus Patrol’s “Space Cowboy Jam”. This was my first ever game jam

The game was inspired by the astronautical concept of “delta-v”, which describes the change in velocity a body must undergo a change in trajectory.

The further I got through the project, the more I noticed the similarities to Brendon Chung’s “Flotilla” which you should definitely go play.

Players take-turns to enter instructions for their crafts to perform. Ships can either translate or rotate. Both of these actions deplete the same pool of fuel. While moving, ships will fire missiles that seek out the other player. These missiles do the least damage on the sides, more on the front and the most on the rear of ship.

Controls:

WASD: Translate Controls

Arrow Keys: Rotate Controls

Space Bar: End Turn

PLAY IT HERE: http://shinyshez.itch.io/delta-v

Here’s something nice and computer sciency for a change.

Dijkstra’s Algorithm solves the shortest path problem for a graph with non-negative edge path costs. It’s a very helpful algorithm for routing and other graph traversal problems. The graph is represented by edges with a cost for each.

(node node cost) (defparameter *nodes* '((a b 2) (a c 6) (b c 5) (b d 1) (c d 7) (d e 12) (e f 4) (d f 5) (f g 8) (f z 8) (y u 7)))

And called by:

(return_cheapest_path (start_node end_node graph))

Which will return the cost of the cheapest path from the start node to the end node.

Here’s the description of how the algorithm works from wikipedia. Further comments are in the code.

Let the node at which we are starting be called the **initial node**. Let the **distance of node Y** be the distance from the

- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
- Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the
*unvisited set*consisting of all the nodes. - For the current node, consider all of its unvisited neighbors and calculate their
*tentative*distances. Compare the newly calculated*tentative*distance to the current assigned value and assign the smaller one. For example, if the current node*A*is marked with a distance of 6, and the edge connecting it with a neighbor*B*has length 2, then the distance to*B*(through*A*) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value. - When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the
*unvisited set*. A visited node will never be checked again. - If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the
*unvisited set*is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished. - Select the unvisited node that is marked with the smallest tentative distance, and set it as the new “current node” then go back to step 3.

;;Returns all nodes. (defun get_initial_uncon_nodes_helper (flat_list accum) (cond ((null flat_list) accum) ((atom flat_list) accum) (t (get_initial_uncon_nodes_helper (cdddr flat_list) (cons (first flat_list) (cons (cadr flat_list) accum)))) )) (defun get_initial_uncon_nodes (start_node nodes) (let ((flatten_nodes (flat nodes nil))) (remove start_node (remove_dupes (get_initial_uncon_nodes_helper flatten_nodes nil) nil)) )) (defun get_all_connected (curr nodes repeat result) (cond ((> repeat 100) (remove_dupes(flat(remove_dupes result nil)nil)nil)) (t (get_all_connected (first (get_neighbours curr nodes nil)) nodes (1+ repeat) (cons (get_neighbours curr nodes nil) result))) )) ;;Returns cost of vertex between given nodes. (defun get_cost (node1 node2 nodes) (cond ((null nodes) nil) (t (let ((curr_tuple (first nodes))) (cond ((and (eq (first curr_tuple) node1) (eq (cadr curr_tuple) node2)) (caddr curr_tuple)) ((and (eq (first curr_tuple) node2) (eq (cadr curr_tuple) node1)) (caddr curr_tuple)) (t (get_cost node1 node2 (rest nodes))) ))))) ;;Returns all connected nodes. (defun get_neighbours (curr_node nodes accum) (cond ((null nodes) accum) (t (let ((curr_tuple (first nodes))) (cond ((eq (first curr_tuple) curr_node) (get_neighbours curr_node (rest nodes) (cons (cadr curr_tuple) accum))) ((eq (cadr curr_tuple) curr_node) (get_neighbours curr_node (rest nodes) (cons (first curr_tuple) accum))) (t (get_neighbours curr_node (rest nodes) accum)) ))))) ;;Returns neighbours not passed in connected_nodes (defun get_neighbours_unconnected(curr_node nodes connected_nodes) (let ((neighbours (get_neighbours curr_node nodes nil))) (remove_many_items connected_nodes neighbours) )) ;;Returns the cheapest neighbour not in the visited_nodes list. (defun get_cheapest_neighbour_helper(start_node nodes neighbours cheapest_node) (cond ((null neighbours) cheapest_node) (t (let ((curr_node (first neighbours)) (curr_cost (get_cost start_node (first neighbours) nodes))) (if (< curr_cost (get_cost start_node cheapest_node nodes)) (get_cheapest_neighbour_helper start_node nodes (rest neighbours) curr_node) (get_cheapest_neighbour_helper start_node nodes (rest neighbours) cheapest_node) ))))) (defun get_cheapest_neighbour(curr_node nodes visited_nodes) (let ((neighbours (remove_many_items visited_nodes (get_neighbours curr_node nodes nil)))) (get_cheapest_neighbour_helper curr_node nodes neighbours (first neighbours)) )) (defun check_neighbours_and_update_helper (curr_node neighbours nodes connected_nodes unconnected_nodes desired_tree tentative_cost predecessors) (cond ((null neighbours) (dijkstra nodes connected_nodes unconnected_nodes desired_tree tentative_cost predecessors)) (t (let ((new_cost (+( rest (assoc curr_node tentative_cost)) (get_cost curr_node (first neighbours) nodes))) (old_cost (rest (assoc (first neighbours) tentative_cost)))) (cond ((null old_cost) (check_neighbours_and_update_helper curr_node (rest neighbours) nodes connected_nodes unconnected_nodes desired_tree (acons (first neighbours) new_cost tentative_cost) (acons (first neighbours) curr_node predecessors))) ((< new_cost old_cost) (check_neighbours_and_update_helper curr_node (rest neighbours) nodes connected_nodes unconnected_nodes desired_tree (acons (first neighbours) new_cost tentative_cost) (acons (first neighbours) curr_node predecessors))) (t (check_neighbours_and_update_helper curr_node (rest neighbours) nodes connected_nodes unconnected_nodes desired_tree tentative_cost predecessors)) ))))) (defun check_neighbours_and_update (curr_node nodes connected_nodes unconnected_nodes desired_tree tentative_cost predecessors) (let ((neighbour_list (get_neighbours_unconnected curr_node nodes connected_nodes))) (check_neighbours_and_update_helper curr_node neighbour_list nodes connected_nodes unconnected_nodes desired_tree tentative_cost predecessors) )) (defun get_next_node_helper(unconnected_nodes tentative_cost chosen_node) (cond ((null unconnected_nodes) chosen_node) (t (let ((curr_node (first unconnected_nodes))) (if (null (first (assoc curr_node tentative_cost))) (get_next_node_helper (rest unconnected_nodes) tentative_cost chosen_node) (let ((curr_cost (rest (assoc curr_node tentative_cost)))) (cond ((null chosen_node) (get_next_node_helper (rest unconnected_nodes) tentative_cost curr_node)) ((null curr_cost) (get_next_node_helper (rest unconnected_nodes) tentative_cost chosen_node)) ((<= curr_cost (rest (assoc chosen_node tentative_cost))) (get_next_node_helper (rest unconnected_nodes) tentative_cost curr_node)) (t (get_next_node_helper (rest unconnected_nodes) tentative_cost chosen_node)) ))))))) (defun get_next_node (unconnected_nodes tentative_cost) (get_next_node_helper unconnected_nodes tentative_cost nil)) (defun dijkstra (nodes connected_nodes unconnected_nodes desired_tree tentative_cost predecessors) (cond ((null unconnected_nodes) (cons desired_tree tentative_cost)) (t (let ((cheapest_neighbour (get_next_node unconnected_nodes tentative_cost))) (let (( new_desired_tree (cons (cons cheapest_neighbour (rest (assoc cheapest_neighbour predecessors))) desired_tree))) (check_neighbours_and_update cheapest_neighbour nodes (cons cheapest_neighbour connected_nodes) (remove cheapest_neighbour unconnected_nodes) new_desired_tree tentative_cost predecessors) ))))) (defun cheapest_paths_no_formatting (start_node nodes) (let ((connected_nodes (cons start_node nil)) (unconnected_nodes (get_all_connected start_node nodes 0 nil)) (desired_tree nil) (tentative_cost (acons start_node 0 nil)) (predecessors (acons start_node nil nil))) (check_neighbours_and_update start_node nodes connected_nodes unconnected_nodes desired_tree tentative_cost predecessors) )) (defun get_tentative_cost (node1 node2 tentative_cost) (let ((cost1 (rest (assoc node1 tentative_cost))) (cost2 (rest (assoc node2 tentative_cost)))) (if (> cost1 cost2) cost1 cost2) )) ;;Formatting Final Answer (defun return_highers_helper (list element result) (cond ((null list) result) ((equalp (first element) (first (first list))) (cond ((< (rest element) (rest(car list))) (return_highers_helper (cdr list) element (cons (car list) result))) (t (return_highers_helper (cdr list) element result)) )) (t (return_highers_helper (cdr list) element result)) )) (defun strip_highers (list fulllist result) (cond ((null list) result) ((strip_highers (cdr list) fulllist (return_highers_helper fulllist (first list) result))) )) (defun remove_listp_items_helper (item list result) (cond ((null list) result) ((if (and (equalp (car item) (car (car list))) (eq (rest item) (rest (first list)))) (remove_listp_items_helper item (cdr list) result))) (t (remove_listp_items_helper item (cdr list) (cons (car list) result))) ) ) (defun remove_listp_items (items_to_remove list_to_remove_from) (cond ((null items_to_remove) list_to_remove_from) (t (remove_listp_items (cdr items_to_remove) (remove_listp_items_helper (car items_to_remove) list_to_remove_from nil))) )) (defun return_all_cheapest_paths (start_node nodes) (let ((result_list (rest (cheapest_paths_no_formatting start_node nodes)))) (remove_listp_items (strip_highers result_list result_list nil) result_list) )) (defun return_cheapest_path_helper (result_list end_node) (cond ((null result_list) nil) ((equalp end_node (car (car result_list))) (cdr (car result_list))) (t (return_cheapest_path_helper (cdr result_list) end_node)) )) (defun return_cheapest_path (start_node end_node nodes) (let ((result_list (return_all_cheapest_paths start_node nodes))) (return_cheapest_path_helper result_list end_node) )) ;;Helper Functions (defun get_from_index (index list current_index) (cond ((eq index current_index) (first list)) ((minusp index) nil) ((eq (length list) current_index) nil) (t (get_from_index index (rest list) (+ 1 current_index))) )) (defun contains (element list) (cond ((null list) nil) ((equal element (first list)) t) (t (contains element (rest list))) )) (defun flat(x y) (cond ((null x) y) ((atom x) (cons x y)) (t (flat (first x) (flat (rest x) y))) )) (defun flatten (li) (cond ((null li) nil) ((listp li) `(,li) ) (t (mapcan #'flatten li)))) (defun remove_dupes (x y) (cond ((null x) y) (t (if (contains (first x) y) (remove_dupes (rest x) y) (remove_dupes (rest x) (cons (first x) y)))) )) (defun remove_many_items (items_to_remove list_of_elements) (cond ((null items_to_remove) list_of_elements) (t (remove_many_items (rest items_to_remove) (remove (first items_to_remove) list_of_elements))) ))

The first type of erosion I will be using in my model is the simulation of matter becoming loose and falling under gravity, this is known as thermal erosion.

The program loops through every point on the heightmap checking the difference between the height of it and of its neighbors. When this value is above a value defined by the user (the talus value) height is moved from the higher square to the lower to make them teven. If multiple lower squares exist, height is distributed according to:

Where ‘hi’ is the current point, ‘dmax’ is the largest height difference between all neighbors, ‘di’ is the current neighbor, ‘dtotal’ is the sum of all the differences in height between this point and its neighbors. ‘c’ is a value that stops strange oscillation artifacts effecting the program and ‘T’ is the talus value.

Neighbours are defined as either being all the points around any point (left, Moore Neighborhoods) or the points in each cardinal direction from any point (right, Von Neuman Neighborhoods). Using Von Neuman is twice as fast, and produces just as convincing erosion effects.

* *

The top terrain is eroded into the lower using this method.

Two years ago, during the height of the British General Election, I helped with phone canvassing for the Labour party campaign. Phone canvassing, for those who don’t know, is when political parties engage with likely voters over the phone. Asking whom they’re voting for, whether they usually vote etc. During my time canvassing, I got to use Labours “virtual phone bank” and it struck me how much like a videogame the interface was. Phone Canvassing goes off a script, with the caller asking questions and looking for the voters response to tell him what to say next according to the script. Labours interface only has the current question that you’re asking and various buttons (green for more likely, red for likely but undesirable and grey for unlikely) to enter the response. The conversation can quickly branch into what would be a deep conversation down a script without the caller having to search for anything.

Fast forward to now, the 2012 US Presidential elections and I got to take a look at the system that the Barack Obama campaign uses for their telephone canvassing (I didn’t make any calls, too expensive) and it’s shocking how different and less intuitive it is. Callers literally just have the script of all possible conversations infront of them and must do their best to pick the right path through it.

So this got me thinking about the interactivity of Labours system, and how just one small step towards videogame made the system so much more intuitive and easy to use. And while I have no doubt that its designers were not at all thinking about making it fun when they designed it, aiming instead for ease of use and not letting the callers die of boredom it goes a long way to show how interactivity can make an activity so much more engaging.

Onto question two!

**What is Gameplay?**

Gameplay is the interactions between the player, the internal processes and the display of a game.

Gameplay is (but is not always recognized as) the single most defining aspect of a game. Like the words of an author or the brush strokes of a painter, it holds any and all thematic meaning a game has, and transcends visual art or story. Unfortunately, the as-yet undiscovered and seemingly subjective qualities of “good gameplay”, coupled with the relative immediacy of a games visuals or sound mean that most of the game play we receive lacks any deeper goal than providing a fun experience.