> Drafts
Draft in progress, written by ''Hazurl''
This article gives you the basics for tackling any kind of algorithmic problem. It is mainly aimed at beginners who don't know where to start, but not only them. The first part explains the different ways of solving a problem, that is, the theory. Then I will use the reachable cells algorithm as an example to put these methods into practice. I chose this algorithm because it is one of the most useful ones, and because the page about it isn't suited to beginners: it is written with optimization in mind. Speaking of which, optimization won't be covered in this article; other articles already deal with it.
Generally speaking, an algorithmic problem is a question that a computer can solve. There are two kinds:
You don't really need to memorize this; it's more for your general knowledge.
Nothing could be more obvious, and yet it's a step many people forget. And not just beginners. You need to understand the subject properly, and don't hesitate to read it again so that nothing is unclear. Imagine explaining the subject to someone who has never read it. You must be able to rephrase it from memory, without generalizing or narrowing it down, or you'll start off on the wrong foot. Don't start thinking about how to solve it yet. You need to spell out the input and output data, how they are structured, etc... If the problem places no constraint on the output, think about how it will be handled, so as to make it easy to use. You must be able to answer these two questions (perfectly!):
The best way to find how to implement the algorithm is to solve it yourself. Don't pick the examples purely at random: take varied cases and edge cases. Look for the point where solving it gets complicated, then push your examples to the extreme. Next, prepare something to test the algorithm with. A simple equality test against the correct output can do the job; otherwise, you can display the output in a simple way and check it by hand.
This is the most hands-on step. You must turn your problem into a solution. The best way is to proceed in increasingly precise steps, starting from your initial problem; you'll notice, by the way, that this process is an algorithm in itself 😉. Split the problem into sub-problems while bringing out the control structures: loops, conditional structures... At each step, try to redefine all your problems. Nothing beats an example to illustrate this idea: sorting an array. We have an array as input, and we return a sorted array (say, in ascending order). How do you sort an array? You obviously have to modify it, but that's not enough: you have to modify it until it is sorted. Oh! But... wouldn't that be a loop? So our first split has revealed a loop, along with its body and its condition. But "modify the array" is not very precise... You also have to keep in mind that a loop can mean an infinite loop. Make very sure that the condition evaluates differently at some point, so that you exit the loop. So modifying the array must leave it more sorted than before, so that the array ends up sorted at some point and the loop ends. There are many ways to sort an array; one of the simplest is to swap the smallest element with the first element, then do the same with the second element, and so on. More generally: for each element of the array at position i, swap it with the smallest element to its right. Here is where we stand:
Function sort_array (arr) // arr being the variable holding the array to sort While is_not_sorted(arr) For i from 0 to n - 1 // n is the size of the array pos_min = pos_min_on_right(arr, i) // position of the smallest element of the array to the right of i swap(arr, i, pos_min) // swap the two elements End For End While return arr End Function
We still need to define whether an array is sorted or not (the condition), the position of the smallest element to the right of i, and finally how to swap the two elements of the array. To find the smallest element to the right of i, go through the elements from i to the end of the array and take the smallest of them:
[Not finished]
It's important to test your algorithms, first with the examples you solved by hand earlier, then with more complex problems. You need a way to check the results, though. You can check them by calculation or by looking at the data (with mark or debug). If your algorithm doesn't meet the requirements of the problem, rework it by targeting the cause of the problem, again with the help of the debug functions. You can also write your own bench to test your algorithm, but that is usually done with optimization in mind. To describe it briefly, a bench is a function that tests, checks and measures the execution cost of your function on large samples of data. For example: function bench (functionToTest, message, input, expectedResult);.
Great, now that you know everything, you need to put it into practice. And why not with the reachable cells algorithm... I'll briefly explain the problem; if you want more details or optimization ideas, there is a whole page dedicated to it.
What do I have at the start?
Remember the basic questions you must be able to answer? This is one of them, and it's not very complicated. But first, I'd like to give you a tip. Don't make your functions too specific: they should only need the information passed to them as parameters, and side effects (fetching information from outside the function) must be avoided. You should never do something like getNearestEnemy inside a function. This applies to all your functions. Of course, what I just said isn't true in every single case. If you write a getDistanceFromNearestEnemy function, calling getNearestEnemy is justified, even though a more generic function would serve you better: getDistanceFrom. You have to strike the right balance. Right, back to our question... We need to find all the cells that can be reached from a given cell with a certain number of MP. The choice of parameters matters: if we don't define any, there's no way to know which cells our leek can reach, or which ones the enemy leek can reach. So we need at least the choice of leek in our parameters, but then another problem shows up: what if we want to work out the reachable cells after a move, to plan ahead? In that case we need a cell in our parameters, but then there's no longer any way to know the number of MP, so here is the function's signature:
getReachableCells (cellFrom, MP)
This is the one we'll use on this page. Feel free to do it differently, for example by computing the distance for every cell, so you don't need to recompute anything after an MP boost.
What do I need to get?
We need to get the list of cells reachable from a given cell with a certain number of MP. A list is represented by an array. It would be convenient to have the array sorted by distance, so that when we go through it with a for loop, we look at the closest cells first and save MP. We can do even better: by taking advantage of (associative) arrays, we can have an array with the cells as keys and the number of MP as values, that is: arr[cell] returns the number of MP needed to reach cell. So we've decided that our array will look like this:
[cellFrom: 0, cell1 : 1, ... , cellX : 2, ..., cellN : n] // or more simply [cell : MP] sorted by increasing MP for an array that starts from cellFrom with n MP. Thanks to this, if we go through our array with for (var cell : var mp in getReachableCells (cellLambda, MPLambda) ), the two variables cell and mp will take the values cellLambda and 0, then all the cells at a distance of 1, then 2, etc., up to MPLambda.
We'll now split our problem so that we can translate our algorithm into LeekScript more easily. Initially, we have: "Find all the cells reachable from a cell with a certain number of MP" Since we want them in a specific order (increasing distance), the best is to build the array directly in that order, since sorting is relatively expensive. So we need to add the cells at distance 0, then 1, then 2, up to n MP. We already have our first cell, since it's given as a parameter. Next, we need to find the cells at distance 1 (unless we have 0 MP). How can we get them? getCellDistance doesn't take obstacles into account, and getPathLength is expensive... too expensive; remember that the whole point of this algorithm is to avoid calling getPathLength every time. Let's think more broadly: once we've found the cells reachable at distance 1, we'll need to find the cells reachable at distance 2, and so on. So, to sum up, when we want the cells at x MP, we have:
The starting cell: cellFrom The list of cells at x - 1 MP
The easiest way is not to find them from the starting cell, but rather from the list of previous cells. Indeed, we have to take obstacles into account, and starting from cellFrom would make us recompute everything all over again. To get the new cells from the previous ones, we need to find the "neighbors" of those cells. Then we need to check them, so that we don't add an obstacle or a cell that has already been defined.
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.