Godot Simple 2D Square Lattice Random and Self Avoiding Walk Generator Addon

This simple addon gives you two Resources, one for generating random walks (RWs) and the other for self avoiding walks (SAWs), both on 2D square lattice.

This can be useful to create paths in roguelike games.

Walks are defined by their endpoints, that must be provided. 

You can decide if the path must stay in a given box (xmin,ymin) (xmax,ymax) or not.

In the case of SAWs, it is possible to introduce obstacles that must be avoided, but to ensure that this happens, some extra work is needed by the programmer: namely, a starting configuration that avoids the obstacles must be provided. Otherwise, the generated path might not avoid all the obstacles.

I have not added this feature for RWs, please tell me if you would like it. 

For RWs, on the other hand, you have an additional parameter, the directionality, that controls how much directional the walk is. Default value is 1 which is fine imho. For directionality = 0 you have a pure RW, which is seldom useful because it has Hausdorff dimension of 2, therefore it tends to fill the plane and never reach its endpoint. Negative directionality makes no sense and will produce neverending loops, avoid it. Also too big directionality (say > 1000) is useless and might produce long loops, avoid it too. Stay in the range 0-10 imho, or up to 100 but really you will see it does not make sense to get to such high values.

The walks are constructed in rather different ways:

SAWs are built modifying an initial configuration (that can be provided by the programmer or you can choose to let the addon build it) and modifying it with the BFACF algorithm, ensuring self avoidance. It is a slow algorithm, however you will always get your SAW with desired endpoints in a fixed amount of loops.

RWs, on the other hand, start at an endpoint, and crawls its way to the other. This means that, in principle, it might never reach it! Use directionality and/or confine the walk in a box to prevent this.

The description of the exported variables is in the code and is very simple. 

You also get a demo that shows you most of the functionalities.

For the methods:

- the Random Walk generator has only a method of interest, random_walk_in_grid(). It generates the random walk, with the parameters set in the @exported variables.

- the Self Avoiding Walk generator has 3 methods of interest: 

1) self_avoiding_walk_in_grid(), that generates the SAW; 

2) bilinear_path_initializer(), that can be used as a starting path initializer if you do not want to give your starting path AND the default path initializer is not fine for you (play with the two initializers to see the difference: the default one, which is in the self_avoiding_walk_in_grid() method, tends to produce walks "straight from start to end", the bilinear tends to produce walks made of 2 "horizontal" pieces and two "vertical" pieces, especially if you reduce the @exported parameter  "iterations_multiplier")

3) reduce_wiggles() can be used to reduce some of the SAW wiggliness (which is sometimes annoying so this method comes in handy imho).

Ask me anything if you have any trouble, leave a comment if you like, and if you decide to use this addon credit me as "coros (boris marcone)".