Come sarebbe un piano di studio ideale per lo sviluppo di videogames?

N.B.: articolo WIP

Ciao a tutti, oggi si va a fare un enorme esperimento mentale.

Qualche tempo fa, basandomi sull’IGDA Curriculum Framework, ho provato a pensare: come si potrebbe comporre un piano di studi ideale di tre anni riguardante lo sviluppo di videogames?

Ovviamente si suppone che chi voglia fare un percorso del genere abbia una buona base sull’informatica e sulla programmazione in generale.

Il piano di studi da me ideato è diviso in corsi che vanno a identificare i seguenti sottopercorsi:

  • Game design
  • Computer science
  • Game development
  • Art skills
  • Game studies
  • Game production

Per ciascun corso, sarà presente una descrizione, un syllabus, o dei link a corsi di università reali che mostreranno informazioni a riguardo.

Quella che segue è la struttura che mi è venuta in mente.

1° parte

Introduction to videogame studies

Introduzione allo studio del medium videogioco nella quale si esaminano le sue funzioni culturali, educazionali e sociali.

Syllabus

  1. Studio dei videogiochi
  2. L’industria
  3. Cos’è un gioco
  4. Storia
  5. Estetica del videogioco
  6. Cultura del videogioco
  7. Cultura del giocatore
  8. Narrativa
  9. Serious games
  10. Videogiochi e rischi

Libro

  • Understanding Video Games: The Essential Introduction

Game design 1

Corso di introduzione alla disciplina del game design. L’approccio è inizialmente analitico, diventa poi pratico con la prototipazione e con le tecniche di design iterativo. La parte finale è dedicata alla comprensione dell’integrazione del game design all’interno di un team di sviluppo reale.

Syllabus

  1. Basi di game design
    1. Il ruolo del game designer
    2. Struttura di un gioco
    3. Elementi formali
    4. Elementi drammatici
    5. Sistemi dinamici
  2. Progettare un gioco
    1. Concettualizzazione
    2. Prototipazione
    3. Prototipazione digitale
    4. Playtesting
    5. Funzionalità, completezza ed equilibrio
    6. Divertimento e accessibilità
  3. Lavorare come game designer
    1. Strutture di team
    2. Fasi di sviluppo
    3. Il documento di design
    4. Comprendere la game industry
    5. Vendere un’idea alla game industry

Libro

  • Game Design Workshop – A playcentric approach to creating innovative games

Practical game development 1

Corso di introduzione allo sviluppo di videogames 3D con l’utilizzo di Unity.
Si studiano e si applicano le tecniche basilari di sviluppo di videogiochi, incluse la gestione degli input, dei suoni, la fisica, le camere, l’intelligenza artificiale, le interfacce utente e qualche cenno sul multiplayer online.
L’approccio è molto incentrato sulla pratica su Unity, al termine è previsto un progetto nel quale si implementa un videogioco in 3 dimensioni.

 Syllabus

  1. Introduzione alla programmazione di giochi
  2. Grafica 2D
  3. Algebra lineare per giochi
  4. Grafica 3D
  5. Input
  6. Suono
  7. Fisica
  8. Camere
  9. Intelligenza artificiale
  10. Interfacce utente
  11. Linguaggi di scripting e formati di dato
  12. Giochi online

Libri

  • Game programming algorithms and techniques – Sanjay Madhav
  • Game Programming in C++: Creating 3D Games – Sanjay Madhav
  • Unity in Action: Multiplatform Game Development in C# with Unity 5 – Joe Hocking

Computer graphics

Corso di introduzione alla computer grafica. Si svolge su due filoni, uno di teoria e uno pratico nel quale, utilizzando C++ e OpenGL, si mettono in pratica i concetti teorici.

Syllabus

  1. Matematica miscellanea
  2. Algoritmi di rasterizzazione
  3. Processamento del segnale
  4. Algebra lineare
  5. Matrici di trasformazione
  6. Viewing
  7. Eliminazione della superficie nascosta
  8. Shading
  9. Ray tracing
  10. Mappatura delle texture
  11. La pipeline grafica
  12. Strutture dati per grafica
  13. Sampling
  14. Curve
  15. Animazione
  16. Utilizzo dell’hardware grafico
  17. Costruzione di applicazioni grafiche interattive
  18. Luce
  19. Colore
  20. Percezione visuale
  21. Riproduzione del tono
  22. Illuminazione globale
  23. Modelli di riflessione
  24. Rendering image-based
  25. Visualizzazione

Libri

  • Fundamentals of computer graphics – Peter Shirley e altri
  • Learn OpenGL
  • OpenGL Programming guide – Shreiner e altri

2° parte

History of video games

Vabbè, abbastanza banale. Studiare la storia per poter guardare le cose in prospettiva. Utile approfondire l’evoluzione della tecnologia negli anni.

Libro

  • The Ultimate History of Video Games – Steven L. Kent

Level & world design

Corso utile a mettere in pratica i concetti visti in Game design 1 (design iterativo incluso) nella creazione di un livello, di un mondo o di un ambiente di gioco in generale.
L’approccio è sia teorico sia pratico, si vedrà come prototipare livelli usando AutoREALM e realizzarli effettivamente in Unity.
Si conclude con un progetto realizzato in Unity.

Syllabus

  1. Previsualizzazione
  2. Pianificazione e costruzione di livelli
  3. Illuminazione, texturing, particelle, effetti e audio
  4. Attori, oggetti di scena, item e dettagli sulla camera
  5. Design per genere
  6. Scripting
  7. QA e play-testing
  8. Considerazioni per gli MMOG

Libri

  • Designing virtual worlds – Richard A. Bartle (utile per approfondire)
  • Building levels in Unity – Volodymyr Gerasimov
  • Ultimate Game Design: Building Game Worlds – Tom Meigs

Game engine development 1

In questo corso si introduce dal punto di vista teorico e pratico l’architettura di un motore di gioco. Si affronta in dettaglio la struttura e lo sviluppo del motore di rendering in C++.

  1. Introduzione
    1. Fondamenti di ingegneria del software per giochi
    2. Matematica 3D
  2. Sistemi a basso livello
    1. Sistema di supporto
    2. Risorse e file system
    3. Game loop e simulazione real-time
    4. Human Interface Devices
    5. Strumenti per debug e sviluppo
  3. Grafica e moto
    1. Motore di rendering
    2. Sistemi di animazione
    3. Collisioni e dinamiche del corpo rigido

