From: Charles <Charles@92bb83a3-7c8f-8a45-bc97-515c4e399668>
Date: Mon, 19 Apr 2010 05:09:51 +0000 (+0000)
Subject: New test map: maze.cfmap
X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fcarfire;a=commitdiff_plain;h=8bd8893e7f7516c76558ad7262e9f9350f5192b9;hp=1368c1af3d7a4a12b0b0577dbe3edbfd254e2d04

New test map: maze.cfmap
New classes:
- Timer is a basic event scheduler.
- IPriorityQueue, BinaryHeap is a basic heap... not sure why .Net doesn't provide one.
- PathFinder lets your search the map for paths.
- Script is a WIP.

git-svn-id: https://bd85.net/svn/cs3505_group@107 92bb83a3-7c8f-8a45-bc97-515c4e399668
---

diff --git a/CarFire/CarFire/CarFire/CarFire.csproj b/CarFire/CarFire/CarFire/CarFire.csproj
index fd92b88..2edc12d 100644
--- a/CarFire/CarFire/CarFire/CarFire.csproj
+++ b/CarFire/CarFire/CarFire/CarFire.csproj
@@ -84,6 +84,7 @@
     </Reference>
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="PathFinder.cs" />
     <Compile Include="ChatInfo.cs" />
     <Compile Include="Display.cs" />
     <Compile Include="Game.cs" />
@@ -95,9 +96,12 @@
     <Compile Include="MapReader.cs" />
     <Compile Include="NetworkManager.cs" />
     <Compile Include="Parse.cs" />
+    <Compile Include="PriorityQueue.cs" />
     <Compile Include="Projectile.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="Program.cs" />
+    <Compile Include="Script.cs" />
+    <Compile Include="Timer.cs" />
     <Compile Include="XnaGame.cs" />
     <Compile Include="ScreenManager.cs" />
   </ItemGroup>
diff --git a/CarFire/CarFire/CarFire/Content/Content.contentproj b/CarFire/CarFire/CarFire/Content/Content.contentproj
index e53208f..818dbdd 100644
--- a/CarFire/CarFire/CarFire/Content/Content.contentproj
+++ b/CarFire/CarFire/CarFire/Content/Content.contentproj
@@ -136,6 +136,13 @@
       <Processor>TextureProcessor</Processor>
     </Compile>
   </ItemGroup>
+  <ItemGroup>
+    <Compile Include="Maps\maze.cfmap">
+      <Name>maze</Name>
+      <Importer>MapImporter</Importer>
+      <Processor>PassThroughProcessor</Processor>
+    </Compile>
+  </ItemGroup>
   <Import Project="$(MSBuildExtensionsPath)\Microsoft\XNA Game Studio\v3.0\Microsoft.Xna.GameStudio.ContentPipeline.targets" />
   <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
        Other similar extension points exist, see Microsoft.Common.targets.
diff --git a/CarFire/CarFire/CarFire/Content/Maps/maze.cfmap b/CarFire/CarFire/CarFire/Content/Maps/maze.cfmap
new file mode 100644
index 0000000..a7d220d
--- /dev/null
+++ b/CarFire/CarFire/CarFire/Content/Maps/maze.cfmap
@@ -0,0 +1,33 @@
+[metadata]
+	author = Chaz McGarvey
+	levelname = Maze
+	type = Campaign
+	dimensions = [80,21]
+	tileset = FuturisticBuilding
+	numplayers = 1
+
+; okay, so it's more like a spiral...
+[maptable]
++------------------------------------------------------------------------------+
+|   +                                                                          |
+| 1 +                     +                                                    |
+|   +                     +                                                    |
+|   +   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++   |
+|   +   +                                         +                        +   |
+|   +   +                                         +                        +   |
+|   +   +                                                                  +   |
+|   +   +   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++   +   |
+|   +   +        +           +             +                           +   +   |
+|   +   +        +           +             +                ++++++++   +   +   |
+|   +   +              +         +    +        +++++++        +++      +   +   |
+|   +   +              +         +    +              +                 +   +   |
+|   +   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++   +   |
+|   +                                                                      +   |
+|   +                                                                      +   |
+|   +                                                                      +   |
+|   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++   |
+|                                                                              |
+|                                                                 +            |
++------------------------------------------------------------------------------+
+
+; vi:ft=dosini
diff --git a/CarFire/CarFire/CarFire/Content/Maps/stable.cfmap b/CarFire/CarFire/CarFire/Content/Maps/stable.cfmap
index fc7f2c3..fe5a7e2 100644
--- a/CarFire/CarFire/CarFire/Content/Maps/stable.cfmap
+++ b/CarFire/CarFire/CarFire/Content/Maps/stable.cfmap
@@ -1,7 +1,4 @@
-; Comments can be made with a semicolon as the first character of a line.
-; Blank lines are also ignored.
-; This is my sandbox level I will use to test against while building the
-; level-loading code.
+; This map should load and function just fine.
 
 [metadata]
 	author = Chaz McGarvey
