I am currently brainstorming strategies on how to compute the distance in a 2D array, of all points from sets of points with specific attributes. A good example (and one of my likely uses) would be a landscape with pools of water on it. The idea would be to calculate the distance of all points in this landscape from water.
These are the criteria that I would like to abide to and their reasoning:
1) Execution speed is my greatest concern. The terrain is dynamic and the code will need to be run in a semi continuous manner. What I mean by that is that there are be periods of terrain updates which will require constant updates.
2) Memory overhead is not a major concern of mine. This will be run as the primary application.
3) It must be able to update dynamically. See #1 for the reasons behind this. These updates can be localized.
4) Multi-threading is a possibility. I am already make extensive use of multi-threading as my simulation is very CPU intensive. I'd prefer to avoid it since it would speed up development but I can do it if necessary.
I have come up with the following possible approach and am looking for feedback and/or alternative suggestions.
1) Iterate through the entire array and make a collection positions in a container class corresponding to points are next to those with the particular property. Assign a value of 1 to these points and 0 to the points with the property.
2) Use the positions to look up those points adjacent to them that are the next distance away, place them in a second container class.
3) Repeat this process till no points are left unsigned.
4) Save the list of points directly one unit away for future updates.
The idea is to basically flow outward from distance 0, and save computation by continually narrowing the list of points in the loop.
1) The only other way of doing this well, which I can think of, would be with the Cartesian distance formula, but your way seems like it would have less CPU time (since the Cartesian way must calculate to every point on each point).
2) Or, if I understand your desire correctly, you could iterate through once, saving all of the points with your special attribute in a container (point to them), and then iterate through one more time, only using the distance formula from each iteration to each of the saved points (then repeat). Please comment and ask about it if this explanation is unclear. It's late, and I am quite tired.
If you want to run this comparison in the background, you have no choice but to multi-thread the whole program. However, whether or not to multi-thread the functionality of this process is up to you. If you go with the second option I provided, I think you will have cut down enough CPU usage to forgo multi-threading the process in question. The more I think about it, the more I like the second option.