Fun With Graham's Scan Hull Finding Algorithm
The Battle of Red Against Blue
by Jason Plumb, Deric Waters, and Chad Sauvain
 

Table of Contents:

Introduction
This program provies an exciting and enjoyable demonstration of the Graham's scan convex hull-finding algorithm.  As the "how-to-play" section below indicates, the "realm" of each team is represented by a convex hull.  This program demonstrates how the convex-hull-finding algorithm can be applied to real-world scenerios.  In calculating the convex hull, the program also utilizes the QuickSort algorithm as an added bonus!

How to play
    Gameplay is quite simple.  Each game beings with two teams:  Red and Blue.  Each of the two players chooses a corresponding team.  The Red team always has the (dis)advantage of going first. The goal of the game is to expand one's territory (or convex hull) to encompass the most area and to attack the opposing team.  The end of the game is not calculated by the program and is left to the discretion of the players.
    At the start of each game, each team begins with a small territory composed of 3 points in a semi-random location.  Players should begin by setting up new base camps and expanding their territory.  Players may only set up new camps within a  limited distance from the existing camps.  When the cursor is placed over an existing point, a green circle will indicate the maximum distance of movement.
    On each move, there is a random chance of something excting happening.  It is possible that a new camp discovers useful resources which allow the player to move an extra turn.  However, it is also possible that harsh environmental conditions prohibit the establishment of a new base camp (or the equivalent of a lost turn).  The probability of each event is not listed here (that would spoil the fun...check the source code if you want to ruin it!).  One may notice, though, that Java's randomness is not necessarily so "random"...see for yourself!
    Attacks can be made in one of two ways:  Intersecting directly into the opposing team's hull (preferred method) or "swallowing" the opposing team's camp with one's own hull border.  Note that is is possible to overlap hull borders (fences) without attacking, provided that there are no camps from the opposing team within your hull (and vice versa).  Once an attack is attempted, the program uses a simple method (based on the number of points in each team and a random factor) to determine if the attack was successful.  If the attacker is successful, the opposing team will lose repeatedly lose camps until there is no longer an overlapping of camps/hulls.  The specifics of how this works will not be explained here so that the players may enjoy blasting away at one another without emphasis on strategy.....:)
    A new game may be started by pressing the "New Game" button or by switching to another scenerio.  There are 3 possible scenerios to enjoy.

Scenerio 1:  Ancient Countryside
In the "Ancient Countryside" scenerio, the ancient lords of the land are out to conquer the most territory and avenge the death of their ancestors. You strive to ride across the countryside to meet your foe in head-to-head combat!  They must pay for what they have done to your people...and pay dearly!  Lord Red has fought many "heated battles" and is truly a foe to fear.  On the other hand, Lord Blue is the cunning underdog whose skills should never be underestimated.

Scenerio 2:  Conquer Lubbock!!!
In the "Conquer Lubbock" scenerio, the Texas A&M Aggies (Blue team) are out to sieze the territory of our beloved Texas Tech Raiders (Red team).  It's a battle of rivals at its finest (but this is no pathetic football game)!!!  See once and for all who is truly the champion of Texas.  Or, if you're feeling up to the real challenge, download the source code, modify it to support multi-player internet action, and challenge our foes to meet us again on our turf!

Scenerio 3:  Brain Microbes Attack
Because this project required so much mental power, it was only appropriate that one of the scenerios incorporate the vast space that is the human brain.  It doesn't actually matter what you want the scenerio to be (if you haven't caught on by now) :), but it could represent different contradictory thoughts that plague one's mind from time to time.  Or, it could represent some nasty bacteria fighting over an unsuspecting person's gray matter.  Better still...it's "right-handers" vs. "left-handers"....WHICH TEAM WILL BE VICTORIOUS?

How it all works
As indicated above, this program centers around the Graham's scan convex-hull finding algorithm.  In order for this algorithm to work properly, each point in each team's point array must be sorted by order of angle (referenced to the minimum point marked by the letters "HQ").  In order to accomplish this, the program implements the QuickSort algorithm to increase speed.

Also, there are two types of "attacks" which can occur:  direct intersection into the opposing team's hull or enclosing an opponent's  point with one's own hull.  Thus, there are two functions to check for both of these conditions.  In the first case, the program checks to see if the new point would lie on a hull if it were added to the opposing team's point array.  If not, then an intersection has occured.  In the second case, the program must loop to check if any of the opposing team's points cause an intersection with one's own hull.

To reduce screen flicker which normally occurs during the paint method, an update method was implemented along with off-screen graphics buffering.  A global graphics object is used by all functions except for the paint method which simply copies the buffered graphic to the screen.  The result is a much smoother screen refresh.

The algorithm which handles the "chance" of a successful attack is quite simple (and should probably be improved to make the game more interesting). If the result of the following equation is larger than 100, a successful attack has occured:

100*(A/(A+V)) + Random(100)
where A represents the number of "attacker" camps and V represents the number of "victim" camps.  As the number of attacker camps becomes larger than the number of victim camps, the attacker gains a higher chance of winning any given battle.
 

This file may be found at http://chimera.acs.ttu.edu/~z9d58/cs2464/hull/hull.html
The source.