We don't see U shapes in real games because the AI programmers of those games kick level designers in the butt if they do that =)

It seems like your map is binary. Either you can pass ... or you can't. Right ?

This might be a big limit in some games. Some terrain could be harder to go through than others.

Yep, that's still on my to do list.
How much does your Pentium 800 score?

6011.783 paths/s

You scared me there for a second eheh, i though you were talking about the 128x128 map. =)

With that result you're talking for sure about the small one, the 64x64.

This guy that once told me a Pentium 1G would have about half the performance of a Pentium 3G was right =), my cpu goes a bit over 15k.

To compensate Bruno for this off-topic rambling of owers =).
Bruno, you can use a simple 2 dimentional array or a graph.

@Crucifer
thanks for the source.
I will take a better look at it tomorrow to see how it works, however, i don't know why, i just hate stl :)

@White Rabbit ,
Yeah, Portuguese here, i went to pt net sometimes, but i don't go there for more than a year now, however i lurk a lot in gamedev-pt.net.

I used to lurk around there aswell, but there is just not a big enough comunity there.

Quote: Original post by Bruno
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

A link list can be used by the Location nodes, but you will need a second link list as each nodes (one to many) connections list (link list of pointers to LocationsNodes).

I usually use a static array for the Primary nodes so I can search quickly (and use array indexes in place of pointers to save memory) and then a seperate array of pointer nodes to make up the connection lists.
I can do this because I already know how many nodes my maps are
and the number of links between them. BUT nothing says you
cant also do it with dynamicly allocated nodes.

If you are going to read in serialized data from a file, the
linear search capability of arrays is handy, and you would need to maintain yet another link list (all existing Location Nodes) to do the same search operation.

Another reason I use an indexed array system is that my maps are
modular (based on regular zones of a certain size) which can be rolled in and out of memory as a block and I dont have to rebuild the link lists/allocate each time....