Libri

  • Game Engine Architecture – Jason Gregory
  • OpenGL Superbible: Comprehensive Tutorial and Reference – Sellers

Artificial intelligence

Corso che introduce tecniche di intelligenza artificiale utilizzate nell’industria videoludica. Le varie tecniche sono viste sia in teoria, sia in pratica (sempre con Unity).

Syllabus

  1. Tecniche
    1. Movimento
    2. Pathfinding
    3. Decision making
    4. Tattiche e strategie
    5. Apprendimento
    6. Giochi da tavolo
  2. Tecnologie di supporto
    1. Gestione dell’esecuzione
    2. Interfacciarsi col mondo
    3. Strumenti e creazione di contenuti
  3. Progettare IA di gioco
    1. Sparatutto
    2. Guida
    3. Strategico in tempo reale
    4. Sport
    5. Strategico a turni

Libro

  • Artificial Intelligence for Games – Ian Millington
  • Unity 2018 Artificial Intelligence Cookbook – Jorge Palacios

3° parte

Computer animation

Syllabus

  1. Background tecnico
  2. Interpolazione e tecniche di base
  3. Algoritmi avanzati
  4. Fenomeni naturali
  5. Modellare e animare figure articolate

Libro

  • Computer animation: algorithms and techniques

Advanced game mechanics design

In questo corso ci si affaccia alla progettazione di meccaniche di gioco complesse.

Syllabus

  1. Progettazione di meccaniche di gioco
  2. Emergenza e progressione
  3. Sistemi complessi e struttura dell’emergenza
  4. Economia interna
  5. “Machinations”
  6. Meccanismi comuni
  7. Design patterns
  8. Simulare ed equilibrare giochi
  9. Costruzione di economie
  10. Integrazione di level design e meccaniche
  11. Meccanismi di progressione
  12. Meccaniche significative

Libro

  • Game Mechanics: Advanced Game Design – Ernest Adams

Practical game development 2

Si raffinano le competenze acquisite in Practical game development 1 e si implementa un gioco che fa uso di meccaniche di gioco complesse, come ad esempio può essere un simulatore di macroeconomia. La complessità va gestita sia sul piano del design sia su quello dell’ingegneria del software. Il tutto, con l’utilizzo di Unity.

Syllabus

  1. Implementazione di meccaniche di gioco avanzate
  2. Ottimizzazioni Unity

Advanced algorithms

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005/syllabus/

4° parte

Game production 1

Corso introduttivo al processo di produzione di un gioco, si parla delle difficoltà intrinseche, dei vari componenti del team di sviluppo, delle documentazioni che è necessario produrre e delle varie fasi di sviluppo.
E’ evidente il legame di questa materia con l’ingegneria del software.

Syllabus

  1. Difficoltà dello sviluppo di giochi
  2. Componenti di un gioco
  3. Contesto di mercato
  4. Elementi di design chiave
  5. Documento di design del gioco
  6. Documento di design tecnico
  7. Piano di progetto
  8. Tracciare i task
  9. Strategie di outsourcing
  10. Pubblicazione del gioco

Game design 2

Si affrontano in maniera completa delle tecniche poco comuni di game design.

Syllabus

  1. Generazione procedurale
  2. Giochi pervasivi
  3. Gamification

Online game development

Syllabus

  1. Internet
  2. Sockets
  3. Serializzazione di oggetti
  4. Replicazione di oggetti
  5. Topologie di rete e giochi di esempio
  6. Latenza, jitter e affidabilità
  7. Gestione migliore della latenza
  8. Scalabilità
  9. Sicurezza
  10. Motori di gioco reali
  11. Servizi per giocatori
  12. Server di cloud hosting dedicati

Libro

  • Multiplayer game programming: architecting networked games – Glazer, Madhav

3D modeling

5° parte

Game production 2

Serious game design

Game engine development 2

Completamento di Game Engine Development 1.
Si prosegue lo sviluppo di un motore di gioco con la creazione di un sistema di gameplay.

  1. Introduzione ai sistemi di gameplay
  2. Comportamento a run-time

Audio design

6° parte

Game Company creation

Virtual reality design

Syllabus

  1. Introduzione e background
    1. Cenni storici
    2. Linee guida di design
  2. Percezione
    1. Realtà oggettiva e soggettiva
    2. Modelli e processi di percezione
    3. Modalità di percezione
    4. Percezione di spazio e tempo
    5. Stabilità percettiva, attenzione e azione
    6. Percezione: linee guida di design
  3. Effetti di salute collaterali
    1. Motion sickness
    2. Problemi alla vista
    3. Sfide hardware
    4. Latenza
    5. Misurare sickness
    6. Linee guida per ridurre effetti collaterali
  4. Creazione contenuti
    1. Concetti ad alto livello
    2. Design degli ambienti
    3. Condizionare il comportamento
    4. Transizione alla creazione di contenuti VR
    5. Linee guida di design
  5. Interazione
    1. Interazione human-centered
    2. Concetti di interazione in VR
    3. Dispositivi di input
    4. Pattern e tecniche di interazione
    5. Linee guida di interazione
  6. Design iterativo
    1. Filosofia del design iterativo
    2. Fase di definizione
    3. Fase di creazione
    4. Fase di apprendimento
    5. Linee guida di design iterativo
  7. Presente e futuro della realtà virtuale

Libro

  • The VR book: human-centered design for virtual reality – Jason Jerald

Virtual reality game development

Un clone di Tetris realizzato su Unity

Scrivo questo post per mostrare un clone di Tetris realizzato dal sottoscritto in collaborazione con un amico.

Si tratta di un’implementazione che, dal punto di vista delle meccaniche di gioco, prova ad essere pulita e performante, si evita quindi di utilizzare raycast o elementi fisici, preferendo a questi le semplici trasformazioni geometriche in combinazione con una matrice per la gestione della griglia di gioco.

La cosa più interessante è la gestione della griglia di gioco, la quale avviene su due piani, quello grafico (posizioni dei pezzi, trasformazioni, ecc.) e quello “effettivo” (matrice di short che indica la presenza o meno di un cubo in ciascuna posizione).

