Casual Game Development Techniques and Algorithms 2007-03-22T00:33:54Z Copyright 2007 WordPress austin <![CDATA[actionscript-mode for EmacsW32]]> http://blog.pettomato.com/?p=24 2007-03-22T00:33:54Z 2007-03-22T00:33:54Z Ben Leiting just sent me his modifications of actionscript-mode.el to get it to work with EmacsW32. I don’t have time right now to merge the two versions together, but you can download his version here. You’ll want to remove the “.w32″ from the end of the filename after you download it. Thanks Ben!

]]> austin <![CDATA[Memoization in Actionscript]]> http://blog.pettomato.com/?p=23 2007-01-14T20:14:26Z 2007-01-14T20:14:26Z I love this programming technique, mostly because it is so easy to just drop into your code and instantly trade execution time for memory usage. More information can be found here.

Actionscript
  1. package{
  2.   public class Memo{
  3.  
  4.     static public function Memoize(obj:*,func:Function):Function{
  5.  
  6.       // *** Each argument to func must provide a unique value when
  7.       // *** converted to a string. For example, something that just
  8.       // *** prints out as [Object] will not work.
  9.  
  10.       var hash:Object = {};
  11.  
  12.       var f:Function = function(...args):*{
  13.  
  14.         // Check hash for result.
  15.         var key:String = args.join(",");
  16.            
  17.         var result:* = hash[key];
  18.  
  19.         if(result == null){
  20.  
  21.           result = func.apply(obj, args);
  22.  
  23.           hash[key] = result;
  24.         }
  25.  
  26.         return result;
  27.       }
  28.  
  29.       return f;
  30.     }
  31.   }
  32. }

Example Usage

Actionscript
  1. package{
  2.  
  3.   import Memo;
  4.  
  5.   public class MemoTest{
  6.  
  7.     private var SumSeries_Memo:Function;    // Our memoized variant of the SumSeries function.
  8.  
  9.     public function MemoTest(){
  10.  
  11.       SumSeries_Memo = Memo.Memoize(null,SumSeries);  // Create the memoized version.
  12.  
  13.       var result:Number;
  14.       result = SumSeries_Memo(100,1);   // Computes result, caches it, and returns it.
  15.       result = SumSeries_Memo(100,1);   // Returns cached result.
  16.       result = SumSeries_Memo(100,1);   // Returns cached result.
  17.     }
  18.  
  19.     static public function SumSeries(last:Number,step:Number):Number{
  20.       var result:Number = (((last * last)/step) + last)/2;
  21.       return result;
  22.     }
  23. }

This is the simplest version that I could come up with which works in the greatest variety of cases. If you knew that you were only going to use it with integer arguments, then you could create a faster method to generate keys than converting the arguments to strings and combining them with join.

In case that it isn't clear, memoization only helps if you are calling the memoized function many times with the exact same arguments. Otherwise, it will be slower, due to the overhead of creating the keys and storing the result, and it will be a waste of memory. It is a very nice alternative to creating explicit lookup tables, because you are creating the table on the fly instead of beforehand. If you decide later that you would prefer for the computations to be done beforehand, you can simple call the memoized function sooner and let it cache the results.

If you have a different version of this technique, please post it to the comments area.

]]> austin <![CDATA[Emacs mode for AS3]]> http://blog.pettomato.com/?p=22 2006-12-31T16:06:40Z 2006-12-31T16:06:40Z I've rewritten my actionscript-mode to support AS3. I've stripped out everything related to AS2, but you can still get the old version from here.

actionscript-mode.el

I have been using this new mode for a couple months and I haven't had any problems, but your coding style might differ from mine, so please let me know if you run into any issues.

Update: Here is the other set of functions that I use when I code actionscript. As I said before, you probably will want to just pick and choose some functions from this file since it is highly customized to my personal environment and has a lot of dependencies.

