BREADTH FIRST SEARCH
^

breath first search sounds like something from a mouthwash commercial.



Depth fisrt is usually used when a significant hint of the most-likely candidate is possible (like being closer to the target on a cartesian grid). A* can also be used on generic graphs as well.

Quote: Original post by UnshavenBastard
This comes close to what I did :-)
But beware, custom ADTs are eeeevil, reinventing the wheel and whatnot *gg*
I personally prefer O(1) to O(log n), though ;-)


- unshaven

Well, there are still times when it's necessary to write your own. For example, an application where performance is absolutely critical. Like A pathfinder class for a game engine :)

I did write my own class that is similar to std::vector, before I used STL much. I also had a class that derived from it and deallocated the memory for you. If STL works anything like my class, a call to Remove() iterates through its internal list comparing items until it finds a match. O(n) removes just won't cut it. And it gets worse. STL tries to remove ALL instances of the item. This means it will never early out, which is bad considering that all items in the open and close list of A* are unique.

The issue here is not which is the best data architecture for A*, but at what point you should start looking at your data structures as an optimisation strategy.

When learning A* and doing your first implementations, stick with easy to understand structures like arrays and lists. As you progress and have a stable pathfinder that is independent of the domain, then consider improvements like a hashmap.

From there it totally depends on your domain and thus development is customisation of your basic pathfinder product. Optimise to take advantage of domain characteristics such as low branching factor, or pre-searched nodes, etc. There are dozens and dozens of tricks and tips that you'll find posted over the web and in books. Read them... understand them... try them out... and you'll very quickly learn what is likely to work in your game.

Cheers,

Timkin

A list with O(1) removals? Yeah right.

Quote: Original post by Kevinator
A list with O(1) removals? Yeah right.

STL lists have an ammortized constant time requirement for removals: http://www.sgi.com/tech/stl/List.html

Quote: Original post by Kevinator
A list with O(1) removals? Yeah right.

My list has exactly O(1) removal.

Quote: Original post by UnshavenBastard

Quote: Original post by Kevinator
A list with O(1) removals? Yeah right.

My list has exactly O(1) removal.

TO have non-amortized, O(1) removal in *any* case, you need to have O(1) access. Doesnt that mean your list is an array?

Aren't doubly linked list removals O(1)? Assuming you have the link, all you do is tie the next and previous neighbors together.

Yea, assuming your have an iterator to the element, which would involve a linear search on an unsorted list.

Quote: Original post by Steadtler

Quote: Original post by UnshavenBastard

Quote: Original post by Kevinator
A list with O(1) removals? Yeah right.

My list has exactly O(1) removal.

TO have non-amortized, O(1) removal in *any* case, you need to have O(1) access. Doesnt that mean your list is an array?

Well, if you make a list that requires items listable with it to inherit from an interface which provides two methos, object GetLink() and object SetLink(), only accesible from the list, and the listable item implements those as setting and getting a variable of type object it holds, the list can put the pointer (or reference, depending on language) to the node of the list representing this item into the item and also obtain it via the two methods. For anything but the list this is all unknown, so I think this even doesn't break encapsulation, at least not as bad as if you'd stick pointers for nodes all visible directly into an item. Whatever, this was meant to be a list for special caes, not all-purpose. Sometimes I prefer speed ofer total cleanness.

Of course this way of doint it puts some constraints on what you can put in what lists (which also can be overcome easily if you need), but if this is clearly stated in the specs of the data type... I think it's okay.
But even if not... speed counts :-D