Shortest Path

January 5, 2009

Hello world!

Filed under: non-technical — dharabor @ 12:51

Hi! Welcome to little corner of the web.

I decided to start this blog for a few reasons. Firstly, I’m really interested in AI and secondly, in recent times I’ve become fascinated with pathfinding techniques and in particular their application to games.

If you’re an outsider to this field you might be under the impression that pathfinding is a solved problem. While it’s true that the classical A* algorithm has provided us with a nice method for efficiently finding shortest paths in a graph it does not address many of the bigger problems we encounter in modern video games. For example, group movement and formation-based pathfinding are both open problems which require attention to many variables: do all the agents in a group move at the same speed? are they all the same shape? can they all traverse the same kind of terrain? should the group stay together or is dispersion OK? 

Other problems involve finding paths in apriori unknown environments (for example, pathfinding with fog-of-war turned on), dynamic environments with changing terrain, and real-time environments where our units must respond in a (usually very small) timeframe. When we increase the complexity of the prototypical pathfinding problem in these ways we often also increase the amount of computation that is required to produce a solution. This calls for different techniques to be employed of which A* is often only a small part of. 

I hope to discuss these problems and other related issues on this blog; more for myself I think than for any particular audience. If this happens to be useful to others however, then so much the better!


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

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

Blog at

%d bloggers like this: