The algorithm used in building the board part of the tutorial isn’t as efficient as it can be. Can you think of a better way of doing it? Hints:
self.__gridwith available locations instead of initializing it to an empty array and populating it every loop step with locations of placed tiles
- the only other modification that needs to be made is in the
__add_other_tilesfunction. Instead of adding the locations to
self.__gridthink of a way on how to efficiently use the array of available locations
Let’s understand what the problem is with the implementation from building the board part. Say we have a 10 by 10 grid to place objects, so we have 100 valid places. Let’s say then that we have 50 obstacles to place on the board, 30 items and 11 enemies. Now, consider what would happen on the iteration for placing the last enemy on the board, the 91st object (or the 11th enemy). We have already occupied the first 90 tiles so there’s a 90% chance that we will hit a location on the grid that already has an object placed on it because the random number generator that picks a location uses a uniform distribution. That’s not good, that means that out of 10 tries, 9 of them are likely to fail, that’s a lot of iterations to fail and a lot of wasted time.
Wid. 01. Interactive widget exemplifying the process of board creation using this solution. Courtesy of Dazz.
Luckily there’s a better algorithm for placing the tiles, and as you can try on the widget, there’s no need to check for placed objects on the grid any longer. How can we do this? Well, instead of keeping track of placed objects, we keep track of empty places to put our objects in, eliminating used up spaces as we go along!
Let’s get to the implementation. The first hint that was given in the assignment is to initialize
self.__grid with these places that we’ll need. This is very simple. Let’s construct a method for this, to keep things neatly organized:
1 2 3 4 5 6
func __make_grid(): var grid =  for x in range(self.inner_grid_size.x): for y in range(self.inner_grid_size.y): grid.push_back(Vector2(x, y)) return grid
This is very straightforward and self-explanatory. We iterate over the
x coordinate of the inner grid, then on the
y coordinate and finally we add that location at the back of the grid array with
Vector2) which we will then return from the function.
The second hint is that we should modify
__add_other_tiles in order to use these inner grid locations to our advantage so we won’t have to check each iteration for objects that have already been placed.. Well think about it, if we have the list of available locations, we just need to randomly pick one, place the object in that place and then remove this location from the list. This way there’s no risk of picking the location again on the next iterations. Let’s implement that, it’s really easy:
1 2 3 4 5 6 7 8 9
func __add_other_tiles(tile_set, count=Vector2(1, 1)): var n = int(rand_range(count.x, count.y)) for i in range(n): var idx = int(rand_range(0, self.__grid.size())) var xy = self.__grid[idx] var tile = self.__rand_tile(tile_set) self.__add_tile(tile, xy) self.__grid.remove(idx)
Let’s go over it. First we randomly select the number of objects to be placed (
n). Then we iterate over exactly
n times. Each iteration we get a random index (
idx), just a number, between 0 and the number of available locations in the
self.__grid variable, next we retrieve that location from
self.__grid, add the tile in that location and finally remove the location from
self.__grid so there’s no risk of it being picked again. Very simple, let’s compare it to the old implementation:
1 2 3 4 5 6 7 8 9 10
func __add_other_tiles(tile_set, count=Vector2(1, 1)): var n = int(rand_range(count.x, count.y)) while n > 0: var xy = Vector2(randi() % int(self.inner_grid_size.x), \ randi() % int(self.inner_grid_size.y)) if not xy in self.__grid: var tile = self.__rand_tile(tile_set) self.__add_tile(tile, xy) self.__grid.push_back(xy) n -= 1
Wouldn’t you agree that the better algorithm is actually more intuitive? Now to actually make proper use of this, we’ll have to properly initialize
self.__grid inside the
make_board function: just replace
self.__grid =  with
self.__grid = self.__make_grid(), that’s it!
Thanks for dropping by! As always, let me know what you think about the lessons/tutorials so I can improve them.