Hello im new here. Ive been interested in A* and decided to make one. Since i dont know well any programming language such as C, C#, C++ or Java i use warcraft3 script to make my tests of the algorithms, the logic should be the same. Here are 2 screenshots, the small dots are the checked grids/nodes and the glowing ones represent the path found. Im happy it found a path tat isnt too bad. Took 2 days to make it work. But i cant seem to get the predictation right. And i dont know where to look or read to fix it so the path is more like the red lines drawn. I guess people here have experience and give me tip on wat might be wrong here, like if this is a typical of a wrong heuristic or something?

The paths look correct to me.

The problem is that you're working with a fixed grid. When you're at one grid location, you can only move in one of 8 directions: N, S, E, W, NW, NE, SE, SW, so you can't move at "non-standard" angles like you've drawn in red.

Edit: having said that, if you can modify the unit's movement code, you could do some checks so that if a straight line from node N to node N+m is clear, the unit could skip the nodes in between and just walk in a straight line between N and N+m.

So, look at the image below:



If you start at node #1, you can see that a straight line from #1 to #7 is clear of obstructions, but from #1 to #8 is not. So you can make the unit walk in a straight line to #7. Then from #7 to #11 is clear, so you walk in a straight line to #11 and so on.

This is, however, a separate step to actually finding the path in the first place.

i read somewhere and tested a bit. As i suspected, the problem was in the heuristic, i didnt think heuristic change behaviour this big. I tested 2 heuristics, and found the Pythagoras to give the best result, just tat it is slower. And Warcraft3 have an operation limit. So i wonder now if its a good idea to not find the path instantly, but searching it overtime, eventho the unit may start to move wrong but tat will be fixed over time. And the time step is small too so wat do you think?


This heuristic follow the line more correctly:




[Edited by - madlios on February 16, 2009 1:28:58 AM]

There is no difference as far as I can tell in the paths produced. Your examples are certainly different in the second case however. Why don't you try your revised algorithm using the same examples as in the original two pictures?

I can think of no reason why the heuristic would affect the quality of the path provided both are admissible.

the thing with A* as i know is that the heuristic change its behaviour greatly. Here are the examples of the 2 original tests.

oh its not exact same, i forgot i reduced the density of the path

Quote: Original post by madlios
the thing with A* as i know is that the heuristic change its behaviour greatly. Here are the examples of the 2 original tests.

oh its not exact same, i forgot i reduced the density of the path

Yes, the heuristic can change the path, but even in the first example, the generated path is still "optimal" (in that it would take the same number of moves for the unit to reach as the one with your updated heuristic). As long as your heuristic follows the rules of A*, you'll always get the optimal path, it's just in these cases where there's more than one "optimal" path, you can affect which one is chosen.

There's nothing wrong with the paths you've shown. They are the shortest in the GRAPH that A* searches. What they aren't is shortest in Euclidean space. Unfortunately, the topology of a graph representing a 4- or 8-connected grid is not the same as that of Euclidean space.

What to do?

One answer, from robotics: Instead of working with a grid, work with the VISIBILITY GRAPH. This will give you truly optimal (in the Euclidean distance sense) paths, if all your obstacles are polygonal (they are). Google this a little and you'll figure it out.

Another more complicated answer is to realize that A* and other kinds of breadth first search can be thought of as discretized versions of a particular PDE (a "wavefront propagation" PDE; it's called the Eikonal equation); so instead of using A* you can use a special kind of numerical PDE solver.

Option #2 is interesting in principle, but for the polygonal case the answers it gives will be the same as those gotten from #1. And #1 is vastly simpler and faster.

thanks people. Ive researched a bit and found solution for improving the path from A* to become euclidean shortest + smooth turn

I cant use VISIBILITY GRAPH, cus wc3 doesnt allow tat. I dont get access to polygon data. But ofc i can find a rough path with A* and then make a VISIBILITY GRAPH based on these nodes. But first ill read the article i found to see if there is a better technique

Hmm... ok. Here are some more ideas:

-- 1. More Visibility Graphs ----

There's a reasonably straightforward way to apply the visibility graph idea to an occupancy grid (what WC3 gives you).

Imagine building the following graph ahead of time as an offline computation:

Let the nodes of your visibility graph be all the walkable grid cells that are
1. adjacent to an obstacle.
and
2. (this restriction is not necessary, but will reduce the number of nodes:) does not lie on a Bresenham-line path between any other two such nodes.
and let an edge exist between any two of these nodes when the you can draw a Bresenham-line from one to the other. This could be computed efficiently by walking along the edges of your obstacles.

Then, your paths can be composed of Bresenham-lines between nodes. These will approximate the optimal-in-the-Euclidean-sense paths as closely as is possible on a discrete grid.

There's one additional piece of the puzzle that I left out: Also, ahead of time, you'd need to precompute, for every walkable grid cell (not just the visibility graph nodes), which visibility graph nodes are visible from that cell (where "visible" again, means, can draw a Bresenham line between them).

Then, when you want to find a path from point A to point B, the graph that you search on is the union of,
1. grid cell A, and all the edges between it and visibility graph nodes.
2. grid cell B, and all the edges between it and visibility graph nodes.
3. the visibility graph.

This will definitely give you optimal-in-the-Euclidean-sense paths in all circumstances. It also has the advantage over old-fashioned grid-based A* that your graph has fewer nodes to search on. The disadvantage is that you need to precompute and store these visible sets.


-- 2. Path refinement -----

You could compute a path using A* on your 4- or 8-connected grid, and then refine it to make it more optimal in the Euclidean sense. This kind of approach will not guarantee globally-Euclidean-optimal paths, but should produce paths that are still optimal on 4- or 8- connected grids and LOOK Euclidean-optimal. For a mental image, imagine that your path is a string, and we stretch it tight.

Here's one technique I just made up which should work nicely:
1. Your path is itself a collection of nodes with edges.
2. Iteratively, move each node (except the end nodes) towards the average of its two neighbors' positions. (Subject to the constraint that it cannot collide with an obstacle).

There may well be (read: almost certainly are) more efficient algorithms than this. But it should give you the idea.

[EDIT: link3333's reply immediately following this post gives another way to do path refinement; it sounds much more efficient, but I'd need to think about whether it'd give the same results.]


-- 3. Grids with more connectivity ------

This idea also will not give you Euclidean-optimal paths, but will give you paths closer to being so. Instead of pathfiding on a 4- or 8-connected grid, consider larger neighborhoods of your node. A picture here is worth a thousand words; this shows the "neighborhood" of a given grid cell with various degrees of connectivity:

(Notice that I only include an edge from (x,y) to (x+dx,y+dy) when |dx| and |dy| are coprime; i.e., their greatest common divisor is 1.)

[Edited by - Emergent on February 18, 2009 4:26:02 PM]

You can achieve your straight (red line) paths with the following:

1. Start at one endpoint.
2. Select 3 continuous nodes. If the selection goes over the other endpoint, stop.
3. Draw a virtual box from the 1st node to the 3rd node.
4. If no building or obstruction is in that box, then you can safely remove the middle node and repeat steps 2-4 with the same starting node. If there is an obstruction, then shift your node selection by one and repeat steps 2-4.