Jump to content
  • Advertisement
Sign in to follow this  
Bruno

A* and nodes

This topic is 5413 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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 ?

Share this post


Link to post
Share on other sites
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.

Share this post


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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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)?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!