On algorithms and doing things the “right way”

April 9, 2012

(Warning: source code ahead!)

One of the things that is fun about writing games is figuring out how to “do things.”  That’s amazingly vague, I know.  A couple of examples of what I’m talking about:

  • How to create a random maze in a few seconds
  • How to calculate what a monster can “see” in a dungeon
  • Trace the trajectory of a projectile

And so on.   It’s fun, I swear!

In the past I would often tackle problems like these by sitting down with a pencil and paper and cooking up logical systems by drawing them, or just work them out conceptually as I walked to work.  In the case of random maze creation, that actually took several days of thought and experimentation.  And the system I came up with was quite complex.   I found out later, well after the game was finished, that there are many simple and elegant algorithms for maze creation available by a simple google search.

Similarly, when I needed to trace the path of a stone thrown from a catapult for this game:

http://empireforge.com/alchemist/index.html

I spent quite a bit of time coming up with a way to get only the integer points that the stone would pass through, so I could detect collisions with it along its path, etc.  I spent a lot of thought on it, but not a lot of time searching… so once again cooked up something fairly complex.  Boring detail: I took the start and end points, then calculated a midpoint.  Then repeated that for each new line segment created by using the calculated midpoint, recursively.   This was at least 5 years ago, before I learned some valuable coding lessons.  The “midpoint” method looked like this:


public class LinePointEnumerator {

	Point start;
	Point end;

	Vector points;
	String quadrant;
	int resolution;

	public LinePointEnumerator( Point start, Point end, int resolution ) {
		this.start = start;
		this.end = end;
		this.resolution = resolution;

		quadrant = "unset";

		if ( ( start.x > end.x ) && ( start.y > end.y ) ) {
			quadrant = "I";
		}
		if ( ( start.x < end.x ) && ( start.y > end.y ) ) {
			quadrant = "II";
		}
		if ( ( start.x < end.x ) && ( start.y < end.y ) ) {
			quadrant = "III";
		}
		if ( ( start.x > end.x ) && ( start.y < end.y ) ) {
			quadrant = "IV";
		}

		if ( quadrant.equals("unset") ) {
			if ( ( start.x == end.x ) && ( start.y > end.y ) ) {
				quadrant = "I";
			}
			if ( ( start.x == end.x ) && ( start.y < end.y ) ) {
				quadrant = "IV";
			}
			if ( ( start.x < end.x ) && ( start.y == end.y ) ) {
				quadrant = "III";
			}
			if ( ( start.x > end.x ) && ( start.y == end.y ) ) {
				quadrant = "IV";
			}
		}

		buildPoints();
	}
// ================================================
	public Vector getLinePoints() {
		return points;
	}
// ================================================
	public int getDistance( Point a, Point b ) {

		return (int) Math.sqrt(
				Math.pow( ( b.x - a.x ), 2 ) + Math.pow( ( b.y - a.y ), 2 )
				);
	}
// ================================================
	private void buildPoints( ) {
        points = new Vector();

        // add start point
		points.add( start );

		// the magic
		foldingAlgorithm( points );

		// the points probably need to be sorted!
		sortPoints( points );

        // add end point
        points.add( end );

    }
// ================================================
	private void foldingAlgorithm( Vector points ) {
		Vector lineSegments = new Vector();

		LineSegment currentSegment;
		LineSegment leftSegment;
		LineSegment rightSegment;
		Point midPoint;
		Point leftPoint;
		Point rightPoint;

		// initial segment
		lineSegments.add( new LineSegment( start, end ) );

		// pop a line segment
			// get its endpoints
				// get its midpoint
					// store all points in the point list, if not there already
					// create two new line segments with the endpoints and midpoint
						// if a line segment is longer than 2, store it back in the stack
						// repeat loop

		while ( lineSegments.size() > 0 ) {

			currentSegment = (LineSegment) lineSegments.get(0);
			lineSegments.remove(0);

			leftPoint = currentSegment.start;
			rightPoint = currentSegment.end;
			midPoint = new Point (
					( ( leftPoint.x + rightPoint.x ) / 2),
					( ( leftPoint.y + rightPoint.y ) / 2)
			);

			if ( !(points.contains( leftPoint )) ) { points.add( leftPoint ); }
			if ( !(points.contains( rightPoint )) ) { points.add( rightPoint ); }
			if ( !(points.contains( midPoint )) ) { points.add( midPoint ); }

			currentSegment = new LineSegment( leftPoint, midPoint );
			if ( getDistance( currentSegment.start, currentSegment.end ) > resolution ) { lineSegments.add( currentSegment ); }

			currentSegment = new LineSegment( midPoint, rightPoint );
			if ( getDistance( currentSegment.start, currentSegment.end ) > resolution ) { lineSegments.add( currentSegment ); }

		}

	}
// ================================================
	private void sortPoints( Vector points ) {
		// an implementation of selection sort ripped from the google

		for( int i = points.size() - 1; i >= 0; i-- )		// start at the end of the array
		{
			int highestIndex = i;				// (1) default value of the highest element index.
			for( int j = i; j >= 0; j--) 			// (2) loop from the end of unsorted zone to the
										//  beginning of the array.
			{
				Point pj = (Point) points.get(j);
				Point phi = (Point) points.get(highestIndex);

				if( isGreaterPoint( pj, phi )	)// compare current element to highest
				{ highestIndex = j;	 }	// if it's higher, it becomes the new highest
		}
		// swap the two values
		Point temp = (Point) points.get(i);
		Point phi2 = (Point) points.get(highestIndex);
		points.set( i, phi2 );
		points.set( highestIndex, temp );

		}

	}
// ================================================
	private boolean isGreaterPoint( Point a, Point b ) {

		if ( quadrant.equals("I") ) {
					if ( ( a.x < b.x ) || ( a.y < b.y ) ) {
						return true;
					}
		}
		else if ( quadrant.equals("II") ) {
					if ( ( a.x > b.x ) || ( a.y < b.y ) ) {
						return true;
					}
		}
		else if ( quadrant.equals("III") ) {
					if ( ( a.x > b.x ) || ( a.y > b.y ) ) {
						return true;
					}
		}
		else if ( quadrant.equals("IV") ) {
					if ( ( a.x < b.x ) || ( a.y > b.y ) ) {
						return true;
					}
		}

		return false;
	}
// ================================================

}

Still here?
Heh.

What was the point of that? I’m giving examples of the “wrong way” to solve problems.
One of the best ways to learn is by making mistakes! And I have learned!
In the next post, I will share some of the more recent problems and the elegant, simple algorithms I used to solve them.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: