Last updated on Sunday, November 17, 2024

Week 8: Pathfinder

Introduction

In this lab, you will develop a pathfinder solver. You will then implement a simplified version of the game “Bloxorz”, using your solver.

Logistics

• Please review our usual course policies about lab assignments, plagiarism, grading, etc.

• You can get the materials for this lab by running:

  git clone https://gitlab.epfl.ch/lamp/cs-214/pathfinder.git
  

• Once you are done, submit the following files to Moodle:

  src/main/scala/pathfinder/grid/BloxorzDef.scala
  src/main/scala/pathfinder/Solver.scala
  src/main/scala/pathfinder/grid/StringParserTerrain.scala
  src/main/scala/HowManyHoursISpentOnThisLab.scala
  

Setup

The sbt buildBloxorz command will internally run two commands at once:

$ sbt
> bloxorz / compile
> bloxorz / fastLinkJS

fastLinkJS is a command that compiles (and optimizes) the Scala code to JavaScript code. You can also use ~bloxorz / fastLinkJS to automatically recompile the code when you make changes to the source code.

Then, you can open the file bloxorz-www/src/main/www/bloxorz.html in your browser to see the web page. You need to manually recompile the page when you make changes to the source code.

Senior track

If you want to follow this week’s senior track, do not run the unit tests. Run only the system tests, which will check if your solver provides the correct final solution, regardless of intermediate steps.

However, your grade will be based on all tests, including the unit tests. We recommend re-enabling them before submitting.

To run only the system tests, we provide an alias sbt testSenior. Internally, it runs sbt testOnly pathfinder.SolverSystemSuite. Additionally, we suggest creating your own unit tests to verify each function you implement.

Bloxorz

Bloxorz is a game in Flash, which you can access here. As a first step for this assignment, play it for a few levels.

The objective of Bloxorz is simple; you must navigate your rectangular block to the hole at the end of the board, by rolling it, in the fewest number of moves possible.
A block can be moved in 4 possible directions, left, right, up, down, using the appropriate keys on the keyboard.

You will quickly notice that for many levels, you will be, in your head, trying to walk through different configurations of where the block can go in order to reach the goal position. Equipped with some new programming skills, you can now let your computer do the work!

The idea of this assignment is to code a solver for any pathfinding game and apply it to solve a simplified version of this game, with no orange tiles, circles or crosses on the terrain. The goal of your program, given a terrain configuration with a start position and a goal position, is to return the exact sequence of keys to type in order to reach the goal position. Naturally, we will be interested in getting the shortest path as well.

Pathfinding

We will build a general pathfinder program. The goal is to find (one of) the shortest paths from a start state towards a goal state in a specified game definition. Our program will work with 2D grid-like terrain, but is not limited to that. For example, think about the water pouring example from the lecture, it can be written as a BFS problem and our solver can actually solve it.

To find this path, we will use a Breadth-first search algorithm. From a starting state, we will explore all of the states we can reach i.e., its neighbors. Then, we will recursively explore the neighbors of each of them. When we first reach the goal state, we will have found an optimal solution since the distance to the start state is strictly increasing between steps.

Game definition

Let us start by setting up our game foundation. The trait GameDef contains the core logic of a game, required by the solver. It expects a State and Move type parameters which describe how the player is represented and how they move.
Additionally, we define the trait TerrainGameDef which contains all the logic regarding how our 2D terrain is set up.

Positions

2D positions are represented using the Pos case class:

/** The case class `Pos` encodes positions in the terrain.
  *
  * IMPORTANT NOTES
  *   - The `row` coordinate denotes the vertical position on the grid
  *   - The `col` coordinate denotes the horizontal position on the grid
  *   - These coordinates increase when moving down or to the right
  *
  * Illustration:
  *
  * ```
  *     0 1 2 3   <- col axis
  *   0 o o o o
  *   1 o o o o
  *   2 o # o o    # is at position Pos(2, 1)
  *   3 o o o o
  *
  *   ^
  *   |
  *   row axis
  * ```
  */
case class Pos(row: Int, col: Int):
  /** The position obtained by changing the `row` coordinate by `d` */
  def deltaRow(d: Int): Pos = copy(row = row + d)

  /** The position obtained by changing the `col` coordinate by `d` */
  def deltaCol(d: Int): Pos = copy(col = col + d)

Terrain

We represent our terrain as a function from positions to booleans:

/** The terrain is represented as a function from positions to booleans. The
  * function returns `true` for every position that is inside the terrain.
  */
type Terrain = Pos => Boolean

