Hello Currently, i'm working on a pathfinding system, The image linked below shows my situation http://img230.imageshack.us/img230/2171/croppedrj8.gif Basicly, we take 2 nodes, first would be a start, and the second would be the end. Grey lines are illustrating the connections which we can use to find the shortest way, between nodes. Have you any idea which algorithm might I use? Regards

The answer is in your subject line: A* is the algorithm that you want

-me

So you want to pathfind on an arbitrary graph with unit edge weights?

The gold standard for most situations is A*, but it only helps when you can define an admissible heuristic. In your case, on an arbitrary graph, it's less useful.

Since all your edge weights are equal, it looks like plain old breadth first search (BFS) is king.

There are slight twists you can put on this. For instance, if you will often be looking for paths leading to (or from) a single node, then you can think of BFS in terms of a "distance transform." Suppose you often want to go TO a particular node. Then, as a precomputation step, you can label all of the nodes with numbers in the following way:
1 - Label the goal node with 0.
2 - Label its neighbors with 1.
3 - Label THEIR neighbors with 2.
...and so on, in a flood-fill kind of way. Then, no matter where you start, you can take the shortest path to the goal by just doing steepest-descent: wherever you are, the right place to go next is the node adjacent to you with the smallest number.

Well okay, but A* is based on 2-D array, right?
Do you have any idea how could I put into an array all the points with their connections to each other?

@up:

Well, we actually do not care about edge wiehgts, it doesn't matter. The goal is, to find shortest-jump-way (by a jump i mean to jump from 1 point to another).

Quote: it looks like plain old breadth first search (BFS) is king.

I don't really understand that...

No, A* is just based on a graph traversal exactly like you have. It's what you want; just read up on the algorithm. The algorithm uses arrays to solve the problem, but if you read the algorithm you'll understand how they get put in the array(s).

-me

Quote: Original post by travikk
Well okay, but A* is based on 2-D array, right?
Do you have any idea how could I put into an array all the points with their connections to each other?

A* works on any kind of graph, not just a square grid -- but you need some kind of heuristic that gives you an idea of "how far" a given node is from another node independent of the graph.

For instance, if you had a hex-grid on a plane, A* works perfectly well, because you still have an idea of how far apart points are; you can use the Euclidean distance, for example (though there is a better heuristic for hex grids... but leave that for another thread).

In your situation, I assume vertexes don't have any sort of "coordinates?" In that case, see my post above; A* will work, but there's not much point to using it as your heuristic will just be zero.

Quote: Original post by Emergent
In your situation, I assume vertexes don't have any sort of "coordinates?" In that case, see my post above; A* won't help.

Of course they have coordinates. Otherwise how would they be drawn to those positions in that image?

If they don't have "coordinates" or some kind of spatial structure then all paths are equivalent because all are the same distance. In that case there's no point in pathfinding =)

-me

Quote: In your situation, I assume vertexes don't have any sort of "coordinates?" In that case, see my post above; A* won't help.

Yes, they don't have any coordinates.
Lol, guys this post is going so fast... ;-)

Quote:

Quote: it looks like plain old breadth first search (BFS) is king.

I don't really understand that...

Oh, sorry... missed that sentence. Wikipedia has a good article:
http://en.wikipedia.org/wiki/Breadth-first_search

Algorithms like A* and such are pretty much more sophisticated versions of BFS.

Quote: Original post by travikk

Quote: In your situation, I assume vertexes don't have any sort of "coordinates?" In that case, see my post above; A* won't help.

Yes, they don't have any coordinates.
Lol, guys this post is going so fast... ;-)

Are you just interested in the shortest number of nodes touched? While not coordinates, that's still a distance metric (all traversals == cost of 1). That's a pretty trivial A* heuristic to use.

-me