Advice on sorted list please

[si guy]

Hi all, I'm trying to optimize an A* implementation and I was going to start by keeping the openList of nodes sorted. I'd like the same data structure to allow for quick access to nodes of arbitrary coordinates. I'm not a compsci grad so I have no idea what method would be the most all-round efficient. I was thinking some sort of two-faced hash map of pointers(combining cost and coordinates somehow) but I'm reluctant to spend lots of time studying a method which may not be best. Any pointers on which data structure to study first?

Thanks.
-Simon Watt

[Patrick Mylund Nielsen]

I think what you're looking for a (self-balanced) binary search tree,
a tree data structure that keeps itself sorted.

http://en.wikipedia.org/wiki/Binary_search_tree
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Self-balanced BSTs change themselves to retain the same height.

Here are some implementations:

http://code.google.com/p/go-avltree/
https://github.com/stathat/treap

[John Asmuth]

If you want to quickly access nodes at specific coordinates, especially if it's something like an integer (x, y), use a map with the key struct { X, Y int }.

Since you're doing A*, you'll probably want some way to look up the node on the fringe with the highest sum of cost+heuristic. The normal way to do this is via a priority queue, backed by a max heap.

[Patrick Mylund Nielsen]

Except maps aren't sorted. You get that with a self-balancing BST, and
the lookup cost is pretty comparable. (That's not to say A* can't be
implemented using maps--it's just that auto-sort was a criterion
here.)

[John Asmuth]

For looking up nodes by their (x,y), sorting is irrelevant.

The correct way to combine cost and coordinates in A* on a 2d space is to use a priority queue where the priority is the cost plus the heursitic, where the heuristic is a function of the location.

[Patrick Mylund Nielsen]

"I'm trying to optimize an A* implementation and I was going to start
by keeping the openList of nodes sorted. I'd like the same data
structure to allow for quick access to nodes of arbitrary
coordinates."

[John Asmuth]

Sometimes people don't ask the right question. Doesn't mean I can't give the right answer.

In any case, si guy is free to judge whether or not my suggestions work for his goals.

[Patrick Mylund Nielsen]

"Oh sorry, I didn't read that part of your email, but I believe my
approach would suit your goal." would have worked just fine. I have no
doubt your approach works/is correct, but you don't win any Internet
points for telling people posting to the list that they're asking the
wrong questions when it was you who didn't read their email -- it just
comes across as arrogant. Nobody cares who's "right." It's petty. If
anything, "Oh, sorry" just makes you come across a nicer guy.

OT, but, IMO, lately, and especially since the release of Go 1
(probably because more people are trying out Go), many regulars on
this list have been pretty unwelcoming, almost hostile to people who
are new to Go, or want to know more about the design decisions behind
the language (which is often mistaken for a personal attack against r,
gri, rsc et al, or Plan 9, or UNIX.) This doesn't really help
adoption.

I don't really know where I'm going with that. Just an observation.

[si guy]

I'm now considering using a dual data structure where both contain pointers to the same set, some sort of priority queue for the cost and maybe a map for coordinates, and just let the gc clean up the mess afterwards. It would double? insertion time but lookups would be O(1) (is that correct? Big O confuses me sometimes). I'm already running the search in parallel so I have to be careful about that.

What would be really neat would be if those two functions could be combined, hashing functions seem to be relevant, I must search more.

Thanks for the suggestions all.

-Simon Watt

[John Asmuth]

On Tuesday, May 15, 2012 10:02:21 PM UTC-4, Patrick Mylund Nielsen wrote:

"Oh sorry, I didn't read that part of your email, but I believe my
approach would suit your goal." would have worked just fine.

It wasn't your email, so why would I apologize to you? I stated what I thought would be a good solution to si guy's problem. I think you're reading a lot of extra "tone" into my email that simply wasn't there.

 

I have no doubt your approach works/is correct,

Then why say anything? I'm pretty sure my first reply wasn't offensive or arrogant. I guess if you video-taped me making it I could make seem a bit snotty if I tried :)

 

but you don't win any Internet
points for telling people posting to the list that they're asking the
wrong questions when it was you who didn't read their email -- it just
comes across as arrogant. Nobody cares who's "right." It's petty.

