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:

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: