Algoritmo per videogame

Messaggioda Senzacervello » 06/11/2019, 11:18

Ciao a tutti. Spero che questo mio topic non sia fuori luogo, ma mi sto interrogando da tempo sul miglior modo di risolvere un problema specifico che mi sta torturando.

Descrivo: In un semplice videogame che sto disegnando con alcuni amici, abbiamo il problema di determinare l'utilizzo ottimale del carburante per un certo numero automobili impegnate in una corsa. In sostanza, ogni automobile ha un suo ammontare massimo di carburante alla partenza e consuma quantita' di carburante variabili in funzione della velocita'.

Le velocita' sono tre ognuna delle quali comporta un diverso consumo di combustibile al secondo.

Lo scopo e' trovare un algoritmo che calcoli il tempo minimo di percorrenza date la lunghezza del tracciato, la quantita' di carburante e le velocita' utilizzabili.

Quindi, date la lunghezza del tracciato (L) e la quantita' di carburante (C) e sapendo che

- alla velocita' V1 l'auto percorre "x" metri al secondo e consuma "x1" unita' di carburante;
- alla velocita' V2 l'auto percorre "x*2" metri al secondo e consuma "x1*2,5" unita' di carburante;
- alla velocita' V3 l'auto percorre "x*4" metri al secondo e consuma "x1*6" unita' di carburante

come mi suggerite di impostare l'algortimo per trovare il tempo minimo possibile di percorrenza a condizione che l'auto non consumi piu' del 90% del totale del carburante (C)?

Spero di essermi espresso in modo comprensibile. Se qualcuno mi potesse dare un suggerimento sarei molto felice. Grazie comunque per la pazienza

Ciao

Mauro
Senzacervello
Starting Member
Starting Member
 
Messaggio: 2 di 4
Iscritto il: 06/11/2019, 10:38

Re: Algoritmo per videogame

Messaggioda axpgn » 07/11/2019, 11:43

Mi pare sia un problema più adatto alla sezione di "Ricerca operativa", lì sapranno darti migliori consigli sugli algoritmi più adatti.
Fai spostare il thread da un moderatore.
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14428 di 14471
Iscritto il: 20/11/2013, 22:03

Re: Algoritmo per videogame

Messaggioda vict85 » 07/11/2019, 12:24

Hai che \(s = vt\) e \(c = C_0 - kt\) dove \(s\) è lo spazio percorso, \(v\) la velocità scelta, \(c\) la quantità di carburante, \(C_0\) la dimensione del serbatoio, \(k\) il consumo di carburante al secondo e \(t\) il tempo in secondi.
Siccome stai ponento \(c = 0\) (hai finito il carburante), puoi ricavare \(t\) dalla seconda equazione. Ovvero hai che \(\displaystyle t = \frac{C_0}{k}\). A questo punto ricavi che \(\displaystyle s = \frac{v}{k}C_0\). Siccome C_0 è lo stesso per tutte le velocità, non ti resta che confrontare i \(\displaystyle\frac{v_i}{k_i}\).

Il primo è pari a \(1\), il secondo a \(\displaystyle\frac{4}{5}\) e il terzo \(\displaystyle\frac{2}{3}\). Quindi il primo è quello più conveniente in termini di spazio percorribile. Cosa piuttosto prevedibile dato che l'aumento di velocità è accompagnato da un aumento più alto nei consumi.

Se invece vuoi fissare lo spazio. Hai che \(\displaystyle t = \frac{s}{v}\). Sostituisci nell'altra equazione e ricavi che \(\displaystyle (C_0 - c) = k\frac{s}{v}\). Insomma ti basta a questo punto vedere se \( \displaystyle (C_0 - c) > \frac{9C_0}{10}\)
vict85
Moderatore
Moderatore
 
Messaggio: 9964 di 9977
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Algoritmo per videogame

Messaggioda Senzacervello » 07/11/2019, 12:42

