Return to Answer

You can make the grid size of each array twice as big as the last one, and let each tile in the lower-resolution grids equal to the maximum value of the smaller tiles it covers, see the figure below.

That way they would be very easy and fast to update. For each lower-res array you get the wanted index by simply dividing by 2. When a tile's value is changed it will be pretty straight forward to update all the arrays.

If a tile's value is increased, set the value of all the covering tiles to max(newValue,currentValue).

When a tile's value is decreased, refresh the covering tiles to make sure they have the correct value. You can be clever about this and compare the previous value with the new one and only update if neccessary, or just check all the tiles in the most detailed array and use the highest. This update is really fast anyways since you aren't rebuilding the whole array but just updating the affected tiles, so it shouldn't matter.

If you use this method, you will have to be careful not to make any passages narrower than double the dimension of the tiles in the lowest-resolution array, or the PF might not find the optimal path.

You might also find this article interesting, if you haven't already read it: http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php

You can make the grid size of each array twice as big as the last one, and let each tile in the lower-resolution grids equal to the maximum value of the smaller tiles it covers, see the figure below.

That way they would be very easy and fast to update. For each lower-res array you get the wanted indices by simply dividing by 2. When a tile's value is changed it will be pretty straight forward to update all the arrays.

If a tile's value is increased, set the value of all the covering tiles to max(newValue,currentValue).

When a tile's value is decreased, refresh the covering tiles to make sure they have the correct value. You can be clever about this and compare the previous value with the new one and only update if neccessary, or just check all the tiles in the most detailed array and use the highest. This update is really fast anyways since you aren't rebuilding the whole array but just updating the affected tiles, so it shouldn't matter much for performance.

If you use this method, you will have to be careful not to make any passages narrower than double the dimension of the tiles in the lowest-resolution array, or the PF might not find the optimal path.

You might also find this article interesting, if you haven't already read it: http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php

You can make the grid size of each array twice as big as the last one, and let each tile in the lower-resolution grids equal to the maximum value of the smaller tiles it covers, see the figure below.

That way they would be very easy and fast to update. For each lower-res array you get the wanted index by simply dividing by 2. When a tile's value is changed it will be pretty straight forward to update all the arrays.

If a tile's value is increased, set the value of all the covering tiles to max(newValue,currentValue).

When a tile's value is decreased, refresh the covering tiles to make sure they have the correct value. You can be clever about this and compare the previous value with the new one and only update if neccessary, or just check all the tiles in the most detailed array and use the highest. This update is really fast anyways since you aren't rebuilding the whole array but just updating the affected tiles, so it shouldn't matter.

If you use this method, you will have to be careful not to make any passages narrower than double the dimension of the tiles in the lowest-resolution array, or the PF might not find the optimal path.

You can make the grid size of each array twice as big as the last one, and let each tile in the lower-resolution grids equal to the maximum value of the smaller tiles it covers, see the figure below.

That way they would be very easy and fast to update. For each lower-res array you get the wanted index by simply dividing by 2. When a tile's value is changed it will be pretty straight forward to update all the arrays.

If a tile's value is increased, set the value of all the covering tiles to max(newValue,currentValue).

When a tile's value is decreased, refresh the covering tiles to make sure they have the correct value. You can be clever about this and compare the previous value with the new one and only update if neccessary, or just check all the tiles in the most detailed array and use the highest. This update is really fast anyways since you aren't rebuilding the whole array but just updating the affected tiles, so it shouldn't matter.

If you use this method, you will have to be careful not to make any passages narrower than double the dimension of the tiles in the lowest-resolution array, or the PF might not find the optimal path.

You might also find this article interesting, if you haven't already read it: http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php

You can make the grid size of each array twice as big as the last one, and let each tile in the lower-resolution grids equal to the maximum value of the smaller tiles it covers, see the figure below.

That way they would be very easy and fast to update. For each lower-res array you get the wanted index by simply dividing by 2. When a tile's value is changed it will be pretty straight forward to update all the arrays.

If a tile's value is increased, set the value of all the covering tiles to max(newValue,currentValue).

When a tile's value is decreased, refresh the covering tiles to make sure they have the correct value. You can be clever about this and compare the previous value with the new one and only update if neccessary, or just check all the tiles in the most detailed array and use the highest. This update is really fast anyways since you aren't rebuilding the whole array but just updating the affected tiles, so it shouldn't matter.

If you use this method, you will have to be careful not to make any passages narrower than double the dimension of the tiles in the lowest-resolution array, or the PF might not find the optimal path.

You can make the grid size of each array twice as big as the last one, and let each tile in the lower-resolution grids equal to the maximum value of the smaller tiles it covers, see the figure below.

That way they would be very easy and fast to update. For each lower-res array you get the wanted index by simply dividing by 2. When a tile's value is changed it will be pretty straight forward to update all the arrays.

If a tile's value is increased, set the value of all the covering tiles to max(newValue,currentValue).

When a tile's value is decreased, refresh the covering tiles to make sure they have the correct value. You can be clever about this and compare the previous value with the new one and only update if neccessary, or just check all the tiles in the most detailed array and use the highest. This update is really fast anyways since you aren't rebuilding the whole array but just updating the affected tiles, so it shouldn't matter.

If you use this method, you will have to be careful not to make any passages narrower than double the dimension of the tiles in the lowest-resolution array, or the PF might not find the optimal path.