The function returns true for every position that is inside the terrain. Terrains can be created easily from a string representation using the methods in the file StringParserTerrain.scala.

Your first task is to implement two methods in the trait StringParserTerrain that are used to parse the terrain and the start / end positions. The ScalaDoc comments give precise instructions on how they should be implemented.

/** This method returns a terrain function that represents the terrain in
  * `levelVector`. The vector contains a parsed version of the `level` string.
  * For example, the following level
  *
  * ```
  *   val level =
  *     """ST
  *       |oo
  *       |oo""".stripMargin
  * ```
  *
  * is represented as:
  *
  * `Vector(Vector('S', 'T'), Vector('o', 'o'), Vector('o', 'o'))`
  *
  * The resulting function should return `true` if the position `pos` is a
  * valid position (not a '-' character) inside the terrain described by
  * `levelVector`.
  */
def terrainFunction(levelVector: Vector[Vector[Char]]): Pos => Boolean =
  (pos: Pos) =>
    ???

/** This function should return the position of character `c` in the terrain
  * described by `levelVector`. You can assume that `c` appears exactly once
  * in the terrain.
  */
def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos =
  ???

States

GameDef takes State and Move type parameters. A state represents the current state of a game, typically the position of the player. For example, in Bloxorz, a state is a 2 x 1 cuboid block.

Neighbors of a state are the set of states that can be reached by executing 1 move from the current state. For example, if the player occupies a 1 x 1 cell and lies at position Pos(row=1, col=1) and we can move leftwards or rightwards, then the neighbors would be Pos(row=1, col=0) and Pos(row=1, col=2)

In Bloxorz

In Bloxorz, a state is represented as a case class which contains the 2d position of the two cubes that compose the block.

case class BloxorzState(b1: Pos, b2: Pos):

From a state, we can move in four different directions, each time yielding a new state.

/** In Bloxorz, we can move left, right, up or down. */
enum BloxorzMove:
  case Left, Right, Up, Down

To this effect, the methods left, right, up, down, and isStanding are provided. Make sure that the first position b1 is lexicographically smaller than the second position b2 (b1.row <= b2.row && b1.col <= b2.col).

Given these methods, you can now implement the method physicalNeighbors which return a list of tuples: the neighboring blocks, as well as the move to get there. Note that it returns all the physical neighbors, even if they’re not reachable (outside of the terrain):

def physicalNeighbors(state: BloxorzState): Seq[(BloxorzState, BloxorzMove)] =
  ???

Then, implement a method isLegal which tells us whether a state is on the terrain or off it:

/** Returns `true` if the state is entirely inside the terrain. */
def isLegal(state: BloxorzState): Boolean =
  ???

Combining these two functions, you can complete the neighbors which only returns the neighbors that are legal:

def neighbors(state: BloxorzState): Seq[(BloxorzState, BloxorzMove)] =
  ???

Next, we need to implement a method that constructs the initial state for our simulation, the standing block located at the start position:

def startState: BloxorzState =
  ???

Finally, implement a method isDone which determines when we have reached the goal. Remember we reached the goal if we are standing at the goal position:

def isDone(state: BloxorzState): Boolean =
  ???

Play the Game in Browser!

Once you have implemented the above methods in BloxorzDef.scala, you can play the game in the browser. You can use the arrow keys or WASD to move the block around. If a move leads the block to an invalid position, it will stay at the original position. You can reset the game to the initial state using R.

By default, you start at level 0 and when you finish it you’ll automatically go to the next level. You can change the initial level or add new levels by modifying the currentLevel and levels variables in bloxorz-www/src/main/scala/cs214/grid/Bloxorz3D.scala. Make sure you recompile the project and refresh the browser after you make changes to the source code.

Finding the shortest path

To solve the game, we are interested in computing the shortest sequence of moves that takes the game from the initial state to the goal state. The only piece that moves in the game is the block the player controls, so we may as well speak of the ‘block’s initial state’ instead of the ‘initial game state’.

Note that this may be different from finding the shortest path from the starting tile to the goal tile! For example, in Bloxorz, the block doesn’t simply move from tile to tile, but as you’ve seen above, it can occupy one tile or two tiles, and moves by rolling. Hence, we have been representing the block’s state as a BloxorzState with methods to move left, find neighbors (neighboring states that are still on the terrain), etc.

This problem is an instance of a more general graph search problem. In our case, the vertices of the graph are game states, and the edges are valid moves, like left, that connect to the resulting state. Our objective is to find the shortest path in this graph from a given initial state S to the goal state T using the move edges. (We can speak of “the” goal state because there is only one winning state in game, when the block is vertical on the goal tile; but in general, there may be multiple winning states.)

