Applying Graph Based (Node Map) shortest-path algorithms

[rishabsingh3003]

Most graph bases algorithms (Djikstras, A* etc) require a set of nodes. Now the algorithm has already been designed and implemented, but how you assign nodes is extremely important. For reference: The algorithm must be fast enough to run(give the shortest path per bot) at least 4-5 times a second.
Applying Djisktra's on 40 nodes takes < 40 ms to run, applying it on 40*40 nodes takes about 30 seconds to run (On my i7 processor).

Therefore, a good scheme needs to be developed to mark the nodes on the plane(I.e node map). One good way to do this (inspiration taken from ArduPilot), is to mark the nodes in the following way:

1. One node at the current location of the bot
2. One node at the goal location
3. Multiple nodes (I guess around 4 or more?) around the obstacles.

To see the third point graphically:

Here "0" node corresponds to starting location of the bot
"1" node corresponds to goal location
Nodes "2" - "5" are margin nodes of the obstacle.

Therefore, the bot can travel from one node to node, as per the algorithm, and safely traverse through the obstacle.

Again, this map can be used for any of the "node" based shortest path algorithms. I would suggest we follow this but comment down below any changes that you think might benefit the project.

[rishabsingh3003]

Another way to do this would be to uniformly divide the plane into a set number of N X N nodes. And then delete the nodes that are coinciding with obstacles.

(Red nodes are obstacle nodes, green nodes are the path taken, blue are the available nodes)

But that's a really bad way to approach this problem, and will never work out