1. 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-llenyataire.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.

1.1. Funció parelles (2 punts)

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

npc.parelles(g)
Paràmetres:

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

Retorna:

llista de parelles d’estats (x, y) tals que hi ha un canvi en g que duu directament de x a y i un altre que duu de y a x. Cadascuna de les parelles de la llista retornada ha de ser tal que x < y. A més, la llista ha d’estar ordenada lexicogràficament (l’ordre per defecte de Python).

Tipus de retorn:

llista de tuples de parelles de strings

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


>>> parelles(g)
[('buidant motxilla', 'en espera'), ('cercant arbre', 'ociós')]

>>> g.add_edge('cap al magatzem', 'recollint fusta', canvi='ensopega')
>>> parelles(g)
[('buidant motxilla', 'en espera'), ('cap al magatzem', 'recollint fusta'), ('cercant arbre', 'ociós')]

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

1.2. Funció llista_canvis (2 punts)

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

npc.llista_canvis(g, e1, e2)
Paràmetres:

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

  • e1 (str) – un dels estats de g

  • e2 (str) – un dels estats de g

Retorna:

llista més curta dels canvis que provoquen que el NPC passi de l’estat e1 a l’estat e2. Si hi més d’una possibilitat amb el mínim nombre de canvis, la funció retorna qualsevol de les llistes de canvis més curtes. Si no hi ha cap possibilitat, cal retornar la llista buida.

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


>>> llista_canvis(g, 'ociós', 'tallant arbre')
['espai en magatzem', 'arbre trobat']
>>> llista_canvis(g, 'morint', 'tallant arbre')
[]
>>> llista_canvis(g, 'cercant arbre', 'buidant motxilla')
['arbre trobat', 'arbre tallat', 'motxilla plena', 'al magatzem']

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