E’ presente anche una banale interfaccia utente che sicuramente non rispetta i migliori criteri di usabilità ma fa il suo dovere. La sua aggiunta è stata una scusa per imparare il funzionamento delle interfacce utente su Unity3D, e sono certo che in un progetto futuro ci sarà maggiore attenzione e cura a riguardo.

Può essere utile a chi vuole imparare qualcosa di Unity.
Se invece si vuole semplicemente giocare, basta lanciare il file .exe presente nel repository.

LINK

Prego il Signore che The Tetris Company non mi faccia causa.

Il kernel panic era una funzione semplicissima

Ecco una curiosità che potrebbe interessare a qualcuno.

La funzione che si occupa di generare il cosiddetto kernel panic in Linux 0.01 era:

Invece, nell’ultima versione di Linux (al momento in cui scrivo), è la seguente:

 

La progettazione di un motore di gioco è una cosa bella

A ogni pagina di Game Engine Architecture me ne rendo sempre più conto: realizzare un motore di gioco serio è un lavoro di una difficoltà estremamente elevata.

L’intenzione per la tesi di laurea (frequento il corso di Informatica presso Unica) sarebbe quella di riuscire nell’impresa, ma francamente sono sicuro che riuscirci anche solo in parte sarebbe un gran successo.

Se da una parte, quindi, mi accorgo che realizzare un motore di gioco diventa un sogno sempre meno raggiungibile (almeno in solitario e in soli 2 anni), d’altra parte proseguo nella lettura del libro Game Engine Architecture, per un motivo molto semplice.

E’ bello vedere, attraverso questo libro, come la creazione di un motore di gioco porti con sè delle necessità particolari, come ad esempio quelle di gestire delle risorse (audio, modelli 3D e molto altro), sfruttare al massimo l’hardware, semplificare il lavoro di un team e far comunicare tra loro delle componenti software ben separate ma interdipendenti (es. gestore della memoria, gestore della fisica, gestore del rendering…).

In ognuna di queste componenti, la natura (golosa di risorse) di un videogioco costringe a delle scelte che raramente diventano necessarie per un qualsiasi altro software.

Questo si ripercuote sulla scelta di alcune strutture dati, sulla particolare gestione della memoria e su molto altro. Facciamo alcuni esempi.

L’utilizzo di numerose malloc/new e free/delete in C/C++ rallenta tantissimo il programma perché a ogni chiamata si cambia la sua modalità di esecuzione (da user mode a kernel mode e viceversa).
Per ovviare a questo problema si evita assolutamente di allocare/deallocare memoria all’interno di cicli (verrebbe ripetuta più volte) e si cerca, invece, di prevedere già in anticipo quanta memoria verrà usata e allocarla una sola volta (es. prima di caricare un livello sappiamo più o meno quanta memoria verrà utilizzata) in modo da effettuare una sola volta il passaggio da user mode a kernel mode e viceversa. Una volta fatto ciò si effettuano operazioni sullo heap in modo tale che pesino il meno possibile e con un po’ di astuzia.

E a proposito del livello… spesso (anche in giochi abbastanza vecchiotti tra l’altro) si utilizzano strutture dati particolari per la sua gestione, vedi lo stack double-ended.

Da una parte si caricano le risorse utili per TUTTO il livello (o anche il gioco, dipende sempre dalle esigenze), dall’altra quelle che si utilizzano solo momentaneamente.

Non vengono utilizzati due stack separati perché ciò porterebbe ad effettuare operazioni sullo heap: la memoria necessaria allo stack double-ended è stata già allocata in precedenza, quindi occorre anche riscriversi a mano tutta la gestione delle operazioni su questo particolare stack, con un occhio di riguardo all’ottimizzazione.

Parlando di ottimizzazione… che dire dell’allineamento dei dati? In C e C++ è possibile ottimizzare al meglio l’esecuzione di certe istruzioni da parte della CPU allineando i dati in maniera tale che la CPU, appunto, utilizzi il più basso numero possibile di cicli.

La CPU accede in maniera più veloce ai dati se questi si trovano in un indirizzo di memoria divisibile per la dimensione della variabile, quindi vale la pena utilizzare un pochino di spazio in più per ogni variabile ma avere poi la certezza che questa sia allineata correttamente spostandola manualmente di qualche byte se necessario (si lavora sempre sulla memoria heap).

Due link per approfondimenti a riguardo:

  • https://en.wikipedia.org/wiki/Data_structure_alignment
  • http://www.agner.org/optimize/optimizing_cpp.pdf

Ma non finisce qui: siamo abituati a utilizzare Git o un altro software di controllo di versione per gestire del codice sorgente. Ciò viene comodo perché i sorgenti sono leggeri e, soprattutto, sono file di testo (e Git, si sa, fa miracoli con questi).

Potrebbe essere necessario, però, utilizzare un VCS per gestire delle risorse che, come si può immaginare, sono file binari e soprattutto sono pesanti. E qui i soliti VCS, sebbene sempre funzionali, potrebbero portare altri problemi che necessitano di essere risolti (più difficile l’utilizzo concorrente del VCS a causa dei file binari, file di dimensione maggiore comportano utilizzo maggiore della banda, ecc.).

Probabilmente aggiornerò questo articolo man mano che scopro cose interessanti riguardo alla progettazione di motori di gioco.

Python is overrated

“Python is overrated”.

Well, this statement may well be a bit hasty, and maybe it is. The problem is that after having used some languages I have seen that some characteristics of Python that if on one hand can be seen as amazing (coinciseness of the code), on the other hand I think they can become a double edged-sword.

In fact, behind the simplicity of Python syntax, there is always the concrete risk of doing something in a superficial way. While some languages as Java (imho C and C++ too) implement a precise idea of programming, Python gives too much freedom to the programmer.

This freedom, in the proper hands, may result in well written and coincise code, but in the wrong hands it may become a disaster.

The last is, obviously, the real problem about Python.

Python is very often recommended as first language to learn, but it is not able to offer a tangible frame within which the programmer can act. This often becomes an illusion of simplicity of the language and, finally, a less robust code (if not wrong).

