2. Estats d’un NPC

Un nonplayer-character (NPC) és un personatge d’un videojoc que no està controlat per un jugador, sinó per l’ordinador, com ara un monstre que t’ataca d’un joc de rol, un personatge de suport que t’ajuda a lluitar o, en un joc de construcció, un robot llenyataire com el de la figura, que recull fusta i la duu al magatzem. El comportament d’un NPC es pot modelitzar amb un graf dirigit. Els nodes d’aquest graf són els diferents estats del NPC; les arestes, que indiquen canvis d’un estat a un altre, estan etiquetades amb informació de la condició o esdeveniment que provoca el canvi d’estat.

../../../../_images/npc-llenyataire1.svg

Graf d’estats d’un NPC llenyataire

Representarem el graf d’estats d’un NPC qualsevol mitjançant un networkx.DiGraph. Les arestes tindran un atribut anomenat 'canvi', un string que indica què provoca el canvi d’un estat a l’altre. Per tal de poder fer proves fàcilment us proporcionem el fitxer crea.py, on hi ha funció graf_exemple() que crea i retorna el graf de l’exemple de la figura.

2.1. Funció estats_segons_canvi (2 punts)

Dissenyeu la següent funció i deseu-la al mòdul npc (fitxer npc.py):

npc.estats_segons_canvi(g, c)
Paràmetres:

  • g (DiGraph) – graf d’estats d’un NPC

  • c (str) – etqiqueta d’un canvi (per exemple, “magatzem ple”)

Retorna:

tupla amb dues llistes:

  • Llista ordenada dels estats de g tals que c provoca un canvi d’estat

  • Llista ordenada dels estats de g tals que s’hi arriba amb el canvi c

Cap de les dues llistes retornades no pot contenir elements repetits.

Essent g el graf de la figura, aquesta funció ha de respondre així:


>>> estats_segons_canvi(g, 'arbre trobat')
(['cercant arbre'], ['tallant arbre'])
>>> estats_segons_canvi(g, 'espai en magatzem')
(['en espera', 'ociós'], ['buidant motxilla', 'cercant arbre'])
>>> estats_segons_canvi(g, 'energia=0')
(['buidant motxilla', 'cap al magatzem', 'cercant arbre', 'recollint fusta', 'tallant arbre'], ['morint'])

Disposeu de més jocs de prova en el fitxer tests-estats-canvi.txt.

2.2. Funció camins_de_retorn (1 punt)

Dissenyeu la següent funció i deseu-la al mateix mòdul npc (fitxer npc.py):

npc.camins_de_retorn(g, e)
Paràmetres:

  • g (DiGraph) – graf d’estats d’un NPC

  • e (str) – un dels estats de g

Retorna:

llista amb tots els cicles de g que parteixen de l’estat e. En altres paraules, llista de tots els camins que, partint de l’estat e, arriben al mateix estat e sense passar dues vegades per un mateix node (llevat de e, no cal dir-ho).

Observacions:

  • Cada cicle de la llista retornada ha de ser una llista que comença i acaba amb el node e.

  • El cicle trivial [e, e] no ha de formar part de la llista retornada.

  • És indiferent com estigui ordenada la llista de cicles.

Essent g el graf de la figura, aquesta funció ha de respondre així:


>>> camins_de_retorn(g, 'morint')
[]
>>> camins_de_retorn(g, 'en espera')
[['en espera', 'buidant motxilla', 'en espera']]
>>> sorted(camins_de_retorn(g, 'ociós'))   # usem sorted() perquè és indiferent l'ordre de la llista retornada
[['ociós', 'cercant arbre', 'ociós'], ['ociós', 'cercant arbre', 'tallant arbre', 'recollint fusta', 'cap al magatzem', 'buidant motxilla', 'ociós']]

Disposeu de més jocs de prova en el fitxer tests-retorn.txt.