Algoritmo del percorso rettilineo semplice [chiuso]

Algoritmo di Dijkstra

Potresti applicare l'algoritmo che A * è basato su: l'algoritmo di Dijkstra con l'assunto che viaggiare per il nodo adiacente è uguale. Questo ti darà comunque il percorso più breve (o percorsi come la tua rete può variare) Tuttavia potresti comunque vederlo come eccessivo (dato che non fai menzione del percorso più breve, solo di lineare)

Implementa te stesso PathFinding di base

Ti suggerisco di dare un'occhiata al tutorial per la ricerca dei percorsi del Beginner Artificial Depot Beginner. Contiene pseudocodice per un algoritmo di ricerca del percorso molto semplicistico e spiega le basi della logica necessaria per comprenderle e implementarle. Ho incluso lo pseudocodice sotto per il tuo beneficio:

 create a list P
 add the start node S, to P giving it one element
 Until first path of P ends with G, or P is empty
    extract the first path from P
    extend the path one step to all neighbors creating X new paths
    reject all paths with loops
    add each remaining new path to P
 If G found -> success. Else -> failure.

Si prega di notare che

"This also assumes there is a tree or network from which contains the paths to be followed."

A * - Ma più semplice

Oltre a questo puoi ancora usare l'algoritmo A * e fare semplicemente un semplice valutatore per determinare l'euristica per il miglior passo successivo. In tal caso sarebbe molto semplice usare la distanza euclidea (pensate alla distanza assoluta) per ottenere il vostro percorso. Se sei interessato, ho scoperto che ho imparato molto dal tutorial di Patrick Lester per principianti e da Articolo su Coca-Cola e codice su A * .

Spero che questo ti aiuti a implementare ciò che stai cercando.

Se stai cercando di trovare un percorso attraverso una serie di quadrati di terreno, o un percorso attraverso un insieme di nodi connessi, allora l'attraversamento in ampiezza o prima in profondità funziona bene. (Un trucco per limitare le dimensioni della traversata per fare una ricerca in ampiezza, ma iniziare una traversata sia al punto iniziale che al punto finale, e fermarsi alla prima cella che entrambi hanno raggiunto.)

Tuttavia, se stai disegnando una linea da A a B su qualche griglia, allora funzionano gli algoritmi di disegno di base. Una versione classica è l'algoritmo di riga di Bresenham , che è piuttosto semplice.

Se vuoi una versione più semplice che distribuisca solo passi sull'asse X con passi sull'asse Y, sembra proprio questo. È un po 'come "divisione aggiungendo". Questo è solo il fondamento: un sacco di spazio per miglioramenti! (Python)

def line(x0, y0, x1, y1):

    # number of steps x and y
    mx = abs(x1 - x0)
    my = abs(y1 - y0)

    # the greater number of steps
    steps = max(mx, my)
    sx = 0
    sy = 0

    x = x0
    y = y0
    path = [(x0, y0)]

    while x != x1 or y != y1:
        sx += mx
        sy += my

        if sx >= steps:
            sx -= steps
            x += 1  # only one direction for now

        if sy >= steps:
            sy -= steps
            y += 1  # only one direction for now

        #print((sx, sy, mx, my))

        path.append((x,y))

    return path

if __name__ == '__main__':
    print(line(0, 0, 8, 8))
    print(line(0, 0, 4, 8))
    print(line(0, 0, 8, 4))
    print(line(0, 0, 0, 8))
    print(line(0, 0, 8, 0))

Ho usato questo algoritmn per creare archi circolari o ellittici, linee oblique (cioè uno che arriva al bersaglio con una leggera angolazione), percorsi perpendicolari, o anche solo correre direttamente dal bersaglio! Probabilmente ho trascorso più tempo su questo di quanto avrei dovuto da giovane. ;)

...

Un altro pensiero; se stai programmando un algoritmo di "caccia", in cui un robot insegue un bersaglio, allora ci sono alcune divertenti varianti su questo. Non devi calcolare il percorso completo.

• Sposta diagonalmente o lungo un asse: x += 1 if x1 > x0 , x -= 1 if x1 < x0

• Sposta lungo linee di 45 gradi: x += 1 if dx > dy / 2 ecc.

Un altro divertente è quello di spostare il robot x += dx / 10 ... mentre non sta facendo passi costanti, diventa uno schermo piuttosto interessante se hai un gruppo di robot sparsi casualmente che si rincorrono.

...

Un altro pensiero. Questo funziona quando x e y sono dimensioni spaziali (come in una griglia o in una matrice), ma funziona anche se una delle dimensioni è tempo . Ad esempio, se desideri distribuire 5 messaggi in 8 secondi, puoi considerare y come tempo e utilizzare lo stesso ciclo per distribuire un certo numero di eventi in un lasso di tempo.

La tua domanda potrebbe essere posizionata meglio su gamedev , ma se non sei preoccupato per il terreno e / o i muri, allora cosa voglio non un algoritmo di individuazione del percorso. La differenza tra i due punti (o vettori) è il "passo" richiesto per passare dal punto A al punto B immediatamente . Devi quindi semplicemente dividere la differenza, utilizzando una certa quantità, per determinare il "passo" e applicare ogni fotogramma.