Unit 6 - Activity 1 Map Pathfinding Strategies

Activity Overview

This activity frames map games within the concept of computational pathfinding, exploring the concepts of graphs and how they are used in the programming and design of computing systems.

Key Terms and Concepts

  • PATHFINDING is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes.
  • GRAPHS are sets of vertices connected by edges, where the edges may have a direction associated with them.

    • Key Takeaways:

  • Players can think strategically about how to go from start to goal state while playing map games. Programmers commonly use graphs to represent simply-connected data.

    • Driving Questions:

  • What are the elements of the game map that we focus on when trying to get to the goal?
  • What is the simplest way to get from the start tile to the goal tile in the map game?
  • Are there more strategic ways to get from the start tile to the goal tile in the map game?
  • How can we represent map games in graph form?

    • Materials and Preparation:

    MATERIALS

    1. Projector
    2. Computer
    PREPARATION

    Instructors should identify a map-related game for students to play prior to this workshop. Examples include but are not limited to: Minecraft, PacMan, Legend of Zelda, map games on Scratch, or Mazzy. Please refer to Unit 4: Activity 1 for additional details and guidance.

    Activity Instructions

    1. Discussing Map Game Strategies (15 minutes)
      2.
      • Briefly review the experience students had playing map-related games and have them consider their experience playing the map game and thinking through strategies for finding paths.
      • For example, we can consider a simple map grid in the game Mazzy.
      • ASK: What are the elements of the game map that we focus on when trying to get to the goal?
      • Discuss the fact that we tend to focus on 4 main elements when playing map games:
        • walkable tiles (where the player can move)
        • non-walkable tiles (where the player is not allowed to move)
        • start tile (where the player avatar is placed at the beginning)
        • goal tile (where the player is supposed to reach to win the level)
      • For example, we can consider a simplified representation of the Mazzy game:
        • the light-blue colored tiles represent the tiles we can walk on
        • the dark-grey colored tiles represent the tiles we can NOT walk on
        • the avatar is located at the start tile
        • the target symbol represents the “goal” tile, which is where we want to get to
      • ASK: What is the simplest way to get from the start tile to the goal tile in the map game?
      • Have students “speak out loud” the mental process for how they would think about getting their avatar from the start tile to the goal tile, as if they were explaining it step-by-step to a little brother or sister.
      • For example “My avatar is starting at this tile, I am going to look around my avatar and see which tiles it can move to. Then, I will do XYZ.”
      • Explain that the most basic thing to do would be to:
        • choose a path to travel on first
        • go as far as we can go on that path to see if it gets us to the goal node
        • If it doesn’t, start back at the beginning and do the same with the next possible path
        • continue so on, and so forth, until we reach the goal tile
      • ASK: Are there more strategic ways to get from the start tile to the goal tile in the map game?
      • Explain that a more “sophisticated” thing to do would be to:
        • consider all of the possible paths on the map “in parallel”
        • choose only the best one to reach the goal tile
    2. Representing Game Maps With Graphs (20 minutes)
      3.
      • Explain that in computer science, maps like these can easily be programmed and represented using “graphs” which contain nodes and arrows. The directions on the arrows show the ways that we can “traverse” (step) from node to node. So, all that matters is:
        • how the nodes are ordered
        • their connections to one another
      • ASK: How can we represent map games in graph form?
      • Explain that, for example, we can transform the Mazzy game map to represent it as a graph:
      • Explain that the graph representation of the map would be logically equivalent to the visual map in the game itself, in terms functionality and relationships between nodes.
      • Explain that graphs are good for modeling real world problems like representing cities which are connected by roads and finding the paths between cities, air traffic controller systems, etc.
      • Have students consider a few examples of graph representations, and check for their understanding of equivalence by ensuring they understand a graph is equivalent if both of the following are the same in both graphs:
        • how the nodes are ordered
        • their connections to one another
      • For example, you could consider the following equivalent graphs, which are presenting in two different ways:
      • Explain that the strategies we discussed are two common strategies for “pathfinding” which involves:
        • searching a graph
        • starting at one point on the graph
        • exploring adjacent nodes until the destination node is reached
        • usually attempting to identify the “cheapest” route
      • Transition to the end of the discussion and have students consider how they might represent the neighborhoods within their city or stops on a train using a graph.

    © MIT Imagination, Computation, and Expression Laboratory 2017.
    This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 United States License.