#### Table of contents

## assignment¶

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:

- 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 - 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¶

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 91^{st} object (or the 11^{th} 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.