Feeds:
Posts
Comments

Archive for May, 2007

This is my second post in a series covering some popular AI topics. Previously I discussed emergent behavior and the game of life. In this post I continue with a slightly more advanced and practical example, Boids. I finish by showing an example and how I modified the classic Boids approach just a little.

Boids is a set of 3 simple rules. When these rules are applied to many agents (birds in this case) they behave like flocks of birds. Agents group together to form flocks and fly together as one. Flocks can merge into one or divide into multiple new flocks. These set of rules can be added to and modified fairly easily and applied to other types of creatures to achieve a wide range of behaviors.

Here is the classic Boids rule set. Each agent (boid) follows these rules:

  • Separation – If the agent is too close to another agent, then steer away.
  • Alignment – Steer toward the average heading of nearest boids
  • Cohesion – Attempt to match the speed of the nearest boids

If you think about the above rules you can visualize how flocking will occur. In my example below I added a fourth rule:

  • Avoidance – If too close a non-boid object (such as a tree), then steer away.

In addition to the 4th rule I added a restriction. An agent is only affected by an agent that it can see. It can see an agent if it is within a certain distance of that agent, and if the cone of view is such that it can actually see that agent. So, the leader of a flock of birds is not affected at all by its followers because from its perspective they aren’t even there. What this gives us though is a a flock that mostly follows the leaders. If you give a minor perturbation to the a leader then you can affect the entire flock!

Enough rambling. Check out the example below. Download the source if you’re interested.

One last note: In my example you might notice the birds rotating a little funny sometimes (wobbling or spinning). The movement is right, the rotation needs a little love. Right now they rotate to face the instantaneous direction of movement. In reality a bird won’t rotate directly to the right if its going to slide a bit to the right while in flight (wow that rhymes).

click to view example

Advertisements

Read Full Post »

Emergent Behavior

Like many programmers I find working with artificial intelligence fascinating. Most of my next several post will discuss common AI topics; and of course I’ll provide source files.

The focus of my first two or three AI posts will be on emergent behavior. Some AI is very complicated (think deep blue here). But what I think is extremely cool is when you have a simple set of rules and get a lot of interesting behavior out of it.

Emergent behavior can be described as behavior that isn’t explicitly defined by the system or by any rule in the system, but still occurs. Well, that’s my definition anyway :). Think of a line of ants walking across a yard. No ant knows how long the line is, or even that its a line. The ant just follows a scent or taste and the emergent behavior is dozens of ants following what looks like a long organized line.

I love emergent behavior! From a programmatic standpoint here is generally how it works.

  • Your system supports at least 1 agent type. An agent is anything that you want to follow a set of rules. Such as an ant, bird, monster, etc.
  • Each interval you apply the rule set to each agent.

That’s it! Well, the devil is in the details. Applying the rule set of course depends on the rules. Luckily this is usually not too complicated.

As an example of emergent behavior I’ve created a Conway’s Game of Life example (below). This is a very simple example. In this case, there is a larges grid of agents. There are around 2,000. The agents cannot change positions. Each agent is either alive or dead.

Every iteration these simple rules are applied to every agent.

  • A lonely agent dies. So, if it has two or fewer living neighbors then it dies.
  • An overcrowded agent dies. If the agent has greater than 3 living neighbors then it dies.
  • A content agent lives. If the agent has 2 or 3 neighbors then it lives.
  • Resurrection. A dead agent with exactly three neighbors is given life.

As you can see, the rule set is simple. But when applied to every agent you get some interesting behavior. Check it out below. Read even further to learn about some seed patterns.

DOWNLOAD

The Game Of Life is a well known system. Certain seed patterns have been found that end up exhibiting certain features. For instance, a ‘spaceship’ is a pattern that moves itself across the board. In the example above I show two such examples – glider and light weight spaceship. The ‘diehard‘ example is a pattern that looks interesting and dies after 130 generations.

So, is this useful at all? Not really. Or at least not to me. The Game of Life isn’t something you can just take and use in a useful way (or if you can then please clue me in). It is generally just used as a simple example of emergent behavior.

The next example I’ll show in a day or so is more useful, and way cooler!

click to view example

Read Full Post »