For the sake of illustration, assume we are working with the graph below.

The way we will search is as follows. At all times, we will maintain two lists: one of vertices that we plan to explore, and one of vertices that we have already seen (either because we have already explored them or because we plan to explore them), to avoid exploring them again and possibly ending up in a cycle. At each step, we will take the next vertex that we planned to explore. If it is the goal state, we’re done. Else, we add all its neighbors that we have not already seen to our list of vertices to explore later, and repeat. Thus the steps of our search are:

1. We start at S, we plan to explore it first so we’ve seen it. Seen: [S]. To explore: [S].

2. We haven’t explored S yet but it isn’t the goal state. Its neighbors are A, B, and C. Seen: [S, A, B, C]. To explore: [A, B, C].

   At this point, the “to explore” list contains all vertices at distance 1 from the start:

   

3. We haven’t explored A yet but it isn’t the goal state. Its neighbors are D.

   Seen: [S, A, B, C, D]. To explore: [B, C, D].

4. We haven’t explored B yet but it isn’t the goal state. Its neighbors are A and F. However, since we’ve already seen A, we do not include it.

   Seen: [S, A, B, C, D, F]. To explore: [C, D, F].

5. We haven’t explored C yet but it isn’t the goal state. Its neighbors are F and T. However, since we’ve already seen F, we do not include it.

   Seen: [S, A, B, C, D, F, T]. To explore: [D, F, T].

   At this point, after we’re done exploring all vertices at distance 1, the “to explore” list contains all vertices at distance 2 from the start. (There is a way to get to D with distance 3—S, B, A, D—but the minimum distance is what we’re tracking with our search process.)

   

6. We haven’t explored D yet but it isn’t the goal state. Its neighbors are E.

   Seen: [S, A, B, C, D, E, F, T]. To explore: [F, T, E].

7. We haven’t explored F yet but it isn’t the goal state. Its neighbors are T. However, since we’ve already seen T, we do not include it.

   Seen: [S, A, B, C, D, E, F, T]. To explore: [T, E].

8. The next state to explore is the goal state, T, so we’re done!

But wait—how did we get here? To figure out the sequence of edges, we have to notice that T was added in step 5 because it was a neighbor of C, and that C was added in step 2 because it was a neighbor of S, which was the starting vertex. So the path is S, C, T. This means we need to change our algorithm above to also keep track of the sequence of edges that led to every vertex in our to-explore list. For instance, in step 2, we should write instead in our to-explore list: [B(S), C(S), D(S, A)].

Visualization for Bloxors

At the bottom of our Bloxors UI, there is a schematic rendering of the layout of the level and of the corresponding state graph. Blue nodes represent the block vertical on a single tile; green nodes between two tiles represent the block horizontal on the two tiles; the brown node is the initial state; and the yellow node is the goal state. The arrows are possible moves.

Click “Animate” to see the graph search algorithm progress by one ‘unit of distance’, i.e. one move further out than it was before.

Feeling lazy?

When we found the goal state T in the example above, note that we still had two items remaining in the to-explore list, that were ultimately useless. We did all that work and computed them for nothing! For large graphs, this could be a lot of unnecessary computation. How might we avoid that?

This should remind you of lazy lists! If we represent the to-explore list as a lazy list, then we can compute its elements only as they are needed, and as soon as we find the goal, we can stop. For each vertex that isn’t the goal, we simply append its neighbors to the to-explore list; remember from lecture and the exercises that appending a lazy list to another does not require any of the elements to have actually been evaluated.

Implementing the Solver using Lazy List

Now that everything is set up, we can concentrate on actually coding our solver which is defined in the file Solver.scala.

We could represent a path to a solution as a LazyList[State]. We however also need to make sure we keep the history on our way to the solution. Therefore, a path is represented as a LazyList[(State, List[Move])], where the second part of the pair records the history of moves so far. Unless otherwise noted, the last move is the head element of the List[Move].

Finding Neighbors

In Solver.scala, implement a function neighborsWithHistory, which, given a block, and its history, returns a lazy list of neighboring blocks with the corresponding moves.

/** This function takes two arguments: the current state `s` and a list of
  * moves `history` that was required to reach the position of `s`.
  *
  * The `head` element of the `history` list is the latest move that was
  * executed, i.e. the last move that was performed for the block to end up at
  * state `s`.
  *
  * The function returns a lazy list of pairs: the first element of each pair
  * is a neighboring block, and the second element is the augmented history of
  * moves required to reach this block.
  *
  * It should only return valid neighbors, i.e. block positions that are
  * inside the terrain.
  */
