Creating Glitch Graphics

I’m sure most programmers have accidentally created graphics glitches in the past – corrupt image files, incorrect texture maps, that sort of thing, and I’ve certainly encountered them many times as a games player… y’know, the sorts of things that make Lara Croft look like this:

However, I’ve only just become familiar with intentional glitching of graphics data for artistic effect – so called glitch art.

You can see some great examples in the glitch art pool on Flikr, which no doubt the artists have spent some considerable time compositing and refining, but I thought I’d try out a much simply technique using nothing more than a hex editor (such as XVI32)

So, start with an image file (JPG/PNG/whatever – doesn’t really matter), load it up in a hex editor, and then search and replace some bytes with another set of random bytes. For example, try replacing the byte 5D with the byte D5:

 

Or, if you’re feeling a little more confident, try replacing the byte pair 97 5D with a text string, “NIGD”.

 

Or, try adding non-ASCII characters and replacing string of different lengths too, or add messages in to the file:

 

After each replacement, save as a new file and try to load it up in an image viewer. If you’re lucky, you might have generated an interesting glitch effect. If you’re unlucky, you might just have a corrupt image file, in which case revert back to the previous save and try something else.

It’s also worth noting that since PNG/BMP/JPG store byte data in different formats, you’ll get different effects from each, so try experimenting.

With a handful of random replacements, you can convert an image from:

to the altogether more interesting…:

The Norwich Game Expo, or “breaking one’s New Year’s resolutions”

Every year I set New Year’s resolutions. Many years I don’t succeed in keeping them, but I still believe that there’s a benefit in having thought about what you want to change in your life, and at least making a start towards doing something about it.

For 2013, I set myself a resolution that, before the end of the year, I would finish and publish one of the many ideas I’ve had for a computer game (which I’ve had floating around my head since about the age of 9). Even though it’s only April, I don’t think I’m going to make it, but I’m not concerned  because other good things have happened as a result.

Having set the resolution, I decided to become more active in my local indie game development group – the Norfolk Indie Game Developers. As a result, I’ve met a bunch of really nice and talented people, and I’ve enjoyed giving a presentation on Game A.I. to the group (having not presented at a major event since SQLBits VIII, back in April 2011, it was good to get back into it).

Then, following a meeting with my friend Adrian Cooke, director of Norwich Sound + Vision, I now find myself co-organising the Norwich Game Expo – a public event in Norwich on October 11th/12th 2013 showcasing some of the creative game dev talent going on in the East of England.

I’ve spent the day planning the event: speaking to sponsors, funding organisations, media organisations, and I feel excited and energised. Despite being only an “adopted” Norfolkian, I’m proud to represent the technical and creative talents of Norwich and the East of England, and I’m looking forward to showing the rest of the world some of that greatness too. Expect to hear a lot more soon.

 

Methods for Combining Autonomous Steering Behaviours

“Autonomous Steering Behaviours”, as first defined by Craig Reynolds in his presentation at the 1999 Game Developer’s Conference, are a simple yet effective method of creating realistic movement in computer-controlled characters. As such, they are often considered an important part of “Game A.I.”, despite not really having any relation to traditional A.I. techniques.

Using Reynolds’ model, the movement behaviour of an autonomous character can be described using active verbs that represent certain desires:

• A homing missile seeks its target
• A police car pursues a fleeing criminal
• A hoard of orc minions follow their orc leader
• An outlaw evades the sheriff’s bullets
• A convict may hide from the prison warden
• etc. etc.

Although they represent a range of different movements, each of these behaviours can be implemented following the same basic pattern, which can be summarised as follows:

1. Determine the desired target location.
2. Calculate the desired velocity vector, which points from the character in the direction of the target,  truncated to the maximum allowed speed of the character (assuming that the character wants to reach the target location as quickly as possible)
3. Compare the desired velocity to the current velocity, and calculate the acceleration required as the difference between them.
4. Apply a steering force to the character, in the direction of the desired acceleration, truncated to the maximum allowed force produced by the character.

This is illustrated below, for the example of a car seeking a target (notice how the steering force is parallel to the vector of desired velocity – current velocity)

There are plenty of good online demonstrations of different individual steering behaviours (such as here or here), and, at some point, I’ll probably get round to writing up my own examples. However, for this post, I’m going to look at different methods to handle situations in which there may be two or more competing behaviours – you want to flee from an attacker but also avoid obstacles in your path, or you want to stay close to your teammates, but not so close that you’re stepping on their toes: how should we resolve these conflicting desires to come up with a single steering force in a given situation?

