I’m working on a priority queue for network communications so that important things (the enemy right next to your player) get sent before unimportant things and truly trivial things can get culled if anything important is happening. That is just for context, the real question isn’t network related.
Considering implementation – based on what I want to do, if I were writing this independent from Unity, I would probably use a binary heap as it seems like an ideal data structure for this task. With a little digging, I’ve found several C# implementations to dissect (I’m still getting the hang of the whole .NET thing). My question though is - does doing things like this with scripting in Unity even make sense? Maybe I just haven’t looked enough, but most of what I’ve seen in scripts is a little logic wrapped around the Unity-specific API stuff. That probably speaks to a number of things – the ease of scripting in Unity, the usefulness of what is available by default, etc – but is it also because dealing with things like this isn’t completely feasible in the context of scripting in Unity?
I know that is a pretty open-ended question and sorry if it is too naive.
I would guess that a binary heap would have the same utility in any programming language. I’ve written a binary heap method for a Unity game that doesn’t use any Unity API. Whether you use a binary heap really depends on what you require of a sorted list.
I guess the post was based on two things that were only sort of semi related.
Most (not all) of the scripts I’ve seen people using in Unity are very straightforward and rely almost exclusively on stuff like for/while/if wrapped around the Unity API stuff. Sometimes (rarely) I’ll see references to other .NET stuff (usually used briefly for a discreet task - like IO). Why is this?
While a binary heap would have the same utility in any language, it wouldn’t necessarily have the same performance in any environment – and in a sense, performance is a big part of utility when you are thinking about the types of structures you are using. Maybe I’m mistaking things that are relatively new to me for things that are opaque – this may be not being totally comfortable with .NET yet, not being 100% familiar with Mono and not having done a whole lot in terms of scripting inside of an engine that motivates this.
My concern, I guess, is that 2 is what is leading to 1. I don’t know if that makes sense. I suppose that I should just do and see how things perform.
The logical process is going to be the same in any setting. A binary heap system is a very specific method of sorting. Any API references are most likely the input of the binary heap, the comparators of the input, the output of the binary heap or a reference to the data structure of the output required by the API, but not part of the actual sorting process itself.
I meant utility in the same way you do, performance. The entire utility of a binary heap, compared to a different sorting method, is performance. If there is something about a language that would make a binary heap slower, it would most likely make any other sorting method slower as well. The only thing I could see making a difference is that possibly .NET has some optimized built in sorting methods. I haven’t looked up anything in it yet about sorting. For short lists, there might be some fast built in sorting method, but for larger lists the speed of a binary heap, even if implemented through scripting, is going to be hard to beat.
It’s a really useful device that can be used in any situation where you can say one item in an array is less than, greater than or equal to another item in the array. Also, it’s not much more than 20 lines of code. The problem is they have to be perfect or else they don’t work at all. My hang up was getting the math right for figuring out parent/child relationships in an array index where the first member is member zero.
Something useful that I read: Don’t use your binary heap to do anything except sorting a list of numbers until you get it working. After that, you can try to use it with your A* etc.
Goodluck. I’d be happy to comment specifically on any problems too.
As a side note, I think it is interesting how Platonic so many computing concepts are. Binary heaps are going to look the same in any language because that is how they must look.
There is no particular reason not to write large amounts of code in one of the Unity languages. One of the many proverbs of the Perl community is that the main virtues of a programmer are laziness, impatience and hubris. Or to put it another way, coders who have found an easy and quick way to achieve a goal will tend to want to post it for other people to see. I think it is fair to say that the majority of Unity coders are resourceful hobbyists who are good at making use of the built-in stuff but less willing and able to hand-craft more complex code by themselves. Also, professional coders are more likely to be bound by copyright or simply less willing to share any sophisticated code with the “competition”. Basically, I think you are more likely to see simple code shared, but that code can often be quite clever and effective at what it does.
Also worth remembering is that much of the built-in code is probably written in optimised C/C++, which you would expect to be faster than C# code (although there are a few exceptions to this).
Implementing a binary heap in C# or JS, Boo shouldn’t be a problem, but you should be aware that it isn’t necessarily always an efficient technique. A simple array-based priority queue is maximally fast for removals, but a naive version could be slow (linear time) for insertions. A heap takes about the same time (logarithmic) for both insertions and removals - in other words, insertions are optimised at the expense of removals. In the situation you describe, the insertions that really matter will be near the head of the queue (therefore very quick if you start searching from the head end of the array). The time-sensitive nature of their priority means that they need to be retrieved quickly and therefore won’t be around long to clutter the array and make subsequent insertions slower. Also, the operation of a heap tends to jump around to widely separated locations in the array, which is bad for cache performance, and may well drag more than the linear searching of an array.
I would first try implementing the queue as either a cyclic array or a linear array in “reverse” (with the high priority items at highest indices) and see what performance is like. If it seems slow, maybe then try the heap implementation. It will probably come down to the relative numbers of low vs. high priority events and in what order they arrive - very difficult to predict in advance.
Thanks for the advice and observations - that makes sense.
To expand on this situation, there will be a lot of items enqueued but there might only be a handful of items dequeued at any given time (they would be dequeued until a list to send is full). What I want to ensure is that the highest priority items are always the ones put into list for sending and that the structure is optimized for insertion.
I’ve not done anything with cyclic arrays, but I’m assuming that it is (at least conceptually) similar to a circular buffer where the computation cost is independent of the length of the data?
It seems that you will have a small set of predetermined priority values (urgent, fairly urgent…) and you are planning to throw away low priority events after a certain time. The ordering scheme should arrange the high priority events in FIFO order. However, since the low priority events get less important with age (until they are eventually discarded altogether), they could be in LIFO order. You could try seeking the correct insertion point for a new item using a linear search starting at the head end of the list. With low priority events, you will not need to find the “correct” position in terms of temporal order, but rather insert the new item in front of the other low priority items. The high priority part of the list should be short (since items need to be dealt with quickly) and so there aren’t many items to search through when a low priority item is added.
Basically, you get the simplicity and cache-friendliness of a simple linear insertion queue, but you avoid much of the inefficiency of a naive implementation. There are many possibilities, but you should avoid a simple linear list with the highest priority item at index 0 and quicksorting the entire list after each insertion is also a bad idea.
Just two different names for the same thing. The advantage of this structure is that you never need to shuffle more than half the items along during an insertion.
By the way, if you have only a few priority levels, you might try just making a separate list for each. Then each list is a simple FIFO queue - you just have a rule that a queue won’t be looked at until all higher priority queues are empty.
Priority value would be a float between 0 and 1. Values would be determined both by environmental things like distance from the player and by the nature of the information being queued (rigidbody movement vs. notice of starting a new animation vs current animation frame, for example).
If there were no items in the queue with high scores (like rigidbody movement of a close object) then it makes sense to send what is there (which might be animation synching information of a distant object). So those things should all be added to the queue because if nothing more important comes along they will be sent. Rather then sending the entire queue, I would send a predetermined quantity of information – so dequeue items based on priority until a buffer is full and send it. The queue can be destroyed here or it could be destroyed as some other reasonable interval.
That was my plan, anyway. And a binary heap seamed ideal given those goals.
I’ll experiment with circular buffers too – I’m not completely sure why I wasn’t considering that in the first place. Familiarity, I guess.