Why uses Intense Pathfinding pure Dijkstra and not A*

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.

This discussion makes not much sense when you compare both algorhithms. Basically Dijkstra and A* are the same. The only difference is one estimation function that you have to add to Dijkstra and you will automatically get A*. So it will not calculate each possible route on a node, it will estimate with a function where to go to find the shortest route to the goal node. Often they simply use a length-function (length between current node and goal) for that.

So if you have Dijkstra, than you almost have A*. And if you have A*, then Dijkstra is already implemented. You only have to remove this estimation function.

But when you want to calculate all routes in a tree (for each node to each possible node), then you have to use Dijkstra. This makes sense, when you pre-calculate a matrix. With such a matrix you dont have to calculate routes in real-time. You just look them up from this pre-calculated matrix. I thought this is the way Intense-X pathfinding works.

You can find more details on this here:
http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782

Never said that i wnat to workaround the graph with A* o.O. Did A* while ago, i know what it is, the major question was just about the speed(or have i spoken so unclearly? dont know^^, sometimes my english isnt very good).

Oh and nice idea todo a complete precalculation. Will try it(maybe) later. Depends on my current progress, and the current performance.


But thanks for your suggestions^^.

EDIT: ah okay foun the point where you misunderstood me. I used a Graph and an open(closed list system to see whether a node is used or not, so i used a graph in my A* version, too

Greets
Rackscha

Of course that depends how often the "fast enough" code gets run. If paths are being searched for a very large number of objects, even comparatively fast operations can cause a significant slowdown.

where in this case it would not be fast enough or the wrong method..

What I stated was, that if the code is fast enough for the purpose it
is used in, there are other things to work on, than
wasting time on optimization.

--

I have a pathfinding for RTS units on a mobile phone game (Java phone)
that can find a path in realtiime for hundreds of objects with no
remarkable slowdown.
It is then just using a more appropriate metod than
a classic A* pathfinding.
Where it would not be as fast for single units.

The initial choice of the method is more important than the optimization of it.