Want to know the shortest path from one point to another? If you're making a roguelike then you probably do. You could use Dijkstra's algorithm, but there's an alternative that finds the result much faster. It's the A*, or A Star, algorithm. It's a lot like Dijkstra's algorithm except instead of checking the neighbors of all the currently visited cells, it just checks the neighbor of the visited cell that's the closest to the target. Of course if you already know which one is closest then you don't need to pathfind. Instead you just estimate which one is closest. Even if your estimates are a bit off, you'll still find the shortest path in much less time.
Here's an ActionScript implementation.
This algorithm needs some explanation since it was made by mathematicians - who generally suck at naming variables. That's why there's a g, h, and f cost. The H cost is the heuristic or estimated cost from a point to the end point. The G cost is the actual cost from the start point to a point. There's no need to estimate that because you only calculate this on points that you've visited. The F cost is the total of the two. By only checking the neighbors of the point with the lowest F cost, you end up - in the best case - only checking the points that are in the shortest path. You can change the getGCost and getHCost methods to cause different behavior. Maybe some points cost more to travel through? Maybe moving diagonal cost more than moving in the cardinal directions? Try it and see what happens.
The checkEnding boolean is because in my game people sometimes can pathfind to walls and obstacles that block movement.
It's mostly used for pathfinding but can also be used for carving rivers, roads, or caves during worldgen. You could also use it to tell where someone is probably going to go - useful for placing traps I suppose. Have you seen any interesting uses for this algorithm?
No comments:
Post a Comment