Дерево квадрантов по сравнению с Красно-черным деревом для игры в C++?

См. Нижеприведенный код:

package blob;

import com.microsoft.azure.storage.CloudStorageAccount;
import com.microsoft.azure.storage.blob.*;

import java.net.URI;
import java.util.*;

public class ListBlobBySasToken {
    public static void main(String[] args) throws Exception {
        String storageConnectionString = "DefaultEndpointsProtocol=https;AccountName=***;AccountKey=***;EndpointSuffix=core.windows.net";

        CloudStorageAccount storageAccount = CloudStorageAccount.parse(storageConnectionString);
        CloudBlobClient blobClient = storageAccount.createCloudBlobClient();
        CloudBlobContainer container = blobClient.getContainerReference("jay");

        String sasToken = generateSAS(container,true);
        System.out.println(sasToken);
        String sasUrl = container.getUri()+ sasToken;

        //Then use sasUrl to init container1
        CloudBlobContainer container1 = new CloudBlobContainer(new URI(sasUrl));
        CloudBlob blob = container1.getBlockBlobReference("test.json");
        System.out.println(blob.getStorageUri());
    }

    private static String generateSAS(CloudBlobContainer container, boolean readonly) throws Exception {
        // Create a container if it does not exist.
        container.createIfNotExists();
        // Create a new shared access policy.
        SharedAccessBlobPolicy sasPolicy = new SharedAccessBlobPolicy();
        // Create a UTC Gregorian calendar value.
        GregorianCalendar calendar = new GregorianCalendar(TimeZone.getTimeZone("UTC"));
        // Specify the current time as the start time for the shared access
        // signature.
        //
        calendar.setTime(new Date());
        sasPolicy.setSharedAccessStartTime(calendar.getTime());
        // Use the start time delta one hour as the end time for the shared
        // access signature.
        calendar.add(Calendar.HOUR, 10);
        sasPolicy.setSharedAccessExpiryTime(calendar.getTime());
        if (readonly) {
            // Set READ permissions
            sasPolicy.setPermissions(EnumSet.of(SharedAccessBlobPermissions.READ, SharedAccessBlobPermissions.LIST));
        } else {
            // Set READ and WRITE permissions.
            //
            sasPolicy.setPermissions(EnumSet.of(SharedAccessBlobPermissions.READ, SharedAccessBlobPermissions.WRITE, SharedAccessBlobPermissions.LIST));
        }
        // Create the container permissions.
        BlobContainerPermissions containerPermissions = new BlobContainerPermissions();
        // Turn public access to the container off.
        containerPermissions.setPublicAccess(BlobContainerPublicAccessType.OFF);
        container.uploadPermissions(containerPermissions);
        // Create a shared access signature for the container.
        String sas = container.generateSharedAccessSignature(sasPolicy, null);
        // HACK: when the just generated SAS is used straight away, we get an
        // authorization error intermittently. Sleeping for 1.5 seconds fixes that
        // on my box.
//        Thread.sleep(1500);
        // Return to caller with the shared access signature.
        return sas;
    }
}

Более подробную информацию см. В этой статье .

8
задан Brock Woolf 16 December 2008 в 14:45
поделиться

6 ответов

Деревья квадрантов используются, когда только необходимо сохранить вещи, которые находятся эффективно на плоскости. Как единицы в классическом РТС, где они - все на земле или просто немного выше его. По существу каждый узел имеет ссылки на 4 детей, которые делят пространство узла на равномерно распределенные четверти.

Деревья октантов делают то же, но во всех трех измерениях, а не всего два, и таким образом они имеют 8 дочерних узлов и делят пространство в восьмерки. Они должны использоваться, когда игровые объекты распределяются более равномерно среди всех трех измерений.

При поиске двоичного дерева - как красно-черное дерево - затем Вы хотите использовать структуру данных, названную двоичным деревом распределения пространства (дерево BSP), или версия его назвала Дерево KD. Они делят пространство в половины с помощью плоскости, в дереве KD плоскости являются ортогональными (на XZ, XY, осях ZY) поэтому иногда, это работает лучше в 3D сцене. Деревья BSP делят сцену с помощью плоскостей в любой ориентации, но они могут быть довольно полезными, и они еще использовались Гибель.

Теперь, потому что Вы разделили игровое пространство, Вы теперь не должны тестировать каждый игровой объект против любого игрового объекта, чтобы видеть, сталкиваются ли они, который является O (n^2) алгоритм в лучшем случае Вместо этого Вы запрашиваете структуру данных, чтобы возвратить игровые объекты в подобласти игрового пространства и только выполнить обнаружение коллизий для тех узлов друг против друга.

Это означает, что обнаружение коллизий для всех игровых объектов должно быть n O (nlogn) операция (в худшем случае).

Несколько дополнительных вещей не упустить:

  • Удостоверьтесь, что Вы тестируете игровые объекты от соседних узлов, не только тех в текущем узле, так как они могли все еще столкнуться.
  • Восстановите равновесие структуры данных после того, как объекты переместились, так как у Вас могут быть пустые узлы в структуре данных теперь или, которые содержат слишком много объектов для хорошей производительности (также вырожденный случай всех объектов, находящихся в том же узле).
18
ответ дан 5 December 2019 в 05:00
поделиться

Красно-черное дерево не является пространственным индексом; это может только отсортировать на единственном порядковом ключе. Дерево квадрантов является (для двух размеров) пространственным индексом, который позволяет быстрый поиск и устранение точек. Дерево октантов делает то же самое для трех измерений.

10
ответ дан 5 December 2019 в 05:00
поделиться

Я тепло предлагаю, чтобы Вы использовали механизм визуализации, Ogre3D, например. Насколько я знаю, что это поддерживает Деревья октантов для управления сценой. Но можно расширить Основанный на дереве октантов класс, как Вы желаете. Я раньше кодировал материал, в котором я нуждался один, но для сложных проектов, это - просто не правильный путь.

3
ответ дан 5 December 2019 в 05:00
поделиться

Причина использовать дерево квадрантов состоит в том, потому что можно затем разделить на x-и y-координатах, дереве октантов на x, y и z, делая обнаружение коллизий тривиальным.

Дерево квадрантов: если элемент не находится в верхнем левом, это, привычка сталкивается с одной в верхнем правом, нижнем левом или нижнем правом.

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

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

5
ответ дан 5 December 2019 в 05:00
поделиться

Деревья в целом проблематичны для этого, в котором любой вставленный объект может лечь на границу, и все методы справления с той ситуацией являются довольно неудовлетворительными.

Вы, скорее всего, захотите отсортировать свои объекты в подвижный и статическое, и проверить что-либо, что переместилось в данный кадр против статических объектов.

Деревья BSP являются принятым решением для статической геометрии (граничные случаи, обработанные путем разделения объекта на две части) для динамической попытки что-то как Вид и Развертка (также известный как Развертка и Чернослив).

0
ответ дан 5 December 2019 в 05:00
поделиться

На данный момент STANN - лучшая реализация с открытым исходным кодом.

http://sites.google.com/a/compgeom.com/stann/

0
ответ дан 5 December 2019 в 05:00
поделиться
Другие вопросы по тегам:

Похожие вопросы: