Category Archives: Tutorials

Here comes the sun lalala

Porting Surreal Engine C++ to WebAssembly

In this post I will describe how I ported the Surreal Engine game engine to WebAssembly.

Surreal Engine is a game engine that implements most of the functionality of the Unreal Engine 1 engine, famous games on this engine are Unreal Tournament 99, Unreal, Deus Ex, Undying. It belongs to the classic engines that worked mainly in a single-threaded execution environment.

My initial idea was to take on a project that I couldn’t complete in any reasonable amount of time, thus showing my Twitch followers that there are projects that even I can’t do. On my very first stream, I suddenly realized that the task of porting Surreal Engine C++ to WebAssembly using Emscripten was doable.

Surreal Engine Emscripten Demo

A month later I can show my fork and assembly of the engine on WebAssembly:
https://demensdeum.com/demos/SurrealEngine/

The controls are the same as in the original, using the keyboard arrows. Next, I plan to adapt it to mobile controls (touch), add correct lighting and other graphic features of the Unreal Tournament 99 render.

Where to start?

The first thing I want to say is that any project can be ported from C++ to WebAssembly using Emscripten, the only question is how complete the functionality will be. Choose a project whose library ports are already available for Emscripten, in the case of Surreal Engine, you are very lucky, because the engine uses the SDL 2, OpenAL libraries – they are both ported to Emscripten. However, Vulkan is used as a graphics API, which is currently not available for HTML5, work is underway to implement WebGPU, but it is also in the draft stage, and it is also unknown how simple the further port from Vulkan to WebGPU will be, after its full standardization. Therefore, I had to write my own basic OpenGL-ES / WebGL renderer for Surreal Engine.

Building the project

The build system in Surreal Engine is CMake, which also simplifies porting, since Emscripten provides its own native builders – emcmake, emmake.
The Surreal Engine port was based on the code of my last game on WebGL/OpenGL ES and C++ called Death-Mask, because of this the development went much easier, all the necessary build flags were with me, code examples.

One of the most important points in CMakeLists.txt is the build flags for Emscripten, below is an example from the project file:


-s MAX_WEBGL_VERSION=2 \

-s EXCEPTION_DEBUG \

-fexceptions \

--preload-file UnrealTournament/ \

--preload-file SurrealEngine.pk3 \

--bind \

--use-preload-plugins \

-Wall \

-Wextra \

-Werror=return-type \

-s USE_SDL=2 \

-s ASSERTIONS=1 \

-w \

-g4 \

-s DISABLE_EXCEPTION_CATCHING=0 \

-O3 \

--no-heap-copy \

-s ALLOW_MEMORY_GROWTH=1 \

-s EXIT_RUNTIME=1")

The build script itself:


emmake make -j 16

cp SurrealEngine.data /srv/http/SurrealEngine/SurrealEngine.data

cp SurrealEngine.js /srv/http/SurrealEngine/SurrealEngine.js

cp SurrealEngine.wasm /srv/http/SurrealEngine/SurrealEngine.wasm

cp ../buildScripts/Emscripten/index.html /srv/http/SurrealEngine/index.html

cp ../buildScripts/Emscripten/background.png /srv/http/SurrealEngine/background.png

Next, we’ll prepare index.html, which includes the project file system preloader. For posting on the web, I used Unreal Tournament Demo version 338. As you can see from the CMake file, the unpacked game folder was added to the build directory and linked as a preload-file for Emscripten.

Major code changes

Then it was necessary to change the game loop, you can’t run an infinite loop, it leads to the browser freezing, instead you need to use emscripten_set_main_loop, I wrote about this feature in my 2017 note “Porting SDL C++ game to HTML5 (Emscripten)”
We change the code for the condition for exiting the while loop to if, then we output the main class of the game engine, which contains the game loop, to the global scope, and write a global function that will call the step of the game loop from the global object:


#include <emscripten.h>

Engine *EMSCRIPTEN_GLOBAL_GAME_ENGINE = nullptr;

void emscripten_game_loop_step() {

	EMSCRIPTEN_GLOBAL_GAME_ENGINE->Run();

}

#endif

