Condado Braveheart

Isso, o Cherry eu sei que ainda está ativo, mas o Bananen-Joe faz um bom tempo que não ouço dele.
Exato, reservei uma variável pra cada peso, mas pra evitar essa treta eu fiz um esqueminha para que elas sejam alocadas dinamicamente. Eu testei em um mapa de 500x500 e fica realmente puxado. O limite ideal que achei foi lá por volta dos 100x100 onde a performance do sistema ainda fica desejável.

Pô, se tu conseguiu usar em um mapa com área de 10_000 tiles, ou o tu tá fazendo alguma bruxaria pra usar mais que 9_999 variáveis ou tá fazendo de uma forma bem melhor do que eu imaginei. xD
Na prática, tu tá reservando quantas variáveis no pior caso?

Quando quero alocar uma quantidade enorme de variáveis eu uso somente ponteiros. Nesse caso temos uma única variável que aponta para diferentes endereços, independente do limite de variáveis do seu jogo. É claro que pra não quebrar o jogo, esses endereços devem estar fora do limite de variáveis.

Por exemplo: se seu jogo tem 100 variáveis, eu preciso alocar a partir do endereço 101. Pra ter acesso a esses endereços, somente através de ponteiros.

Sim! Também uso ponteiros em todo lugar. Deus me livre de alocar cada endereço manualmente. xD
Mas por incrível que pareça, as vezes penso que vou precisar de mais do que 9999 variáveis, e isso ponteiro não resolve. haha'

Rapaz, com ponteiro vc vai até 999.999. O tamanho máximo do mapa vc precisaria de 250k. Mas pra não alocar 250k para um mapa de 20x15, aí a gente aloca de forma dinâmica, nesse caso somente 300

Por exemplo, eu acabei de fazer uma implementação de QuickSort aqui, no RM2003. Como é um algorítimo que depende de recursão, há um ponteiro que indica a "profundidade" da thread, sendo que cada thread precisa de 3 variáveis reservadas. Nos meus testes, em uma array de tamanho 100, o máximo de threads que usei foram 20... Ou seja, só nessa brincadeira já foram umas 160 variáveis, e é só a cereja do bolo. xD

Pois é... Tem certos algoritmos que no 2003 fica puxado. No A* eu usei a estrutura Heap, que não precisa de tantas tantas variáveis auxiliares como o caso da QuickSort. Aí o resto como a heurística, por exemplo, foi na matemática mesmo pra não ter que alocar mais variáveis

Pera, realmente da pra usar além da variável 9999 utilizando ponteiros. Mdsss, eu sempre achei que internamente as variáveis eram uma array estática e se eu tentasse usar além daria erro. uahsuhasuhae'
Só é um saco não poder ver no editor, mas já é algo. xD

E quanto ao Quicksort, não vale a pena. A performance do fucking Insertion Sort (e até o Bubble!) foi melhor do que a dele nos meus testes. uhasuhae' (Na verdade meu corações ficou um pouco dilacerado com isso :c)

Aí nesse caso pra vc depurar esses valores eu uso o Show Message e um caderninho do lado (ou o OneNote aberto) anotando as casas do array pra eu imaginar kkkkkkk !!

Realmente a Insertion Sort é bem mais rápida que a QuickSort.

Insertion Sort tem uma complexidade média de O(n²), enquanto que o Quick de O(n log). Na teoria deveria ser mais rápido, mas na prática não foi bem assim. haha'

QuickSort só ganha da BubbleSort kkkkkkk !!

A complexidade é assintótica jorge, é mais uma análise quando os termos tendem a infinito do que para termos pequenos.

O insertion sort apesar de n^2 costuma ser mais rápido pra listas pequenas, porque a quantidade e complexidade das operações que ele faz é menor que a do quick sort. Pra listas maiores, quick sort vai ser melhor (apesar que o n log n é caso médio, dá pra tirar n^2 com quick sort se você pegar o pivô errado).

Sim, a minha surpresa era que eu estava usando arrays grandes (de tamanho +100) e mesmo o insertion tinha performance melhor. Lendo um pouco, soube que o quick performa mal em arrays já ordenadas, então o problema parece até meio obvio agora. uhausaaea'

Como estou usando o algoritmo de sort pra determinar a ordem de renderização das imagens, dando prioridade aquelas que tem maior posição Y, considerando que elas quase sempre estão em posições iguais, a array é ordenada uma vez e em seguida fica sofrendo pra ordenar de novo o que já está praticamente ordenado, o que seria algo próximo ao pior caso, O(n²).

Aí faz sentido ahushaus
Uma alternativa é você fazer uma passagem inicial só pra determinar se está ordenado (isso é O) e só depois ordenar usando algum algoritmo O(n log n), possivelmente merge sort que é garantido ter essa complexidade. O(n log n + n) ainda é O(n log n).

Outro jeito é mandar um Tim Sort, igual python

Pô, eu pensei exatamente isso! Mas me pareceu um pouco selvagem. xD
Vou dar uma olhada nesse aí. o/

E por curiosidade: Se eu der um shuffle na array sempre antes do sort, a performance melhora consideravelmente. uahsuhaea'