Esercitazioni del corso di Fondamenti di Informatica

Ingegneria Informatica, Elettronica, Automazione, I anno

Esercitazioni, versione 2017-2018

Introduzione a Python (corso People@DEIB)

Programma delle esercitazioni (2015-2016)

Python

Per avvicinarsi a Python, è possibile avvalersi di vari testi liberamente disponibili in formato pdf o html, fra cui:

Inoltre, ho raccolto quanto visto a lezione in questo notebook Jupyter. Qui le slide corrispondenti.

Applicazioni di esempio

Sia per il linguaggio C, sia per Python fornisco una applicazione di esempio.

Python: Space-themed 3x turn-based strategy game

Nel caso di Python si tratta un gioco di strategia a turni. Qui c'è l'ultima versione, in cui ho implementato un modo standard per aggiungere nuove varianti dell'intelligenza artificiale. Potete provare a implementare nuove AI, e testarle con il programma main.py, che vi consente di far giocare varie AI le une contro le altre in combinazioni casuali.

Python: Saucers, a real time shoot 'em up

Un secondo gioco, piu' semplice, dimostra come si possono realizzare applicazioni grafiche real time. Presento sei diverse versioni. La prima, che non fa uso di costrutti avanzati di Python, è molto semplice ma non include un vero e proprio gameplay (semplicemente, mostra un disco volante che puo' muoversi in uno spazio bidimensionale). La versione piu' avanzata consente non solo di colpire i dischi nemici con proiettili, ma anche di conservare traccia dei punteggi realizzati in un apposito file.

C: roguelike

Come detto durante le ultime esercitazioni prima della pausa, questo piccolo gioco può essere usato come base per vari esercizi.

Un esempio di esercizio svolto è l'implementazione dell'attacco da parte dei mostri, che mostra come impiegare utilmente i costrutti switch e static per ottenere un iteratore sui mostri che si trovano nelle caselle adiacenti a quella dove si trova il personaggio giocante.

Alcuni esercizi semplici dal punto di vista concettuale sono i seguenti:

  1. Muovere in modo casuale i mostri (assumete una velocità di 1 casella per turno)
  2. Visualizzare il contenuto dell'inventario (usate una schermata “nuova”, e ripristinate quella originale in seguito; avvantaggiatevi del fatto che l'inventario contiene al più 25 oggetti diversi)
  3. Raccogliere gli oggetti (comando PICK) e inserirli nell'inventario
  4. Lasciar cadere un oggetto presente nell'inventario (comando DROP)
  5. Mangiare un oggetto edibile per recuperare punti nelle varie abilità (decidete voi quali cibi permettono di recuperare punti in quali abilità)
  6. Usare armi (WIELD) e introdurre i loro effetti nel combattimento corpo a corpo. Suggerimento: armi piccole infliggono 2 (o 1d4 se preferite danni casuali) punti di danno, armi medie 4 o 1d8, armi grandi 6 o 1d12
  7. Inserire nel gioco nuovi oggetti utilizzabili (ad esempio, bacchette magiche o pozioni)
  8. Salvare e ricaricare il gioco
  9. Consentire al giocatore di creare il personaggio invece di crearlo in modo casuale

Parte Seconda

Un altro esercizio, decisamente più complesso, riguarda la determinazione della visibilità (line of sight) fra due posizioni (tipicamente quella del personaggio giocante e la posizione di un mostro o di un oggetto). Si può realizzare questo tipo di funzionalità sfruttando l'algoritmo di Bresenham. Oltre al controllo di visibilità dei mostri e degli oggetti (utile per mostrare nella schermata di gioco solo i mostri e gli oggetti effettivamente in vista, i.e. per la “fog of war”), la line of sight serve anche per determinare l'area esplorata dal personaggio, e mostrare a video solo quella parte del dungeon. Qui trovate l'implementazione dell'algoritmo di Bresenham e delle sue applicazioni principali nel gioco. Il grosso delle modifiche riguarda il file level.c. Nei prossimi giorni vedremo come applicare lo stesso concetto per consentire ai mostri di individuare e inseguire il personaggio.

Con la funzione line_of_sight, potete ora realizzare anche altri esercizi semplici, come i seguenti:

  1. Attacchi a distanza (con arco e frecce o altre armi simili; considerate l'arco un'arma media)
  2. Attacchi con incantesimi (cominciate con un semplice “dardo incantato” che infligge 3 o 1d6 punti ferita)
  3. Ovviamente, potete introdurre mostri con abilità magiche o armi a distanza; questo potrebbe richiedere qualche modifica nelle strutture che descrivono i mostri, o anche no (e.g., assumendo che i mostri infliggano danni a distanza o da incantesimi pari ai normali danni da mischia)

Nota: nella terza versione ho inserito anche un supporto generico per le liste, che sarà utile in seguito, ad esempio per realizzare un dungeon multilivello come lista di livelli.

Parte Terza

