quote: Original post by bpj1138
I don''t see what you mean by "use data structures to compute the cost". It seems redundant to me, because you already have the node/link structure, and what other structure can be more efficient or more intuitive or more suitable?

You are using a horrendously computationally intensive recursion. In doing so, you may very likely evaluate positions multiple times, when nothing in them has changed.
A clever data structure will prevent unnecessary evaluations.

quote:
Which brings me to another point, you said my implmentation is "naive". I take that as a compliment, because I strive to make my code as simple as possible, even if it sacrifices some efficiency. Code clarity is number one concern.

--bart

Bubble sort is more clear than quicksort. Does that mean that bubble sort is a "better" sort, due to the fact that it can be more easily understood?

I said it was naive because you implied that you would recursively evaluate costs of every individual node. Not only is it still unclear how you plan to do this, but even doing so is horribly inefficient.

Naive does not refer to the readablility of the code. A very complex algorithm can be written with very clear code, and a naive algorithm could be written horrendously.

Actual coding is just a routine excercise.

Algorithm development is much more important as a science.

quote: Original post by bpj1138
Well, I actually found a description of Dijkstra''s algorith, and indeed, it seems to be the same thing. So those of you that said it was A* you really had no idea what you were talking about, did you?

Second, since A* is directed by whatever huristic you give it, say direction, it will omit some branches that could be a better solution. In effect, A* doesn''t guarantee the shortest path, especially if the cost varies a lot.

Actually, as long as the heuristic is considered "admissible", the A* algorithm has been
mathmatically proven to find the optimum (read shortest) path in the least nodes searched.

Any decent graph algorithm book will confirm this. Also, see Bryan Stout''s article Smart Moves
for various algorithm comparisons, which can be found on gamasutra.

quote:
Keep in mind, this (Dijkstra''s), algorithm should be used on nodes, not tiled maps, obviously.

Actually, Dijkstra''s works equally well on nodes or tiled maps. As long as a connected graph
can be achieved (what nodes and tiles are in abstract) both Dijkstra''s and A* are effective.

quote:
And lastly, the algorithm is not slow, compared to depth first search, which takes eons, it''s millions of times faster, and I myself don''t care if I can get 1 more millisecond out of a more complicated, partial solution to the problem.

Slow is a relative comparison. Because of how they work Dijkstra''s will always be slower than an
A* with an admissible heuristic. That matters in FPS and RTS games where speed is important.
It may not matter to you, but that does not change the reality of their speed comparisions.

And, for whatever this is worth, an A* without a heuristic works just like a Dijkstra''s.

Eric

quote: Original post by bpj1138

And I also agree that it can be used in tiled maps, but it's not optimized for that. A* is. With tiled maps, you have so many nodes and links, it must be slow. This is where A*'s direction/distance huristic comes in.

A* does not have a 'direction/distance' heuristic. A*, among other requirements, implements a cost function for a node i of the form f(i) = g(i) + h(i) where g(i) is the lowest cost of all paths from the start node to node i and h(i) is an estimate of the cost of any path from node i to the goal node. How you define h(i) is totally up to you. Obviously, some domains have more suitable and more obvious heuristics to use than others.

Note: if you set h(i) = 0 for all i then A* reverts to uniform cost search. In this situation, Dijkstra's provides the optimally efficient solution, A* does not.

The reason why some people believed your algorithm was A* was because you had a non-zero heuristic. However, you actually have g(i) = 0 and have effectively implemented a regression search algorithm (ie, searching from the goal back to the start). This means that you have simply inverted your search task. Your 'heuristic' is now just the path cost to the node i from the start (really the end) and the heuristic (estimate of path cost from node to end - which is really the start) is zero.

quote: Original post by bpj1138
However, I still think A* is different. A* backtracks, Dijkstra's algorithm never backtracks. A* never updates nodes with new values. Correct?

A* doesn't backtrack, per se. At least not in the sense of backtracking in a DFS. A* explores the successor states of the lowest cost node. If viewed in terms of contours within the fitness space, A* always expands the node in the highest fitness contour (lowest cost). This node may or may not be in the same subtree as any previously expanded node. This is why A* suffers from memory problems on large search spaces.

Regards,

Timkin

Edited by - Timkin on September 16, 2001 11:16:51 PM

You''re fighting a losing battle here. No, A* is not recursive. I don''t even know if it''s possible to implement it recursively. Pretty much every implementation I''ve ever seen has been iterative.

Just so we all know what we're talking about:

From Patrick Winston's 'Artificial Intelligence', 3rd Edition, pg 94:


To conduct A* search,

1 Form a one-element queue consisting of a zero-length path that contains only the root node

2 Until the first path in the queue terminates at the goal node or the queue is empty,

3 Remove the first path from the queue; create new paths by extending the first path to all the neighbors of the terminal node.

4 Reject all new paths with loops.

5 If two or more paths reach a common node, delete all those paths except the one the reaches the common node with the minimum cost.

6 Sort the entire queue by the sum of the path length and a lower-bound estimate of the cost remaining, with least-cost paths in front.

7 If the goal node is found, announce success. Otherwise announce failure.



I added the line numbers. Note that 2-6 are supposed to form a loop. (Certainly doesn't look like it would lend itself to recursion to me).




Edited by - cheesegrater on September 17, 2001 1:28:53 PM