While Python lives with this problem, languages as C++ or Java force the programmer to organize much better their code introducing concepts such as declarations and, in the case of C/C++, pointers.

This fact is very important for a newbie programmer.

As if that were not enough,  C and C++ allow newbie programmers to see how a data structure (e.g. linked list) is really made, something that doesn’t happen in Python, a language where someone can literally improvise something without knowing exaclty how things work.

Can simplicity be seen as a Python trait? Well, only if you really know what programming means, something that doesn’t happen when you’re a newbie.

Writing a one line hello world is not as useful as learning to declare a main function on C.

Introduzione agli algoritmi – 2. Come descrivere gli algoritmi per computer

Eccoci alla seconda parte di questo corso di introduzione agli algoritmi.

Innanzitutto vorrei ringraziare chi, in vari modi, mi ha fornito un feedback consentendomi così di correggere le cose che non vanno bene.

In realtà è davvero difficile definire “corso” quella che è semplicemente una rielaborazione di appunti presi durante lo studio di algoritmi, ma è anche vero che, come diceva un vecchio saggio (di cui ignoro nome ed età):

Non hai capito una cosa fin quando non riesci a spiegarla a tua nonna.

Ed ecco che con questi post cerco di spiegare gli algoritmi alle tante nonne che leggono 😀

Bando alle ciance e buttiamoci a capofitto sull’argomento di oggi.
La scorsa volta abbiamo visto in maniera molto terra a terra il significato di algoritmo e alcuni dei concetti principali di cui bisogna tenere a mente quando si parla di algoritmi.

Oggi andiamo nello specifico e parliamo degli algoritmi per computer e in particolare di un semplice algoritmo per la ricerca di un elemento all’interno di un array.

Come descrivere algoritmi per computer

Solitamente si pensa che basti descrivere l’algoritmo utilizzando un linguaggio di programmazione, ma questo approccio può portare un problema: i dettagli riguardanti il linguaggio di programmazione rischiano di nascondere/offuscare la logica dell’algoritmo.

Per questo inconveniente ci viene incontro lo pseudocodice.

 

Come molti di voi sapranno, un programma può essere diviso in procedure.
Una procedura si occupa di ricevere dei parametri in input e, alla fine, di restituire un valore alla procedura chiamante.

Ecco ad esempio la chiamata a una procedura che calcola la radice quadrata di un numero:

L’input della procedura è il parametro x.
La chiamata a una procedura può o non può produrre output (leggasi restituire valori alla procedura chiamante).

Molti programmi e algoritmi lavorano con array di dati.

Un array aggrega dati dello stesso tipo nella stessa entità.
Ad esempio, ecco una tabella che mostra i primi 5 presidenti della Repubblica Italiana:

Schermata del 2016-08-01 22:55:08

Possiamo dire che il quarto elemento dell’array è Antonio Segni. Ciò che vediamo non è un insieme di elementi separati tra loro, bensì cinque voci di una tabella.

Un array è esattamente questo. Gli indici di un array sono numeri consecutivi che nei computer partono da 0 e in pseudocodice da 1, quindi occhio a non confondersi.

Dato il nome di un array e un indice dell’array, possiamo combinarli utilizzando le parentesi quadre.
Per denotare l’elemento i-esimemo di un array A, quindi, usiamo la notazione: A[i].
C’è anche un’altra cosa di cui tener conto, ovvero che il tempo di accesso ad un elemento dell’array è lo stesso per tutti gli elementi.

Ora che abbiamo gettato le fondamenta (array e procedure), iniziamo a vedere l’algoritmo che ci accompagnerà per tutta questa lezione: ricerca di un valore all’interno di un array.

Dato un array contenente n elementi, quindi, ci interessa sapere quale indice permette di accedere al valore ricercato (se esistente).

Facciamo finta che l’array sia uno scaffale di libri e che noi vogliamo sapere dove, nello scaffale, si può trovare un libro di Italo Calvino.

mastailibri-scaffale-libri-libreria-2

I libri presenti sullo scaffale potrebbero essere organizzati in ordine alfabetico per nome dell’autore, ma anche no.

Non sapendo come sono organizzati i libri nello scaffale, come facciamo a trovare il libro di Italo Calvino?

Guardando al problema con gli occhi di un programmatore possiamo dire che abbiamo un array A (lo scaffale di libri) di n elementi (i singoli libri) e vogliamo sapere se un valore x (un libro di Italo Calvino) è presente nell’array A.
Se sì, vogliamo determinare un indice i tale che A[i] = x.

Abbiamo bisogno anche di un modo per indicare che l’array A non contiene l’elemento x (il libro di Italo Calvino non è presente nello scaffale).

Se cerchiamo il libro di Calvino iniziando dall’estremità sinistra dello scaffale, controllando libro per libro man mano che ci muoviamo verso destra, allora stiamo utilizzando una tecnica chiamata ricerca sequenziale.

In termini di array, partiamo dall’inizio dell’array, esaminiamo ogni elemento in ordine (prima A[0], poi A[1], poi A[2], …, infine A[n-1]) e ci fermiamo quando troviamo x, se lo troviamo.

Procedura ricercaSequenziale(A, n, x)

Input:
  • A: un array.
  • n: il numero di elementi in A attraverso i quali cercare.
  • x: il valore ricercato.
Output:

O un indice i per il quale A[i] = x, o il valore speciale NON-TROVATO, che può essere un qualunque indice non valido per l’array (es. un numero negativo).

Algoritmo:
  1. settare risposta a -1 (ovvero NON_TROVATO);
  2. per ogni indice i, andare da 0 a n-1, in ordine:
    1. se A[i] = x, allora settare risposta al valore di i.
  3. restituire il valore di risposta come output.

Oltre ai parametri A, n ed x abbiamo utilizzato una variabile chiamata risposta. La procedura assegna il valore -1 (che idealmente possiamo far corrispondere a “non-trovato”) alla variabile risposta. Il valore della variabile poi cambia nel caso in cui venga trovato l’elemento x ricercato, prendendo il numero dell’indice.

L’esecuzione di azioni ripetute è chiamata ciclo, mentre ogni ripetizione presa a sé è chiamata iterazione.