vict85 ha scritto:Hai che \(s = vt\) e \(c = C_0 - kt\) dove \(s\) è lo spazio percorso, \(v\) la velocità scelta, \(c\) la quantità di carburante, \(C_0\) la dimensione del serbatoio, \(k\) il consumo di carburante al secondo e \(t\) il tempo in secondi.
Siccome stai ponento \(c = 0\) (hai finito il carburante), puoi ricavare \(t\) dalla seconda equazione. Ovvero hai che \(\displaystyle t = \frac{C_0}{k}\). A questo punto ricavi che \(\displaystyle s = \frac{v}{k}C_0\). Siccome C_0 è lo stesso per tutte le velocità, non ti resta che confrontare i \(\displaystyle\frac{v_i}{k_i}\).

Il primo è pari a \(1\), il secondo a \(\displaystyle\frac{4}{5}\) e il terzo \(\displaystyle\frac{2}{3}\). Quindi il primo è quello più conveniente in termini di spazio percorribile. Cosa piuttosto prevedibile dato che l'aumento di velocità è accompagnato da un aumento più alto nei consumi.

Se invece vuoi fissare lo spazio. Hai che \(\displaystyle t = \frac{s}{v}\). Sostituisci nell'altra equazione e ricavi che \(\displaystyle (C_0 - c) = k\frac{s}{v}\). Insomma ti basta a questo punto vedere se \( \displaystyle (C_0 - c) > \frac{9C_0}{10}\)


Il mio problema e' diverso e, molto probabilmente, non mi sono espresso in modo del tutto comprensibile. Durante la gara le auto possono cambiare velocita' in modo da percorrere il tracciato nel minor "t" possibile. Alla "v1" sicuramente l'auto puo' percorrere l'intero tracciato e preservare una quantita' di carburante superiore al vincolo posto (C_residuo >= C*0.1), ma avra' gareggiato in modo sub ottimale poiche', se avesse incrementato la velocita' per un certo periodo, avrebbe impiegato meno tempo.

L'algoritmo che vorrei individuare dovrebbe darmi come risultante, ferme le condizioni, per quanto tempo l'auto viaggia a v1 (minimo possibile in quanto e' la velocita' minore), a v2 (minimo possibile poiche' non e' la velocita' massima) e a v3 (massimo possibile perche' e' la velocita' massima).

Avveo pensato di ricorrere ad una matrice, ma forse e' una sciocchezza

Spero di essere stato piu' chiaro
Senzacervello
Starting Member
Starting Member
 
Messaggio: 3 di 4
Iscritto il: 06/11/2019, 10:38

Re: Algoritmo per videogame

Messaggioda vict85 » 07/11/2019, 14:00

Ok, allora ha ragione axpgn, si tratta di un problema di ottimizzazione lineare. Insomma, hai tre tempi \(t_1\), \(t_2\) e \(t_3\) da trovare e le condizioni su spazio percorso e consumo. Con funzione obiettivo \(t = t_1 + t_2 + t_3\). Non sono un esperto, non è un argomento che ho trattato durante i miei studi.
vict85
Moderatore
Moderatore
 
Messaggio: 9965 di 9977
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Algoritmo per videogame

Messaggioda giammaria » 09/11/2019, 20:52

Il problema era stato originariamente postato in Scuola Secondaria e temo che una vera risposta tecnica sarebbe incomprensibile per il proponente; do una risposta a livello liceale.

Premesse
- Intendo che in frasi come "consuma "x1" unita' di carburante" sia sottinteso "al secondo".
- Non scrivo i calcoli intermedi, limitandomi all'impostazione e al risultato, che consiglio di controllare.
- Per brevità spesso non faccio distinzioni come quella fra $>$ e $>=$ e considero solo la più facile.
- Indico con $t_k$ il tempo (in secondi) in cui si viaggia alla velocità $v_k$ e con $c_k$ il relativo consumo al secondo.

Soluzione
Dobbiamo trovare la più piccola $y$ collegata al sistema
${(y=t_1+t_2+t_3), (v_1t_1+v_2t_2+v_3t_3=L),(c_1t_1+c_2t_2+c_3t_2<=90/100C):}$