as-config.el

]]> austin <![CDATA[Sound Effects]]> http://blog.pettomato.com/?p=21 2006-06-30T14:56:18Z 2006-06-30T14:56:18Z I've produced the sound effects for almost every project that I've worked on for the last 7 years. I've used synthesizers, tone generators, samplers, and sound libraries. At this point in my career, I've found that I can get the best results (for games) by starting with The SFX Kit. It's not cheap at $700, but if you do a lot of sound work, it pays for itself. The sounds are excellant quality and I can almost always find what I'm looking for. The set was designed for games, so there are all sorts of weapon, force field, and pickup sounds.

As a supplement to that set, I also recommend the XV Series. This set isn't geared towards games, but it contains a lot of foley sounds that aren't in the other set.

]]> austin <![CDATA[Changed Blog Name]]> http://blog.pettomato.com/?p=20 2006-06-01T01:13:43Z 2006-06-01T01:13:43Z I've renamed this blog "Casual Game Development," instead of "Flash Game Development." I'm only mentioning it here because I want to explain why. For the past three years, I have been using GNU/Linux for my personal work and general home computing, and for the last year, I have been using GNU/Linux as much as possible for my business. The switch to free software has been an eye opening and liberating experience. As a consequence (and following 7 years of Flash development), I'm trying to move away from Flash as quickly as possible*.

For more info on why free software matters, please visit The Free Software Foundation.

If you'd like to test drive GNU/Linux, you can burn a copy of Knoppix. With Knoppix in your cd or dvd drive, you can boot into a fully functioning GNU/Linux distro without putting anything on your hard disk.

*I'm sure that I will still be using Flash for client projects in the foreseeable future.

]]> austin <![CDATA[Reinitializing an Instance]]> http://blog.pettomato.com/?p=19 2006-04-17T13:45:14Z 2006-04-17T13:45:14Z Occasionally, I want to reuse an object without having to create a new instance from scratch. Creating an instance with the new operator can be prohibitively expensive if you have to do it a lot. For example, I'm working on a project where a firework explodes into several dozen sparks. If I was to create that many new instances at the same time, the game would stick on that frame for too long. After testing a variety of convoluted solutions, I discovered that the answer is actually quite simple.

Example Class

Actionscript
  1. class SomeClass{
  2.   public var Initialize:Function = SomeClass; // points to the constructor.
  3.   public var someProperty:Number;
  4.   public function SomeClass(arg1){
  5.     someProperty = arg1;
  6.   }
  7. }

Now, I have created a new variable that points to the constructor function. By calling Initialize(), I can re-run the constructor without having to create a new instance. As long as all the member variables are initialized in the constructor, the object should be good as new.

Example Usage

Actionscript
  1. var a = new SomeClass(3);
  2. trace(a.someProperty); // 3
  3. a.Initialize(7);
  4. trace(a.someProperty); // 7
  5.  

This solution works best if you can maintain a pool of instances, and grab a free instance when you need it. For my firework project, I create around 200 sparks up front because I know that is the maximum that I will ever use at one time. Then, instead of creating and deleting sparks during the game, I just borrow them from the pool and return them when I'm done.

]]> austin <![CDATA[Hooks and Closures]]> http://blog.pettomato.com/?p=18 2006-03-07T04:24:05Z 2006-03-07T04:24:05Z One design idiom that I have borrowed from Emacs Lisp is the concept of hooks. A hook is a function that's called when a particular event happens. In Emacs, for example, whenever I create a new file, I have a hook that checks if the file ends in ".as" and if it does, I automatically add some boilerplate code to the file (constructor, toString, etc). In a game, you could have a set of hooks that fire whenever a collision takes place, a timer runs out, a room is entered, etc. Any number of hooks can be added to an event and they are run in the order they were added. They can also be added/removed at runtime.

Below is a simple utility class, Hook.as, that provides two functions for working with hooks. The first function returns a new function that can be used to add hooks to an event. The second one returns a function that will run all the hooks that have been added.

Hook.as

