By popular request, I will reveal you how we do pathfinding in Driftmoon. This might be interesting to you if you're making your own game and want to implement pathfinding, and also if you're making a Driftmoon mod. Pathfinding in Driftmoon has gone through a couple of iterations already, so I'll start at the beginning.
First of all, we use the A* search algorithm. That was pretty much the only thing that went right from the start. A* is easy to implement, and there are libraries available for it. All I needed to do was create some amount of location nodes, tell the algorithm where I want to go, and where I start, and that's it.
So how do we make the nodes? Driftmoon is a top-down game, so I figured we could make a grid. All of the examples I saw at the time were of grids. An automatically generated grid would be good, because modders would never have to worry about the pathfinding, it would just work. So I made a grid, and looped through all the points, and connected the ones which didn't have walls in between them. To make sure our AI could navigate small doors or cracks in dungeon walls, I had to make the grid pretty small. So I ended up with grids that amounted to about 10000*10000 points in them. You might spot the problem with that.
While A* is obviously a fast algorithm, it can't possibly cope with that amount of points in the graph. When my maps started getting bigger my AI churned about a minute looking for a new path. I had to reduce the amount of nodes in the pathfinding grid. So I tried it algorithmically. Make the grid sections bigger where there's nothing but open space, and smaller where there are gaps and doors. It worked, but it started taking minutes to create the grid when the map was saved in the editor. And I couldn't make the algorithm optimal, it still produced millions of nodes.
After all that, the AI works like this: It knows where it is (here), and where it wants to go (eg. go talk to the player, or go kill the player). For both the start and the end points, it looks for a way to the nearest pathfinding nodes. And then it looks for the optimal path between those nodes. Here are some of the optimizations it uses: If it sees the end point straight away, it doesn't bother with pathfinding at all. If it sees a clear path to a pathfinding node one step ahead, it will skip any unnecessary pathfinding points. I've tuned the A* algorithm to prefer routes with no dynamic obstacles, but the AI goes through the obstacles like a bulldozer if it can't find an alternate route. From the above you probably reasoned, that a lot of the times the AI simply has to decide whether there is a clear path from A to B. If your making your own game, the most straight forward way to do that might be to use the raytracer in your physics library, but in Driftmoon, we're using our own spatial hash maps.
An important matter to realize is that inside dungeons, often there simply isn't a path from where you are to where you want to go. In this case, the A* algorithm hammers through the entire set of pathfinding nodes, and this is obviously the slowest possible case. We need the ability to quickly check if we ever could get from A to B, or is it completely impossible. This is done by marking each pathfinding node with an area number. If the area numbers are different between the start and the end nodes, that means they are on areas that are not accessible to each other. So now the nonexisting path case is the fastest one, we just check whether the area numbers match. I'm setting the area numbers simply by doing a flood fill for each node when we start the level.
Now I was left with a pretty snappy pathfinding, but as I added more monsters and townspeople, I started noticing that it was bogging down the framerate when the AI wanted to do pathfinding. The problem was that when the player moved, a lot of the monsters might decide to start looking for a new path at the same time. So I implemented a pathfinding queue with priority numbers. The monsters nearest to the player get their pathfinding done first, and monsters very far from the player might not get pathfinding at all, or might get it less than the others. And if the monster's pathfinding wasn't complete yet, it fakes it by just going on a direct path.
So that's how pathfinding in Driftmoon works. I've spent many months making it. My advice to people making their own games is this, skip pathfinding altogether. Make the monsters zombies, robots, or green slimes that don't need pathfinding, and you've saved yourself many weeks of development time! 
The MindTrek jury writes:
Driftmoon [..] Competes in very difficult genre which has the most demanding but also most loyal users. Fascinating story offers possibility to prevail.
How right they are, roleplaying games are extremely demanding to make. When starting work on Driftmoon I had no idea it would take years to finish it. But now that it's nearly complete, I'm glad we decided to take the challenge! 
So go on to the MindTrek page and check the other nominees!
Update: DIY Gamer has posted an article on the competition.
In our last Driftmoon alpha, there was little reason to use bows in combat, since (1) the arrows were limited, (2) you got the bow pretty late in the game, and (3) most of the monsters were far easier to defeat using melee weapons. We're changing that right now, bows will be much more useful from now on! I thought about a hundred very complex ways to make that happen, but finally I realized it's not nuclear physics. We simply needs some monsters that are easier to defeat using melee weapons such as swords, and some monsters that are easier to defeat using ranged attacks, such as bows.
We're now in the middle of weighing different alternatives that would make it convenient to react to the new varying enemy types. For example, now that I frequently want to change my weapon set, a button that changes between two weapon sets would come in handy. I could reserve the right mouse button for this purpose.
Another problem we've been thinking about is that some of the attack skills, such as the Retreat skill, should actually work outside combat. But you can only activate the skill while in combat because the skill buttons only show up when you're fighting someone!
So I'm thinking that we could turn the current quick item slots into two-purpose slots, meaning you could fill them with skills as well as items. We'd get rid of the current skills list that only appears in combat. I think this opens up a lot of possibilities for modding, with the player being able to activate skills out of combat. Since skills are just scripts, modders could make skills that make the player invisible before combat, or skills that make the player change into a werewolf shape - all without requiring the player to carry special items to do that.
The only problem that I see with the multipurpose slots, is that you'd get 10 slots less! Any ideas? Don't need more than 10 slots? Go Warcraft and add as many slots as the screen edges can take (but you'd loose visibility?)? Make the weapon set button, the right mouse button perhaps, switch to another set of 10 slots?
The code is only about 12000 lines, but I didn't have time to put it into separate files at the time. Unlike Bikez 2, which I released earlier, Wazzal is mostly in English! Bear in mind, that it is still one of my earlier projects, so I'm releasing the code on one condition: If you're ever thinking about hiring me, don't judge my coding skills by this.
PS. We're making more enemy types to Driftmoon. And let me tell you, it's hard work training new monsters! They ate through my hat, and one of them nearly got away with Anne, but I've managed to capture a good number of them into Driftmoon! I'll tell you more about the little critters later.
Jgprof in the forum wanted to know a bit about Driftmoon's background. I thought the question interesting enough to write a short post about.
"What language is Driftmoon written in, and what libraries are you using? How many LOC is it and how many hours have you spent on it?"
The Driftmoon game engine consists of about a 100 000 lines of C++, including the editor tools. It's a lot of code on one person's plate, I find it a great exercise for my memory. There are a lot of libraries we use. Ogg Vorbis, the sound decoding library. DirectX for graphics. Box2D for physics. And of course the standard JPEG and PNG libraries. Zlib. The actual game is written mostly in the Driftmoon scripting language, but I don't know how many lines of code there would be. Thousands in any case.
A quick calculation shows that we must have spent about 5000 hours for the game and the engine in the last six years. We've worked on the actual game content only for the last two years, after I had to drop the Cormoon project and adapted the engine to Driftmoon. The tough part at the moment is getting enough hours to work on Driftmoon, as we have two lovely little distractions running (and crawling) around the house and I have my day job. But we've managed pretty well, I think.
"Simlarly for the content: how much time goes in to creating a level as beautiful as the ones in the Alpha release?"
It's hard to say how long a good level takes to make, as we always have to work on new additions to the engine and the overall experience. And there's a lot of testing that we have to do. The upcoming monastery area and the adjoining crypt took about two calendar months to complete. Our current rate seems to be about one hour of gameplay per month of work, as we don't have to touch the engine so much and can finally focus more on the content side of Driftmoon. Making the content is very hard work, since we're committed to keeping each hour of gameplay fun! We're certainly hoping to keep that up for the rest of the development time.
Get our newsletter!