Map Generator

Assignment 1 – August 27, 2006

Due: 8.00 a.m. September 10, 2006

Language: Use C/C++ for the first part. And any programming language of your choice for the second part.

Objectives:

• Implement a program that can generate terrain maps
• Refresh your memory of C/C++ IO
• Learn some simple optimizing techniques in C
• Learn about the basics of CSS

Welcome to CS242! This will be your first assignment. Since discussion sections do not meet until September 11, this gives you about two weeks to finish this assignment. Be sure to look at the sections with the UPDATE markers.

UPDATE: As some of you have noticed on the newsgroup, they are indeed different ways for doing this. This assignment does not list everything that you need to do to accomplish the task. When we do not specify a particular way of doing things, you can always do it in whatever way you see fit. We will ask for your justifications when you present your code in class. This is different from a regular machine problem where you have to follow rigid rules to facilitate grading.

Let’s begin with the goal of this assignment. We are going to take a bunch of data like such:

Listing 1

And turning it into something like this (notice that each tile has been made to fit seamlessly with its neighbors.):

Map 1

And, eventually, once you have ironed out all the bugs (the grid above helps debugging) and replace the tables with divs, you get something like:

Map 2

We are going to do all the image display in a web browser using some CSS and HTML so that we do not need to mess around with image libraries and all that stuff. We will be using image libraries later on in the semester, just not now. If you are not familiar with HTML or CSS, don’t worry; there is a quick guide section at Part II of this assignment.

While doing this assignment, please adhere to all good coding practices that you have been exposed to: good comments, short functions, appropriate names for variables, etc.

Part I

The process of generating an image from the raw data above involves a couple of steps. And each of these steps can be pretty independent from one another.

A very simple way to convert the raw data above into an image would be just to associate each character with an image and just output it. However, if we do that, we end up with something like this:

Map 3

Notice how the edges of each tile do not match with the other tiles. That is just plain ugly. And we can definitely do better than that.

We will be using a image that contains multiple configurations of each tile. I have taken this image from the FreeCiv game. Please take a look at it. We will not be using all the image inside for this assignment. We will be making use of [g]rass, [d]esert, [i]ce, [j]ungle, [p]lains, [s]wamps, [r]oads, [w]ater, [h]otrocks, [f]orest and [m]ountains. Except for hotrock, which is just a name I made up, the rest should be pretty intuitive. All the images that we use are illustrated in the Map 1 above. Please right click and save this image to use in your project.

Take a look at the desert strip of images (it’s the third from the top). Notice how the first image from the left on this row shows a plain desert tile without any grass on the sides. The next image from the left has some grass on the north side. And the third image from the left has some grass on the west side. This is not an arbitrary order. If we count in base 2 and use 4 bits (meaning that we have number of the form 0000, 0001, 0010, 0011, etc), we notice the following pattern.

A one in the column signifies that the neighbor in that direction is different from the tile we are interested in. Please make sure that you understand the previous sentence before attempting this assignment.

Update: So, the first step would be to take the data above and determine the neighbors for each of the grid. Neighbor, in this case, refers to the tile directly above (north), below (south), to the right (east), to the left (west) and the diagonals of the tile we are interested in.

For each element on the grid, we are going to generate an 8-bit number to represent its neighbors. Here is how we order those bits:

Here is an example.

So, for the grass element in the middle, we will generate an 8-bit number of the form 11011010. Remember, a '1' means that the neighbor is the different from the element we are interested in.

So, step-by-step, here are the main things you have to do for part I

1. Read a file of the format in listing 1. The first line tells the number of rows. The second line gives the number of columns in each row. The subsequent lines contain the data that we want.
2. For each element on the grid, generate the 8-bit number that describes its neighbors. You can use a char data type in C since that is by default 8 bits.
3. The collection of 8-bit numbers should be written out to the file of format similar to listing 1. The first line tells the number of rows; the second line tells the number of columns in a row. And the subsequent lines will be the 8-bit number that corresponds to the elements of the grid from listing 1. You can write this out as a binary or text file.

And here are some things you have to watch out for.

1. Do not read off the ‘edge’. If you are the corner, don’t just go to the previous neighbor! There is none!
2. What are you going to do at the edges? Are you going to set the corresponding bit to 1 or 0? Why?
3. How are you going to handle “bad” data? For instance, what if the number of rows and columns is not the same as the numbers given in the first two lines of the file?
4. After you get it working, think of how you might be able to check faster. For instance, you can make use of symmetry. Once you have checked the neighbor to the right of the first cell, when you check the second cell, you do not need to check the previous cell to the left since you have already done that. Making use of symmetry reduces the amount of redundant checks.

If your C/C++ is a bit rusty, you can always go a quick search on your favorite search engine for some examples. CPPReference is a good site.