After this, you need to make sure that there are no background threads in the application. If there are, then get ready to rewrite them for single-thread execution, or use the phtread library in Emscripten.
The background thread in Surreal Engine is used to play music, the main thread of the engine receives data about the current track, about the need to play music, or its absence, then the background thread via mutex receives a new state and starts playing new music, or pauses. The background thread is also used to buffer music during playback.
My attempts to build Surreal Engine under Emscripten with pthread were unsuccessful, because the SDL2 and OpenAL ports were built without pthread support, and I did not want to rebuild them for the sake of music. Therefore, I moved the background music thread functionality to single-thread execution using a loop. Having removed pthread calls from the C++ code, I moved buffering, music playback to the main thread, so that there were no delays, I increased the buffer by several seconds.

Next I will describe specific implementations of graphics and sound.

Vulkan is not supported!

Yes, Vulkan is not supported in HTML5, although all the advertising brochures point out cross-platform and wide support on platforms as the main advantage of Vulkan. For this reason, I had to write my own basic graphics renderer for a simplified type of OpenGL – ES, it is used on mobile devices, sometimes does not contain fashionable features of modern OpenGL, but it is very well transferred to WebGL, this is what Emscripten implements. Writing a basic tile renderer, bsp rendering, for the simplest display of GUI, and drawing models + maps, was possible in two weeks. This was probably the most difficult part of the project. There is still a lot of work ahead to implement the full functionality of the Surreal Engine rendering, so any help from readers in the form of code and pull requests is welcome.

OpenAL is supported!

It was a great stroke of luck that Surreal Engine uses OpenAL for audio output. After writing a simple hello world in OpenAL and building it in WebAssembly using Emscripten, it became clear to me how simple it all is, and I set out to port the audio.
After several hours of debugging, it became obvious that there are several bugs in the OpenAL implementation of Emscripten, for example, when initializing the reading of the number of mono channels, the method returned an infinite number, and after trying to initialize a vector of infinite size, C++ crashes with the exception vector::length_error.
This was circumvented by hardcoding the number of mono channels to 2048:


		alcGetIntegerv(alDevice, ALC_STEREO_SOURCES, 1, &stereoSources);



#if __EMSCRIPTEN__

		monoSources = 2048; // for some reason Emscripten's OpenAL gives infinite monoSources count, bug?

#endif

Is there a network?

Surreal Engine currently does not support network play, play with bots is supported, but someone is needed to write AI for these bots. Theoretically, it is possible to implement network play on WebAssembly/Emscripten using Websockets.

Conclusion

In conclusion, I would like to say that porting Surreal Engine turned out to be quite smooth due to the use of libraries for which there are Emscripten ports, as well as my previous experience implementing a game in C++ for WebAssembly on Emscripten. Below are links to sources of knowledge, repositories on the topic.
M-M-M-MONSTER KILL!

Also, if you want to help the project, preferably with WebGL/OpenGL ES render code, then write to me in Telegram:
https://t.me/demenscave

Links

https://demensdeum.com/demos/SurrealEngine/
https://github.com/demensdeum/SurrealEngine-Emscripten

https://github.com/dpjudas/SurrealEngine

Turn on USB keyboard backlight on macOS

Recently bought a very inexpensive Getorix GK-45X USB keyboard with RGB backlighting. After connecting it to a MacBook Pro with an M1 processor, it became clear that the RGB backlighting was not working. Even pressing the magic combination Fn + Scroll Lock did not turn on the backlighting, only the level of the MacBook screen backlighting changed.
There are several solutions to this problem, namely OpenRGB (does not work), HID LED Test (does not work). Only the kvmswitch utility worked:
https://github.com/stoutput/OSX-KVM

You need to download it from GitHub and allow it to run from the terminal in the Security panel of the System Settings.
As I understood from the description, after launching the utility sends a press of Fn + Scroll Lock, thus turning on/off the backlight on the keyboard.

Tree sort

Tree sort – sorting by binary search tree. Time complexity – O(n²). In such a tree, each node has numbers on the left less than the node, on the right greater than the node, when coming from the root and printing values ​​from left to right, we get a sorted list of numbers. Amazing, right?

Let’s consider the binary search tree diagram:

Derrick Coetzee (public domain)

Try manually reading the numbers starting from the second to last left node in the lower left corner, for each node on the left – a node on the right.

