Ball Bouncing off Plane Calculation

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.

ActionScript for Multiplayer Games and Virtual Worlds

I recently finished writing ActionScript for Multiplayer Games and Virtual Worlds, my first book since Flash 8! With the help of some amazing contributors I think this is the most useful and geeky-fun book I've ever been a part of. According to Amazon (shameless link) it hits shelves in 8/3/2009.

So what's it about? If the title of the book doesn't give it away, it is a book that focuses on multiplayer concepts and applies them to games and virtual worlds via ActionScript. Some of the coolest topics are those on dead reckoning, real-time movement and time synchronization, loads of information on avatar rendering, and other useful topics like thorough coverage of isometric concepts.

While there are many examples throughout the book, there are 3 major examples. In one chapter we build a real-time multiplayer tank game (top down). In another chapter a cooperative multiplayer games is created, and its a fun one! Then over the course of several chapters we dig into various major topics on virtual worlds to build a complete world.

Here are some screenshots, and I hope some of you check it out and find it useful :)

Virtual world

Real-time tank game

Cooperative multiplayer game

Ball Bouncing off Line Calculation

I'm working on a new game that requires me to dig into some physics and math that I haven't touched in a while. The Vector3D class was introduced with Flash Player 10. I used this as an opportunity to get familiar with that class and see if it could make life a little easier, and it does!

The Vector3D class keeps track of x and y (and z if you want it to) values. It uses the sign on the value to imply direction. You can then perform cross products or dot products and a few other basic vector actions via its methods.

Conceptually, here is how to make a ball (or sphere) bounce off of a line (assuming you can calculate that the collision is occurring).

1. Use a vector for the ball velocity
2. Use a vector to represent the line normal (perpendicular to line)
3. Do simple vector algebra to get new velocity

Step 1
Represent the ball velocity as a vector. For instance,
var velocity:Vector3D = new Vector3D(2, 0);

Step 2
Represent the line normal as a vector (which it is). For instance,
var normal:Vector3D = new Vector3D(1, -1/line_slope);
normal.normalize();

Step 3
Do the vector math when a collision is detected. You can imagine that the velocity vector can be projected onto the normal, and it is only that bit that will be reflected off of the surface. So, we'll project it onto the normal and set the net change to 2 * this value. 1* the value makes the velocity 0, 2 * the value sends it back an equal amount. We then take this reflected vector and subtract from the incident velocity vector.

var reflectionScalar:Number = 2 *velocity.dotProduct(normal);
var reactionProjection:Vector3D = normal.clone();
reactionProjection.scaleBy(reflectionScalar);
velocity.subtract(reactionProjection);

Download source

Progeny Particle Engine

Lately I've been able to find a few hours here and there to start experimenting with code again and exploring ideas that have been on my mind for a while. (I sure have missed that!)

What I've been working on specifically is a particle engine. Over the years I've kicked out simple one-off particle effects just for fun (like this one in AS2 a couple of years ago). But I never took the time to do it right and build something extensible and reusable. The example shown in this blog post on theflashblog.com is what inspired me to make an engine rather than one-off effects. All cool projects deserve a cool name, so I call this progeny.

Before I talk about how the system works and where I think I am in the development cycle, here is an example that shows 4 effects. Each effect uses progeny and has no throw-away code other than the lines used to configure the effect.



You can see that some of the effects that I show here are made to look similar to the partigen example from theflashblog.org post I referred to above. I started with those since I knew they were possible and could be fairly high performance.

This version of progeny is sprite-based. Each particle is a sprite that is scaled, alpha'd, rotated, and moved over time. It is used by adding an emitter (or progenitor if you will) to the screen and then configuring it. The example above contains 4 emitters. Effects can be made up of multiple emitters. For example, if the smoke was made to be a bit more subtle and then offset above the fire, it makes for a much cooler and realistic fire example.

I hope to be able to go into more detail about what is going in here and how it really works in one or more future posts. And I hope that I can do that really soon (within days) if my schedule allows.

My current plan is to develop a simple user interface that allows you to create and configure effects. Also, I am considering toying with making this a 100% bitmap-based approach, where there is a single display object and the scene is rendered by manipulating BitmapData instances directly.

That's it for now!

How to Crash Flash CS4 With a Single Click

UPDATE (11/22/2008) -
Just wanted to post my final solution to this particular issue - I bought a new computer. I've been on it for about 2 weeks running CS4 crash free the whole time! Note: Adobe made themselves available to assist with my problem. But we were not able to solve it.

UPDATE (10/20/2008 - evening) -
I just got a good 20-30 minutes of usage out of Flash CS4 this time before it crashed with the same error as seen below. At this point I'm through with Flash CS4 until Adobe releases an update, or until I hear from other people that CS4 is rock solid for them. Back to CS3 for me...

UPDATE (10/20/2008 - morning) -
Reinstalling Flash CS4 a 2nd time fixed this particular issue! Time for me to give CS4 another shot.

