A journey of 1000 steps

AIM:

Commence development of pathfinding

CONDUCT:

  • 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)

RESULTS:

Graph creation:

  • 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.

Top down view showing enemy position areas in and out of line of sight with path from friendly position avoiding areas in enemy line of sight and taking shortest path given terrain undulations
Final output from pathfinding (Green path) given terrain undulations and enemy (Black circle) position viewshed from friendly location (Blue dot) to target location (Black square above enemy position)

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.

Edit:

Continued work on testing. Fixed one bug with stack path being returned. Now runs well in real time. Example visualisations below.

3D isometric view of animated target position moving around terrain with path between friendly location and target position.
Path (marked in white) demonstration between friendly location and target location given enemy position and observation. Note the path avoids the areas the enemy can see as much as possible (Completely avoids unless path destination is in LOS – then minimises time in LOS). Terrain data is 139×139 (~20k points)
Same demonstration as before without enemy LOS visible. Easier to identify terrain undulations.
Same demo as before but with 1390×1390 data points (~ 2 million total). Slight FPS drop due to unoptimised path visualisation only. 

TODO:

  • 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

TIME SPENT:

7 hours (54 hours running total)

After edit:

3 hours (57 hours running total)

DISCUSSION:

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s