Estats d'un NPC
===============

.. py:module:: npc
   :noindex:

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.

.. figure:: npc-llenyataire.svg
   :width: 90 %
   :align: center

   Graf d'estats d'un NPC llenyataire

Representarem el graf d'estats d'un NPC qualsevol mitjançant un :py:class:`networkx.DiGraph`. Les arestes tindran un atribut anomenat :py:const:`'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 :download:`crea.py`, on hi ha funció :py:func:`graf_exemple` que crea i retorna el graf de l'exemple de la figura.


Funció `estats_segons_canvi` (2 punts)
--------------------------------------

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

  .. py:function:: estats_segons_canvi(g, c)

     :param ~networkx.DiGraph g: graf d'estats d'un NPC
     :param str c: etqiqueta d'un canvi (per exemple, 'magatzem ple')
     :return: 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í:

.. literalinclude:: tests-estats-canvi.txt
   :language: pycon
   :start-after: --ini-enunciat
   :end-before: --fi-enunciat
                
Disposeu de més jocs de prova en el fitxer :download:`tests-estats-canvi.txt`.


Funció `camins_de_retorn` (1 punt)
----------------------------------

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

  .. py:function:: camins_de_retorn(g, e)

     :param ~networkx.DiGraph g: graf d'estats d'un NPC
     :param str e: un dels estats de `g`
     :return: 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í:

.. literalinclude:: tests-retorn.txt
   :language: pycon
   :start-after: --ini-enunciat
   :end-before: --fi-enunciat
                
Disposeu de més jocs de prova en el fitxer :download:`tests-retorn.txt`.