Inoltre tutte le grandezze indicate devono essere positive (le $t_k$ possono annullarsi).
I dati dicono che si ha $v_2=2v_1; v_3=4v_1; c_2=5/2c_1; c_3=6c_1$ e conviene porre $L=av_1; 90/100C=bc_1$; il sistema diventa
${(y=t_1+t_2+t_3), (t_1+2t_2+4t_3=a),(t_1+5/2t_2+6t_3<=b):}$

Se si viaggiasse sempre alla velocità $v_1$ il consumo sarebbe $a$, quindi per $b<a$ non si può arrivare al traguardo col previsto margine di sicurezza. Se invece si viaggiasse sempre alla velocità $v_3$ il consumo sarebbe $3/2a$, quindi per $b>=3/2a$ si arriva in ogni caso e conviene usare sempre la massima velocità. Resta da esaminare cosa succede per valori intermedi di $b$.
Dalle due equazioni ricaviamo $t_1,t_2$ in funzione di $t_3=x$; otteniamo
${(t_3=x),(t_2=-3x-y+a),(t_1=2x+2y-a):}" "$ formule (1)

Le tre $t_k$ devono essere positive o nulle e deve valere l'altra limitazione, quindi dobbiamo avere
${(x>=0), (-3x-y+a>=0),(2x+2y-a>=0),((-3x-y+a)+5/2(2x+2y-a)+6x<=b):}->{(x>=0),(y<=-3x+a),(y>=-x+a/2),(y>=x+3a-2b):}$

Sul piano cartesiano, le prime tre disequazioni dicono che dobbiamo essere all'interno del triangolo di vertici $A(a/4,a/4), B(0,a),C(0,a/2)$. L'ultima dice che dobbiamo essere al di sopra di una retta $r$ che, restando parallela a se stessa, si abbassa all'aumentare di $b$; passa per A se $b=3/2a$, passa per B se $b=a$ e passa per C se $b=5/4a$. Osservando il disegno e ricordando che volevamo la $y$ accettabile più bassa possibile, distinguiamo due casi:
- se $a<b<5/4a$ la soluzione è l'intersezione di $r$ con l'asse $y$;
- se $5/4a<b<3/2a$ la soluzione è l'intersezione di $r$ con la $y=-x+a/2$
Sostituendo le coordinate (x,y) nelle formule (1) otteniamo i tempi desiderati. Non ho fatto i calcoli, facili ma noiosetti.
- Indicando i metri con m e i centimetri con cm, si ha m=100 cm. Quindi 5 centimetri equivalgono a metri m=100*5=500.
- E' disonesto che un disonesto si comporti in modo onesto (R. Powell)
giammaria
Cannot live without
Cannot live without
 
Messaggio: 5115 di 5115
Iscritto il: 29/12/2008, 22:19
Località: provincia di Asti

Re: Algoritmo per videogame

Messaggioda Senzacervello » 12/11/2019, 16:15

Grazie infinite per la risposta.

giammaria ha scritto:... temo che una vera risposta tecnica sarebbe incomprensibile per il proponente; do una risposta a livello liceale.


Timore ben riposto visto che nella vita mi occupo di tutt'altro

giammaria ha scritto:Premesse
- Intendo che in frasi come "consuma "x1" unita' di carburante" sia sottinteso "al secondo".


Ovviamente e' riferito al consumo per unita' di tempo

giammaria ha scritto:Dalle due equazioni ricaviamo $t_1,t_2$ in funzione di $t_3=x$; otteniamo
${(t_3=x),(t_2=-3x-y+a),(t_1=2x+2y-a):}" "$ formule (1)


Chiedo venia, ma qui sono perso. Da quali due equazioni? Ammetto senza vergogna che il mio diploma liceale andrebbe stracciato senza indugi. Le sarei grato se potesse spiegarmi meglio questo passaggio.

Grazie per la pazienza
Senzacervello
Starting Member
Starting Member
 
Messaggio: 4 di 4
Iscritto il: 06/11/2019, 10:38


Torna a Analisi Numerica e Ricerca Operativa

Chi c’è in linea

Visitano il forum: Nessuno e 6 ospiti