ACTIONSCRIPT
  1. class standard.Hook{
  2.  
  3.   private function Hook(){
  4.     // We never instantiate this class.
  5.   }
  6.  
  7.   static public function MakeAddHookFunc(a:Array):Function{
  8.  
  9.     var f = function(new_func:Function,bOverwrite:Boolean){
  10.       // The list of hooks can be cleared by sending new_func=null
  11.       // and bOverwrite=true.
  12.  
  13.       // bOverwrite=true means to remove any previous hooks before
  14.       // adding new_func.
  15.  
  16.       if(bOverwrite == true){
  17.         // If we set a to a new [], then it becomes a different
  18.         // array than the one we used with MakeRunHooksFunc. Therefore,
  19.         // we instead set the length to 0.
  20.         a.length = 0;
  21.       }
  22.  
  23.       if(new_func != null){
  24.         a.push(new_func);
  25.       }
  26.     }
  27.  
  28.     return f;
  29.   }
  30.  
  31.   static public function MakeRunHooksFunc(a:Array):Function{
  32.  
  33.   // Returns a function which, when called, will call each of the functions
  34.   // in 'a'. You can call the function with any number of arguments as long as
  35.   // the functions that you added to 'a' can take those args.
  36.  
  37.   // *Note that the array that you pass to this function should be the same
  38.   // exact array that you used with MakeAddHookFunc.
  39.  
  40.   var f = function(){
  41.     var N = a.length;
  42.     for(var i=0;i<N;i++){
  43.       a[i].apply(null, arguments); // apply is used so that we can pass any number
  44.                                    // of arguments to this function.
  45.       }
  46.     }
  47.  
  48.     return f;
  49.   }
  50.  
  51.   public function toString(Void):String{
  52.  
  53.     return "Hook()";
  54.   }
  55. }

The second class, Simple_Button.as, is something that I use in a lot of places to give button behaviors to MovieClips. It uses the functions in Hooks.as to create hooks for button events and for disabling/enabling the button. For a button press event, I might add one hook to change the button graphic and a second hook to do whatever action the button should perform.

Simple_Button.as