Se andiamo a vedere bene, nell’algoritmo appena visto abbiamo un problema. Mettiamo il caso in cui il libro ricercato sia al primo posto… che senso ha continuare a cercarlo fino alla fine dell’array?
Nessuno, ma è ciò che avviene!

Il modo per ovviare a questo problema è far sì che il ciclo si interrompa una volta trovato l’oggetto cercato e ne restituisca l’indice.

Procedura ricercaSequenzialeMigliorata(A, n, x)

INPUT e output come prima.
Algoritmo:
  1. per ogni indice i, andare da 0 a n-1, in ordine:
    1. se A[i] = x, allora si restituisce il valore i in output (ciò comporta l’interruzione dell’algoritmo, quindi non viene eseguito il passo 2).
  2. restituire il valore di risposta come output.

Nonostante tutto, la ricerca sequenziale può essere resa ancora più efficiente.

Si noti, nella ricerca sequenziale migliorata, che a ogni iterazione vengono effettuati due controlli: il primo nel passo 1 per determinare se i < n-1,  e il secondo per verificare l’uguaglianza tra l’elemento ricercato e quello che si sta scorrendo nell’array.

Tornando all’esempio della libreria, questo significa controllare ogni volta se abbiamo superato la fine dello scaffale e, se no, se il libro successivo è quello di Calvino oppure no.

Il modo per migliorare l’algoritmo appena visto, quindi, è far sì che si riesca ad effettuare un solo controllo ad ogni iterazione invece che due.

Per far ciò, dobbiamo trovare un escamotage… che ne dite di prendere un libro finto, scrivere sulla copertina che è di Calvino e piazzarlo al posto dell’ultimo libro del scaffale?

In questo modo non ci serve controllare se abbiamo superato la fine dello scaffale perché siamo certi che alla fine dello stesso troveremo il libro ricercato smettendo così di iterare!

Uno potrà chiedersi: come facciamo a sapere se quello trovato è il vero libro di Calvino oppure no?
Semplice, quando si trova il libro di Calvino si controlla che questo non sia quello fantoccio, quindi il controllo avviene solo quando si trova il libro cercato.

Tradotto in termini di array, questo significa controllare che l’indice dell’elemento trovato sia minore della dimensione dell’array (array al quale alla fine abbiamo sostituito il “finto” elemento ricercato).

Il “finto” elemento inserito al posto dell’ultimo elemento dell’array si chiama sentinella.

Procedura ricercaSequenzialeSentinella(A, n, x)

INPUT e OUTPUT come prima.
ALGORITMO:
  1. Salvare A[n] in ultimo e mettere x in A[n].
  2. Settare i a 0.
  3. Mentre A[i] è diverso da x, fare ciò che segue:
    1. Incrementare i.
  4. Ripristinare il valore originale di A[n] settandolo a ultimo.
  5. Se i < n o A[n] = x, allora restituire il valore di i come output.
  6. Altrimenti, restituire NON-TROVATO come output.

Si può capire che la ricerca sequenziale con sentinella potrebbe risultare meno intuitiva delle altre, ma d’altro canto è più efficiente.
Si noti al passo 3 abbiamo un ciclo basato sul mantenimento o meno di una condizione, infatti il passo 3.1 viene eseguito fin quando la condizione “A[i] diverso da x” risulta vera.

Il fatto che vengano eseguiti molti meno controlli rispetto agli altri due algoritmi, rende la variante con sentinella il miglior algoritmo di ricerca sequenziale.

Dopo aver visto e formalizzato l’esecuzione di alcuni algoritmi, la prossima volta andremo ad analizzare gli stessi da un altro punto di vista, ovvero il tempo di esecuzione.
Da cosa è determinato? Come descriverlo?
Prepariamoci a vedere un po’ di matematica.

Sinhuè Angelo Rossi

Introduzione agli algoritmi – 1. Cosa è un algoritmo?

In questo articolo, primo di una lunga serie, proverò a spiegare a chi per i motivi più disparati ne ha bisogno, qualcosa sugli algoritmi.

Infatti ho iniziato a studiare questa interessante e soprattutto utile materia attraverso un libro dell’ottimo Thomas H. Cormen, ovvero Algorithms Unlocked.
Credo che questo lavoro possa diventare utile sia per me che sono in fase di apprendimento, sia per chi leggerà, anche perché le risorse in italiano a riguardo sono abbastanza pochine (togliendo ovviamente le dispense universitarie).

Direi quindi di non perdere altro tempo e buttarci nel discorso ponendoci una importante domanda.

Cos’è un algoritmo?

Beh, dal punto di vista formale questa è una definizione ancora oggetto di discussione, quindi occorre accontentarci, specie inizialmente, di una definizione informale che però racchiude il concetto di algoritmo:

Un algoritmo è un insieme di passi necessari per portare a termine un compito.

Considerando il mondo reale, possiamo dire che eseguiamo algoritmi praticamente in ogni momento.

Vogliamo preparare un bel piatto di pasta? Bene! Non so cucinare, potrei sbagliare qualcosa.

  1. Scegliere il tipo di pasta che si vuole;
  2. Prendere una pentola;
  3. Riempire la pentola con acqua salata;
  4. Scaldare la pentola finché l’acqua non inizia a bollire;
  5. Buttare la pasta scelta nella pentola;
  6. Attendere per il numero di minuti indicato nella scatola;
  7. Scolare la pasta;
  8. Condire se volete;
  9. Servire.

Come potrete ben vedere in cucina sono un disastro, ma ciò non toglie che abbiamo appena visto un esempio di algoritmo che chiunque conosce (magari con qualche variazione).

Spostandoci sui nostri amati computer, invece, possiamo citare due esempi di gruppi di algoritmi che sono abbastanza diffusi:

  • Algoritmi del percorso minimo (o pathfinding);
  • Algoritmi di criptazione.

Tra gli algoritmi eseguiti da noi umani e quelli eseguiti dai computer è presente un’enorme differenza che occorre tenere ben presente: noi umani possiamo tollerare qualche imprecisione nell’algoritmo (nell’esempio non è stato precisato quale tipo di pasta scegliere, ma non sarà certo un problema!), il computer no.

Un computer non tollera imprecisioni di alcun tipo su un algoritmo, tutto dev’essere già stabilito per non avere spiacevoli sorprese.

