Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Scrivo in c++, ma in realtà il mio quesito si potrebbe generalizzare
Forum - C/C++ - Scrivo in c++, ma in realtà il mio quesito si potrebbe generalizzare

Avatar
3E8b12 (Normal User)
Newbie


Messaggi: 11
Iscritto: 08/11/2015

Segnala al moderatore
Postato alle 11:36
Domenica, 08/11/2015
Salve a tutti, la mia domanda è:
Partendo da una matrice (immaginate una scacchiera 8*8) come faccio da un qualsiasi punto A(x,y) a raggiungere un qualsiasi punto B(x,y) della scacchiera, senza andare in diagonale?
Immaginate pacman.
Nel momento in cui si ha la possibilità di mangiare i fantasmini, essi muteranno sprite e diventeranno degli occhi, che, indifferentemente dalla posizione, torneranno sempre nella loro "base" per rigenerarsi.
Avete qualche suggerimento?

EDIT: Chiaramente, scegliendo sempre la strada "più breve"


3E8b12 ha allegato un file: chessboard.png (1844 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da 3E8b12 il 08/11/2015 alle 11:39
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6380
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 11:58
Domenica, 08/11/2015
Dato che il problema si riduce al tracciamento di una linea tra due pixel in un array di pixel, puoi usare l'algoritmo di Bresenham, magari adattandolo un po' ...

http://www.roguebasin.com/index.php?title=Bresenham%27s_Li ...

Ultima modifica effettuata da nessuno il 08/11/2015 alle 12:12


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
Ultimo (Member)
Guru


Messaggi: 877
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 12:13
Domenica, 08/11/2015
Avevo visto in questo sito dei programmi per la risoluzione dei labirinti (Maze) in particolare uno in C molto rapido
nel trovare il percorso giusto e più breve.


http://www.pierotofy.it/pages/search/search.php?query=Maze ...

Ultima modifica effettuata da Ultimo il 08/11/2015 alle 12:19


If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
3E8b12 (Normal User)
Newbie


Messaggi: 11
Iscritto: 08/11/2015

Segnala al moderatore
Postato alle 14:15
Domenica, 08/11/2015
Testo quotato

Postato originariamente da nessuno:

Dato che il problema si riduce al tracciamento di una linea tra due pixel in un array di pixel, puoi usare l'algoritmo di Bresenham, magari adattandolo un po' ...

http://www.roguebasin.com/index.php?title=Bresenham%27s_Li ...


Potrebbe essere una possibile soluzione

Testo quotato

Postato originariamente da Ultimo:

Avevo visto in questo sito dei programmi per la risoluzione dei labirinti (Maze) in particolare uno in C molto rapido
nel trovare il percorso giusto e più breve.

http://www.pierotofy.it/pages/search/search.php?query=Maze ...


non mi ispira tanto l'idea di pensarla come un labirinto, non so onestamente quanto possa essere efficiente

PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 449
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 14:02
Martedì, 10/11/2015
Ma hai dei constraint (tipo muri come in pacman) o puoi muoverti liberamente?
Inoltre puoi muoverti solo spostandoti in caselle adiacenti ma non quelle diagonali giusto?
Se è questo il caso supponi di trovarti a x0, y0 e che il punto che vuoi raggiungere sia x1, y1: la distanza minima che puoi percorrere è di m = |x1-x0| + |y1-y0| caselle e ci sono m!/((|x1-x0|)!(|y1-y0|)!) percorsi con questa lunghezza minima.
Quindi ti basterebbe ad esempio prendere il percorso che forma un triangolo rettangolo.

Ultima modifica effettuata da lumo il 10/11/2015 alle 14:06
PM Quote
Avatar
3E8b12 (Normal User)
Newbie


Messaggi: 11
Iscritto: 08/11/2015

Segnala al moderatore
Postato alle 1:43
Sabato, 14/11/2015
Testo quotato

Postato originariamente da lumo:

Ma hai dei constraint (tipo muri come in pacman) o puoi muoverti liberamente?
Inoltre puoi muoverti solo spostandoti in caselle adiacenti ma non quelle diagonali giusto?
Se è questo il caso supponi di trovarti a x0, y0 e che il punto che vuoi raggiungere sia x1, y1: la distanza minima che puoi percorrere è di m = |x1-x0| + |y1-y0| caselle e ci sono m!/((|x1-x0|)!(|y1-y0|)!) percorsi con questa lunghezza minima.
Quindi ti basterebbe ad esempio prendere il percorso che forma un triangolo rettangolo.



anche questa potrebbe essere una validissima soluzione:k:
anche se implementare questa roba sulla mappa di pacman, che non è proprio una scacchiera, è un po' più tedioso...

Ultima modifica effettuata da 3E8b12 il 14/11/2015 alle 1:48
PM Quote