ACTIONSCRIPT
  1. class standard.widget.Simple_Button extends standard.widget.Widget{
  2.  
  3.   private var _enabled:Boolean;
  4.  
  5.   private var RunEnableHooks:Function;
  6.   private var RunDisableHooks:Function;
  7.  
  8.   public var AddEnableHook:Function;
  9.   public var AddDisableHook:Function;
  10.  
  11.   public var AddMouseDownEvent:Function;
  12.   public var AddMouseUpEvent:Function;
  13.   public var AddRollOverEvent:Function;
  14.   public var AddRollOutEvent:Function;
  15.  
  16.   private var OnMouseDown:Function;
  17.   private var OnMouseUp:Function;
  18.   private var OnMouseOver:Function;
  19.   private var OnMouseOut:Function;
  20.  
  21.   static private var COUNT:Number = 0;
  22.  
  23.   function Simple_Button(parentMC, bCreateMC:Boolean){
  24.  
  25.     super();
  26.  
  27.     if(bCreateMC == null ||
  28.        bCreateMC == true)
  29.         Create_MC(parentMC);
  30.  
  31.     var enable_hook_ar  = [];
  32.     var disable_hook_ar = [];
  33.  
  34.     AddEnableHook     = standard.Hook.MakeAddHookFunc(enable_hook_ar);
  35.     RunEnableHooks    = standard.Hook.MakeRunHooksFunc(enable_hook_ar);
  36.  
  37.     AddDisableHook    = standard.Hook.MakeAddHookFunc(disable_hook_ar);
  38.     RunDisableHooks   = standard.Hook.MakeRunHooksFunc(disable_hook_ar);
  39.  
  40.     var mouseDownEvent_ar = [];
  41.     var mouseUpEvent_ar   = [];
  42.     var mouseOverEvent_ar = [];
  43.     var mouseOutEvent_ar  = [];
  44.  
  45.     AddMouseDownEvent = standard.Hook.MakeAddHookFunc(mouseDownEvent_ar);
  46.     AddMouseUpEvent   = standard.Hook.MakeAddHookFunc(mouseUpEvent_ar);
  47.     AddRollOverEvent  = standard.Hook.MakeAddHookFunc(mouseOverEvent_ar);
  48.     AddRollOutEvent   = standard.Hook.MakeAddHookFunc(mouseOutEvent_ar);
  49.  
  50.     OnMouseDown = MakeMouseEventFunc(mouseDownEvent_ar, _mc);
  51.     OnMouseUp   = MakeMouseEventFunc(mouseUpEvent_ar, _mc);
  52.     OnMouseOver = MakeMouseEventFunc(mouseOverEvent_ar, _mc);
  53.     OnMouseOut  = MakeMouseEventFunc(mouseOutEvent_ar, _mc);
  54.  
  55.     _enabled = true; // will be set to false, immediately.
  56.  
  57.     Enable(false);
  58.   }
  59.  
  60.   public function Enable(b:Boolean):Void{
  61.  
  62.     // Call Enable(true) to enable the button, and Enable(false) to
  63.     // disable it. If the button is already in the desired state, then
  64.     // the request will be ignored.
  65.  
  66.     if(b){
  67.  
  68.       if(!_enabled){
  69.  
  70.         _enabled = true;
  71.  
  72.         _mc.onPress          = OnMouseDown;
  73.         _mc.onRelease        = OnMouseUp;
  74.         _mc.onReleaseOutside = OnMouseUp;
  75.         _mc.onRollOver       = OnMouseOver;
  76.         _mc.onRollOut        = OnMouseOut;
  77.  
  78.         RunEnableHooks();
  79.       }
  80.     }
  81.     else{
  82.  
  83.       if(_enabled){
  84.  
  85.         _enabled = false;
  86.  
  87.         delete _mc.onRelease;
  88.         delete _mc.onPress;
  89.         delete _mc.onReleaseOutside;
  90.         delete _mc.onRollOver;
  91.         delete _mc.onRollOut;
  92.  
  93.         RunDisableHooks();
  94.       }
  95.     }
  96.   }
  97.  
  98.   public function IsEnabled(Void):Boolean{
  99.  
  100.     return _enabled;
  101.   }
  102.  
  103.   static private function MakeMouseEventFunc(a:Array,mc:MovieClip):Function{
  104.  
  105.     // This is just like Hook.MakeRunHooksFunc, but we are assuming that all the
  106.     // mouse event hooks are going to take the current mouse x and y positions
  107.     // the only arguments. *I don't really like this, but I need it right now
  108.     // to support legacy code.
  109.  
  110.     var f = function(){
  111.  
  112.       var x = mc._xmouse;
  113.       var y = mc._ymouse;
  114.  
  115.       var N = a.length;
  116.       for(var i=0;i<N;i++){
  117.         a[i](x,y);
  118.       }
  119.     }
  120.  
  121.     return f;
  122.   }
  123.  
  124.   public function toString(Void):String{
  125.  
  126.     return "Simple_Button()";
  127.   }
  128. }

Here is some example code that I used to create three buttons for selecting a character in a game:

Example Usage

ACTIONSCRIPT
  1. private function CreateButtons(Void):Void{
  2.  
  3.   var buttons = [];
  4.  
  5.   for( var i=0;i<3;i++ ){
  6.  
  7.     var b = new Simple_Button(_mc);
  8.  
  9.     buttons.push(b);
  10.  
  11.     var b_index = i + 1;
  12.     var b_mc = _mc["characterMC" + b_index];
  13.  
  14.     b.AddMouseDownEvent(MakeMsgFunc(_fsm,MSG_ChangeState,300,{index: b_index}));
  15.     b.AddMouseDownEvent(MakeMCFrameFunc(b_mc,"down",true));
  16.     b.AddMouseDownEvent(MakePressButtonFunc(buttons));
  17.     b.AddRollOverEvent(MakeMCFrameFunc(b_mc,"over",false));
  18.     b.AddRollOutEvent(MakeMCFrameFunc(b_mc,"off",false));
  19.  
  20.     b.Enable(true);
  21.   }
  22. }
  23.  
  24. static private function MakeMsgFunc(sending_fsm:StateMachine_NEW,msg_type:Number,delay:Number,data:Object):Function{
  25.  
  26.   if(delay == null)
  27.     delay = 0;
  28.  
  29.   var f = function(){
  30.     sending_fsm.SendDelayedMsgToMe(delay,msg_type,SCOPE_TO_THIS_STATE,data);
  31.   }
  32.  
  33.   return f;
  34. }
  35.  
  36. static private function MakePressButtonFunc(button_ar:Array):Function{
  37.  
  38.   var f = function(){
  39.  
  40.     // disable all buttons
  41.     for(var i in button_ar)
  42.       button_ar[i].Enable(false);
  43.   }
  44.  
  45.   return f;
  46. }
  47.  
  48. private function MakeMCFrameFunc(mc:MovieClip,label:String,bPlay:Boolean):Function{
  49.  
  50.   var f;
  51.  
  52.   if(bPlay){
  53.     f = function(){
  54.       mc.gotoAndPlay(label);
  55.     }
  56.   }
  57.   else{
  58.     f = function(){
  59.       mc.gotoAndStop(label);
  60.     }
  61.   }
  62.  
  63.   return f;
  64. }

