### My Lisp Game is Done!

Monday, August 9th, 2010I just checked in the ‘final’ code to github. Check out my first program in lisp!

I just checked in the ‘final’ code to github. Check out my first program in lisp!

So after my first (almost) 30 days of learning lisp, I have a playable game. The gameplay is a cross between tower defense and orbient. You control a planet-base (the core) in the center of the screen. This core comes equipped with one weapon, the core-blast. Enemies are generated at the edge of the screen, in the spawning-belt, and are drawn toward your core by gravity. When enemies collide with the core, the core looses life. Life is displayed as a green outline around the core and when your core is out of life, it explodes. When an enemy dies, which happens either by colliding with your core, being hit by a blast or being thrown past the spawning belt, you gain resources. Resources are displayed by purple boxes in the upper left. You can spend these resources on extra cores and weapons in the weapon-store, which is displayed in the upper right. Below is a screen shot of the game in action.

A lot of work still remains to be done, but I hit the 30 day deadline with this first draft. Luckily, the contest hosts have extended the due date to August 10th. By then I plan to fix some bugs, add more weapons, enemies, a game-over screen and do some optimization. I feel accomplished after learning lisp, though I know I’ve only seen the tip of the iceberg and have found my new favorite language. To the hosts of the competition, thanks! You guys have made me a better programer.

The source to the game is here and you can download and build the game as you please. Send me a message with your thoughts on my game or my code!

A friend and I have decided to write a game in LISP in 30 days. The game will be entered in the 2010 lisp games expo.

My good friend Aaron Maus is a lisper, and wanted to make a game. I’ve never programmed in lisp. We have 30 days to program a game for this contest. Super fun.

Let’s pretend you have an application that lets users create shapes to be used in a physics simulation and that the user must click on the screen to set the vertices of the shape. Many physics engines only support convex polygons, or shapes that don’t have inlets, bites, or coves, basically shapes that don’t have inward facing edges. With this limitation we have to be able to restrict [read as "guide"] the user to make only convex polygons. For this we are going to need an algorithm that takes an unordered set of points and finds the convex hull that encloses those points. This way the user can click and add points at random, if desired, and your program will keep track of what points create a convex polygon, while the others are thrown away [or dealt with however you see fit].

**The Graham Scan Algorithm** is a process of ordering a random set of points and then calculating jumps to the points in that set that constitute a convex polygon. In this algorithm there are three steps. First is to find a corner point, usually the topmost, leftmost point in the set. The second step is to order all other points by the polar angle between the corner point and the point in question. The last step is to traverse the set, taking each proceeding subset of three points (n, n-1, n-2) to determine whether the angle made by these three points is a left turn, right turn, or a straight line. If the turn made is our desired turn [which is usually left - but in Flash it's right, due to the flipped y-axis] then we add that point to the convex hull. If the turn is not our desired turn, we get rid of that point and move on.

Here is an example that shows first the data set drawn from point to point. Each successive line gets progressively whiter. In the second step we find the corner point, order the other points and then show the outer polygon.

Here’s the code for the class:

/**

* Use this class freely - 2009 blog.efnx.com

*/

package

{

import flash.geom.Point;

public class GrahamScan extends Object

{

/**

* The Graham scan is a method of computing the convex hull of a finite set of points

* in the plane with time complexity O(n log n). It is named after Ronald Graham, who

* published the original algorithm in 1972. The algorithm finds all vertices of

* the convex hull ordered along its boundary. It may also be easily modified to report

* all input points that lie on the boundary of their convex hull.

*/

public function GrahamScan()

{

super();

}

/**

* Returns a convex hull given an unordered array of points.

*/

public static function convexHull(data:Array):Array

{

return findHull( order(data) );

}

/**

* Orders an array of points counterclockwise.

*/

public static function order(data:Array):Array

{

trace("GrahamScan::order()");

// first run through all the points and find the upper left [lower left]

var p:Point = data[0];

var n:int = data.length;

for (var i:int = 1; i < n; i++)

{

//trace(" p:",p,"d:",data[i]);

if(data[i].y < p.y)

{

//trace(" d.y < p.y / d is new p.");

p = data[i];

}

else if(data[i].y == p.y && data[i].x < p.x)

{

//trace(" d.y == p.y, d.x < p.x / d is new p.");

p = data[i];

}

}

// next find all the cotangents of the angles made by the point P and the

// other points

var sorted :Array = new Array();

// we need arrays for positive and negative values, because Array.sort

// will put sort the negatives backwards.

var pos :Array = new Array();

var neg :Array = new Array();

// add points back in order

for (i = 0; i < n; i++)

{

var a :Number = data[i].x - p.x;

var b :Number = data[i].y - p.y;

var cot :Number = b/a;

if(cot < 0)

neg.push({point:data[i], cotangent:cot});

else

pos.push({point:data[i], cotangent:cot});

}

// sort the arrays

pos.sortOn("cotangent", Array.NUMERIC | Array.DESCENDING);

neg.sortOn("cotangent", Array.NUMERIC | Array.DESCENDING);

sorted = neg.concat(pos);

var ordered :Array = new Array();

ordered.push(p);

for (i = 0; i < n; i++)

{

if(p == sorted[i].point)

continue;

ordered.push(sorted[i].point)

}

return ordered;

}

/**

* Given an array of points ordered counterclockwise, findHull will

* filter the points and return an array containing the vertices of a

* convex polygon that envelopes those points.

*/

public static function findHull(data:Array):Array

{

trace("GrahamScan::findHull()");

var n :int = data.length;

var hull:Array = new Array();

hull.push(data[0]); // add the pivot

hull.push(data[1]); // makes first vector

for (var i:int = 2; i < n; i++)

{

while(direction(hull[hull.length - 2], hull[hull.length - 1], data[i]) >= 0)

hull.pop();

hull.push(data[i]);

}

return hull;

}

/**

*

*/

private static function direction(p1:Point, p2:Point, p3:Point):Number

{

// > 0 is right turn

// == 0 is collinear

// < 0 is left turn

// we only want right turns, usually we want right turns, but

// flash's grid is flipped on y.

return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);

}

}

}

