Feeds:
Posts
Comments

Archive for the ‘flash’ Category

Bresenham’s line algorithm is a fairly simple algorithm that takes two tile positions in a grid and returns a list of all tile positions that a line drawn between the two positions touches. It is well described along with easy-to-read pseudo code here.

When is this useful? According to what I’ve read, this algorithm and variations of it are useful in graphics programs. I’m sure you’ve seen programs that let you draw icons in a zoomed-in view. While you draw lines it just colors in boxes. It is likely this algorithm was used for that. However, I use this algorithm for game-related purposes. The last time I used it was probably 5 or 6 years ago in a Flash pool game. I set up a grid with an arbitrary tile size on the pool table (that the user can’t see). Every frame I determined in memory which tiles a ball covered as it moved (assuming no collisions). Then I would only run collision detection against balls that touched the same tiles. This let me cut down on the number of collision checks per frame.

I’m coming back to this algorithm again now because of a first person shooter game I’m working on. I hope to create a blog post on how the algorithm is used in that game (on the server) to keep the collision detection calculations to a minimum.

I created a Flash demo of Bresenham’s line algorithm that you can play with by clicking on the image. Or you can download the source files here.

click to view example (drag dots around)

Advertisements

Read Full Post »

Adobe invited me to participate in the prerelease programs for Flash CS5 and AIR for Android. I took some time and built a game for the iPhone called Fruit Smash Organic which is currently in the iTunes app store. While I love my iPhone, Apple sure does make you jump through some ridiculous hoops to get an app on it. Even if it is your own testing device! The biggest frustration I had was with just getting my game onto the device.


With the latest crApple news it was time to get my hands on an Android device. My Nexus One arrived yesterday (FedEx Saturday delivery FTW) about 4pm, and I had Fruit Smash Organic ported to the device and running beautifully by 7pm! That includes downloading and installing the SDKs, walking through a Hello World tutorial, charging the device for a little while, and making some minor code edits. Kudos to Adobe and Google for making the process easy instead of a nightmare.

Also, the game performance is great! It doesn’t even think about dropping below full frame rate, and easily out performs the same app running on the iPhone. I look forward to creating more games for Android using Flash!

Short 45 second video showing primary game play.

A slightly longer video showing primary game play and some secondary elements. And you can see the reflection of my and my flipcam 🙂

Read Full Post »

This post is related to a post I made a few days ago titled Ball Bouncing off Line Calculation.

The code used to determine the collision reaction of a ball bouncing off of a line shown in the previous post is the same as the code required to do it in 3D! So, you can achieve a ball bouncing off of a plane. Or, when you add gravity plus a little damping on the floor you can have things rolling around.

This example was designed so the ball would hopefully roll for a long time without rolling off. But if the ball was going a little faster you’d see how it can bounce into the air a bit if it hits an incline fast. Anyway, just thought I’d share!

(marble madness anyone?)

Note: if it seems a little slow, it is probably the 5 other blogs on this page that are running more intense things.

click to view example

Read Full Post »

A* (astar) Pathfinding

Finally I am getting around to the A* post I promised more than a year ago. Better late than never I guess 🙂

A* is a state change optimization algorithm. It looks at a system in its current state and determines the lowest cost series of state changes needed to arrive at a target end state. Most commonly A* is used for pathfinding. I have never seen A* used for anything but pathfinding, but you could use it to do things like solve a Rubik’s cube or a picture slider puzzle.

Here is how it works. First, your map needs to be tile-based. A* will take a starting point and a target destination, run its logic, and kick out the lowest cost path to that destination tile. In most A* implementations that I’ve seen lowest cost means shortest distance.

Cost
I’ve mentioned cost a few times now. Let me explain what this means. When you want to get a path from point A to point B you probably want the shortest path right? Well, what if that short path takes you through a river? Or through a fire? You’d probably want to the shortest path around that water or fire. But if the path around those things gets to be way too long, then maybe going through the water or fire isn’t such a bad idea anymore.

What cost does is assign a value to the act of moving from one tile to another. Those tiles have a terrain associated with them, such as grass, water, or fire. The cost of moving from grass to grass would be low because that is something you’d like to do. The cost of moving from grass to water would be a bit higher because you don’t want to get wet, but not extremely high because getting wet won’t kill you. The cost of going from grass to fire would be extremely high because fire is dangerous.

