next »

[prettymuchbryce]

Hey TIG. I don't come here often, but I think I'm in the right forum for this sort of topic.

I have created an API for using A* easily in AS3. My hope is that it could help someone make a game. I remember a some years ago when I wanted to make tile-based games, but was unsure of how to make my own A* implementation. I was hoping I could get some feedback here, but I'm not sure how prominent flash is here on TIG. It's worth a try I guess. I also notice that i have many emoticons to choose from so I will choose one now at random.  boink

https://github.com/prettymuchbryce/EasyStarAS3

[Dacke]

AS3 is one of the most used languages here and A* is one of the most discussed algorithms. So you are certainly in the right place!

This isn't really related to the API, but you seem to be using a naive implementation of the priority queue:
https://en.wikipedia.org/wiki/Priority_queue#Naive_implementations

I think you would get a significant speed boost for big maps if you instead used a proper priority queue:
https://en.wikipedia.org/wiki/Priority_queue#Usual_implementation

I'm not sure if AS3 has any built-in class for priority queues. Otherwise you should probably be able to find an implementation with a good license online. Or easily implement one yourself, if AS3 has support for heaps or something like that. (There are dozens of possible approaches that would work; you can even build a priority queue on top of a standard linked list with no loss of efficiency).


edit, to clarify what I mean:

Right now you are maintaining an unsorted list of open nodes (_openList). Adding a new node to the list is cheap and can be done in constant time: O(1). But every time you want to pick the best node from the list, you have to look through the entire list which takes a lot of time: O(n).

What you can do instead is to make _openList a priority queue. It's basically a sorted list. Every time you add a new node to the queue, you put it in the right place in the queue. This can be done quite fast: O(logn). Then picking the best node means just picking the node that is first in the list, which can be done in constant time: O(1).

(But do note that the entire priority queue doesn't have to be sorted. The only thing you need to do is to extract the best node. This is why a heap works, even though it doesn't maintain a complete ordering of the nodes)

[Attila0413]

You may want to test and compare results with other AS3 A* implementations, to check if your's fast enough.

I usually use BrainBlitz's A* class: http://www.brainblitz.org/anthony/as3-a-pathfinding-class

[prettymuchbryce]

What you can do instead is to make _openList a priority queue.

Hey Dacke. I appreciate your detailed response. I don't know much about priority queues, but this sounds like a good opportunity to learn how they work. I am reading now about binary heap implementation.

You may want to test and compare results with other AS3 A* implementations, to check if your's fast enough.

Attila you are absolutely right. I should be running speed tests against other libraries. I should have thought of this. Thanks!

[prettymuchbryce]

I implemented a priority queue per Dacke's suggestion. Here it is: https://github.com/prettymuchbryce/EasyStarAS3/blob/master/src/com/pmb/priority/PriorityQueue.as

It can actually be used with any object type.. the only really silly thing is I haven't tested it's speed at all yet. For all I know -- array.sortOn could be faster. This is something I want to look into soon to figure out if it's even worth it. It was still fun to make, though.  

[Dacke]

That was quick work, good job

It is always possible to get small constant savings that improve the speed for each node/insert/read/whatever. But such improvements often come at the cost of code readability and often aren't that important.

When it comes to speed for stuff like this, it's generally computational complexity that matters. (If you use a 100 times bigger map, will it take 100 times longer to run or 10,000 times?) For A*, it's the queue and the heuristic that affect the computational complexity. So by just changing to a heap you probably have a the same complexity as other AS3 A* libraries (unless they use something more complex, like a Fusion tree, but even then it may be comparable).

So while it is a good idea to compare your speed to other libraries, I wouldn't worry too much about speed at this point. Just make sure that your solution scales as well as that of other libraries. So if a comparison shows that you are 30% slower for 1,000 nodes, you should be approximately 30% slower for 1,000,000 as well.

What is more important at this point is what you came here for: getting the API right. If you manage to construct a worthwhile API, you can then spend months gaining small constant time savings.

Unfortunately, AS3 is not a language I know. So I'm afraid I can't be of much help now. I hope you'll find someone else who can give you feedback on it

edit: Perhaps you can make a small writeup of your API here? The class signature, your reasoning behind it, its strength and its limitations. Or only some of those things

[st33d]

For all I know -- array.sortOn could be faster

It is.

The sort methods in the Flash Player seem to run through the player code instead of native as3 code like you would expect in Java. Writing your own Array sorting functions is largely a waste of time in as3. Unless of course you're using some kind of linked list implementation.

