Project 04: Pathfinding

---

Individual, Due: 2025 Oct 31, 11:59pm

In this assignment, you will implement a practical algorithm used to find an efficiently traversable path between two points.

This assignment is based on web exercises from the Algorithms 4/e book website.

Introduction

---

This section introduces the general idea of path finding, different ways we can model the pathfinding problem, and some extensions that will count as extra credit.

The Pathfinding Problem

---

In general, a pathfinding algorithm searches for the "shortest" or "best" path from one node in a graph to another. Nodes represent locations and are connected by edges. Edges represent an ability to move between the end nodes, and each edge has an associated weight representing the cost of moving across the edge. The "shortest" or "best" path between any two nodes is a sequence of edges connecting the two nodes that has the smallest sum of weights. In other words, there may be many possible sequences of edges that connect the two nodes, but we are interested in choosing only the sequence that is or is close to the optimal.

Pathfinding is a very common algorithm that is applied in many ways. Below is a short list of pathfinding examples.

• navigating swarm of drones navigating through obstacle course while maintaining formation
• Hipmunk.com: finding a sequence of flights from Indianapolis to Amsterdam with least agony
• Google Maps finding a toll-free route from Upland, IN to Geneva, IL
• solving a 15-puzzle
• solving maze puzzles
• finding the degrees of separation between an actor and Kevin Bacon

Given enough time a breadth-first search algorithm will find a solution assuming one exists, but such a searching solution does not scale well, especially as the dimensionality of movement increases. In this assignment, you will implement Dijkstra's Algorithm and a variant of this called the A* Algorithm, both of which find a solution efficiently. The figures below show the solution (pink path) to the maze from the figure above, where the searched area is tinted magenta. Although the two figures show exactly the same (optimal) path, they use different heuristic coefficient values, and therefore the area of searching is different. The starting point is the upper-left corner, and the ending point is the upper-right corner.

We can use these same pathfinding algorithms to solve all types of mazes.

Nearly all real-time strategy video games use pathfinding to control character movements. The player selects a character and then specifies a destination, and the character starts moving toward the location. The difficulty in this scenario is that there are obstacles (buildings, other characters, etc.) or terrain types that have varying easiness in traversal (walking on pavement is usually easier than walking on sand). If the pathfinding algorithm takes this variability into account, the character will could choose routes that move it more quickly to the destination.

We will modify our pathfinding algorithm to account for elevation change. A character can move easily from one location to a nearby location if the elevation does not change. However, the more the elevation changes (either up or down), the more difficult moving there becomes.

The figures below show a top-down view of a randomly generated terrain. The black color represents sea-level, and the bright green represents higher ground above water. The starting point is drawn as a large blue circle near the bottom, and the ending point is a large red circle closer to the top-left corner. The top-right, bottom-left, and bottom-right figures visualize three different paths. Note that the path taken in the bottom-right figure would be shorter to go "as the crow flies" between the two points, the change in elevation along that path would make for difficult travel.

Modeling the Pathfinding Problem, Dijkstra's, and the A* Search

---

We will use several data structures to solve this problem, notably the priority queue, the linked list (tree), and the array. For the priority queue, use the MinPQ data type provided by the algs4.jar library. You will implement a simple linked-list node that will be the key to MinPQ, therefore it will need to implement the Comparable interface.

As an aside, we could solve this problem using less memory on average (the worst case is same) using other data structures, but we have not yet learned about them yet. Furthermore, we are trading off some computation time (remove key from priority queue) for memory usage (keys can be invalidated).

Cost Model: Manhattan Distance

To determine a path, we will begin at the path's starting coordinate and expand outward in all directions until we reach the ending coordinate. For every coordinate we explore, we will create an object that records a path back to the starting location.

To keep track of where we've explored and where we're searching next, we can use a queue. Simply start by enqueueing the starting location. Then, while the queue is not empty, dequeue the next location to process, and enqueue all unexplored neighboring locations.

For example, suppose we have the following simple terrain, where S indicates the path's starting location and E indicates the end.

	0	1	2	3	4