As an example for the methods discussed below, consider the steering forces shown in the following diagram generated by three different behaviours, named simply as A, B, and C, representing the vectors (1,4), (3,2), and (1,-2), respectively:

 

1. Priority Arbitration

Under this scheme, the various enabled steering behaviours are assigned a priority and, at any given time, only the behaviour with the highest priority is given control over the character’s movement.  Priorities can be set dynamically based on the current environment so that, for example, when a character’s health is low, the desire to seek for a health pack may have greater priority than the desire to steer for cover, but, at other times, the desire to steer into cover has greater priority and is therefore given control. To be more specific, arbitration should choose the highest priority non-zero steering behaviour. “Obstacle avoidance” behaviour, for example, might always be given top priority but only needs to produce a steering force in situations when a collision would otherwise occur. If no corrective action needs to be taken, obstacle avoidance produces zero force, and arbitration should continue to consider the next highest priority behaviour and so on.

For the example above, assuming that behaviour A has highest priority, the resulting steering force is therefore (1,4):

There are some limitations to this approach: if the “avoid collisions” behaviour only kicks in when it is given top priority, say, it’s probably at the point when the character is facing an imminent collision that could have been avoided earlier and more gracefully if that behaviour were allowed to have taken some slight corrective action a bit earlier (but it was never given priority to do so). Priority arbitration also does not allow for opportunistic behaviour so that, for example, when the current priority is to seek to a target, the character will not make a slight detour suggested by one of the other behaviours to pick up a great power-up along the way, which a human player would probably have done in the same situation.

 

2. Weighted Blending

In contrast to arbitration, “blending” involves considering all of the competing desires acting upon the character, weighting them, and adding them together to create a combined force suggesting the appropriate steering direction. This can result in smoother behaviour than arbitration, since every desire is considered at every step, rather than the character switching abruptly from one steering behaviour to the next. Weighted blending is often used in flocking behaviours, where the desires for separation, cohesion, and alignment with other members of the flock are blended together.

For the preceding example, if the behaviours were weighted (A:0.25, B:0.5, C:0.25), the resulting force would then (1*0.25 + 3*0.5 + 1*0.25 , 4*0.25 + 2*0.5 – 2*0.25 ) = (2, 1.5):

The problem with blending is that you can end up with a compromise that suits nobody. Suppose you were trying to seek towards a target, but evade an enemy that stands directly in the way. At some point, the sum of the weighted force assigned to these two actions would cancel each other out into an equilibrium, so that the character would remain motionless, torn between the desires to reach the goal but not wanting to get any closer to the enemy. Blending can also be computationally expensive, as every force must be calculated on every frame.

 

3. Prioritised Dithering

This approach combines elements of the above two, while also involving an element of random chance. Under prioritised dithering, the various behaviours are once again assigned a priority, but they are also given a probability, expressed as a value between 0 and 1. In any given step, a random number is generated between 0 and 1. If the probability assigned to the top priority behaviour exceeds the random number generated (and, when executed, the behaviour generates a non-zero force), then that behaviour is given control and no other behaviours are considered. Otherwise, if the probability of the top priority behaviour is less than the random number, or if the resulting action generated no force, then a new random number is generated and used to test against the probability of the next-highest priority behaviour being executed. This continues down the behaviours in descending order of priority, until a non-zero force is generated by some behaviour.

The result of the previous example, if we assume that behaviour A is not chosen by random selection, and then behaviour B is selected, is (3, 2):

This is an interesting approach, which solves some of the problems of the previous two. Because only one steering behaviour actually gets given control, it is relatively cheap on CPU, whilst still giving every behaviour some opportunity to influence movement at every step. However, tweaking the appropriate values of probability and priority for each behaviour can take some work.

 

4. Weighted Prioritised Truncated Sum

Apart from having a silly name, this is my favoured approach, as it is a nice balanced hybrid method that makes use of both weight and priority assigned to each behaviour. Once again, behaviours are considered in priority order, with the highest priority behaviour being considered first. Any steering force generated by this behaviour is multiplied by its assigned weight and added to a running total. Then, the total (weighted) force accumulated so far is compared to the maximum allowed force on the character. If the maximum allowed force has not yet been reached, the next highest priority behaviour is considered, the steering force it generates is weighted, and then this is added onto the cumulative total. And so on, until either all of the steering behaviours have been considered, or the total maximum steering force has been assigned, whichever occurs first. If at any point there is still some surplus steering force left, but not enough to allocate the whole of the desired steering force from the next highest-priority behaviour, the extra force is truncated and what can be accommodated is added to the total (hence the weighted prioritised truncated sum).

