BrainBlitz.org

Now that I’ve reached a bit of a milestone with the pathfinding stuff, I’m taking a break to play with some other items on my to-do list. One of those items is “Give haXe (hex) a spin. haXe is a programming language (very similar to AS3 in syntax) that compiles to multiple targets, including PHP, C++ (code), AS3 (code and swf). It extends AS3 in a couple of ways, and those extensions are the reason I became interested in it in the first place. These include conditional compilation, assertions, apparent execution speed improvements,  and alternative syntax for some unwieldy–yet very frequently occurring–situations involving traversing object members and list elements.

haXe is just a compiler, so of course I had to find a decent IDE, as I’m too un733t to mess with the command line. I’m going with FlashDevelop at the moment, which seems entirely sufficient, andit has an extremely clever name to boot. (That last part was sarcasm, for the less sarcastically perceptive reader). Also, support for haXe is built in. Also, Michael at polygonal labs likes it, and I like every thing Michael likes by default, because he’s smart and wrote such a nice data structure library for AS3 (and haXe).

ANYway, the actual reasonfor this post is that I ran into a couple of complications while getting things up and running. They weren’t covered anywhere in the docs for haXe OR FlashDevelop, so I thought I’d just mention them here.

First, when installing haXe, I received “ERROR = [file_open,C:\Program Files/Motion-Twin/neko/gc.dll]“, followed by “installation aborted.” In my case, simply running the installer with admin privileges fixed it.

Second, although I had the debug version of flash installed, for some reason FlashDevelop was showing an error instead of traces in it’s output. It was compiling and running fine (the swf), but I just wasn’t getting any output. So I downloaded the latest “Projector content debugger” from adobe, then set the path in FlashDevelop ( Tools | Program Settings… | FlashViewer | External Player Path ). Now it’s showing output correctly.

Back to playing…

And here I thought I was doing good because I had basic pathfinding implemented. Pffft. Turns out, that is only half of the story. The other half is unit coordination.

A* works very nicely, as long as the walkable/unwalkable cell states are at least somewhat permanently so. But what happens when you have, say, two units, getting all up in each-other’s grill? With A*, you find the path, then set the units on their way. Along the way, one may invalidate the path of the other. You can, of course, be performing collision detection en-route, and repath a unit if it encounters another. This is what I did in the demo on this page. The problem is, this direct approach opens a huge can of complicated worms. The system as a whole is so dynamic, that trying to handle all of the possible “race conditions” and circular results inevitably produces quite the code quagmire.

Here’s the actual demo. Click to create a tower “character.” Control-click to reinitialize the whole thing.

It won’t take much playing with it to realize that it is very, very broken. Characters will freeze as their states become invalid. Characters will be retarded. Sometimes the whole darn thing will freeze. (No code this time… it’s simply a nightmare, what-with all of my experimenting.)

 Not that you can’t make an acceptable algorithm using the straight-forward approach that I have here for simple applications, but I’m aiming a little higher for my final “product,” and most likely will take a step backwards in progress and work on more elegant solutions.

Here’s a rough outline of what’s happening in my code:

• Unit starts in sleep mode, searching within its site range for entities from a different (“enemy”) group.
• If enemy unit is found, build a list of all open cells adjacent to enemy. 
• Pick closest enemy-adjacent cell that is open, and run A*.
• Check for collision with other units on frame.
• If collision, modify A* map with other character’s cell as unwalkable, recalc path, and revert A* map to prior state.

So, where do the issues come in?

One example is when the characters go into a collision state, and may respond in a way that keeps them in a collision state (i.e. they both move to the same cell to avoid the collision). This often results in “stuttering,” where the solution to the collision puts them into a collision for which the solution puts them back into the original collision. This could be handled in a couple of ways.

1. Have the first unit (#1) to detect the collision send a message to the other unit (#2) to ignore it (#1).
2. …sorry, I forgot what the other idea was while writing the first. I’m tired.

I’ll spend a little more time seeing if I can get an acceptable algorithm with the straight forward method. Otherwise…

I’ve got my reading cut out for me.
Amit’s Notes about Path-Finding – the pathfinding Bible? (Look at the rest of the site too)
Gamasutra: Coordinated Unit Movement - by Dave Pottinger (developed AI for Age Of Empires)
Gamasutra: Implementing Coordinated Movement - also by Dave

Also relevant:
AS3 data structures library (requires CS4, I believe) – at the moment I’m only using singly and doubly linked lists, but as I take a step back, I’ll probably end up using a lot more from it.
Cute lil’ character sprites by Karura

UPDATE: newer demo and source at http://www.brainblitz.org/anthony/as3-pathfinding-and-game-source.

Here is a* (a star) again, a little further along. Download: http://www.brainblitz.org/Misc/astar/v1.0/AStarMap1.0.zip

 Instructions: drag to fill squares, shift-drag to erase, space to run, r to clear all cells.

If you play with it, you’ll notice that the path always veers slightly into concave “barricades.” Some times it even just seems to arbitrarily wander off course by one cell, when it should be going in a straight line.

Why? The g cost of a diagnol movement is supposed to be 1.4 times the cost of a “straight” movement. I left that out of the algorithm for 2 reasons:

1. For reasons I haven’t quite figured out, it runs 3 to 4 times faster without it.
2. The imperfect solution almost looks more natural, with a little bit of random-ish looking meandering.

Here are a couple of examples of some of the quirks:

Speedwise, I don’t know what is typical for A*, but in Flash player, the time varied from 12ms to 23ms, the latter for very concave maps. In comparison, the graphics usually registered 0. So I’m sure there’s tons of room for improvement.

Class AStarMap

• gridWidth
• gridHeight
• AStarMap(_gridWidth:int, _gridHeight:int)
• setEndPoints(originX:int, originY:int, destX:int, destY:int)
• solve():Array
• getPath():Array
• getCell(xx:int, yy:int):Object
• setCell(xx:int, yy:int, cellType:int)
• toggleCell(cellX:int, cellY:int)
• reset()

Typical usage:

   var map:AStarMap = new AStarMap(20, 20);
   map.setCell(2, 4, map.CELL_FILLED);
   map.setCell(3, 4, map.CELL_FILLED);
   map.setCell(4, 4, map.CELL_FILLED);
   map.setCell(5, 4, map.CELL_FILLED);
   map.setEndPoints(2, 2, 18, 18);

   var solution:Array = map.solve();

The returned Array is an array of cell objects. Each object has the following properties:

   cell.x
   cell.y
   cell.parentCell  

Note that this class does NOT address graphics: it is purely “math space.”