Sorry your browser is not supported!

Hey guys,

I just recently made a program that implements Dijkstra's algorithm for finding the shortest path in a provided graph. What I have is a 3d representation of a graph with the cost of each edge being the distance from the nodes it connects to. If anyone knows anything about Dijkstra's algorithm it is that it exhausts all possibilities before coming to the best solution. Although my program works really fast with a graph of 9 nodes and 16 edges (I think...), this function can get costly quick if there are about 10 enemies and about 30 or 40 nodes to traverse to(and even more edges!).

Anyways, my question is that I want to implement the A* algorithm but not too sure what to use for the heuristic value. I know some people use their H value to be the direct distance from that node to the destination node. However, depending on how the graph is setup, this is not always the best way. Although it will be able to find a path to the destination, it won’t always be the shortest path.

If I couldn't find a way to implement A* accurately, then I was considering optimizing Dijkstra's algorithm. Maybe I can have a queue that will perform the shortest path function maybe 3 or 4 times for each game cycle. Another thought is to have a two-tiered path finding system. If the agent needs to travel across the map, then it can traverse through a macro sized graph and once it gets closer to its destination, then traverse through a micro sized graph.

What do you guys think?

A* should find the shortest possible path as long as the heuristic is admissible, meaning that it never overestimates the distance to the goal.

So you should be fine using the direct distance. If you are on a grid and you can't move diagonally, you could use the 'Manhattan distance', which would just be deltaX + deltaY. That way you can avoid using sqrt().

Can you tell us more about your map? I assume you're using grid-based A* - is the map more like a maze, or a city, or are obstactles more spread out?

Well looking at this example I quickly drew up, green being our starting point and red being the destination. We see that the connection from green to yellow and yellow to red is the shortest path. But, at a heuristic standpoint, the blue node that is next to green is closer to the destination if you took an absolute distance from the destination. Now I cant exactly say what the edge cost is but the neighboring nodes of green could be the exact same F value.

Thoughts?

That's how A* is supposed to work. It's a lot like Dijkstra's, it just uses the heuristic to refine the search a little bit. It will still open some unnecessary nodes, but fewer than if there were no heuristic.

yeah i was able to implement the A* algorithm and it works alright. I haven't been able to thoroughly test it but it seems like every so often it doesnt quite give me the optimal path. But it would only be like 1 off and to be honest I have a method in my head of how im going to make the final paths look nicer while having minimal edges. Essentially A* should be much quicker than Dijkstra's right?

Yes.

Good luck .