Per sapere come scrivere un algoritmo per computer, però, dobbiamo dare una risposta alla seguente domanda: cosa vogliamo da un algoritmo per computer?

Vogliamo semplicemente che, dato un input, l’algoritmo produca sempre la soluzione corretta per un problema attraverso l’utilizzo efficiente delle risorse computazionali.

La correttezza e l’utilizzo di risorse sono due concetti chiave che meritano particolare attenzione.

Correttezza

Cosa significa produrre la soluzione corretta?

Aiutiamoci con un esempio. Mettiamo il caso in cui il nostro navigatore GPS debba calcolare il percorso più veloce per farci spostare da un punto A verso un punto B.

Potrebbe suggerirci un percorso che sì, è il più corto, ma magari è anche il più trafficato o il più lento a causa dei limiti di velocità.

Possiamo dire, in tal caso, che la soluzione data è quella corretta?

Beh, l’algoritmo ha funzionato correttamente, questo è fuor di dubbio, il problema è la mancanza di informazioni (sul traffico e sui limiti di velocità) ricevute in input necessarie a trovare il percorso più veloce.

La soluzione fornita dal navigatore, tenendo conto dell’input che ha ricevuto, può essere quindi considerata corretta.

In alcuni casi, però, si può accettare che un algoritmo possa produrre una risposta non corretta, almeno finché possiamo sapere quanto spesso ciò possa accadere. È questo il caso dell’algoritmo di crittografia asimmetrica RSA.

Ecco un interessantissimo documento in PDF che parla del crittosistema RSA.

Il problema a cui l’algoritmo deve fornire una soluzione è determinare l’appartenenza di un numero all’insieme dei numeri primi o meno.

La prima cosa che si può fare è scrivere un programma che prova a dividere il numero in questione n per tutti i numeri che vanno da 2 a n-1.

Viene facile pensare che se n è composto da centinaia di cifre, il computer potrebbe impiegare un bel po’ di tempo nel calcolo, occorrono quindi delle ottimizzazioni:

  • Eliminare tutti i possibili divisori pari una volta stabilito che 2 non è divisore di n;
  • Fermarsi quando si arriva a √(n). Infatti, se non si riesce a dividere n per un numero compreso tra 2 e √(n) significa che n è primo.

Un algoritmo che funziona in questo modo può determinare se n è numero primo o numero composto. C’è un problema, però.

Se l’algoritmo stabilisce che n è composto, allora questo lo è, ma se stabilisce che n è primo c’è una piccolissima possibilità che questo sia invece composto, stimabile intorno a 1 volta su 250.

In questo caso siamo quindi davanti ad un algoritmo di approssimazione.

Gli algoritmi di approssimazione vengono incontro a problemi di ottimizzazione che vanno affrontati quando si vuole risolvere un problema che richiederebbe svariato tempo di calcolo in un tempo che sia invece ragionevole.

Manca quindi un algoritmo capace di trovare una soluzione ottima in tempi ragionevoli, e di conseguenza ci si accontenta di una soluzione quasi ottima.

Insomma, possiamo accontentarci della soluzione data.

Utilizzo di risorse

Cosa significa per un algoritmo utilizzare efficientemente le risorse computazionali?

Abbiamo già velatamente parlato di un’unità di misura che ci consente di determinare l’efficacia di un algoritmo, ovvero il tempo.

Provate a pensare ad un algoritmo che fornisce una soluzione corretta ma in moltissimo tempo: che valore potrà mai avere?

Basta pensare all’esempio riguardante il navigatore GPS. Se quest’ultimo impiega svariate ore per calcolare un percorso, tanto vale non usarlo.

Il tempo, però, non è l’unica misura per l’efficacia di un algoritmo. Infatti ci sono anche altri fattori da considerare, vedi la memoria (un algoritmo in esecuzione deve stare entro i limiti di memoria disponibili), la comunicazione con la rete, le operazioni su disco, etc.

In più è da notare che la correttezza di un algoritmo non dipende dal computer utilizzato, mentre il tempo sì.

Tutti i computer possono essere diversi, idem gli input… come trovare un metodo per valutare la velocità di un algoritmo?

Si combinano due idee:

  • determiniamo quanto l’algoritmo impiega in funzione della dimensione del suo input (es. dimensione di una lista di oggetti o il numero di incroci facenti parte di una mappa);
  • ci concentriamo su quanto velocemente la funzione che rappresenta il tempo di esecuzione dell’algoritmo cresce in base alla dimensione dell’input, ovvero la complessità temporale.
Un confronto sulla velocità in relazione alla dimensione dell'input tra algoritmi di ordinamento.
Un confronto sul tempo di esecuzione (asse y) in relazione alla dimensione dell’input (asse x) tra algoritmi di ordinamento.

Mettiamo che possiamo determinare che una specifica implementazione di un algoritmo di ricerca in una lista di n elementi impieghi 50n + 125 cicli macchina.

50n supera di molto 125 quando n diventa abbastanza grande, a partire da n>=3.
Man mano che n cresce, quindi, 125 diventa sempre più insignificante, idem il coefficiente di n.

Un altro esempio può essere quello in cui determiniamo la durata di esecuzione di un algoritmo in
20n3 + 100n2 + 300n + 200 cicli macchina.

Possiamo dedurre che il tempo di esecuzione dell’algoritmo cresce in n3 perché 100n2 + 300n + 200 conterà sempre di meno all’aumentare di n.

Dal punto di vista pratico, i coefficienti che ignoriamo contano ma dipendono da fattori non rilevanti tali che diventa possibile confrontare due algoritmi A e B con stessa complessità temporale (o tasso di crescita) tali che A però va più veloce di B in alcuni computer e B va più veloce di A in altri.

Se sia A che B producono soluzioni corrette con A che però risulta veloce il doppio rispetto a B, allora chiaramente si preferisce A rispetto a B.

Per paragonare due o più algoritmi nell’astratto è necessario concentrarsi sulla complessità temporale, non considerando (come fatto precedentemente) tutti i coefficienti di termine più basso.

L’importanza degli algoritmi

