Hi all!

As yesterday told, got prepared another post, using infrastructure explained in my prior one. Will use Java server to generate a maze using depth-first search algorithm & use Javascript to paint it into browser. As my coding way, I do it compressing all info to just one byte, using bit masks to store all info needed, and using prefabricated SIN & COS functions to redirectioning to next cells.

Ok. Let’s go then. Little theoretical explanation : Depth-search algorithm it’s an algorithm that allow, in an abstract way, to fill any area with obstacles. That can be interpreted as it can be used to visit just one time any point of a given area, or to generate that area with special conditions as well, but going through just allowed path, not visiting excepted or not-allowed ones. It is used, for example, for the popular ‘flood’ option in paint programs, or to check out all possibles ways from a map, or as used here, to generate a map about.

The main working, in our case, of the algorithm is :

• Coming up from a concrete position, check out if neighbours positions had been visited.
• Go to one of that positions, in a random or a defined way, and do whatever you want. Then repeat first step on this cell to visit next cells.
• If from a particular cell all neighbour ones had been visited, then go to prior position and repeat process to check out if still neighbours there had yet not being visite
• And so on until all cells had been visited…note that last cell will be the same as first one, as all work as a fill-tree-algorithm.

So, this way, you can define obstacles as ‘visited positions’, and you got sure that all other ‘free’ positions will be visited/worked by the algorithm just one time. Of course it can be did in a form as for each position, running them in a systematic one-each-one check out, but with depth-search algorithm it’s as the natural behavior, that’s it, walking by the allowed path, just working in allowed points, but never working or checking not allowed cells. So, as a man running in a maze, that when does not got more options to go, goes to prior position and check from there new positions.

We can extend this algorithm to use as a maze generator: will check out all positions and mark there’s a corridor yes and only yes if the checked next position (inside margins) was not visited.

Ok, let’s code. This as you can see can be achieved in a recursive way easily: just a function that given an x,y, check out randomly if x-1,y; x, y-1; x+1,y; x,y+1 adjacent cells were visited, and if case not, mark that there’s a corridor, and repeat same process in next cell, until all neighbours cells were marked as visited. In that case, return to prior cell as job was done in actual one.

As told, we are going to use bitmasking. Bitmasking is an underestimated way to use flag information with just one byte. Remember that a byte are 8-bit, so 8 boolean variables in fact, so, you can store in a byte 256 combinations of 8 true or false flags . This is really a lot of info stored. In computer science really there’s a lot of info that can be resumed & represented with just one byte, but the most of the time we prefer to use more complex objects to do this tasks. A pity, so bit processing is the most fast & less CPU consuming task that can do a machine. Technically, you just set positions with the OR operator in desired position, and retrieve it with the AND operator at desired position as well, that is easy and with no real CPU cost.

As repeated in previous posts, to use bitmasking and all possibilities of byte was a normal way in the 80’s, 90’s programming, to maximize memory & CPU speed performance. Again, a pity the mosts of the coders don’t use this tricks anymore.

So, in our case, we will define that first bit active in a cell will mean right corridor open, second one will mean up corridor, 3rd one will mean left corridor, and 4th bit will mean down corridor. Order it’s not random. If you note it, it’s the same as works mathematics COS & SIN functions, as defined angles. We will use this feature to first know the oposite one (just adding 2 & module with 4) or to find increment about current position (with special SIN & COS functions). That will simplify code a lot, resuming in a line the calculus of the next cell to visit, and to know the previous one. Note that precalculated & ajusted COS & SIN tables where a normal way to allow rotation in firsts ages of coding, as well bitmasking in general.

Then, let’s create a class called Maze. It will contain maze’s width & height, and a byte array with the map itself, remembering that each byte will represent a cell, and first 4 bits of each byte will indicate to which direction is open that cell. There’s no need to make a double index array so get&set can calculate exact offset with no problem. Note that this way we’re replicating info (x cell indicating right side is opened, and x+1 cell indicating that left side is opened) but we can afford it with no problem. Of course it can be optimized more, but there’s enough for this example at least. We will add the setters & getters specifically to make easier or job.