0
1		S
2
3					E
4

Now, if we expanded out in all cardinal directions (up, down, left, right) from S and remember the way back, we would see the following.

	0	1	2	3	4
0		⇣
1	⇢	S	⇠
2		⇡
3					E
4

Expanding once more...

	0	1	2	3	4
0	⇢	⇣	⇣
1	⇢	S	⇠	⇠
2	⇡	⇡	⇠
3		⇡			E
4

Note that in this example, the top-left spot could point to the right or down, but both paths take the same time. Continuing this fully, we get the following.

	0	1	2	3	4
0	⇢	⇣	⇣	⇠	⇠
1	⇢	S	⇠	⇠	⇠
2	⇡	⇡	⇠	⇠	⇠
3	⇢	⇡	⇠	⇡	⇡ E
4	⇢	⇡	⇡	⇡	⇠

If we follow the path back from E to S, we get: ⇡ ⇠ ⇠ ⇠ ⇡. Note: this is in reverse order if we want to start at S and end at E, but we can easily compute that path by reversing the steps. The diagram below visualizes the shortest path, where the cost of a path is equal to the number of steps/movements.

	0	1	2	3	4
0
1		S
2		⇡	⇠	⇠	⇠
3					⇡ E
4

The algorithm above runs in \(N^2\) time but always finds an optimal route. Note: some maps might not have a single, unique route; there might be several optimal routes that all have the same distance.

So far, this is not a very interesting problem, yet. Let's see how we can generalize the model, and begin tackling interesting problems!

Cost Model: Position Cost

An example of a more interesting problem is this: what if some of those squares are more costly to cross (e.g., takes more time to cross such as with quicksand or ice)? We could model this by assigning values to each point on the grid, and then as we explore out we accumulate the values (stored at each point along with the way back). This time, though, if there are two or more possible ways to go, we choose the cheapest path. Below is an example, where the left table shows S and E, and the right table shows the traversal cost at each grid point.

	0	1	2	3	4			0	1	2	3	4
0							0	+1	+1	+1	+1	+5
1		S					1	+9	+0	+4	+1	+1
2							2	+9	+9	+4	+8	+2
3					E		3	+1	+7	+4	+2	+1
4							4	+1	+1	+2	+4	+1

Starting at S and accumulating while expanding out, we would see the following diagram. If we follow the path back from E to S, we get: ⇡ ⇡ ⇠ ⇡ ⇠ ⇠ ⇣. Notice that this path (highlighted in pink) is the cheapest path to take.

	0	1	2	3	4
0	⇢ 2	⇣ 1	⇠ 2	⇠ 3	⇠ 8
1	⇢ 9	S	⇠ 4	⇡ 4	⇠ 5
2	⇢ 18	⇡ 9	⇡ 8	⇡ 12	⇡ 7
3	⇢ 17	⇡ 16	⇡ 12	⇢ 10	⇡ 8
4	⇡ 18	⇡ 17	⇡ 14	⇡ 14	⇡ 9

Dijkstra's Algorithm: Searching Only What Is Necessary

A careful observer would notice that we actually do not need to fill in the entire table. In fact, since the shortest path costs \(8\), then any number greater than \(8\) does not need to be checked (ex: bottom-left corner at \(18\)).

A simple way to take this into account and therefore only compute what is absolutely necessary is to use a minimum priority queue (as opposed to a "plain vanilla" queue). We start by placing in this queue the starting location (S) with a cost of \(0\). Then, we repeat the following until the queue is empty or we have reached our destination (E):

1. Remove the location with the smallest cost so far.
   • First it will be S with \(0\) cost, then it will be a location next to S, and so on.
2. For each surrounding location, insert into the queue a direction to the current location along with the accumulated cost so far.
   • Insert neighboring locations with total cost going all the way back to S.

It is worthwhile to prove to yourself that this implementation will determine the optimal path.

The algorithm described above is called Dijkstra's algorithm. Although the algorithm will improve our average runtimes by only searching along the cheapest route so far, it is still not great, yet.

