I figured it out! For anyone wondering, I used this heuristic function:
public static function diagonalHeuristic(node:INode, destinationNode:INode, cost:Number = 1.0, diagonalCost:Number = 1.0):Number {
var dx:Number = Math.abs(node.x  destinationNode.x);
var dy:Number = Math.abs(node.y  destinationNode.y);
var diag:Number = Math.min( dx, dy );
var straight:Number = dx + dy;
return diagonalCost * diag + cost * (straight  2 * diag);
}
And then I just increased the cost of traveling diagonally.
