Page Menu
Home
Wildfire Games
Search
Configure Global Search
Log In
Paste
P212
Simple flood fill (against list of tiles  which is 0(n²) so transform to "map" first to be O(n))
Active
Public
Actions
Authored by
FeXoR
on Jun 27 2020, 6:22 PM.
Edit Paste
Archive Paste
View Raw File
Subscribe
Mute Notifications
Award Token
Flag For Later
Tags
None
Subscribers
None
function
getMap
(
points
)
{
let
i_min
=
Infinity
;
let
i_max
=
0
;
for
(
let
p
of
points
)
{
if
(
p
[
0
]
<
i_min
)
i_min
=
p
[
0
];
if
(
p
[
0
]
>
i_max
)
i_max
=
p
[
0
];
if
(
p
[
1
]
<
i_min
)
i_min
=
p
[
1
];
if
(
p
[
1
]
>
i_max
)
i_max
=
p
[
1
];
}
if
(
i_min
<
0

Math
.
round
(
i_min
)
!=
i_min
)
warn
(
"getMap: i_min is supposed to be nonnegative integer but is "
+
uneval
(
i_min
));
if
(
Math
.
round
(
i_max
)
!=
i_max
)
{
warn
(
"getMap: i_max is supposed to be integer but is "
+
uneval
(
i_max
));
i_max
=
Math
.
round
(
i_max
);
}
let
m
=
new
Array
(
i_max
).
fill
(
0
).
map
(()
=>
new
Uint8Array
(
i_max
));
for
(
let
p
of
points
)
m
[
p
[
0
]][
p
[
1
]]
=
1
;
}
function
getContinuousAreaFromTiles
(
startTile
,
allowed_tiles
)
{
if
(
allowed_tiles
.
indexOf
(
startTile
)
==

1
)
return
[];
if
(
allowed_tiles
.
len
()
==
1
)
return
[
startTile
];
let
tilesToCheck
=
[
startTile
];
let
connectedTiles
=
[];
while
(
tilesToCheck
)
{
let
currentTile
=
tilesToCheck
.
shift
();
let
index
=
allowed_tiles
.
indexOf
(
currentTile
);
// This may be a performance issue
if
(
index
!=

1
)
{
connectedTiles
.
push
(
currentTile
);
tilesToCheck
.
push
([
currentTile
[
0
]
+
1
,
currentTile
[
1
]]);
tilesToCheck
.
push
([
currentTile
[
0
],
currentTile
[
1
]
+
1
]);
tilesToCheck
.
push
([
currentTile
[
0
]

1
,
currentTile
[
1
]]);
tilesToCheck
.
push
([
currentTile
[
0
],
currentTile
[
1
]

1
]);
allowed_tiles
.
splice
(
index
,
1
);
}
}
return
connectedTiles
;
}
Event Timeline
FeXoR
created this paste.
Jun 27 2020, 6:22 PM
FeXoR
changed the visibility from "All Users" to "Public (No Login Required)".
Jun 27 2020, 8:38 PM
Feldfeld
mentioned this in
D2828: Flood fill algorithm to check tile connections
.
Jun 28 2020, 7:59 PM
Log In to Comment