Monday, December 5, 2011

Pathfinding Options

So this will probably be my most 'half-baked' article so far, mainly because it's on a topic I haven't fully fleshed out. At some point I may come back and add my conclusions, but for now, I am typing about the journey as I am taking it, so sorry if I steer people down the wrong path.

I am working on a side project that involves moving pieces around a rather complex game board. I am in serious need of path finding, which happens be a topic we didn't really cover in my college courses (among them a course specifically on game design, which to me feels like a pretty big miss. Then again, I helped write the course structure, so I share some of the blame for that.)

So far, my search has turned up a number of algorithms, all deigned to handle different levels of complexity. It does, however, give me (and you) a great place to state, so I will just post all the links so far and allow you to research yourself.


A*
Wiki
Tutorial (this is where I am starting, but it may not be enough to handle 'teleporting' squares)

Breadth First Search
Wiki

Dijkstra's
Wiki

Good luck, and happy path finding!