It will look like this:

  1. The second to last node on the bottom left is 3.
  2. It has a left branch – 1.
  3. We take this number (1)
  4. Next we take the vertex itself 3 (1, 3)
  5. On the right is branch 6, but it contains branches. Therefore, we read it in the same way.
  6. Left branch of node 6 is number 4 (1, 3, 4)
  7. The node itself is 6 (1, 3, 4, 6)
  8. Right 7 (1, 3, 4, 6, 7)
  9. We go up to the root node – 8 (1,3, 4,6, 7, 8)
  10. Print everything on the right by analogy
  11. We get the final list – 1, 3, 4, 6, 7, 8, 10, 13, 14

To implement the algorithm in code, two functions are required:

  1. Building a Binary Search Tree
  2. Print out the binary search tree in the correct order

A binary search tree is assembled in the same way as it is read, each node is assigned a number on the left or right, depending on whether it is smaller or larger.

Example in Lua:


function Node:new(value, lhs, rhs)
    output = {}
    setmetatable(output, self)
    self.__index = self  
    output.value = value
    output.lhs = lhs
    output.rhs = rhs
    output.counter = 1
    return output  
end

function Node:Increment()
    self.counter = self.counter + 1
end

function Node:Insert(value)
    if self.lhs ~= nil and self.lhs.value > value then
        self.lhs:Insert(value)
        return
    end

    if self.rhs ~= nil and self.rhs.value < value then
        self.rhs:Insert(value)
        return
    end

    if self.value == value then
        self:Increment()
        return
    elseif self.value > value then
        if self.lhs == nil then
            self.lhs = Node:new(value, nil, nil)
        else
            self.lhs:Insert(value)
        end
        return
    else
        if self.rhs == nil then
            self.rhs = Node:new(value, nil, nil)
        else
            self.rhs:Insert(value)
        end
        return
    end
end

function Node:InOrder(output)
    if self.lhs ~= nil then
       output = self.lhs:InOrder(output)
    end
    output = self:printSelf(output)
    if self.rhs ~= nil then
        output = self.rhs:InOrder(output)
    end
    return output
end

function Node:printSelf(output)
    for i=0,self.counter-1 do
        output = output .. tostring(self.value) .. " "
    end
    return output
end

function PrintArray(numbers)
    output = ""
    for i=0,#numbers do
        output = output .. tostring(numbers[i]) .. " "
    end    
    print(output)
end

function Treesort(numbers)
    rootNode = Node:new(numbers[0], nil, nil)
    for i=1,#numbers do
        rootNode:Insert(numbers[i])
    end
    print(rootNode:InOrder(""))
end


numbersCount = 10
maxNumber = 9

numbers = {}

for i=0,numbersCount-1 do
    numbers[i] = math.random(0, maxNumber)
end

PrintArray(numbers)
Treesort(numbers)

Важный нюанс что для чисел которые равны вершине придумано множество интересных механизмов подцепления к ноде, я же просто добавил счетчик к классу вершины, при распечатке числа возвращаются по счетчику.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/treesort

Источники

TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube

Tree sort – YouTube

Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube

Sorting algorithms/Tree sort on a linked list – Rosetta Code

Tree Sort – GeeksforGeeks

Tree sort – Wikipedia

How to handle duplicates in Binary Search Tree? – GeeksforGeeks

Tree Sort | GeeksforGeeks – YouTube

Bucket Sort

Bucket Sort – sorting by buckets. The algorithm is similar to counting sort, with the difference that the numbers are collected in “buckets”-ranges, then the buckets are sorted using any other, sufficiently productive, sorting algorithm, and the final chord is the unfolding of the “buckets” one by one, resulting in a sorted list.

The algorithm’s time complexity is O(nk). The algorithm works in linear time for data that obeys a uniform distribution law. To put it simply, the elements must be in a certain range, without “spikes”, for example, numbers from 0.0 to 1.0. If among such numbers there are 4 or 999, then such a series is no longer considered “even” according to the yard laws.

Example of implementation in Julia:

    buckets = Vector{Vector{Int}}()
    
    for i in 0:bucketsCount - 1
        bucket = Vector{Int}()
        push!(buckets, bucket)
    end

    maxNumber = maximum(numbers)

    for i in 0:length(numbers) - 1
        bucketIndex = 1 + Int(floor(bucketsCount * numbers[1 + i] / (maxNumber + 1)))
        push!(buckets[bucketIndex], numbers[1 + i])
    end

    for i in 0:length(buckets) - 1
        bucketIndex = 1 + i
        buckets[bucketIndex] = sort(buckets[bucketIndex])
    end

    flat = [(buckets...)...]
    print(flat, "\n")

