Page MenuHomeWildfire Games

Flood fill algorithm to check tile connections
Needs RevisionPublic

Authored by Feldfeld on Jun 22 2020, 9:07 AM.

Details

Reviewers
FeXoR
nani
elexis
lyv
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Summary

This patch introduces the flood fill algorithm to check tile connections for generating random maps. This can be useful for maps which feature a highly random generation that cannot be controlled easily (like by creating passages) for some reasons. In particular, it can be used to ensure player connections.

Test Plan

It has been used in my new map Alpine Mountains. It can also be tested by creating tileClasses for specific cases and running the algorithm.

Diff Detail

Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

Feldfeld created this revision.Jun 22 2020, 9:07 AM
Feldfeld created this object with visibility "Feldfeld".
Feldfeld changed the visibility from "Feldfeld" to "Public (No Login Required)".Jun 22 2020, 9:49 AM
asterix added reviewers: Restricted Owners Package, FeXoR, nani, elexis.Jun 22 2020, 12:00 PM
lyv added a subscriber: lyv.Jun 22 2020, 12:04 PM

Keeping the connectivity map in a tileclass is also an idea but seems like that cache would always be on the verge of invalidation.

There are certain optimizations one could do for our use case. But this algorithm is cleaner and much more readable. And I think we can trade performance for readability here.

binaries/data/mods/public/maps/random/rmgen/math.js
184

These arrays should be avoided if the typed versions could be used. These generic ones also prone to cache misses. So, thats a nice bonus.

let connectionArray = new Uint8Array(mapSize*mapSize).fill(-1);

You can check against -1 instead of undefined and keep 1 and 0 for true and false respectively.

Feldfeld updated this revision to Diff 12422.Jun 22 2020, 12:21 PM
Feldfeld added inline comments.Jun 22 2020, 12:24 PM
binaries/data/mods/public/maps/random/rmgen/math.js
184

Actually, needing true/false was a relic from when I didn't use early stop when all connections were reached. Now we just need 0 = unvisited and 1 = visited

lyv added inline comments.Jun 22 2020, 12:29 PM
binaries/data/mods/public/maps/random/rmgen/math.js
184

Ah, my typo while writing Int8Array turned out to not be a typo after all.

Seems like this array can now be named touchedPoints or something similar. Guess this is just keeping track of processed tiles now.

Aside, from that, looks good. I will try to come up with some visual tests.

lyv added a comment.Jun 22 2020, 3:23 PM

I slightly cleaned up the syntax.

And since you are not in the credits yet, should I add just your nick, or your nick with your initials, or your nick with your real name?

Feldfeld updated this revision to Diff 12423.Jun 22 2020, 4:37 PM

For the credits, well just put my nickname I guess. I had another diff which modified it but I think it's pretty dead

lyv added a comment.Jun 22 2020, 8:45 PM

I will do those aforementioned tests and post here if something is not behaving as expected.

I think this would be all of the easy to see issues at least.

binaries/data/mods/public/maps/random/rmgen/math.js
329

This one was not renamed.

356

Would be nice to not push and pop useless values.

I dont think it matters, but the idx values for these points could be calculated using some basic arithmetic.

FeXoR added a comment.EditedJun 26 2020, 2:14 PM

Hi @Feldfeld and thanks for your patch ;)

Also thanks to you @smiley for the review so far. Indeed a visual test would be great so I would be greatful if you would share it when you happen to have that ;)

Bugs:

  • Like @smiley already mentioned: tilesToVisit is not defined and has to be renamed (see below).

Misleading naming:

  • AFAICT this function takes 2 areas (One area represented by a list of Vector2D each representing a (terrain) tile, and a second given as a list of TileClasses) and checks if all tiles of the first only contains tiles connected to (atm. randomly chosen) one of them by edges. if those tiles are contained in one of the given TileClasses areas it returns True, otherwise false. A floodfill algorithm - as I understand it - would take one tile and a set of constraints (which could be given by a list of TileClasses as you do) and return the area of all tiles that connects under those constraints to the given tile. So this proposal is more an "checkContinuity" function. Also TileClass can specify a lot of constraints that are not limited to "reachability", great! Just the name doesn't fit well then :D areTilesConnected maybe?
  • Points and (terrain) tiles should be clearly distinguished in the names in the variables holding them IMO.
    • points represent tiles AICT and must have integer x and y values. So I would prefer to call them tiles. An alternative would be position like phrased by constraints.
    • processedPoints represent the tiles of the map (or one point of every tile of the map I guess) so I would propose to call them processedTiles. (Sorry for that back and forth)