When applied to the example using the same weights as before, and, assuming that the maximum force is exceeded after the steering force from behaviour B has been applied, the result is (1*0.25 +  3*0.5, 4*0.25 + 2*0.5)  = (1.75, 2):

 

So there you have it – four different methods, producing four different results. They each have their own strengths and weaknesses, so there’s no “correct” answer, but it’s worth considering the different options available when deciding how to adjust an autonomous character’s movement behaviour.

Artificial Immune Systems and Adaptive Strategies in Game A.I.

A.I., perhaps unsurprisingly, often borrows inspiration, language, and models from the world of biology. Two common examples are Artificial Neural Networks (ANNs) – based on a model of the brain, and Genetic Algorithms (GAs) - based on a model of evolution.

There are plenty of case studies of these biologically-inspired systems being used to develop “intelligent” computer-controlled videogame characters, and there are implementation examples in many game AI textbooks. However, I’ve never heard of an example of a game that makes use of an Artificial Immune System (AIS), i.e. a system based on the structure and processes of the human immune system. In fact, I could barely find any material on it at all, save a few articles in academic journals.

I find this a bit surprising because I can imagine several scenarios in which, following an initial exposure to a player’s actions, an A.I. system could develop an “immunity” to further situations in which the player plays that same action, which I’ll attempt to describe here.

The Scenario : a Simple RTS

Consider a simple Real-Time Strategy game in which two players each build up an army containing a maximum of 60 units chosen from three different unit types. As is common, each unit type is strong against one of the other types, but weak against the other, as follows:

• Type A beats Type C, but is beaten by Type B (i.e. B > A > C)
• Type B beats Type A, but is beaten by Type C (i.e. C > B > A)
• Type C beats Type B, but is beaten by Type A (i.e. A > C > B)

Depending on your gaming preferences, you might prefer to substitute “A”, “B”, and “C” with:

• A:“Scissors”, B:“Rock”, C:“Paper”
• A:“Archers”, B:“Cavalry”, C:“Pikemen”
• A:“Cockroach”, B:“Foot”, C:“Armageddon”…

However, I’ll just stick with A, B, and C for now.

Over the course of the game, a number of encounters take place. In an encounter, one unit is randomly chosen from each player’s army and they do battle. The unit who wins the battle is decided based on the precedence rules above. In a battle between two units of the same type, the winner is decided randomly with 50:50 chance.

Following a battle, the victorious unit survives and returns to the winning player’s army, while the defeated unit is destroyed.

Let’s now assume that both players always maintain their army at maximum strength. In other words, as soon as a unit is defeated in combat, the losing player always build a new unit to replenish their army back to full capacity of 60 units. The strategy of the game therefore comes in deciding which unit types to initially build, and which types to replace them with when they are defeated following an encounter.

 

#1: Balanced Mixed Strategy

In this simple strategy, each player initially builds their army to consist equally of one third each of the different unit types.

When a unit is defeated, the player builds another unit of the same type to replace it, maintaining the same ratio of unit types in their army throughout the entire game.

Player 1’s Army

Player 2’s Army

As you’d probably expect, after simulating 1,000 battle encounters under this balanced mixed strategy, the win ratio between the players averages out to be 50:50:

In this type of simple 2-player, zero-sum game, both players randomising between the three unit types is a Nash Equilibrium and, if both players were rational, their optimum strategy would always be to ensure their army consisted of one third each of the different unit types. Anything other than this could be exploited profitably by the opponent, as we’ll see shortly.

 

#2: Unbalanced Mixed Strategy

Real players aren’t rational, and different people’s play styles often choose them to favour one unit type over another. Suppose Player 1 has a preference to playing with Unit A, and they don’t really like Unit C much at all. So, they build up their army as follows:

• Unit A: 35
• Unit B: 20
• Unit C: 5

Player 2 (the computer-controlled player) has no knowledge of Player 1’s strategy, so starts as before with a balanced army of each type:

• Unit A: 20
• Unit B: 20
• Unit C: 20

