Paul! Glad you chimed in!
Before I reply, I want to say that I know you are a MUCH better programmer than I and probably have alot more experience than I. So, if I question or disagree in any way, don't take it personally - it is probably due to a misunderstanding on my part, BUT it could also be due to a misunderstanding on your part of what I am trying to say. Basically, I am THRILLED to have your input in this or any discussion and I really appreciate how well you comment your code...in short: Respect!
I really do understand the differences between Heat Map, influence maps, potential fields, etc, but the basic mechanics of how they are generated is pretty much the same: with Dijkstra's algorithm. Am I right? With a heatmap or Influence map, the distance values are saved in the map, whereas with potential fields, it goes one step further and saves the vectors as well. Am I right?
according to this guy:
he says:
Vector field pathfinding is composed of three steps.
(1) First, a heatmap is generated that determines the path-distance between the goal and every tile/node on the map.
(2) Second, a vector field that designates the direction to go in to reach the goal is generated.
and then:
This vector field is generated one tile at a time by looking at the heatmap. The x and y components of the vector are calculated separately, as shown in the pseudocode below:
1 - Vector.x = left_tile.distance - right_tile.distance
2 - Vector.y = up_tile.distance - down_tile.distance
with that said, I don't think my 'heatmap' generation routine is 'wrong', it does not go on and then generate the vectors for a Flow Field, but I don't see how that helps much.
I also am aware of how to incorporate terrain costs... in my example, I am just using a Breadth-First search/fill - it will take very little to change it to Dijkstra's algorithm and incorporate Terrain Costs as you did in your nice example.
Now, as far as 'slow' or 'fast'...
One agent using A* to path to a location will be faster than generating an entire Heatmap (or Vector Field), correct?
Having 1000 agents using A* to path to different locations will be much slower than generating an entire Heatmap/Vector Field.
It ALSO depends on how large the map is because the size of the overall map does not matter to A*, whereas a Heatmap takes longer in porportion to the overall size of the map.
I would like a VERY large map.....
This slowdown of generating a Heatmap (forgive me for continually using this term, I am just so used to using it loosely) can be mitigated by figuring out a routine that only regenerates the portion that has changed...as I stated in the first post.
So, the question comes down to: How many Agents will pathfind with the same HeatMap BEFORE something alters that Heatmap?
For Trees, probably alot which is why I choose to use a Heatmap for Tree Objects.
But not for agent to agent pathfinding (agent A paths to agent X, agent B paths to agent Y, agent C paths to agent M, or, agent D paths to Object A, agent E paths to Object B,etc) , where each agent is probably moving in some fashion so that MULTIPLE heatmaps would have to be re-generated each game loop (almost), then A* is probably the best way.
Although is not shown here, you can smooth paths simply by a weighted average of the surrounding nodes to get continuous instead of discrete movement.
really? That is a nice way to do it! can't wait to test that! - I was thinking of using a version of "string pulling" to smooth, with possibly some adjust near blocking tiles/objects so that agents don't hug the walls and such....
Hold on, you just posted your 'connectivity map/graph' thing and it IS very interesting... questions coming....