Handle fog-of-war

[dkniffin]

Currently, it looks like the pathfinding algorithm doesn't take fog-of-war into account at all. If a token hasn't explored an area, it should treat the edge of the unexplored area as a wall, and not route through it.

[manuelVo]

I'd love for routinglib to take fog of war into account. However, I currently haven't found a way to do so efficiently. Foundryvtt stores fog of war as a bitmap, where a white pixel indicates that an area is explored while a black pixel means that that are is hidden. Routinglib on the other hand works with vector data, where it needs to check if moving from coordinate x to coordinate y is possible (with x and y not necessarily being right next to each other). Any input for ideas on how to solve this are greatly appreciated and may lead to future support for fog of war.

[dkniffin]

@manuelVo Hmm. Perhaps it could do something like this? https://stackoverflow.com/questions/42595343/bitmap-to-svg-path

Not sure how performant that would be. It would need to run something like that every time the FOW updates, I think. Maybe there's some way to intelligently ignore the previously calculated visible areas, to make it quicker. Or even better, only recalculate the newly explored areas, if that data is available. I'm not sure how the API and events for this work.

[dkniffin]

@manuelVo This library might also be useful: https://www.npmjs.com/package/bitmap2vector

[manuelVo]

To give a bit of context about what I mean by efficient: The gridless pathfinder (which is the slower of the two) has a runtime of O(n²), where n is the number of walls (or more generally, edges that a token isn't allowed to step over). Admittedly, I haven't done any Benchmarking on this, but I feel creating a vector like suggested in that Stackoverflow answer would yield enough edges to cause a significant drop in performance.

Here are a few more performance-related insights: To allow players with slower computers to use routinglib on large maps with many edges, routinglib will only once generate a graph from the given map data, that indexes if it is legal to move between two given points and how much the cost for that move is. Once the graph is created it'll re-use that graph as much as possible. The slowdowns mentioned above only affect initial graph creation and once the graph is complete, no further performance penalty applies. Usually this graph stays valid as long as the same scene remains loaded and the walls aren't modified. However, once routinglib takes fog of war into account, that graph will become invalid as soon as the fog of war changes (which might happen at every single token drag). So we need to do one of two things:

• Delete the cached graph so it'll be re-generated with the updated data on next use
• Somehow update the graph to reflect the changes that have been done to the fog of war

In my current performance estimations, I'm assuming that it's necessary to do the former. Any good ideas on how to do the latter might allow us to use a more expensive algorithm during graph generation, so that's another possible avenue for input.

[dkniffin]

@manuelVo That's great info! I want to dig into this a bit more. Can you point me towards the docs on that FOW bitmap you mentioned?

[manuelVo]

I'm not aware of any documentation on this. My knowledge comes entirely from poking around in the vision code for the Lichtgeschwindigkeit module. That was back in Foundry 0.8, so my knowledge of this might be outdated at this point, so take what I was saying with a grain of salt. In any case, if you're interested in digging into this, canvas._fog looks like a good place to start in Foundry v11.

[dkniffin]

@manuelVo What if we convert the bitmap to a 2d array of 0 and 1, then here, we check all the values between the start/end points, and reject the path if it crosses any non-visible points. We would need to do a translation between coordinate systems, but that should be quick, I think. For checking the array, I think we could write it in a way that doesn't have to loop through the whole array, but instead just the start and endpoints. I think that would be pretty efficient, right? Not sure what the O() would be though.

[dkniffin]

Perhaps there's also a way to simplify that array once it's calculated, to make it even easier to check 🤔 I'm not very good at linear algebra and matrices though 😅 Or maybe there's even a fancy matrix math way to do that check without the loops

[dkniffin]

I made an extremely rough test of what this might look like. For the data in explored here, I copy/pasted the value from my canvas._fog.exploration.explored. I'm running this on a dummy html file with a single element: <canvas id="cv"></canvas>

var explored = "data:image/jpeg;base64,..."

var canvas = document.getElementById("cv")

var ctx = canvas.getContext("2d");

var image = new Image();
image.onload = function() {
  canvas.width = image.width;
  canvas.height = image.height;
  ctx.drawImage(image, 0, 0);
};
image.src = explored

var checkVisibility = (x, y) => {
  var imageData = ctx.getImageData(x, y, 1, 1)
  return imageData[1] > 0
}

for(var i = 0; i < 100; i++) {
  for(var j = 0; j < 100; j++) {
    console.log(`${i}, ${j}`)
    console.log(checkVisibility(i, j))
  }
}

It seems to run decently fast. But I don't know the big-O of it, because I don't know how fast getImageData is.

Instead of the loop at the bottom, of course we'd want to loop over all x,y coordinates the token would move through. And as I understand it, we'd need to do that for all possible paths, right?

I'll try later or sometime soon to see if I can integrate this more into a real example.

[manuelVo]

This could actually work. Since this check would only run once, either before or after the collision checks with walls, it won't affect the hot O(n²) loop, so I suppose performance could be decent enough. This need some testing before I can say for sure though.

[dkniffin]

@manuelVo It would only run once per path, correct. I think it's O(m), where m is the set of x,y coords that make up a path. So linear time, I think, and for a small set. That should be really fast, I think

I'd say we should run the faster of these two checks first, that way we only run the slower one for paths that we know will work for the other.

[manuelVo]

I've been thinking about this a bit more, and I think the most efficient way would be this: Have the graph store for each edge not only the cost of taking the edge (null if the edge cannot be taken because of a wall), but store three separate data points: Whether a wall is blocking the move in that direction, whether fog of war is blocking a move in that direction, how much the move would cost. Each of the values can be undefined if it hasn't yet been evaluated.

When an edge is requested, the execution order is as follows:

1. Check whether the graph indicates that a wall blocks movement along that edge. If the value is set to undefined, do that check (which is the extremely expensive one I've been talking about) and store the result in the graph. If a wall turns out to be blocking that move, stop execution and report the edge as unusable.
2. Check whether the graph indicates that fog of war blocks movement along that edge. If the value is set to undefined, do that check and store the result in the graph. If fog of war blocks the move, stop execution and report the edge as unusable.
3. Check if the graph has information on how expensive the edge is. If not, calculate the cost and store the result in the graph. Then report the edge as usable and return the cost.

Now, if the fog of war is updated, we don't need to invalidate the entire graph. We just need to set the fog of war indicator on each edge to undefined so it'll be recalculated upon next use. The indicator whether a wall is blocking the movement and the cost of the edge remain intact and don't need to be recalculated.

In contrast to your suggestion, this puts the more expensive calculation (whether a wall is blocking the movement) first. However, I suppose that the fog of war will be updated much more frequently during a game session than the walls, so we're performing the more stable check first. As a result, we can skip many of the fog of war calculations, because a wall is blocking the path anyway leading to us needing to do much fewer recalculations do to fog updates than if we were to do the fog calculation first.

[dkniffin]

@manuelVo makes sense to me!