Feature proposal: DijkstraMaps with 'weighted' starts.

[dwino]

(First time opening an issue, so sorry if I did something the wrong way.)

I wanted to try out the 'Desire-driven ai' like it is explained in these two articles :

• The Incredible Power of Dijkstra Maps (4th section)
• Dijkstra Maps Visualized (heading: -- Variable strengths, and what distance really means --)
  -> The second article proposes a different implementation, but the idea is the same. I used this implementation.

These articles explain it better than me, but the idea is:
The starting points for the dijkstra map can have any float value (even negative values).
This way it is possible for the 'next lowest exit' to be towards a certain starting point that is 'further away' (in number of tiles/nodes) than ones that are 'closer' (in the same way), because the flow of the map is weighted more towards the the starting point that has a more negative value, this could represent two different desires, with one winning from the other even though it's fulfillment is further away. Sorry if this doesn't make sense, the articles will make sense, I promise.

I looked for a way to do this with bracket-lib's DijkstraMap, but as far as I can tell you can only supply your starting point(s),
but not their 'weights'. I went through the source code for DijkstraMaps and
saw that the weight of the starting points is hard-coded to '0.0'.
source code (line 124 & 166):

I copied the entire 'dijkstra.rs' file, changed the naming too "WeightedDijkstraMap", made the 'starts' parameter accept a collection of tuples (with the first value being the index for the point, the second the weight) and changed it so that is uses the supplied value instead of 0.0 where necessary. I have no idea how the 'threaded' code works, I just copied it and made the relevant changes (I think). I added my code as a text file.

I tested it in a toy example and is seems to work ( an entity I spawn on the map moves towards a tile that is further away, because the starting weight of it was much more negative than the one that is closer).

Because it was such a small change that I had to make,
maybe it could be included as a feature (assuming it works the way I think it works).
I think the two articles do the rest of the work of showing why it would be an interesting feature.

I thought of two ways to do it (there are probably other / better ways):

• Like I solved it now: Add a separate 'DijkstraMap' struct with this functionality, named to convey the difference.
• Add extra new(), build() and other necessary functions to the existing implementation, allowing weighted starting points.

My code :
weighteddijkstramap.txt

[thebracket]

This would be a great idea. I'll add it to the list - thank you.

[thebracket]

I've added a build_weighted and new_weighted set of functions to Dijkstra, allowing you to provide a tuple (index, weight) for your starts. I went with a new set of methods to preserve backwards compatibility. This is only minimally tested. I did add an example that uses it, and it looks right.