next »

[PompiPompi]

I made some blog post about A* in my dev blog.
Can you please take a look and tell me if it's clear enough, or you find any blantant mistakes?

http://pompidev.net/2012/05/29/a-practical-overview-of-awith-code/

[st33d]

Some pictures would make it easier to follow. It's quite tiring to read a lot of text without a break.

The flee stuff would really benefit from this. Adding slope towards the goal is a neat idea (one I don't have the cpu to spare for, but well done there).

The code looks pretty sensible to me. If you got it to draw a full diagnostic diagram then you can screen-cap it and that would help you explain your code. It would also help you debug it and help you come across a bit more confident about what you've achieved.

[Dacke]

A good initiative! So good that I will take the time to point out any errors I find

The first thing I noticed is that you treat your paragraphs inconsistently, making the whole thing a bit hard to read. Always put a newline between every paragraph, without any exceptions, and you'll be fine

If you are inside a maze and you are at the starting point and there is an exit, you need to search for the exit.

This may give the reader the impression that they could use A* if they ever find themselves inside a maze. But A* only works if you already know what the labyrinth looks like.

However, even with A*, sometimes it can’t perform well. A maze is a good example because in a maze the only possible path to the exit might also be the longest one, which with the most common heuristics of A* will make it go search for a lot of wrong paths with dead ends.
In an environment that is not exactly a maze, but also not an open field, A* can be very efficient.

You are implying that there may be better options than A* to this problem. But A* will find the optimal solution in the fastest possible way¹ given a specific heuristic. So even if you have a complex maze, you can't really find a better algorithm. If the problem takes time to solve even when using a good heuristic, it's simply a difficult problem.

But unless you solve the problem every frame for such a maze (which you shouldn't be doing), A* can easily find the optimal path for extremely huge, complex labyrinths. So there is no reason to tell people not to use A* for big stuff.

[lots of code]

I won't read and try understand the actual code right now, but it's good that you have it in there. You should probably mention what language it's written in, so that people can try it out. If you also add imports and a small usage example it will be easy for people to run the code for themselves.

In addition to that it would be good to add a permissive license to the code, so that people can try it out in their own projects. If you just say something like "Code license: CC-BY". Then people can use the code in any way they want, either to experiment with or put in their own projects, as long as they credit you or your post for that code. As it is now, people can't really use your code for anything meaningful without breaking the law. (Which is absurd, I know, but it's how it is)

A small style note: please consider using 1TBS indentation for your brackets. While it is largely a matter of taste, it makes for more compact code without adding any clutter, making it easier to skim through lots of code.

If you plan to post more code in the future, you may also want to consider adding code highlighting support to your wordpress.

Overall impressions:
I couldn't really follow the explanation. I get the impression that you're still a bit intimidated by the algorithm (which is understandable) which makes it hard for you to break it down and explain it. But writing this post is probably a good step towards getting that deeper understanding.

I would probably have focused more on the heart of the algorithm: the priority queue. Once I understood how that worked the other pieces fell into place for me (if I remember correctly, it's been a few years now)

¹ Lowest number of explored squares/nodes in the maze

[PompiPompi]

Thanks.
I know how the priority queue data structure works, but understand how a heap works is not really important for understanding A*. As I understand the A* algorithm simpley has a front, like I explained. The front is advancing, eventhough in practice you only pick one node of that front at a time.
I think that understanding the A* has a front is the important part. And that the heuristic affects how this front advance.

[Dacke]

Understanding how the priority queue is implemented isn't important at all. I fully agree with that.

But from a practical point of view, this is what is really important:

Starting with the initial node, it maintains a priority queue of nodes to be traversed, known as the open set. The lower f(x) for a given node x, the higher its priority. At each step of the algorithm, the node with the lowest f(x) value is removed from the queue, the f and h values of its neighbors are updated accordingly, and these neighbors are added to the queue. The algorithm continues until a goal node has a lower f value than any node in the queue (or until the queue is empty). (Goal nodes may be passed over multiple times if there remain other nodes with lower f values, as they may lead to a shorter path to a goal.) The f value of the goal is then the length of the shortest path, since h at the goal is zero in an admissible heuristic. If the actual shortest path is desired, the algorithm may also update each neighbor with its immediate predecessor in the best path found so far; this information can then be used to reconstruct the path by working backwards from the goal node. Additionally, if the heuristic is monotonic (or consistent, see below), a closed set of nodes already traversed may be used to make the search more efficient.

Except that the Wikipedia explanation is really hard to understand. So you'd have to simplify the explanation and perhaps talk about a front to make it easier to understand.

[st33d]

What?

You sort the open list in order of lowest F?

That's all there is to it. How you sort it is a different topic.

[Dacke]

Interesting that both of you assume that I'm talking about how the queue is implemented. But as I tried to explain in my last post: No, I'm not talking about implementation details.

But rather how the algorithm runs, where the priority queue is at the core of everything.

From a top-down perspective, A* can be described as the manipulation of an automatically sorted priority queue:

1. Add the starting node to the queue
2. Pick the first node from the queue, call it N
3. Add any unexplored neighbours of N to the queue
4. If N isn't the goal, Goto 2

Then you can go into further detail, explaining how you figure out how good a node is (distance travelled + heuristic for distance left).  Then go into explaining how the heuristic is defined.

[st33d]

The definition of A* is the open and closed lists. Without the two, you don't have A*, and you are not teaching A*.

By all means use it as a springboard to go on about your priority queue model, but don't leave out the classic interpretation. Just because you think your view is better, doesn't mean you shouldn't present the other side of the argument.

[kamac]

Thanks PompiPompi

Got it working:

[Dacke]

@St33d:

No, my ways obviously isn't the only way of explaining A*. But it is how it was taught to me and I think it makes it easy to understand. If you re-read my post, you'll see that I was only making a suggestion from personal preference

The original paper only says to mark nodes as open and closed. It doesn't say anything about maintaining lists of open and closed nodes. A common implementation is to have a priority queue for the open nodes and a problem-specific implementation for the closed nodes (for example a 2d-array for a grid-based map).

I'm not sure what your interpretation of "the definition A*" is, but I would be interested in hearing it. To me it sounds like you may be using a naive implementation if you are maintaining plain lists of open and closed nodes, which could lead to really bad computational complexity. But I may be mistaken?

[PompiPompi]

I think what he means is that using lists or priority_queue or arrays does not matter for the correctness of the algorithm. It only matters for performance.

[st33d]

Bam

[Dacke]

@PompiPompi

Well, I've tried several times to tell you that I agree with that

But a priority queue isn't a data structure. It's just a concept. You can implement a priority queue as a list or array or heap or hat with paper notes in it. And conceptually, A* is very often explained in terms of a priority queue, for example on Wikipedia (but not in the original paper, admittedly)

The original paper says: select the best open node

Many practical books/tutorials say: add the open nodes to a priority queue and pick the best node from the queue

The effect is exactly the same, it's just that actually calling it a priority queue can be very helpful (at least it was for me)

@st33d
thanks!  

[PompiPompi]

@PompiPompi

Well, I've tried several times to tell you that I agree with that

But a priority queue isn't a data structure. It's just a concept. You can implement a priority queue as a list or array or heap or hat with paper notes in it. And conceptually, A* is very often explained in terms of a priority queue, for example on Wikipedia (but not in the original paper, admittedly)

The original paper says: select the best open node

Many practical books/tutorials say: add the open nodes to a priority queue and pick the best node from the queue

@st33d
thanks! 

Oh ok.
Well, yea you basically search for the optimal next node. With the lowest f specifically.
Though I think that really doesn't explain how A* works conceptually. Because pulling the maximum value from a heap does not explain why it is done and how it is helping you.
Although it might be worth to mention it's done like that.
I think it's more intuitive to say that A* has a front(although sometimes revisiting old nodes), even if in practice it picks only one node each iteration.
It helps me understand that and also helps me understand what heuristics do, they simpley change the way the front advance.

[Dacke]

Hm, interesting. Thinking about it now, I think that my teachers did it like this:

1. show the top-down algorithm in terms of the queue, to give you a sense of what happens each "step"

2. manually use the algorithm on the whiteboard, showing what happens when you run it (indirectly showing the front progressing)

3. explain why it works (always picking the lowest F with an admissible H will give you the optimal path)