Per avere un’idea dell’importanza dell’efficienza di un algoritmo basti pensare che dati due algoritmi di ordinamento A e B con A molto più efficiente rispetto a B, non è difficile che l’algoritmo A eseguito su un PC vecchissimo superi nettamente in velocità l’algoritmo B eseguito su un PC di ultima generazione.

Anzi, dirò di più, gran parte delle prestazioni di un sistema dipendono dagli algoritmi utilizzati e non dal computer su cui gira!

Concludendo, possiamo dire che gli algoritmi sono uno strumento indispensabile quando si tratta di tirare fuori il meglio da un computer.

Per tutto l’arco di questo corso cercherò di presentarvi al meglio delle mie possibilità tutto ciò che sto attualmente studiando, sperando che il tutto possa rivelarsi utile per il vostro corso di studi, per i vostri studi personali e quant’altro.

Occhio ai dettagli

Oggi vi racconterò quanto ho imparato da una disavventura causata dalla mia inesperienza nel trattamento da riservare ai clienti o in generale a chiunque chieda il nostro aiuto per lo sviluppo di un’applicativo di qualunque genere.

Ci son tre cose che vanno ASSOLUTAMENTE stabilite prima dell’inizio di un progetto, ovvero nella fase in cui si accetta l’incarico:

  • specifiche del progetto: dovete sapere esattamente cosa dovrete fare, questo perché da una parte ciò consente di stabilire dei tempi di sviluppo e dall’altra fornisce una grande mano in fase di progettazione del software. Sapere ciò che bisogna fare è il primo passo verso la riuscita di un progetto.
    Ovvio che non si può stabilire da subito il tutto nei dettagli, ma almeno a grandi linee bisogna sapere cosa si andrà a scrivere.
  • modalità di pagamento: sebbene un tizio con la barba che ha creato GNU possa vederla diversamente, ciò che noi scriviamo va pagato. Come?
    Beh, ci sono diverse modalità, si può decidere di farsi pagare ad avanzamento (ogni tot di giorni si mostra a che punto procede lo sviluppo e si viene pagati), in anticipo, a progetto e in tanti altri modi.
    L’importante è che ciò si sappia prima.
  • la PROPRIETÀ DEI CODICI SORGENTI: questo è un punto che va assolutamente chiarito prima dell’inizio di un progetto perché può portare a disguidi nel corso dello sviluppo, proprio come successo al sottoscritto.
    Se voi doveste abbassare il prezzo di un software per cercare di venire incontro al cliente, vi farebbe piacere che questi ottenesse anche il possesso del codice sorgente per poi magari darlo ad altri programmatori diversi da voi?
    Ecco, il problema è tutto qui.
    Sappiate che il vostro codice vale più di ogni altra cosa, senz’altro più dell’applicativo già compilato.
    Proprio per questo motivo se il vostro cliente dovesse voler acquistare il vostro sorgente questo andrebbe pagato a parte e probabilmente 3 o 4 volte quanto la versione compilata.

Nel mio caso è stato richiesto il sorgente di un’applicazione iOS e di una Android quando ormai buona parte dello sviluppo era stato compiuto. Cos’è accaduto?

Io ovviamente ho rifiutato di dare il sorgente gratuitamente, e questo ha comportato la fine del rapporto di lavoro, con buona pace del progetto che si è rivelato essere tempo sprecato (ben due mesi belli pieni).

Quindi il mio consiglio, rivolto praticamente a tutti, è quello di stabilire in anticipo tutti i dettagli relativi al progetto che si porterà avanti e non solo: informatevi sui vostri diritti per evitare di svendervi col primo furbo che vi capita.

Firebase, uno strumento completissimo

Su suggerimento di Giorgio Taverniti, uno dei principali esperti di web marketing in Italia, realizzo un articolo (mi ha consigliato di creare un video, ma pazienza) nel quale cerco di spiegare qualcosa su Firebase, strumento del quale ho avuto modo di scorgere il potenziale lavorando allo sviluppo di un’applicazione Android per conto di terzi.

Innanzitutto: cos’è Firebase?

Firebase è un’azienda che fornisce servizi cloud e Backend as a Service.

Con l’unione tra Firebase e Google (link), i servizi della prima hanno la possibilità di trovare un campo di utilizzo molto più vasto rispetto al passato, essendo Google quasi padrone assoluto quando si parla di applicazioni mobile (basti pensare al Play Store).

Come mai scrivo questo articolo? Beh, le API di Google Firebase sono uscite proprio durante lo sviluppo dell’applicazione di cui al primo paragrafo, e guarda a caso mi son servite per implementare un servizio di notifica.

Quindi, molto semplicemente, racconto quella che è stata la mia (breve per ora) esperienza con questo servizio che credo abbia un grandissimo potenziale per tutti gli sviluppatori Android e iOS.

Prima di iniziare, sappiate che al momento in cui scrivo Firebase su Android è utilizzabile solo con una versione ancora non stabile di Android Studio (anche se non mi ha dato alcun problema sinora), scaricabile qui.

Partiamo dalla documentazione. Molto chiara e intuitiva, vengono mostrati segmenti di codice sia in Java (per Android) sia in Swift (per iOS) che possono essere benissimo copiati e incollati (brutto da dire, ma perché reinventare la ruota? Come ho sempre pensato, l’importante è capire cosa accade per poi modificare o ricreare all’occorrenza).

Come già detto, ho avuto la necessità di implementare un servizio di notifica per i clienti e parlerò solo di questo. È stato quindi necessario utilizzare il servizio “Notifications”, visibile nel seguente screenshot:

2016-06-13-175841_1366x768_scrot

A lato client, quindi sull’app, serve inserire il servizio che permette di ricevere i messaggi (notifiche) dal server di Google. I messaggi possono essere invece spediti attraverso il form visibile qua sotto o attraverso l’invio di una richiesta POST con una stringa in formato JSON alla pagina https://fcm.googleapis.com/fmc/send.

La documentazione spiega come fare il tutto, io dico semplicemente che questa è una grandissima possibilità perché praticamente tutti i principali linguaggi di programmazione (basterebbe solo il terminale di Linux a dirla tutta) permettono di inviare richieste POST alle pagine web, quindi diventa veramente facile creare notifiche personalizzate in base alle proprie esigenze e soprattutto integrarle all’interno di infrastrutture software già esistenti.

