Pathfinding estremo
Silver Drake
piccolo puzzle game che sto realizzando. E fin qui niente di più facile,
di risorse è pieno.
Il problema sta nel fatto che il pathfinding richiesto dal gioco è
alquanto particolare.
In pratica ho 2 o più entità e devono arrivare entrambe in un punto
d'arrivo tra quelli a disposizione senza cadere fuori dalla mappa. Il
pathfinding mi serve per calcolare il minimo numero di mosse necessario a
raggiungere il punto d'arrivo. E fin qui la cosa è ancora semplice.
Il problema nasce dal fatto che ogni volta che un'entità si muove in una
direzione tutte le altre entità si muovono con lei ma non nella stessa
direzione; la direzione che scelgono dipende comunque direttamente (e
senza alcuna discrezionalità) da quella scelta dalla prima entità.
Ho visto che ci sono risorse sul pathfinding cooperativo ma anche lì si
presume sempre che le mosse, per quanto legate, non siano forzate in
maniera così stretta. Avete idea di dove potrei trovare qualche
riferimento utile?
Grazie :)
See you,
Silver Drake
--
Paperblog: l'irriverente blog della famiglia pinguina
http://www.silverdrakenet.it/blog/blog.html
Quello che scrive il Drake è la verità (gg)
RADIO HELL: http://www.myspace.com/rh666
GPied...@gmail.com
> Il problema nasce dal fatto che ogni volta che un'entità si muove in una
> direzione tutte le altre entità si muovono con lei ma non nella stessa
> direzione; la direzione che scelgono dipende comunque direttamente (e
> senza alcuna discrezionalità) da quella scelta dalla prima entità.
Interessante questo algoritmo puoi spiegare meglio con qualche schema
quello che intendi?
Silver Drake
> Interessante questo algoritmo puoi spiegare meglio con qualche schema
> quello che intendi?
Che tipo di schema, esattamente?
GPied...@gmail.com
> On Thu, 17 Jul 2008 05:22:03 -0700, GPiedimo...@gmail.com wrote:
> > Interessante questo algoritmo puoi spiegare meglio con qualche schema
> > quello che intendi?
>
> Che tipo di schema, esattamente?
>
> See you,
> Silver Drake
> --
Non ho capito esattamente come deve comportasi questo pathfinding...
che significa che nn si possono muovere nella stessa direzione? quante
direzioni posso avere? le diagonali? e un terreno o sono mattoncini?
Silver Drake
> Non ho capito esattamente come deve comportasi questo pathfinding... che
> significa che nn si possono muovere nella stessa direzione? quante
> direzioni posso avere? le diagonali? e un terreno o sono mattoncini?
Teoricamente possono muoversi anche nella stessa direzione, ma questo
dipende dalle caratteristiche delle mappa.
In pratica c'è un tabellone a caselle. Ognuna di queste caselle indica
una delle otto direzioni possibili, ed è impostata a random quando viene
lanciato il livello.
Mettiamo che l'entità A sia su una casella che "va" a destra e B sia su
una casella che "va" in basso a sinistra:
- A va avanti (quindi a destra), B va in basso a sinistra.
- A va a destra (quindi in basso), B va in alto a sinistra.
Una volta mosse, le entità si trovano su caselle che avranno un
orientamento, come abbiamo detto casuale, quindi potrebbero anche
trovarsi entrambe su caselle che vanno in alto, per esempio.
Una cosa che "semplifica" la vita è che il movimento utilizzabile è
sempre nelle quattro direzioni cardinali rispetto alla direzione della
casella su cui ci si trova; anche perché già così le sinapsi dei
giocatori fumano abbastanza :)
Spero di aver reso l'idea in maniera un po' più chiara.
GPied...@gmail.com
> See you,
> Silver Drake
Ok molto piu chiaro, nn appena ho un attimo ci penso su.
GPied...@gmail.com
wrote:
Dunque ci stavo pensando mentre lavoravo... (si nn faccio un lavoro
divertentissimo... stavo disegnando un dataset...) comunque condivido
con te la mia idea, poi vediamo cosa salta fuori.
Dunque ti comporti come con un semplicissimo pathfinding 2D, ovvero
calcoli la strada piu corta evitando i wall o hole con la seguente
modifica alla logica.
Ad ogni turno ricalcoli il pathfinding per ogni pedina, considerando
un wall "immaginario" nella direzione in cui la pedina precedente si e
mossa. Cosi per ogni pedina aggiungendo un wall immaginario ad ogni
pedina.
Vediamo se riesco a fare un esempio:
Le caselle piene di "!" sono da considerarsi con calpestabili
Al primo turno la mappa va considerata cosi:
_____ _____ _____ _____ _____
| | | | | |
| A->| | | | |
|_____|_____|_____|_____|_____|
| | | ! ! | | |
| | |! ! !| | |
|_____|_____|_!_!_|_____|_____|
| | | | | |
| | | | | |
|_____|_____|_____|_____|_____|
| | | | | |
| | | | | |
|_____|_____|_____|_____|_____|
Il calcolo di B va calcolato con un muro immaginario in piu
_____ _____ _____ _____ _____
| | | | | |
| A->| | | | |
|_____|_____|_____|_____|_____|
| | ! ! | ! ! | | |
| B |! ! !|! ! !| | |
|_____|_!_!_|_!_!_|_____|_____|
| | | | | |
| | | | | |
|_____|_____|_____|_____|_____|
| | | | | |
| | | | | |
|_____|_____|_____|_____|_____|
Che ne dici?
qui trovi un normale Pathfinding 2D: http://www.policyalmanac.org/games/aStarTutorial.htm
Silver Drake
> On 17 Lug, 15:14, "GPiedimo...@gmail.com" <GPiedimo...@gmail.com> wrote:
>> On 17 Lug, 14:48, Silver Drake <silverdr...@email.it> wrote:
>>
>> > See you,
>> > Silver Drake
>>
>> Ok molto piu chiaro, nn appena ho un attimo ci penso su.
>
> Dunque ci stavo pensando mentre lavoravo... (si nn faccio un lavoro
> divertentissimo... stavo disegnando un dataset...) comunque condivido
> con te la mia idea, poi vediamo cosa salta fuori.
>
> Dunque ti comporti come con un semplicissimo pathfinding 2D, ovvero
> calcoli la strada piu corta evitando i wall o hole con la seguente
> modifica alla logica.
>
> Ad ogni turno ricalcoli il pathfinding per ogni pedina, considerando un
> wall "immaginario" nella direzione in cui la pedina precedente si e
> mossa. Cosi per ogni pedina aggiungendo un wall immaginario ad ogni
> pedina.
[...]
> Che ne dici?
Sembra molto interessante, provo a studiarmelo per bene.
Grazie mille :)