I’ve been very slow to move out of the Flash IDE for authoring my class files. With Flash CS3 I’ve pretty much been forced to due to the annoyingly laggy script editor. (Seeing characters appear 1/3 of a second after I type them and so on.)

So, a few weeks ago I checked out Flash Develop. I love it! With intellisense gone are the days when I have to actually open up a class to to remember the exact name of a method I want to call. That feature alone is worth the switch, but there are more! It auto-detects the class files in your project so you don’t have to manually add them all. And control + enter still does its thing. Nice.

Read Full Post »

One of my fellow tankers Mike Grundvig has been doing some AS3 speed tests and has come to some useful conclusions.

  1. Sprite sheets using scrollRect yield the highest performance animations.
  2. Object pooling helps avoid the overhead of object creation, but more importantly eliminates the annoying stutter that can happen during the garbage collection process.
  3. Using the display list (when that’s an option) to manage objects can allow faster iterations and eliminate name-based look-ups.

    Check out the post here. It is an interesting read and has an impressive example!

Read Full Post »

The ELO Rating System has been around for decades. It was originally used for rating chess players but is portable to other games and really fits in well with web games. We’ve been using it in various projects for 5 or 6 years.

Here’s what it does:

  • First of all, ELO is used to rate players based on skill level. It is generally used for two player games like chess. But with some modifications it can be used for more than that.
  • A new player is assigned a default rating, say 1200.
  • Two players compete and end with one of three results: player 1 wins, player 2 wins, tie.
  • The two player’s ratings are fed into an algorithm along with the end state of the game and a new rating for each player is returned.

If two players both rated 1200 played and player 1 wins. Then player 1 will have a rating of about 1205 and player 2 will be 1195.

What makes ELO so cool is what happens over time. Players that win a lot end up with higher ratings. But the higher rated player starts to see diminishing returns for defeating low ranked players. So in order for a high ranked player to increase his rank, he must defeat other higher ranked players. If a high ranked player loses to a low ranked player, he loses much more of his rating then he’d gain if he won the match.

Over time the game players will end up being rated based on their skill level rather than other factors.

Last year we (at Electrotank) created a series of 10 multiplayer minigames for The Daily Show with Jon Stewart. These multiplayer games support 2 to 4 players per game. Mike Grundvig wrote a modified ELO system to support this. The end result is a pretty cool rating system. Players can view their own ratings and the ratings of other players in the game.

You can download an example ELO algorithm written in AS2 by me here: DOWNLOAD

Or here is the code:

function determineRatingConstant(rating:Number) {

	var returnVal:Number = 10;

	return returnVal;

	if (rating<2000) { 		returnVal = 30; 	} else if (rating>=2000 && rating<2400) {

		returnVal = 20;

	} else {

		returnVal = 10;

	}

	return returnVal;

}

function calculateNewRating(player1Rating:Number, player2Rating:Number, player1Victory:Boolean):Number {

	var outcome:Number = 0;

	if (player1Victory) {

		outcome = 1;

	}

	//Takes the rating of two players, the outcome of the game, and returns the new rating of the first player

	var d:Number = player1Rating-player2Rating;

	var exponent:Number = -d/400;

	var expected_outcome:Number = 1/(1+(Math.pow(10, exponent)));

	var k:Number = determineRatingConstant(player1Rating);

	var new_rating:Number = Math.round(player1Rating+k*(outcome-expected_outcome));

	return new_rating;

}

var player:Object = new Object();

player.rating = 2000;

for (var i=0;i<1000;++i) {

	player.rating = calculateNewRating(player.rating, 2100, true);

	trace("i: "+i);

	trace(player.rating);

}

ELO is O.G.!

Read Full Post »

You can affect the address bar from within Flash! I don’t know how this has escaped my notice for so long. So I thought I’d post about it for the benefit of anyone else interested!

First, check out this simple example. Just click on the buttons and watch the URL change in the address bar. Notice that the Flash content does not get refreshed.
View Example
Download Example

If you want to learn more then you should download the latest version of SwfAddress created by Asual, here. There is code to work in AS1, AS2, and As3. SwfAddress uses some JavaScript files that work with Flash to get the job done.

Read Full Post »

Is it just me?

Or do Zorak and Larry King look like they share the same mother?

Read Full Post »

Older Posts »