weight of nodes

[xpoveda]

Hi, first of all congratulations for this great implementation and pretty object oriented definition of A* algorithm.

On the other hand I have found a little issue. The algorithm don't use the weight of nodes.

By example with these matrix:

short[,] matrix2 = {
{8, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{2, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 9}
};

short[,] matrix2 = {
{8, 2, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 9}
};

The result for origin and target 8 and 9 is the same using Manhattan heuristic (tried with another heuristics and the same).
0,0 1,0 2,0 3,0 4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8 4,9

Is possible a little change to use too the weight of the nodes?

Thanks so much!!

Xavier.

[xpoveda]

Solved:

                // XPN
                // var newG = q.G + DistanceBetweenNodes;
                var newG = q.G + DistanceBetweenNodes + _world[successor.Position];
                // XPN ADDED WEIGHT CALCULATE

...

                // XPN
                // var updatedSuccessor = new PathFinderNode(
                //     position: successor.Position,
                //     g: newG,
                //     h:_heuristic.Calculate(successor.Position, end),
                //     parentNodePosition: q.Position);
                var updatedSuccessor = new PathFinderNode(
                    position: successor.Position,
                    g: newG,
                    h:_heuristic.Calculate(successor.Position, end) + _world[successor.Position],
                    parentNodePosition: q.Position);
                // XPN ADDED WEIGHT CALCULATE

Thanks so much :)

[valantonini]

Hi @xpoveda,

Thank you for the kind words and apologies for the delay. That is exactly how I would do it! A user hard reached ouut with a similar problem in the past and I wrote a short blog post on it. Ran a couple tests at It did appear to work but wasn't confident merging it in. Let me know if you have success with this approach and I'll updated the library to support it out of the box.

thanks again,

val

[xpoveda]

Hi Val, thanks so much for your answer 😀.

I have tested my solution only with manhattan heuristic and horizontal/vertical movement.

In this case works perfect.

I don't have tested anothers use cases by the moment, when I do I'll let you know.

Xavier.

[valantonini]

Hi @xpoveda,

Since this has been asked a few times, I have implemented weightings. It can be opted into via options to maintain backwards compatability for those who rely on the current behaviour. Looking at your implementation, I believe you will want a negative weighting.

var level = @"1111115
              1511151
              1155511
              1111111";
var world = Helper.ConvertStringToPathfinderGrid(level);
var opts = new PathFinderOptions { Weighting = Weighting.Negative };
var pathfinder = new PathFinder(world, opts);

A prerelease of this can be found on Nuget