Bay 12 Games Forum

This seems like the most dwarfy ending there could ever be. I would be content with having the story end here.

"You currently do not have an ‘id’ cookie."

I think this is why:
Firefox options -> Privacy -> Tell web sites I do not want to be tracked

Google suggestions > Firefox spell check.

So I have a ton of completely random stuff that has nothing to do with my interests.

Google suggestions is the only thing I use for spell checking.

It will finish generating just after Dwarf Fortress 1.0 is released.

Quote from: Valid_Dark on March 01, 2012, 12:06:53 am

Quote from: Nadaka on February 29, 2012, 11:53:34 pm

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?

Correct, I probably need to clarify. It only seeks in the cardinal direction most directly towards the destination until that direction is blocked and it then stops and starts flooding, even if it can still travel in a straight line that brings it closer to the destination.

That's just how A* works. To my knowledge, it's the best algorithm that will always produce the shortest path in an efficient way.

I can change one variable that will kind of make it do what you describe. If I increase the heuristic multiplier (hMult) from 1 to 10, it will be more aggressive in testing nodes that are closer to the destination. In your example, it would be faster, since it would branch out into less nodes. However, consider this example:

XXXXXXXXXXXXXXXXXX
X          B     X
XXXXXXXXXXXXXXXX X
X              X X
X              X X
X              X X
XA               X
XXXXXXXXXXXXXXXXXX

With hMult = 1 and hMult = 10, it will probably test the same amount of nodes each. More importantly, if hMult is greater than 1, it may generate a suboptimal path. I suspect in this case it would start to move toward B, and then move back into the optimal route. This article has some excellent animations.

Here's an animation I made that shows my pathfinding algorithm at work. It's standard A*, which I believe is exactly the algorithm Dwarf Fortress uses. It runs on a seperate thread, too. Take that Toady One!

Alright, I've finished reading this entire thread.

Hi. I'm dreadmullet, adept C# programmer. I'm currently making my first roguelike using ncurses. It's going incredibly well (roguelike development is refreshingly easy), and I'll probably share some stuff about it soon.

If anyone needs help with C#, I'll try to help if I can.

Makes sense to me. It's just diagonal movement: move right one tile, move up one tile.