Outcomes

Once you have completed this final workshop of the Applied CS with Android series you will have:

• Strengthened your understanding of dynamic programming
• Practiced using a range of recursive programming approaches to address a problem

Aim

Palindrome Prior Work

If you did not have a chance to complete the Palindrome app in this unit's preparation, please start the workshop by implementing that app.

Then proceed to this unit's main app: Continental Divide.

In geography, a continental divide is an imaginary line that divides land where water flows to one sea or ocean, from land that flows to a different sea or ocean.

For example, in the United States, the continental divide runs through the Rocky Mountains and divides land with water flow to the Atlantic from land with water flow to the Pacific.

In Africa, the continental divide splits the continent in three parts:

• land with water flow to the Indian Ocean
• land with water flow to the Atlantic Ocean
• land with water flow to the Mediterranean Sea

For our purposes, we will consider an imaginary square land mass surrounded by the Green Ocean to the North and West and by the Blue Ocean to the South and East. Our land will be stored as array of integers representing the height of each tile in our land.

The challenge of this app will be to color each cell to represent which ocean it flows to or to represent the fact it flows to both like this:

Timing

In total, this workshop activity should take you around 4 hours to complete. While this is longer than other workshops, it is divided into several milestones to aid you in splitting up the work.

Tour of Code

Starter Code

Just as for previous workshops, we’ve got some starter code to help you.

For this app it is composed of two classes:

• MainActivity is fully implemented with onCreate that adds a ContinentMap to the UI and handlers for each of the buttons.
• ContinentMap:
  • DEFAULT_MAP: The heights for the default map.
  • ContinentMap: Constructor that instantiates cell with the values in DEFAULT_MAP.
  • onMeasure: Boilerplate code to make ContinentMap square.
  • Cell: An inner class to store the information we need for each point in the map. The fields are:
    • height: The height of this spot
    • flowsNW: Whether this cell flows to the Green Ocean
    • flowsSE: Whether this cell flows to the Blue Ocean
    • basin: Whether this cell has been determined to flow to neither ocean
    • processing: A flag to allow us to track whether the current cell is already being evaluated (more on this below)
  • clearContinentalDivide: esets the continental divide info for each cell (except the height).
  • onDraw: Draws the current state of the Continent.
  • buildUpContinentalDivide: Labels each cell's continental divide status by starting from the coasts and working uphill. Note that this method takes a oneStep parameter which allows you to build the solution incrementally. This will be handy in debugging your own solution.
  • buildUpContinentalDivideRecursively: Unimplemented helper for the above.
  • buildDownContinentalDivide: Labels each cell's continental divide status by starting from the peaks and working downhill. Note that this method takes a oneStep parameter which allows you to build the solution incrementally. This will be handy in debugging your own solution.
  • buildDownContinentalDivideRecursively: Unimplemented helper for the above.
  • generateTerrain: Method to pseudo-randomly generate other continent maps. This is an extension for this unit's activity.

Random

Can you explain the difference between pseudo-random numbers and true random numbers?
If not, it might be worth taking a look at the Wikipedia entry for pseudorandomness.

Milestone 1: onDraw

The first milestone revolves around getting the canvas and graphical representation ready.

Start by implementing onDraw. You should break up the canvas into squares of the appropriate size (based on getWidth) and draw each square in the appropriate shade of grey.

You can pick your own color scheme but we recommend shading the cell between white for height 0 and a 50% grey (rgb(128, 128, 128)) for the highest point on the map. You'll have to figure out the math for getting the appropriate rgb value.

In addition, you should make cells that flow to the Green Ocean green and cells that flow to the Blue Ocean blue. Cells on the divide can be red (or any other combination of colors you choose as long as you can distinguish them).

Bonus points

Bonus points if you shade the red, green and blue tones depending on the height.

Finally, add a label to each square with the numerical height. This is not required but will make debugging easier. You can use paint.setTextAlign(Paint.Align.CENTER); to help center your text and canvas.drawText to draw the label.

Milestone 2: buildUpContinentalDivideRecursively

In Milestone 2 we will implement the continental divide functionality from the coasts up. This is similar to the strategy that was demonstrated in the fibonacciUp example in the preparation module. The idea is to start from each coastal spot and mark each point that is uphill from that point as flowing to whatever ocean this is on the coast of. Note that the southwest and northeast corners of the board are assumed to flow to both oceans.

Start by making sure you understand the code in buildUpContinentalDivide. Note that it calls buildUpContinentalDivideRecursively on each edge cell that has not yet been processed. This may be a good time to change the invocation of buildUpContinentalDivide to pass true for oneStep to help you debug.

