Hey guys!,

So, I'm basically working on an explorer right now.

It should, as the name suggests, explore the entire thing, the most efficient way possible.

• Your character has vision around you, of, 10x10.
• The map is much bigger, 100x100.
• However, it can't just go straight from a corner to another, because: The tiles can be an occupied, or un-occupied one.
• You can add weights to the tiles, so feel free to use this in your advantage (let's say, adding an extra weight to a visited tile so you can compare visited against non-visited ones).
• You can use the Pathfinder I'm using, based on the A* algorithm.

So, I could be wrong, but by basic logic, I assumed that the "fastest way" to explore the entire thing, is answering the question "What is the nearest tile that I can walk in, that is not occupied and that can reveal as much fog-of-war (unvisited tile) as possible?"...

My questions are:

• 1) Is my question correct? is that really the best way to explore the entire map?
• 2) If so, what's the best way to know "which is the tile that could reveal the most fog of war"?

Once I get the tile that reveals the most fog of war possible, then I just throw the pathfinder to it.

But I'm having problems doing a good way to achieve that :'( 

I hope you guys can help me on this one! 

Thank you

Isn't it sufficient to walk to the nearest fog tile?

Hello guys! thank you for answering me...

On 4/20/2018 at 6:45 PM, L. Spiro said:

• Nearest Tile
  • Simple distance check.
• Not occupied.
  • Simple boolean check—game mechanics can update the boolean.
• Can Reveal as Much as Possible
  • How is this determined?  Does the tile have a number that represents how much coverage it has?  Don't tiles all cover the same area and thus reveal the same amount?  How is this calculated?

 

1) I got the nearest tile function already and it works pretty nicely to discover stuff like the nearest mob, or to discover the nearest resource when doing basic exploration.
2) Got it too.
3) This is the thing, of course, tiles separately can either be revealed or not, but the map being 300x300 or whatever, it could not be the same to try to explore "top" (when there's only 20x to be explored there) or explore "bottom" where the map could be 50% unexplored in that direction... that's the algorithm I'm trying to improve a bit.
 

On 4/20/2018 at 12:49 PM, Alberth said:

Isn't it sufficient to walk to the nearest fog tile?

Nope haha...

Here's what I've been trying to do:
1) What I just quoted (it works, but is very inefficient and sometimes it takes too long to explore.
2) I've been seeing people applying the circular formula or the checksum of the surrounding square of a tile to get the "sum" of the entire area around it, so you can know which tiles have the most "fog of war" around it, it is much more efficient than #1 because it will hardly choose cornered tiles and such, but feels like there's probably a fast enough way to do something like this but with much bigger area than 20x20.

To illustrate what I'm trying to achieve a little bit better I just drew the picture from above.
Black being unexplored and green explored, given that situation, the algorithm should be able to detect that going south is a preferred unexplored tile to go  

You're not telling why you need this algorithm, is this for an AI?

In that case, be aware that it's not very difficult to outperform a human with things like this. In the end, you have an overpowered AI which is no fun to play against, as it just wipes you just clean off the board before you get a chance since it is faster and more accurate in just about anything.

18 minutes ago, L. Spiro said:

Then use a routine to find a mark fog sections, find the closest largest fog section, and use A* to head in that direction.


L. Spiro

This sounds juicy!

What do you mean with 'mark fog sections' exactly?

13 minutes ago, Alberth said:

You're not telling why you need this algorithm, is this for an AI?

In that case, be aware that it's not very difficult to outperform a human with things like this. In the end, you have an overpowered AI which is no fun to play against, as it just wipes you just clean off the board before you get a chance since it is faster and more accurate in just about anything.

 

I used to create a lot of bots before but I never had to deal with fog of war before...

Because I could explore the map myself then save the explored map, but in this new kind of games, maps change and are re-created regularly (just as Diablo dungeons worked back then), so I need to have quite a decent explorer for this.

Multiple things require exploration, gathering resources and so forth...

The maps are also quite big so small tweaks in efficiency have a huge impact on the required time to achieve such result ;P 

11 minutes ago, L. Spiro said:

Count the number of squares in a fog patch.

Use that information to decide the direction of the closest largest fog patch.


L. Spiro

Ohhhh yeah! I think this is exactly what I'm doing now, as I said before in the #2 thing I've seen so far, it looks like the most efficient way to do it so far.

Thank you for sharing your thoughts!

One thing to consider:

When exploring an area with fog, it may be better for the explorer not to head for the center of the largest fog, but instead follow a pattern that follows the edge of that fog. This is for two reasons. One, often it is more important to explore near your base, rather than venture out aimlessly into the fog. Two, this would result in exploring a blob of fog more efficiently, because spiraling toward the center of a blob is more efficient than crisscrossing a blob, splitting it into small strips that need to be revisited.