Commence development of pathfinding
- Implemented graph of terrain nodes with connected edges
- Implemented cost field calculations
- Implemented vector field for complete graph given a target location (which is friendly position in this instance. This means each point on the terrain can navigate back to the friendly position – or in other words a path can be created to any position on the terrain from the friendly location)
- 27×27 grid (729 data points) : 15ms
- 139×139 grid (~19k data points) : 407ms
- 278×278 grid (77k data points) : 1665ms
- 1390×1390 grid (1.9 million data points) : 49663ms
- 1000×1000 grid (5k by 5k grid with 5m sampling) : 24062ms
Graph and cost field/vector field creation with one path tracked:
- 27×27 grid (729 data points) : 34ms
- 139×139 grid (~19k data points) : 635ms
- 278×278 grid (77k data points) : 3270ms
- 1390×1390 grid (1.9 million data points) : 101448ms
- 1000×1000 grid (5k by 5k grid with 5m sampling) : 48959ms
Output demo visualised below. Note the avoidance of enemy line of sight and fastest path given terrain undulations.
The pathing is quite efficient too. A test with a 1000×1000 grid generated (5k by 5k grid with 5m sampling, total generation time of 42841ms) with 100 000 paths subsequently requested was conducted. The total time spent on the path requests was 12559ms. A test with 1 million path requests in the same scenario took a total of 113149ms.
It should be noted that while it is a good result for time for number of path requests, given the preprocessing there isnt even a need for a path request until the final locations have been determined. All the information required for planning (which would otherwise require a pathing request with a different pathing solution) is present in the cost field.
Continued work on testing. Fixed one bug with stack path being returned. Now runs well in real time. Example visualisations below.
- Implement data classes for core element variables. eg. The viewshed can take in viewer height etc. The Edge class calculates cost based on viewshed values (eg. currently more than 5m clearance will put a 0.1 modifier on cost, 1.5-5m will put a 1x modifier on and less than 1.5m will put a 10000x modifier on.
- Create a planning data class which is the overarching container for all the preprocessing classes already created. Implement the above data classes (eg. ViewshedConstructionInfo) into the planning data class. Use this class as the main interface for all future operations
7 hours (54 hours running total)
3 hours (57 hours running total)
Moving forward. We are now finally at a point where the major preprocessing requirements have been implemented! This means it is (finally) time to start looking towards solving the actual problem. I will definitely revisit the stuff I have done so far in order to provide relevant helper methods etc that things like the fitness function may require but the heavy lifting is now done!
The only other addition that falls under the ‘preprocessing’ step would be to identify and store FUP and SBF candidate locations however that will evolve as we go through the planning process.
Optimisation reflection. It appears as though the graph creation may be a bottleneck much more than the viewshed calculations. This was somewhat of a surprise however is pretty clear with a bit of consideration.
I have heard someone say that ‘premature optimisation is the root of all evil’ or alternatively, get it working then get it working fast. This is a great example of why they are reasonable statements. My early thoughts on how I could optimise the viewshed calculation involved multithreading parts to get up to a 75% reduction (pure best case) in viewshed creation time. In this instance though the viewshed is a fraction of the total preprocessing time. This means that what would have been a somewhat complicated endeavour (and added in more potential bugs and a fair bit of development time) would have ended up providing negligible benefit overall. The optimisation thoughts are still valid and it definitely has merit for use in something that required real time viewshed calculations but for now, it is not something I will pursue. I will potentially look at optimising the graph creation process down the line though.