This might seem convoluted at first, but the best part is that everything only does one thing. One of the main goals of functional programming is that there are (nearly) no side-effects. Notice that there's no "owner" or "parent" crap in any of the buttons. Also, notice that "buttons" is a local variable, but all the functions that you create with MakePressButtonFunc will always keep a reference to it, even when it passes out of scope. That's the "closure" that Actionscript and Lisp can do that many languages can't. Lisp advocates think that it's one of Lisp's most important features.

I'm not sure about the implementation in Flash, but in Lisp there are not any performance issues with creating all those functions, because it isn't like creating a new object. The "new" functions are actually very similar to the methods of a class. That's why you don't have to say "var f = new function." Also, the closures have those passed-in variables bound to them, so they might even be faster than "owner.doSomething()" which has to look up "owner" and then call the function.

Anyway, for me, this stuff has solved a lot of problems that I've dealt with in the past and I've been able to reduce a lot of my code significantly.

]]> austin <![CDATA[Flash Socket Server in Lisp]]> http://blog.pettomato.com/?p=17 2005-10-31T20:00:29Z 2005-10-31T20:00:29Z Here is another version of a socket server that you can use to catch your debug messages from a live swf. Python version here. This one is written in SBCL, which was compiled with threading enabled.

NOTE: I am new to Lisp. I have a feeling this script will be revised several times.

This code was built off of some example code by Patrick May. Dave Roberts, on the sbcl-help mailing list also gave me a few pointers.

This server probably doesn't need to be multithreaded if you are only using it to catch your debug output. I, however, plan to build some other servers off of this, so I am keeping it this way.

The necessary Actionscript to communicate with this server is the same as the Python version.