* Use this class freely - 2009 blog.efnx.com

*/

package

{

import flash.geom.Point;

public class GrahamScan extends Object

{

/**

* The Graham scan is a method of computing the convex hull of a finite set of points

* in the plane with time complexity O(n log n). It is named after Ronald Graham, who

* published the original algorithm in 1972. The algorithm finds all vertices of

* the convex hull ordered along its boundary. It may also be easily modified to report

* all input points that lie on the boundary of their convex hull.

*/

public function GrahamScan()

{

super();

}

/**

* Returns a convex hull given an unordered array of points.

*/

public static function convexHull(data:Array):Array

{

return findHull( order(data) );

}

/**

* Orders an array of points counterclockwise.

*/

public static function order(data:Array):Array

{

trace("GrahamScan::order()");

// first run through all the points and find the upper left [lower left]

var p:Point = data[0];

var n:int = data.length;

for (var i:int = 1; i < n; i++)

{

//trace(" p:",p,"d:",data[i]);

if(data[i].y < p.y)

{

//trace(" d.y < p.y / d is new p.");

p = data[i];

}

else if(data[i].y == p.y && data[i].x < p.x)

{

//trace(" d.y == p.y, d.x < p.x / d is new p.");

p = data[i];

}

}

// next find all the cotangents of the angles made by the point P and the

// other points

var sorted :Array = new Array();

// we need arrays for positive and negative values, because Array.sort

// will put sort the negatives backwards.

var pos :Array = new Array();

var neg :Array = new Array();

// add points back in order

for (i = 0; i < n; i++)

{

var a :Number = data[i].x - p.x;

var b :Number = data[i].y - p.y;

var cot :Number = b/a;

if(cot < 0)

neg.push({point:data[i], cotangent:cot});

else

pos.push({point:data[i], cotangent:cot});

}

// sort the arrays

pos.sortOn("cotangent", Array.NUMERIC | Array.DESCENDING);

neg.sortOn("cotangent", Array.NUMERIC | Array.DESCENDING);

sorted = neg.concat(pos);

var ordered :Array = new Array();

ordered.push(p);

for (i = 0; i < n; i++)

{

if(p == sorted[i].point)

continue;

ordered.push(sorted[i].point)

}

return ordered;

}

/**

* Given an array of points ordered counterclockwise, findHull will

* filter the points and return an array containing the vertices of a

* convex polygon that envelopes those points.

*/

public static function findHull(data:Array):Array

{

trace("GrahamScan::findHull()");

var n :int = data.length;

var hull:Array = new Array();

hull.push(data[0]); // add the pivot

hull.push(data[1]); // makes first vector

for (var i:int = 2; i < n; i++)

{

while(direction(hull[hull.length - 2], hull[hull.length - 1], data[i]) >= 0)

hull.pop();

hull.push(data[i]);

}

return hull;

}

/**

*

*/

private static function direction(p1:Point, p2:Point, p3:Point):Number

{

// > 0 is right turn

// == 0 is collinear

// < 0 is left turn

// we only want right turns, usually we want right turns, but

// flash's grid is flipped on y.

return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);

}

}

}

I’ve been working on another game lately, it’s called Machinista – it’s a game where you control motors in a 2D physics simulation. The entire thing is built around Box2D, which is a great physics system. Last night I worked on using Brownian Bridge fractals for explosions – check it out! Use keys W, A, S, D and shift+click to control the tank and make explosions, respectively.