Page MenuHomeWildfire Games

Flood fill algorithm to check tile connections
Needs ReviewPublic

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

Details

Reviewers
FeXoR
nani
elexis
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.Mon, Jun 22, 9:07 AM
Feldfeld created this object with visibility "Feldfeld".
Feldfeld changed the visibility from "Feldfeld" to "Public (No Login Required)".Mon, Jun 22, 9:49 AM
asterix added reviewers: Restricted Owners Package, FeXoR, nani, elexis.Mon, Jun 22, 12:00 PM
smiley added a subscriber: smiley.Mon, Jun 22, 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.Mon, Jun 22, 12:21 PM
Feldfeld added inline comments.Mon, Jun 22, 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

smiley added inline comments.Mon, Jun 22, 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.

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.Mon, Jun 22, 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

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.EditedFri, Jun 26, 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.

smiley added a comment.EditedFri, Jun 26, 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.

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.