end

numbersCount = 10
maxNumber = 10
numbers = rand(1:maxNumber, numbersCount)
print(numbers,"\n")
bucketsCount = 10
bucketSort(numbers, bucketsCount)

На производительность алгоритма также влияет число ведер, для большего количества чисел лучше взять большее число ведер (Algorithms in a nutshell by George T. Heineman)

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bucketSort

Источники

https://www.youtube.com/watch?v=VuXbEb5ywrU
https://www.youtube.com/watch?v=ELrhrrCjDOA
https://medium.com/karuna-sehgal/an-introduction-to-bucket-sort-62aa5325d124
https://www.geeksforgeeks.org/bucket-sort-2/
https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
https://www.youtube.com/watch?v=LPrF9yEKTks
https://en.wikipedia.org/wiki/Bucket_sort
https://julialang.org/
https://www.oreilly.com/library/view/algorithms-in-a/9780596516246/ch04s08.html

Radixsort

Radix Sort is a radix sort. The algorithm is similar to counting sort in that there is no comparison of elements, instead, elements are grouped *symbolically* into *buckets*, the bucket is selected by the index of the current number-symbol. Time complexity is O(nd).

It works something like this:

  • As input we receive the numbers 6, 12, 44, 9
  • Let’s create 10 list buckets (0-9) into which we will add/sort numbers bitwise.

Next:

  1. Start a loop with counter i until the maximum number of characters in the number
  2. According to the index i from right to left we get one symbol for each number, if there is no symbol, we consider it zero
  3. Convert the symbol to a number
  4. We select a bucket by index – number, put the number there in full
  5. After we finish iterating over the numbers, we transform all the buckets back into a list of numbers
  6. We get numbers sorted by rank
  7. Repeat until all the digits are gone

Radix Sort example in Scala:


import scala.util.Random.nextInt



object RadixSort {

    def main(args: Array[String]) = {

        var maxNumber = 200

        var numbersCount = 30

        var maxLength = maxNumber.toString.length() - 1



        var referenceNumbers = LazyList.continually(nextInt(maxNumber + 1)).take(numbersCount).toList

        var numbers = referenceNumbers

        

        var buckets = List.fill(10)(ListBuffer[Int]())



        for( i <- 0 to maxLength) { numbers.foreach( number => {

                    var numberString = number.toString

                    if (numberString.length() > i) {

                        var index = numberString.length() - i - 1

                        var character = numberString.charAt(index).toString

                        var characterInteger = character.toInt  

                        buckets.apply(characterInteger) += number

                    }

                    else {

                        buckets.apply(0) += number

                    }

                }

            )

            numbers = buckets.flatten

            buckets.foreach(x => x.clear())

        }

        println(referenceNumbers)

        println(numbers)

        println(s"Validation result: ${numbers == referenceNumbers.sorted}")

    }

}

The algorithm also has a version for parallel execution, for example on a GPU; there is also a bit sorting variant, which is probably very interesting and truly breathtaking!

Links

https://gitlab .com/demensdeum/algorithms/-/blob/master/sortAlgorithms/radixSort/radixSort.scala

Sources

https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D 0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0% BA%D0%B0
https://www.geeksforgeeks.org/radix-sort/

https://www.youtube.com/watch?v=toAlAJKojos

https://github.com/gyatskov/radix-sort

Heapsort

Heapsort is a pyramid sort. The time complexity of the algorithm is O(n log n), fast, right? I would call this sorting – sorting of falling stones. It seems to me that the easiest way to explain it is visually.

The input is a list of numbers, for example:
5, 0, 7, 2, 3, 9, 4

From left to right, a data structure is made – a binary tree, or as I call it – a pyramid. Pyramid elements can have a maximum of two child elements, but only one top element.

Let’s make a binary tree:
⠀⠀5
⠀0⠀7
2 3 9 4

If you look at the pyramid for a long time, you can see that it is simply numbers from an array, following one after another, the number of elements on each floor is multiplied by two.

Next comes the most interesting part, we sort the pyramid from the bottom up, using the falling pebbles method (heapify). Sorting could start from the last floor (2 3 9 4), but there is no point because there is no floor below to fall to.