Here are some example terrain transition values:
grass-to-grass = 1
grass-to-water = 10
grass-to-fire = 100000000000

The cost of moving from one tile to another is determined by multiplying the distance between the two tile centers by the terrain transition value. Since the tile size is consistent through the entire map you can just assume that tiles are 1-by-1 for cost calculation. Horizontal or vertical transitions are a distance of 1. Diagonal distances are the square root of 2, which is 1.414.

The algorithm
During the search each tile that is touched is assigned a total score called ‘f’.
f = g + h

f -the total score
g – the total transition cost of all tiles touched along a path up to this current tile
h – the total estimated cost from the current tile to the destination

The h value is called the heuristic. It is what allows A* to start looking in the right direction from the moment it starts its search. If h was set to always be zero, then the search would expand radially from the start node. This heuristic allows it to start moving in what is probably the correct direction.

What the algorithm does is this:

  • Starts at the current tile and puts all of that tile’s neighbors into an array and stores their f value. The act of doing this (storing tiles with total cost in an array) is known as expanding the tile.
  • That array is sorted based on f.
  • The lowest f tile is grabbed and expanded.

This process continues until the goal node is reached. By the very nature of the algorithm, the first time the goal tile is touched you have found the the lowest cost path. There is more to the algorithm than shown above, but that is the main idea.

Demo
What I think is so cool about A* is the terrain stuff. If you take the time to use actual terrains and assign appropriate transition costs, then you can get realistic paths that look like an intelligent creature would have walked.

In the demo below you’ll notice that you can click on either side of the water and the path will usually take you over the bridge. But, if you go far enough away from the bridge then the path starts to take you through the water instead. If in your game your character should never go through the water, then you’d crank up that cost.

I put in a little editor UI so you can try making your own simple maps to test the pathfinding.

Just click once to add a start position, and again to add a target position. The path will automatically be calculated. To do it again, just click and the path will reset. (Beware of Trogdor. He is burninating the country side!)

Download Source

click to view example

Some final notes
Code improvements
The source code is set up well with a separate package for A*. It is reusable. We’ve been using it across many projects for more than a year. The search time in general is not a problem. But, if you wanted to significantly improve it you can implement a true priority queue. I put in a poor man’s priority queue – an array that is searched every time we do an insert.

Intended usage
While pretty fast, this algorithm isn’t blazing. It isn’t intended to handle real-time continual path updates. So if you have baddies running around looking for people to slaughter, A* isn’t the best way for them to seek and destroy. A* is generally meant to be used rarely (no more than once or twice a second.)

Concavities
The heuristic estimates the cost from the current tile to target tile. It doesn’t use terrain or walls when making this guess. So, if there is big concavity between the current tile and the target tile, A* might waste a lot of time going toward the target only to hit a wall, back track, and then eventually find the true best path. In my experience this does not prove to be an issue. In general the paths to be generated are on the order of 5 to 15 tiles and not massive.

Read Full Post »

I just got back from a fun week in Brighton, England for the Flash on the Beach conference. The weather was actually pretty amazing this year. Mostly Sunny, upper 50s, no rain! (After the blustery 2006 conference anything would be an improvement.) And as for the beer, I sampled bitters from no fewer than a dozen pubs with cool names 🙂 The Cricketer, Druid’s Head, etc

Anyway, on to the Flash stuff…

Electrotank was a FOTB sponsor and had an on-site presence. Thanks to the FOTB crowd for huge level of interest in ES4! It is always great to hear what multiplayer applications everyone is working on. Virtual worlds are all the rage right now and so we’re getting a lot of great feedback for ElectroServer’s insane scalability!

Read Full Post »

We just wrapped up another crazy week on the road. This week we attended the Flashforward conference in Boston to catch some amazing sessions and to present ElectroServer 4, our Flash streaming media and MMO server. Thanks to the attendees for the tremendous interest. It is always great to hear what innovative applications everyone is working on!

Below you can see our booth in the exhibitor area (cell pic).

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 »

Older Posts »