Come promesso, ecco una quarta versione del gioco, con un po' di funzionalità in più. In questa versione, ci concentriamo sulla gestione del movimento dei mostri. Per semplicità, manteniamo separato il caso dei mostri adiacenti al personaggio, e creiamo un nuovo campo turn nella descrizione di ciascun mostro, che ci consente di determinare se un mostro ha già agito nel turno, oppure no. In questo modo, possiamo creare ora una funzione statica che restituisce uno alla volta tutti i mostri che non hanno ancora agito, e usarla in game.c nella funzione principale per gestire le loro azioni. Una funzione monster_ai nel file monsters.c implementa la scelta dell'azione in una gamma definita da un set enumerativo (enum). Al momento la scelta è piuttosto semplice: i mostri attaccano il personaggio (o gli si avvicinano se lontani) quando lo vedono, e quando i loro punti ferita sono ancora abbastanza alti. Se invece hanno pochi punti ferita (hits) tendono a fuggire. Se non vedono il personaggio, si muovono casualmente, o rimangono fermi.

Nel file level.c ci sono ora molte funzioni relative alla gestione del movimento e delle direzioni, che richiedono l'uso dei tipi monster e Level. In realtà, a questo punto level.c è troppo complesso. Sarebbe opportuno spostare le funzionalità diverse dal semplice caricamento del livello in una coppia di file (.c e .h) separati. Questo è lasciato (al momento) come esercizio.

Altri esercizi semplici che potete svolgere sulla base di questa versione del gioco sono i seguenti:

  1. Rendere più realistica l'intelligenza artificiale dei mostri: ad esempio, i mostri feriti gravemente potrebbero continuare ad attaccare il personaggio se anche questi è gravemente ferito. Usate un tiro casuale (d20()) con il bonus mind del mostro per valutare le condizioni del personaggio.
  2. Al momento i mostri si muovono verso i loro obiettivi solo in linea retta. Gestire il caso in cui c'è un ostacolo, cercando di spostarsi nella direzione migliore (e.g., il mostro vuole andare verso SOUTH, ma c'è un muro o un altro mostro, proverà allora a spostarsi verso SOUTHEAST o SOUTHWEST).
  3. Introdurre la gestione della velocità: usate il rapporto fra le caratteristiche di speed del personaggio e dei mostri per determinare chi è più veloce. E.g., se la velocità del personaggio è almeno 2x la velocità del mostro, quest'ultimo agisce solo una volta ogni due turni. Suggerimento: i turni sono visti dal punto di vista del personaggio (che agisce quindi sempre una volta per turno), mentre i mostri possono agire anche più volte (o meno) per turno, a seconda della velocità relativa.

Parte Quarta

E ultima, visto che le vacanze sono quasi finite. Arrivati alla versione che trovate nella terza parte, risulta evidente che il file level.c sta assorbendo troppe funzionalità. E' preferibile allora estrarre le parti relative al comportamento dei mostri, aggiungendo una nuova coppia di file enemyactions.c e enemyactions.h, tanto più che in level.c avremo bisogno di ulteriori funzionalità per gestire l'ultima caratteristica primaria che vogliamo aggiungere, ovvero la possibilità di avere un numero illimitato (memoria permettendo) di livelli.

