IMGD 4000

Project Pathfinding

Due date: Thursday, March 31st, 11:59pm

The goal of this project is to implement A*, a core pathfinding algorithm used by games. Additional goals are to either extend the assignment into a simple game or implement an advanced pathfinding element.


Top | Hints | Submission | Grading

Details

You are to extend the Quick Start Paper 2D Tutorial in the following ways:

  1. Add waypoints. These waypoints must be placeable from the UE4 Level Editor.
  2. Enable connections among the waypoints. An option could be that all waypoints automatically connect to waypoints that are nearby. Another option would be to have the connections manually specified either in the editor or in the code. Connections should have a "cost", either implicit based on distance or explicit based on some external modifier (e.g., representing movement through sand).
  3. Enable selection of a source node and a destination node. The source node could be, for example, the closest node to the player.
  4. Compute the path from source to the destination using A*. There are many Internet sources that describe A*, including slides from IMGD 3000, but all code written must be your own.
  5. Depict the path in some fashion. At the very least, the path should be displayed in text form (e.g., using AddOnScreenDebugMessage()). Better would be to display it with lines.

Successful completion (and demonstration) of the above steps is sufficient for a "B" grade. To achieve an "A" grade, one of the following must be accomplished:

  1. Implement path smoothing as presented in class. Note, you also must implement some obstacles to smooth "around" in this case.
  2. Make a "game" out of the project. As a game, it should have a goal with a win/loss condition. It can be quite basic.

You should be prepared to demo your solution, including your extension for an "A" grade (if any), as well as answer questions about your code and implementation.

You will work alone for this project. You may discuss this project with others, but you must write all the code yourself.


Hints

Waypoints are easiest to extend from the Actor. Having a visible element, such as a sphere, will make them viewable in the level editor.

You are strongly encouraged to check out the tutorial on "Making Waypoints in UE4" (doc, pdf). This walks you through creating Waypoints that are visible in the Level Editor, while allowing C++ code to be written for the A*. Important! Accessing the Blueprint PathNode's "nextNode" variable from C++ is possible, but not advised. An alternate waypoint implementation is to create a PathNode C++ class and then create a Blueprint that inherit's from that class. If you create attributes in the C++ PathNode and prefix them with:

UPROPERTY(EditAnywhere, BlueprintReadWrite)
they will be available for editing from the inherited Blueprint.

Lines between the waypoints, including the computed path, can be shown with DrawDebugLine():

  static void DrawDebugLine (
    UObject *WorldContextObject,
    const FVector LineStart,
    const FVector LineEnd,
    FLinearColor LineColor,
    float Duration,
    float Thickness
  );

For example:

  // Draw a red line.
  FVector start(0.0, 0.0, 0.0);
  FVector end(0.0, 10.0, 0.0);
  DrawDebugLine(GetWorld(), start, end, FColor::Red, 1.0, 12);


Submission

Your assignment is to be submitted electronically no later than 11:59pm on the last day of class. You must hand in the following:

To submit:

  1. Upload your .exe (see above).
  2. Place the README and Source code in a folder with your last name (e.g., "claypool").
  3. Zip up the folder.
  4. Log into the Instruct Assist website:
    https://ia.wpi.edu/imgd4000/

    Use your WPI username and password for access. Visit:

    Tools → File Submission

    Select "Project-Pathfinding" from the dropdown and then "Browse" and select your assignment (claypool.zip).

    Make sure to hit "Upload File" after selecting it!

    If successful, you should see a line similar to:

     Creator    Upload Time           File Name      Size     Status    Removal
     Claypool 2016-04-01 20:33:13    claypool.zip    3508 KB  On Time   Delete
    

IMPORTANT!

After submitting your project, you must arrange a time to provide a demonstration with the TA. On the Instruct Assist website, visit:

Tools → Demonstrations - List → Project-Pathfinding
and select an available slot. Demonstrations will be:

Show up to your slot with game ready and loaded! Don't spent any of your 15 minutes logging in, connecting to the network, loading your game ...


Grading

A grading guide is available.

Grading Guidelines
Placeable Waypoints 5%
Waypoint Connections 20%
Selectable Source & Destination 10%
A* Pathfinding 35%
Path Depiction 20%
Path Smoothing or Game 10%

Below is a general grading rubric:

100-90. The submission clearly meets requirements. The waypoints are placeable from the level editor. The source and destination are selectable. The resulting path is accurate and clearly visible. The path smoothing element is effective and demonstrable or the game implemented is playable with clear win/loss conditions.

89-80. The submission meets requirements. The waypoints are placeable from the level editor. The source or destination are selectable. The resulting path is accurate and mostly visible. The path smoothing element is not implemented effectively or is not clearly demonstrable or the game implemented is somewhat playable but may be missing clear win/loss conditions.

79-70. The submission barely meets requirements. The waypoints may not be (easily) placeable from the level editor. The source and destination is not selectable. The resulting path is inaccurate or not visible. The path smoothing element is not implemented and the game is not implemented

69-60. The submission fails to meet some requirements. Some combination of: a) the waypoints are not placeable from the level editor; b) the source and destination are not selectable; and/or c) the resulting path is inaccurate and not visible. The path smoothing element is not implemented and the game is not implemented.

59-0. The submission fails to meet requirements. The waypoints are not placeable from the level editor. The source and destination are not selectable. The resulting path is inaccurate and not visible. The path smoothing element is not implemented and the game is not implemented.


Top | Hints | Submission | Grading

Return to the IMGD 4000 Home Page

Send all questions to the TA mailing list (imgd4000-staff at cs.wpi.edu).