well... i am now building a basic and simple RTS game. i have used the a* path finding algorithm.... the path (even if there is no obsticale what so ever) is usually NOT in a straight line.... i read somwhere that inorder to make the path go in a straight line, i need to give a bonus, or to substruct a certain percentage from the cost calculation in the huristic function... and well, i have been having a hard time implementing it. plz plz plz help me cyberia_2ooo@linuxmail.org icq - 76671658

Assuming you are using something like manhattan distance as your heuristic your problem may lie in the tie breaking of nodes of the same value. Assume you have a map like this and you can only move north, south, east or west:

GOO
OOO G = goal S = start
OOS

What may be happening is:

XOO
XOO X = path traveled
XXX

which is one of the shortest paths

assuming you want something like this:
XOO
XXO
OXX

which is also the shortest path but a bit more of a straight line (as best as you could do on a grid)

The problem comes from nodes like this one:

GOO
OOO P = problem node
OPX

The A* algorithm has two choices here, either to go west or north
It sounds like yours is going west when you want it to go north.
What you can do is add a simple routine to break ties by moving to the node that makes the difference between the X and Y distance to the goal closest to 0.

If that is in fact the problem, I hope this helps.

Grunhund

Could you please draw a map with your problem so we can know exactly the behaviour you don''t want. I have coded a A* as well and had this problem (not real problem although)

ooXooo
oXoXoo
SoooXG
oooooo

Because it costed the same moving in any of the tiles surroind your tile. If you make that your costs to your 4-neighbours is less than to your 8-neighbours you will avoid that. Is this what was happening to you?

You can forget additional heuristics and just solve the problem easily just with a little randomization.

Normally, most A* implementations expand the current nodes'' children in a preset order. However, that order doesn''t matter, and it doesn''t need to remain constant. So if you recurse on a nodes'' children in a random order, you''ll avoid annoying right-angle patterns, and the algorithm will still work exactly as it did before.

quote: Original post by TerranFury
You can forget additional heuristics and just solve the problem easily just with a little randomization.

But this is not as efficient. You''ll expand more nodes unnecessarily with this approach. Altering the heuristic a tiny amount is more deterministic.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

For all monotonic domains you can get away with using straight line distance from the node to the goal as the heuristic estimate. For most game scenarios this will be sufficient. Anything else is just unnecessary complication.

Cheers,

Timkin

Timkin:

I agree that straight-line distance is a good heuristic, as it is an admissable heuristic, and it will also lead to straight rather than right-angle paths.

However, I don''t understand how the random order I proposed is inefficient. Of course, part of the problem may be a simple error (on my part) of communication, since I was thinking more of depth-first searches than I was of A*. My mistake. Anyway, the idea still works.

A* is usually done something like this (OPEN list begins with one entry, the starting node) Then, it performs the following:

1 - If OPEN list is empty, there is no path. End. Otherwise...
2 - Remove first node from OPEN list.
3 - Add this node to CLOSED list.
4 - If this node is the destination node, end. Otherwise...
5 - Insert NORTH neighbor node, if accessible, into OPEN list.
6 - Insert SOUTH neighbor node, if accessible, into OPEN list.
7 - Insert EAST neighbor node, if accessible, into OPEN list.
8 - Insert WEST neighbor node, if accessible, into OPEN list.
9 - Repeat.

Instead, I merely propose performing steps 5-8 in a random order. This will prevent direction from biasing placement in the OPEN list of nodes with equal weights.

hmmm

hmmm

quote: Original post by TerranFury
However, I don''t understand how the random order I proposed is inefficient.

I didn''t say it was... I''m sure Kylotan can elaborate further on his comments.

quote: Original post by TerranFury
A* is usually done something like this

5 - Insert NORTH neighbor node, if accessible, into OPEN list.
6 - Insert SOUTH neighbor node, if accessible, into OPEN list.
7 - Insert EAST neighbor node, if accessible, into OPEN list.
8 - Insert WEST neighbor node, if accessible, into OPEN list.

Instead, I merely propose performing steps 5-8 in a random order. This will prevent direction from biasing placement in the OPEN list of nodes with equal weights.

Actually, for each successor node of the current node (in this case N, S, E & W), a check is made to determine if this node already exists in the CLOSED list. If it does, a cost comparison is made between the two versions of the node, with the lower cost node taking the place in the closed list.

Furthermore, a similar check is also made as to whether the node already exists in the OPEN list.

A more efficient way of avoiding bias for nodes of the same cost is to randomise the insertion into the OPEN list (presuming its ordered from lowest cost to highest cost). When inserting a node, traverse the list until a cost is found that is higher than the cost of the current node. Normally you would simply insert the node in the OPEN list one place higher than this higher cost node. However, if you find that there are several nodes with the same cost as the current node, randomly choose a place to insert the new node among them. This is a fairly trivial exercise, although it does increase the computational cost of the insertion algorithm.

Cheers,

Timkin