If we used Dijkstra's algorithm instead, we would see the following, where only part of the grid has been explored. In other words, all grid points that have an accumulated cost greater than the E might have been placed on the MinPQ, but they never come off.

	0	1	2	3	4
0	⇢ 2	⇣ 1	⇠ 2	⇠ 3	⇠ 8
1	⇢ 9	S	⇠ 4	⇡ 4	⇠ 5
2		⇡ 9	⇡ 8	⇡ 12	⇡ 7
3			⇡ 12		⇡ 8
4

Cost Model: Travel Cost #

One further modification that we can make on modeling the cost of traveling is to assign costs for traveling from one position to a neighboring position. As an example, imagine that each location has its own elevation. Traveling from one position to another not only incurs a cost for traveling along the xy-plane (around the grid, without regard to the elevation), but we must also account for the cost of possibly traveling "uphill" or "downhill". This modification allows us to capture the cost differences among walking along a flat surface, walking up/down a ramp, walking up/down rugged terrain, trying to vault a high ledge, etc.

In the example below, the elevation of each position is given in the diagram on the right. Note: the values are not positional costs like in the previous subsection, but instead are heights for each position.

y \ x	0	1	2	3	4		y \ x	0	1	2	3	4
0							0	2	1	2	1	5
1		S					1	3	0	4	1	0
2							2	4	5	4	8	0
3					E		3	5	7	4	4	5
4							4	1	1	0	4	1

Now, suppose that the cost of traveling from one position (\(M\)) to a neighboring position (\(N\)) is given by the equations below. Note: the total travel cost involves the xy-distance as well as a climbing distance.

\[\begin{array}{rcl} \text{climb}(M, N) & = & | \text{height}(M) - \text{height}(N) |^{ 1.5 } \\ \text{distance}(M, N) & = & \sqrt{(M_x - N_x)^2 + (M_y - N_y)^2} \\ \text{travelcost}(M, N) & = & (1 + \text{climb}(M,N)) \cdot \text{distance}(M,N) \\ \end{array}\]

The interesting thing to note about this \(\text{travelcost}\) function is that it is non-linear. This means that it will be easier to climb up a given height if done over a distance (e.g., ramp or staircase) than to climb it over a short distance (e.g., rock climbing or bouldering). Because of this, the costs of reaching a position will depend on which direction you come from if each neighboring position has a different height.

Below is a grid showing the values of traversing from one position to a neighboring based on the heights example and \(\text{travelcost}\) function above.

y \ x	0		1		2		3		4
0	2	+2.0	1	+2.0	2	+2.0	1	+9.0	5
	+2.0		+2.0		+3.8		+1.0		+12.2
1	3	+6.2	0	+9.0	4	+6.2	1	+2.0	0
	+2.0		+12.2		+1.0		+19.5		+1.0
2	4	+2.0	5	+2.0	4	+9.0	8	+23.6	0
	+2.0		+3.8		+1.0		+9.0		+12.2
3	5	+3.8	7	+6.2	4	+1.0	4	+2.0	5
	+9.0		+15.7		+9.0		+1.0		+9.0
4	1	+1.0	1	+2.0	0	+9.0	4	+6.2	1

The diagram below shows the optimal path that Dijkstra's algorithm will produce.

y \ x	0	1	2	3	4
0	⇢ 4.0	⇣ 2.0	⇠ 4.0	⇠ 6.0	⇠ 15.0
1	⇡ 6.0	0.0	⇡ 7.8	⇡ 7.0	⇠ 9.0
2	⇡ 8.0	⇠ 10.0	⇡ 8.8	⇠ 17.8	⇡ 10.0
3	⇡ 10.0	⇠ 13.8	⇡ 9.8	⇠ 10.8	⇠ 12.8
4	⇡ 19.0	⇠ 20.0	⇡ 18.8	⇡ 11.8	⇠ 18.0

A* Search: Adding Heuristic to Reduce Searching

Another observation you might have made is that the optimal route will likely take us toward our destination, not away. If we temporarily add to our accumulated cost a heuristic value that captures this notion "every step should get us closer", then the costs will be artificially inflated areas that take us away from the goal. Implementing this observation is the A* search algorithm.

