Think about maps for a minute. We see them in one form or another almost every day, but we usually do not think about them even though there are some highly sophisticated theories about maps. We simply use them. We just want to figure how to get from here to there.
On a computer, however, a map is something we have to think about. Many computer games—and other applications, too—use maps to store and represent information. In this article, we will examine some ways of putting maps into your ZX80 or ZX81. We will also see how the Sinclair computers can generate complex maps by themselves.
Starting at the Beginning
What exactly is a map? Let us define it at this point as a representation of a group of places and of the ways of getting from one place to another.
One of the most familiar types is the road map. Cities and towns marked on the map with different types of dots; the roads are shown as lines of various sizes and colors. The towns are the places on the map, and the roads connect each of them to other towns.
One of the defining characteristics of a map is that every place on the map must be connected, somehow, with every other place on the map. Maybe the connection will not be direct. On a road map, for example, the route from town A to town B might lead through several other towns along the way. But, if you literally “can’t get there from here,” the two places are not really on the same map.
Actually, most road maps contain plenty of other information besides locations of towns and roads. For example, since a road map is usually a picture of an entire region, it also shows such features as rivers and lakes.
In addition to those extra details, all the distances on a road map are usually to scale. “To scale” means that distances on the road map are proportional to the distances in the real world. Thus one inch on the map might represent ten miles in the real world. That may seem pretty obvious, but not all maps are drawn to scale. Many do not need to be.
Concentration
A map drawn to scale contains a lot of information concentrated in a relatively small space. We scan the map quickly and get the information we need fast. That is, we process the information the map contains visually.
The very complete to-scale map is not nearly so useful to a computer though. To understand why, think about what you do to figure out how far it is from New York to Los Angeles.
1) You open up the map.
2) You find New York.
3) You find Los Angeles.
4) You measure the distance between the two cities.
Now think about what a computer has to go through to do the same thing:
1) It has to scan the entire map, one small section at a time, to look for New York.
2) It must repeat the whole process to find Los Angeles.
3) Having figured out where the two cities are, it has to measure the distance between them. Generally that is the easiest part of the task.
But before any of that happens, the computer must be able to scan the map. Since this generally means the map must be stored in the memory of the computer, lots of memory is required, much more than is reasonable for something as simple as figuring out how far it is between two cities.
The simple truth is this: human beings are good at processing visual information. Computers are not. As a result, the best kind of map for a human being may be the worst sort of map for a computer.
A Computer Map
The simplest kind of computer map is the equivalent of a map actually drawn on a piece of paper. For example, enter and run the program in Listing 1. Your screen display should look something like Figure 1.
Listing 1.
8K ROM
10 LET L=INT (RND*100)
20 LET N=INT (RND*100)
30 IF N=L THEN GOTO 20
40 PRINT "............"
50 FOR A=0 TO 9
60 PRINT ".";
70 FOR B=0 TO 9
80 LET A$=" "
90 IF 10*A+B=N THEN LET A$="N"
100 IF 10*A+B=L THEN LET A$="L"
110 PRINT A$;
120 NEXT B
130 PRINT "."
140 NEXT A
150 PRINT "............"Changes for 4K ROM
10 LET L=RND(100)-1
20 LET N=RND(100)-1This is a randomly generated map of New York and Los Angeles. The “N” represents New York, and the “L” Los Angeles.
It certainly looks like a map—a sort of map, anyway. And it is relatively easy for a human brain to understand. But it is not nearly so easy for a computer to work with. Remember that, using just the map, a computer calculating the distance between the two cities would have to scan every space on the map to find each of the cities. That is not too large a problem on a tiny map of 100 spaces. But for a map representing the entire United States, featuring a significant number of cities, it would take lots of time—and lots of memory.
A human brain has a huge capacity for processing and storing information, but a computer (especially a small, personal-size computer like the Sinclair) does not have the luxury of all that spare memory. For most computerized maps, drawing out the map for the computer to work with will not be very helpful.
A More Coordinated Version
The computer has several ways of handling this information instead of actually drawing out a map. One is to assign coordinates to each important place on the map. In Listing 1, for example, lines 10 and 20 assign a random position to each of the two cities. Finding the distance between the two cities would be much easier for the computer if it could deal directly with the variables N and L.
Listing 2.
8K ROM
160 LET A=INT (N/10)-INT (L/10)
170 LET B=N-L-10*A
180 LET A=INT SQR (A*A+B*B)
190 PRINT "N=";N,"L=";L
200 PRINT "DISTANCE=";AChanges for 4K ROM
10 LET L=RND(100)-1
20 LET N=RND(100)-1
160 LET A=N/10-L/10
180 LET C=A*A+B*B
190 IF A<0 THEN LET A=-A
200 IF NOT C>A*A THEN GO TO 230
210 LET A=A+1
220 GO TO 200
230 PRINT "N=";N,"L=";L
240 PRINT "DISTANCE=";AThe program in Listing 2 lets it do exactly that. This time, there is no visual map for the human being, but the computer can give us the information we want much faster because it is working with a map is designed for it.
To get a human-readable version of the map at the same time, combine the two programs into one—none of the line numbers will conflict—and run the resulting program. In one sense, what we have done in the second program is to eliminate all the “white space” from the first map. Only the pertinent information is left.
The Real World
In most computer games, it is assumed that the whole universe is divided up into squares, and that you always move from one square to the next. This a system lends itself well to simple maps.
If you are pretending to fight monsters or shoot aliens, it may work fine, but the real world is not so convenient. Consider an airline route map, for example. You can create a computer map that shows all the territory between cities, but there is not much point in that since airplanes always fly directly from one place to another. All that “white space” just gets in the way. Remember what a map is: simply a group of interconnected places.
Suppose you want to make an airline map containing New York and Los Angeles. You might do it like this:
Places: Routes: New York (NY) NY-LA: 2800 miles Los Angeles (LA)
You might also include another route—LA-NY: 2800 miles. In this case it is safe to assume that the route goes in both directions, but that is not always true. If you were making a map of a plumbing system or a circuit board, it might be important to know which way everything was moving. For now, though, assume that there are no one-way routes.
Bigger and Better
Of course, there is no reason to limit this map to two cities. Let’s expand it as in Figure 2. This looks like a long list of interconnections, but actually it is rather straightforward. In a computer, the important information—the distances—could be represented in a single one-dimensional array which requires far less memory than an accurately scaled visual map.
Figure 2.
Places: Route: Miles
(1) New York (1) NY-LA 2800
(2) Los Angeles (2) NY-Ch 840
(3) Chicago (3) NY-Ho 1650
(4) Houston (4) NY-Bo 220
(5) Boston (5) NY-SF 3040
(6) San Francisco (6) LA-Ch 2100
(7) LA-Ho 1550
(8) LA-Bo 3050
(9) LA-SF 410
(10) Ch-Ho 1100
(11) Ch-Bo 1000
(12) Ch-SF 2410
(13) Ho-Bo 1860
(14) Ho-SF 1950
(15) Bo-SF 3170
The Traveling Salesman
Now suppose you are a salesman who has to visit six cities, beginning in one of them and ending in the same city you started from. How can you find the route that requires the least amount of traveling, that is, the route that covers the shortest distance? (This is a variation of the old “traveling salesman” problem.)
We find that there are six-factorial possible routes. (Six-factorial, or 6, means 6x5x4x3x2x1, or 720.) Some of these are virtually identical, following the same route but starting in a different city, or running the route backwards. But even after eliminating duplication, there are still 60 different possibilities to choose from. Which one is shortest?
You could figure out all the possible routes, if you had lots of paper and lots more time. However, with this map of the six cities, it is easy for the computer to figure out every route and then tell you which circuit is the most efficient.
Listing 3 is a program to try all the different routes. The 8K version requires over 1K RAM. To use the program on the 4K ROM, make the changes at the end of the listing.
The first lines of the program load the distances into the D array. Then P (the current “shortest distance” for the whole circuit) is set very high, and the A array is set up as 1, 2, 3, 4, 5, 6 to indicate a route through New York, Los Angeles, Chicago, Houston, Boston, San Francisco, and then back to New York. The rest of the main program simply generates a new route each time, while the subroutine beginning at line 1000 calculates how long each route is.
Listing 3.
8K ROM
1 REM 2800,0840,1650,0220,304
0,2100,1550,3050,0410,1100,1000,
2410,1860,1950,3170
10 DIM A(7)
20 DIM D(15)
30 FOR D=1 TO 15
40 FOR A=16509 TO 16512
50 LET D(D)=10*D(D)+PEEK (5*D+
A)-28
60 NEXT A
70 NEXT D
80 LET P=32767
90 FOR A=1 TO 6
100 LET A(A)=A
110 NEXT A
120 GOSUB 1000
130 FOR D=1 TO 4
140 LET N=6-D
150 FOR A=N TO 5
160 IF A(A+1)>A(A) THEN GOTO 20
0
170 NEXT A
180 NEXT D
190 STOP
200 LET A(N)=A(N)+1
210 FOR A=1 TO N-1
220 IF A(A)=A(N) THEN GOTO 200
230 NEXT A
240 LET N=N+1
250 IF N=7 THEN GOTO 120
260 LET A(N)=1
270 GOTO 210
1000 LET R=0
1005 LET A(7)=A(1)
1010 FOR D=1 TO 6
1020 LET Q=0
1030 FOR A=1 TO 5
1040 FOR B=A+1 TO 6
1050 LET Q=Q+1
1060 IF A(D)=A AND A(D+1)=B OR A
(D)=B AND A(D+1)=A THEN GOTO 110
0
1070 NEXT B
1080 NEXT A
1090 RETURN
1100 LET R=R+D(Q)
1110 NEXT D
1120 IF R>P THEN RETURN
1130 IF R<P THEN CLS
1140 LET P=R
1150 FOR A=1 TO 7
1160 PRINT A(A);
1170 NEXT A
1180 PRINT TAB 8;P
1190 RETURNChanges for 4K ROM
40 FOR A=16422 TO 16425
50 LET D(D)=10*D(D)+PEEK(5*D+A
)-28
1180 PRINT ,PIt should only take about three minutes for a ZX80 to come up with the shortest route.
Trees
It should be clear by now that different kinds of maps are useful for different purposes. For a human being to find the right highway, a road map works just fine. For a computer to solve the “traveling salesman” problem, we saw a better kind of map.
A third type that has a very specialized use is the “tree-structured” map. Remember what the defining characteristic of any map is: it represents a group of interconnected things. A tree-structured map has one additional characteristic: the map begins with a single place (or thing), and exactly one new connection is made for each new place (or thing) on the map.
The best way to understand this type is with an example. Let’s start out with a map like this:
New York
True this is not much of a map, but now add some more cities:
New York
/
Chicago Los Angeles
Notice that the new cities are connected to New York, but not to each other. Why not? Think about the definition of a tree-structured map. It starts out with one place—New York. Then, with each city added to the map, exactly one new connection is made. Thus there will always be more cities than connections—exactly one more, in fact.
Let’s make the map still larger as in Figure 3. Once again, there is just one new connection for each new city. One way of looking at this is to say that each new city connects to exactly one previously existing city.
Figure 3.
New York
/
Chicago Los Angeles
/ /
St.Louis Peoria Las Vegas Sacramento
Shaking the Family Tree
How useful can a map like this be? Not very, if you are looking for a road map. Most cities are a little better connected than that.
But consider for a moment a family tree. It works exactly like a tree-structured map. For example, Figure 4 shows a visual map of a family tree covering four generations. If we consider this tree structure as a map with places and routes (the places are people, and the routes are lines of parentage), it will look like this:
Figure 4.
Art
/
Beth Charles
/ | |
David Edna Fred George Henry
/ |
Irma Jack Kathleen
Places: Routes:
Art
Beth Art to Beth
Art to Charles
David Beth to David
Edna Beth to Edna
Fred Beth to Fred
George Charles to George
Henry Charles to Henry
Irma Edna to Irma
Jack Edna to Jack
Kathleen Henry to Kathleen
As you would expect in a family tree, each new person is the son or daughter of exactly one person already in the tree. That means there will be just one new connection for each new person; the number of connections is one less than the number of family members.
Counting Off
Now suppose we give everyone in our family tree a number, beginning with zero, and each family connection a number, beginning with one. Since there is one more family member than connections, we find that the member and the connection have the same number. The result looks like this:
Places: Routes: (0) Art (1) Beth (1) (0,1) (2) Charles (2) (0,2) (3) David (3) (1,3) (4) Edna (4) (1,4) (5) Fred (5) (1,5) (6) George (6) (2,6) (7) Henry (7) (2,7) (8) Irma (8) (4,8) (9) Jack (9) (4,9) (10) Kathleen (10) (7,10)
Now something else becomes obvious: the second element of each pair matches the route number. Why? Because a tree structure gets bigger by one place and one route at a time. Each new place connects, by a new route, to some previous place. Each new family member is the son or daughter of exactly one previous family member.
This map is significantly different from the one we made of the six cities. For that map, we got all the distances into one array, but to do it we used the programming trick found in lines 1030-1080. The trick was necessary to fit the program into 1K, but it is still a trick.
With a tree structure, there is no gimmick involved. We really can represent the entire map in a single one-dimensional array which is a very memory-efficient way of making a very complex and extensive map of a tree.
A-Maze-Ment
If a carefully constructed map of the tree type be stored as an array, why not stand the process on its head? We should be able to use an array full of random numbers as a maze.
We must keep a few things in mind. First, the random numbers have to be chosen within the right range. Remember, every place on a map has to connect, directly or indirectly, with every other place. Second, to keep the maze from being too easy we should scramble some of the connections and add some extra cross-connections to the basic tree structure.
A program that does all of these things and puts them together to generate a complex random maze of almost any size is given in Listing 4. The 8K ROM version requires over 1K RAM. To use on the 4K ROM, make the changes at the end of the listing.
Listing 4.
8K ROM
10 PRINT "NUMBER OF ROOMS?"
20 INPUT N
30 DIM D(2*N)
40 FOR A=1 TO N
50 IF A=1 THEN LET D(A)=0
60 IF A>1 THEN LET D(A)=INT (R
ND*(A-1))+1
70 NEXT A
80 FOR A=N+1 TO 2*N
90 LET D(A)=INT (RND*N)+1
100 IF D(A)=A-N THEN GOTO 90
110 IF RND>.5 THEN GOTO 150
120 LET L=D(A)
130 LET D(A)=D(A-N)
140 LET D(A-N)=L
150 NEXT A
160 LET Q=INT (RND*N)+1
170 CLS
180 PRINT "YOU ARE ";
190 IF Q>0 THEN GOTO 220
200 PRINT "OUTSIDE--YOU MADE IT
"
210 STOP
220 PRINT "IN ROOM ";Q;" WITH "
;
230 GOSUB 400
240 PRINT 2*N-L;" DOORS. WHICH
DOOR?"
250 INPUT L
260 GOSUB 410
270 IF L<>0 THEN GOTO 250
280 IF Q=D(A) THEN GOTO 310
290 LET Q=D(A)
300 GOTO 170
310 LET Q=A+N*(A>N)
320 GOTO 170
400 LET L=2*N
410 FOR A=1 TO 2*N
420 IF A=Q OR A=Q+N OR D(A)=Q T
HEN LET L=L-1
430 IF L<>0 THEN NEXT A
440 RETURNChanges for 4K ROM
60 IF A>1 THEN LET D(A)=RND(A-
1)
90 LET D(A)=RND(N)
110 IF RND(2)=1 THEN GO TO 150
160 LET Q=RND(N)
270 IF L THEN GO TO 250
430 IF L THEN NEXT AThe program is rather straightforward. The first FOR/NEXT loop generates a random tree structure. The second loop adds interconnections between the rooms of the maze and mixes up the doorways so it will not be as easy to find the way out. Line 160 starts the player in a random room. The subroutine beginning at line 400 or 410 is used both to count the number of doors in each room (GO SUB 400), and to find where each door leads (GO SUB 410).
It may surprise you that a maze with close to 100 rooms will fit into 1K RAM. Enter the program and try it. You will discover that finding your way through the maze is quite tricky. That is because the maze is genuinely complex: the rooms are not laid out on any kind of flat surface, but are completely random.
This type of mapped maze can be adapted for use with any game that involves a multitude of rooms or locations—caves, castles, dungeons, or haunted houses. However, it will probably require more than 1K RAM. On the other hand, this “different every time” is an interesting and challenging game in itself.
Note: Type-in program listings on this website use ZMAKEBAS notation for graphics characters.