Part II

Update: For this part, I suggest using a scripting language. We are mostly doing string manipulation and that can be pretty tedious in C/C++. For instance, your 8-bit number from Part 1: 11011010 will be transformed to the css class “desert1011”. Remember we are only using the west, south, east and north neighbors (they correspond to bit7, bit5, bit3 and bit1). So, why do we check for all neighbors when we use only 4 of them? Because next time around, we might need to use the diagonal checks depending on our terrain image. In fact, if we had a more elaborate terrain with roads and rivers, we might need to use the diagonals to determine the orientation for the rivers.

Here is the exciting part. We will be using very little HTMl. In fact all you need to know is how to create a table.

How to create a table in HTML

    
        <html>
        <!-- this is a comment -->
            <table border="1">
                <!-- tr = table row -->
                <tr>
                    <td> <!-- td = table data. treat it as columns -->
                        here is some text
                    </td>
                    <td>
                        here is some more text
                    </td>
                </tr>
                <tr>
                    <td>
                        some more text on the next row, first column
                    </td>
                    <td>
                        some more text in the next row, second column
                    </td>
                </tr> 
            </table>
        </html>
    

Copy the html code above (that means everything in between and including the < html > ... < /html >) into a file and save it as tables.html. You can then open the file in your web browser to see the result. Basically, all you need is to create <tr> and </tr> for each row. And then insert multiple <td> </td> with the data between them. As you will see later on, when we use CSS, there is no need for any data between the tags since we are going to apply a background to the tag.

How to use CSS

First make sure that you have downloaded the terrain image. If not, you can get it here. Save it as tiles.png. Make sure you put it into the same directory as the file below.

    
        /* This is a comment */

        /* In this case, .g is how you define a class called g */ 
        .g{
            height: 30px; 
            width: 30px;
            background: url(tiles.png) ;
            background-position: 0px -30px;
            overflow: hidden;
            border-width: 0px;
        }

        .d{
            height: 30px; 
            width: 30px;
            background: url(tiles.png) ;
            background-position: 0px -60px;
            overflow: hidden;
            border-width: 0px;
        }
    

Listing 4

Save the file in listing 4 as map.css. Make sure that you put it into the same directory as the rest of the files so far.

    
        <html>
        <!-- Here we include the .css file. 
            Think of it as import in Java or #include in C -->
            <link rel=stylesheet href="map.css" type="text/css" media=screen>
            <table border="1">
                <tr>
                    <td class="g">
                    </td>
                    <td class="d">
                    </td>
                </tr>
                <tr>
                    <td class="g">
                    </td>
                    <td class="d"> 
                    </td>
                </tr> 
            </table>
        </html>
    

Listing 5

Save listing 5 as tables2.html. Try modifying the background-position attribute for the css file and see what happens. Also see what happens when you change the class attribute for each <td> tag above.

At this stage, what is left is to figure out how to name your classes and generate the css file that contains all the possible combination. An important parameter to know is that each little tile is 30 pixels by 30 pixels. That information should help you calculate how much you need to shift the image for each tile. An incomplete list might look something like this:

    
        .g_0_0_0_0{
        height: 30px;
        width: 30px;
        background: url(tiles.png);
        background-position: 0px -30px;
        overflow: hidden;
        }

        .g_0_0_0_1{
        height: 30px;
        width: 30px;
        background: url(tiles.png);
        background-position: -30px -30px;
        overflow: hidden;
        }
    

Once you are done and wish to make it look better, you can get rid of the tables, and use div. You can search on the web to see how to use div or you can come and ask any of the TAs.

In case anyone is curious, I got the idea of using css to clip the images from this site. And the original inspiration came from Dr. Nic.

Questions to think about:

• Why did we separate the task of generating the map into two parts? Why use two different programs to do what one know-it-all program can do?
• How would you handle the forest, mountain and hotrock tiles? They do not have different configurations.
• Are you generating the css file by hand? You should NOT be doing that. You can write a helper program to generate it for you.
• How would you restructure your program to handle a different tile map or different grid elements?
• Did you hard code the name of the input file in your code? Should you really be doing that? Why not make it a command-line argument.
• Generate some other maps to make sure that your program works. Try to find any border cases that will cause your map to look weird.

Grading:

• Technical:
  • Can the program display a map of images? [5]
  • Can the program do edge detection? [5]
  • Can you quickly change the raw data and run your program without recompiling to generate another map? [5]
  • Did you test it on other raw data? [3]
• Style:
  • Were comments adequate? [3]
  • Were meaningful names used for variables, constants and function? [3]
  • Was the naming convention consistent? [3]

• Participation:
  • Did you ask questions in discussion section? [5]
  • Did you turn in your assignment on time? [5]
  • Did you read your partner’s code before class? [3]