The heuristic that we will use is simply the distance between the surrounding location (\(N\)) and the path's end (\(E\)) times some constant scalar (\(h\)).

The following equation defines how to compute the accumulated cost to travel from the starting point \(S\) through point \(M\) to point \(N\) (a neighbor of \(M\)) with the added A* heuristic. Specifically, find a neighbor point \(M\) of \(N\), compute the accumulated cost from \(S\) to \(M\) without the heuristic, add the cost of traveling from \(M\) to \(N\), and then add the heuristic cost of traveling from \(N\) to \(E\).

\[ \text{cost}_h(S, N) = \text{cost}_0(S, M) + \text{travelcost}(M, N) + h * \text{dist}(N, E) \]

In the equation above,

• \(\text{cost}\) is a recursive function that takes two locations as parameters, and \(\text{cost}(X, X) = 0\) for some location \(X\).
  • The subscript (\(h\)) on the \(\text{cost}_h\) function indicates how strong the heuristic should be.
  • When \(h=0\), there is no heuristic, and we simply have Dijkstra's Algorithm.
  • When \(h\) is too big, the heuristic term dominates, and the A* Search Algorithm basically ignores the travel cost.
  • The goal is to find a "Goldilocks" \(h\) that's not too big and not too small.
  • For more information, see Amit Patel's A* Pages for more information.
• \(\text{travelcost}\) is a function that takes two neighboring locations and computes a travel difficulty of moving from the first location to the next, where \(\text{travelcost}(X, X) = 0\).
• \(\text{dist}\) computes the Euclidean distance between the two passed locations.

Extra Credits

---

There are a couple of ways to receive extra credit on this project.

Cardinal vs. Ordinal Directions

You can get full credit if you correctly implement path finding by looking at only the four neighbors along the cardinal directions (North, South, West, East or Up, Down, Left, Right). The details of this write-up is presented using only the cardinal directions.

You can get extra credit if you correctly implement path finding by looking at the eight ordinal directions (Noth, East, South, West, Northeast, Southeast, Southwest, Northwest).

Finding Better Routes

Recall that each location can be reached from any of its four neighbors. Careful analysis of how the travel cost is computed and accumulated shows that simply considering the very first time we reach a location could actually result in a suboptimal path, even when the heuristic is turned off. The reason for this incorrectness is the travel cost is non-linear. In order to compute the optimal path, we need to take extreme care when reaching a location by two different paths. Specifically, we might need to invalidate the previous found paths if we manage to find a shorter path to the same location.

Let's look at an example...

In iteration 42, suppose that node [← 100] is at location a and node [105 →] is at location c, and both are currently on the priority queue. The 100 and 105 indicates the costs back to the start. Presently, there are no nodes at b, but we can reach position b from either a or c. Now, suppose that traveling from a←b costs 10 and traveling from b→c costs 2.

iter		a	b	c		Current MinPQ
42	...	[← 100]	?	[105 →]	...	[a:← 100], [c:105 →]
43	...	[← 100]	?	[105 →]	...	[c:105 →]
	...	[← 100]	[← 110]	[105 →]	...	[c:105 →], [b:110 ←]
44	...	[← 100]	[← 110]	[105 →]	...	[b:110 ←]
	...	[← 100]	[← 110]	[105 →]	...	[b:110 ←]
	...	[← 100]	[107 →]	[105 →]	...	[b:107 →], [b:110 ←]
45	...	[← 100]	[107 →]	[105 →]	...	[b:110 ←]
46	...	[← 100]	[107 →]	[105 →]	...

key:

• gray unprocessed position
• blue node is on priority queue
• green indicates current node being processed
• red node is invalidated
• white node has been fully processed

In iteration 43, the [← 100] node at a comes off the priority queue, because it has the min cost (100 vs 105). Its neighbor at position b is added to the priority queue as node [← 110].