Once again, whenever a unit is defeated, the losing player chooses to replace it with a unit of the same type as that just defeated to maintain their chosen ratios, so the makeup of each player’s army over the course of the game remains constant, as follows:

Player 1’s Army

Player 2’s Army

It might not be as apparently obvious as in the first example, but the win ratio between players using these strategies after a series of encounters still converges to 50:50. Even though it is more likely that Unit A will be chosen from Player 1’s army, there is an equal chance of Unit A, B, or C being chosen from Player 2, so it is still equally likely that either player will win a random encounter (this would still be the case even if Player 1 built only one type of unit):

But, is there are a way that Player 2 could exploit the fact that Player 1’s army is now unbalanced? Obviously, computer-controlled A.I. can always “cheat” and simply build the appropriate unit types to defeat the unit types it knows the player is building, but that is a little unfair. Instead, let’s see if we can develop a kind of “Artificial Immunity” through nothing more than knowledge of the unit types encountered in battle, and whether they were defeated or not.

 

#3: Adaptive Strategy using Artificial Immunity

Suppose that, once again, Player 1 favours an unbalanced mix of unit types as in the last example:

• Unit A: 35
• Unit B: 20
• Unit C: 5

And, as before, Player 2 starts with a balanced army of each type:

• Unit A: 20
• Unit B: 20
• Unit C: 20

However, in this example, we’ll attempt to model the idea of Player 2 developing an artificial immunity to Player 1’s actions by changing the strategies regarding unit replacement:

• If Player 1 wins, their successful unit survives while Player 2’s unit is destroyed. Player 2 is no longer constrained to maintain the same ratio of unit types in their army, but is none the wiser about how to defeat this type of opponent, so they build a replacement unit of a randomly chosen type.
• If Player 2 wins, their successful unit survives while Player 1’s unit is destroyed. Player 1 builds a replacement unit of the same type that was defeated (in order to maintain their preferred 35:20:5 ratio of unit types). BUT, Player 2 also chooses to replace one of the existing units of their army (chosen at random) with another unit of the type that just succeeded in battle.

You can consider this second rule to mimic the immune response – having encountered a hostile antigen (Player 1’s unit), and successfully neutralised it, the Artificial Immune System generates more of the appropriate antibodies (the unit type that dominated it) to respond if the same antigen is found in the future. (This at least concurs with my GCSE biology understanding of the immune system!)

So, how does it perform in practice? First, let’s see how the composition of Player 2’s army changes over the course of the game using this strategy:

Player 1’s Army

Player 2’s Army

Player 2’s army starts, as in all the previous examples, equally composed of A:20, B:20, C:20. However, rather than being fixed, notice how the composition of Player 2’s army changes to approximate A:5, B:35, C:20, which best responds to the composition of Player 1’s army of A:35, B:20, C:5. If you prefer to think in colours, notice that the green band of Player 2’s graph approximates the red section of Player 1’s, the red section of Player 2 approximates the blue section of Player 1, and the blue section of Player 2 approximates the green section of Player 1.

And the effect on the average win rate clearly shows that this “immunity” that has developed over the course of previous encounters gives Player 2 the competitive edge, with an average win rate of over 70% after 1,000 encounters :

At this point, it seems reasonable to expect Player 1 to notice that things aren’t going as well as they’d hoped, and to try changing their strategy. Let’s suppose that, after 1,000 encounters, they change the composition of their army, dropping unit A entirely and instead forming their army equally from unit types B and C (i.e. A:0, B:30, C:30). Player 2 continues to play the same adaptive immunity strategy:

Player 1’s Army – switching after 1,000 encounters

Player 2’s Army adapting to change

Notice how Player 2’s strategy quickly adapts to the change in Player 1’s strategy: after 1,000 battles, Player 2 no longer encounters any further Type A units from Player1 (as there are none in her army), so Player’ 2’s own production of Type B units (green) drops accordingly. Likewise, Player 2’s production of Type A units (red) increases to reflect the increased number of encounters with Player 1’s Type C units (blue).

Note that, even after 1,000 iterations with no encounter of a Type A unit, Player 2’s army still contains a residual reserve of Type B units generated by random chance following a defeat, ready to be activated should Player 1’s strategy change again.

This is only a very simple model of how game A.I. could be modelled based on an artificial immune system response, but I think it shows that it’s definitely a technique worth investigating further.