LISP
(in-package :common-user)                                                                                       
  •                                                                                                                      
  • (require :sb-bsd-sockets)                                                                                             
  •                                                                                                                      
  • (defpackage :myServer                                                                                                 
  •   (:use :common                                                                                                 
  •         :sb-thread                                                                                                   
  •         :sb-bsd-sockets                                                                                               
  •         :sb-unix                                                                                                     
  •         :sb-ext)                                                                                                     
  •   (:export :run                                                                                                       
  •            :stop))                                                                                                   
  •                                                                                                                      
  • (in-package :myServer)                                                                                               
  •                                                                                                                      
  • (defparameter *default-server-address* '(192 168 0 1)                                                                 
  •   "The default address on which instances of the server listen.")                                                     
  •                                                                                                                      
  • (defparameter *default-server-port* 8007                                                                             
  •   "The default port on which instances of the server listen.")                                                       
  •                                                                                                                      
  • (defparameter *default-server-backlog* 16                                                                             
  •   "The default number of simultaneous connections to the server.")                                                   
  •                                                                                                                      
  • (defconstant +null+ (code-char 0)                                                                                     
  •   "A null byte.")                                                                                                     
  •                                                                                                                      
  • (defun read-upto-null (stream char-array)                                                                             
  •   "Read everything from stream up until a null byte or EOF."                                                         
  •   ;; TODO: char-array was separated for efficiency, but now                                                           
  •   ;;       this isn't very clean.                                                                                     
  •   (do ((c (read-char stream nil nil) (read-char stream nil nil)))                                                     
  •       ((or (equal c +null+)                                                                                           
  •            (equal c nil))                                                                                             
  •        (if (equal c +null+) char-array nil))                                                                         
  •     (vector-push-extend c char-array)))                                                                               
  •                                                                                                                      
  • (defmethod handle-client ((socket inet-socket))                                                                       
  •   "Handle a client request."                                                                                         
  •   (let ((client-stream (socket-make-stream socket :input t :output t :element-type 'character :buffering :full))     
  •         (s (make-array 1024 :fill-pointer 0 :adjustable t :element-type 'character)))                                 
  •     (do ((message (read-upto-null client-stream s) (read-upto-null client-stream s)))                                 
  •         ((equal message nil)) ; Quit when the client closes the socket.                                               
  •       (cond                                                                                                           
  •         ((equal message "<policy-file-request/>")                                                                     
  •          (write-line "sending policy file")                                                                           
  •          (format client-stream "<?xml version=\"1.0\"?><cross-domain-policy><allow-access-from domain=\"*\" to-ports=\"~A\" /></cross-domain-policy>" *default-server-port*)
  •          (write-char +null+ client-stream) ; terminate the response with a null byte                                 
  •          (finish-output client-stream))                                                                               
  •         (t                                                                                                           
  •          (write-line message)))                                                                                       
  •       (setf (fill-pointer s) 0)))   ; Reset our character array                                                       
  •   (write-line "Closing client connection.")                                                                           
  •   (socket-close socket))                                                                                             
  •                                                                                                                      
  • (defmacro with-socket (socket &body body)                                                                             
  •   "Create and close a socket around the body."                                                                       
  •   `(let ((,socket (make-instance 'inet-socket                                                                         
  •                                  :type :stream                                                                       
  •                                  :protocol :tcp)))                                                                   
  •     (unwind-protect (progn ,@body)
  •       (socket-close ,socket))))
  •  
  • (defmethod run ()                                                                                                     
  •   "Run the server, listening on the specified port and dispatching                                                   
  •   client requests."                                                                                                   
  •   (write-line "Starting server.")                                                                                     
  •   (with-socket server-socket                                                                                         
  •     (setf (sockopt-reuse-address server-socket) t)                                                                   
  •     (socket-bind server-socket *default-server-address* *default-server-port*)                                       
  •     (socket-listen server-socket *default-server-backlog*)                                                           
  •     (do ((client-socket (socket-accept server-socket) (socket-accept server-socket)))  ; ignore peer value           
  •         (nil)  ; infinite loop                                                                                       
  •       (write-line "New client")                                                                                       
  •       (let ((client-socket client-socket))                                                                           
  •         (make-thread (lambda () (handle-client client-socket)) :name "handle-client")))))                             
  •                                                                                                                      
  • (defun start ()                                                                                                       
  •   (setf myServer-thread (make-thread (lambda () (run)) :name "myServer")))                                           
  •                                                                                                                      
  • (defun stop ()                                                                                                       
  •   (let ((st myServer-thread))                                                                                         
  •     (cond                                                                                                             
  •       ((thread-alive-p st)                                                                                           
  •        (write-line "Server stopped.")                                                                                 
  •        (terminate-thread st))                                                                                         
  •       (t                                                                                                             
  •        (write-line "Server is not running.")                                                                         
  •        nil))))                                                                                                       
  •                                                                                                                      
  • ;; start the server                                                                                                   
  • (start)

    • ]]>         austin <![CDATA[Heap]]> http://blog.pettomato.com/?p=15 2005-10-18T20:16:48Z 2005-10-18T20:16:48Z A Heap is a really interesting data structure. It uses an array to hold it's elements, but the elements are ordered in such a way to form a binary tree. A heap can be used to sort an array efficiently, but other algorithms such as QuickSort are usually faster. A common use of a heap is to implement a Priority Queue. I use one in my implementation of A*.

    The Heap class that I wrote is an implementation of the Heap functions from the book "Introduction to Algorithms," by Cormen, Leiserson, and Rivest. I made some changes to make it work in Actionscript, and I implemented the key function in an iterative, rather than recursive, control structure (as was suggested in one of the exercises), because it runs a lot faster in Flash (about 30-60% faster on my machine).

    Note that I also use the cpp preprocessor with my code, which I described in this post. If you aren't using a preprocessor, then you need to inline the macros Left, Right, and Parent. It should be trivial in this case, because they are only used a few times.

    Actionscript
    1. // Macros for navigating the heap.
    2. #define Parent(x) ((x-1)>>1)
    3. #define Left(x) ((x<<1)+1)
    4. #define Right(x) ((x<<1)+2)
    5.  
    6. class Heap{
    7.  
    8.   function Heap(){}
    9.  
    10.   private static function Heapify(A:Array,i:Number,heap_size:Number):Void{
    11.     // Iterative version //
    12.  
    13.     var l,r,largest;
    14.     var isDone = false;
    15.  
    16.     while( !isDone ){
    17.  
    18.       /// Check if our children are larger than we.
    19.  
    20.       l = Left(i);
    21.       r = Right(i);
    22.  
    23.       if( l <heap_size && A[l]> A[i] ){
    24.         largest = l;
    25.       }
    26.       else{
    27.         largest = i;
    28.       }
    29.  
    30.       if( r <heap_size && A[r]> A[largest] ){
    31.         largest = r;
    32.       }
    33.  
    34.       if( largest != i ){
    35.  
    36.         var temp = A[i];
    37.         A[i] = A[largest];
    38.         A[largest] = temp;
    39.  
    40.         i = largest;
    41.       }
    42.       else{
    43.         isDone = true;
    44.       }
    45.     }
    46.   }
    47.  
    48.   public static function Build_Heap(A:Array):Void{
    49.     // Create a heap from an array A.
    50.     // Mutates the original array.
    51.  
    52.     var heap_size = A.length;
    53.     var i = (heap_size>> 1);
    54.  
    55.     while( i-- )
    56.       Heapify(A,i,A.length);
    57.   }
    58.  
    59.   public static function Heapsort(A:Array):Void{
    60.     // Sorts an array in place.
    61.  
    62.     Build_Heap(A);
    63.  
    64.     var heap_size = A.length;
    65.     var i = heap_size;
    66.     var temp;
    67.  
    68.     while( --i ){
    69.  
    70.       temp = A[i];
    71.       A[i] = A[0];
    72.       A[0] = temp;
    73.  
    74.       heap_size--;
    75.  
    76.       Heapify(A,0,heap_size);
    77.     }
    78.   }
    79.  
    80.   //// --- Priority Queue methods -------------------------
    81.  
    82.   public static function Extract_Max(A:Array){
    83.     // * A must already be a heap.
    84.     // 1. Remove and return the maximum value from a heap (priority queue).
    85.     // 2. Maintain the heap structure.
    86.  
    87.     var max = A.[0];
    88.     A[0] = A[A.length - 1];
    89.     A.pop();
    90.     Heapify(A,0,A.length);
    91.  
    92.     return max;
    93.   }
    94.  
    95.   public static function Insert(A:Array,key):Void{
    96.     // * A must already be a heap.
    97.     // Insert a new element into a heap (priority queue).
    98.  
    99.     var i = A.length;
    100.     A.length++;
    101.  
    102.     while(i> 0 && A[Parent(i)] <key){
    103.       A[i] = A[Parent(i)];
    104.       i = Parent(i);
    105.     }
    106.  
    107.     A[i] = key;
    108.   }
    109. }

    ]]>         austin <![CDATA[Game Design: Magnet]]> http://blog.pettomato.com/?p=14 2005-10-17T22:10:41Z 2005-10-17T22:10:41Z This is another idea we came up with for something that would be quick to produce. We originally planned to make it a downloadable game in Python, because we wanted to do a lot of things that wouldn't be feasible in Flash, but now with Flash 8 they are possible! There's even a little Flash demo at the bottom. Game Design Document here.

    ]]>