2016-06-13-175829_1366x768_scrot

Com’è possibile vedere in questo screenshot si possono inviare i messaggi a tre tipi di destinatari, ovvero verso un segmento di utenti, verso coloro che sono iscritti a un topic o verso un singolo dispositivo.

Per segmento di utenti s’intendono tutti i possessori dell’applicazione che rispettano determinati criteri specificati nel form (es. solo gli utenti italiani).

Per capire i destinatari basati sui topic basti pensare ai feed RSS: quando vi iscrivete a un determinato feed riceverete tutte le informazioni che lo riguardano. Ecco, tutto qui.
Considerate che per l’iscrizione a un determinato topic basta una sola riga di codice (nell’app) e, come se non bastasse, i topic alla quale ci si può iscrivere sono infiniti. In più, per inviare messaggi a un topic nuovo non serve prima crearlo attraverso il form presente nella pagina di Firebase, ma basta specificarlo nella stringa JSON (link alla documentazione) per far sì che questo venga creato in automatico.

La terza possibilità è quella di mandare un messaggio verso un singolo dispositivo attraverso un token di registrazione a FCM (Firebase Cloud Messaging), il quale dev’essere creato dall’applicazione stessa.

Si ricorda che è possibile fare tutto attraverso una semplice richiesta POST che passa una stringa JSON alla pagina https://fcm.googleapis.com/fmc/send. Mi sembra giusto ribadirlo.

Che altro aggiungere?

Come avrete visto (se vi siete informati) sono disponibili molti altri servizi che permettono l’interazione coi database (non ho idea nello specifico), la raccolta di dati sull’utilizzo delle applicazioni e sui crash (utilissimo per chi sviluppa), il piazzamento di pubblicità… insomma, si tratta di una suite molto varia e completa, imprescindibile per chi sviluppa applicazioni Android e iOS.
E lo dice uno che ha dovuto sviluppare un’applicazione tutto sommato piccola, pensate quindi ai possibili utilizzi su progetti grandi.

Ecco, se devo fare una critica (solo questa per ora) è il tempo di compilazione dell’applicazione Android, che a seguito dell’inserimento delle librerie necessarie per l’utilizzo di Firebase è passato da una ventina di secondi a quasi un minuto.

Quisquìlie.

C++ per principianti – 8. programmazione procedurale

Ciao a tutti e bentornati al corso di C++ per principianti! Dopo aver visto nelle lezioni precedenti quelle che sono le strutture capaci di determinare il flusso di un programma (condizionali, iterative, ecc.), è arrivato il momento di fare un passo in avanti.
Perché sì, fin’ora abbiamo visto i vari modi in cui è possibile applicare la logica ai nostri programmi… però l’attività di programmazione non consiste solamente in questo, anzi.

Quando si ha a che fare con programmi più grandi rispetto a quelli visti fin’ora iniziano a nascere delle nuove necessità, dettate da problemi che si presentano.
Una di queste necessità è quella di dividere il codice in più parti in modo da gestire in maniera più agevole il flusso del programma.

A questo scopo ci vengono in aiuto le funzioni, dette anche procedure.

Cosa sono le funzioni? Beh, le funzioni non sono altro che dei blocchi di codice che in C++ hanno un nome e, solitamente, un tipo (a meno che non siano void).
Essendo questa la prima volta che incontriamo le funzioni, occorre…. wait, ma noi una funzione l’abbiamo già incontrata!

Ebbene sì, main() è una funzione. E non si tratta di una funzione qualsiasi, si tratta della funzione dalla quale un programma inizia la sua esecuzione!

Come possiamo notare, prima della dicitura main() abbiamo il tipo int… cosa sta a significare? Molto semplicemente, int ci fa sapere che il valore che la funzione restituirà (in questo caso al sistema operativo, trattandosi della funzione main) sarà di tipo intero.

Il valore viene restituito attraverso la parola chiave return, seguita dal valore e dal punto e virgola.

Questa era quindi la funzione main. Come avrete potuto intuire, siamo liberi di creare nuove funzioni seguendo la struttura già vista nel main.

Per quanto riguarda i nomi che possono essere dati alle funzioni valgono le stesse regole viste qui per le variabili. E’ chiaro che una variabile e una funzione NON possono avere lo stesso nome.
Vedendo la struttura di una funzione, possiamo notare la presenza, tra parentesi tonde, dei parametri.

I parametri sono delle variabili che, se dichiarate tra le parentesi tonde, verranno utilizzate all’interno della funzione e non potranno essere utilizzate all’infuori di questa. Con questo si introduce il concetto di ambito delle variabili, che non tratterò in dettaglio in questo corso. Alla fine della lezione comunque ci sarà un collegamento a un documento PDF dell’Università di Pavia che tratta l’argomento.

Iniziamo a sporcarci le mani e realizziamo un semplice programma che, dati due numeri, ne calcola e ne mostra in output la somma, la differenza, il prodotto e il quoziente.

Immagine

In questo programma di esempio possiamo notare come il codice sia diviso in più parti facilmente gestibili. In questo caso ogni funzione contiene al suo interno un’istruzione che restituisce il valore dell’operazione, ma in altri casi potrebbero essere necessarie molte più istruzioni e l’utilizzo delle funzioni si rivelerà fondamentale.

Altra cosa che possiamo notare, non spiegata prima, è l’utilizzo dei parametri. Le variabili num1 e num2 (in questo caso rispettivamente 79 e 33) vengono passate come parametri alle funzioni somma(), differenza(), prodotto() e quoziente() .

Le funzioni quindi ricevono questi valori e li sostituiscono a quelli dichiarati in fase di definizione, ovvero ad a e b.
Se non avessimo voluto inserire variabili in input avremmo potuto, ad esempio, ottenere la somma dei numeri 79 e 33 scrivendo:

Se avessimo voluto assegnare a una variabile c la somma dei due numeri, avremmo potuto scrivere semplicemente:

Per concludere la lezione, ecco alcuni materiali che potrebbero essere utili per l’approfondimento di quanto visto oggi:

Nella prossima lezione si parlerà degli array. Se ci sono dubbi, domande e curiosità riguardanti quanto visto oggi, non esitate a commentare.

Sinhuè Angelo Rossi