Ironic!

 

If anything, "Oh, sorry" just makes you come across a nicer guy. 

I suppose I hadn't realized that I had misread anything. I still don't think I have, so I'm having trouble mustering up an apology that means anything. I guess that makes me a mean, arrogant jerk who should really just keep his nose out of things when someone asks a question about AI algorithms.

Now, *this* email can certainly come off as a bit jerky, but it's intentional, since I'm a bit piqued.

[Patrick Mylund Nielsen]

Yes, except this is your regular tone.

Your reply just proves my point.

[John Asmuth]

I think you should consider the map access to be constant time, but priority queues backed by heaps have O(log n) complexity for insertion and extraction, and O(n) time for extracting an arbitrary element (generally if you want to do this you don't use a priority queue).

A parallel A* is an interesting thing to think about. I've never done it before (though I'm sure there are people who have), but there are some issues that jump to mind:

- if you have a set of workers getting the best node and adding to the fringe, the synchronization overhead might slow you down so much that it turns out to be slower than the original.

- if you assign swaths of nodes to workers, and have them do the search within those swaths, you risk having one swath being particularly unattractive and wasting a worker.

I can't immediately think of a good way to divvy up the work for A*. Maybe some perusing of google scholar for "parallel A*" would be worth it.

[John Asmuth]

I submit. I'm a horrible person.

[si guy]

Actually, I stumbled across the parallelization by accident. I had everything in "mini functions" already for readability while developing and everything uses channel passes instead of shared state, and I accidentally put "go" before the function call to get the neighbors and process them(force of habit). I had no explicit synch structure in place at all, but it still works and it is ~6x speedup on the 6 core machine I'm using.

[Patrick Mylund Nielsen]