Therefore, we begin to drop elements from the penultimate floor (0 7)
⠀⠀5
⠀0⠀7
2 3 9 4

The first element to fall is chosen from the right, in our case it is 7, then we look at what is under it, and under it is 9 and 4, nine is greater than four, and nine is also greater than seven! We drop 7 on 9, and lift 9 to the place of 7.
⠀⠀5
⠀0⠀9
2 3 7 4

Next, we understand that the seven has nowhere to fall lower, we move on to the number 0, which is on the penultimate floor on the left:
⠀⠀5
⠀0⠀9
2 3 7 4

We look at what’s underneath it – 2 and 3, two is less than three, three is greater than zero, so we swap zero and three:
⠀⠀5
⠀3⠀9
2 0 7 4

When you reach the end of the floor, go to the floor above and drop everything there if you can.
The result will be a data structure – a heap, namely a max heap, since the largest element is at the top:
⠀⠀9
⠀3⠀7
2 0 5 4

If you return to the array representation, you will get a list:
[9, 3, 7, 2, 0, 5, 4]

From this we can conclude that by swapping the first and last elements, we will get the first number in the final sorted position, namely 9 should be at the end of the sorted list, swap them:
[4, 3, 7, 2, 0, 5, 9]

Let’s look at a binary tree:
⠀⠀4
⠀3⠀7
2 0 5 9

We have a situation where the bottom of the tree is sorted, we just need to drop 4 to the correct position, we repeat the algorithm, but we do not take into account the already sorted numbers, namely 9:
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

It turned out that, having dropped 4, we raised the next largest number after 9 – 7. We swap the last unsorted number (4) and the largest number (7)
⠀⠀4
⠀3⠀5
2 0 7 9

It turns out that now we have two numbers in the correct final position:
4, 3, 5, 2, 0, 7, 9

Then we repeat the sorting algorithm, ignoring those already sorted, and as a result we get a heap of the following type:
⠀⠀0
⠀2⠀3
4 5 7 9

Or as a list:
0, 2, 3, 4, 5, 7, 9

Implementation

The algorithm is usually divided into three functions:

  1. Creating a heap
  2. Heapify Algorithm
  3. Replace the last unsorted element with the first

The heap is created by going through the penultimate row of the binary tree using the heapify function, from right to left until the end of the array. Then the first number swap is made in the loop, after which the first element falls/stays in place, as a result of which the largest element gets to the first place, the loop is repeated with the participants decreasing by one, since after each pass at the end of the list there are sorted numbers.

Heapsort example in Ruby:






module Colors



    BLUE = "\033[94m"



    RED = "\033[31m"



    STOP = "\033[0m"



end







def heapsort(rawNumbers)



    numbers = rawNumbers.dup







    def swap(numbers, from, to)



        temp = numbers[from]



        numbers[from] = numbers[to]



        numbers[to] = temp



    end







    def heapify(numbers)



        count = numbers.length()



        lastParentNode = (count - 2) / 2







        for start in lastParentNode.downto(0)



            siftDown(numbers, start, count - 1)



            start -= 1 



        end







        if DEMO



            puts "--- heapify ends ---"



        end



    end







    def siftDown(numbers, start, rightBound)      



        cursor = start



        printBinaryHeap(numbers, cursor, rightBound)







        def calculateLhsChildIndex(cursor)



            return cursor * 2 + 1



        end







        def calculateRhsChildIndex(cursor)



            return cursor * 2 + 2



        end            







        while calculateLhsChildIndex(cursor) <= rightBound



            lhsChildIndex = calculateLhsChildIndex(cursor)



            rhsChildIndex = calculateRhsChildIndex(cursor)







            lhsNumber = numbers[lhsChildIndex]



            biggerChildIndex = lhsChildIndex







            if rhsChildIndex <= rightBound



                rhsNumber = numbers[rhsChildIndex]



                if lhsNumber < rhsNumber



                    biggerChildIndex = rhsChildIndex



                end



            end







            if numbers[cursor] < numbers[biggerChildIndex]



                swap(numbers, cursor, biggerChildIndex)



                cursor = biggerChildIndex



            else



                break



            end



            printBinaryHeap(numbers, cursor, rightBound)



        end



        printBinaryHeap(numbers, cursor, rightBound)



    end







    def printBinaryHeap(numbers, nodeIndex = -1, rightBound = -1)



        if DEMO == false



            return



        end



        perLineWidth = (numbers.length() * 4).to_i



        linesCount = Math.log2(numbers.length()).ceil()



        xPrinterCount = 1



        cursor = 0



        spacing = 3



        for y in (0..linesCount)



            line = perLineWidth.times.map { " " }



            spacing = spacing == 3 ? 4 : 3



            printIndex = (perLineWidth / 2) - (spacing * xPrinterCount) / 2



            for x in (0..xPrinterCount - 1)



                if cursor >= numbers.length



                    break



                end



                if nodeIndex != -1 && cursor == nodeIndex



                    line[printIndex] = "%s%s%s" % [Colors::RED, numbers[cursor].to_s, Colors::STOP]



                elsif rightBound != -1 && cursor > rightBound



                    line[printIndex] = "%s%s%s" % [Colors::BLUE, numbers[cursor].to_s, Colors::STOP]



                else



                    line[printIndex] = numbers[cursor].to_s



                end



                cursor += 1



                printIndex += spacing



            end



            print line.join()



            xPrinterCount *= 2           



            print "\n"            



        end



    end







    heapify(numbers)



    rightBound = numbers.length() - 1







    while rightBound > 0



        swap(numbers, 0, rightBound)   



        rightBound -= 1



        siftDown(numbers, 0, rightBound)     



    end







    return numbers