But before I continue a suggestion:
If we add a flood fill algorithm that takes a tile position (represented by a Vektor2D for conformity I'd say) and constraints returning an array of tiles (like those Area takes) we get the functionality of the proposed patch by checking if the flood filled area called with one point of the area contains all of the area given to the check against (e.g. with the AndConstraint). If not the area is not connected ;)

Maybe I have overlooked something but if we do it this way we have a much more powerful tool at our hands as I see it.

EDIT: With this patch you can just find out "yea, damn, the players are not connected" - but with a flood fill you would know where to place players so they are.

P.S.: The areaclass also uses the wording points for tiles but I really think we should be clear in our variable names.

lyv added a comment.EditedJun 26 2020, 5:43 PM

I have been looking at this as a connectivity test rather than a flood fill algorithm.

The usage is not the optimal in the proposed map, but I can certainly think of multiple reasons why this would be useful.

If we are going there, the connectivity test should not be a traditional vertex by vertex flood fill. The ideal solution would be constructing a graph out of chunks. A chunk being the 16 vertices that could be stored quite efficiently using an integer and could be tested even more easily.

I think you are focusing on the wrong detail here. This function as named is a connectivity test. The flood fill is used for detecting the connection. If this function were to use A* to do so, the function will still be the same to whoever is calling it.

While generating the provided map, this function was found to be a bit slow to my liking. It wasn't slow per se. It was fast enough. But when compared to other code in the rmgen I used, it was slow relatively. So, I am more inclined to reimplement the algorithm. But unfortunately that has to wait.

Your code, your decision. Seems like you are the only remaining rmgen guy, so you are gonna have to maintain this code.

lyv added a comment.Jun 27 2020, 11:35 AM

Since there seems to be some confusion.

If we add a flood fill algorithm that takes a tile position (represented by a Vektor2D for conformity I'd say) and constraints returning an array of tiles (like those Area takes) we get the functionality of the proposed patch by checking if the flood filled area called with one point of the area contains all of the area given to the check against (e.g. with the AndConstraint). If not the area is not connected ;)

Ideally, that's what the proposed map should be doing.

However, there are cases where you want a bool areTilesConnected function rather. One doesn't always want to create an area just to check if tiles are connected. Especially when the number of vertices in terrain is higher than currently supported (Lets face it, we can create a lot more cool shit if there are more to work with). Such a function in the general case can be written to perform way faster than using the function you propose. That's no surprise since you are proposing a different function that will be better for this kind of thing.

Say you want to place a path between t[x, y] and t1[x1, y1] only if t and t1 are connected. You could either generate an area just to check if your two tiles are in there. Or you could just traverse a pre-generated graph. The only problem I have with this is that this is implementing an identical algorithm to parts of the Hierarchical Pathfinder. Maybe that's not a problem, maybe it is. I haven't looked into this too deeply before this patch was proposed. In any case, until I do, I can't decide on something concrete. Nobody likes using a function only to find out it has to be rewritten yet again to be usable.

Just in case, I'm waiting for either a consensus or a decision by @FeXoR before updating my patch. I saw P212
This patch was intended as a connectivity test but I'm fine with changing it to return an Area.
The reason I didn't check against constraints instead of Tileclasses was because I didn't check how they worked under the hood (and, again, I wanted quickly something to work with my map), but that sounds better indeed.

FeXoR added a comment.EditedJul 17 2020, 8:53 PM
In D2828#121656, @smiley wrote:

I think you are focusing on the wrong detail here.

I also get the feeling that I'm doing something wrong when reviewing @smiley , yes! I don't know what it is yet though :p

Sorry @Feldfeld for my absences, I didn't forget about you just little time ATM ;)

Feldfeld updated this revision to Diff 15198.Jan 12 2021, 7:28 PM

Bug fix required for D2830 to work.

Feldfeld updated this revision to Diff 18345.Jul 28 2021, 5:31 PM

Update: use flood fill to get an area instead of only connectivity check.

lyv requested changes to this revision.Jun 9 2022, 7:15 PM

Some leftovers from the previous iteration.

With regards to simple test vs connected area, there are two different use cases. When you want to use the existing terrain and make the placement flexible instead, this is the better function as it allows to get all the needed information in one pass. The area of all tiles that are viable positions that would be guaranteed to be connected.
For other use cases, the boolean test would be better, for example deciding if a river way is suitable for fish placement. (Salmon in a river tributary only connected to the ocean).
For player placement for example, the area function is more suited as test and discard is less efficient than test and constrain. Assuming that the generated terrain won't be discarded and regenerated instead of moving player positions around.

binaries/data/mods/public/maps/random/rmgen/math.js
121

Given constraint, not just tileclasses. And better to clarify its tiles, or vertices and not just point.

123

This could be left to the caller to construct the appropriate constraint. The function would then receive a single constraint (an AndConstraint for an array). Would prevent unnecessary constraint construction in the general case. Also, the API always take a singular constraint as parameters.

124

Area

126

createConnectedArea

128

Safe to make it a static constraint. But again better to leave it up to the caller as this function really does not have the information to determine whether StaticConstraint would help with the performance. The caller can use it for lengthy AndConstraint and significantly improve performance. But for a single constraint, indiscriminate use would actually make it slower.

129

g_Map.getSize()

137

Bounds checking does not usually consider the map shape, just the grid. Let's make it consistent and just check 0 <= idx < mapSize^2

This revision now requires changes to proceed.Jun 9 2022, 7:15 PM