Not at all :) Sorry, I didn't mean to imply anything about you
personally, and I think you're one of the few who has helped the most
people, on here and on IRC -- it's just the general tone here lately
has been more about being right (or the language being "right, god
damnit") than about giving people a warm welcome. I said this was your
regular tone because you said I was reading too much into it when it's
a much broader observation. I should have said "it's the general tone,
lately."

Anyway, now I'm just babbling. I bumped the thread about setting up a
golang-beginners list -- it's probably more constructive to discuss
that.

[John Asmuth]

Always awesome when that happens.

[Andrew Gerrand]

On 16 May 2012 12:19, Patrick Mylund Nielsen <pat...@patrickmylund.com> wrote:
> Yes, except this is your regular tone.
>
> Your reply just proves my point.

You are way out of line. John was being nothing but helpful. If you
saw anything more than that in his post, then you must be projecting.
(And forgive me if I am presumptuous in saying so.)

Please keep the drama off-list, or at least in another thread.

(Sorry, si guy, for continuing to distract from your question.)

Andrew

[Patrick Mylund Nielsen]

Agree to disagree then. I stand by "sometimes people ask the wrong
questions" being neither helpful nor "a warm welcome" (ref. the other
thread). I guess I'm a little disappointed that you of all people
don't even recognize the general point I'm trying to convey here (that
this list, not this thread in particular, is becoming increasingly
less welcoming with the influx of people who don't have PhDs.)

Anyway, as I mentioned, I did move it to the other thread regarding
mailing lists as this wasn't constructive.

[Ethan Burns]

Hi si guy,

Are you using A* for pathfinding in a grid?  If so, there are two good options for the open list depending on whether or not you allow for non-integer costs (it is common to use sqrt(2) for diagonal movements in grids).  If you allow for non-integer costs then I would recommend using container/heap as your open list, with the node with the minimum cost + heuristic at the front.  This will give you O(lg n) for most operations used by A* (push, pop, remove).  If you are only considering integer-base costs then you may want to use a data structure called a 1-level bucket priority queue.  A 1-level bucket priority queue is just a simple array of lists and gives you constant time insertion, and if you have some fixed limit on the number of priority values you also get constant time removal.  The 1-level bucket priority queue can make A* significantly faster if it's applicable for your problem.

Also, I am guessing that you want via x,y values in order to perform lookups in your closed list (to see if you have visited a node already).  As John said, a map will work here, however, I would recommend using a slice instead as it will be quite a bit faster than a map and you can allocate the entire slice upfront, effectively removing all allocations from the inner-loop of your A*.

One last thing, I see that you got a 6x improvement by using parallelism: that is great!  I do want to warn you that your improvement may be because you are no longer finding optimal solutions.  If you don't care about optimality and if the paths look good then this is probably not a big issue, however, it may be something to think about.  Usually a better and slightly more principled technique for relaxing optimality to improve the performance of an A*-like algorithm is to multiply the heuristic by some value > 1.  This will guarantee that your solution is within a constant factor (the factor is the value by which you multiplied the heuristic) of optimal.

By the way, Nathan Sturtevant has some interesting resources for grid-based pathfinding at http://movingai.com/

Best,

Ethan

[Kyle Lemons]

There was an excellent post by Russ Cox specifically about Djikastra's algorithm and described using a heap backed by a slice.

https://groups.google.com/d/msg/golang-nuts/Rj5t1h_ztxI/Fgs6HfLqMHAJ

This may be instructive in creating your datastructure.

[Ethan Burns]

Si guy,

I just wrote a simple grid pathfinder that you may find helpful: http://code.google.com/p/eaburns/source/browse/#hg%2Fgridpath

It is not heavily tested.

Best,

Ethan

[si guy]

Wow, thank you for the reference implementation, it's the most comprehensive one I've seen in go thus far.

As with any ai problem, my specific environment allows me to fudge some things that are un-important.
A non-optimal solution is fine here for many reasons: I'm only going about 10 tiles due to collisions and changes to the map, this is fine because the map has no real blocked terrain/I just don't want the ai to "flatten" the map, and it recalculates when an imminent collision is detected; the terrain is very "cloudy" (there are no large obstacle groupings); the map is _huge_ (hundreds or thousands of tiles to a side) and generated via perlin and the like; units are relatively short-lived; units are directed from "above" in groups that perform maneuvers against the players via a sort of hull made of player positions -> find weak spots in formation + prioritize targets -> attack -> destinations for the pathfinder are being changed often; etc etc.

I'm also post-smoothing the path a la: http://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php?page=2

Sorry for the poor/non grammar there but the essence is this: speed is the dominating factor here, if units collide occasionally or run into things that's ok, but it can't lag... At all.

TLDR: for me, fast and slightly wrong is much better than slow and right. Now where have I heard that mantra before...;)

Thanks again,

-Simon Watt

[Job van der Zwan]

I was about to ask whether or not HPA* (or one of its predecessors) is a useful algorithm in your case, but based on what you wrote down here I suspect not...

http://aigamedev.com/open/tutorial/clearance-based-pathfinding/

[si guy]

Ya, all of my units can make tight corners and can fit in one tile, and nothing can move through "building" tiles without destroying them. I'd love to do this sort of thing but, you know, time constraints. Thanks for the article, I'll probably need it for the next game. A space rts a la home world but more realtime.

Thanks.

[Jiří Zárevúcky]

Don't overrate warm welcomes. I personally prefer people shutting down my wrong approach immediately.

What's the point of nice people telling me how to do what I want, when what I want is wrong in the context? I would just waste my time trying wrong things.

That being said, I think your hostile attitude towards John's reply is completely unwarranted and does nothing to improve things you say you seek to remedy.

On Wednesday, 16 May 2012 05:59:55 UTC+2, Patrick Mylund Nielsen wrote:

Agree to disagree then. I stand by "sometimes people ask the wrong
questions" being neither helpful nor "a warm welcome" (ref. the other
thread). I guess I'm a little disappointed that you of all people
don't even recognize the general point I'm trying to convey here (that
this list, not this thread in particular, is becoming increasingly
less welcoming with the influx of people who don't have PhDs.)

Anyway, as I mentioned, I did move it to the other thread regarding
mailing lists as this wasn't constructive.

On Wed, May 16, 2012 at 5:46 AM, Andrew Gerrand wrote:

[Patrick Mylund Nielsen]

Okay.

I don't think continuing this conversation is constructive, so let's
end with "to each his own".