To that class, we add a Dig method that will begin to dig at a random position. We will dig on a position, checking out neighbours cells, in a random way, finding relative position with our fixed SIN&COS functions, and using bitmask to mark where are corridors in that cell. Of course we will need then a method to check out if a cell was visited or inside margins (ToDig) and as well a method to make the bitmasking easier to understand (Open), and a class with the main mask definitions & the SIN&COS functions/arrays.

We got then this:

 package com.dvtrsc.games.mazeescape;
 
 import java.util.Random;
 
 import com.dvtrsc.general.utility.K;
 import com.dvtrsc.general.utility.Utility;
 
 public class Maze 
 {
     int width,height;
     byte[] map;
     Random rnd = new Random();
     long tickns;
 
     public Maze()    {}
     public byte[] getMap()     {      return map;     }
     public long getTickns()    {      return tickns;  }

     public Maze(int w, int h)
     {
         this.width = w;
         this.height = h;
 
         map = new byte[w*h];
 
         Dig();
     }    

     public byte getCell(int x, int y)    { return map[x + y*width];  }
     public void setCell(int x, int y, byte b)  {  map[x + y*width] = b;}

     public int getWidth()     {  return width;   }
     public int getHeight()    {  return height;  }
 
     @Override
     public String toString()
     {
         int i;
         String s = "";
 
         for (i=0;i<map.length;i++)
             s+=map[i] + ",";
 
         return s.substring(0,s.length()-1);        
     }        
 
     private boolean ToDig(int x, int y)
     {
         return (x >= 0 && x < width && y >= 0 && y < height && getCell(x,y) == 0);
     }
 
     private void Open(int x, int y, byte direction)
     {
         setCell(x,y, (byte)(getCell(x,y) | 1 << direction));
     }
 
     private void DigHere(int x, int y)
     {        
         byte[] A = new byte[]{0,1,2,3};         
         Utility.Shuffle(A, rnd);
 
         byte i;
         int xf,yf;
 
         for (i=0;i<A.length;i++)
         {
             xf = x + K.COS[A[i]]; 
             yf = y + K.SIN[A[i]];
 
             if (ToDig(xf,yf)) 
             {
                 Open(x, y, A[i]);
                 Open(xf,yf,(byte)((A[i]+2)%4));
                 DigHere(xf,yf);
             }
         }
     }
 
     private void Dig()
     {
         tickns = System.nanoTime();
         DigHere(rnd.nextInt(width),rnd.nextInt(height));    
         tickns = System.nanoTime()- tickns;
     }
 
     public String toBinString()
     {
         int x,y;
         String s = "";
 
         for (y=0;y<height;y++)
         {
             for (x=0;x<width;x++)
                 s += Integer.toBinaryString(0x20 + getCell(x,y)).substring(2) + "\t";
 
             s += "\n";
         }
 
         return s.substring(0,s.length()-1);
     }
 
     public String toMapString()
     {
         return null;
     }
 }

K class used is as easier as :

package com.dvtrsc.general.utility;

public class K {
    
    public static byte RIGHT = 0;
    public static byte UP = 1;
    public static byte LEFT = 2;
    public static byte DOWN = 3;
    
    public static byte[] SIN = {0,-1,0,+1};
    public static byte[] COS = {+1,0,-1,0};
}

And we got the core right now! We got a mapped x,y byte array on which we can generate a maze with depth-search recursive algorithm.

Showing result as binary, you can check out that generates a correct result. Remember first bit of each cell means right corridor open, 2nd up corridor, 3rd left corridor, 4th down corridor :

As told by architecture, our server will generate it & deliver it in a REST/JSON form; client JS must then understand the received response, and paint it accordly. Preparing then our class inside a maven web app, and adding a REST/JSON service in it. We are not going to enter how can a Netbeans webapp generate REST/JSON (there’s full templates in same Netbeans & milliards of example through internet, no sense to repeat them here), neither details. Just say that this function as controller, using Jackson JSON jar, is enough to make deployed WAR file to serve REST/JSON results more than correctly.

NOTE: As updated on 2017/12/29, now API REST/JSON is rendered using SpringBoot. Please see github to see updated code or springboot: REST api example