def neighborsWithHistory(s: State, history: List[Move]): LazyList[(State, List[Move])] =
  ???

As mentioned above, the history is ordered so that the most recent move is the head of the list. If you consider Level 1 as defined in BloxorzLevels.scala, then

neighborsWithHistory(BloxorzState(Pos(1,1),Pos(1,1)), List(Left,Up))

results in a lazy list with the following elements in any order:

LazyList(
  (BloxorzState(Pos(1,2),Pos(1,3)), List(Right,Left,Up)),
  (BloxorzState(Pos(2,1),Pos(3,1)), List(Down,Left,Up))
)

Avoiding Circles

While exploring a path, we will also track all the blocks we have explored so far, so as to not get lost in circles of movements (such as sequences of left-right-left-right). Implement a function newNeighborsOnly to this effect:

/** This function returns the list of neighbors without the block positions
  * that have already been explored. We will use it to make sure that we don't
  * explore circular paths.
  */
def newNeighborsOnly(neighbors: LazyList[(State, List[Move])], explored: Set[State]): LazyList[(State, List[Move])] =
  ???

Example usage:

newNeighborsOnly(
  LazyList(
    (BloxorzState(Pos(1,2),Pos(1,3)), List(Right,Left,Up)),
    (BloxorzState(Pos(2,1),Pos(3,1)), List(Down,Left,Up))
  ),
  Set(BloxorzState(Pos(1,2),Pos(1,3)), BloxorzState(Pos(1,1),Pos(1,1)))
)

returns

LazyList((BloxorzState(Pos(2,1),Pos(3,1)), List(Down,Left,Up)))

Finding Solutions

Now to the crux of the solver. Implement a function from, which, given an initial lazy list and a set of explored blocks, creates a lazy list containing the possible paths starting from the head of the initial lazy list:

/** The function `from` returns the lazy list of all possible paths that can
  * be followed, starting at the `head` of the `initial` lazy list.
  *
  * The blocks in the lazy list `initial` are sorted by ascending path length:
  * the block positions with the shortest paths (length of move list) are at
  * the head of the lazy list.
  *
  * The parameter `seen` is a set of block positions that have been visited,
  * or planned to be visited before, on the path to any of the blocks in
  * `initial`. In particular, it contains all states in `initial`. When
  * choosing the next blocks to explore, blocks that have already been seen
  * should not be included a second time to avoid cycles.
  *
  * The resulting lazy list should be sorted by ascending path length, i.e.
  * the block positions that can be reached with the fewest amount of moves
  * should appear first in the lazy list.
  *
  * Note: the solution should not look at or compare the lengths of different
  * paths - the implementation should naturally construct the correctly sorted
  * lazy list.
  */
def from(initial: LazyList[(State, List[Move])], seen: Set[State]): LazyList[(State, List[Move])] =
  ???

Putting Things together

Finally we can define a pathsFromStart which is a lazy list of all the paths that begin at the starting block:

/** The lazy list of all paths that begin at the starting block. */
lazy val pathsFromStart: LazyList[(State, List[Move])] =
  ???

We can also define pathsToGoal which is a lazy list of all possible pairs of goal blocks along with their history. Indeed, there can be more than one road to Rome!

/** Returns a lazy list of all possible pairs of the goal block along with the
  * history how it was reached.
  */
lazy val pathsToGoal: LazyList[(State, List[Move])] =
  ???

To finish it off, we define solution to contain the (or one of the) shortest list(s) of moves that lead(s) to the goal.

Note: the head element of the returned List[Move] should represent the first move that the player should perform from the starting position.

/** The (or one of the) shortest sequence(s) of moves to reach the goal. If
  * the goal cannot be reached, the empty list is returned.
  *
  * Note: the `head` element of the returned list should represent the first
  * move that the player should perform from the starting position.
  */
lazy val solution: List[Move] =
  ???

Testing the Solver

You can now test your solver on the levels defined in Bloxorz3D.scala. Open bloxorz-www/src/www/bloxorz.html to play the game and press Enter to admire your solver finishing the level for you. You are encouraged to add more levels to the game, and test your solver on them.

🔥 (Optional) Create a solver for another game!

This section is not graded.

If you feel aventurous, you can try creating a solver for another game (no need for a UI). Here is a small list of ideas:

• Water pouring example from the lecture
• Pokemon ice puzzle
• Simple 2D maze
• Fill (mobile game)

© 2023, 2024 EPFL. All rights reserved.