UPDATE (10/18/2008) -
Looks like I spoke too soon below. I cannot reproduce this error on my other machine with another CS4 installation. This is reproducible every time on one machine, and never on the other machine. So it does look like it is specific to my installation. This is hopefully not a CS4 issue. When/if I learn more I'll update here.

Original post -

I was so excited to start using Flash CS4 that I bought it within hours of becoming available. The very first project I tried it on is one that we (at Electrotank) have been working on for a while. It won't compile properly. You can watch the status of that issue here.

So, forced to continue with Flash CS3 on that other project I was looking for an excuse to use Flash CS4 on something else. This morning I decided to give it a shot on a brand new smallish game project. I opened an FLA created by an artist containing the game UI and Flash crashed within about 2 or 3 minutes.

If you haven't seen this crash window yet consider yourself lucky. I'm guessing you'll become acquainted with it shortly. I have tried two projects in CS4 neither of which will allow me to do my job.







By letting Flash crash on me about a dozen times I narrowed it down to a single spot. If I click on this spot Flash crashes. (The application Adobe Flash CS4 has unexpectedly quit.)

I packaged up an example for others to try. Sure, maybe (and hopefully) this is just something funky with my setup. But you can try it yourself. Download this fla.

1. Open the FLA
2. Click on the word 'Repeat'
3. Weep

You probably don't have that font installed. I opened it up in CS3, changed the font to Arial, then tried again in CS4 and it still crashed.

I'm not sure I'll try a 3rd project in CS4 until we hear from Adobe that these issues have been resolved. We've already lost more money this week on man-hours than we did on buying Flash CS4. We'll cut our losses for now.

I'll be the first one using CS4 once I can have confidence in it.

Flasch CS4 and White Screen of Death (WSOD)

Note: This issue was completely resolved in the 11/17/2008 Flash CS4 update. Scroll to the bottom for more final update to this post.

For those that don't know this issue in Flash CS3, here is the briefest summary: it SUCKS.

White Screen of Death is the issue where your compiled application will run no code. Throw a trace statement on line 1 of frame 1, and nothing. This has happened here at Electrotank on at least 3 projects, each of which has hundreds of classes (in CS3).

In Flash CS3 you could get this to stop happening by wishing real hard and rebooting 17 times. Then you're good for a few weeks. But seriously, it can actually go way sometimes by just restarting Flash.

So CS4 shipped yesterday. I immediately bought a copy and fired up my current application, published. And guess what? WSOD!

Open that same FLA in CS3, works. CS4, doesn't. Verified on 3 machines.

Obviously this really, really, sucks. We have to stick with Flash CS3 for now because CS4 won't function properly. There is at least some hope though. Erik Bianchi has packaged up an example and sent it to several Adobe engineers so they have an example right in front of them.

If anyone out there happens to know a trick to get around this, please speak up!

UPDATE - Friday Otober 17 2008
My backchannel tells me that Adobe is "on it". And that they have been burried by emails since launch.

UPDATE - Saturday October 18 2008
I've gotten word (indirectly) that a couple of Adobe's engineers are working on this issue.

Update - Monday October 20 2008
No word from Adobe today. But I heard from someone on a completely unrelated project that they just upgraded to CS4 and are getting WSOD. Works in CS3, not in CS4.

Update - Saturday October 25 2008
There is an Adobe technote that looks to have been added in the last week. It is definitely the issue outlined here. If you rip your project into enough swcs or swfs then apparently you can still move forward. It is good to see it officially listed as a problem - but I don't like the solution. I hope that Adobe sees it as a bug and will address it in a future update. The applications in which I've witnessed this bug have hundreds of classes. I reduced it substantially with a few bigger swcs and still had the same bug. There is no definitive limit here. So, how far do you have to break your application down?

This is likely to be my last update on this topic for a while unless there is some noticeable movement at Adobe or if someone in the community has a good discovery.

Update - Thursday October 30 2008
Great news on this topic! Richard Galvan (Adobe Flash's product manager) and Sean Kranzberg (senior manager quality assurance) reached out directly to me regarding this issue. Apparently it is related to memory allocation to the JVM, which the compiler uses. They assured me that they are taking this issue seriously and *will* have a fix in their first Flash CS4 update. No release date is currently slated - but the worlds "some time in November" were spoken. When the release is official I'll update here.

Update - Saturday November 22 2008
Adobe released an update this wee to Flash CS4 that completely fixes the issue! You can get the update yourself through the Adobe Updater, through Flash CS4 > Help > Updates, or here. Here is the relevant part of their release notes:

"This update also provides fixes for problems related to compiling large files and applying motion to multiple objects. "

Update - Thursday February 19 2009
A fellow Electrotanker sent me a link to this blog post where someone else reporting the WSOD issue. If you scroll down to response #4 a person suggested increasing the Java heap size on his computer (which is a global setting). WSOD occurs when the Flash compiler runs out of memory. Increasing the Java memory allocation solves the problem!

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

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.