end







numbersCount = 14



maximalNumber = 10



numbers = numbersCount.times.map { Random.rand(maximalNumber) }



print numbers



print "\n---\n"







start = Time.now



sortedNumbers = heapsort(numbers)



finish = Time.now



heapSortTime = start - finish







start = Time.now



referenceSortedNumbers = numbers.sort()



finish = Time.now



referenceSortTime = start - finish







print "Reference sort: "



print referenceSortedNumbers



print "\n"



print "Reference sort time: %f\n" % referenceSortTime



print "Heap sort:      "



print sortedNumbers



print "\n"



if DEMO == false



    print "Heap sort time:      %f\n" % heapSortTime



else



    print "Disable DEMO for performance measure\n"



end







if sortedNumbers != referenceSortedNumbers



    puts "Validation failed"



    exit 1



else



    puts "Validation success"



    exit 0



end

Without visualization, this algorithm is not easy to understand, so the first thing I recommend is to write a function that will print the current form of the binary tree.

Links

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/heapsort/heapsort.rb

Sources

http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
https://www.youtube.com/watch?v=LbB357_RwlY

https://habr.com/ru/company/ otus/blog/460087/

https://ru.wikipedia.org/wiki/Пыramidal_sorting

https://neerc.ifmo.ru/wiki /index.php?title=Heap_sort

https://wiki5.ru/wiki/Heapsort

https://wiki.c2.com/?HeapSort

https://ru.wikipedia.org/wiki/Tree (data structure)

https://ru.wikipedia.org/wiki/Heap (data structure)

https://www.youtube.com/watch?v=2DmK_H7IdTo

https://www.youtube.com/watch?v=kU4KBD4NFtw

https://www.youtube.com/watch?v=DU1uG5310x0

https://www.youtube.com/watch?v =BzQGPA_v-vc

https://www.geeksforgeeks.org/ array-representation-of-binary-heap/

https://habr.com/ru/post/112222/

https://www.cs.usfca. edu/~galles/visualization/BST.html

https://www.youtube.com/watch?v=EQzqHWtsKq4

https://medium.com/@dimko1/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC% D1 %8B-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-heapsort-796ba965018b

https://ru.wikibrief.org/wiki/Heapsort

https://www.youtube.com/watch?v=GUUpmrTnNbw

Bumblebee All Troubles

Recently, it turned out that users of modern Nvidia GPUs under Arch Linux do not need to use the bumblebee package at all, for example, for me it did not detect an external monitor when connected. I recommend removing the bumblebee package and all related packages, and installing prime using the instructions on the Arch Wiki.
Next, to launch all games on Steam and 3D applications, add prime-run, for Steam this is done like this prime-run %command% in additional launch options.
To check the correctness, you can use glxgears, prime-run glxgears.
https://bbs.archlinux.org/viewtopic.php? pid=2048195#p2048195