This is an implementation of the Disjoint-set algorithm to check if the grid Percolates. The program launches a GUI that allows you to poke holes in a grid, these holes will be represented as white cells. Once there is a pass through from the top to the bottom of the grid, the program will notify that the grid percolates. Diagonals do not count as a pass through.
I used both flattening and weighting techniques to make both connect() and is_connected() operations extremely efficient, even with millions of cells in the grid. Unfortunately this is bottlenecked by the rand() operations and SDL rendering, however if you wish to try and fix this, feel free!
⚠ Warning: The grid size cannot be above 1/2 of the window size, otherwise the grid will not render. If you wish to test a larger grid, please increase the window size to at least 2x the desired grid size in the rendering.c file.
User Mode: bin user [grid size]
Random Mode: bin random [milliseconds interval] [grid size]
The milliseconds interval can be set to zero fastest possible simulation.
You can also change the parameters in the Makefile and call make run.
⚠ I have currently setup the configuration for my Windows Mingw environment. Feel free to play around to get this working for your system, and PRs are welcome!
If you are using Mingw on windows:
- Install the SDL source code for the mingw environment
- Create a
/srcfolder in the root of your project - CD into either
/i686-w64-mingw32or/x86_64-w64-mingw32 - Copy the
/includeand/libfolders into your project's/srcfolder - CD into the
/binfolder of your chosen source folder - Copy the
SDL2.dllfile into the root of your project - Run
maketo build - Run
make runto run the program