1
\$\begingroup\$

I'm making an RTS game using html canvas. I've made a program that randomly generates levels in order to test my pathfinding script. it divides the pathable blocks into squares so that you can apply A* pathfinding to it.

the level generator

While this is all well and good, I'm more fond of Navmeshes, as the movement in them is more natural, and units move directly to their goal instead of taking jagged routes across blocks.

Mike West has the best implementation of this in HTML, which you can find here: JS navmesh

In this script, however, navmeshes cannot be generated on the fly. with this in mind, I'd like to create a script that analyses the entire level and groups together the largest possible areas in the entire map while only using rectangles and squares.

Ideally, it would look like this:

enter image description here

So far, I have yet to come up with a solution. the script would have to scan the level and then look at it objectively to find the largest areas. I'm sure something like this has yet to be done before, though I can find no trace of it. what do you think?

var Tile = [[1, 1, 1, 1, 1, 1, 1, 1],
            [1, 0, 0, 0, 0, 0, 0, 1],
            [1, 0, 0, 0, 0, 0, 0, 1],
            [1, 0, 0, 0, 0, 0, 0, 1],
            [1, 0, 0, 0, 0, 0, 0, 1],
            [1, 0, 0, 0, 0, 0, 0, 1],
            [1, 0, 0, 0, 0, 0, 0, 1],
            [1, 1, 1, 1, 1, 1, 1, 1]];

$( document ).ready(function(){
  $('#GenerateButton').click(function() {
    GenTiles();
    CreateNavMesh();
  });
});



function GenTiles(){
  $('#window').html('');


  var terrainString ="";
  	for (var x = 0; x < Tile.length; x++){
  		terrainString += '<div class="row">';
  		for (var y = 0; y < Tile[x].length; y++){
        var dirt = '<div class="tileGround" id='+ x + '|' + y +'></div>';
        var wall = '<div class="tileWall"  id='+ x + '|' + y +'></div>';
        switch(Tile[x][y]){
  				case 0:

            if (Math.random() > 0.3){
              terrainString += dirt;
            }
            else {
              terrainString += wall;
            }

  				break;

  				case 1:
  					terrainString += wall;
  				break;
  			}

  		}
  		terrainString+='</div>';
  	}
  	$('#window').append(terrainString);
}

function CreateNavMesh(){
  /*


  var mainDiv = $("#window").children().toArray();
  console.log(mainDiv[0][0]);
  for (var x = 0; x < mainDiv.length ; x++){
    console.log(mainDiv[x].children().toArray());
    for (var y = 0; y < mainDiv[x].length; y++){
      console.log(mainDiv[x],[y]);
      if(mainDiv[x],[y] == 0){
          mainDiv[x],[y].addClass('.highLight');
      }
      else {
        chosCol = back[Math.floor(Math.random() * back.length)];
      }

    }
      }
    */
    var back = ["#ff0000","blue","gray", "purple"];
    var rand = back[Math.floor(Math.random() * back.length)];
    var chosCol = rand;
    $( ".row" ).each(function() {
      $(this).children().each(function(){
          console.log($( this ));
          if($(this).hasClass("tileGround")){
              $(this).css("background-color", chosCol);;
          }
          else {
            //chosCol = getRandomColor();
          }
      });
    });
  }

  function getRandomColor() {
  var letters = '0123456789ABCDEF';
  var color = '#';
  for (var i = 0; i < 6; i++) {
    color += letters[Math.floor(Math.random() * 16)];
  }
  return color;
}
#window{
  width: 240px;
  height: 240px;
  overFlow: auto;
}

.row{
  display: block;
  float: none;
  position: relative;
  height: 30px;
}

.tile{
  background-color: #ddd;
  width: 30px;
  height: 30px;
  float: left;
}

.tileWall{
  background-color: #333;
  width: 30px;
  height: 30px;
  float: left;
}

.tileGround{
  background-color: #fff;
  width: 30px;
  height: 30px;
  float: left;
}

.highLight{
  background-color: #444;
}
<html>
  <head>
    <link rel="stylesheet" type="text/css" href="style.css">
    <script src="https://ajax.googleapis.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
    <script src="code.js" type="text/javascript"></script>
  </head>

  <body>
    <div id="window">
    </div>
    <button id="GenerateButton">Generate Grid</button>
  </body>

</html>

\$\endgroup\$
  • \$\begingroup\$ Maybe this answer helps then you just need to calculate each bound and make quads/rects ( 4 vertices ) out of them for your navigation mesh \$\endgroup\$ – Sidar Feb 23 at 13:33
1
\$\begingroup\$

I've heard this called "Room Generation" when used as an optimization to speed up A*. The only algorithm I know of is Rectangular Symmetry Reduction (though there are probably more)

Image from blog post

It is described in these two papers1,2. Daniel Harabor (one of the creators of both RSR and the more well-known "Jump Point Search") has a blog post about it here, which is where I took the image from.

I don't know enough about it to describe its implementation here, but this should get you started.


  1. D. Harabor, A. Botea and P. Kilby. 2011. Path Symmetries in Uniform-cost Grid Maps.
  2. D. Harabor and A. Botea. 2010. Breaking Path Symmetries in 4-connected Grid Maps.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.