NOTE2:

 @GET
 @Produces("application/json")
 public String getNew(@QueryParam("w") int w, @QueryParam("h") int h) {        
     try
     {
         return new ObjectMapper().writeValueAsString (new Maze(w,h));
     }
     catch(Exception E)
     {
         return null;
     }
 }

We can check out, after deploying it to our VPS Glassfish, if REST/JSON is working :

Ok then! Let’s realize a JS script that makes the call to that WS, and interprets it to a canvas object, and we got it all!

 <html>
 <head>
 <title>Maze generator</title>
 <style>
 </style>
 <script type="application/javascript">
     // Lets draw map!
     function DrawMap(p)
 {
     var w = p['width'];
     var h = p['height'];
     var m = p['map'];                            
     var c = atob(p['map']);
     var o = 0;
     var d;
 
     var s = 3;
 
     var canvas = document.getElementById("_canvas");
     canvas.width = w << s // just faster, multipliying by 2**s
         canvas.height = h << s; //
     var ctx = canvas.getContext("2d");
     ctx.strokeStyle = "#00aaff";
 
     var lx,rx,ty,by;
     for (var x=0;x<w;x++)
         for (var y=0;y<h;y++)
         {
             lx = x<<s;
             rx = (x+1)<<s;
             ty = y<<s;
             by = (y+1)<<s;
 
             d = ~c.charCodeAt(x + y*w); // making NOT. Easier and faster (not to compare to exact number each time, just true/false)
 
             // Let's masking to bits 1,2,3,4, and depending on result, paint a wall or not.
             if (d & 1) { ctx.moveTo(rx, ty); ctx.lineTo(rx, by);  }
             if (d & 2) { ctx.moveTo(lx, ty); ctx.lineTo(rx, ty);  }                 
             if (d & 4) { ctx.moveTo(lx, ty); ctx.lineTo(lx, by);  }          
             if (d & 8) { ctx.moveTo(lx, by); ctx.lineTo(rx, by);  }                             
         }
 
     ctx.stroke(); // paint canvas...
 
     document.getElementById("destination").innerHTML = w + ' ' + h + ' ' + m;                          
 }
     function getmaze() 
     // calling service to retrieve a maze. Remember each byte it's a cell, and of each byte
     // 1st byte means right corridor open
     // 2nd byte means up corridor open
     // 3rd one means left corridor open 
     // 4th one menas down corridor open
 {
     var w = document.getElementById("width").value;
     var h = document.getElementById("height").value;
 
     console.log(w + " " + h);
 
     // doing the call to service...
     var uri = "http://vps264757.ovh.net/GameFactoryService/resources/maze?w=" +w + "&h=" + h;
     var r = new XMLHttpRequest();              
     r.onreadystatechange = 
         function() {
         if (r.readyState == 4)
         if (r.status == 200) 
             DrawMap(JSON.parse(r.response));                        
         else // ooops...
             window.alert("Call failed!");
     }
         r.open("GET",uri,true);
     r.send(null);
 }
 
     </script>
     </head>
     <body bgcolor="">
     <input id="width" type="number" value="10" title="width"></input><br>
     <input id="height" type="number" value="10"></input><br><br>      
     <button type="button" onclick="getmaze()">Get Maze!</button><br><br>
     <a id="destination" title="response">nothing loaded yet...</a><br><br>
     <canvas id="_canvas"  style="border:1px solid #d3d3d3;" width="0" height="0"></canvas><br><br>
     </body>
     </html>

And this will be the result!

Note that this is an example of how works all our considered infrastructure. Anyway this is probably one of the fastest way to generate a puzzle from a server, and painting it into a browser. Note as well that still got 4 bits for info in our cells, so we can extend them for upper & down corridors to make 3D mazes, inclusive traps info, etc. Still there’s holes to fill in. As another terrain generators realized, will try in a future to paint them as 3D, to make more impressive and more actual. About infrastructure, we can then use this system to make more complex objectives, begin the principal idea remaining the same, and so, the overall performance and the who-must-make-the-work of each part.

Hope you enjoyed!

Here you can check out live examples :

API call

JS drawing

NOTE: as updated on 2019/09/24, you can check all live examples in http://mtupd.com

Best regards!