Then set about implementing buildUpContinentalDivideRecursively. Some things to think about as you implement this:

• You'll need to handle going off the board should your recursion take you there.
• Don't proceed if the current cell is lower than the previous cell.
• Call buildUpContinentalDivideRecursively recursively in all four directions (we'll consider water to flow horizontally and vertically only, not diagonally).
• Use cell.processing to avoid getting into an infinite recursive loop.
• For the time being, it's ok to assume that no neighboring cells have equal height.

Although the logic is tricky, this can be implemented in about 15 lines of code so if you find yourself writing much more code than that, take a step back and re-think your strategy.

Iterate on your code until you get the result in the above screenshot. Then try changing around the values in the DEFAULT_MAP.

Stop and Check

You want to make sure that your code correctly handles basins. Basins are areas that flow to neither side of the map. They could be a lake or a dry lake. You can create one by changing DEFAULT_MAP to have a zero in the middle:

private Integer[] DEFAULT_MAP = {
1, 2, 3, 4, 5,
2, 3, 4, 5, 6,
3, 4, 0, 3, 1,
6, 7, 3, 4, 5,
5, 1, 2, 3, 4,
};

But you should also test larger basins and other map configurations, as well as larger maps.

Milestone 3: buildDownContinentalDivideRecursively

In the final milestone, you can now try solving this problem using dynamic programming by implementing buildDownContinentalDivideRecursively. Again, start by taking a look at buildDownContinentalDivide: it calls buildDownContinentalDivideRecursively on the highest unprocessed cell in the map (which is the highest on the first iteration) until all cells have been processed. Depending on the map, this means that buildDownContinentalDivideRecursively may be called once or several times.

Now implement buildDownContinentalDivideRecursively to recursively process each cell lower than the current cell then determine which way the current cell flows by examining the flow of its neighbors. Some things to think about as you implement this:

• You'll need to handle going off the board should your recursion take you there. You can create a dummy cell that is returned in this case.
• Don't proceed if the current cell is higher than the previous cell (this is the reverse from above).
• Call buildDownContinentalDivideRecursively recursively in all four directions and determine whether the current cell flows NE or SW or both based on the values of those neighbors.
• Again, use cell.processing to avoid getting into an infinite recursive loop.
• It's still ok to assume that no neighboring cells have equal height.

Stop and Check

Once more, use various maps with and without basins to check your code. You can also check your results against the results of building up your solution since they should both result in the same coloring of the map.

Extensions

The continental divide problem allows for some interesting potential extensions.

Handle neighboring cells with equal heights

Changing buildUpContinentalDivideRecursively may be as simple as changing a < to a <= but is significantly trickier for buildDownContinentalDivideRecursively. Try the following input for example:

private Integer[] DEFAULT_MAP = {
        50, 50, 50, 50, 60,
        50, 22, 26, 70, 50,
        50, 24, 30, 30, 29,
        50, 28, 28, 29, 22,
        60, 50, 50, 50, 50,
};

The '30' in the middle of the board should flow southeast. Because it is surrounded by a basin on three side, the recursion that processes that cell will have been called by its '30' neighbor. But because we avoid infinite recursion, the fact that the second '30' flows southeast will not be considered as we try to evaluate the middle cell. Part of this challenge is to figure out how to ensure that you support this case.

Random terrain

Writing height maps by hand is no fun, how about getting the computer to do it for us. Like this:

Assigning random values to each cell leads to a very artificial looking terrain so let's try doing a bit better. One popular algorithm for generating pseudo-random terrain is called the diamond-square algorithm.

It consists of assigning each cell a height that is a random variation from the average of its neighbors. But instead of processing each cell in numerical order, it processes them in ever smaller squares considering the neighbors in a square pattern and a diamond (really a square that's rotated 45 degrees) pattern. Read the wikipedia description above then step through the visualization in this great tutorial before implementing it yourself. Note that because the random variations are both positive and negative, you might end with some negative height terrain when you are done with this algorithm. So it might be a good idea to shift up the whole terrain in the end by the absolute value of the lowest negative height.

Once you have it working, make sure that you are able to compute the continental divide over your random terrain (results may vary given the randomness):

Note that as you vary the size of the detail parameter to getTerrain, you may end up with neighboring cells of equal height so you may need to also implement the previous extension.

3D view

While shading the cells of the map is a nice visualization, it would be great to be able to see our continent in 3D.

Try rewriting onDraw to create such a visualization. There are several different projections that you might use for this. One popular one is called an 'isometric' projection and you can see an example of how it is implemented in JavaScript here.

You are welcome to use other projections if you prefer.

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.