@@ -22,15 +19,15 @@
 |                  |------------------------------------------                 |
 | 4                |                                       |                   |
 |                  |                                       |                   |
-+-------------+----+                                       |                   |
-|             |                                            |                   |
-|             |                                            |                   |
-|             |                                            |                   |
-|             |          \ @ # $ % ^ & * ( )               |                   |
-|     +-------+                                            |                   |
-|                                                          |                   |
-|                                                                              |
-|                                                                              |
++-------------+----+                                       |      \       /    |
+|             |                                            |       \     /     |
+|             |                                            |        \   /      |
+|             |                                            |         \ /       |
+|             |          \ @ # $ % ^ & * ( )               |          |        |
+|     +-------+                                            |         / \       |
+|                                                          |        /   \      |
+|                                                                  /     \     |
+|                                                                 /       \    |
 |                                                                              |
 +------------------------------------------------------------------------------+
 
diff --git a/CarFire/CarFire/CarFire/PathFinder.cs b/CarFire/CarFire/CarFire/PathFinder.cs
new file mode 100644
index 0000000..8b627ac
--- /dev/null
+++ b/CarFire/CarFire/CarFire/PathFinder.cs
@@ -0,0 +1,277 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Diagnostics;
+using Microsoft.Xna.Framework;
+
+namespace CarFire
+{
+    /// <summary>
+    /// A class to navigate from here to there through a grid of
+    /// open and closed cells.
+    /// </summary>
+    public class PathFinder
+    {
+        #region Public Types
+
+        /// <summary>
+        /// The heuristic function should return some value representing
+        /// the distance between two points.  A common approach is to
+        /// return the manhattan distance.
+        /// </summary>
+        /// <param name="a">A point.</param>
+        /// <param name="b">The endpoint.</param>
+        /// <returns>The heuristic.</returns>
+        public delegate int Heuristic(Point a, Point b);
+
+        /// <summary>
+        /// The cost function should take two points representing two
+        /// adjacent cells and return a cost measure of how expensive it
+        /// is to move from one cell to the other.
+        /// </summary>
+        /// <param name="a">A point.</param>
+        /// <param name="b">Another point.</param>
+        /// <returns>The cost.</returns>
+        public delegate int CostFunction(Point a, Point b);
+
+        #endregion
+
+
+        #region Public Methods
+
+        /// <summary>
+        /// Construct a path finder with a grid.  The grid is a matrix
+        /// of boolean values, true meaning the cell is walkable and false
+        /// meaning the cell is closed.
+        /// </summary>
+        /// <param name="grid">The grid to find paths on.</param>
+        public PathFinder(bool[,] grid)
+        {
+            Debug.Assert(grid != null);
+
+            mGrid = grid;
+            mGridWidth = mGrid.GetUpperBound(0) + 1;
+            mGridHeight = mGrid.GetUpperBound(1) + 1;
+        }
+
+
+        /// <summary>
+        /// The A* algorithm for finding the best path through a grid of cells.
+        /// The manhattan distance heuristic and a simple distance-based cost
+        /// function will be used.
+        /// </summary>
+        /// <param name="start">The cell to start at.</param>
+        /// <param name="finish">The desired destination.</param>
+        /// <returns>A list of points representing the path through the grid,
+        /// ends points not included, or null if no path could be found.</return>
+        public List<Point> GetPath(Point start, Point finish)
+        {
+            return GetPath(start, finish, GetManhattanDistance, GetCost);
+        }
+
+        /// <summary>
+        /// The A* algorithm for finding the best path through a grid of cells.
+        /// A simple distance-based cost function will be used.
+        /// </summary>
+        /// <param name="start">The cell to start at.</param>
+        /// <param name="finish">The desired destination.</param>
+        /// <param name="heuristic">The heuristic function.</param>
+        /// <returns>A list of points representing the path through the grid,
+        /// ends points not included, or null if no path could be found.</return>
+        public List<Point> GetPath(Point start, Point finish, Heuristic heuristic)
+        {
+            return GetPath(start, finish, heuristic, GetCost);
+        }
+
+        /// <summary>
+        /// The A* algorithm for finding the best path through a grid of cells.
+        /// The manhattan distance heuristic will be used.
+        /// </summary>
+        /// <param name="start">The cell to start at.</param>
+        /// <param name="finish">The desired destination.</param>
+        /// <param name="costFunction">The cost function</param>
+        /// <returns>A list of points representing the path through the grid,
+        /// ends points not included, or null if no path could be found.</return>
+        public List<Point> GetPath(Point start, Point finish, CostFunction costFunction)
+        {
+            return GetPath(start, finish, GetManhattanDistance, costFunction);
+        }
+
+        /// <summary>
+        /// The A* algorithm for finding the best path through a grid of cells.
+        /// </summary>
+        /// <param name="start">The cell to start at.</param>
+        /// <param name="finish">The desired destination.</param>
+        /// <param name="heuristic">The heuristic function.</param>
+        /// <param name="costFunction">The cost function.</param>
+        /// <returns>A list of points representing the path through the grid,
+        /// ends points not included, or null if no path could be found.</return>
+        public List<Point> GetPath(Point start, Point finish, Heuristic heuristic, CostFunction costFunction)
+        {
+            mFringe = new BinaryHeap<Cell>();
+            mCells = new Cell[mGridWidth, mGridHeight];
+
+            Cell startCell = new Cell(start, 0, GetManhattanDistance(start, finish));
+            mFringe.Add(startCell);
+            mCells[start.X, start.Y] = startCell;
+            while (mFringe.Count > 0)
+            {
+                Cell cell = mFringe.GetNext();
+                cell.IsOpen = false;
+
+                if (cell.Point == finish)
+                {
+                    List<Point> list = new List<Point>();
+
+                    cell = cell.Parent;
+                    while (cell.Point != start)
+                    {
+                        list.Add(cell.Point);
+                        cell = cell.Parent;
+                    }
+
+                    list.Reverse();
+                    return list;
+                }
+
+                List<Point> neighbors = new List<Point>(8);
+                neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y - 1));
+                neighbors.Add(new Point(cell.Point.X + 0, cell.Point.Y - 1));
+                neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y - 1));
+                neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y + 0));
+                neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 0));
+                neighbors.Add(new Point(cell.Point.X - 1, cell.Point.Y + 1));
+                neighbors.Add(new Point(cell.Point.X + 0, cell.Point.Y + 1));
+                neighbors.Add(new Point(cell.Point.X + 1, cell.Point.Y + 1));
+                foreach (Point point in neighbors)
+                {
+                    Cell inQueue = mCells[point.X, point.Y];
+
+                    if (0 <= point.X && point.X < mGridWidth && 0 <= point.Y && point.Y < mGridHeight &&
+                        mGrid[point.X, point.Y])
+                    {
+                        int cost = cell.G + GetCost(cell.Point, point);
+
+                        if (inQueue == null)
+                        {
+                            Cell neighbor = new Cell(point, cost, GetManhattanDistance(point, finish), cell);
+                            mFringe.Add(neighbor);
+                            mCells[point.X, point.Y] = neighbor;
+                        }
+                        else if (inQueue.IsOpen && cost < inQueue.G)
+                        {
+                            inQueue.G = cost;
+                            inQueue.Parent = cell;
+                            mFringe.Promote(inQueue);
+                        }
+                    }
+                }
+            }
+
+            return null;
+        }
+
+
+        /// <summary>
+        /// Get the manhattan distance between two points.  This is a simple but
+        /// effective and commonly-used heuristic.
+        /// </summary>
+        /// <param name="a">A point.</param>
+        /// <param name="b">Another point.</param>
+        /// <returns>The manhattan distance.</returns>
+        public static int GetManhattanDistance(Point a, Point b)
+        {
+            int w = b.X - a.X;
+            int h = b.Y - a.Y;
+            if (w < 0) w = -w;
+            if (h < 0) h = -h;
+            return w + h;
+        }
+
+        /// <summary>
+        /// Get the cost to travel from one point to another.  This is a simple
+        /// cost function based purely on distance.  On a square grid, diagonal
+        /// cells are further away than adjacent cells; therefore, adjacent moves
+        /// are favored.
+        /// </summary>
+        /// <param name="a">A point.</param>
+        /// <param name="b">Another point.</param>
+        /// <returns>The cost.</returns>
+        public static int GetCost(Point a, Point b)
+        {
+            if (a.X != b.X && a.Y != b.Y) return 14;
+            return 10;
+        }
+
+        #endregion
+
+
+        #region Private Types
+
+        class Cell : IComparable<Cell>
+        {
+            public Point Point;
+            public Cell Parent;
+            public bool IsOpen;
+
+            public int G
+            {
+                get { return mG; }
+                set { mG = value; mF = mG + mH; }
+            }
+
+            public int H
+            {
+                get { return mH; }
+                set { mH = value; mF = mG + mH; }
+            }
+
+            public int F { get { return mF; } }
+
+
+            public Cell(Point point, int g, int h)
+            {
+                Point = point;
+                IsOpen = true;
+                mG = g;
+                mH = h;
+                mF = g + h;
+            }
+
+            public Cell(Point point, int g, int h, Cell parent)
+            {
+                Point = point;
+                Parent = parent;
+                IsOpen = true;
+                mG = g;
+                mH = h;
+                mF = g + h;
+            }
+
+            public int CompareTo(Cell other)
+            {
+                return F - other.F;
+            }
+
+
+            int mG;
+            int mH;
+            int mF;
+        }
+
+        #endregion
+
+
+        #region Private Variables
+
+        bool[,] mGrid;
+        int mGridWidth;
+        int mGridHeight;
+
+        IPriorityQueue<Cell> mFringe;
+        Cell[,] mCells;
+
+        #endregion
+    }
+}
diff --git a/CarFire/CarFire/CarFire/PriorityQueue.cs b/CarFire/CarFire/CarFire/PriorityQueue.cs
new file mode 100644
index 0000000..df60ec0
--- /dev/null
+++ b/CarFire/CarFire/CarFire/PriorityQueue.cs
@@ -0,0 +1,455 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Diagnostics;
+
+namespace CarFire
+{
+    /// <summary>
+    /// Why .NET doesn't already provide such a basic data structure
+    /// as a priority queue is anybody's best guess.  This is an interface
+    /// for a queue class which treats the items themselves as keys,
+    /// the relative priorities being determined by a comparison between
+    /// them.
+    /// </summary>
+    /// <typeparam name="T">The type of item to queue.  This must be a
+    /// comparable class.</typeparam>
+    public interface IPriorityQueue<T> where T : IComparable<T>
+    {
+        /// <summary>
+        /// Add a new item to the priority queue.
+        /// </summary>
+        /// <param name="item">The item to add.</param>
+        void Add(T item);
+
+        /// <summary>
+        /// Get the item with the highest priority, removing it
+        /// from the priority queue.
+        /// </summary>
+        /// <returns>The highest priority item.</returns>
+        T GetNext();
+
+        /// <summary>
+        /// Get the item with the highest priority, but keep it in
+        /// the priority queue.
+        /// </summary>
+        /// <returns>The highest priority item.</returns>
+        T Peek();
+
+        /// <summary>
+        /// Notify the priority queue that the priority of a certain item
+        /// has improved.  If the items is not in the queue, it is added.
+        /// Do not use this to demote items.  The internal structures will
+        /// be reconfigured in order to ensure correct priority queueing.
+        /// </summary>
+        /// <param name="item">The item that improved.</param>
+        void Promote(T item);
+
+        /// <summary>
+        /// Remove all the items from the priority queue.
+        /// </summary>
+        void Clear();
+
+        /// <summary>
+        /// Get the number of items in the priority queue.
+        /// </summary>
+        int Count { get; }
+    }
+
+
+    /// <summary>
+    /// A minimum binary heap implementing a priority queue.
+    /// </summary>
+    /// <typeparam name="T">The type of items to load in the heap.</typeparam>
+    public class BinaryHeap<T> : IPriorityQueue<T> where T : IComparable<T>
+    {
+        #region Public Properties
+
+        /// <summary>
+        /// Get the number of items in the binary heap.
+        /// </summary>
+        public int Count { get { return mSize; } }
+
+        #endregion
+
+
+        #region Public Methods
+
+        /// <summary>
+        /// Construct a binary heap.
+        /// </summary>
+        public BinaryHeap()
+        {
+            mList.Add(default(T));
+        }
+
+        /// <summary>
+        /// Construct a binary heap with a predetermined capacity.
+        /// The heap is dynamically-sized, but it will be more
+        /// efficient if you set the capacity to the number of items
+        /// you plan to add.
+        /// </summary>
+        /// <param name="capacity">The capacity of the heap.</param>
+        public BinaryHeap(int capacity)
+        {
+            mList.Capacity = capacity;
+            mList.Add(default(T));
+        }
+
+
+        /// <summary>
+        /// Add a new item to the heap.
+        /// </summary>
+        /// <param name="item">The item to add.</param>
+        public void Add(T item)
+        {
+            mList.Add(item);
+            mSize++;
+            PercolateUp(mSize);
+        }
+
+
+        /// <summary>
+        /// Get the item with the lowest value, removing it from the heap.
+        /// </summary>
+        /// <returns>The highest priority item.</returns>
+        public T GetNext()
+        {
+            Debug.Assert(mSize > 0);
+
+            T next = mList[1];
+
+            mList[1] = mList[mSize];
+            PercolateDown(1);
+            mList.RemoveAt(mSize);
+            mSize--;
+
+            return next;
+        }
+
+        /// <summary>
+        /// Get the item with the lowest value, but keep it in the heap.
+        /// </summary>
+        /// <returns>The highest priority item.</returns>
+        public T Peek()
+        {
+            Debug.Assert(mSize > 0);
+
+            return mList[1];
+        }
+
+
+        /// <summary>
+        /// Decrease the value of one of the items in the heap.  If the
+        /// item is not already in the heap, it is added.
+        /// </summary>
+        /// <param name="item">The item to change.</param>
+        public void Promote(T item)
+        {
+            for (int i = 1; i < mList.Count; i++)
+            {
+                if (item.Equals(mList[i]))
+                {
+                    mList[i] = item;
+                    if (PercolateUp(i) == i) PercolateDown(i);
+                    return;
+                }
+            }
+
+            Add(item);
+        }
+
+
+        /// <summary>
+        /// Remove all the items from the heap.
+        /// </summary>
+        public void Clear()
+        {
+            mList.Clear();
+            mSize = 0;
+        }
+
+        #endregion
+
+
+        #region Private Methods
+
+        int PercolateUp(int index)
+        {
+            T temp = mList[index];
+
+            for (int parent; index > 1; index = parent)
+            {
+                parent = index / 2;
+                if (temp.CompareTo(mList[parent]) < 0) mList[index] = mList[parent];
+                else break;
+            }
+
+            mList[index] = temp;
+            return index;
+        }
+
+        int PercolateDown(int index)
+        {
+            T temp = mList[index];
+
+            for (int child; index * 2 <= mSize; index = child)
+            {
+                child = index * 2;
+                if (child != mSize && mList[child].CompareTo(mList[child + 1]) > 0) child++;
+                if (temp.CompareTo(mList[child]) > 0) mList[index] = mList[child];
+                else break;
+            }
+
+            mList[index] = temp;
+            return index;
+        }
+
+        #endregion
+
+
+        #region Private Variables
+
+        List<T> mList = new List<T>();
+        int mSize = 0;
+
+        #endregion
+    }
+
+
+    /// <summary>
+    /// The binary heap might be too slow for shortest path algorithms,
+    /// so here is a fibonacci heap which should perform better.
+    /// </summary>
+    /// <typeparam name="T">The type of items to load in the heap.</typeparam>
+    public class FibonacciHeap<T> : IPriorityQueue<T> where T : IComparable<T>
+    {
+        #region Public Properties
+
+        /// <summary>
+        /// Get the number of items in the fibonacci heap.
+        /// </summary>
+        public int Count { get { return mCount; } }
+
+        #endregion
+
+
+        #region Public Methods
+
+        /// <summary>
+        /// Construct an empty fibonacci heap.
+        /// </summary>
+        public FibonacciHeap()
+        {
+            mList = new LinkedList<NodeInfo>();
+            mLookup = new Dictionary<T, LinkedListNode<NodeInfo>>();
+        }
+
+
+        /// <summary>
+        /// Add a new item to the heap.
+        /// </summary>
+        /// <param name="item">The item to add.</param>
+        public void Add(T item)
+        {
+            LinkedListNode<NodeInfo> node = mList.AddLast(new NodeInfo(item));
+            if (mMin == null || item.CompareTo(mMin.Value.Item) < 0) mMin = node;
+
+            mLookup[item] = node;
+            mCount++;
+        }
+
+
+        /// <summary>
+        /// Get the item with the lowest value, removing it from the heap.
+        /// </summary>
+        /// <returns>The highest priority item.</returns>
+        public T GetNext()
+        {
+            LinkedListNode<NodeInfo> temp = mMin;
+            mList.Remove(mMin);
+            mMin = null;
+
+            LinkedListNode<NodeInfo> node = temp.Value.Children.First;
+            while (node != null)
+            {
+                Cut(node);
+                node = temp.Value.Children.First;
+            }
+            Consolidate();
+
+            mLookup.Remove(temp.Value.Item);
+            mCount--;
+            return temp.Value.Item;
+        }
+
+        /// <summary>
+        /// Get the item with the lowest value, but keep it in the heap.
+        /// </summary>
+        /// <returns>The highest priority item.</returns>
+        public T Peek()
+        {
+            return mMin.Value.Item;
+        }
+
+
+        /// <summary>
+        /// Decrease the value of one of the items in the heap.  If the
+        /// item is not already in the heap, it is added.
+        /// </summary>
+        /// <param name="item">The item to change.</param>
+        public void Promote(T item)
+        {
+            LinkedListNode<NodeInfo> node;
+            if (mLookup.TryGetValue(item, out node))
+            {
+                LinkedListNode<NodeInfo> parent = node.Value.Parent;
+                if (parent != null)
+                {
+                    if (node.Value.Item.CompareTo(parent.Value.Item) < 0)
+                    {
+                        Cut(node);
+                        CascadingCut(parent);
+                        if (node.Value.Item.CompareTo(mMin.Value.Item) < 0) mMin = node;
+                    }
+                }
+                else if (node.Value.Item.CompareTo(mMin.Value.Item) < 0) mMin = node;
+            }
+            else
+            {
+                Add(item);
+            }
+        }
+
+
+        /// <summary>
+        /// Remove all the items from the heap.
+        /// </summary>
+        public void Clear()
+        {
+            mList.Clear();
+            mMin = null;
+            mCount = 0;
+            mLookup.Clear();
+        }
+
+        #endregion
+
+
+        #region Private Methods
+
+        // Builds up the binomial trees.  More importantly, it sets the min
+        // pointeer and ensures that no root binomial tree has the same degree.
+        void Consolidate()
+        {
+            LinkedListNode<NodeInfo>[] degree = new LinkedListNode<NodeInfo>[64];
+
+            for (LinkedListNode<NodeInfo> node = mList.First; node != null;)
+            {
+                LinkedListNode<NodeInfo> match = degree[node.Value.Degree];
+                if (match == null)
+                {
+                    if (mMin == null || node.Value.Item.CompareTo(mMin.Value.Item) <= 0) mMin = node;
+                    degree[node.Value.Degree] = node;
+                    
+                    node = node.Next;
+                }
+                else
+                {
+                    degree[node.Value.Degree] = null;
+
+                    if (node.Value.Item.CompareTo(match.Value.Item) < 0)
+                    {
+                        Link(match, node);
+                    }
+                    else
+                    {
+                        mList.Remove(match);
+                        mList.AddAfter(node, match);
+                        Link(node, match);
+                        node = match;
+                    }
+                }
+            }
+        }
+
+        // Removes child from whatever list it is in and makes it a child
+        // of parent.  This is for building up the binomial trees.
+        void Link(LinkedListNode<NodeInfo> child, LinkedListNode<NodeInfo> parent)
+        {
+            child.List.Remove(child);
+            parent.Value.Children.AddLast(child);
+            child.Value.Parent = parent;
+            child.Value.IsMarked = false;
+        }
+
+        // Removes node from whatever list it is in and makes it a root binomial
+        // tree.
+        void Cut(LinkedListNode<NodeInfo> node)
+        {
+            node.List.Remove(node);
+            mList.AddLast(node);
+            node.Value.Parent = null;
+            node.Value.IsMarked = false;
+        }
+
+        // Cuts each node that is marked, following the ancestry until it finds
+        // an unmarked ancestor (in which case it marks it) or a root node.
+        void CascadingCut(LinkedListNode<NodeInfo> node)
+        {
+            while (node.Value.Parent != null)
+            {
+                if (node.Value.IsMarked)
+                {
+                    Cut(node);
+                    node = node.Value.Parent;
+                }
+                else
+                {
+                    node.Value.IsMarked = true;
+                    break;
+                }
+            }
+        }
+
+        #endregion
+
+
+        #region Private Types
+
+        // This container class has the information we need to form
+        // a tree out of linked lists.
+        class NodeInfo
+        {
+            public LinkedListNode<NodeInfo> Parent;
+            public LinkedList<NodeInfo> Children = new LinkedList<NodeInfo>();
+            public bool IsMarked = false;
+
+            public int Degree { get { return Children.Count; } }
+
+            public T Item { get { return mItem; } }
+
+            public NodeInfo(T item)
+            {
+                mItem = item;
+            }
+
+            T mItem;
+        }
+
+        #endregion
+
+
+        #region Private Variables
+
+        LinkedList<NodeInfo> mList;
+        LinkedListNode<NodeInfo> mMin;
+        int mCount;
+
+        // To speed up promotions, we need a fast lookup for nodes.
+        Dictionary<T, LinkedListNode<NodeInfo>> mLookup;
+
+        #endregion
+    }
+}
diff --git a/CarFire/CarFire/CarFire/Script.cs b/CarFire/CarFire/CarFire/Script.cs
new file mode 100644
index 0000000..5ae6908
--- /dev/null
+++ b/CarFire/CarFire/CarFire/Script.cs
@@ -0,0 +1,50 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace CarFire
+{
+    public class Script
+    {
+        #region Public Types
+
+        public enum Status
+        {
+            Waiting,
+            Done,
+        }
+
+        public enum Function
+        {
+            Create,
+            Has,
+            Play,
+            Remove,
+            UseUp,
+            Wait,
+        }
+
+        #endregion
+
+
+        #region Public Methods
+
+        public Script(string code)
+        {
+        }
+
+        public Status Run()
+        {
+            return Status.Done;
+        }
+
+        public Status Evaluate(out bool value)
+        {
+            value = true;
+            return Status.Done;
+        }
+
+        #endregion
+    }
+}
diff --git a/CarFire/CarFire/CarFire/Timer.cs b/CarFire/CarFire/CarFire/Timer.cs
new file mode 100644
index 0000000..01dfd77
--- /dev/null
+++ b/CarFire/CarFire/CarFire/Timer.cs
@@ -0,0 +1,183 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace CarFire
+{
+    /// <summary>
+    /// A simple timer class.  I'm not sure why .NET or at least
+    /// XNA doesn't already have one of these.
+    /// </summary>
+    public class Timer<T> : IComparable<Timer<T>> where T : IComparable<T>
+    {
+        #region Public Properties
+
+        /// <summary>
+        /// Get and set the expiration time.  If the time is already set
+        /// and the timer is registered, you cannot push the expiration time
+        /// further back, but you can decrease it.
+        /// </summary>
+        public T Time
+        {
+            get
+            {
+                return mTime;
+            }
+            set
+            {
+                if (mTime.CompareTo(value) > 0)
+                {
+                    mTime = value;
+                    gTimers.Promote(this);
+                }
+            }
+        }
+
+        /// <summary>
+        /// Get the current absolute time, accurate up until
+        /// the last time Timer.FireAll was called.
+        /// </summary>
+        public static T Now { get { return gNow; } }
+
+        /// <summary>
+        /// Get and set the events that will be called when the
+        /// timer expires.
+        /// </summary>
+        public event ExpiredEventHandler Expired;
+
+        /// <summary>
+        /// Get and set a user contextual object.
+        /// </summary>
+        public object Context;
+
+        #endregion
+
+
+        #region Public Types
+
+        /// <summary>
+        /// The type for an event handler for timers that expire.
+        /// </summary>
+        /// <param name="timer">The timer that expired.</param>
+        public delegate void ExpiredEventHandler(Timer<T> timer);
+
+        #endregion
+
+
+        #region Public Methods
+
+        /// <summary>
+        /// Construct a timer with an absolute time (in seconds)
+        /// when the timer should expire.
+        /// </summary>
+        /// <param name="time">Absolute time, in seconds.</param>
+        public Timer(T time)
+        {
+            mTime = time;
+            gTimers.Add(this);
+        }
+
+        /// <summary>
+        /// Construct a timer with an absolute time (in seconds)
+        /// when the timer should expire, and an event handler.
+        /// </summary>
+        /// <param name="time">Absolute time, in seconds.</param>
+        /// <param name="expired">An event handler.</param>
+        public Timer(T time, ExpiredEventHandler expired)
+        {
+            mTime = time;
+            Expired += expired;
+            gTimers.Add(this);
+        }
+
+        /// <summary>
+        /// Construct a timer with an absolute time (in seconds)
+        /// when the timer should expire, and a contextual object.
+        /// </summary>
+        /// <param name="time">Absolute time, in seconds.</param>
+        /// <param name="context">A user contextual object.</param>
+        public Timer(T time, object context)
+        {
+            mTime = time;
+            Context = context;
+            gTimers.Add(this);
+        }
+
+        /// <summary>
+        /// Construct a timer with an absolute time (in seconds)
+        /// when the timer should expire, an event handler, and a
+        /// contextual object.
+        /// </summary>
+        /// <param name="time">Absolute time, in seconds.</param>
+        /// <param name="expired">An event handler.</param>
+        /// <param name="context">A user contextual object.</param>
+        public Timer(T time, ExpiredEventHandler expired, object context)
+        {
+            mTime = time;
+            Expired += expired;
+            Context = context;
+            gTimers.Add(this);
+        }
+
+
+        /// <summary>
+        /// Fire all outstanding timers which should be expired
+        /// before a certain time.
+        /// </summary>
+        /// <param name="time">Absolute time, in seconds.</param>
+        public static void FireExpired(T time)
+        {
+            gNow = time;
+
+            while (gTimers.Count > 0)
+            {
+                Timer<T> timer = gTimers.Peek();
+                if (timer.Time.CompareTo(Now) <= 0)
+                {
+                    if (timer.Expired != null) timer.Expired(timer);
+                    if (timer.Time.CompareTo(Now) <= 0) gTimers.GetNext();
+                }
+                else
+                {
+                    break;
+                }
+            }
+        }
+
+
+        /// <summary>
+        /// Unregister all registered timers without firing any events.
+        /// </summary>
+        public static void Clear()
+        {
+            gTimers.Clear();
+        }
+
+
+        /// <summary>
+        /// Compare a timer with another, based on the expiration
+        /// times of both timers.
+        /// </summary>
+        /// <param name="other">The timer to compare against.</param>
+        /// <returns>A negative value if this timer is less than the
+        /// other, a positive value if this timer is greater than the
+        /// other, or zero if they are the same.</returns>
+        public int CompareTo(Timer<T> other)
+        {
+            return Time.CompareTo(other.Time);
+        }
+
+        #endregion
+
+
+        #region Private Variables
+
+        T mTime;
+
+        static IPriorityQueue<Timer<T>> gTimers = new BinaryHeap<Timer<T>>(10);
+        static T gNow;
+
+        #endregion
+    }
+}