disclaimer

Although I have quite a bit of programming experience in high level languages, I may not be qualified to teach you anything about game development as I am learning myself and I probably do not have a sense of how code should be written just yet. So please keep in mind that I am very new at this as well and don’t take it as the definite way to do it. It is only my way.

assignment

with Godot v2.1.stable.officiali-godot

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:

  1. initialize self.__grid with available locations instead of initializing it to an empty array and populating it every loop step with locations of placed tiles
  2. the only other modification that needs to be made is in the __add_other_tiles function. Instead of adding the locations to self.__grid think of a way on how to efficiently use the array of available locations

solution

with Dazz‘s helpDazz on itch

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 push_back (as 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!

concluding remarks

Thanks for dropping by! As always, let me know what you think about the lessons/tutorials so I can improve them.

project files

As usual I’m attaching the zipped finished project which has annotations in the res://Scripts/Game.gd. Have fun with it!