Hi., Ok, this is the first time i will try to implement A*, for path finding in my engine, so bare with me :) I understand the theory behind the algorthim, and i'm confident i can implement it, however i have a little problem, wich is more of a data structure problem, than the A* itself. My problem is the data structure in where the information will be stored. The way i'm thinking, is i will place manually nodes around my level. What i'm unable to grasp is that, one node can have more than 1 link to another node, so a linked list is out of the question, right ? What kind of structures are used to make this ? At first i was thinking in something like this : struct node { float bla; node *links; } Then depending on the number of links, i would initialize the "links" variable accordingly, but i believe this will get very complex to handle. Thanks everyone, Bruno

Quote: Original post by Bruno
<snip>
What i'm unable to grasp is that, one node can have more than 1 link to another node, so a linked list is out of the question, right ?
<snip>
Bruno

A linked list can hold any number of connections you need. Why do you say it is out of the question?

this:
std::list<node *> connections;
could contain any number of links from the current node to any other node.

J

Well, i know a linked list can have as many connections i want, i just think it's too messy(recursion).
I know how to do it without stl, but if i do use stl, how do you navigate the list in the case you posted ?
Is it less messy ?

I just finished making an A* algorithm (today). Actually, I have never seen any documentation on A*, but knowing how A* finds the path, I am pretty sure my algorithm works on the same principles.

It is pretty simple to use :
you send
-an array of your map (in my case, the map is a float map[HEIGHT][WIDTH]. The value of the map being how hard it would be for a unit to go through this position.
-the starting position and ending position

it sends you back an array of the sequential position the unit would have to move to.

If anybody is interested in having the class, I don't mind putting it online.

Yeah, i would love to see it.
How do you organize your data structure ? You use some kind of grid from the input array ?

namespace astar{    struct node    {        stl::vector<node *> Connections;        float cost;        int x, y;    }    struct map    {        stl::vector<node> Nodes;    }}

I used vector since the connections probably won't change often and the number of nodes will vary likewise.

I actually use an array in my node class to reduce overhead.
-Greg

Here is the source code

http://francoisjanson.no-ip.com:8080/astar

For the data structure, I have :

-an array dedicated to storing the best path up to a position (it contains only the position from where the path came and the cost it took to get there)

-a ordered list(an stl vector actually) that contains the nodes.

Also, you will notice that I made a garbage collector. That prevents my pathfinder to request memory from the kernel all the time. When I need memory, I request ... but I don't give back until the program ends (don't worry, this didn't caused any problems even in a 4000x4000 map).

I hope it helps

Crucifer

crucifier:
You have any real life specs?
Like how many paths per second on a 128x128 map?

btw Bruno:
I just realized you're Portuguese, do you hang out on irc(ptnet)?

White Rabbit, I just benched it for you at 128x128.

with :
-128x128 map
-pentium 800
-compile:release

random starting position
random ending position

I get a little above a thousand pathfind per second.