Vediamo allora l'implementazione, che trovate in questo file. Concettualmente, ci sono pochi punti importanti da considerare:

  • Gestire più livelli richiede più file di configurazione (due per ogni livello). Pertanto trovate altri due file di configurazione di esempio (test_level_2.txt e test_level_2_map.txt)
  • Dobbiamo gestire il passaggio da un livello all'altro. Per questo usiamo le scale, che rappresentiamo con i simboli < e > rispettivamente per scale che salgono e scendono.
  • Assumiamo che una scala in posizione (x,y) al livello A ci conduca alla posizione corrispondente nel livello B. In tal modo, dobbiamo solo rappresentare la destinazione della scala come livello, e non anche come coppia di posizioni.
  • Nel file di configurazione, aggiungiamo delle linee del tipo [x,y]:< filename.txt per rappresentare le scale (in questo caso verso l'alto).
  • Nella descrizione dellivello, riportiamo il simbolo della scala direttamente nella mappa (tanto non può essere spostato o rimosso), e aggiungiamo in content un campo stairs_to che rappresenta la destinazione.
  • Poichè il livello destinazione potrebbe non essere ancora stato caricato, il caricamento dei livelli diventa una funzione ricorsiva. Inoltre, non restituisce più un unico livello, ma una lista di livelli.
  • Di conseguenza, usiamo le liste generiche implementate in list.c. Notate che il tipo di dato contenuto nella lista non è specificato (void *), quindi dobbiamo tenerne traccia noi (qui non è un problema, dato che per il momento abbiamo una sola lista).
  • L'implementazione della lista generica usa due puntatori a funzione come parametri delle funzioni di ricerca e ordinamento. In sostanza, questi servono per specificare come svolgere i confronti fra dati la cui natura è ignota alla libreria che implementa le liste. L'uso dei puntatori a funzione va limitato a questo tipo di situazioni.

Notate che al passaggio del personaggio da un livello all'altro, il livello non più attivo rimane “congelato”, ma gli effetti delle azioni compiute dal personaggio permangono – tornando nel livello appena lasciato, ad esempio, i mostri uccisi non ricompaiono.

Aggiungiamo anche un caso speciale di scala, quella verso l'esterno. Questa si specifica nel file di configurazione come [x,y]:< exit, e permette di terminare il gioco. Viene stampata una scritta di commiato, comprensiva del numero di XP raccolti dal personaggio, dopodichè il gioco termina.

Altri esercizi che fanno uso di liste e dei livelli multipli includono:

  1. Mantenere (in un file separato, tradizionalmente chiamato morgue.txt) e mostrare alla fine della partita una lista di “high score”, ordinati per XP decrescenti. Potete usare le liste e la funzione sort per ordinare i punteggi, senza mantererli necessariamente ordinati nel file morgue.txt.
  2. Trasformare level→objs da array a lista di content.
  3. Inserire nel gioco dei portali. Un portale consente di spostarsi in un altro livello (o in quello corrente), ma non nella medesima posizione (la posizione di arrivo deve quindi essere specificata esplicitamente).
  4. Scrivere una funzione che controlli che la definizione di un insieme di livelli non presenti errori o incoerenze (e.g., se due livelli sono collegati da scale, queste devono essere presenti in entrambi i livelli, e devono essere discendenti nel livello superiore e ascendenti in quello inferiore). La funzione può essere anche utilizzata da un programma separato, la cui funzionalità è solo quella di verificare la correttezza dell'intero dungeon.
  5. Al momento, se il personaggio si trova nella posizione x,y al livello A e scende le scale verso il livello B, si ritrova nella posizione x,y al livello B. Questo potrebbe non essere possibile, in quanto potrebbe esserci un muro o un mostro. Verificare e/o risolvere questo tipo di problema (o spostando la posizione di arrivo, o facendo sì che la posizione di arrivo sia quella della scala).

Nota: qui potete trovare una versione ulteriormente semplificata (rispetto a quella vista a lezione) del gioco, senza oggetti nè mostri. Può essere utile come punto di partenza per implementare in modo diverso oggetti e mostri. Sarebbe possibile semplificare ulteriormente il gioco, eliminando le caratteristiche del personaggio (comunque inutilizzate in questa versione molto semplice). Il codice risultante potete scaricarlo qui.

Documenti utili

Raccolgo qui materiali vari che possono risultare utili, ma non sono direttamente connessi con le esercitazioni. Principalmente, riguardano la programmazione in linguaggio assembler per architetture ARM.

Bibliografia

Le fonti citate qui sono suggerimenti per chi desidera approfondire alcuni dei temi visti nelle esercitazioni, non materiali del corso.

  • David Harel with Yshai Feldman, Algorithmics: The Spirit of Computing, 3rd edition, Addison Wesley 2004
  • Brian W. Kernighan, Dennis M. Ritchie, Il linguaggio C: principi di programmazione e manuale di riferimento, 2nda edizione, Pearson 2007
  • Brian W. Kernighan, Rob Pike, The Practice of Programming, Addison Wesley, 1999
  • Neal Stephenson, In the Beginning was the Command Line, available from the author's website, 1999
  • Neal Stephenson, Cryptonomicon, Harper Collins 2002
  • Al Sweigart, Invent Your Own Computer Games with Python, available online website
  • Raspberry Pi, an ARM development board under 25 euro, running Ubuntu Linux

Programmi e materiali degli anni precedenti

Programma delle esercitazioni (2014)

Programma delle esercitazioni (2012)

Programma delle esercitazioni (2011)

Data Argomenti Materiali
27/09 Algebra di Boole, Rappresentazione dei numeri
14/10 Linguaggi di programmazione: C, Assembler (1) Sintesi GNU as e ARM ISA, semplici programmi in assembler ARM
21/10 Linguaggio di programmazione C: stringhe e array esercizi sulle stringhe
28/10 Funzioni e Strutture esercizi su funzioni e strutture
4/11 Definizione di nuovi tipi di dato in C esercizi su funzioni e strutture, schema dell'architettura del programma
7/11 Esercizi di preparazione per l'esame esercizi, soluzioni degli esercizi da corsi online
8/11 Esercizi di preparazione per l'esame esercizi
25/11 Puntatori e chiamata di funzioni introduzione all'assembler e struttura a basso livello di una chiamata di funzione
12/12 Ricorsione
13/12 Ricorsione + File
16/12 Ricorsione + Liste Esercizi
10/01 Liste Esercizi sulle liste
16/01 Processi Esercizi sui processi
17/01 Esercizi vari Esercizio ecopass
Esercitazione riassuntiva
teaching/info1tlc.txt · Last modified: 2018/01/15 15:20 by agosta
Recent changes RSS feed Creative Commons License Donate Driven by DokuWiki