Assignment 2: FSM Framework

In this assignment, you will design and implement a framework for finite-state machine (FSM) based artificial intelligence. This will increase your practical understanding of:

  • the use of finite state machines for specifying AI behaviour
  • the implementation of AI frameworks within a game engine
  • the scheduling (or allocation of time) to AI agents

Overview

Finite state machines are widely used to implement the functionality of AI agents. Rather than requiring developers to start from scratch with every finite state machine, engines often provide some kind of framework to make it easier to create and deploy FSMs. In this assignment, you will create a set of classes supporting the development of AI behaviour with FSMs. You will demonstrate this in a simple 3D world where NPCs are tasked with gathering fruit.

Getting Sample Code

To help you test your FSM framework,I have provided a sample application, including a terrain and a single NPC (a villager). The villager has a set of four animations attached, for walking, idling, picking fruit, and dropping the fruit off.

If you execute the application, you will find that the villager walks to the tree, and picks fruit.

The application includes an animator controller called ElfVillagerCtl. You do not need to understand this controller in order to do the assignment, but if you wish to learn about how it works, refer to the relevant Unity documentation. To control animation in this clip (e.g., to switch from walking to picking fruit), you need to trigger animation events. The script in Villager.cs shows examples of how this is done.

To get the sample application:

  • Dowload it from OnQ: it is attached to the assignment description
  • Unzip the project
  • In Unity, select File | Open Project
  • In the resulting dialogue box, select "Open Other"
  • Navigate into the CISC486As2-stripped folder, and select "Open"
  • In the project, open the "Walker" scene in your project assets

Part 1: FSM Framework

Design and implement a framework making it easy to create finite state machines for encoding NPC behaviour. I suggest that the core of your framework include a class FSM which implements finite state machine behaviour, and a class FSMNode, which implements a single node of the finite state machine.

Users of your framework would create specialized classes for each node, deriving from the FSMNode class. A finite state machine class (deriving from FSM) would create instances of these nodes and transitions.

To use the finite state machine, it is simply attached to an NPC's game object in the Unity visual editor.

I suggest creating a class FSMScheduler whose job it is to start all finite state machines.

Part 2: Testing the FSM Framework

To test the framework, create a finite state machine adding behaviour to the villager NPC provided in the sample code. The NPC's job is to pick fruit from three trees. These trees are specially marked with a "fruit tree" tag. The rules are:

  • Each tree has three pieces of fruit
  • The villager can carry up to two pieces of fruit
  • Whenever she has collected two pieces of fruit, she must go back to the village and drop them off
  • She must continue until all fruit has been collected.

The finite state machine should be built using the framework you have developed in part 1.

Once you have demonstrated your FSM with the villager, add a second villager. (The second villager, "Fred", is in the scene, but needs to be activated in the inspector to be visible.) Attach the same FSM to this NPC.

Part 3: Level of Detail Scheduling

In the implementation you performed in parts 1 and 2, you most likely are updating your FSMs every frame. In games with a large number of NPCs, this will lead to poor performance.

Modify your FSM scheduler so that it can provide two levels of priority. High priority FSMs are updated every frame. Low priority FSMs are updated once per second.

Demonstrate this by assigning high priority to one of your villager NPCs and low priority to the other.

Part 4: Questions

Provide brief answers to the following questions.

  1. Create a class diagram of your FSM framework. Show the key classes, and any public attributes and operations. I suggest using the UMLet UML diagram editor to create your class diagrams. Your diagram should show just the framework, not the game itself using the framework. Provide brief English-language text to explain the important elements of the class diagram.

  2. We have arbitrarily assigned priorities to your two NPCs. Describe a more interesting priority assignment algorithm that could be implemented in your level-of-detail scheduler. Your description should clearly explain the criteria used to determine the priority assigned to FSM's. No implementation is required for this question.

  3. Based on your experience implementing a finite state machine in this assignment, explain the difficulties inherent in implementing a graphical editor for finite state machines. Specifically consider what information is provided about FSM's in code that would be challenging to specify in a graphical editor.

Part 5: Optional Extensions

These extensions are not for credit, but will help you learn more deeply about this aspect of game engine development. You may choose to do any or none of these additional problems. Or you can wait until term is over, and do them on your own time for fun and further education.

  • The NPCs use a very poor steering algorithm, which can result in their walking through buildings or across water. Replace the steering algorithm with a Unity NavMesh.
  • Implement a more interesting priority algorithm for your level of detail scheduling, as discussed in part 4 above.
  • Implement another NPC behaviour. For example, introduce an NPC whose job is to find trees. Change the fruit-gathering NPCs to only visit trees that have been found.

To Hand In

Using OnQ, submit two files: (1) a link to your code for parts 1-3, and (2) a report answering the questions from part 4.

Your modified code should be a zip file containing a folder called fsm-yourLastName. That folder should contain your full running solution to parts 1-3, as a Unity project. If your project doesn't work, include a description in your report specifying what does and does not work.

Your report should be in PDF format. It should include your name and a title (e.g., Assignment 2 Report). Use 11 pt type with at least 1" margins. UML diagrams should be integrated into the report, not submitted as raw UMLet files.

Evaluation

This assignment will be graded using the rubric posted on OnQ. It is advisable to review this rubric in advance of submitting your work.

© 2019 Nicholas Graham