Jump Flooding Algorithm for GMS2
Jump Flooding Algorithm for GMS2 made with shaders.
Algorithm fills empty areas of surface texture with given seeds. This is done by creating coordinate mapping, which tells position to closest seed. This coordinate mapping can be used for various things. Like filling empty areas with closest color, which generates approximate Voronoi diagram. Coordinate mapping can be transformed to different fields, like distance and normal fields.
Further reading about algorithm:
https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf
https://www.rykap.com/graphics/skew/2016/02/25/voronoi-diagrams/
This asset uses shaders for heavy lifting, but there is wrapper for easy-to-use, check screenshot for how-to-use. Internally jump flooding struct creates a own surface, where every pixel maps coordinates for closest non-empty seed. These coordinates are encoded to color channels, to support larger surfaces, x-coordinate is encoded to RG channels and y-coordinate BA-channels.
This has been made with GMS2.3.3. If you have other GMS2.3 version, it should work when you modify use of default arguments. This will not work with GMS2.2 or earlier.
- - -
Here is example of use in jam-game:
The ground, glow and collisions use distance field; which has been generated with modified version of this asset. Game uses distance field is size of 64x64 pixels, but it doesn't look blocky because distances can be interpolated when scaling up.
Download
Click download now to get access to the following files:
Comments
Log in with itch.io to leave a comment.
Can this find neighboring voronoi cells? I have before used floodfill to just add a cell if it is neighboring but that I don't believe is all that efficient, you may have a better way of doing it
Hello. First note, that this asset uses shaders to fill up empty areas of surface. So you need to decode values from surfaces to use them in GML.
The main focus in this asset is to create coordinate mapping, so we have surface which tells coordinates to the closest seed values.
This mapping can be used for several things, like doing approximate Voronoi diagram by filling empty areas with closest seed. You can transform coordinates to different fields, like distance or normal fields.
Now from off the hat, I can't say could you do this efficiently; but you would want to transform this mapping to tell coordinates about second closest seed. I have idea how you could do that (edit. nope didn't work, I'll rethink)
As the elephant in the room, this asset is most useful for visual things, because all important information are stored in surfaces. To access them in GML, you need to decode them to e.g. buffer.
That can be huge hassle, but also can cause lot of overhead; if you need to constantly flood and then decode to buffer. In that case, I wouldn't recommend using this asset, even if finding second closest seed would be feasible.
Now if seed is rarely updated, then it can be useful (because then you don't need to re-flood and decode it constantly). Here is example of use with my jam-game.
The ground, glow and border use 64x64 distance-field. Distances can be interpolated nicely, so ground is smooth instead blocky. Also distances are decoded into buffer, which games uses as collisions.
In that game, distance-field is created with this asset by using 256x256 seed surface, which is only done at the start of level. Making level was done by just drawing random shapes to seed, then: flood, transform & decode. This allows destructible environment too, as I could have just erase area in seed, and do steps again.
Sorry about long post 😅