digitsensitive / astar-typescript

A* search algorithm in TypeScript
MIT License
87 stars 18 forks source link

[Feature] Node cost #15

Open wlfio opened 3 years ago

wlfio commented 3 years ago

Whilst working on my own project i found i wanted to include a cost into node, so that the pathing would avoid them if possible.

So I have implemented it and will let you decide if you want it. (this also addresses issue #14)

I have implemented it so that it is non breaking, as it only enables if the developer sets a previously non existant option.

0 = walkable 2 = walkable but not prefered 5 = not walkable

let myMatrix = [
  [0, 0, 2, 2, 2, 2, 0, 0],
  [0, 0, 2, 2, 2, 2, 0, 5],
  [0, 0, 5, 5, 0, 5, 5, 0],
  [0, 0, 5, 0, 0, 0, 5, 0],
  [0, 0, 0, 0, 0, 0, 5, 0],
  [5, 5, 5, 0, 5, 0, 5, 0],
  [0, 0, 0, 0, 5, 0, 5, 0],
  [0, 0, 5, 0, 0, 0, 0, 0]
];

this.aStarInstance = new AStarFinder({
  grid: {
    matrix: myMatrix,
    maxCost: 5,
  }
});

Examples:

I wanted the wires to avoid blocking the pins on the chips if possible to make it easier for later wire to path to them.

2020-08-24_00-45-35_firefox

So with my cost feature i added an extra cost to the nodes just above and below a chip. now it paths like this.

2020-08-24_00-44-50_firefox

But if it MUST go into a space because going around is impossible or far too costly it will

2020-08-24_00-46-04_firefox

Developers using the feature can set their own cost values to make things even les desirable if they wished, this could for instance be used in a game to avoid different types of terrain if possible, unless the path arround is far too long.