Безрекурсивный алгоритм обхода N-мерных деревьев Константина Тарасенкова
Проснувся, голодненький, начал думать что мне нужен алгоритм обхода двумерного дерева но без рекурсий, так как выполнять я его буду в while цикле на GPU, а многие GPU языки программирования, особенно графические, рекурсию не умеют, поэтому остаётся только придумать безрекурсивный алгоритм.
И придумал. Где-то за час. Не знаю, есть уже такой или нет, но на всякий случай назову его своим именем: "Безрекурсивный алгоритм обхода N-мерных деревьев Константина Тарасенкова".
Почему я публикую это в раздел gamedev? Потому что это алгоритм обхода BVH нод для GPU рей трейсера. :)
Для простоты примера возьмём двумерное дерево, хоть и алгоритм может работать с любой мерностью деревьев.
Каждая нода дерева возвращает правду (t) или ложь (f) -- нужно ли продолжать обход ветвей этой ноды или нет.
Наша цель, которую мы хотим найти, это правда (t) в конечной ветви дерева, которая в данном примере находится только в ноде под индексом 3.
В данном примере, дерево и его ноды выглядят так:
........... 0t ..........
.... 1t ....... 2t .....
.. 3t 4f ... 5f 6f ..
Для вычисления алгоритма дополнительно требуется только одно число (итератор, далее будет выглядеть как i) и один массив чисел (далее массив будет выглядеть как [индекс ноды, индекс ноды, ...])
Алгоритм состоит из 5-ти условий, можете пропустить читать их, они будут более понятны чуть позже:
1. Если итератор равен нулю, и текущая нода массива под итератором имеет индекс -1, -- терминация всего алгоритма.
2. Если текущая нода массива под итератором имеет индекс -1, -- декремент итератора на 1.
3. Если текущая нода массива под итератором имеет индекс не -1 и возвращает ложь (f), -- замена индекса этой ноды в массиве на -1, декремент итератора на 1.
4. Если текущая нода массива под итератором имеет индекс не -1 и возвращает правду (t), -- замена индекса этой ноды в массиве на -1, если нода является промежуточной, добавляем все индексы её ветвей в массив после текущего значения итератора, инкремент итератора на количество добавленных ветвей.
5. Если достигнута конечная ветвь дерева, и нода возвращает правду, -- успех, миссия выполнена, либо останавливаем весь алгоритм на одной найденной правде конечной ветви дерева, либо продолжаем итерацию если нужно найти несколько конечных ветвей с правдой.
Алгоритм прост как автомат калашникова (все мои алгоритмы просты как автомат калашникова, потому что я люблю простоту автомата калашникова), давайте посмотрим на его действие на каждой итерации while цикла:
i = 0
[*0]
правда, заменяем индекс ноды на -1, добавляем индексы всех ветвей ноды в конец массива после значения i, икремент i на количество ветвей (i += 2)
i = 2
[-1, 1, *2]
правда, заменяем индекс ноды на -1, добавляем индексы всех ветвей ноды в конец массива после значения i, икремент i на количество ветвей (i += 2)
i = 4
[-1, 1, -1, 5, *6]
ложь, заменяем индекс ноды на -1, декремент i на 1 (i -= 1)
i = 3
[-1, 1, -1, *5, -1]
ложь, заменяем индекс ноды на -1, декремент i на 1 (i -= 1)
i = 2
[-1, 1, *-1, -1, -1]
пропускаем -1, декремент i на 1 (i -= 1)
i = 1
[-1, *1, -1, -1, -1]
правда, заменяем индекс ноды на -1, добавляем индексы всех ветвей ноды в конец массива после значения i, икремент i на количество ветвей (i += 2)
i = 3
[-1, -1, 3, *4, -1]
ложь, заменяем индекс ноды на -1, декремент i на 1 (i -= 1)
i = 2
[-1, -1, *3, -1, -1]
правда + достигнута конечная ветвь дерева -- миссия выполнена. :)
На этом всё. :)
Edit: максимальный размер массива индексов похоже здесь заранее известен: (максимальная длинна ветвей вглубь * максимальная ширина ноды) - (максимальная ширина ноды - 1)
Другие мною придуманные алгоритмы можно заценить вот в этом моём ютюб плейлисте, например последним был ligma, мой уникальный алгоритм парсера математических выражений для любого языка программирования: https://www.youtube.com/playlist?list=PLvcobyidYcZ2MnOzhhPkbG7hwRbwoNDQU
Мои аккаунты в социальных сетях: https://dtf.ru/redgpu/4056166-moi-igrovye-profili-nya