Forge of Legends update

June 19, 2012

A quick note that I’ve updated the site with new info on combat.  There’s a new dev journal video, as well as some new content in the combat section.


May 4, 2012

No, I’m not dead (yet).

I invite you to read this:

which is one of the best posts about Indie Game development I’ve seen!

And… there.  Proof I’m not dead.  Or something

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:

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:

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

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";

// ================================================
	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);

			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?

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.

The Wheel of Time

March 26, 2012

Yes, I’m speaking about the beyond-epic-length series of books.

I’d say that its readers fall into three categories:

1)  Never heard of it.

2)  Read some of the books, lost patience, and gave up.

3)  Avid fan of the series.  Think it’s great.

Before I say a bit more about each of these categories, let me state that for several years I would have fallen into category “2.”  That has changed, but more later.

For those who have never heard of it, imagine a series begun in 1990 and spanning 14 books (the 14th still in the works).  Most of these books are epics on their own, with quite a few of them exceeding 1,000 pages in paperback form.  At least five of them are bestsellers, though I suspect the number is higher.

Why so many books and so many pages?  I think there are some out there who would accuse Robert Jordan of cashing in — just writing books for the recurring income.  For my part, I’d say it is more likely that once he had built his fantasy world, he couldn’t help but keep returning to keep it alive.  As for the style of the books, it varies quite a bit.  I would describe the first 10 books as “moments of interesting stuff spread thinly through lots of less-interesting stuff.”  There are literally whole chapters in the middle books of people glaring at each other.  Just.  Glaring.

I started reading the books when I was a wee lad, just starting out in college in 1992 or so.  I found the first several books interesting, though admittedly my taste in books has changed quite a bit from those days.  By the late 90s, I simply couldn’t go on.  I put down book 7 unfinished and did not return for more than a decade.  Hence, I fell into category 2.

I’m in a different category now.  What changed?

Well, there are ways to approach that question, and some of them just don’t sound nice.  So, let me make nice first: Robert Jordan was an author with vision, talent, and a unique style.  He did lots of things right — some of them even brilliant.  Furthermore, what I’ve learned of the man leads me to respect him a great deal.  He lived a good life, and touched many people.   As for the Wheel of Time, he brought a world to life and put interesting characters in it.  Characters that people really identify with, in many cases.  I could go on, but I think my point is clear.  He was a good man, and a good writer in many ways.

So, having explained why I stopped reading the series, and stated my views on Robert Jordan as an author, I’ll (slowly) get to “what changed.”

I read other books by other authors, of course, and over the years began to identify a few who appealed to my tastes — authors whose stories were not chores to read (sadly, some of the first 10 Wheel of Time books were chores to get through at times).  One of these authors is Brandon Sanderson.

I no longer recall which of Sanderson’s works I read first, but I do know that I’ve read everything he has written that I can get my paws on.   I enjoy his books, and I think they are well done.  There is little, if any, of his work that is boring or tedious.  That’s a good thing.   I would stop short of labeling him the “best author ever.”  There are very, very few I would say that about (I’m looking at you, Tolkien).

What does he have to do with the Wheel of Time?  Anyone in category 3 above would already know.  Robert Jordan passed away before he could complete the Wheel of Time series.  I’ve read a bit about how he passed, and while sad, the circumstances are rather heart-warming.  From what I can tell, he died peacefully among family and loved ones after a long battle with his health.  Since it was not something sudden like a car accident or heart-attack, plans had been made to finish the series.  And so, after a “selection process” involving Jordan’s widow, Sanderson was approached to finish the series and has written books 12 and 13.  He has also written book 14, the final book, though it is still in pre-production editing and such.

When I heard this had happened, I knew I had to read these new books.  But I’m not the kind of person to pick up at book 8 after more than 10 years and try to jump back in… no.  I started over at book 1, of course.  Over the course of several months, I must have read around 10,000 pages of Robert Jordan, finally arriving at “The Gathering Storm,” Brandon Sanderson’s entry into the series.  I felt I deserved a t-shirt, at least, for the effort.

I expected the “new books” to be better.  No slight meant against Jordan, of course, but I simply knew going in that Sanderson’s writing style was more to my liking.  But “expected it to be better” does not move a person to write a 1,000 word blog post (the first post on the site, at that).

Sanderson breathed real life into the characters — without changing who and what they were.  Every time I sat down to read the book I was amazed — and what he did with Rand’s character (a central character in the series) was beautiful.  I was beside myself after reading the book, enough to re-read portions of the final chapters.  It was that good.

I am nearly finished with book 13 now, also by Sanderson.  It has been a joy to read, as well.  It’s going to be tough waiting for 14, and even tougher to finish it.  Because then it will be over.  20 years and somewhere near 13,000 pages.  I know one thing — Sanderson will finish it beautifully.

And there it is.  If you have the stamina, read the whole series.  For my part, I say it’s worth it if you like fantasy books.   Might be worth checking out some of Sanderson’s other works first, though.  I would recommend the standalone novel “Warbreaker,” for that.