Microsoft MakeCode

Heap Extension (TypeScript only)

This one’s an extension that’s more likely to be used in other extensions than directly in a game. It adds a Heap data structure (~~ Priority Queue), which is a data structure that allows quick access to the smallest element of all inputs. This extension should work across the board when editors are updated (for example, it won’t work in the current microbit release, but will with the next release).

(I have another extension that relies on this one that’ll be more interesting in general; I’ll post that in a bit :slight_smile: )

The fact that it only returns the smallest element may sound particularly limiting, but you define how elements are compared; you do this by passing a comparator function in the constructor, which takes two objects of the given type, and should return a negative value if the first object is smaller than the second, 0 if the values are the same, or a positive value if the first value is larger than the second value.

That can definitely sound confusing at first, so a few quick examples (click details to expand):

Number min heap

If you have a large group of numbers, and always want access to the smallest one, you want a MinHeap. To make this, you just need the comparator to subtract b from a:
const minHeap = new Heap((a: number, b: number) => a - b);

Now, when you push values into the heap, it will always give you the smallest value when you peek or pop:

const minHeap = new Heap((a: number, b: number) => a - b);

const values = [1, 18, -5, 256, -32, 0.0005, 82];

for (const v of values)
    minHeap.push(v);

while (minHeap.length > 0)
    console.log(minHeap.pop());

results in the following being logged to the console:

-32
-5
0.0005
1
18
82
256

Number max heap

If you want the exact opposite - to always get the largest value of a set of values - all you need to do is reverse the value - you can multiply the previous example by negative one, or just subtract a from b:

const maxHeap = new Heap((a: number, b: number) => b - a);

Using the same example from the previous section:


const maxHeap = new Heap((a: number, b: number) => b - a);

const values = [1, 18, -5, 256, -32, 0.0005, 82];

for (const v of values)
    maxHeap.push(v);

while (maxHeap.length > 0)
    console.log(maxHeap.pop());

results in

256
82
18
1
0.0005
-5
-32

Sorting Sprites by distance && Heap.BuildHeap

The heap can store any type of value; you just have to have a way to define how the elements are compared. (Note that the actual values returned don’t matter beyond whether the value is negative, 0, or positive; returning -1 will be treated the same as returning -100000)

This example will have the heap will have the heap the will always return the next sprite of kind Enemy that is closest to the origin (0, 0):

const myEnemies = sprites.allOfKind(SpriteKind.Enemy);
const myEnemyHeap = Heap.buildHeap<Sprite>(
    (a, b) => (a.x ** 2 + a.y ** 2) - (b.x ** 2 + b.y ** 2),
    myEnemies
);

Note that there are two things different in this one; I defined the type by explicitly supplying the value for the generics (the <Sprite> before the parentheses), and I’m using a different way of constructing a heap – Heap.buildHeap.

BuildHeap is an efficient way of constructing a heap, that manages to do it faster than inserting elements one by one; it mutates the given array, and uses it for the internal storage. This version manages to complete the task in linear ( O(n)), as compared to inserting elements one by one into the heap (O(n * log(n))). Note that this means the heap now relies on the myEnemies array; if you modify it, the heap will no longer necessarily work / output the correct value.

Notes

Few other notes; this is just a simple binary heap; another approach is using a fibonacci heap, but that is significantly more complicated, and almost always ends up being slower in practice even if it theoretically has lower algorithmic complexity.

3 Likes

@peli had a good idea for a demo so I added it; the demo is a riff on the last example, where it spawns a bunch of enemies and builds a heap of them based on distance from (0, 0), except it builds the heap every frame and has the enemies bounce around the screen, so it can give each enemy a ‘rank’ of in order of closeness.

Press up to add an asteroid, down to remove one (min 2 so there’s something to demo), and a to reset :slight_smile:

3 Likes