Algoritmo per generare bordi e vertici verso l'esterno dall'origine con una molteplicità massima di 3

Question

Algoritmo per generare bordi e vertici verso l'esterno dall'origine con una molteplicità massima di 3

#1 da (2 voti)

11

Sto creando un gioco 2D per un sito Web in cui l'universo può diventare estremamente grande (praticamente infinitamente grande). Inizialmente, l'universo è composto da 6 stelle che sono a uguale distanza dall'origine (0, 0). Il mio compito è di essere in grado di generare più stelle che avranno "percorsi" (bordi) che si connettono tra loro. Come posso progettare un algoritmo che soddisfi queste restrizioni:

Le stelle vengono generate casualmente verso l'esterno. (ad es. (x, y) le coordinate per le nuove stelle lentamente andranno verso l'esterno da (0, 0) in tutte le direzioni, preferibilmente in formato a spirale)
I bordi NON si incroceranno.
Anche se ci dovrebbe essere qualche variazione, le nuove stelle non dovrebbero essere troppo lontane o troppo vicine ad altre stelle. (Ad esempio, deve esserci un raggio minimo)
Nessuna stella / punto dovrebbe avere una molteplicità di più di 3.
Dato che tutto questo verrà memorizzato in un database, l'algoritmo non può essere troppo costoso. In altre parole, mi piacerebbe ottenere qualcosa di O (n) complessità (non so se questo è fattibile).

In sostanza, quello che sto cercando è una galassia dall'aspetto a spirale in cui le stelle sono punti sul grafico e il viaggio tra le stelle è rappresentato dai bordi tra quelle stelle.

I passaggi particolari che devo risolvere sono:

Genera casualmente un punto nelle vicinanze vicine di altre stelle che non hanno ancora una molteplicità di 3.
Trova la prima stella che non ha ancora una molteplicità di 3 che non genererà conflitti da bordo.
Se la stella è una distanza minima di x unità, quindi crea un bordo tra i due punti.

Ho provato a cercare soluzioni, ma le mie abilità matematiche (e le conoscenze sulla Teoria dei grafi) richiedono molto lavoro. Inoltre, qualsiasi risorsa / link su questo argomento sarebbe molto apprezzato.

Ecco qualche pseudo-codice a cui stavo pensando, ma non sono sicuro che funzionerebbe e sono sicuro che non funzionerebbe molto bene dopo poche 10.000, ecc. stelle.

newStar = randomly generated (x, y) within radius of last star from origin
while(newStar has not been connected):
    for (star in the known universe):
        if(distance between newStar and star > x units):
            if(star has < 3 multiplicity):
                if(path from newStar to star does not intersect another path):
                    connect the star to the other star
                    break;

    newStar = new random (x, y) coordinate

Inoltre, se qualcuno ha qualche consiglio su come dovrei archiviarlo su un database MySQL, lo apprezzerei anche.

Infine, nel caso in cui nulla abbia senso sopra, ho incluso un'immagine di ciò che vorrei ottenere qui sotto:

php algorithms mysql graph graph-databases

posta John F. 12.01.2016 - 06:27

fonte

1 risposta

Leggi altre domande sui tag php algorithms mysql graph graph-databases

Ho ragione riguardo le differenze tra gli algoritmi di Floyd-Warshall, Dijkstra e Bellman-Ford? Modelli dell'interfaccia utente in lingue funzionali

score 2 · Answer 1

Suggerimento: mantenere la rete dell'universo interno perfettamente ordinata, algoritmica e relativamente semplice. Hai bisogno dell'universo solo per sembrare casuale quando viene visualizzato sullo schermo utente . Applicare solo offset casuali alle posizioni delle stelle per la visualizzazione utente.

Problema: l'approccio più ovvio di calcolare un offset casuale per ciascuna stella non è un ottimo lavoro nel nascondere la vera struttura sottostante. Puoi solo randomizzare le stelle di una piccola quantità prima che rischino di scontrarsi tra loro o incrociarsi.

Soluzione: puoi applicare grandi distorsioni casuali e ottenere un universo molto più casuale e interessante se applichi casualità coordinata non locale. Immagina di posizionare le stelle su un foglio di gomma e immagina di allungare e schiacciare casualmente diverse parti del foglio. Ciò può spostare un intero gruppo di stelle di una lunga distanza. Non si scontreranno o si incroceranno mai perché le stelle vicine si allungano e si squilibrano l'una con l'altra.

Come si fa: Cerca i generatori di terreno frattale. C'è un sacco di codice gratuito e aperto per questo. Hai solo bisogno di un codice di base che generi un valore di altezza per ogni punto su una mappa. Lo useremo in un modo diverso. Usa quel codice per generare DUE mappe indipendenti dell'altezza del terreno. Inizia con la posizione X, Y vera della stella, osserva quella posizione su ciascuna mappa, usa un valore di mappa per sfalsare la posizione di visualizzazione X della stella e usa l'altro valore della mappa per sfalsare la posizione di visualizzazione Y della stella. Dovrai giocare con alcuni dei fattori di ridimensionamento, ma ciò può darti l'effetto di foglio di gomma deformato a caso. Le grandi variazioni nella posizione della stella dovrebbero nascondere completamente le posizioni ordinate sottostanti. La natura frattale della casualità darà un effetto dall'aspetto molto naturale, con cose visivamente interessanti che apparentemente accadono in diverse regioni dell'universo.