gawkinet: MAZE
1
1 3.7 MAZE: Walking Through a Maze In Virtual Reality
1 ===================================================
1
1 In the long run, every program becomes rococo, and then rubble.
1 Alan Perlis
1
1 By now, we know how to present arbitrary 'Content-type's to a
1 browser. In this node, our server will present a 3D world to our
1 browser. The 3D world is described in a scene description language
1 (VRML, Virtual Reality Modeling Language) that allows us to travel
1 through a perspective view of a 2D maze with our browser. Browsers with
1 a VRML plugin enable exploration of this technology. We could do one of
1 those boring 'Hello world' examples here, that are usually presented
1 when introducing novices to VRML. If you have never written any VRML
1 code, have a look at the VRML FAQ. Presenting a static VRML scene is a
1 bit trivial; in order to expose 'gawk''s new capabilities, we will
1 present a dynamically generated VRML scene. The function
1 'SetUpServer()' is very simple because it only sets the default HTML
1 page and initializes the random number generator. As usual, the
1 surrounding server lets you browse the maze.
1
1 function SetUpServer() {
1 TopHeader = "<HTML><title>Walk through a maze</title>"
1 TopDoc = "\
1 <h2>Please choose one of the following actions:</h2>\
1 <UL>\
1 <LI><A HREF=" MyPrefix "/AboutServer>About this server</A>\
1 <LI><A HREF=" MyPrefix "/VRMLtest>Watch a simple VRML scene</A>\
1 </UL>"
1 TopFooter = "</HTML>"
1 srand()
1 }
1
1 The function 'HandleGET()' is a bit longer because it first computes
1 the maze and afterwards generates the VRML code that is sent across the
1 network. As shown in the STATIST example (⇒STATIST), we set the
1 type of the content to VRML and then store the VRML representation of
1 the maze as the page content. We assume that the maze is stored in a 2D
1 array. Initially, the maze consists of walls only. Then, we add an
1 entry and an exit to the maze and let the rest of the work be done by
1 the function 'MakeMaze()'. Now, only the wall fields are left in the
1 maze. By iterating over the these fields, we generate one line of VRML
1 code for each wall field.
1
1 function HandleGET() {
1 if (MENU[2] == "AboutServer") {
1 Document = "If your browser has a VRML 2 plugin,\
1 this server shows you a simple VRML scene."
1 } else if (MENU[2] == "VRMLtest") {
1 XSIZE = YSIZE = 11 # initially, everything is wall
1 for (y = 0; y < YSIZE; y++)
1 for (x = 0; x < XSIZE; x++)
1 Maze[x, y] = "#"
1 delete Maze[0, 1] # entry is not wall
1 delete Maze[XSIZE-1, YSIZE-2] # exit is not wall
1 MakeMaze(1, 1)
1 Document = "\
1 #VRML V2.0 utf8\n\
1 Group {\n\
1 children [\n\
1 PointLight {\n\
1 ambientIntensity 0.2\n\
1 color 0.7 0.7 0.7\n\
1 location 0.0 8.0 10.0\n\
1 }\n\
1 DEF B1 Background {\n\
1 skyColor [0 0 0, 1.0 1.0 1.0 ]\n\
1 skyAngle 1.6\n\
1 groundColor [1 1 1, 0.8 0.8 0.8, 0.2 0.2 0.2 ]\n\
1 groundAngle [ 1.2 1.57 ]\n\
1 }\n\
1 DEF Wall Shape {\n\
1 geometry Box {size 1 1 1}\n\
1 appearance Appearance { material Material { diffuseColor 0 0 1 } }\n\
1 }\n\
1 DEF Entry Viewpoint {\n\
1 position 0.5 1.0 5.0\n\
1 orientation 0.0 0.0 -1.0 0.52\n\
1 }\n"
1 for (i in Maze) {
1 split(i, t, SUBSEP)
1 Document = Document " Transform { translation "
1 Document = Document t[1] " 0 -" t[2] " children USE Wall }\n"
1 }
1 Document = Document " ] # end of group for world\n}"
1 Reason = "OK" ORS "Content-type: model/vrml"
1 Header = Footer = ""
1 }
1 }
1
1 Finally, we have a look at 'MakeMaze()', the function that generates
1 the 'Maze' array. When entered, this function assumes that the array
1 has been initialized so that each element represents a wall element and
1 the maze is initially full of wall elements. Only the entrance and the
1 exit of the maze should have been left free. The parameters of the
1 function tell us which element must be marked as not being a wall.
1 After this, we take a look at the four neighboring elements and remember
1 which we have already treated. Of all the neighboring elements, we take
1 one at random and walk in that direction. Therefore, the wall element
1 in that direction has to be removed and then, we call the function
1 recursively for that element. The maze is only completed if we iterate
1 the above procedure for _all_ neighboring elements (in random order) and
1 for our present element by recursively calling the function for the
1 present element. This last iteration could have been done in a loop,
1 but it is done much simpler recursively.
1
1 Notice that elements with coordinates that are both odd are assumed
1 to be on our way through the maze and the generating process cannot
1 terminate as long as there is such an element not being 'delete'd. All
1 other elements are potentially part of the wall.
1
1 function MakeMaze(x, y) {
1 delete Maze[x, y] # here we are, we have no wall here
1 p = 0 # count unvisited fields in all directions
1 if (x-2 SUBSEP y in Maze) d[p++] = "-x"
1 if (x SUBSEP y-2 in Maze) d[p++] = "-y"
1 if (x+2 SUBSEP y in Maze) d[p++] = "+x"
1 if (x SUBSEP y+2 in Maze) d[p++] = "+y"
1 if (p>0) { # if there are unvisited fields, go there
1 p = int(p*rand()) # choose one unvisited field at random
1 if (d[p] == "-x") { delete Maze[x - 1, y]; MakeMaze(x - 2, y)
1 } else if (d[p] == "-y") { delete Maze[x, y - 1]; MakeMaze(x, y - 2)
1 } else if (d[p] == "+x") { delete Maze[x + 1, y]; MakeMaze(x + 2, y)
1 } else if (d[p] == "+y") { delete Maze[x, y + 1]; MakeMaze(x, y + 2)
1 } # we are back from recursion
1 MakeMaze(x, y); # try again while there are unvisited fields
1 }
1 }
1