-

Other nitpicks:

The Dictionary object is very slow to access. You're using the format:
_nodeDictionary[coordinateX + "_" + coordinateY]
An Object can do this with identical syntax and do it faster. Or perhaps use coordinateX + coordinateY * gridWidth in an Array/Vector for even more speed.

The EventDispatcher system is fairly slow - you really only want to use it with UI elements where lots of things are listening to one object. Consider using a Function object as a listener instead if possible.

It's good that you're marking Nodes as open and closed, however String comparisons are slower than integer comparisons, you should consider changing the datatype.

[Dacke]

Hah, there you go! Pretty obvious that I'm not an AS3 programmer

But do note that a heap and array sort are two very different things.

With an in-place array sort you will get a really bad time complexity for inserts : O(n) (both on average and as a worst-case). So if you are going to have a big queue (which you must be prepared for) you risk getting much worse results with an array sort.

For a small queue you will probably get much better results with the built-in sort. Because it's faster at what it does. But for larger queues, you will start getting much worse results due to the time complexity of array sort.

So I think you should probably stick with the heap if you want to handle arbitrarily big maps. But if you have an expected max-size, you can do tests and see when the heap catches up with the built-in sort. It is possible that you'll run out of memory before the heap catches up, though. So it is worth testing.

edit: On second thought: I think that your original naive implementation actually could be faster than the built in sort. Seeing how you'll do a lot more inserts than pulls. So I would bet my money on heap>naive>builtInSort. But I may be underestimating how slow AS3 code is compared to native code.

[st33d]

Yeah, but he's already doing a lot of function calls in the priority queue, which pretty much kills any advantage from the off. Function calls in as3 slow things down, the compiler is 100% unoptimised (seriously, no seriously). You use them for readability, then abandon them when you need speed.

I'm not an expert on Array.sort, but whatever is going on inside it runs incredibly fast and may in fact be optimised already for large lists.

[Dacke]

You have to remember the difference between constant speed costs and computational complexity. Extra function calls only add extra constant time per element, while sorting an array over-and-over adds extra computational complexity which can't be optimized away (disclaimer: if an array actually is an array in AS3).

The math:

Insert into an array has time complexity O(n). Where n is the length of the array. The time it takes to insert a new element into a sorted array with n elements can be written as:
arrayInsertTime(n) = Constant_A * n + Constant_B
Where Constant_A > 0

Insert into a heap has time complexity O(log n), where n is the number of elements in the heap:
heapInsertTime(n) = Constant_C * log(n) + Constant_D
Where Constant_C > 0

Given a large enough value for n, the heap will be faster because n grows much faster than log(n). It doesn't matter how small Constants A and B are, or how big Constants C and D are. As long as you add enough elements, the heap will eventually be faster.

Some concrete math using arbitrary numbers:

We'll pretend that the built-in solution has the time formula:
arrayInsertTime(n) = 1*n+1 milliseconds.

So to insert a new element into an array that is 10 long, it would on average take:
arrayInsertTime(10) = 1*10 + 1 = 11 ms

And we assume that the heap has horrible constants, because every function call (etc.) adds a lot of extra cost:
heapInsertTime(n) = 100*log(n)+100 ms

So to insert a new element into a heap with 10 elements would on average take:
heapInsertTime(10) = 100*log(10)+100 ~=  330 ms

But if we try some bigger numbers:

n	array sort insert (in milliseconds)	heap insert (in milliseconds)
1	2	100
10	11	330
100	101	561
1,000	1,001	791
10,000	10,001	1,021
100,000	100,001	1,251
1,000,000	1,000,001	1,482

So even if we try to completely cripple the heap by giving it horrible constants, it wins out pretty quickly. Already at a 1,000 elements it is faster to do the insert into the heap.

Actually calculating the constants isn't really interesting in a real-world situation. You have to do tests to find out when/if the heap catches up. But this shows that the heap is likely (but not guaranteed) to catch up with the built-in sort before you run out of RAM.

Unless, as I mentioned before, an array actually isn't an array but rather a list in AS3. And if AS3 has a engine-powered sort that can make use of an already-sorted list, then that will probably outperform both these options.

Either way: run some tests!

(a small disclaimer: my math isn't really rigorous here regarding O(log n) as I ignore the base and stuff, but it does the job of showing the principle.

Also, I have probably missed something obvious, so please correct me where I'm wrong!)