Hello,
On their site for Intense Pathfinding, thei wrote that it uses Dijkstra(fast...?!).
link

Thought A* is better. So why should someone use Dijkstra in anodebased system instead of A*?


Greets
Rackscha

"A* star is better than Dijkstra" is a statement equal to "A hammer is better than a nail pistol". You can compare these two only in terms of their results. And the results of both of them are equally good. Other than that they are totally different. A* is a heuristic search. Dijkstra is pure graph theory. In most cases the implementation of dijkstra algorithms is a little more slim than the A* ones. But there are even hundreds of variations of the dijsktra algorithm. As a rule of thumb A* can get faster results when you have really many nodes to search (that is why it uses heuristics). In scenarios where you've got medium or low number of nodes the choice of algorithm is a purely technical decision.

A* is valid for Big searches, as in RTS Gridbased pathfinding
with thousands of grids or nodes.

If you only have to search though a couple of hundred
nodes, any other algorythm is fast enough.

Then its better to take the most slim approach,
with the least overhead.

A pure pathfinding (creating the path of nodes)
is not really a performance eater nowerdays.
Other things like the players physics and
"traces" to avoid obstacles are of a bigger concern.

Ah ok, so for a Nodebased Level,
Dijkstra would fit?

@Uhrwerk: Ok the statement was a bit false^^.

Oh year and since we have pointed out the "slim" way...mh currently creating a quadtree search algorythm to find Nodes in the level without going through all nodes.
(like: find all nodes in a range of 100quants and check which of them is the nearest visible node to start from)

Do you think its worth it?

Greets
Rackscha

Searching though nodes is very quick,
so dont expect any notable performance improvment.

It also depends how often you do the search...

(dont optimize stuff that is quick already, it
just creates unnesesary complicated overhead)

I can only agree with Damocles. Don't waste time speeding up code thats already fast enough. That is really a hard task for programmers, I know, we always want it as good as it can be. But it's a waste of time. If you later find out that this is the reason for performance issues, go change it. But don't waste your time with that now.

So for now its better to have a linked list with all nodes and going through it to find suitable nodes, right?


Greets
Rackscha

If you use a linked list is another design decision. An array list may work as well. Though normally you don't use linked lists with a dijkstra algorithm. You use a graph. However, if you plan to use IntenseX just don't care what they do as long as it works. Or are you going to implement your own solution?

Thats why iam talking about^^.
Did several A* algorythm in the past for learning. This time i want to complete it by starting from scratch and doing a system thatl work properly and move an entity.

And yes for the algorythm itself i use a graph, in A* i used Lists for open and closed lists for the nodes. HAve to look abit more into dijkstra if there is anbother difference as the heuristic.

In A*, i used ARRAY lists to store node sin open/closed list. When deleting a node in the middel of one of these lists, i had to modify all indexes >current index to avoid empty entries. With linked lists i could just delete a part of the chain and merge the rest together in no time.
If i remember right, i wont need random acces, so doing sequently is ok.

Greets
Rackscha

Of course you can use A*. There is no reason against it except for the more on complexity you have to deal with. B.t.w.: You'll have a graph in both cases. You just happen to manage the graph in nodelists on the A* algorithm. But you also have to store the information which node is accessible from which other node. So you can't work around the graph with the A* algorithm.