3 ms·
This method is super fun for mazes of size 10x10 but the odds a particle reaches exit decrease exponentially with the size of the maze. Make the maze 20x20 and
by pkrumins 4y ago
This method is super fun for mazes of size 10x10 but the odds a particle reaches exit decrease exponentially with the size of the maze. Make the maze 20x20 and you will have to wait for the solution for a day, and make it 30x30 and you will have to wait for a year.
- thriftwy 4y agoI would assume it should be possible to craft relatively small mazes which will be practically unsolvable by this algorithm. Which is DoS vulnerability.
- planede 4y agoNote that there are two variables for running the simulation: t - duration of simulation for each individual particle N - number of simulated particles I believe if you leave t fixed, and then increase the size of the grid, then yeah, the number of simulated particles you need probably increase exponentially (or worse) for finding one that reaches the exit. But you probably want to increase t with the grid size as well, and I think that would mitigate this to be less bad than exponential. This is basically diffusion, and characteristic distance travelled by diffusion is proportional to sqrt(t).