I don’t think people would be too eager to discuss strategies while the contest is ongoing (me neither, of course), so I’d like to invite you to try it out. However, a few notes…
I’m confused why you would consider flood fill conceptually different from BFS or DFS in this case. In general, I’m rather against considering “flood fill” an algorithm, as much as I wouldn’t consider “max flow” an algorithm. I’d say that “flood-fill” is a problem that can be solved via several algorithms. However, I don’t want to get into that because it’s probably a lost fight and the whole Internet doesn’t agree with me.
You’d probably want to balance several factors: getting close to the most likely position for your enemy, not making your position too obvious, delaying as much as possible the need to surface… You’ll notice that these objectives go a little bit against each other, committing too much to one of them can sacrifice the others, and different algorithms are best suited for each of them.
These are my first steps with pathfinding.
Still, your reply was helpful.
I went with simplified BFS and the boat moves properly.
Although, moving alone is not enough to jump up out of Wood League
I didn’t consider that the people would be so competitive and keep quiet with theirs ideas
Yesterday evening in the chat, they told me to use Flood Fill (I’m only checking the 4 adjacents for now with some kind of evaluation of which would be the best, but it seems to be enough for Silver league with a few torpedoes and silence)
every time I want to move, I check adjacent cells and evaluate them quickly taking into account if they have enough accessible adjacents themselves and how far they are from the closest possible enemy.
But I’ll do a flood fill because I’m running into dead-ends too often
My understanding of Voronoi is that its goal is to determine the areas that are closest to some positions and I am not sure how it would help in this game.
A simple floodfill with a move depth of 1 should be enough for acceptable pathing (at least until silver league).
Here is an example:
ooo
ooo
oxx
poo
x: visited cells or islands
o: sea cells that are not visited
p: your current position
The algorithm is quite simple, for every every new cell you can reach, compute its accessible zone (cells that are linked to it by non visited sea cells), then choose the one with the biggest zone:
_N (0,2): 6
_E (1,3): 1
So here your best move is N.
In some edge cases you can make wrong decisions, but it’s marginal (and if you really want to you could compute the accessible zone after n moves instead of just 1):
ooooo
xxoxx
oopxx
oooxx
N: 6
W: 5
S: 5
So N seems to be the better option, but then your zone will be cut in 2. In the end you will only get 4 moves while W and S would have given you 5 moves. => this doesn’t arrive often.
My experience is that you won’t often surface more than once per game with by computing the accessible zones with a move depth of 1. Also most of the time the game will end before you even surface when at least one player has good opponent detection. (I think there is no silence in wood?)
Managed to get into the silver league with flood filling and avoiding surface for as long as possible. Also I tried sticking to the walls as much as possible, but overall this revealed my position to opponent very much. Moving in the same direction many turns in a row also reveals your position to opponent pretty much.
