Back
Close

Voronoi Diagrams

Marchete
25.6K views

Let's get our hands dirty

Now that you know what a Voronoi Diagram is, let's see what you've got! We have a board where multiple firetrucks can move in four directions (up, down, left, right). By using a Voronoi Diagram, a truck always knows what tiles of the grid it has to cover, because the tiles in its Voronoi site are the tiles it would reach first in case a fire starts.

You have to define, for each tile of the grid, in what Voronoi site it is, relative to the trucks' positions. The trucks move around the map randomly.

We call your function at every game turn and draw the map accordingly. You don't have to code the game, just fill the Voronoi diagram!

As a reminder, here is the pseudo-code for the naive Voronoi algorithm:

 for each (tile in tiles){
   tile.site = null; // Clear site owner of the point
   for each (site in sites){
     double tempdist = distance(tile,site);
     if (tile.site == null || tempdist < distance(tile, tile.site)) {
      tile.site = site; // Update site owner if it's nearest.
     }
   }
 }
Did you solve it?
Got Stuck? Click here to view a solution for this exercise
// Create the Voronoi areas
function fillVoronoi (tiles, players) {
  for(var t in tiles) {
    var tile = tiles[t];
    tile.site = null;
	//Then, for each player we will check if it's the nearest:
    for (s in players){
      var site = players[s];
      var tempdist = distance(tile,site);
      if (tile.site === null || tempdist < distance(tile, tile.site) ){
        tile.site = site; // Update site owner
      }
    }
  }
}

function distance(pointA, pointB) {
  //We return the Manhattan distance, that is coded as:
  var dx = pointA.x - pointB.x;
  var dy = pointA.y - pointB.y;
  return Math.abs(dx) + Math.abs(dy); // Manhattan distance formula  
}

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
// Create the Voronoi areas
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants