RTS pathfinding

Newbie & Debugging Questions
#21

A* is “optimal” in that with a valid heuristic it will visit the same or less than Dijkstra’s algorithm and still find the shortest path. With a invalid heuristic you don’t get the shortest path guarantee, but you still generally visit even less nodes. Perhaps on a pathological graph this would not be the case, but that does not apply here.

#22

@princec

A* state space evaluation can be quite subtle. Its best to try and mentally compare Greedy search (ignore the distance you have traveled so far) to A*.

Consider moving from A at the top of a map, to B at the bottom in these two case.

  1. with a round obstacle in the middle
  2. with a bucket (concave) shaped object (with the opening aiming a A) in the middle

With greedy search,

  1. the states expanded go straight toward B, hit the obstacle and slide over the round surface until in LOS of B.
  2. the states expanded go straight toward B, enter the opening of the bucket, hit the bottom of the bucket, and then fill the bucket, until pouring out over the side into LOS of B.

With A*

  1. the states expanded go straight toward B, and hit the obstacle. So we now have a line of explored states from A to the obstacle. Then, every state adjacent to that line is expanded as the heuristic is compromised. So the line fattens at the rate of the surface area of the explored state until the end part of it is in LOS of B. It becomes a bit like a breadth first search at that point (Argh! the complexity!).
  2. Like 1. but much worse

So greedy search is always my default position over A*. Heuristic compromises can be quite subtle. So if you are on a grid world with diagonal moves and you use the Euclidean distance, bam! you got problems because the path exploration can’t follow such a direct route as the heuristic expects.

Yeah direct LOS paths are best, that’s equivalent to greedy search in a discretized world. It doesn’t have problems with using euclidean distance on grid worlds either.

#23

All a bit of a brain melt isn’t it. Though on the other hand, a sub-optimal search is possibly a little more realistic if you think about what the little gidrah can actually see when it’s on the ground. If your AI is spread out per-tick then what happens is they take longer to start moving, because they had to think a bit harder about how to get there. I like that :slight_smile:

Cas :slight_smile:

#24

I remember the very old game Outpost 2 offering improved pathfinding as a researchable ingame upgrade. xD