In iteration 44, the [105 →] node at c comes off the priority queue, because it has the next min cost (105 vs 110). Its neighbor at position b is already visited (b's node is still on priority queue), so we could ignore adding c's neighbor b to the priority queue (to avoid revisiting positions), but this would lead to a suboptimal path! Specifically, the path from b to start going through c would cost \(105+2=107\) where the current path from b to start through a costs \(100+10=110\).

The correct way to handle this:

• invalidate the current [← 110] node at b (note: this node is STILL on the priority queue, so it will eventually come off!),
• create a new [107 →] node at b which is inserted on the priority queue, and
• ignore any invalidated nodes (ex: [← 110]) when they come off the priority queue.

Solving this problem is fairly straightforward, but it does require careful coding to not retrace paths already taken. Therefore, implementing an optimal solution will result in extra credit.

The reason we need to "invalidate" nodes is because the MinPQ API does not provide a way to delete an arbitrary item. By marking a node invalid, we can keep the node in the priority queue, but ignore it when it finally comes off.

The API

---

This framework includes several classes that provide lots of functionality to support the project. Some classes rely on other classes. You will need to provide implementations for only two of the classes: Pathfinder and Walker. The following subsections describe each class in more detail.

The Pathfinder Class

---

To model a pathfinding problem, modify the data type Pathfinding and the internal private data type PFNode (pathfinding node) to implement following API:

The Pathfinder constructor takes a Terrain object as an argument.

The setPathStart() and setPathEnd() methods will set the starting and ending locations, and the setHeuristic() method will set the search heuristic. The getPathStart(), getPathEnd(), and getHeuristic() methods are the corresponding getters.

Once the main properties of the Pathfinder object have been set, the computePath() method will perform Dijkstra / A* search to find a path from the starting locations to the ending location that has (approximately) the least cost.

foundPath() returns true if a path was found. getPathCost() returns the total (non-heuristic) cost of traveling along the path. The getPathSolution() method returns an Iterable<Coord> that iterates along the path from the starting position to the ending position. This will be used to draw the path in PathfinderVisualizer and for the Walker (see next section). Note: each Coord along the solution must be adjacent to the previous and next Coord on the path. If no path is found, getPathCost() should return Float.POSITIVE_INFINITY and getPathSolution() should return either null or an empty Iterable<Coord>.

getSearchSize() and wasSearched() are two methods that are useful for debugging. getSearchSize() returns the number of locations that were looked at (placed on priority queue) while finding the path. wasSearched() returns true if the specified Coord was looked at (placed on priority queue) while finding the path. The visualizer will tint purple all Coords where wasSearched() returns true. Note: The exact values of getSearchSize and wasSearched are tricky to determine, but they should still return reasonable values based on the map and heuristic.

The resetPath() method will clear out any path information.

The PFNode class is a private, inner class for PathFinder. I have provided a very basic API to get you started, but you are completely free to change this class however you see fit. Because it is private, the automated tester cannot test it directly.

Similar Problem/Fewer Variables: The simplest method of solving this problem is to ignore the travel costs during computePath() and simply find a path. In fact, this can be computed in time linear to \(N\) (not \(N^2\)).

Edge Cases: Throw an IllegalArgumentException if the Coord passed to setPathStart() or setPathEnd() is null. Throw an IndexOutOfBoundsException if the Coord is outside the acceptable range (hint: use isInBounds() method of Coord). Throw an IllegalArgumentException if computePath() is called before the start or end locations have been set.

Performance Requirements: Your implementation of computePath() must use space that is linear to the final search space, and it should run no worse than \(\sim a\ N^2 \lg N\) time, where \(a\) is about 15% (depending on map and heuristic). Also, all methods but computePath() and resetPath() should run in constant time.

The Walker Class  #

---

To model an individual following the path along a terrain, modify the Walker data type to implement the following API:

The constructor takes as parameters the Terrain the walker is to traverse and the path (as Iterable<Coord>). The getLocation() returns the walker's current location, which starts at the first Coord in path. doneWalking returns true if the walker has reached the end of the path.

The advance() will "walk" the walker along the path for a given amount of time (byTime), which will always be a non-negative value. This should take into account the cost of following the given path along the Terrain. In other words, if the path is along level ground, the walker should traverse it rather quickly, but if it is uphill/downhill, then the walker will go much slower. Use the computerTravelCost() method of the Terrain to determine how much time it takes to travel from the walker's current position to the next position on the path.

Scoring:

• You will receive 1pt if your walker returns the next Coord each time getLocation() is called. (ignore advance())
• You will receive up to 2pts if your walker advances to the next Coord each time advance() is called with a positive byTime. (ignore byTime)
• You will receieve up to 3pts if your walker takes non-negative byTime into account correctly.
• You will lose points if your walker unnecessarily misses a Coord along the path (i.e., if a Coord is skipped but should not have been skipped).
• All functions should return in (approximately) constant time, otherwise you will lose points.

Example

Here is an example that might help you see how advance should work.

Suppose you are given the path below, where A is the first Coord, D is the last Coord, the travel cost from A⇒B is \(1.2\), from B⇒C is \(1.5\), and from C⇒D is \(0.5\).

The walker starts at Coord A, so getLocation() will return A and doneWalking() returns false.

Now, let's say that advance(1.0) is called. This means that the walker starts walking away from A toward B, however now enough time has elapsed for the walker to reach B; still \(1.5 - 1.0 = 0.5\) away! So, getLocation() will continue to return A.

Let's say that advance(1.0) is called again, so it total the walker has walked for \(2.0\). That \(2.0\) is long enough to make it to B and then head on toward C by \(2.0 - 1.2 = 0.8\). There is still \(0.7\) time left for the walker to reach C. So, getLocation() will return B.

Let's supposed that advance(1.0) is called a third time. That means the walker has traveled \(0.8 + 1.0 = 1.8\) past B, which puts the walker past C by \(1.8 - 1.5 = 0.3\), but still \(0.5 - 0.3 = 0.2\) away from D.

If advance(1.0) is called a fourth time, now the walker has traveled the rest of the distance from C⇒D (\(0.5\)). In fact the walker is now \((0.3 + 1.0) - 0.5 = 1.3 - 0.5 = 0.8\) past D, but that extra bit does not matter as the walker has reached the end. From this point on, getLocation() should return D and doneWalking() should return true.

         0.0         1.2            2.7   3.2   <- accumulated
          |   1.2     |      1.5     | 0.5 |    <- travel costs
          A --------> B -----------> C --> D
          ^         ^         ^         ^  ^
          |         |         |         |  \------\
         0.0       1.0       2.0       3.0       4.0
          ^         ^         ^         ^         ^
start    -/         |         |         |         |
adv(1.0) -----------/         |         |         |
adv(1.0) ---------------------/         |         |
adv(1.0) -------------------------------/         |
adv(1.0) -----------------------------------------/

The Terrain Class

---

We have provided a class to load and store maps or heightmaps. The key functions to this class, though, are computeDistance() and computeTravelCost() functions, as they will help you perform the A* search. The computeDistance() returns the "as the crow flies" distance between the two input coordinates. The computeTravelCost() returns the cost of traveling (a combination of distance and height difference) from the first input coordinate to the second.

Other Classes

---

The Coord class is a convenient way to pass 2D coordinate (longitude+latitude, i+j, etc.). The i coordinate represents the longitude or x value (i increases going right). The j coordinate reprenents the latitude or y value (j increases going down). Note that the class is immutable, so you can assign to it only at construction The class does contain a useful function called isInBounds() that will return a boolean to indicate whether the Coord is within the specified minimum and maximum values (inclusive).

The PathfinderVisualizer is a straightforward class that renders the data stored in Terrain and Pathfinder objects.

The InteractivePathfinderVisualizer provides some simple interaction to the PathfinderVisualizer. See the comments at the top of .java file for details.

Finally, the TerrainEditor class contains a handful of useful functions to edit a Terrain object. The InteractivePathfinderVisualizer uses these functions to smooth, increase, or decrease the heightmap or to generate a new fractal terrain.

Keyboard Shortcuts

---

Listed below are the many useful keyboard shortcuts for the InteractivePathFinderVisualizer.

Key	Action		Key	Action
S	set start location		E	set end location
C	clear / reset path		Space	recompute path
0	\(h \leftarrow 0\)		1	\(h \leftarrow 1\)
LeftArrow	\(h \leftarrow h / 2\)		RightArrow	\(h \leftarrow h * 2\)
W	create walker		R	generate render random terrain
Shift+M	smooth all terrain		M	smooth terrain near mouse cursor
UpArrow	increase height of terrain near mouse		DownArrow	decrease height of terrain near mouse

Possible Results

---

The table below shows the path costs that our code produces using only cardinal directions and without invalidating paths. NOTE: Since this project involves some tricky bookkeeping, your code does not need to match our code exactly, but it should be reasonably close.

More specifically, we are less concerned about the exact numbers your getSearchSize() returns, but we will be interested in seeing that number get smaller as the heuristic increases.

Map	Heuristic	Cost	Searched
map32_0	0.0	252.0	447 (43%)
	1024.0	252.0	335 (32%)
map32_1	0.0	56.0	447 (43%)
	2.0	56.0	81 (7%)
map232	0.0	4524.0	10094 (18%)
	1024.0	4524.0	5706 (10%)
usa128	0.0	1.746e7	9093 (55%)
	1.0	1.747e7	7103 (43%)

There are many other elevation map files under data_ref/ folder. See the readme.md file in the folder for more information.

Requirements and Submission

---

You will need to implement and analyze the Pathfinder and Walker classes across several maps.

Readme

---

Do all of the problems above in the appropriate Java file, and then write about your findings in the readme.md. Show your work and be thoughtful. Your job is to convince me that you have done the work and that you have either learned something new or verified an already understood concept.

Include screenshots of the project running!

Files

---

The diagram below indicate which files you can edit, which files/folder you should not edit, and the rest are files/folders that might be changed by IntelliJ or git but you should not change directly.

P04_Pathfinding/...
 ├─ P04_Pathfinding.iml
 ├─ .idea/...
 ├─ .git/...                    <- **DO NOT EDIT**
 ├─ .gitignore                  <- **DO NOT EDIT**
 ├─ .gitmodules                 <- **DO NOT EDIT**
 ├─ out/...
 ├─ libs/...
 ├─ src/...
 │   ├─ Pathfinder.java         <- Java file that you might need to modify
 │   ├─ Walker.java             <- Java file that you might need to modify
 │   │                           The following files should not need edited
 │   ├─ Coord.java
 │   ├─ PathfinderVisualizer.java
 │   ├─ InteractivePathfinderVisualizer.java
 │   ├─ Terrain.java
 │   └─ TerrainEditor.java
 ├─ data/...                    <- Additional test input files you create
 ├─ data_ref/..                 <- **DO NOT EDIT**
 └─ readme.md                   <- Fill this out before submission!

We will supply an IntelliJ project with stdlib.jar and algs4.jar libraries. These libraries contain many useful classes. On this assignment, the only library functions you may call are those in java.util, stdlib.jar, and algs4.jar. Do not import any other library! You may create your own test maps under data/ folder.

Submission

---

Once you have completed the assignment requirements, simply stage, commit, and push your changes to the CSE GitLab, and then close the issues.

Do NOT submit anything to the course Brightspace page.

Grading Rubric

---

	Implementation
3pts	Correct implementation of computePath() and getPathSolution()
3pts	Correct implementation of getPathCost() and getSearchSize()
3pts	Correct implementation of Walker class
3pts	Efficient code
	Readme
3pts	Completed readme.md
3pts	Convincing evidence that Dijkstra implementation is correct
3pts	Convincing evidence that A* implementation is correct
3pts	Convincing evidence that Walker implementation is correct
3pts	Reasonable analysis on travel cost and search size
	Extra Credit
+3pts	Extra Credit: computePath() correctly handles eight ordinal neighbors
+3pts	Extra Credit: computePath() implementation finds optimal path (invalidates nodes)