More on algorithms

April 10, 2012

In my last post, which was a bit of an eye-chart, I alluded to the pain involved in doing things the wrong way.  Lessons learned, was the point.

Here are some of the fruits of those lessons!  In my current game project, “Forge of Legends,” I have needed to do each of the following:

  • Find a path through a dungeon
  • Determine what a player or monster can see
  • Get all the integer points within an area

To be honest, I actually already had an idea how to tackle the first one.  I knew of the existence of the “A* Pathfinding Algorithm” but had had only limited success implementing it.  Instead of a ghetto attempt, I went to google and found a really nice walkthrough of the algorithm here:

http://www.policyalmanac.org/games/aStarTutorial.htm

I got to experience that unique joy only a game developer can understand — when you code something and watch it work, and are amazed at how cool it is.  I traced paths all through my test dungeons, watching the algorithm find the shortest paths and avoid dead-ends.  Neat.

The next two problems in need of a solution I had come across before, when working on a now-defunct life simulator.  How to determine what an entity “sees,” including taking into account things like obstructions.

It turns out the key to this problem is also the perfect solution to the problem I showed ugly monster code for in the last post.  A ray-tracing algorithm.  Namely, “Bresenham’s Line Algorithm.”  My guess is that anyone who has worked much with programming games is well aware of what this is, but I was not.

If I treat an entity as a light source, I can then use the algorithm to trace rays out from the source, “illuminating” an area — but also “seeing” into an area.  It is also affected by obstructions just the way I’d want.

Here’s a little graphic that shows what it does — getting back integer coordinates interpreted from two points on a grid:

There is a bit more to it, though.  This shows one “ray,” which is just a set of coordinates from point A to point B.  Perfects for looking down a line at something.  But, if I am an entity or light source, I’m looking in all directions, of course.  So, I have my entity’s location as a starting point for any number of lines that radiate out, but how do I select all those needed destination points for drawing a line?

I was tempted to try to figure out something complicated and… probably broken.  But, a little more research yielded information on the “Midpoint Circle Algorithm.”  With that, which you can visualize with the following image, I was able to build a circle of destination points and trace lines to each one.

And bam!  It works.  And it’s so fun to watch.  My entities can find paths, and can see!

To see all these algorithms in action, head over to the Forge of Legends site and view the developer journal entries for “formations” and “line of sight.”

Here’s a link:

http://empireforge.com/fol/devJournalOverview.html

(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.