Voronoi Diagrams
Marchete
93.3K 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.
Suggested playgrounds
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Create the Voronoi areas
function fillVoronoi (tiles, players) {
/*
Modify the `site` property of *each* tile to be a *reference* to one of the players
given as parameter. The tile must be in that player's Voronoi site.
ex:
tiles[0].site = players[0];
tiles[1].site = players[1];
*/
for(var t in tiles) {
var tile = tiles[t];
tile.site = null;
// TODO: Select the nearest player, assigning it to tile.site
}
}
function distance(pointA, pointB) {
// TODO: Implement the manhattan distance function
// Both tiles and players have a `x` and a `y` property
return 0;
}